Porovnání vhodnosti a výkonu algoritmů pro okluzní odstřel

M ASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Porovnání vhodnosti a výkonu algoritmu˚ pro okluzní odstˇrel D IPLOMOVÁ PRÁCE

Zdenˇek Crha

Brno, 2006

Prohlášení Prohlašuji, že tato diplomová práce práce je mým puvodním ˚ autorským dílem, které jsem vypracoval samostatnˇe. Všechny zdroje, prameny a literaturu, které jsem pˇri vypracování používal nebo z nich cˇ erpal, v práci rˇ ádnˇe cituji s uvedením úplného odkazu na pˇríslušný zdroj.

Vedoucí práce: Mgr. Vít Kovalˇcík ii

Shrnutí S rostoucím uplatnˇením 3D grafiky v ruzných ˚ oblastech lidského života rostou také požadavky na komplexnost a realistiˇcnost zobrazovaných scén. Bohužel, aˇckoliv výkon grafických karet roste také, rychlost jeho rustu ˚ je nižší. Vykreslování všech objektu˚ ve scénˇe je proto pˇrístup, který pro rozsáhlé scény selhává. Aby bylo možno komplexní scény zobrazovat, je nutno použít ruzných ˚ metod ke snížení poˇctu trojúhelníku, ˚ které bude grafická karta vykreslovat. Algoˇ ritmy okluzního odstˇrelu patˇrí do kategorie odstˇrelu dle viditelnosti. Cas potˇrebný k vykreslení snímku snižují tím, že kreslí pouze trojúhelníky, které nejsou zastínˇeny objekty umístˇenými blíže k pozorovateli. V této práci jsem se zamˇerˇ il na implementaci tˇrí algoritmu˚ realizujících okluzní odstˇrel a porovnání jejich výkonu a vhodnosti použití na dvou ruzných ˚ 3D scénách.

iii

Klíˇcová slova 3D grafika, okluzní odstˇrel, Hierarchical Occlusion Maps, Prioritized Layered Projection, Hardware Depth Queries

iv

Podˇekování V první rˇ adˇe bych chtˇel podˇekovat své rodinˇe, která mi byla v tˇežkých chvílích oporou a nikdy mˇe nepˇrestala podporovat. Dále bych rád podˇekoval svému vedoucímu diplomové práce, Mgr. Vítu Kovalˇcíkovi, za zajímavé téma a podnˇetné rady.

v

Obsah I. Úvod 1. Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1. Cíle diplomové práce . . . . . . . . . . . . . . . . . . . . . . . . . . . II. Teoretická cˇ ást 2. Základní pojmy . . . . . . . . . . . 2.1. Odstˇrel . . . . . . . . . . . . . 2.2. Reprezentace objektu˚ a scény 2.3. Další pojmy . . . . . . . . . . 3. HDQ . . . . . . . . . . . . . . . . . 3.1. Popis algoritmu . . . . . . . . 3.2. Poznámky k algoritmu . . . . 4. HOM . . . . . . . . . . . . . . . . . 4.1. Popis algoritmu . . . . . . . . 4.2. Poznámky k algoritmu . . . . 5. PLP . . . . . . . . . . . . . . . . . . 5.1. Popis algoritmu . . . . . . . . 5.2. Poznámky k algoritmu . . . .

2 3 4

. . . . . . . . . . . . .

5 6 6 7 8 9 9 10 13 13 16 19 19 20

. . . . . . . . . . . .

25 26 26 27 27 28 28 28 31 33 33 33 34

IV. Závˇer 9. Závˇer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35 36

V.

38

III. Implementace a testování 6. Implementace . . . . . . . . . . . . 6.1. Hardware Depth Queries . . 6.2. Hierarchical Occlusion Maps 6.3. Prioritized Layered Projection 7. Testování . . . . . . . . . . . . . . . 7.1. Použité scény . . . . . . . . . 7.2. Porovnání algoritmu˚ . . . . . 7.3. Shrnutí . . . . . . . . . . . . . 8. Porovnání . . . . . . . . . . . . . . 8.1. Hardware Depth Queries . . 8.2. Hierarchical Occlusion Maps 8.3. Prioritized-Layered Projection

. . . . . . . . . . . . . . . . . . . . . . . . .

Pˇrílohy 1

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

ˇ Cást I.

Úvod

Kapitola 1

Úvod 3D grafika se uplatnuje ˇ ve stále více oblastech lidského života. Její aplikace usnadnují ˇ práci na mnoha místech, at’ již se jedná o technické obory jako návrh a konstrukce technických zaˇrízení nebo o diagnostiku stavu pacienta. Ale nejde jen o usnadnˇení a zkvalitnˇení práce, v podobˇe animovaných filmu˚ a poˇcítaˇcových her se stala nedílnou souˇcástí života dnešního cˇ lovˇeka. S rostoucím množstvím aplikací 3D grafiky, a hlavnˇe s rostoucími požadavky na detailnost a realistiˇcnost, se stále cˇ astˇeji setkáváme s nutností interaktivnˇe vykreslovat extrémnˇe velké množiny objektu. ˚ A nejde jen o vykreslování, jedná se také o vyhlazování obrazu, práci s texturami a další operace násobící nároˇcnost úkolu. Aˇckoliv rust ˚ výkonu grafických karet bˇehem uplynulých let nestagnoval a udˇelal velký krok kupˇredu, množství dat, které je nutno zpracovávat, rostlo mnohem rychleji. Proto ani nejmodernˇejší karty nejsou schopny zajistit, aby interaktivní vykreslování bylo plynulé a kvalitní bez aplikace sofistikovaných algoritmu. ˚ Grafické karty dokáží vykreslit jen urˇcitý poˇcet trojúhelníku˚ za jednotku cˇ asu. Pokud napˇríklad chceme dosáhnout zlepšení snímkové frekvence pˇri interaktivním vykreslování, je zapotˇrebí zmenšit poˇcet trojúhelníku, které musí karta vykreslovat bˇehem jednoho snímku. K tomu lze využít celou škálu metod. Algoritmy používající pˇri vykreslování úrovnˇe detailu (level of detail) aproximují velmi vzdálené objekty pomocí modelu˚ s menším poˇctem trojúhelníku. ˚ Vhodnˇe zvolená aproximace zachová siluetu objektu bez nutnosti vykreslovat detaily, které by stejnˇe nebyly rozpoznatelné. Další možností je použití celé škály algoritmu˚ z kategorie odstˇrelu neviditelných objektu˚ (visibility culling). Pomˇernˇe jednoduché jsou techniky odstˇrelu odvrácených trojúhelníku˚ (backface culling) a odstˇrelu trojúhelníku˚ mimo zorný úhel (view-frustum culling). Pˇres svoji jednoduchost jsou schopny výraznˇe snížit množství trojúhelníku˚ posílaných na grafickou kartu a urychlit tak vykreslení scény. Mezi techniky složitˇejší patˇrí okluzní odstˇrel (occlusion culling). Kritériem k odstˇrelu trojúhelníku˚ je zde zastínˇení objekty, které jsou blíže k pozici pozorovatele. ˇ Casto se ale stává, že použití jen jedné techniky nevede k požadovanému cíli. Skuteˇcnˇe dobrých výsledku˚ pak mužeme ˚ dosáhnout vhodnou kombinací jednotlivých metod odstˇrelu.

3

KAPITOLA 1. ÚVOD

1.1. CÍLE DIPLOMOVÉ PRÁCE

1.1. Cíle diplomové práce Cílem mé diplomové práce je implementovat vybrané algoritmy okluzního odstˇrelu a porovnat je z hlediska jejich výkonu a vhodnosti použití v nˇekolika testovacích scénách. Mezi vybrané patˇrí následující algoritmy: • Hierarchical Occlusion Maps • Prioritized Layered Projection • Hardware-Based Depth Queries

4

ˇ Cást II.

ˇ Teoretická cást

Kapitola 2

Základní pojmy Objektem je v této práci oznaˇcovaná skupina k sobˇe náležejících trojúhelníku. ˚ Napˇríklad množina trojúhelníku˚ tvoˇrících geometrii knihy je objektem.

2.1. Odstˇrel Odstˇrel dle viditelnosti (visibility culling) je termín, kterým oznaˇcujeme skupinu algoritmu, ˚ jejichž cílem je zvýšení rychlosti vykreslování. Zrychlení je dosaženo odstˇrelením (nekreslením) objektu, ˚ které nejsou v daný okamžik viditelné. Tyto algoritmy se dále dˇelí na nˇekolik skupin podle toho, na jaký typ neviditelných objektu˚ se zamˇerˇ ují. Algoritmy odstˇrelu zadních stˇen (backface culling) se soustˇred’ují na trojúhelníky, jejichž normálový vektor je oznaˇcuje jako odvrácené od pozorovatele. Tato technika je pˇrímo podporovaná nˇekterými API (napˇríklad OpenGL) ale lze ji využít jen v pˇrípadˇe, že objekty jsou uzavˇrené. Algoritmy odstˇrelu dle zorného úhlu (view-frustum culling) posílají na grafickou kartu jen ty objekty, které jsou v zorném úhlu kamery. Pˇri vhodném úhlu pohledu takto mužeme ˚ odstˇrelit i více než 90 % trojúhelníku˚ ve scénˇe. Algoritmy okluzního odstˇrelu (occlusion culling) kreslí jen objekty, které nejsou zastínˇené jinými, položenými blíže k pozici pozorovatele. Tyto algoritmy patˇrí mezi výpoˇcetnˇe nejnároˇcnˇejší. Všechny zmínˇené skupiny algoritmu˚ se vyplatí použít jen v pˇrípadˇe, že cˇ as ušetˇrený jejich nasazením pˇresáhne cˇ as vynaložený na výpoˇcet informací potˇrebných k jejich správné funkci. Konzervativní algoritmus implementující techniku odstˇrelu je takový algoritmus, který vždy vykreslí všechny viditelné objekty. U objektu˚ o nichž s jistotou nevíme, zda jsou nebo nejsou viditelné, pˇredpokládáme, že viditelné jsou a kreslí se také. Dusledkem ˚ tohoto postupu je vykreslení urˇcitého procenta objektu, ˚ které vidˇet nejsou. V nˇekterých pˇrípadech ale není vhodné být pˇríliš konzervativní. Napˇríklad pokud se ve scénˇe vyskytuje hustá mˇríž, objekty za ní nejsou pro celkový obraz duležité ˚ a proto mohou být zanedbány. Takovému postupu se rˇ íká agresivní odstˇrel.

6

˚ A SCÉNY KAPITOLA 2. ZÁKLADNÍ POJMY 2.2. REPREZENTACE OBJEKTU

2.2. Reprezentace objektu˚ a scény Ohraniˇcující objem (bounding volume) objektu je jeho prostorová aproximace sloužící ke snížení nároˇcnosti ruzných ˚ testu˚ týkajících se objektu. Napˇríklad pˇri odstˇrelu dle zorného úhlu nemusíme testovat, zda každý z nˇekolika stovek vrcholu˚ objektu je viditelný, místo toho napˇríklad otestujeme 8 vrcholu˚ ohraniˇcující krychle. Cenou za rychlejší vyhodnocení testu je menší pˇresnost, ale algoritmus zustává ˚ konzervativní. Existuje mnoho typu˚ ohraniˇcujících objemu. ˚ Nˇekolik pˇríkladu˚ mužete ˚ vidˇet na obrázcích 2.1 a až c, kde je 2D ohraniˇcující objem objektu znázornˇen cˇ árkovanou cˇ arou a svˇetle šedým pozadím.

(a) Ohraniˇcující cˇ tverec

(b) Ohraniˇcující kruh

(c) Osovˇe zarovnaný ohraniˇcující cˇ tverec

Obrázek 2.1.: Pˇríklady ohraniˇcujících objemu˚ Termínem bunka ˇ (cell) se oznaˇcuje oblast 3D prostoru urˇcená ohraniˇcujícím objemem a obsahující odkazy na všechny objekty, které se v ní nacházejí. V mnoha algoritmech se k tomuto úˇcelu využívá ohraniˇcující kvádr. Dalším prvkem hojnˇe využívaným v algoritmech poˇcítaˇcové grafiky je rozdˇelení prostoru scény (scene spatial subdivision). Obecnˇe se jedná o strukturu, která nˇejakým zpusobem ˚ dˇelí prostor na menší cˇ ásti a organizuje tak objekty ve scénˇe. K organizaci jednotlivých bunˇek, na které byl prostor scény rozdˇelen, se pak cˇ asto používá stromová struktura. Konkrétnˇe mužeme ˚ zmínit octree, bsp-tree nebo kd-tree. Cíl je stejný jako u ohraniˇcujících objemu˚ – zrychlení a usnadnˇení práce se scénou a objekty. Uniformní mˇrížka, jak již název napovídá, rozdˇeluje celou scénu na bunky ˇ stejné velikosti. Poˇcet bunˇek v jednotlivých osách se nemusí rovnat. Quad-tree je hierarchickou strukturou v 2D prostoru. Celá scéna je ohranicˇ ena obdélníkem. Pokud se v ohraniˇceném prostoru nachází víc než n objektu, ˚ obdélník rozdˇelíme na cˇ tyˇri menší. Vzniklé obdélníky rekurzivnˇe dˇelíme podle stejného kritéria. Každý obdélník je pak uzlem ve stromové struktuˇre. Pˇríklad konstrukce quad-tree je na obrázku 2.2. Šrafované obdélníky se již nebudou dále dˇelit. Zobecnˇením do trojrozmˇerného prostoru je octree. Zde dˇelíme každý kvádr obsahující víc než n objektu˚ na 8 menších. 7

KAPITOLA 2. ZÁKLADNÍ POJMY

(a) Poˇcáteˇcní stav

2.3. DALŠÍ POJMY

(b) První iterace

(c) Druhá iterace

Obrázek 2.2.: Konstrukce quad-tree

2.3. Další pojmy Termín projekce objektu (projection) oznaˇcuje oblast, do které byl objekt zobrazen pˇri jeho promítnutí z trojrozmˇerného prostoru scény do dvojrozmˇerného prostoru obrazovky.

8

Kapitola 3

Hardware Depth Queries Hardware Depth Queries [4] je konzervativní algoritmus rˇ ešící problém okluzního odstˇrelu. Prochází objekty ve scénˇe od nejbližších po nejvzdálenˇejší, pomocí tzv. hardwarových dotazu˚ testuje jejich viditelnost a viditelné vykresluje. Vzhledem k tomu, že objektu˚ muže ˚ být ve scénˇe mnoho a testovat každý zvlášt’ by bylo neefektivní, rozdˇelíme prostor scény na bunky ˇ a výsledek okluzního testu bunky ˇ využijeme k urˇcení viditelnosti všech objektu˚ v dané bunce. ˇ

3.1. Popis algoritmu Pˇredzpracování Prvním krokem, který musíme provést než zaˇcne vlastní vykreslování scény, je pˇríprava a inicializace datových struktur algoritmu. Bˇehem pˇredzpracování je prostor scény rozdˇelen na jednotlivé bunky ˇ pomocí uniformní mˇrížky a objekty jsou pˇriˇrazeny k bunkám, ˇ jejichž ohraniˇcující objem protínají. Pokud se objekt nachází na hranici nˇekolika bunˇek, je odkaz na nˇej pˇridán do každé z nich. Rozmˇery uniformní mˇrížky musí být zvoleny velmi peˇclivˇe, protože na nich pˇrímo závisí výkon algoritmu. Ideální stav nastane, jsou-li splnˇeny následující podmínky: • Každý objekt je pˇriˇrazen právˇe jedné bunce. ˇ • Vˇetšina bunˇek obsahuje víc než jeden objekt. • Velikost bunˇek je pˇrimˇerˇ ená. Co je pˇrimˇerˇ ená velikost a jak jí dosáhnout budeme diskutovat v sekci 3.2. Vlastní algoritmus Další krok algoritmu se provádí bˇehem vykreslování jednotlivých snímku. ˚ Málokterá aplikace se spokojí se statickým pohledem na scénu, je tedy nutné pocˇ ítat množinu viditelných objektu˚ pro každý snímek znovu. Protože viditelnost právˇe zpracovávané bunky ˇ testujeme vuˇ ˚ ci již vykresleným objektum, ˚ je nutné scénu procházet od bunˇek nejbližších po nejvzdálenˇejší. Každá bunka ˇ pak prochází dvˇema testy. 9

KAPITOLA 3. HDQ

3.2. POZNÁMKY K ALGORITMU

První zjišt’uje, zda se bunka ˇ nachází v zorném úhlu kamery. Tento krok není nezbytnˇe nutný. Bunky ˇ mimo zorný úhel nemají šanci projít hardwarovým okluzním testem a proto stejnˇe nebudou vykresleny. Hlavní duvod ˚ pro speciální test je jeho menší výpoˇcetní nároˇcnost. Druhý, okluzní test, se zpracovává na grafické kartˇe. Vstupem je ohraniˇcující objem testované bunky. ˇ Výstupem je informace o tom, zda by byly vykresleny nˇejaké pixely, pokud by se ohraniˇcující objem opravdu kreslil. Autoˇri algoritmu [4] k tomuto testu využili GL NV occlusion query, rozšíˇrení OpenGL vytvoˇrené firmou NVIDIA.

Obrázek 3.1.: Ilustrace k algoritmu Na obrázku 3.1 je zobrazena scéna rozdˇelená uniformní mˇrížkou a zorný úhel kamery. Jednotlivé bunky ˇ mˇrížky jsou znaˇceny jako viditelné (jednoduché šrafování), neviditelné (šrafování kˇrížem) a dosud netestované (bez šrafování).

3.2. Poznámky k algoritmu Rozmˇery uniformní mˇrížky Nastavení rozmˇeru˚ mˇrížky, kterou bude algoritmus používat, muže ˚ být komplikovaná záležitost. Problém nejsou celkové rozmˇery mˇrížky, ty jsou dány velikostí scény, ale poˇcet (rozmˇery) bunˇek ve smˇeru jednotlivých os. Zde se mužeme ˚ dostat do dvou extrému: ˚ První extrém je pˇríliš rˇídká mˇrížka. V takovém pˇrípadˇe jsou bunky ˇ hodnˇe velké, což snižuje jejich šanci na zastínˇení. A protože algoritmus urˇcuje viditelnost objektu˚ podle viditelnosti bunky ˇ do které patˇrí, bude mnoho zastínˇených objektu˚ zbyteˇcnˇe vykresleno. Druhý extrém pˇríliš hustá mˇrížka, pak budou bunky ˇ naopak velmi malé a dojde k následujícím obtížím: • Zvýší se poˇcet okluzních testu˚ a cˇ ást z nich budou testy zbyteˇcné (napˇr. testy bunˇek uvnitˇr objektu, ˚ testy bunˇek obsahující jeden a ten samý objekt). 10

KAPITOLA 3. HDQ


• Zvýší se pamˇet’ové nároky. • Dojde k tomu, že velké procento objektu˚ bude pˇriˇrazeno k více než jedné bunce ˇ a to zase zvýší poˇcet nutných pˇrístupu˚ k vlastnostem objektu˚ (napˇr. pˇríznak urˇcující zda objekt byl vykreslen v daném snímku).

ˇ Obrázek 3.2.: Rídká a hustá mˇrížka Pˇríklady jsou na obrázku 3.2. Budeme pˇredpokládat, že pozorovatel se nachází vlevo od mˇrížky a dívá se ve smˇeru osy z. V pˇrípadˇe, že použijeme pˇríliš rˇ ídkou mˇrížku (obrázek vlevo), tmavý objekt ve stˇredu scény je zastínˇen objektem vlevo od nˇej, ale bunka ˇ které je pˇriˇrazen zastínˇena není. Objekt proto bude vykreslen. V pˇrípadˇe, že použijeme pˇríliš hustou mˇrížku (obrázek vpravo), tmavý objekt v horní cˇ ásti scény bude patˇrit k 35-ti bunkám. ˇ Všech 35 bunˇek, je nutno otestovat na zastínˇení. Pˇet nejbližších k pozorovateli je viditelných, ale objekt se vykreslí jen jednou. Ze zbylých tˇriceti bunˇek ani jedna testem neprojde, ale protože všechny obsahují pouze již vykreslený objekt, tyto testy byly provedeny zbyteˇcnˇe. Na obrázku 3.3 je pak graf, který ukazuje zmˇenu výkonu algoritmu na scénˇe s knihovnou pˇri zmˇenˇe rozlišení mˇrížky. Základní použité rozlišení bylo 24×24× 24 bunˇek. Jemnˇejší a hrubší rozlišení pak mˇelo v každé ose o 50 % bunˇek více nebo ménˇe. Více o použitém zpusobu ˚ testování je v kapitole 7. Jedním z možných rˇ ešení tohoto problému je využití vhnízdˇených uniformních mˇrížek. Více k tomuto tématu je v [4] sekce 3.2. Okluzní testy pomocí rozšíˇrení OpenGL Pokud chceme použít k okluzním testum ˚ rozšíˇrení OpenGL, máme k dispozici hned nˇekolik možností. Jedním z prvních rozšíˇrení, které umožnovalo ˇ hardwarové okluzní testy, bylo rozšíˇrení HP occlusion test. Mˇelo a má však dvˇe hlavní nevýhody: 11

KAPITOLA 3. HDQ


Obrázek 3.3.: Rozdíl ve výkonu pˇri ruzných ˚ rozlišeních • Jako výsledek vrací pouze true/false. • Používá stop-and-wait model. Rozšíˇrení NV occlusion query rˇ eší oba rˇ eˇcené problémy. Toto rozšíˇrení použili i autoˇri algoritmu. • Jako výsledek vrací poˇcet pixelu, ˚ které prošly testem. • Nepoužívá stop-and-wait model. • Vyžaduje podporu HP occlusion test. Mužeme ˚ tedy iniciovat nˇekolik testu, ˚ chvíli poˇcítat na CPU jiné, s okluzními testy nesouvisející vˇeci, a pak se teprve ptát na výsledky. Lépe tak využijeme možnosti paralelního zpracování, které nám nabízí použití CPU a GPU zároven. ˇ Další možností je využít vracenou hodnotu k agresivnímu odstˇrelu bunˇek. Pokud je poˇcet pixelu, ˚ které prošly testem (a tudíž by byly vykresleny) menší než zadané n, rˇ ekneme, že pˇríspˇevek objektu˚ v bunce ˇ k celkovému obrazu je zanedbatelný a bunku ˇ prohlásíme za zastínˇenou. Rozšíˇrení ARB occlusion query je vylepšením NV occlusion query. Základní funkcionalita zustává ˚ stejná, obsahuje ale nˇekolik drobných vylepšení. Zpˇresnˇení názvosloví a hlavnˇe odstranˇení závislosti na HP occlusion test.

12

Kapitola 4

Hierarchical Occlusion Maps Algoritmus Hierarchical Occlusion Maps [7] se snaží jít jinou cestou než algoritmus Hardware Depth Queries. K testování objektu˚ na zastínˇení používá vlastní implementaci okluzního testu, která nevyužívá možností grafické karty. Jiným zpusobem ˚ je také rˇ ešen výbˇer objektu˚ do množiny stínících objektu. ˚

4.1. Popis algoritmu Vlastní algoritmus mužeme ˚ rozdˇelit na dva kroky. V prvním kroku se zabýváme výbˇerem do množiny stínících objektu. ˚ V druhém realizujeme test na zastínˇení vuˇ ˚ ci objektum ˚ vybraným v kroku prvním. Vzhledem ke zpusobu ˚ reprezentace zastínˇení ve scénˇe je vlastní test provádˇen opˇet ve dvou krocích. Nejprve zjistíme, zda projekce testovaného objektu padne do té samé oblasti jako projekce množiny stínících objektu. ˚ V pˇrípadˇe že tento test uspˇeje, ptáme se, jestli je testovaný objekt pˇred nebo za stínícími objekty. Výbˇer stínících objektu˚ Zatímco u pˇredchozího algoritmu jsme tento krok neprovádˇeli, respektive, stínícími objekty byla množina již vykreslených objektu, ˚ zde je nejduležitˇ ˚ ejší souˇ cˇ ástí. Cím bližší bude naše aproximace této množiny realitˇe, tím lepší výsledky bude algoritmus poskytovat. Bˇehem pˇredzpracování oznaˇcíme objekty, které mají jen malou pravdˇepodobnost, že zastíní velké množství jiných objektu. ˚ Autoˇri uvádˇejí celou škálu pˇrístupu˚ a kritérií pomocí kterých mužeme ˚ objekty oznaˇcovat. Patˇrí mezi nˇe napˇríklad velikost objektu. Další kritéria lze najít v [7], kapitola 7. Bˇehem zpracování snímku vybereme nˇekteré z neoznaˇcených objektu˚ a umístíme je do množiny stínících objektu. ˚ Výbˇer je provádˇen podle nˇekolika kritérií. Prvním z nich je umístˇení v zorném úhlu kamery, druhé kritérium není pevnˇe dané. Autor ve své práci uvádí dvˇe možnosti, jaké další kritérium použít. Obˇe pracují se vzdáleností testovaného objektu od pozorovatele, ale každé jiným zpu˚ sobem. • Výbˇer pomocí kritéria nazývaného Z-Plane zahrne do množiny stínících objektu˚ všechny objekty, jejichž vzdálenost je menší nebo rovna zadanému z. 13

KAPITOLA 4. HOM

4.1. POPIS ALGORITMU

• Pˇri použití Distance-based výbˇeru do množiny stínících objektu˚ pˇridáváme objekty nejménˇe vzdálené od pozorovatele. Souˇcet poˇctu trojúhelníku˚ ve vybraných objektech nesmí pˇresáhnout limit L. Jakmile máme vybrány stínící objekty, provedeme jejich vykreslení na obrazovku. Objekty se kreslí bíle na cˇ erné pozadí bez použití stínování, z-bufferu a v menším rozlišení. Získaný obraz ještˇe nepujde ˚ na výstup, použijeme ho ke konstrukci hierarchie okluzních map. Hierarchie okluzních map Okluzní mapa (occlusion map) je šedotóní obraz obsahující informaci o tom, které cˇ ásti obrazovky jsou zakryté vykreslenými stínícími objekty. Na obrázku 4.1 vlevo jsou zobrazeny dva stínící objekty. Na obrázku vpravo je pak zobrazena pˇríslušná okluzní mapa.

Obrázek 4.1.: Scéna a pˇríslušná okluzní mapa Práce s okluzní mapou vyššího rozlišení by se ale mohla stát úzkým místem algoritmu, proto používáme nˇekolik okluzních map uspoˇrádaných do hierarchie. Pˇríklad takové hierarchie map je na obrázku 4.2. O puvodní ˚ mapˇe s rozlišením width × height rˇ íkáme, že je úrovnˇe 0. Pixely v této mapˇe nabývají hodnot 1 a 0, kde hodnota 1 znaˇcí zastínˇenou oblast a hodnota 0 oblast nezastínˇenou. Hodnoty pixelu˚ v mapˇe úrovnˇe k +1 získáme jako aritmetický prumˇ ˚ er hodnot pixelu˚ v oblastech velikosti m × n pixelu˚ v mapˇe úrovnˇe k. Její rozlišení pak bude width × height . V takových mapách se vyskytují i hodnoty z intervalu h0, 1i, znaˇcící mk+1 nk+1 míru pruhlednosti ˚ mapy v daném místˇe.

14

KAPITOLA 4. HOM

(a) Úrovenˇ 0

4.1. POPIS ALGORITMU

(b) Úrovenˇ 2

(c) Úrovenˇ 4

Obrázek 4.2.: Pˇríklad hierarchie okluzních map Okluzní test Když testujeme objekt na zastínˇení postupujeme podle následujícího algoritmu: 1. Provedeme projekci ohraniˇcujícího objemu objektu do 2D prostoru obrazovky. 2. Vezmeme okluzní mapu nejvyšší úrovnˇe. 3. Procházíme pixely spadající do oblasti promítnutého ohraniˇcujícího objemu. 4.

• Pokud jsou všechny pixely nepruhledné ˚ (s hodnotou 1), testovaný objekt je považován za zastínˇený. • Pokud se v oblasti najde alesponˇ jeden pixel oznaˇcený jako pruhledný ˚ (s hodnotou 0), testovaný objekt je považován za viditelný. • Pokud nedojde ani k jednomu z výše uvedených pˇrípadu, ˚ vezmeme okluzní mapu o jedna nižší úrovnˇe a opakujeme krok 3.

Jednou z možností jak zvýšit poˇcet odstˇrelených objektu˚ a zrychlit test je povolit agresivnˇejší pˇrístup pˇri vyhodnocování testu. Zvolíme konstanty Tmin , Tmax ∈ h0, 1i tak, že 0 <= Tmin < Tmax <= 1. Nyní budeme považovat za nepruhledné ˚ všechny pixely jejichž hodnota je vˇetší nebo rovna Tmax a za pruhledné ˚ ty, jejichž hodnota je menší nebo rovna Tmin . Podrobnˇejší vysvˇetlení funkce a úˇcinku tˇechto konstant naleznete v [7], kapitola 5.3. Test na hloubku Druhou cˇ ást okluzního testu podstupují pouze objekty oznaˇcené v prvním kroku jako zastínˇené. Víme, že jejich projekce je ve stejné oblasti jako projekce množiny stínících objektu. ˚ Nyní je tˇreba zjistit, zda se nacházejí pˇred nebo až za množinou stínících objektu. ˚ Test se vyhodnocuje s použitím ohraniˇcujících objemu˚ promítnutých do prostoru obrazovky.

15

KAPITOLA 4. HOM


(a) Single depth plane

(b) Depth buffer

Obrázek 4.3.: Druhá fáze okluzního testu – test na hloubku. Existuje nˇekolik zpusob ˚ u, ˚ jak tento test provést. Nejjednodušší, ale zárovenˇ nejménˇe pˇresný je test pomocí jedné roviny (single depth plane). Rovina je nastavena do vzdálenosti rovnající se z souˇradnici zadní stˇeny nejvzdálenˇejšího ohraniˇcujícího objemu. Objekt bude prohlášen za viditelný, pokud se pˇrední stˇena promítnutého ohraniˇcujícího objemu testovaného objektu bude nacházet pˇred definovanou rovinou. Pˇresnˇejší výsledky pˇrinese rozdˇelení obrazovky na nˇekolik cˇ ástí a definování zadní roviny pro každou takovou cˇ ást (depth buffer). Platí, že pˇrední stˇena ohranicˇ ujícího objemu testovaného objektu musí být pˇred zadní rovinou alesponˇ jedné z oblastí, do kterých zasahuje. Jedinˇe pak bude objekt uznán za viditelný. Výhodou tohoto postupu je snadná škálovatelnost a vyšší pˇresnost. ˇ Na obrázku 4.3 jsou pˇríklady použití obou metod. Cást vlevo (4.3(a)) ukazuje použití jedné roviny a cˇ ást vpravo (4.3(b)) pˇet rovin na stejné modelové situaci. Stínící objekty mají výplnˇ šedou, viditelné bílou a zastínˇené cˇ ernou.

4.2. Poznámky k algoritmu Kritéria výbˇeru stínících objektu˚ (Dynamic Z-Plane) Autor ve své práci uvedl pouze dvˇe kritéria, které lze využít pˇri výbˇeru stínících objektu. ˚ Zde bych se chtˇel zamˇerˇ it na první z nich, kritérium Z-Plane. Pˇri jeho použití do množiny zahrneme všechny objekty jejichž vzdálenost od kamery je nejvýše z. Již autor upozornuje ˇ na to, že tento postup funguje dobˇre pouze tehdy, jsou-li objekty ve scénˇe rozmístˇeny rovnomˇernˇe. Jinak dochází k tomu, že kamera je od nejbližšího objektu dál než zadané z a množina zustává ˚ prázdná. Pro takové snímky je algoritmus redukován na vykreslení všech objektu˚ (s pˇrípadným použitím odstˇrelu dle zorného úhlu kamery) a cˇ as vynaložený na hledání stínících objektu˚ a poˇcítání hierarchie okluzních map je promarnˇen. 16

KAPITOLA 4. HOM


Tomuto lze ale pˇredejít jednoduchou úpravou kritéria. Místo abychom pocˇ ítali s nemˇenným z, budeme jej každý snímek modifikovat podle momentální situace. K vyhledání stínících objektu˚ pak použijeme hodnotu z = z + nearest kde nearest je vzdálenost k nejbližšímu objektu. Abychom nemuseli množinu potenciálních objektu˚ procházet dvakrát, jednou hledat nejbližší z nich a až podruhé vybírat stínící objekty, mužeme ˚ v prvním snímku vzít nearest = 0 a bˇehem výbˇeru najít nejbližší objekt. Tuto hodnotu pak použijeme v následujícím snímku. Nevýhodou je nepˇresnost v prvním snímku a ve snímcích následujících po stˇrihu kamery. Takto zajistíme, že množina stínících objektu˚ bude vždy neprázdná a výpocˇ etní cˇ as nebude promarnˇen. Všechna zde popsaná kritéria jsou implementovaná v testovací verzi algoritmu. Výbˇer stínících objektu˚ obecnˇe Další nevýhodou je, že algoritmus využívá jen aproximaci množiny stínících objektu. ˚ Mnoho objektu, ˚ které by poskytly dobré zastínˇení scény, není do množiny vybráno, protože kritéria pro výbˇer jsou pomˇernˇe jednoduchá a nedokáží stínící objekt rozpoznat v každé situaci.

Obrázek 4.4.: Problematická situace pˇri výbˇeru okludéru˚ Na obrázku 4.4 je zachycena typická situace, se kterou si ani jedno z diskutovaných kritérií nedokáže poradit. Šedé objekty v levé cˇ ásti obrázku jsou oznaˇceny jako stínící díky své blízkosti k pozici kamery. Velký šrafovaný objekt však takto oznaˇcen není, protože se nevejde do limitu (bud’ limitu na vzdálenost nebo na poˇcet trojúhelníku). ˚ Pˇritom je daleko lepším stínícím objektem než jakýkoliv již vybraný. 17

KAPITOLA 4. HOM


Otázkou je, zda složitˇejší (a výpoˇcetnˇe nároˇcnˇejší) kritéria jsou rˇ ešením které hledáme. Výbˇerové kritérium musí být aplikováno na tisíce nebo i desítky tisíc objektu˚ bˇehem jednoho snímku. Je velmi pravdˇepodobné, že vyšší režie pˇreváží nad urychlením algoritmu, které nasazení takového kritéria pˇrinese. Jedním z jednoduchých kroku, ˚ jak zvýšit úˇcinnost odstˇrelu je použití techniky podobné odstranˇení objektu, ˚ které nemají velkou šanci stát se dobrými stínícími objekty. Bˇehem pˇredzpracování mužeme ˚ naopak oznaˇcit ty, které budou témˇerˇ jistˇe poskytovat dobré zastínˇení scény. Ty pak do množiny pˇridáme pokaždé když budou v zorném úhlu kamery. Pokud máme napˇríklad scénu pˇredstavující budovu, pak stˇeny a podlahy zajisté padnou do této kategorie. Toto rˇ ešení má samozˇrejmˇe své problémy. Napˇríklad, zda požadovaný výbˇer mužeme ˚ udˇelat automaticky, bez nutnosti zásahu uživatele. Možné smˇery dalšího studia Jednou z nevýhod algoritmu prezentovaného v této kapitole je nutnost bˇehem každého snímku otestovat každý objekt. Použití vhodné struktury, která by sdružovala blízké objekty a umožnovala ˇ nám jedním testem ovˇerˇ it pˇríslušnost nˇekolika objektu˚ do množiny stínících objektu˚ najednou, by mohlo celý algoritmus urychlit. Možnost, která se nabízí jako první je použití uniformní mˇrížky, ale hledání odpovˇedi na tuto otázku leží za hranicemi urˇcenými zadáním této práce.

18

Kapitola 5

Prioritized Layered Projection V pˇredchozích kapitolách jsme si pˇredstavili dva ruzné ˚ algoritmy rˇ ešící okluzní odstˇrel. Oba dva se od sebe lišily jak použitými strukturami, tak zpusobem ˚ provádˇení okluzních testu. ˚ Algoritmus Prioritized-Layered Projection [5], na který se zamˇerˇ íme v této kapitole, sice rˇ eší stejný problém, ale na rozdíl od pˇredchozích se nesnaží o pˇresnou reprezentaci zastínˇení ve scénˇe. Místo aby zjišt’oval viditelnost objektu˚ a podle toho rozhodoval zda budou vykresleny, kreslí vždy pevný poˇcet trojúhelníku˚ vybraných pomocí heuristiky. Kombinací limitu na poˇcet trojúhelníku˚ vykreslených bˇehem jednoho snímku a výpoˇctu viditelnosti pomocí heuristické funkce dostáváme algoritmus, který není konzervativní. Tento fakt nejvíce odlišuje algoritmus PLP od algoritmu˚ diskutovaných v pˇredchozích kapitolách.

5.1. Popis algoritmu Výpoˇcet se opˇet dˇelí do dvou fází. V první fázi pˇripravíme strukturu rozdˇelující prostor ve scénˇe a pˇredpoˇcítáme míru nepruhlednosti ˚ jednotlivých bunˇek. Touto fází je nutné projít pouze jednou. Bˇehem druhé fáze, která se opakuje pˇri kreslení každého nového snímku, urcˇ ujeme aktuálnˇe viditelné bunky ˇ a vykreslujeme objekty k nim pˇriˇrazené. Pˇredzpracování K práci se scénou se používá octree modifikovaný tak, že každý uzel zná kromˇe svého rodiˇce a potomku˚ také všechny uzly, které s ním sousedí a v jakém smˇeru leží. Tyto dodateˇcné informace jsou nezbytnˇe nutné v okamžiku, kdy chceme octree procházet jinak než od koˇrene k listum. ˚ Octree je možné konstruovat dynamicky zárovenˇ s naˇcítáním scény. Teprve v okamžiku, kdy už se octree nebude mˇenit, mužeme ˚ zaˇcít vyhledávat sousedy jednotlivých listových bunˇek. K tomuto úˇcelu lze použít algoritmus [1], který nám zjistí sousedy bunky ˇ a smˇer v kterém leží. Dalším duležitým ˚ údajem, který musíme spoˇcítat bˇehem pˇredzpracování, je hustota (solidity) bunky. ˇ Toto cˇ íslo závisí na množství geometrie v bunce ˇ a zhruba odpovídá tomu, jak moc je bunka ˇ nepruhledná. ˚ 19

KAPITOLA 5. PLP


V dynamické cˇ ásti algoritmu se tato pˇredpoˇcítaná hodnota využívá k odhadu viditelnosti bunky ˇ bˇehem vykreslování snímku. V textu [5] je spoˇctena pomocí vztahu 5.1, kde triangles(A) znaˇcí poˇcet trojúhelníku˚ v bunce ˇ A a leaves je množina všech listových bunˇek octree. solidity(A) =

triangles(A) max{triangles(B)|B ∈ leaves}

(5.1)

V sekci 5.2 uvádím nˇekolik alternativ, které mohou za urˇcitých okolností dávat lepší výsledky. Dynamická cˇ ást Bˇehem této fáze využijeme pˇredpoˇcítaných hodnot a propagaˇcní funkce [5] k uspoˇrádání bunˇek podle míry, s jakou jsou vidˇet. Bunky ˇ se pak postupnˇe vykreslují dokud není dosažen zadaný limit L trojúhelníku. ˚ K uspoˇrádání bunˇek se používá prioritní fronta a bunky ˇ s nejmenší prioritou se ihned kreslí. Priorita bunky ˇ je rovna akumulované hustotˇe bunky ˇ (accumulated solidity) spoˇctené pomocí propagaˇcní funkce. Celý postup pak vypadá takto: 1. Najdeme bunku, ˇ která je nejblíž ke kameˇre a zárovenˇ je v jejím zorném poli. Bunce ˇ nastavíme prioritu 0 a zaˇradíme ji do fronty. 2. Vyjmeme první bunku ˇ ve frontˇe. Vykreslíme její obsah. 3. Všem dosud nevykresleným sousedum ˚ bunky ˇ upravíme prioritu podle výsledku˚ propagaˇcní funkce. Sousední bunky, ˇ které dosud nebyly zaˇrazené do fronty, zaˇradíme. 4. Kroky 2 a 3 opakujeme tak dlouho, dokud fronta není prázdná nebo dokud nedosáhneme limit L vykreslených trojúhelníku. ˚ Propagaˇcní funkce poˇcítá prioritu (akumulovanou hustotu) bunky ˇ B na základˇe vlastností dˇríve vykreslených bunˇek. Výsledná hodnota pak rˇ íká, jak moc je soused B bunky ˇ A zastínˇen bunkou ˇ A a všemi dˇríve vyhodnocenými bunkami. ˇ Vztah pro výpoˇcet vypadá takto: ρB = solidity(A) + (~v · ηAB ~ ) · ρA

(5.2)

Kde ρA , ρB jsou po rˇ adˇe akumulované hustoty bunˇek A a B, ~v je vektor pohledu kamery a ηAB ~ je normálový vektor stˇeny spoleˇcné bunkám ˇ A a B.

5.2. Poznámky k algoritmu Algoritmus diskutovaný v této kapitole nabízí ze všech tˇrí nejvíce možností k další práci. Prostor pro zlepšování se nachází snad v každé cˇ ásti algoritmu, strukturou použitou rozdˇelení prostoru poˇcínaje a propagaˇcní funkcí konˇce. 20

KAPITOLA 5. PLP


Rozdˇelení prostoru Jedním z rysu˚ algoritmu, který si zaslouží bližší prozkoumání je použitý zpu˚ sob rozdˇelení prostoru. V cˇ láncích [5] a [6] autoˇri uvádˇejí jako vhodné struktury kd-tree, octree nebo Delaunayho triangulaci. V cˇ lánku [2] dodávají bez dalšího vysvˇetlení, že ze všech testovaných struktur se jako nejvhodnˇejší ukázala právˇe Delaunayho triangulace. Bˇehem své práce jsem narazil na problém s použitím octree, který mohl být jedním z duvod ˚ u˚ pro odmítnutí této struktury. Zdrojem problému není samotná struktura rozdˇelení prostoru, ale její kombinace s použitou propagaˇcní funkcí. Pˇríklad je na obrázku 5.1. Podle toho, v jakém poˇradí vyhodnotíme jednoduše a kˇrížem šrafovanou bunku, ˇ dojde k výpoˇctu akumulované hustoty pouze z údaju˚ o druhé vyhodnocené bunce. ˇ Šedá bunka ˇ tedy bude mít prioritu mnohem menší než by mˇela a v horším pˇrípadˇe bude vykreslena, pˇrestože je témˇerˇ úplnˇe zastínˇená.

Obrázek 5.1.: Problematická situace pˇri použití octree v PLP K nesprávnému vykreslování dochází v dusledku ˚ nesprávného poˇcítání kumulativního zastínˇení v pˇrípadˇe, že nˇekolik bližších bunˇek sdílí stejnou stˇenu s jednou vzdálenˇejší. Tato situace je navíc u octree pomˇernˇe bˇežná. Problémum ˚ lze pˇredejít modifikací propagaˇcní funkce (viz dále) nebo použitím Delaunayho triangulace. Výpoˇcet solidity Založit výpoˇcet hustoty bunky ˇ na poˇctu trojúhelníku˚ v bunce ˇ se ukázalo v nˇekterých pˇrípadech jako nevyhovující. Konkrétnˇe v okamžiku, kdy scéna obsahuje objekty složené z velmi rozdílných poˇctu˚ trojúhelníku˚ (napˇríklad koule a krychle) nebo když se velikost trojúhelníku výraznˇe liší. Problém je ilustrován na obrázku 5.2. Pˇredpokládejme, že maximální poˇcet trojúhelníku˚ v libovolné bunce ˇ je 1000. Dále pˇredpokládejme, že koule se skládá 21

KAPITOLA 5. PLP


ze 320-ti malých trojúhelníku˚ a krychle ze 12-ti trojúhelníku. ˚ Je zˇrejmé, že krychle na obrázku 5.2(a) stíní šrafovanou bunku ˇ více než koule 36 na obrázku 5.2(b). Ale v pˇrípadˇe 5.2(a) je hustota bunky ˇ solidity() = 1000 av 320 pˇrípadˇe 5.2(b) je solidity() = 1000 . Tedy výpoˇcet rˇ íká, že bunka ˇ obsahující malou kouli je ménˇe pruhledná ˚ než bunka ˇ obsahující tˇri velké krychle.

(a) Krychle (3*12 △)

(b) Koule (320 △)

Obrázek 5.2.: Ilustrace k problému puvodního ˚ pˇrístupu k poˇcítání solidity Pokud se scéna skládá z objektu, ˚ je lepší využít ohraniˇcujících objemu˚ objektu˚ jako základu pro výpoˇcet hustoty bunky. ˇ Jednou z možností jak výpoˇcet definovat je vztah 5.3. P

volume(BVo ∩ BVA ) (5.3) max{volume(BVB )|B ∈ leaves} Kde BVo , o ∈ A je ohraniˇcující objem objektu o obsaženého v bunce ˇ A. Funkce volume() pak vrací objem pruniku/sjednocení ˚ ohraniˇcujících objemu. ˚ Vzhledem k tomu, že hustota bunky ˇ se poˇcítá pouze jednou, pˇri pˇredzpracování, mužeme ˚ použít i velmi složité algoritmy k co nejreálnˇejšímu vyjádˇrení hustoty. Napˇríklad pˇredpis 5.4 se snaží co nejvˇernˇeji spoˇcítat objem zabraný objekty v bunce ˇ a podle toho pak urˇcit hustotu. solidity(A) =

o∈A

S

volume( o∈A (BVo ∩ BVA )) solidity(A) = max{volume(BVB )|B ∈ leaves}

(5.4)

Propagaˇcní funkce Další možné zlepšení algoritmu se týká propagaˇcní funkce. Tak jak je uvedena v [5] trpí nˇekolika neduhy. • Závislost priority bunky ˇ na poˇradí vyhodnocení jejích pˇredchudc ˚ u˚ v pˇrípadˇe, že více bunˇek sdílí jednu stˇenu s jedním sousedem. • Akumulovaná hustota je poˇcítána na základˇe údaju˚ jen jedné pˇredcházející bunky. ˇ 22

KAPITOLA 5. PLP


• Rozdílný zpusob ˚ pˇrenosu hustoty a akumulované hustoty (priority) do sousední bunky. ˇ První dva problémy jsou vzájemnˇe provázané. Když se znovu podíváme na situaci na obrázku 5.1, zjistíme, že v závislosti na poˇradí vyhodnocování pˇredchudc ˚ u˚ se bude priorita šedé bunky ˇ mˇenit. Použití Delaunayho triangulace tento problém rˇ eší. Na obrázku 5.3 je jiná situace, kde každou jednu stˇenu sdílí právˇe dvˇe bunky. ˇ Po vyhodnocení bunky ˇ A bude ρC = solidity(A) + (~v · η~AC ) · ρA Ale bˇehem vyhodnocení bunky ˇ B se tato hodnota pˇrepíše novou hodnotou ρC = solidity(B) + (~v · ηBC ~ ) · ρB Pˇritom správný výsledek by mˇel být ρC = solidity(B) + solidity(A) + (~v · ηBC ~ ) · ρB + (~v · η~AC ) · ρA

Obrázek 5.3.: Chybné vyhodnocení akumulované hustoty V tomto pˇrípadˇe použití Delaunayho triangulace problém nevyˇreší. Z uvedeného pˇríkladu by již mˇela být zˇrejmá potˇrebná úprava propagaˇcní funkce. Vztah 5.5 uvádí nový pˇredpis pro výpoˇcet akumulované hustoty bunky. ˇ ρB = ρB + solidity(A) + (~v · ηAB ~ ) · ρA

(5.5)

Aby nový pˇredpis fungoval správnˇe, je nutné do algoritmu pˇridat omezení na vkládání do fronty. Bunku ˇ lze zaˇradit pouze v pˇrípadˇe, že hodnota akumulované hustoty se již nebude mˇenit. Tedy všechny sousední bunky, ˇ které jsou blíž k pozorovateli, jsou již vykreslené. 23

KAPITOLA 5. PLP


Dalším problémem pˇredpisu 5.2 i upraveného 5.5 je rozdílný pˇrístup k pˇrenosu hustoty a akumulované hustoty do sousední bunky. ˇ Hustota (zastínˇení), kterou bunka ˇ A nasbírala od svých pˇredchudc ˚ u, ˚ je pˇredána jen cˇ ásteˇcnˇe, v závislosti na úhlu pohledu a normálovém vektoru spoleˇcné stˇeny. Vlastní hustota bunky ˇ A je pˇredána celá. Takový postup je nereálný. Lepší rˇ ešení by bylo aplikovat na hustotu A stejný postup jako na akumulovanou hustotu (5.6). ρB = (solidity(A) + ρA ) · (~v · ηAB ~ )

(5.6)

Vztah 5.7 pak kombinuje úpravu 5.5 s úpravou 5.6. ρB = ρB + (solidity(A) + ρA ) · (~v · ηAB ~ )

24

(5.7)

ˇ Cást III.

Implementace a testování

Kapitola 6

Implementace Pro testování implementovaných algoritmu˚ byl vytvoˇren Tsubame 3D Engine. Vývoj probíhal v programovacím jazyce C++ s použitím integrovaného prostˇredí Bloodshed Dev-C++ na systému Microsoft Windows. K realizaci nˇekterých vlastností byly použity knihovny z jiných zdroju: ˚ • Knihovna SDL pro práci s okny a k ovládání programu. • Knihovna OpenGL k vykreslování. • Knihovna pro práci s PLY soubory G. Turka. • Knihovna pro naˇcítání dat z INI souboru˚ od A. Griffina. • Zdrojový kód k interpolaci Catmull-Rom Spline poskytl V. Kovalˇcík. V Tsubame 3D Engine byly implementovány následující vlastnosti: • Naˇcítání geometrie z textových souboru˚ formátu *.ply nebo *.obj. • Procházení scény po definované kˇrivce nebo dle pokynu˚ uživatele. • Odstˇrel zadních stˇen a odstˇrel dle zorného úhlu [3]. • Možnost zobrazení ohraniˇcujících objemu. ˚ • Zobrazování statistik o prubˇ ˚ ehu vykreslování a možnost jejich ukládání do souboru. • Algoritmy okluzního odstˇrelu z kapitol 3, 4 a 5. Kompletní popis ovládání programu a nastavení konfiguraˇcních souboru˚ je pˇriložen na CD spolu s programem.

6.1. Hardware Depth Queries Implementovaný algoritmus využívá uniformní mˇrížku bez možnosti vhnízdˇení dalších mˇrížek do jednotlivých bunˇek. K hardwarovým dotazum ˚ se používá rozšíˇrení OpenGL GL NV occlusion query. Mezi parametry algoritmu, které je možno nastavit patˇrí: • Poˇcet bunˇek mˇrížky v jednotlivých osách. 26

KAPITOLA 6. IMPLEMENTACE

6.2. HIERARCHICAL OCCLUSION MAPS

• Poˇcet najednou iniciovaných hardwarových dotazu. ˚ • Množství pixelu, ˚ které musí projít okluzním testem, aby bunka ˇ byla považována za zastínˇenou.

6.2. Hierarchical Occlusion Maps Jsou zde implementována všechna tˇri kritéria pro výbˇer okludéru˚ zmínˇená v kapitole 4. V pˇrípadˇe, že je kamera ovládána ruˇcnˇe uživatelem, je možno zobrazit používané okluzní mapy. Mezi parametry algoritmu, které je možno nastavit patˇrí: • Kritérium výbˇeru stínících objektu˚ a jeho parametr. • Rozlišení základní okluzní mapy a jak velká oblast bude prumˇ ˚ erována. • Poˇcet úrovní a poˇcet aktivních úrovní hierarchie okluzních map. • Hodnoty konstant Tmin , Tmax . • Poˇcet zadních rovin v rˇ ádcích a sloupcích.

6.3. Prioritized Layered Projection Implementace algoritmu Prioritized-Layered Projection využívá k rozdˇelení prostoru octree se všemi jeho výhodami a nevýhodami. K výpoˇctu hustoty jednotlivých listových bunˇek je možné použít dva postupy. A to výpoˇcet založený na poˇctu trojúhelníku˚ v bunce ˇ a výpoˇcet založený na vztahu 5.3 z kapitoly 5. Limit na poˇcet vykreslených trojúhelníku˚ je možno nastavit absolutnˇe, nebo jako procentuální cˇ ást scény. Pˇri kompilaci je možné zvolit, jestli se má používat originální nebo modifikovaná propagaˇcní funkce. Modifikovaná funkce byla popsána v kapitole 4 vztahem 5.6.

27

Kapitola 7

Testování Implementované algoritmy byly testovány na dvou scénách s použitím poˇcítaˇce s následujícími parametry: • Procesor Intel Celeron 2 GHz. • Operaˇcní pamˇetí 256 MB RAM. • Grafická karta ATI RADEON 9200. • Operaˇcní systém MS Windows XP.

7.1. Použité scény Knihovna První scénou použitou k testování je model osmipatrové knihovny s centrální šachtou umožnující ˇ pohled do ostatních pater. Model se skládá z 129.530 objektu, ˚ tvoˇrených 9 miliony trojúhelníky. Modely objektu˚ byly vytvoˇreny v programu Blender, k jejich kompozici do scény byly použity programy vlastní výroby. Velikost jednotlivých objektu˚ se pohybuje od 12 do 600 trojúhelníku. ˚ Náhodná zmˇet’ Druhou použitou scénou je náhodná zmˇet’ objektu. ˚ Scéna obsahuje 5.000 objektu, ˚ celkový poˇcet trojúhelníku˚ je 9,25 milionu. Použito bylo 5 ruzných ˚ modelu˚ z internetových stránek pˇredmˇetu Introduction to Computer Graphics vyuˇcovaného na Northwestern University v Illinois, USA. Každý model je složen z 1.850 trojúhelníku. ˚

7.2. Porovnání algoritmu˚ Existuje nˇekolik kritérií podle kterých by bylo možné porovnat výkon jednotlivých algoritmu. ˚ Protože se jedná o okluzní odstˇrel, jako první kritérium se nabízí poˇcet odstˇrelených trojúhelníku. ˚ Toto kritérium však nedokáže zachytit 28

˚ 7.2. POROVNÁNÍ ALGORITMU

KAPITOLA 7. TESTOVÁNÍ

jeden duležitý ˚ aspekt na kterém závisí výkon posuzovaného algoritmu. A to nároˇcnost režijních výpoˇctu. ˚ Proto jsem k porovnání použil kritérium založené na cˇ ase vykreslení jednoho snímku. Díky tomu se podaˇrilo zachytit celkový pohled na výkon algoritmu, ˚ na zlepšení výkonu dosažené díky okluznímu odstˇrelu a na degradaci tohoto zlepšení v dusledku ˚ zvýšených nároku˚ na režii. Bˇehem každého bˇehu programu kamera procházela scénou po pˇredem definované kˇrivce a po vykreslení každého snímku se ukládaly statistické údaje o prubˇ ˚ ehu. Na kˇrivce bylo urˇceno 250 bodu, ˚ ve kterých se snímky kreslily. S použitím odstˇrelu dle zorného úhlu Na obrázku 7.2 je vykreslen graf závislosti cˇ asu vykreslení snímku na pozici kamery na kˇrivce. Pˇri tomto mˇerˇ ení byl použit odstˇrel odvrácených trojúhelníku˚ a odstˇrel dle zorného úhlu. Použita byla scéna s knihovnou. Prubˇ ˚ eh grafu, kdy nebyl použit žádný algoritmus okluzního odstˇrelu, vezmeme jako základní mˇerˇ ítko. Zajímat nás budou místa, kde se nachází vrcholy grafu. Ve snímcích jim pˇríslušným je velká cˇ ást scény v zorném úhlu kamery a proto je na nich nejvíce vidˇet dosažené zrychlení vykreslování. Jako první se podíváme na graf pˇríslušný algoritmu Hardware Depth Queries. Hodnoty grafu se drží pod hranicí 500 milisekund bez vˇetších výkyvu, ˚ lokální maxima jsou ve stejných místech jako u referenˇcního grafu, ale nárust ˚ hodnot je minimální.

(a) Celkový pohled na knihovnu

(b) Regály s knihami

Obrázek 7.1.: Chybné vykreslení snímku˚ algoritmem PLP Prubˇ ˚ eh grafu patˇrícího algoritmu Hierarchical Occlusion Maps se také drží pod referenˇcním grafem, ale zlepšení není ani zdaleka tak výrazné jako u pˇredchozího algoritmu. V nˇekterých snímcích se projevil problém s výbˇerem stínících objektu˚ a výsledné cˇ asy v takovém pˇrípadˇe kopírují nebo dokonce pˇrevyšují hodnoty dosažené bez použití okluzního odstˇrelu. Ani algoritmus Prioritized-Layered Projection nedosahuje tak dobrých cˇ asu˚ jako 29

˚ 7.2. POROVNÁNÍ ALGORITMU


Hardware Depth Queries, na druhou stranu jeho graf neobsahuje výrazné výkyvy hodnot nad 750 milisekund. Vysoké rychlosti bez výrazných výkyvu˚ je zde ale dosaženo na úkor kvality obrazu. Ve výsledném obraze chybí objekty, které by mˇely být vidˇet, a naopak jsou vykresleny objekty, které vidˇet nejsou. Na obrázku 7.1 jsou dva pˇríklady chybného vykreslení. Na 7.1(a) je pohled na celou knihovnu, kde víc než polovina budovy chybí. Na obrázku 7.1(b) je snímek z vnitˇrku knihovny. Zde chybí knihy v pˇredních regálech.

Obrázek 7.2.: Vykreslení s odstˇrelem dle zorného úhlu

Bez použití odstˇrelu dle zorného úhlu Naprosto odlišná situace nastane v okamžiku, kdy bˇehem vykreslování nepoužijeme odstˇrel dle zorného úhlu. Pˇríslušné grafy jsou na obrázku 7.3, použita byla opˇet scéna s knihovnou. ˇ Casy vykreslení jednotlivých snímku˚ bez použití okluzního odstˇrelu jsou dle oˇcekávání všechny stejné. Prubˇ ˚ eh tohoto grafu opˇet vezmeme jako mˇerˇ ítko, vuˇ ˚ ci kterému budeme porovnávat prubˇ ˚ ehy grafu˚ ostatních algoritmu. ˚ Prubˇ ˚ eh grafu algoritmu Hardware Depth Queries nedoznal témˇerˇ žádné zmˇeny. Hodnoty v lokálních maximech jsou lehce vyšší než v pˇredchozím pˇrípadˇe, ale nepˇresahují 600 milisekund. Jak bylo rˇ eˇceno v kapitole 3, hardwarový okluzní test zastane i funkci testu na pˇrítomnost v zorném úhlu kamery. U algoritmu Hierarchical Occlusion Maps je situace jiná. Výkon tohoto algoˇ vykreslení vˇetšiny ritmu se bez odstˇrelu dle zorného úhlu výraznˇe zhoršil. Cas snímku˚ je sice kratší než u referenˇcního grafu, ale stále nˇekolikanásobnˇe delší 30


7.3. SHRNUTÍ

oproti pˇredchozím výsledkum. ˚ U zbylých snímku˚ cˇ as potˇrebný na výpoˇcet pˇresáhl cˇ as ušetˇrený aplikací algoritmu. Zhoršení je zpusobeno ˚ hlavnˇe chybným výbˇerem stínících objektu. ˚ Použitá kritéria jsou stavˇena tak, že vybírají z objektu˚ v zorném úhlu kamery. Zahrnutí všech objektu˚ do výbˇeru zpusobilo, ˚ že jako stínící objekt mohl být vybrán i objekt za kamerou. Tím došlo k zhoršení kvality aproximace zastínˇení ve scénˇe a následným špatným výsledkum ˚ celého algoritmu. Algoritmus Prioritized-Layered Projection dopadl ještˇe huˇ ˚ re než algoritmus Hierarchical Occlusion Maps. K nízké kvalitˇe výsledného obrazu se pˇridalo drastické zhoršení výkonu. To bylo zpusobeno ˚ nárustem ˚ velikosti prioritní fronty a tím prodloužení cˇ asu vyhledání a umístˇení uzlu.

Obrázek 7.3.: Vykreslení bez odstˇrelu dle zorného úhlu

7.3. Shrnutí Na grafech získaných bˇehem testování algoritmu˚ na scénˇe s knihovnou jsme porovnali zlepšení dosažené jednotlivými algoritmy. Testování na druhé scénˇe potvrdilo, až na dvˇe výjimky, výsledky vyplývající z testování scény s knihovnou. První výjimkou byl bˇeh algoritmu Prioritized-Layered Projection bez použití odstˇrelu dle zorného úhlu. Díky menšímu poˇctu bunˇek ve scénˇe (osmkrát ménˇe) nedošlo k výrazné degradaci výkonu. Problém s ménˇe kvalitním obrazem však zustal. ˚ Druhou výjimkou byly oba bˇehy algoritmu Hierarchical Occlusion Maps. Zde 31


7.3. SHRNUTÍ

se algoritmu nepodaˇrilo dosáhnout výraznˇejšího zlepšení, pˇri bˇehu s odstˇrelem dle zorného úhlu cˇ as potˇrebný k výpoˇctu pˇresáhl cˇ as ušetˇrený. Pˇres tyto dvˇe odlišnosti, poˇradí algoritmu˚ zustává ˚ stejné. Grafy prezentované v této kapitole a další grafy získané bˇehem testování algoritmu˚ jsou uvedeny v pˇríloze.

32

Kapitola 8

Porovnání V této kapitole se podíváme na vlastnosti jednotlivých algoritmu˚ a jakým zpu˚ sobem ovlivnují ˇ výkon a možné nasazení algoritmu˚ v praxi.

8.1. Hardware Depth Queries Tento algoritmus bˇehem testování dosahoval nejlepších výsledku. ˚ Je konzervativní a v rychlosti vykreslování scény ho pˇredstihl pouze algoritmus PrioritizedLayered Projection. Mezi kladné stránky algoritmu patˇrí: • Paralelní zpracování s využitím procesoru grafické karty. • Výbˇer stínících objektu˚ je velmi blízký realitˇe. • Možnost použití agresivního odstˇrelu. Další výhodnou vlastností je schopnost okluzního testu nahradit chybˇející odstˇrel dle zorného úhlu kamery. Hlavním záporem algoritmu Hardware Depth Queries je požadavek na grafickou kartu urˇcitých vlastností. Na druhou stranu, nejedná se o závažný problém. Požadované vlastnosti (podpora OpenGL rozšíˇrení NV occlusion query a lepších) již nejsou výsadou nových a drahých karet, ale témˇerˇ standardním vybavením.

8.2. Hierarchical Occlusion Maps Hierarchical Occlusion Maps je také konzervativním algoritmem s možností agresivního odstˇrelu, ale trpí dvˇema problémy. Zaprvé, všechna testovaná kritéria výbˇeru stínících objektu˚ mají potíže s rozpoznáním dobrých, ale vzdálených, stínících objektu˚ (pˇríklad na obrázku 4.4). Zadruhé, tvorba hierarchie okluzních map je cˇ asovˇe nároˇcná, zvláštˇe když požadujeme vˇetší pˇresnost. V nˇekterých situacích režie algoritmu témˇerˇ pˇrevýšila dosažené zrychlení vykreslování.

33

KAPITOLA 8. POROVNÁNÍ

8.3. PRIORITIZED-LAYERED PROJECTION

8.3. Prioritized-Layered Projection Poslední algoritmus dosahoval bˇehem testu˚ nejlepších cˇ asu. ˚ Bohužel, vynikajících výsledku˚ dosáhl jen díky tomu, že není konzervativní. Tato nevýhoda více než vyváží výkon algoritmu, protože velká vˇetšina aplikací klade požadavky na kvalitu výsledného obrazu. Druhou závažnou nevýhodou je urˇcitá nedotaženost. V sekci 5.2 jsem zmínil nˇekolik chyb, které algoritmus obsahuje a zárovenˇ nastínil možnosti jejich rˇ ešení.

34

ˇ Cást IV.

ˇ Záver

Kapitola 9

Závˇer Cílem této diplomové práce bylo implementovat, otestovat a nakonec porovnat nˇekolik algoritmu˚ rˇ ešících problém okluzního odstˇrelu z hlediska jejich výkonnosti a vhodnosti použití. Vybrané byly celkem tˇri algoritmy, Hardware Depth Queries, Hierarchical Occlusion Maps a Prioritized-Layered Projection. Každý z nich je založen na jiném principu a k rozpoznávání zastínˇených objektu˚ používá jiných prostˇredku. ˚ Již bˇehem implementace vyšlo najevo, že nˇekteré algoritmy – zejména algoritmus Prioritized-Layered Projection – trpí netriviálními problémy a byl navržen zpusob ˚ jejich odstranˇení. Pˇri testování na dvou ruzných ˚ scénách se pak ukázalo, že nejlepších výsledku˚ dosahuje implementace algoritmu Hardware Depth Queries. Rozložení výpoˇctu mezi procesor a grafickou kartu spolu s postupným budováním reprezentace zastínˇení ve scénˇe mu vyneslo první pˇríˇcku. Pro nasazení do praxe se zdá být nejvhodnˇejší také díky tomu, že netrpí tolika neduhy jako další dva algoritmy. Druhé místo obsadil algoritmus Hierarchical Occlusion Maps, který sice dokázal ve vˇetšinˇe situací zvýšit rychlost vykreslování, ale jeho výpoˇcetní nároˇcnost a hlavnˇe ne vždy kvalitní výbˇer stínících objektu˚ mu zabránili v dosažení lepšího výsledku. V algoritmu Prioritized-Layered Projection bylo nalezeno vˇetší množství chyb a protože navíc není konzervativní, umístil se jako poslední. Po odladˇení chyb by se mohl uplatnit v systémech, kde záleží více na stabilní snímkové frekvenci než na kvalitˇe obrazu, nebo jako souˇcást jiného algoritmu. Výsledkem práce je pak program Tsubame 3D Engine s implementací výše uvedených algoritmu. ˚ Všechny algoritmy jsou plnˇe konfigurovatelné a proto je možné engine použít i k srovnávacím testum ˚ nastavení jednotlivých algoritmu. ˚ Další souˇcástí práce je rozsáhlý 3D model knihovny, opˇet využitelný k dalšímu testování. Další práce na tomto tématu by se mohla zamˇerˇ it právˇe na tuto oblast. Zaprvé, algoritmus Prioritized-Layered Projection nabízí mnoho možností jak ho vylepšit. Za druhé, jeho vlastnosti jsou pˇresnˇe tím, co je potˇrebné pro dobré kritérium výbˇeru stínících objektu˚ algoritmu Hierarchical Occlusion Maps. Kombinace tˇechto dvou algoritmu˚ by mohla pˇrinést lepší výsledky než jejich další zlepšování.

36

Literatura [1] P. Bhattacharya. Efficient neighbor finding algorithms in quadtree and octree, 2001. M.T. Thesis, Dept. Comp. Science and Eng., India Inst. Technology, Kanpur. [2] Wagner T. Correa, James T. Klosowski, and Claudio T. Silva. Fast and simple occlusion culling. [3] G. Gribb and Klaus Hartmann. Fast extraction of viewing frustum planes from the world-view-projection matrix, 2001. [4] K. Hillesland, B. Salomon, A. Lastra, and D. Manocha. Fast and simple occlusion culling using hardware-based depth queries, 2002. [5] J. T. Klosowski and C. T. Silva. The prioritized-layered projection algorithm for visible set estimation. IEEE Transactions on Visualization and Computer Graphics, 6(2):108–123, /2000. [6] James T. Klosowski and Cláudio T. Silva. Rendering on a budget: A framework for time-critical rendering. In David Ebert, Markus Gross, and Bernd Hamann, editors, IEEE Visualization ’99, pages 115–122, San Francisco, 1999. [7] Hansong Zhang. Effective occlusion culling for the interactive display of arbitrary models. Technical Report TR99-027, 1, 1998.

37

ˇ Cást V.

Pˇrílohy

Pˇrílohy V pˇríloze jsou k nahlédnutí grafy získané bˇehem testování jednotlivých algoritmu˚ na scénˇe s knihovnou a na scénˇe s mixem objektu. ˚ Ke každé scénˇe patˇrí cˇ tyˇri grafy, graf závislosti cˇ asu vykreslení na jednotlivých snímcích a graf vykreslené cˇ ásti scény v závislosti na jednotlivých snímcích. Oba tyto grafy jsou ve variantˇe s a bez použití odstˇrelu dle zorného úhlu. Další pˇrílohou pak je CD obsahující: • Text diplomové práce v elektronické podobˇe. • Program Tsubame 3D Engine. • Zdrojové kódy k programu. • Obˇe testovací scény s nastaveními použitými k testování. • Ukázkovou scénu a ukázkovou konfiguraci programu.

ˇ vykreslení s odstˇrelem dle zorného úhlu (knihovna) Obrázek 9.1.: Cas

39

Pˇrílohy

ˇ vykreslení bez odstˇrelu dle zorného úhlu (knihovna) Obrázek 9.2.: Cas

Obrázek 9.3.: Vykreslená cˇ ást s odstˇrelem dle zorného úhlu (knihovna) 40

Pˇrílohy

Obrázek 9.4.: Vykreslená cˇ ást bez odstˇrelu dle zorného úhlu (knihovna)

ˇ vykreslení s odstˇrelem dle zorného úhlu (mix objektu) Obrázek 9.5.: Cas ˚ 41

Pˇrílohy

ˇ vykreslení bez odstˇrelu dle zorného úhlu (mix objektu) Obrázek 9.6.: Cas ˚

Obrázek 9.7.: Vykreslená cˇ ást s odstˇrelem dle zorného úhlu (mix objektu) ˚ 42

Pˇrílohy

Obrázek 9.8.: Vykreslená cˇ ást bez odstˇrelu dle zorného úhlu (mix objektu) ˚

43

Seznam obrázku˚ 2.1. Pˇríklady ohraniˇcujících objemu˚ . . . . . . . . . . . . . . . . . . . . . 2.2. Konstrukce quad-tree . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 8

3.1. 3.2. 3.3.

Ilustrace k algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . ˇ Rídká a hustá mˇrížka . . . . . . . . . . . . . . . . . . . . . . . . . . . Rozdíl ve výkonu pˇri ruzných ˚ rozlišeních . . . . . . . . . . . . . . .

10 11 12

4.1. 4.2. 4.3. 4.4.

Scéna a pˇríslušná okluzní mapa . . . . . . . . . Pˇríklad hierarchie okluzních map . . . . . . . . Druhá fáze okluzního testu – test na hloubku. . Problematická situace pˇri výbˇeru okludéru˚ . .

. . . .

14 15 16 17

5.1. Problematická situace pˇri použití octree v PLP . . . . . . . . . . . . 5.2. Ilustrace k problému puvodního ˚ pˇrístupu k poˇcítání solidity . . . . 5.3. Chybné vyhodnocení akumulované hustoty . . . . . . . . . . . . .

21 22 23

7.1. Chybné vykreslení snímku˚ algoritmem PLP . . . . . . . . . . 7.2. Vykreslení s odstˇrelem dle zorného úhlu . . . . . . . . . . . . 7.3. Vykreslení bez odstˇrelu dle zorného úhlu . . . . . . . . . . . ˇ vykreslení s odstˇrelem dle zorného úhlu (knihovna) . . 9.1. Cas ˇ vykreslení bez odstˇrelu dle zorného úhlu (knihovna) . . 9.2. Cas 9.3. Vykreslená cˇ ást s odstˇrelem dle zorného úhlu (knihovna) . . 9.4. Vykreslená cˇ ást bez odstˇrelu dle zorného úhlu (knihovna) . ˇ vykreslení s odstˇrelem dle zorného úhlu (mix objektu) 9.5. Cas ˚ . ˇ vykreslení bez odstˇrelu dle zorného úhlu (mix objektu) 9.6. Cas ˚ . 9.7. Vykreslená cˇ ást s odstˇrelem dle zorného úhlu (mix objektu) ˚ . 9.8. Vykreslená cˇ ást bez odstˇrelu dle zorného úhlu (mix objektu) ˚

. . . . . . . . . . . .

29 30 31

. . . . . . . .

39 40 40 41 41 42 42 43

44

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . . . . . .

Porovnání vhodnosti a výkonu algoritmů pro okluzní odstřel

Recommend Documents