Aktuální číslo:

2017/12

Téma měsíce:

Kontakty

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

Tajemná „Boží země“ Punt

Tajemná „Boží země“ Punt uzamčeno

Břetislav Vachala  |  4. 12. 2017
Mnoho vzácného zboží starověkého Egypta pocházelo z tajemného Puntu, kam Egypťané pořádali časté obchodní výpravy. Odkud jejich expedice...
Hmyz jako dokonalý létací stroj

Hmyz jako dokonalý létací stroj

Rudolf Dvořák  |  4. 12. 2017
Hmyz patří k nejdokonalejším a nejstarším letcům naší planety. Jeho letové schopnosti se vyvíjely přes 300 milionů let a předčí dovednosti všech...
Hranice svobody

Hranice svobody uzamčeno

Stefan Segi  |  4. 12. 2017
Podle listiny základních práv a svobod, která je integrovaná i v Ústavě ČR, jsou „svoboda projevu a právo na informace zaručeny“ a „cenzura je...

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é