Grafické algoritmy implementované v 3D akcelerátoru Voodoo 1

Obsah

1. Grafické algoritmy implementované 3D grafickým akcelerátorem Voodoo I

2. Gouraudovo stínování

3. Struktura paměti grafického akcelerátoru Voodoo

4. Framebuffer

5. Double a triple buffering

6. Paměť hloubky (Z-buffer)

7. Formát záznamů uložených v paměti hloubky (Z-bufferu)

8. Odkazy na Internetu

1. Grafické algoritmy implementované 3D grafickým akcelerátorem Voodoo I

V předchozí části seriálu o architekturách počítačů jsme si mj. stručně popsali základní vlastnosti grafického akcelerátoru nazvaného Voodoo 1 firmy 3Dfx, která stála na samém počátku vývoje 3D grafických akcelerátorů určených pro běžné osobní počítače typu PC (na grafických stanicích byla situace samozřejmě poněkud odlišná, bližší informace si však řekneme až v některém z dalších pokračování tohoto seriálu). Víme již, že se jednalo o přídavnou akcelerační kartu specializovanou na vykreslování trojrozměrné grafiky určenou pro universální sběrnici PCI, která „pouze“ doplňovala prakticky libovolnou grafickou kartu typu VGA, SVGA či některý 2D grafický akcelerátor. Pro běžnou práci s počítačem se využívalo funkcí grafické karty, jejíž výstup (video signály) byl přes 3D akcelerátor Voodoo 1 posílán přímo do monitoru. Teprve při práci s trojrozměrnými scénami se video signály docházející z grafické karty do akcelerátoru ignorovaly (odpojily) a řízení zobrazování převzal samotný grafický akcelerátor Voodoo 1.

Obrázek 1: Polygony pokryté texturou, které byly vykresleny grafickým systémem Sunstone vyvinutým již v roce 1979 Edem Emshwillerem.

Minule jsme si také řekli, že na tomto grafickém akcelerátoru se kromě obrazové paměti implementované pomocí paměťových modulů EDO DRAM (rozdělené na dvě části – framebuffer a samostatně adresovatelnou texturovací paměť) nacházela i dvojice specializovaných čipů nazvaná FBI (Pixelfx) a TMU (Texelfx). Čip FBI zajišťoval především komunikaci s počítačem přes sběrnici PCI, přístup do lineárního framebufferu (obrazové paměti, viz další kapitoly), implementoval Gouraudovo stínování pomocí hardwarových interpolátorů, funkci Z-bufferu (paměti hloubky), dithering obrazu při jeho ukládání do obrazové paměti a taktéž výpočet efektu mlhy. Naproti tomu čip TMU sloužil zejména pro mapování textur, bilineární a trilineární filtraci textur a mip-mapping, který s filtrací textur úzce souvisí. V následujících kapitolách jsou podrobněji popsány nejdůležitější algoritmy implementované v obou výše zmíněných čipech.

Obrázek 2: Grafický akcelerátor Voodoo 1 s čipy FBI a TMU (viz potisk) a paměťmi EDO DRAM, pomocí nichž je sestavený framebuffer i paměť pro textury.

Detailním popisem komunikace mezi grafickým akcelerátorem a mikroprocesorem se v tomto článku nebudeme podrobněji zabývat, neboť tato činnost přímo nesouvisí s grafickou akcelerací vykreslování prostorových scén. Pro zajímavost však stojí za zmínku informace, že při poslání příkazu na grafický akcelerátor Voodoo 1 musel programátor čekat na potvrzení jeho vykonání, přičemž stav grafického akcelerátoru bylo nutné zjišťovat aktivně, tj. periodickým načítáním stavu v programové smyčce. U současných grafických akcelerátorů jsou komunikační protokoly vytvořeny s ohledem na co největší propustnost dat, tj. tak, aby grafický akcelerátor v daný okamžik dostával přesně ta data, která pro svoji činnost potřebuje (může se například jednat o prokládání dat nesoucích informace o texturách s geometrickými informacemi, tj. souřadnicemi vrcholů polygonů atd.). Další informace o této problematice si řekneme příště, stejně jako popis algoritmů implementovaných v texturovací jednotce – TMU.

2. Gouraudovo stínování

Jedním ze základních a přitom velmi důležitých algoritmů implementovaných na grafickém akcelerátoru Voodoo 1 je algoritmus Gouraudova stínování. Jedná se o implementačně poměrně jednoduchý a tudíž i rychlý způsob vykreslení trojúhelníků či složitějších konvexních polygonů v případě, že jsou zadány (nebo vypočteny, například pomocí Phongova osvětlovacího modelu) barvy ve vrcholech polygonů. Pomocí Gouraudova stínování je s využitím lineární interpolace vypočtena barva celé plochy polygonu, tj. barva všech pixelů (přesněji řečeno všech fragmentů), které polygon tvoří po jeho vykreslení (rasterizaci) do framebufferu. Gouraudovo stínování je implementováno na všech moderních grafických akcelerátorech, protože se pomocí něho může povrch těles vizuálně vyhladit tak, že se na něm nevyskytují takzvané nepravé hrany, tj. hrany vzniklé aproximací zaobleného povrchu tělesa pomocí plošek – polygonů (původní aproximovaný tvar tělesa je však stále patrný, například při pohledu na jeho kontury).

Obrázek 3: Utah teapot vykreslený na grafickém akcelerátoru. Tento známý trojrozměrný model je sice reprezentován pomocí spline ploch (datové soubory lze relativně snadno najít na Internetu), ale před vykreslením jsou tyto plochy rozděleny na síť trojúhelníků a plošných čtyřúhelníků, které jsou následně posílány do grafického akcelerátoru (přesněji řečeno jsou do grafického akcelerátoru posílány informace o barvách vrcholů a o jejich souřadnicích). Grafický akcelerátor všechny polygony vykreslil s využitím Gouraudova stínování, takže došlo ke zdánlivému vyhlazení vykresleného povrchu, i když se jeho geometrie nezměnila (stále se jedná o plošky).

Na grafickém akcelerátoru Voodoo 1 lze využít i takzvané konstantní stínování (constant shading, někdy též označené termínem flat shading), při kterém má celá plocha polygonu (trojúhelníku) konstantní barvu, takže jednotlivé plošky, ze kterých se povrch tělesa skládá, jsou viditelné a jasně odlišitelné. Předností konstantního stínování je urychlení vykreslování celé trojrozměrné scény, samozřejmě za cenu její horší vizuální kvality, zejména v těch případech, kdy je skutečný povrch tělesa pouze hrubě aproximován malým množstvím polygonů (velké problémy vznikají například při modelování lidských obličejů či celých postav).

3. Struktura paměti grafického akcelerátoru Voodoo I

Jednou z příčin velké oblíbenosti a současně i rozšířenosti grafického akcelerátoru Voodoo 1 byla i jeho příznivá cena, která byla mj. způsobena tím, že jeho tvůrci použili relativně levné paměťové moduly typu EDO DRAM (nikoli tedy drahé VRAM), jejichž cena postupně klesala, a to poměrně výrazně právě v době, kdy byl tento grafický akcelerátor uveden na trh. Paměť grafického akcelerátoru Voodoo 1 je rozdělena do dvou částí (na dnešní akcelerátorech je možné velikost oblastí dynamicky měnit). První část paměti je určena pro uložení textur (texturovací paměť), část druhá o shodné kapacitě slouží jako oblast, ve které se nachází framebuffer. Kapacita texturovací paměti byla na většině karet rovna dvěma megabajtům, ovšem samotný čip TMU dokázal obsloužit i paměť s dvojnásobnou kapacitou (karty Voodoo 2 byly vybaveny čtyřmi či dokonce osmi megabajty texturovací paměti, takže celková kapacita všech paměťových modulů na tomto akcelerátoru mohla dosáhnout až 12 MB). Framebuffer měl na kartách Voodoo 1 velikost taktéž dvou megabajtů, na další verzi Voodoo 2 se však již mohla jeho kapacita zvýšit na 4 MB, což umožnilo jak implementaci triple-bufferingu (viz další kapitolu), tak i zvýšení grafického rozlišení z 640×480 pixelů na 800×600 pixelů.

4. Framebuffer

Framebuffer se na grafickém akcelerátoru Voodoo 1 skládá z několika bufferů: takzvaného předního bufferu (front buffer), který je v daném okamžiku zobrazen na monitoru, jednoho či dvou zadních bufferů (back buffers), do nichž lze provádět vykreslování bez toho, aby to uživatel mohl zaregistrovat (ten totiž má na monitoru v průběhu vykreslování do zadního bufferu zobrazen starý snímek uložený v předním bufferu, viz následující odstavec) a konečně Z-buffer neboli paměť hloubky používanou pro implementaci skrývání neviditelných (zakrytých) částí polygonů. Konfigurace framebufferu je volitelná, typicky se však používá nastavení se třemi buffery: předním, zadním a Z-bufferem. Vzhledem k tomu, že bitová hloubka všech tří zmíněných bufferů je rovna šestnácti bitům, je maximální možné rozlišení povolené v této konfiguraci (při instalaci 2 MB EDO DRAM pro framebuffer) rovno 640×480 pixelům, protože při použití tohoto rozlišení je zapotřebí alokovat: 640×480×2×3=1 8­43 200 bajtů, což zhruba odpovídá maximální kapacitě framebufferu: 2 097 152 (2MB).

Obrázek 4: Do framebufferu jsou ukládány jak barvy jednotlivých fragmentů vzniklé po rasterizaci polygonů, tak i vzdálenosti fragmentů od pozorovatele. Data je možné do framebufferu i přímo kopírovat popř. naopak načítat zpět do operační paměti.

V následující tabulce jsou vypsána maximální možná rozlišení výsledného obrazu zobrazovaného na monitoru pro různé kapacity paměti rezervované pro framebuffer i pro jeho různé konfigurace (některé konfigurace lze využít pouze na grafickém akcelerátoru Voodoo 2, nikoli na Voodoo 1). Je zřejmé, že v případě použití pouze dvou bufferů (double bufferingu) je možné využívat větší rozlišení 800×600 pixelů než v případě, že jsou použity buffery tři (v tomto případě se jedná buď o double buffering doplněný o Z-buffer nebo o triple buffering). Význam double bufferingu a triple bufferingu při vykreslování trojrozměrných scén bude uveden v následující kapitole.

5. Double a triple buffering

Při interaktivní práci s prostorovou scénou (například ve hrách) je nutné měnit pohled na scénu, tj. bod umístění kamery i další parametry kamery, popř. pohybovat s prostorovými objekty, které se ve scéně nachází. Po každé změně pohledu se musí celá prostorová scéna znovu překreslit, protože se většinou změní souřadnice všech vrcholů grafických primitiv na obrazovce. Toto překreslení celé scény (které ve většině případů začíná vymazáním plochy obrazovky barvou pozadí) však nějakou dobu trvá a v této době by uživatel viděl problikávání způsobené postupnou změnou barev pixelů v předním (barvovém) bufferu. Tomuto problikávání lze zabránit tak, že se místo jednoho barvového bufferu použijí buffery dva. Do jednoho z těchto bufferů se vykresluje (již zmíněný zadní buffer – back buffer) a druhý je zobrazený uživateli na monitoru (takzvaný přední buffer – front buffer). V grafické knihovně GLIDE, která byla pro účely ovládání grafických akcelerátorů Voodoo vyvinuta, jsou jednotlivé buffery označeny pomocí následujících konstant:

Po dokončení vykreslování do prvního bufferu se tento zobrazí uživateli a role bufferů se obrátí – tomuto využití dvou barvových bufferů se říká double buffering. Důležité je, že při změně role obou bufferů není zapotřebí provádět žádné přesuny dat v obrazové paměti. Jednou z (mála) nevýhod double bufferingu je skutečnost, že po ukončení vykreslení celé scény musí grafický akcelerátor čekat na návrat elektronového paprsku, aby mohl prohodit funkce obou bufferů (wait for V-sync). Pokud by se na návrat paprsku nečekalo, mohlo by dojít k viditelnému horizontálnímu lomu mezi předposledním a posledním snímkem. Ovšem čekání na návrat paprsku znamená, že se funkce grafického akcelerátoru na určitou dobu zastaví. Aby se zbytečnému čekání zabránilo, může se použít takzvaný triple buffering, při němž jsou k dispozici dva zadní buffery a jeden buffer přední, ovšem druhý zadní buffer je na grafických akcelerátorech Voodoo kvůli omezené kapacitě framebufferu vytvořen namísto paměti hloubky (Z-bufferu).

6. Paměť hloubky (Z-buffer)

Při vykreslování prostorové scény s využitím grafického 3D akcelerátoru Voodoo 1 (ale i většiny dalších grafických akcelerátorů) se postupuje poměrně přímočarým způsobem. Nejdříve se programově nastaví základní parametry vykreslování, například identifikátor textury, která se má použít při vykreslování ploch či transformační matice používané při projekci vrcholů polygonů ze světového prostoru (world space) do prostoru obrazového. Posléze se do grafického akcelerátoru posílají geometrické informace o jednotlivých polygonech, které se mají vykreslit. Jedná se o souřadnice jednotlivých vrcholů doplněné o některé další důležité atributy, především o barvu vrcholů (viz výše uvedená kapitola věnovaná Gouraudovu stínování) a souřadnice vrcholů v prostoru textur (jde o dvě či tři souřadnice, tj. buď o dvojici [u, v] nebo o trojici [u, v, w]).

Obrázek 5: Utah teapot pokrytý texturou, která je modulovaná barvovým přechodem vypočteným pomocí Gouraudova stínování na základě jednotlivých vrcholů polygonů.

Pokud by se však polygony rastrovaly do framebufferu přímo (tj. bez využití dalších programových či technických prostředků), docházelo by k jejich nekorektnímu překryvu, protože pořadí polygonů posílané do grafického akcelerátoru obecně neodpovídá reálné viditelnosti jednotlivých stěn (v některých případech to ani není technicky možné, protože například tři polygony mohou být umístěny v prostoru tak, že nelze rozhodnout, který je blíže k pozorovateli a který dále). Jedno z řešení viditelnosti by mohlo spočívat v ručním (algoritmickém) seřazení jednotlivých polygonů tak, že nejdříve by se vykreslily stěny (polygony) nejvzdálenější a poté by se postupně překreslovaly stěny bližší.

Toto řešení, které se také nazývá malířův algoritmus (painter's al­gorithm) je však časově náročné (stěny se musí seřadit a to po každé změně v prostorové scéně nebo při každém pohybu kamery–pozorovatele), nepodporuje proudové zpracování dat (opakované řazení) a může vést k nejednoznačnostem při vyhodnocování vzdálenosti jednotlivých stěn, například v již zmíněném případě, kdy se tři stěny vzájemně překrývají. Z tohoto důvodu se v grafických akcelerátorech používá jiná technika, která je optimalizovaná pro proudové zpracování dat bez nutnosti tvorby a udržování složitých datových struktur či použití časově náročných algoritmů. V této technice je pro řešení viditelnosti jednotlivých polygonů či jejich částí (tj. fragmentů) použita takzvaná paměť hloubky, neboli depth buffer, popř.  Z-buffer.

Obrázek 6: Operace s fragmenty prováděné při vykreslování. Na tomto schématu je zvýrazněný blok zabezpečující vykreslení pouze těch fragmentů, které se nachází nejblíže k uživateli.

Paměť hloubky obsahuje rastrová data, nejsou zde však uloženy barvy jednotlivých fragmentů, ale jejich kolmé vzdálenosti od projekční roviny (ve skutečnosti se většinou interně ukládají převrácené hodnoty těchto vzdáleností, jak si ostatně vysvětlíme v dalším textu). Před vykreslením barvy fragmentu do barvového bufferu se nejdříve provede několik testů, mezi něž patří i test na vzdálenost (hloubku) fragmentu. Pokud fragment tímto testem projde (jeho vzdálenost od pozorovatele je menší než hodnota uložená v Z-bufferu), znamená to, že je blíže pozorovateli nežli fragmenty předchozí (samozřejmě na tom samém místě obrazovky), což značí, že může být vykreslen a příslušný údaj v Z-bufferu může být přepsán hloubkou právě vykresleného fragmentu. V opačném případě je z dalšího zpracování vyjmut. Testy a operace s fragmenty jsou naznačeny na šestém obrázku, kde je zvýrazněn blok pro testy hloubky fragmentu s hodnotou uloženou v paměti hloubky. Při vykreslování 3D scény tedy může být každý pixel překreslen několikrát, v nejhorším případě tolikrát, kolik se vykresluje polygonů.

7. Formát záznamů uložených v paměti hloubky (Z-bufferu)

Rozlišení Z-bufferu je většinou shodné s rozlišením výsledné rastrové mapy, která má být vykreslena. Před vykreslením nového snímku jsou hloubky všech fragmentů nastaveny na maximální vzdálenost, v GLIDE je tato hodnota reprezentována konstantou GR_ZDEPTHVALU­E_FARTHEST. Pokud by se počáteční hloubky fragmentů nastavily na jinou hodnotu, docházelo by při vykreslování scény k ořezávání vzdálených polygonů (resp. jejich částí), což může být v některých případech žádoucí vlastnost. Na tomto místě stojí za upozornění fakt, že při vykreslování poloprůhledných polygonů, tj. polygonů s nanesenou texturou obsahující poloprůhledné texely, nedokáže Z-buffer korektně s těmito polygony pracovat. Z tohoto důvodu je nutné nejdříve (s povoleným zápisem do Z-bufferu) vykreslit všechny neprůhledné polygony a poté zakázat zápis do Z-bufferu a následně vykreslit poloprůhledné polygony, ovšem setříděné podle jejich klesající vzdálenosti od pozorovatele (kamery).

Do paměti hloubky (Z-bufferu) je možné ukládat vzdálenosti fragmentů od pozorovatele (kamery) ve dvou formátech, v obou případech je však každý údaj vždy uložen na šestnácti bitech. Při použití prvního způsobu se do Z-bufferu skutečně ukládají vzdálenosti fragmentů, přesněji řečeno celočíselná část vzdálenosti (výpočty vzdálenosti se provádí přesněji, ale výsledek je při ukládání zaokrouhlen). Tento formát není příliš výhodný, protože po projekci 3D scény ze světových souřadnic do prostoru obrazovky není krok mezi jednotlivými vzdálenostmi konstantní, což vede k vizuálním chybám při vykreslování (rozlišení pouze 2¹⁶ vzdáleností je v tomto případě nedostatečné). Z tohoto důvodu se preferuje druhý způsob (nazývaný také w-buffer), při němž se do Z-bufferu ukládají převrácené hodnoty vzdálenosti, a to ve speciálním formátu čísel s pohyblivou řádovou tečkou (čárkou), který má následující strukturu připomínající formát definovaný v IEEE 754:

1.mantissa × 2^exponent

V tomto formátu je pro mantisu vyhrazeno dvanáct bitů a pro exponent čtyři bity. Povšimněte si implicitní jedničky před desetinnou tečkou i toho, že žádný bit není vyhrazen pro uložení znaménka – vzdálenosti (a samozřejmě i jejich převrácené hodnoty) jsou vždy kladné. Minimální hodnota, kterou lze tímto způsobem uložit, je rovna jedničce (0×0000 ~ 1.00000000000­0₂×2), maximální hodnota 65528.0 (0×ffff ~ 1.11111111111­1₂×2¹⁵). Podobné „krátké“ formáty čísel s plovoucí řádovou tečkou jsou v oblasti grafických akcelerátorů velmi oblíbené, o čemž se přesvědčíme i v navazujících částech tohoto seriálu.

8. Odkazy na Internetu

1. 3dfx Voodoo1 PCI
   http://www.v3info.de/…tml/v1.shtml
2. Glide 2.2 Programming Guide
   http://www.gamers.org/…glidepgm.htm
3. 3dfx Interactive
   http://en.wikipedia.org/…doo_Graphics
4. Glide API
   http://en.wikipedia.org/wiki/Glide_API
5. Edwin Catmull
   http://en.wikipedia.org/…dwin_Catmull
6. Intel i860
   http://en.wikipedia.org/wiki/Intel_860
7. Intel i860 64-Bit Microprocessor
   http://www.microprocessor.sscc.ru/i860.html
8. Intel i740
   http://en.wikipedia.org/wiki/Intel740
9. Intel i740 Datasheet
   ftp://download.intel.com/…29061902.pdf
10. Intel740™ Graphics Accelerator P854 Hardware
    ftp://download.intel.com/…29062202.pdf
11. Intel 860@cpu-collection
    http://www.cpu-collection.de/?…