Aktuální číslo:

2021/2

Téma měsíce:

Stres

Prostorové hierarchie – klíč k rychlosti a detailu

 |  3. 12. 2015
 |  Vesmír 94, 706, 2015/12
 |  Seriál: Počítačová grafika, 4. díl (Předchozí)

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é

Nyní vidíte 18 % článku. Co dál:

Jsem předplatitel, mám plný přístup
Jsem návštěvník
Chci si přečíst celé číslo
Předplatným pomůžete zajistit budoucnost Vesmíru. Více o předplatném
OBORY A KLÍČOVÁ SLOVA: Počítače, internet

O autorovi

Jiří Bittner

Doc. Ing. Jiří Bittner, Ph.D., (*1972) vystudoval FEL ČVUT v Praze. Několik let působil jako výzkumný pracovník na TU Vídeň, pracoval i na několika komerčních projektech v oblasti počítačové grafiky. V současnosti přednáší na Katedře počítačové grafiky a interakce ČVUT FEL, zabývá se problematikou výpočtů viditelnosti v rozsáhlých scénách, prostorovými datovými strukturami a efektivními metodami vrhání paprsků.

Doporučujeme

Minimozky neandrtálců ve zkumavce

Minimozky neandrtálců ve zkumavce audio

Jaroslav Petr  |  27. 2. 2021
Jak se lišily mozky pravěkých lidí Homo sapiens od mozků neandrtálců a denisovanů? Tuto otázku chce zodpovědět vědecký tým s pomocí laboratorních...
Jak čelit nedůvěře v očkování?

Jak čelit nedůvěře v očkování?

Klesající proočkovanost v západním světě byla Světovou zdravotnickou organizací (WHO) označena za jednu z největších hrozeb budoucnosti. Jako...
Ať strom života rozkvete detaily

Ať strom života rozkvete detaily uzamčenovideo

Ondřej Vrtiška  |  1. 2. 2021
Jak se z jedné buňky vyvine složitý mnohobuněčný organismus? Jaké je genetické a molekulární pozadí obrovské rozmanitosti forem a tvarů, jimiž...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné