Prostorové hierarchie – klíč k rychlosti a detailu

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é