Komerční prezentace
Registrace uživatele

Přihlašte se k odběru informací, novinek, získejte přístup do diskuzního fóra.

Vesmír č. 10
Vesmír č. 10
Toto číslo vychází
2. 10. 2017
Novinky
Zdarma jedno celé číslo Vesmíru v pdf.
• Říjnové číslo Vesmíru
reklama

Prostorové hierarchie – klíč k rychlosti a detailu

< předchozí | seriál: Počítačová grafika |
Publikováno: Vesmír 94, 706, 2015/12

Proces, který od vstupního digitálního popisu 3D scény vede k vytvoření jejího 2D obrazu ze zvolené pozice pozorovatele včetně simulování světelných efektů (např. odrazů a lomů) se anglicky nazývá rendering. Čeští grafici sice pro něj nedokázali nalézt lepší pojmenování než nelibě znějící rendrování, zato dokázali tuto metodu výrazným způsobem urychlit. Klíčem k úspěchu bylo efektivní využití hierarchických struktur, tedy grafů doplňujících základní 3D geometrické informace o popis jejich prostorového uspořádání.

V současnosti jsme doslova obklopeni výstupy počítačové grafiky. Často je i pro odborníka těžké rozlišit, zda obrázky prezentované v časopisech jsou reálné fotografie nebo počítačem generované obrazy virtuální scény. V mnoha filmech se takřka nepostřehnutelně prolíná počítačově generovaný obsah s reálnými záběry, v televizi sledujeme zpravodajství z virtuálních studií, zejména mladší generace objevuje kouzlo virtuálních světů počítačových her. Pokud nás v této souvislosti ani nenapadne pojem rendering, je to vlastně výborná vizitka, která ukazuje, jak velký pokrok tento obor počítačové grafiky v posledních několika dekádách učinil.

Oblast renderingu byla od počátků počítačové grafiky hybnou silou pro vývoj efektivních algoritmů. S novými hardwarovými technologiemi se otevíraly nové možnosti pro zobrazovací algoritmy, což vyústilo v bouřlivý rozvoj v oblasti běžně dostupných 3D grafických aplikací a her. Avšak ani kombinace velmi výkonných grafických karet a centrálních procesorů (CPU) nedokáže rozsáhlé a detailní scény zobrazovat „hrubou silou“. To platí zejména pro metody využívající vrhání paprsků (viz níže), které sice dokážou věrohodně simulovat osvětlení ve scéně, nicméně je to vykoupeno potřebou zjistit průsečíky desítek až stovek milionů paprsků za sekundu, zejména pokud chceme dosáhnout interaktivní odezvy (obr. 1).

Namísto použití hrubé síly můžeme využít prostorové hierarchie, které umožňují setřídit nebo přesněji prostorově uspořádat 3D scénu. Uspořádáním 3D scény v prostorové hierarchii získáme možnost efektivně vypočítat různé typy geometrických úloh i pro velmi složité scény. V jazyce počítačových věd dokážou prostorové hierarchie snížit složitost většiny geometrických vyhledávacích problémů z O(n) na O(log n), což v případě rozsáhlých scén obsahujících miliony grafických objektů znamená rozdíl několika řádů.

Typy prostorových hierarchií

Základní členění prostorových hierarchií rozlišuje mezi hierarchickým prostorovým dělením a objektovou hierarchií. Reprezentanty první kategorie jsou datové struktury oktantový strom, kd-strom nebo BSP strom (Binary Space Partitioning, binární dělení prostoru). Reprezentanty druhé kategorie jsou hierarchie obalových těles (BVH, Bounding Volume Hierarchy), které se liší typem používaných obalových těles (obalové těleso je geometricky jednoduchý pomocný objekt, typicky koule nebo kvádr, který obsahuje všechny body jím obaleného objektu).

Každá z uvedených prostorových datových struktur nalézá uplatnění v mírně odlišné oblasti počítačové grafiky. Oktantové stromy například poskytují velmi vhodnou reprezentaci volumetrických dat v různých úrovních detailu, BSP stromy jsou vhodné například pro předzpracování statických polygonálních scén, popřípadě pro výpočet množinových operací nad objekty scény. Kd‑stromy jsou vhodné pro indexaci bodových dat a pro uspořádání scén pro metodu sledování paprsků. Hierarchie obalových těles nalézají uplatnění zejména v oblasti výpočtu detekce kolizí mezi objekty a metodách sledování paprsků, kde nezřídka poskytují lepší výsledky než rovněž často používané kd‑stromy.

Než probereme detaily týkající se stavby efektivních prostorových datových struktur a souvisejících algoritmů jejich využití, uveďme si příklady geometrických úloh řešených v rámci dvou základních zobrazovacích paradigmat: rasterizace a vrhání paprsků.

Test průniku s pohledovým jehlanem

Rasterizace je proces vykreslování grafických objektů do rastru obrázku. Objekty scény jsou postupně promítány do obrázku, kde jsou „rasterizovány“, tj. postupně vyplňují jednotlivé pixely obrazového rastru. Pro urychlení vykreslování scén se v metodách založených na rasterizaci používá test průniku pohledového objemu s objekty scény.

Pohledový objem (nebo též záběr) reprezentuje část prostoru přímo viditelnou z pohledu dané virtuální kamery. Jedná se o komolý jehlan definovaný pomocí šesti rovin. Úkolem algoritmu je určit, které objekty protínají pohledový objem. Ostatní objekty mohou být z dalšího zpracování v zobrazovacím řetězci vyloučeny.

Algoritmus začíná testem v kořeni prostorové hierarchie. V případě kd-stromu algoritmus inkrementálně (přírůstkově) počítá osově zarovnaný kvádr, který odpovídá prostoru reprezentovanému daným uzlem hierarchie. V případě hierarchie obalových těles algoritmus využívá obálky, které jsou explicitně uchovávány v uzlech hierarchie. V obou případech se nejčastěji používá tzv. separační test, který pro každou rovinu testuje, zda celá obálka leží v záporném poloprostoru definovaném ořezávací rovinou. Pokud ano, víme s jistotou, že obálka neprotíná pohledový objem. Tato větev výpočtu může být ukončena a všechny objekty v aktuálně testovaném podstromu mohou být ignorovány.

Pokud separační test selže pro všech šest rovin definujících pohledový objem, je pravděpodobné, že obálka pohledový objem protíná. Pro přesné určení, zda existuje průnik s obálkou, lze použít další sadu separačních testů s využitím rovin odpovídajících stěnám obálky a následně i dalších rovin odpovídajících kombinacím hran a vrcholů obálky a pohledového objemu.

Ve většině případů se však omezíme na test pouze šesti rovin pohledového objemu, a pokud všechny selžou, předpokládáme, že průsečík existuje a výpočet provedeme rekurzivně pro potomky daného uzlu ve stromu. Tento přístup se označuje jako konzervativní algoritmus – z hlediska výsledného obrázku nám nevadí, pokud v této fázi výpočtu zahrneme do množiny objektů protínajících pohledový objem i některé objekty, které ho ve skutečnosti neprotínají. Přesné řešení získáme později pomocí rasterizace objektů předaných dále do zobrazovacího řetězce. V zájmu ušetření výpočetního času tak můžeme některé výpočty vynechat, musíme nicméně zajistit, že z výsledné množiny objektů nebude vyloučen žádný objekt, který byť jen částečně protíná pohledový jehlan.

Popsaný algoritmus nalezne řez v prostorové hierarchii, který odpovídá uzlům, kde bylo možné jednoznačně rozhodnout o jejich vztahu vůči pohledovému jehlanu a listům (uzlům stromu, které nemají žádné potomky), kde přesné řešení nebylo nalezeno, a kde tedy předpokládáme, že mohou být viditelné (obr. 2). Podstrom hierarchie definovaný tímto řezem typicky obsahuje pouze zlomek uzlů ve srovnání s počtem objektů celé scény. Dosáhneme tedy významné úspory v této části výpočtu, zejména pro velké scény.

Vrhání paprsků s prostorovou hierarchií

Metoda vrhání paprsků pro každý pixel vytvoří paprsek, který je vržen do scény s cílem nalezení nejbližšího zasaženého objektu, tedy objektu, který bude použit pro obarvení pixelu. Na rozdíl od rasterizace nejsou objekty zpracovávány postupně, ale k jejich zpracování dochází i opakovaně v závislosti na vržených paprscích. Je tedy nutné scénu uspořádat tak, abychom byli schopni dotazy na průsečíky s paprsky efektivně určit. Na druhou stranu umožňuje metoda vrhání paprsků jednoduše vypočítat i složitější osvětlovací efekty, například pomocí vrhání odražených a lomených paprsků.

Tato metoda je jádrem většiny postupů zaměřených na vytváření realistických obrázků 3D modelů. Tyto postupy simulují šíření světla ve scéně vrháním velkého množství paprsků s využitím stochastických metod integrace množství světla přeneseného od světelných zdrojů do snímače (kamery). Výpočet jednoho kroku tohoto algoritmu musí být velmi rychlý, jelikož pro kvalitní obrázek v HD rozlišení potřebujeme vrhnout řádově desítky milionů až jednotky miliard paprsků.

Algoritmus využívající hierarchie obalových těles (BVH) začíná v kořeni stromu, a v případě, že paprsek protíná s uzlem asociovanou obálku, pokračuje algoritmus testem potomků s využitím zásobníku uzlů. Většina současných algoritmů pro procházení BVH využívá alespoň přibližného uspořádání uzlů od nejbližšího po nejvzdálenější od počátku paprsku pro co nejrychlejší nalezení nejbližšího průsečíku. Na rozdíl od kd‑stromu nemůže algoritmus využívající BVH jednoduše ukončit prohledávání stromu po nalezení prvního průsečíku s objektem, jelikož ve stromě může existovat obálka, která se s nalezeným průsečíkem prostorově překrývá a která obsahuje objekt, jenž leží ještě blíže počátku paprsku.

Prostorová hierarchie umožňuje nalézt průsečík s daným paprskem s tím, že výpočet je omezen pouze na zlomek objektů v blízkosti paprsku. Ve složitých scénách tak urychlíme nalezení průsečíku o několik řádů ve srovnání s metodou, která by pro daný paprsek testovala všechny objekty scény.

Cesty k optimalizaci

Základní varianty algoritmů využívajících prostorové hierarchie jsou dále optimalizovány pro dosažení co nejefektivnějšího průchodu hierarchií. V oblasti rasterizace je to například metoda CHC (Coherent Hierarchical Culling), navržená autory z ČVUT a TU Vídeň. Využívá již dříve zmíněného řezu získaného při procházení hierarchie (v tomto kontextu také označovaného jako visible front) pro inicializaci výpočtu následujícího snímku a pomocí dotazů zastínění (hardwarové podpory grafických karet pro testování viditelnosti obálek hierarchie) minimalizuje dopady zpoždění v komunikaci grafické karty a CPU. Tato metoda byla implementována do populárních open source herních enginů (Ogre, Merlin3D) a uplatnila se i v komerční praxi, o čemž svědčí jak integrace její mírné modifikace do middlewaru od firmy Umbra, který je využíván řadou předních světových herních studií, tak např. zájem o využití metody ze strany firmy SAP pro integraci metody do jejích produktů.

Jedna z nyní velmi často využívaných technik pro efektivní vrhání paprsků v kd-stromech byla navržena v roce 1999 kolektivem autorů z ČVUT FEL (Fast Robust BSP Traversal Algorithm for Ray Tracing). Tato metoda snižuje počet potřebných operací a zejména řeší některé mezní případy, kdy například počátek paprsku leží na dělící rovině některého z uzlů kd-stromu. Dalším rozšířením je využití traverzační historie paprsků pro efektivní procházení koherentních skupin paprsků. Rychlá metoda vrhání paprsků může být využita i v jiné oblasti, než je realistická syntéza obrazu, což dokládá metoda předzpracování globální viditelnosti ve scéně navržená kolektivem autorů z ČVUT FEL, TU Vídeň a Arizonské státní univerzity (Adaptive Global Visibility Sampling, SIGGRAPH 2009). Metoda využívá vzorkování viditelnosti pomocí směsi adaptivních distribucí paprsků a její obdoba byla rovněž integrována do middleware firmy Umbra pro předzpracování viditelnosti v rozsáhlých scénách.

Jak postavit efektivní prostorovou hierarchii?

Doposud jsme se zabývali základními metodami využití prostorových hierarchií. Neméně důležitou částí z hlediska efektivity celého zobrazovacího procesu je ale i struktura a s tím související kvalita prostorové hierarchie. Kvalitní prostorová hierarchie minimalizuje počet operací nutných pro výpočet daného geometrického dotazu. V případě metod založených na vrhání paprsků je to například počet průchodů vnitřních uzlů hierarchie a počet počítaných průsečíků s geometrickými objekty v listech hierarchie. Většina v současnosti používaných metod pro stavbu efektivních prostorových hierarchií využívá tzv. povrchovou heuristiku (Surface Area Heuristic, SAH). Tato heuristika predikuje počet nutných výpočetních operací už během stavby hierarchie. Jejím využitím je tedy možné optimalizovat strukturu prostorové hierarchie s cílem minimalizace předpokládaného počtu výpočetních operací.

SAH je založena na odhadu podmíněné pravděpodobnosti, že paprsek protínající konvexní oblast protne rovněž danou konvexní podmnožinu dané oblasti. Pro velký počet rovnoměrně rozložených náhodných nezastíněných paprsků lze tuto pravděpodobnost vyjádřit jako poměr ploch povrchů daných konvexních oblastí (obr. 3). Algoritmy pro konstrukci prostorové hierarchie vyhodnocují různé možnosti dělení prostoru či objektů typicky s využitím pomocné dělicí roviny. Algoritmus následně vybere takovou dělicí rovinu, která minimalizuje vypočtenou SAH cenu (tj. předpokládaný počet výpočetních operací pro daný uzel hierarchie).

V případě kd-stromu je tato dělicí rovina přímo spojena s odpovídajícím uzlem stromu. V případě BVH je použita pro určení podmnožin objektů pro potomky daného uzlu, pro které jsou následně vypočtena obalová tělesa.

Rychlost bez omezení kvality

Počítačová grafika jako disciplína od samého počátku hledá co nejefektivnější využití dostupných výpočetních prostředků pro rychlé a kvalitní zobrazení virtuálních scén. Prostorové hierarchie sehrávají klíčovou úlohu pro dosažení efektivity při zobrazování velmi složitých 3D modelů a rozsáhlých scén jak v oblasti interaktivních zobrazovacích metod, tak v oblasti neinteraktivních metod zaměřených na vysokou kvalitu generovaných obrázků. Zároveň prostorové hierarchie umožňují modelovat složité scény s ohromující úrovní detailu, které by bez jejich použití nebylo možné zobrazovat v dostatečné kvalitě či rychlosti.

Čeští výzkumníci vytvořili několik technik, které jsou využívány jak v rámci open source komunitních projektů, tak v rámci komerčních nástrojů významných světových firem. Očekáváme, že zobrazovací metody budou v blízké budoucnosti už většinově založeny na technice vrhání paprsků, a tudíž efektivní konstrukce a využití prostorových datových struktur zůstane jedním z důležitých pilířů počítačové grafiky.

ČESKÝ PŘÍNOS KE KONSTRUKCI PROSTOROVÝCH HIERARCHIÍ

Jednou z nejcitovanějších prací věnujících se vyhodnocení různých datových struktur pro akceleraci vrhání paprsku je dizertační práce doc. V. Havrana (ČVUT) z roku 2000. Významnou odezvu našly rovněž práce z ČVUT věnující se pohledově závislé úpravě cenové funkce povrchové heuristiky. Nedávno představená metoda optimalizace hierarchie obalových těles (Fast Insertion Based Optimization of Bounding Volume Hierarchies) provádí globální optimalizaci topologie stromu s použitím vyjímání a opětovného vkládání uzlů hierarchie obalových těles na nové optimalizované pozice. Tato metoda v současnosti umožňuje postavit nejkvalitnější známé hierarchie obalových těles pro danou scénu. Metoda pracuje iterativně nad již existující hierarchií a je velmi jednoduché ji integrovat do stávajících zobrazovacích nástrojů. Metoda je například využita v rámci softwaru Virtual Reality Universal Toolkit (VRUT) vyvíjeného ve spolupráci ČVUT FEL a firmy Škoda Auto, a. s., (obr. 4).

Soubory

článek ve formátu pdf: V201512_706-709.pdf (437 kB)

Diskuse

Žádné příspěvky