Voxel Ray Casting: příští generace grafiky?
16.11.2009, Petr Štefek, článek
O společnosti id Software nebylo dlouho slyšet a nyní k nám přichází s horkou novinkou v podobě vyvíjeného grafického enginu (respektive způsobu zobrazování) s názevm Voxel Ray Casting. Tento způsob zobrazování je do jisté míry revolučnější než ray tracing, takže si o něm pojďme popovídat blíže.
Kapitoly článku:
Strom je velmi používaná datová struktura v počítačové vědě, protože jedna z hlavních výhod je hierarchie dat. Každý z nás tento typ datových struktur často využívá, aniž by o tom třeba věděl nebo přemýšlel. Příkladem může být obyčejný manažer souborů na pevném disku. Na takovém disku jsou přítomny adresáře a podadresáře a někdy to vyžaduje několikero kliknutí, než se dostanete k samotným souborům. Nicméně se stále jedná o velmi dobře organizovaná data a vy hned víte, kam musíte sáhnout, abyste dostali kýžená data.
Používání organizovaného datového stromu je tedy velmi žadoucí. Každý z uzlů stromu může mít další větve. Například pokud jsou maximem dvě větve, mluvíme o binárním stromu, pokud jsou maximem 4 větve, pak se jedná o tzv. “quadtree”. Konečně, v našem případě se jedná o strom s maximálně 8 větvemi, který se jinak nazývá octal tree alias “octree”, který jsme zmiňovali už ve druhé kapitole.
Jak princip stromové struktury dat využijeme v případě voxelů? Jak jsme si již řekli, voxely umístěné v klasické mřížce znamenají potřebu velké kapacity paměti. Díky octree můžeme jemné rozlišení mřížky používat jen tam, kde je to skutečně třeba. Protože by vysvětlování tohoto principu ve třech rozměrech bylo příliš složité, tak si vše vysvětlíme na dvou rozměrech.
Na ilustračním obrázku vidíme aproximaci zobrazení kruhu v mřížce o rozlišení 12x12. Samotná aproximace je díky nízkému rozlišení opravdu hrubá, ale velmi dobře lze vidět, že velká část buněk mřížky je zbytečná, jelikož v nich není žádná část objektu, nebo jsou naopak uvnitř kruhu samotného.
V případě „quadtree“ je to jednoduché. Původní obraz se rozdělí na 4 kvadranty, kde se testuje, zda je kvadrant prázdný a pokud ano, algoritmus se ukončí. Pokud ovšem prázdný není, tak se pokračuje v dalším dělení až do fáze, kdy strom dosáhne 4 větví. Každou z nich v obrázku reprezentují 4 různé velikosti buněk (v každém kvadrantu vidíme 4 subkvadranty, které se dále dělí). Původní mřížka měla 144 buněk, které byly do značné míry zátěží pro paměť. V upraveném obraze již počet buněk výrazně snížila optimalizace.
Když jsme si zmiňovali „octree“, jedná se pouze o rozšíření výše popsaného principu do tří rozměrů. V praxi je ale vše poněkud složitější, neboť každý vzniklý uzel musí obsahovat spojení na menší buňky. V původní mřížce byly totiž pozice voxelů stálé a nic se neměnilo. Nicméně je to jen jedna malá nevýhoda oproti mnohým výhodám, které z využití „octree“ plynou. Pro další porozumění si musíme říci, jakým způsobem jsou data zobrazována. Je totiž několik cest, jak zobrazovat voxely, ale John Carmack a iD Software vsadili na ray casting. Ten jsme si popisovali již dříve, ale opakování je matka moudrosti.
Používání organizovaného datového stromu je tedy velmi žadoucí. Každý z uzlů stromu může mít další větve. Například pokud jsou maximem dvě větve, mluvíme o binárním stromu, pokud jsou maximem 4 větve, pak se jedná o tzv. “quadtree”. Konečně, v našem případě se jedná o strom s maximálně 8 větvemi, který se jinak nazývá octal tree alias “octree”, který jsme zmiňovali už ve druhé kapitole.
Jak princip stromové struktury dat využijeme v případě voxelů? Jak jsme si již řekli, voxely umístěné v klasické mřížce znamenají potřebu velké kapacity paměti. Díky octree můžeme jemné rozlišení mřížky používat jen tam, kde je to skutečně třeba. Protože by vysvětlování tohoto principu ve třech rozměrech bylo příliš složité, tak si vše vysvětlíme na dvou rozměrech.
Na ilustračním obrázku vidíme aproximaci zobrazení kruhu v mřížce o rozlišení 12x12. Samotná aproximace je díky nízkému rozlišení opravdu hrubá, ale velmi dobře lze vidět, že velká část buněk mřížky je zbytečná, jelikož v nich není žádná část objektu, nebo jsou naopak uvnitř kruhu samotného.
V případě „quadtree“ je to jednoduché. Původní obraz se rozdělí na 4 kvadranty, kde se testuje, zda je kvadrant prázdný a pokud ano, algoritmus se ukončí. Pokud ovšem prázdný není, tak se pokračuje v dalším dělení až do fáze, kdy strom dosáhne 4 větví. Každou z nich v obrázku reprezentují 4 různé velikosti buněk (v každém kvadrantu vidíme 4 subkvadranty, které se dále dělí). Původní mřížka měla 144 buněk, které byly do značné míry zátěží pro paměť. V upraveném obraze již počet buněk výrazně snížila optimalizace.
Když jsme si zmiňovali „octree“, jedná se pouze o rozšíření výše popsaného principu do tří rozměrů. V praxi je ale vše poněkud složitější, neboť každý vzniklý uzel musí obsahovat spojení na menší buňky. V původní mřížce byly totiž pozice voxelů stálé a nic se neměnilo. Nicméně je to jen jedna malá nevýhoda oproti mnohým výhodám, které z využití „octree“ plynou. Pro další porozumění si musíme říci, jakým způsobem jsou data zobrazována. Je totiž několik cest, jak zobrazovat voxely, ale John Carmack a iD Software vsadili na ray casting. Ten jsme si popisovali již dříve, ale opakování je matka moudrosti.
