Aktuální číslo:

2018/7

Téma měsíce:

Co kdyby…

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

Peníze z chemie, peníze pro chemii

Peníze z chemie, peníze pro chemii

Ondřej Vrtiška  |  16. 7. 2018
Manželé Hana a Dalimil Dvořákovi se seznámili v laboratoři. A nebylo to naposledy, co zaujetí pro organickou chemii ovlivnilo jejich životy i mimo...
Co když se probudí sopky pod antarktickým ledem?

Co když se probudí sopky pod antarktickým ledem?

John Smellie  |  16. 7. 2018
Antarktida je rozlehlá pustina pokrytá největším ledovým příkrovem světa, který obsahuje asi 90 % globálních zásob sladké vody. Funguje jako obří...
Ztracený potápník

Ztracený potápník uzamčeno

Josef Lhotský  |  16. 7. 2018
„Konference jsou od toho, abys tam navazoval styky a chlastal,“ řekl mi kdysi… — Povídka proplétající osudy tří velkých postav biologie.

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é