Grafické jádro Smalltalku

Daniel H H Ingalls

The Smalltalk graphics Kernel

Byte 1981-08, s. 168

Grafika je pro kvalitu interaktivního programovacího systému a interaktivních aplikací, které jsou s takovým systémem spojeny, zásadní. Lidé kvalitativně myslí pomocí obrázků a každý systém, který není schopen manipulovat s obrázky, není schopen takové myšlení rozšířit. Z kvantitativního hlediska může člověk vizuálně vstřebat informace odpovídající milionům znaků za sekundu, zatímco běžná rychlost čtení textu je méně než 100 znaků za sekundu.

Aby byl cyklus grafické interakce úplný, musí počítačový systém poskytnout kanál pro vstup i ve vizuální oblasti. I když se projekce obrazů z oblasti myšlení do prostoru elektronických informací zdá být nemožným úkolem, dobře navržené ukazovací zařízení může účinně využít grafické výstupní schopnosti počítače k vyjádření grafického vstupu od uživatele. Při použití takového ukazovacího zařízení je proces výběru z grafických objektů, jako je text zobrazený na obrazovce, přirozený a rychlý. Sledováním ukazatele pomocí programu, který simuluje pero nebo štětec, lze kanál vizuálního vstupu rozšířit o kreslení čar a náčrtů z volné ruky.

Účelem grafiky v systému Smalltalk je podpora reaktivního principu:

Každý objekt přístupný uživateli by měl být schopen prezentovat se smysluplným způsobem pro pozorování a manipulaci.

Smysluplná prezentace jakéhokoli objektu v systému vyžaduje maximální kontrolu nad zobrazovacím médiem a mnoho technologií v tomto ohledu zaostává. Jedním z přístupů, který poskytuje potřebnou flexibilitu, je umožnit nezávislé ovládání jasu každého rozeznatelného bodu zobrazeného obrazu. Nejjednodušší implementací tohoto přístupu je souvislý blok paměti, v němž je nastavení každého bitu (1 nebo 0) mapováno na tmavé nebo světlé osvětlení příslušného obrazového prvku, resp. pixelu, při zobrazení nebo kombinaci s jinými obrazy. Blok paměti se proto označuje jako bitová mapa a tento typ zobrazení se nazývá bitmapové zobrazení. Nejjednodušší forma bitmapy umožňuje pouze dvě úrovně jasu, bílou a černou. Na tomto modelu je postaven grafický systém Smalltalk-80.

Foto 1 ukazuje typický pohled na systém Smalltalk-80 a ilustruje širokou škálu grafických idiomů, které jsou implikovány reaktivním principem. Obdélníkové plochy libovolné velikosti jsou vyplněny bílou, černou a různými polotónovými vzory. Text v různých typech písma je na obrazovku umístěn z uložených obrazů jednotlivých znaků. Malování "volnou rukou" je docíleno "rozmazáním poltónových osdtínů. Kromě toho, ačkoli se na tištěné stránce nezobrazují, lze obrázky na displeji pohybovat nebo je řadit v čase, čímž vzniká animace.

Grafické úložiště - formuláře

Jednotlivé obrázky jsou reprezentovány instancemi třídy Form. Formulář má výšku a šířku a bitmapu, která označuje bílé a černé oblasti konkrétního reprezentovaného obrázku. Uvažujme například Form ve tvaru šipky, který se objevuje v pravém dolním okně obrázku na fotografii 1. Vnitřní reprezentace tohoto Form je znázorněna na obrázku 1. Jeho výška je 16, šířka 8 a jeho vzhled je popsán vzorem jedniček a nul (zobrazených jako světlé a tmavé čtverce) v jeho bitmapě. Výška a šířka formuláře slouží k tomu, aby se jinak nestrukturovaným datům v bitmapě vnutilo vhodné dvourozměrné uspořádání. K reprezentaci Formulářů se v tomto článku podrobněji vrátíme později.

Složitý obrázek lze reprezentovat dvěma způsoby: pomocí velmi rozsáhlého Formuláře nebo pomocí struktury, která obsahuje mnoho Formulářů a pravidel pro jejich kombinování a opakování za účelem vytvoření požadovaného obrázku. Kresba od ruky uprostřed fotografie 1 je příkladem první varianty a text pod ní je příkladem druhé varianty.

Velký nestrukturovaný Formulář má další velmi důležité použití: může být předložen zobrazovacímu zařízení jako vyrovnávací paměť skutečných dat, která se mají zobrazit na zobrazovacím terminálu. Takto použitý Form označujeme jako displayForm. Protože rozhraní s hardwarem probíhá prostřednictvím Form, není rozdíl mezi interním kombinováním obrázků a jejich zobrazením na displeji. Animaci lze provést jednoduše tímto způsobem: jeden Form slouží jako displayForm, zatímco další obrázek, který má být zobrazen, je připraven v druhém Form. Po dokončení každého obrázku si oba Formuláře vymění role, čímž se zobrazí nový obrázek a Formulář se starým obrázkem je k dispozici pro sestavení dalšího obrázku v pořadí.

Grafická manipulace - BitBlt

Pro podporu široké škály grafických prezentací jsme specifikovali operaci jádra na Formulářích, kterou nazýváme BitBlt. Všechny textové a grafické objekty ve Smalltalku se zobrazují a upravují pomocí tohoto jediného grafického primitivu. Autor napsal původní návrh v říjnu 1975 s radou a podporou Diany Merry. Po pěti letech zkušeností jsme pocítili potřebu pouze drobných změn a tato vylepšení jsou z velké části zásluhou Boba Flegala a Billa Bowmana. Zbývající část tohoto článku podrobně popisuje současné primitivum BitBlt - jeho specifikaci, příklady jeho použití a nakonec podrobnosti jeho implementace.

Jeden z prvních počítačů, na kterém byl implementován systém Smalltalk, měl instrukci nazvanou BLT pro blokový přenos 16bitových slov. Název BitBlt je odvozen od zobecnění přenosu dat na libovolná bitová místa neboli pixely. BitBlt je záměrně velmi obecná operace, i když většina jejích aplikací je graficky jednoduchá, například "přesuň tento obdélník pixelů odsud tam."

Konkrétní aplikace BitBlt se řídí seznamem parametrů, který zahrnuje:

• destForm - Formulář, do kterého budou pixely uloženy pomocí BitBlt

• sourceForm - Formulář, ze kterého mohou být pixely zkopírovány

• halftoneForm - Formulář obsahující prostorový polotónový vzor

• combinationRule- Celé číslo určující pravidlo pro kombinaci odpovídajících pixelů zdrojového a destForm

• destX, destY, width, heightIntegers určující obdélníkovou podoblast, která má být vyplněna v cíli

• clipX, clipY, clipWidth, clipHeight - Celá čísla určující obdélníkovou hranici, která dále omezuje ovlivněnou oblast cíle - sourceX, sourceY - Celá čísla určující umístění (vlevo nahoře) podoblasti, která má být zkopírována ze zdroje.

Ve zbývající části této kapitoly podrobněji prozkoumáme vliv každého z těchto parametrů.

Formuláře zdroje a cíle

Obrázek 2 znázorňuje proces kopírování znaku textu do oblasti na displeji. Tato operace poslouží k ilustraci většiny vlastností BitBlt. Operace kopírování zahrnuje dva formuláře, zdrojový a cílový. Zdrojem v tomto příkladu je písmo obsahující sadu znakových glyfů vyobrazených v určitém jednotném stylu a měřítku a vodorovně zarovnaných k sobě. Pixely jsou kopírovány ze zdroje (písma) a ukládány do cíle (displeje). Šířka a výška přenosu odpovídají velikosti znaku. Souřadnice x a y zdroje udávají polohu znaku v písmu a souřadnice cíle určují polohu na displeji, kde se zobrazí jeho kopie.

Překlipovací obdélník

Ve své specifikaci obsahuje BitBlt obdélník, který omezuje oblast cíle, kterou lze ovlivnit jeho operací, nezávisle na ostatních parametrech cíle. Tento obdélník nazýváme ořezávací obdélník. Často je žádoucí zobrazit částečné okno na větší scény a ořezávací obdélník zajišťuje, že všechny prvky obrazu spadají do hranic okna. Díky jeho začlenění do primitivu BitBlt lze funkci ořezávání provádět efektivně a na jednom místě, místo aby byla replikována ve všech aplikačních programech. Obrázek 3 znázorňuje výsledek vnucení ořezávacího obdélníku na příkladu z obrázku 2. Pixely, které by byly umístěny mimo ořezávací obdélník (levý okraj písmene "N" a polovina slova "the"), nebyly přeneseny. Pokud by se ostatní znaky nacházely nad nebo pod tímto obdélníkem, byly by oříznuty podobně.

Půltónový Form

Často je žádoucí vyplnit oblasti pravidelným vzorem, který vytváří efekt šedého stínování nebo textury. Za tímto účelem umožňuje BitBlt odkaz na třetí formulář (halftoneForm), který obsahuje požadovaný vzor. Tento Formulář je omezen na výšku a šířku 16. Je-li zadáno polotónování, tento vzor se efektivně opakuje každých 16 jednotek horizontálně i vertikálně po celém cíli. Existují čtyři "režimy" dodávání pixelů ze zdroje a polotónů, které se řídí elidingem (dodáním nil pro) sourceForm nebo halftoneForm:

• Režim - Žádný zdroj, žádný polotón (dodává plnou černou)

• Režim 1 - Pouze polotón (dodává polotónový vzor)

• Režim 2 - Pouze zdroj (dodává zdrojové pixely)

• Režim 3- Zdroj a polotón (dodává zdrojové bity maskované polotónovým vzorem)

Obrázek 4 znázorňuje účinek těchto čtyř režimů se stejným zdrojem a cílem a běžným šedým polotónem.

Kombinační pravidlo

Všechny výše uvedené příklady uložily své výsledky přímo do cíle. Ve skutečnosti existuje mnoho možných pravidel pro kombinaci každého zdrojového prvku S s odpovídajícím cílovým prvkem D, aby vznikl nový cílový prvek D'. Takové pravidlo musí specifikovat bílý nebo černý výsledek pro každý ze čtyř případů, kdy zdroj je bílý nebo černý a cíl je bílý nebo černý.

Obrázek 5 ukazuje pole se čtyřmi buňkami odpovídajícími čtyřem případům, které se vyskytují při kombinaci zdroje (S) a cíle (D). Například buňka s číslem 2 odpovídá případu, kdy zdroj byl černý a cíl bílý. Vhodným vyplněním čtyř políček bílou nebo černou barvou lze vytvořit políčko, které bude zobrazovat libovolné pravidlo kombinace (celkem existuje šestnáct možných pravidel). Čísla ve čtyřech políčkách se vztahují k zobrazenému pravidlu a k celočíselné hodnotě, která toto pravidlo vybírá. Chceme-li například určit, že výsledek má být černý všude tam, kde je zdroj nebo cíl (nebo obojí) černý, začerníme buňky s čísly 4, 2 a 1. Souvisejícím celým číslem pro určení tohoto pravidla je součet čísel začerněných buněk, neboli 4 + 2 + 1 = 7.

Obrázek 6 graficky znázorňuje čtyři běžná kombinační pravidla. Každé z nich je popsáno kombinačním diagramem, celočíselným číslem pravidla a skutečnou aplikovanou logickou funkcí. Dřívější případ ORing je vidět vlevo uprostřed obrázku. Tento případ se často popisuje jako malování "pod" cílem, protože existující černé oblasti zůstávají černé.

Přístup Smalltalku k BitBlt

V této části představíme rozhraní Smalltalku k BitBlt a podrobně se podíváme na použití BitBlt při zobrazování textu a kreslení čar. K přípravě budete potřebovat další souvislosti, které zde uvedeme před popisem třídy BitBlt.

Kromě třídy Form se při práci s uloženými obrázky hojně používají další dvě třídy, Point a Rectangle. Třídy Point (Bod) obsahují hodnoty souřadnic x a y a používají se pro odkazování na umístění pixelů vzhledem k levému hornímu rohu formuláře (nebo jinému referenčnímu bodu). Podle konvence se x zvyšuje doprava a y dolů, což odpovídá rozložení textu na stránce a směru televizního snímání. Obdélník obsahuje dva body: počátek, který určuje levý horní roh, a roh, který označuje pravý dolní roh popisované oblasti. Třída Bod poskytuje protokol pro přístup k souřadnicím a pro různé užitečné operace, jako je translace a škálování. Třída Rectangle (Obdélník) poskytuje protokol pro přístup ke všem příslušným souřadnicím a další operace, jako je průnik s jinými obdélníky. Může být užitečné všimnout si paralely mezi třídami Point, Rectangle, Form a třídami Number, Interval, IndexedCollection. Čísla indexují kolekce a body indexují formuláře. Intervaly označují dílčí kolekce a Obdélníky označují dílčí formuláře.

Obrázek 7 ukazuje kompletní reprezentaci formuláře uvedeného na obrázku 1. Šířka a výška jsou uloženy jako celá čísla. Skutečné pixely jsou uloženy v samostatné instanci třídy Bitmap. Bitmapy nemají téměř žádný protokol, protože jejich jediným účelem je poskytovat úložiště pro Formuláře. Nemají také žádnou vlastní dimenzionalitu kromě té, kterou promítá jejich vlastní Formulář, ačkoli na obrázku je tato struktura pro přehlednost zachována. Je vidět, že v bitmapě je vyhrazeno místo pro šířku 16; to je projevem hardwarové organizace ukládání a zpracování do 16-bitových slov. Bitmapy mají pro každou řadu pixelů přidělen integrální počet slov. Integrální omezení velikosti řádku usnadňuje pohyb z jednoho řádku na druhý během činnosti BitBlt a během hardwarového skenování obrazovky displeje. I když je toto rozdělení paměti na slova významné na úrovni primitiv, je zapouzdřeno tak, že žádná z grafických komponent vyšší úrovně v systému nemusí brát v úvahu velikost slova.

Třída BitBlt

Nejzákladnější rozhraní k BitBlt je prostřednictvím stejnojmenné třídy. Každá instance třídy BitBlt obsahuje parametry potřebné k zadání operace BitBlt. Protokol BitBlt obsahuje zprávy pro inicializaci parametrů a jednu zprávu, copyBits, která způsobí provedení primitivní operace. Šablona třídy BitBlt je uvedena v tabulce 1.

Stav uchovávaný v instanci BitBIt umožňuje provádět více operací v souvisejícím kontextu, aniž by bylo nutné opakovat všechna nastavení. Například při zobrazování scény v okně displeje se cílový Formulář a ořezový obdélník nemění od jedné operace k druhé. Tato situace se v grafickém jádře vyskytuje často, jak je ukázáno v následující části.

Syntéza obrazu textu

Velká část grafiky v systému Smalltalk se skládá z textu a čar. Tyto vysokoúrovňové entity jsou syntetizovány opakovaným voláním BitBIt. V této a následující části se budeme těmito dvěma důležitými aplikacemi zabývat podrobněji.

Jednou z výhod plynoucích z BitBIt je možnost kompaktně ukládat písma a zobrazovat je pomocí různých kombinačních pravidel. Kompaktní uložení vyplývá z možnosti zabalit znaky vodorovně vedle sebe (jak je znázorněno na obrázku 2), protože BitBIt dokáže extrahovat příslušné bity, pokud je mu dodána tabulka levých x souřadnic všech znaků. Tomuto formátu se říká strike format, což je odvozeno od typografického termínu, který znamená souvislé zobrazení všech znaků v písmu.

Skenování a zobrazení textu provádí v systému Smalltalk-80 podtřída BitBIt. Tato podtřída dědí všechny normální stavy, přičemž destForm označuje formulář, ve kterém se má text zobrazit, a sourceForm označuje formulář obsahující všechny znakové glyfy vedle sebe (jako na obrázku 2). Kromě toho tato podtřída definuje další stavové informace, včetně:

• text - řetězec znaků, které mají být zobrazeny

• textPos - celé číslo udávající aktuální pozici v textu

• xTable - pole celých čísel udávající levé umístění x každého znaku ve sourceForm

• stopX - celé číslo, které nastavuje pravou hranici, za níž má vnitřní smyčka zastavit skenování

• výjimky - pole celých čísel, která, pokud jsou nenulové, označují, že příslušné znaky musí být speciálně zpracovány

Pokud je instance inicializována s daným fontem a umístěním textu, funkce scanWord: Smyčka uvedená v příkladu 1 bude skenovat nebo tisknout text, dokud nebude předána nějaká horizontální pozice (stopX), nebude nalezen speciální znak (určený z výjimek) nebo nebude dosaženo konce tohoto rozsahu textu (endRun). Kontrola výjimek zpracovává mnoho možností v jedné operaci. Se znakem mezery může být nutné zacházet výjimečně v případě textu, který je vycpáván, aby bylo dosaženo zarovnaného pravého okraje. Tabulátory obvykle vyžadují výpočet nebo kontrolu tabulky pro určení jejich šířky. Při kontrole výjimek je identifikován také znak Carriage Return. Kódy znaků mimo rozsah daný písmem se zjišťují podobně a obvykle se řeší zobrazením výjimečného znaku, například malého blesku, aby mohly být viditelné a opravené. Příznak tisku lze nastavit jako nepravdivý, aby stejný kód umožnil změřit řádek (zlom na hranici slova) nebo zjistit, kam ukazuje kurzor. I když se toto ustanovení může zdát příliš obecné, vyplývají z něj (kromě kompaktnosti) dvě výhody. Za prvé, pokud provedeme změnu základního algoritmu snímání, je jisté, že paralelní funkce měření, tisku a sledování kurzoru budou synchronizovány. Za druhé, pokud je pro smyčku k dispozici primitivní implementace, působí na výkonnost systému trojnásobně. Smyčka scanWord: je navržena tak, aby se takové primitivní implementaci podrobila; to znamená, že ji interpret může zachytit a provést primitivní kód místo zobrazeného kódu Smalltalku. Tímto způsobem se lze vyhnout velké části režie nastavení copyBits při každém znaku a lze přímo zobrazit celé slovo nebo více slov. Naopak k zajištění plné funkčnosti vyžaduje textový a grafický systém Smalltalku implementaci pouze jedné primitivní operace.

Kreslení čar, syntéza obrázků

Stejný princip návrhu se uplatňuje při podpoře kreslení čar. Pomocí BitBIt lze jedním algoritmem kreslit čáry různé šířky, různé polotóny "barvy" a libovolné kombinační pravidlo. Pro kreslení čáry se instance BitBIt inicializuje s příslušným cílovým formulářem a ořezovým oknem a se zdrojem, kterým může být libovolný formulář, který se použije jako tvar pera podél čáry. Počínaje uloženými destX a destY přijímá smyčka kreslení čáry, drawLoopX:Y: (příklad 2), hodnoty delta x a y a hodnoty kroku x a y podle potřeby a v každém bodě podél čáry volá copyBits. Použitá metoda je Bresenhamův algoritmus vykreslování (IBM Systems Journal, Volume 4, Number 1, 1965). Vybírá hlavní směr a udržuje proměnnou p. Když se změní znaménko p, je čas se posunout i ve vedlejším směru. Tento postup je další přirozenou jednotkou, která má být implementována jako primitivum, protože výpočet je triviální a nastavení v copyBlt je téměř celé konstantní od jednoho volání k druhému.

Zpracování obrázků

Viděli jsme, jak může BitBlt kopírovat tvary a v předchozích příkladech, jak může opakované volání syntetizovat složitější obrázky, jako je text a čáry. BitBlt je také užitečný při manipulaci s existujícími obrázky. Například text může vypadat tučně tak, že se ORingem přesune přes sebe a posune se o jeden pixel doprava. Stejně jako lze z jednoduchých obrázků sestavit složité, lze opakovaným použitím jednoduchých operací dosáhnout složitého zpracování. Zde uvádíme tři příklady takové strukturální manipulace: zvětšení, rotace a hra Život. Tyto příklady vymyslel autor ve spolupráci s Tedem Kaehlerem.

Jak uvidíme v následujících dvou částech, mnoho aplikací BitBlt je velmi jednoduchých, například vyplnění formuláře bílou barvou nebo zkopírování celého jednoho formuláře na nějaké místo v jiném. Smalltalk umožňuje takové příležitostné použití BitBlt prostřednictvím široké škály jednoduchých zpráv pro třídu Form, jako například:

     someForm fillAII: white.
     someForm copyAIITo:
     destLocation in: destForm.

Všechny takové zprávy zde nebudeme uvádět. V následujících příkladech by měl být čtenář schopen odvodit význam z názvů zpráv a doprovodných vysvětlivek.

Zvětšení

Často je užitečné zvětšit obrázek pro bližší zkoumání a zejména umožnit pohodlnou změnu uložených Formulářů. Fotografie 1 ukazuje tuto funkci, která umožňuje uživateli ovládat písmo použité pro zobrazení textu. Znak pro "7" byl zobrazen devětkrát zvětšený. Pomocí ukazovacího zařízení uživatel začernil některé buňky tak, aby vznikla "7" v evropském stylu, a výsledek je vidět v levém horním i pravém dolním okně obrazovky.

Jednoduchým způsobem, jak zvětšit uložený Formulář, by bylo zkopírovat jej do většího Formuláře, čímž by se za každou malou tečku v originálu udělala velká tečka. Pro výšku h a šířku w by to vyžadovalo h X w operací. Algoritmus uvedený ve příkladu 3 (jako dvě zprávy do třídy Form) spotřebuje jen o několik operací více než h + w.

Zvětšování probíhá ve dvou krocích. Nejprve rozřeže obrázek na svislé pruhy v wideForm oddělené mezerou rovnající se faktoru zvětšení. Ty se pak pomocí funkce ORing rozetřou po meziprostoru, aby se dosáhlo horizontálního zvětšení. Poté se proces opakuje z wideForm do bigForm, přičemž se vodorovné plátky oddělí a rozetřou ve svislém směru, čímž se dosáhne požadovaného zvětšení. Obrázek 8 znázorňuje průběh výše uvedeného algoritmu při vytváření zvětšené "7" zobrazené na fotografii 1.

Rotace

Další užitečnou operací s obrázky je rotace o násobek 90 stupňů. Rotace je často považována za zásadně odlišnou operaci od translace a tento úhel pohledu by zavrhl možnost použít BitBlt k otáčení obrázku. Čtenář však musí souhlasit s tím, že první transformace zobrazená na obrázku 9 je krokem k otočení zobrazeného obrázku: zbývá pouze otočit vnitřky čtyř buněk, které byly permutovány. Ve zbývající části obrázku je každá z těchto buněk dále rozdělena, její buňky jsou podobně permutovány atd. Nakonec každá uvažovaná buňka obsahuje pouze jeden pixel. V tomto okamžiku již není nutné žádné další dělení a obraz byl věrně otočen!

Každá transformace zobrazená na obrázku 9 by zřejmě vyžadovala postupně větší množství výpočtů, přičemž poslední transformace vyžaduje několikanásobně více operací než h X w. Záludností níže uvedeného algoritmu je permutace dílčích částí každé rozdělené buňky najednou, čímž se celá rotace provede v konstantním čase log 2 (h) operací. Paralelní permutace mnoha buněk se provádí pomocí dvou pomocných formulářů. První, mask, nese masku, která vybírá levý horní kvadrant každé buňky; druhý, temp, slouží k dočasnému uložení. Série operací BitBlt vymění pravou a levou polovinu každé buňky a pak další série vymění diagonální kvadranty, čímž se dosáhne požadované permutace. Kompletní metoda rotace je uvedena v příkladu 4.

Obrázek 10 sleduje stav temp a self po postupných operacích. Posuny jednotlivých operací nejsou zobrazeny, i když jsou uvedeny ve výpisu programu. Po dvanácti operacích bylo dosaženo požadované permutace. V tomto okamžiku se maska vyvíjí na jemnější zrno a proces se opakuje pro další, menší buňky. Obrázek 11 ukazuje vývoj masky od první do druhé fáze zjemňování. Čtenář si všimne, že zde uvedený algoritmus pro rotaci je použitelný pouze pro čtvercové tvary, jejichž velikost je mocninou dvou. Rozšíření této techniky na libovolné obdélníky je složitější a je ponecháno jako cvičení pro čtenáře. Poněkud jednodušším cvičením je aplikovat výše uvedenou techniku na vodorovné a svislé odrazy kolem středu obdélníku.

Hra života

Hru o životě Johna Conwaye čtenáři časopisu BYTE pravděpodobně dobře znají. Jedná se o poměrně jednoduché pravidlo pro postupné zalidňování bitové mapy. Pravidlo zahrnuje počet sousedů pro každou buňku - kolik z osmi sousedních buněk je obsazeno? Každá buňka bude v další generaci obsazena, pokud má přesně tři sousedy, nebo pokud byla obsazena a má přesně dva sousedy. Vysvětluje se to takto: v prázdné buňce se mohou narodit tři sousední organismy a existující organismus zemře na obnažení při méně než dvou sousedech nebo na přemnožení při více než třech sousedech. Protože BitBlt neumí sčítat, zdá se, že v této aplikaci nemá žádný smysl. Kombinační pravidla BitBlt však obsahují pravidla pro částečný součet (XOR) a přenos (AND). S jistou dávkou vynalézavosti a dostatečným množstvím paměti navíc lze další generaci bitové mapy libovolné velikosti vypočítat pomocí konstantního počtu operací BitBlt.

V příkladu 5 je uvedena metoda pro nextLifeGeneration. Jak je znázorněno na obrázku 12, počet sousedů je reprezentován pomocí tří obrazových rovin pro bit Is, bit 2s a bit 4s počtu sousedů ve dvojkové soustavě. Bit 8s lze ignorovat, protože v tomto případě neexistují žádní přeživší, což je ekvivalentní nule (výsledek ignorování bitu 8s). Tato smalltalkovská metoda je poněkud neekonomická, protože pro každého nového souseda provádí úplné šíření přenosu, přestože se do 4-roviny nic nerozšíří, dokud nepřijde alespoň čtvrtý soused. Někteří čtenáři možná rádi tento algoritmus vylepší.

Pomocí BitBlt lze provádět noho dalších úloh zpracování obrazu. Autor vytvořil kompletní systém optického rozpoznávání znaků pro sanskrtský text pomocí různých kombinačních pravidel a operace, která počítá počet černých bitů v libovolném obdélníku (jak byste to udělali vy?).

Zpracování bitmap je ideální pro implementaci VLSI (very large scale integration). Čtenáři, kteří se zajímají o tento směr, by si měli ve sborníku z konference Design Automation Conference z června 1981 najít článek "Parallel Bitmap Processor" od Toma Blanka, Marka Stefika a Willema vanCleemput.

Úvahy o efektivitě

Naše původní Specifikace pro BitBlt byla publikována jinde (Newman a Sproull, Principles of Interactive Computer Graphics, 2. vydání, McGraw-Hill, 1979) pod názvem RasterOp. Implementaci popsanou v tomto odkazu lze snadno rozšířit tak, aby zahrnovala celou sadu kombinací, a přidání ořezávání je rovněž jednoduché. Zde přidáváme několik poznámek o efektivitě, které jsme získali na základě zkušeností.

BitBlt je pro uživatelské rozhraní tak zásadní, že jakékoli zlepšení jeho výkonu má značný vliv na interaktivní kvalitu celého systému. Při běžném používání systému Smalltalk-80 je většina volání BitBlt buď v extrémním mikroskopickém, nebo makroskopickém rozsahu. Podívejme se na ně blíže.

V makroskopickém rozsahu se šířka přenosu rozprostírá do mnoha slov. Vnitřní smyčka přes horizontální řádek se provádí mnohokrát a požadované operace bývají jednoduché přesuny nebo ukládání konstant. Příklady těchto operací jsou:

• Vymazání řádku textu na bílou barvu

• Vymazání celého okna na bílou barvu

• Posun bloku textu nahoru nebo dolů

Je štěstí, že většina procesorů poskytuje rychlé prostředky pro přesuny a ukládání bloků, a ty mohou sloužit k výše uvedeným aplikacím. Předpokládejme, že horizontální smyčku BitBlt strukturujeme jako následující posloupnost:

1. Přesun levého dílčího slova

2. Přesun mnoha celých slov (nebo žádného)

3. Přesun pravého dílčího slova (nebo žádného)

Speciální případy lze stanovit pro bod 2, pokud je operace jednoduchým uložením nebo pokud se jedná o jednoduché kopírování bez zkreslení (horizontálního bitového posunu) od zdroje k cíli. Tímto způsobem může být většina makroskopických aplikací BitBlt rychlá i na procesorech se skromným výkonem.

Mikroskopický rozsah BitBlt je charakterizován nulovým počtem pro vnitřní smyčku v položce 2, takže práce na každém řádku skenování zahrnuje nanejvýš dvě slova. V tomto případě lze značně snížit celkovou režii nastavení i vertikální smyčky. Protože znaky mají obvykle šířku menší než jedno slovo a řádky mají obvykle tloušťku menší než jedno slovo, spadají do této kategorie téměř všechny texty a kreslení řádků. Vhodným způsobem, jak zajistit takovou efektivitu, je napsat speciální případ BitBlt, který předpokládá mikroskopické parametry, ale přejde na obecný BitBlt, kdykoli nejsou splněny. Vzhledem ke statistice (mnoho malých operací a několik velmi velkých) není na škodu zaplatit pokutu za falešný předpoklad při zřídkavých voláních.