Univerzita Hradec Králové Fakulta informatiky a managementu Katedra informatiky a kvantitativních metod
Vegetace v trojrozměrné scéně (Interaktivní zobrazení trojrozměrné scény s vegetací) Bakalářská práce
Autor :
Jan Vašíček Aplikovaná informatika
Vedoucí práce :
Mgr. Jan Vaněk
Odborný konzultant:
Ing. Bruno Ježek, Ph.D.
Hradec Králové
duben 2005
Prohlášení: Prohlašuji, že jsem bakalářskou práci zpracoval samostatně a s použitím uvedené literatury.
V Kolíně dne 9.dubna 2005
Jan Vašíček
Poděkování: Děkuji vedoucímu bakalářské práce Mgr. Janu Vaňkovi a odbornému konzultantovi Ing. Brunovi Ježkovi, Ph.D. za veškerou pomoc při vypracování bakalářské práce.
Anotace Bakalářská práce se zabývá trojrozměrným zobrazováním rozsáhlé vegetace. Cílem práce je popsat dostupné algoritmy a zvolit nebo navrhnout nový přístup pro zobrazení vegetace na rozloze tisíců až desetitisíců kilometrů čtverečných. V práci je navrženo řešení na vykreslování rozsáhlé vegetace v reálném čase. Annotation This bachelor thesis deals with the three-dimensional visualization of a large-scale vegetation cover. The main aim of the thesis is to describe existing algorithms and to choose or to design a new approach that in real-time renders the vegetation covering a terrain of thousands square kilometers in size. A solution to the problem of a large-scale vegetation cover rendering in real-time is proposed in the thesis.
Obsah Seznam obrázků Seznam zkratek 1
Úvod ............................................................................................................................ 1
2
Existující metody ....................................................................................................... 3
3
4
2.1
Billboardy ............................................................................................................ 3
2.2
Objemové textury ................................................................................................ 4
2.3
Sprity a impostory ............................................................................................... 6
2.4
Listové zjednodušování ....................................................................................... 8
2.5
Plátkování a prolínáním..................................................................................... 10
2.6
Posouzení nalezených řešení ............................................................................. 13
Navrhované řešení ................................................................................................... 15 3.1
Tvorba vrcholů .................................................................................................. 17
3.2
Tvorba indexů.................................................................................................... 19
3.3
Textury .............................................................................................................. 20
3.3.1
Textury jednotlivých stromů ..................................................................... 21
3.3.2
Dlouhá textura ........................................................................................... 22
3.3.3
Neuspořádaná textura lesa ......................................................................... 23
3.4
Úrovně detailu ................................................................................................... 24
3.5
Ořezávání........................................................................................................... 25
Implementace........................................................................................................... 27 4.1
Použité technologie ........................................................................................... 27
5
Výsledky ................................................................................................................... 29
6
Závěr ......................................................................................................................... 31
7
Odkazy...................................................................................................................... 32
Seznam obrázků Obr. 1: Povrch bez vegetace ............................................................................................. 2 Obr. 2: Povrch s vegetací .................................................................................................. 2 Obr. 3: Klasický billboard (vlevo) a křížený billboard (vpravo) – převzato z [Szijártó03 ] ............................................................................................................. 3 Obr. 4: Buňky – převzato z [Decaudin04 ]...................................................................... 4 Obr. 5: Aperiodické pokrytí – převzato z [Decaudin04 ]............................................... 5 Obr. 6: Výsledky použití objemové textury – převzato z [Decaudin04 ]...................... 6 Obr. 7: Sprite (vlevo) a rozmístění spritů ve stromu (vpravo) – převzato z [Szijártó03] .............................................................................................................. 7 Obr. 8: Množství listí vykreslovaných do textury – převzato z [Szijártó03]................ 7 Obr. 9: Koruna stromu (vlevo) a 200 stromů tvořících les (vpravo) – převzato z [Szijártó03 ] ............................................................................................................. 8 Obr. 10: Zjednodušování stromu – převzato z [Inmacul02 ] ........................................ 9 Obr. 11: Výsledky použití listového zjednodušení - převzato z [Inmacul02 ]............ 10 Obr. 12: Slicing box (vlevo) a primární a sekundární sada plátků (vpravo) – převzato z [Jakulin2000] ......................................................................................... 11 Obr. 13: Popis jednoho plátu buňky.............................................................................. 15 Obr. 14: Popis půdorysu buňky ..................................................................................... 16 Obr. 15: Tvorba vrcholů ................................................................................................. 18 Obr. 16: Typy vykreslování trojúhelníků ..................................................................... 20 Obr. 17: Textury jednotlivých stromů........................................................................... 21 Obr. 18: Jedna buňka s texturou jednotlivých stromů ................................................ 22 Obr. 19: Dlouhá textura.................................................................................................. 22 Obr. 20: Jedna buňka s dlouhou texturou .................................................................... 23 Obr. 21: Neuspořádaná textura lesa .............................................................................. 23 Obr. 22: Jedna buňka s neuspořádanou texturou........................................................ 24 Obr. 23: Pomocný ořezávací objem ............................................................................... 26 Obr. 24: Vegetace s prvním nastavením........................................................................ 30 Obr. 25: Vegetace s druhým nastavením....................................................................... 30
Seznam zkratek CPU
central procesor unit
GIS
geografický informační systém
GPU
graphics procesor unit
LOD
level of detail
UHK
Univerzita Hradec Králové
1
Úvod S nárůstem výkonu a rozšířením výpočetní techniky se stále více uplatňují i
aplikace trojrozměrné počítačové vizualizace. Jednou z nejvýznamnějších oblastí nasazení výpočetní techniky jsou geografické informační systémy (dále jen GIS). GIS v současné době využívají trojrozměrné zobrazování geografických dat. Nedílnou součástí každého zemského povrchu je i vegetace, bez ní je vykreslený terén neúplný a působí nepřirozeně (viz Obr. 1 a 2). Proto je nezbytné vykreslovat povrch i s vegetací, aby byla krajina kompletní, měla přirozený vzhled a poskytovala co nejvíce informací. Pojem vegetace je velice široký, tento termín zahrnuje stromy, keře, trávu, mechy a další. Z tohoto důvodu jsou používána data vztahující se pouze ke stromům, protože zobrazování menších objektů na rozlehlém území by bylo výpočetně velice náročné. Tato práce si klade za cíl nalézt nebo vytvořit přístup pro zobrazování vegetace, kterým ji bude možné zobrazovat v reálném čase na území o rozloze tisíců až desetitisíců km2. Vegetace by měla být pozorována „z ptačí perspektivy“, neboť je kladen důraz na její celkové zachycení, více než na reálný vzhled jednotlivých stromů. Přesto by měly stromy vypadat co nejvěrohodněji a výsledná vegetace tvořená těmito stromy by měla mít reálnou hustou zalesnění. Konečný vybraný nebo navržený přístup bude testován na prototypu implementovaném jako aplikace, která bude interaktivně komunikovat s uživatelem. V následujících kapitolách se budeme zabývat přístupy pro řešení, některými problémy spojenými s implementací a testováním vytvořené aplikace.
1
Obr. 1: Povrch bez vegetace
Obr. 2: Povrch s vegetací
2
2
Existující metody Kapitola se zabývá nalezenými existujícími přístupy řešení problematiky
zobrazování vegetace v reálném čase. Na konci kapitoly je provedeno posouzení nalezených přístupů.
2.1
Billboardy Jedna
z nejstarších,
nejjednodušších
a
nejrozšířenějších
technik
real-time
zobrazování vegetace využívá k reprezentaci stromů billboardy. Je popsána například v [Decaudin04], [Szijártó03] nebo [Inmacul02]. Díky tomu, že billboardy jsou velmi nenáročné na výkon počítače, jsou stále považovány za jednu z nejlepších technik pro současné průmyslové simulátory. Metoda má dva odlišné směry. První z nich je klasický billboard, což je čtyřúhelník potažený kvalitní texturou. Při zobrazování je vždy plochou otočen ke kameře a většinou se otáčí kolem vertikální osy, která prochází jeho středem (viz Obr. 3 vlevo). Druhý směr se nazývá křížený billboard. Skládá se ze dvou až čtyř čtvercových nebo obdélníkových ploch křížících se navzájem (viz Obr. 3 vpravo).
Obr. 3: Klasický billboard (vlevo) a křížený billboard (vpravo) – převzato z [Szijártó03 ]
V první metodě se neprojevuje žádná paralaxa při pohybu kamery a nehodí se tedy příliš pro objekty, které nejsou osově souměrné. Vykreslovaný les musí být řídký, protože strom, který je těsně za jiným, by mohl při změně úhlu pohledu přejít náhle do popředí. Obě metody mají společný nedostatek v mizení stromů při pohledu shora. Při pohybu kamery nad takto vykresleným lesem se stromy pod pozorovatelem zobrazují jako roviny
3
kolmé k průmětně. U křížených billboardů se tento problém řeší přidáním dalšího čtyřúhelníku, na němž je nanesena textura koruny stromu. Tento čtyřúhelník bývá rovnoběžný se zemí. Ani jedna metoda nezahrnuje schéma úrovně detailu (dále jen LOD) pro jednotlivé stromy, protože se vytvořené stromy nedají více zjednodušit. Velmi hustý les vykreslovaný za pomoci této techniky by se skládal z miliónů otexturovaných čtyřúhelníků, což by bylo náročné i s moderním grafickým hardwarem.
2.2
Objemové textury Přístupem založeným na využití objemových textur se zabývá Decaudin a kol.
v [Decaudin04].
Metoda
kombinuje
objemové
textury
a
aperiodické
pokrytí.
Reprezentace lesa poskytuje kvalitní vykreslování díky vhodně zvolenému 3D nelineárnímu filtrování a spoléhá se na LOD a strukturu k udržení real-time výkonu, která je přátelská ke grafickému procesoru (dále jen GPU). Objemová textura reprezentuje pokrytí povrchu porostem. Použití objemové textury se skládá z nanášení 3D vrstev na povrch užívající 3D data k nastavení textury. Pro účely hardwarového urychlení je objem vykreslován pomocí sady plátků, která je autorem označována jako texcell a zde jako buňka. Nakonec jsou plátky v každé buňce otexturovány. Mezi výhody patří perfektní paralaxa, protože vytvářené plátky mají vlastní hloubku, a filtrování, jež je hladce řízeno texturovacím hardwarem.
Obr. 4: Buňky – převzato z [Decaudin04 ]
4
V přístupu jsou vytvářeny dva odlišné druhy buněk. Jednoduché pravidelné buňky (regular texcell), které mají dobrý výkon a kvalitu, ale nejsou vhodné pro zobrazování lesů blízko obrysu povrchu, a obrysové buňky (silhouette texcell). Pravidelné buňky (viz Obr. 4) jsou adaptovány pro většinu scény a tvoří je plátky rovnoběžné s povrchem. Lze je jednoduše vytvořit z povrchu a zároveň jsou efektivní, protože se jejich geometrie nemusí obnovovat a transformovat z CPU v každém snímku. Tento model je věrný až do doby, kdy se začíná projevovat a zvětšovat chyba paralaxy. V důsledku této chyby jsou jednotlivé plátky rozeznatelné, a proto se přechází k obrysovým buňkám (viz Obr. 4), které se spoléhají na orientované vytváření plátků. Tyto plátky jsou natočeny směrem k pozorovateli. Otáčení jednotlivých plátků je jednoduše prováděno vertikálním posunem jejich vrcholů. To dovoluje transformovat polygony předtím uchované v GPU místo jejich opětovného vytváření v CPU a tímto se samozřejmě omezuje provoz na sběrnici. V reprezentaci pravidelných buněk se místo 3D textury vytváří sada 2D textur, která koresponduje s plátky. Každá textura v 2D sadě má připojenou MIP-MAP pyramidu a zároveň se vytváří LOD pyramida sady. Pro reprezentaci obrysových buněk je použita 3D textura. LOD použité v tomto řešení závisí na vzdálenosti pozorovatele od slices a úhlu mezi směrovým vektorem pozorovatele a normálovým vektorem plátků.
Obr. 5: Aperiodické pokrytí – převzato z [Decaudin04 ]
5
Pokrytí terénu buňkami je prováděno pomocí aperiodického schématu. V tomto schématu mají buňky tvar trojúhelníků, které jsou mezi sebou různě hranově kompatibilní (viz Obr. 5). Je vyrobeno 16 možných trojúhelníků směřujících na sever a na jih, pro úsporu paměti z nich bylo však vybráno pouze 8 (4 směřují na jih a 4 na sever). Použitím výše popsaného řešení byl pokryt povrch lesem skládajícím se z 2 300 stromů a obnovovací frekvence se pohybovala mezi 25 a 40 snímky za vteřinu. Bylo použito 576 buněk a každá obsahovala 4 stromy. Také byl implementován rozlehlejší les skládající se z 37 000 stromů a z 9 212 buněk. Při těchto parametrech dosahovala obnovovací frekvence 20 až 30 snímků za vteřinu. Výsledky byly měřeny na osobním počítači
s procesorem
Pentium
4
o
frekvenci
1.7 GHz
a
grafickou
kartou
GeForceFX 5800. Výstupní rozlišení bylo 640 x 480. Velikost objemových dat byla 128 plátků o rozměrech 256x256 s 32bitovou hloubkou barev. Výsledky implementace jsou zobrazeny také na Obr. 6.
Obr. 6: Výsledky použití objemové textury – převzato z [Decaudin04 ]
Tato metoda je schopná zobrazovat velmi rozsáhlé terény pokryté vegetací a to i s vysokým stupněm detailu. Ale na druhou stranu se při zvyšování množství stromů ve scéně zvyšuje náročnost aplikace.
2.3
Sprity a impostory Tento algoritmus je popsán v [Szijártó03] a představuje zlepšené vykreslování
pomocí impostorů, které má dvě hlavní části. První se skládá z pohledově závislé operace vykreslující do textury. Toto vykreslování je vlastní tvoření impostoru. V druhé části je vytvořená textura nanesena na sprite nebo billboard.
6
Sprity jsou plochy obdélníkového nebo čtvercového tvaru, které jsou vždy orientovány na pozorovatele (viz Obr. 7 vlevo). Algoritmus vytváří výsledný obraz koruny stromu z více než jednoho spritu. Kdyby však byly použity pouze sprity, vznikl by velmi nerealistický obraz. Algoritmus proto používá pohledově závislých impostorů, aby eliminoval tento problém. Hloubka je zavedena do procedury vykreslování do textury. Při vykreslování je informace o hloubce uložena v texturách s alpha kanálem. Výsledkem je poté 2,5D impostor.
Obr. 7: Sprite (vlevo) a rozmístění spritů ve stromu (vpravo) – převzato z [Szijártó03]
Impostory jsou tvořené texturami, do kterých jsou vykresleny libovolné skupiny náhodně uspořádaného listí. Tato textura je poté implementována na více spritů, aby se vytvořila požadovaná koruna stromu. Kvalita vytvořeného obrazu a pocit realismu se dramaticky zvyšuje, i když je stejný impostor použit pro celý strom.
Obr. 8: Množství listí vykreslovaných do textury – převzato z [Szijártó03]
Výsledek implementace byl testován na osobním počítači s procesorem Athlon o frekvenci 1,2 GHz a grafickou kartou GeForce4. Výsledky implementace jsou velice závislé na třech parametrech. První je množství vykreslovaných stromů, další je počet 7
spritů tvořících korunu stromu a poslední je množství listí vykreslovaných do textury (viz Obr. 8). Samotné výsledky představuje Tabulka 1. Výsledky implementace jsou ukázány na Obr. 9. počet stromů 1 128 spritů s 512 listy 210 64 spritů s 256 listy 214 32 spritů s 128 listy 215
2 198 207 209
4 170 189 199
8 128 158 179
16 83 116 145
32 46 72 103
64 25 42 65
128 13,1 23 38
256 6,7 13 22
Tabulka 1: Počet snímků za vteřinu – převzato z [Szijártó03 ]
Obr. 9: Koruna stromu (vlevo) a 200 stromů tvořících les (vpravo) – převzato z [Szijártó03 ]
2.4
Listové zjednodušování Přístup popsaný v [Inmacul02] spojuje dvě real-time metody vykreslování:
dynamické generování impostoru a multiresolution modelovací techniku. Multiresolution modelování se dělí do dvou skupin: diskrétní a spojité. Diskrétní modely mají konečné množství LOD a vlastní řídící mechanismus. Tyto modely mají řadu nevýhod. Mezi uchovávanými LOD nejsou žádné vztahy, tudíž rychle stoupá velikost těchto modelů při zařazení nové úrovně detailu. Na druhou stranu spojité modely obsahují veliké množství aproximací povrchu objektu. Modely tedy nabízejí adaptivní LOD v real-time, což zrychluje vizualizaci. V [Inmacul02] byl navržen speciální spojitý multiresolution model pro strom. Listy jsou vymodelovány jako množství nezávislých polygonů. Díky užití speciálního modelu pro stromy můžeme adaptovat různé množství polygonů v závislosti na důležitosti stromu ve scéně. Je-li pozorovatel tak blízko, že může vidět detaily objektu, bude impostor kombinovaný s geometrií. Zadní část stromu bude reprezentována s méně detaily a impostorem. Přední část stromu bude naopak vykreslena jen s vlastní geometrií. Stromy 8
tak vypadají opravdu 3D, což u klasických obrazově založených metod neexistuje. V tomto přístupu jsou stromy rozděleny do dvou hlavních částí: pevné části stromu (kmen stromu a větve) a na korunu stromu (listy a větévky). Pevné části stromu jsou tvořeny trojúhelníkovou sítí a koruna stromu je tvořena množstvím nezávislých polygonů. V modelu je pro korunu vytvořen zjednodušující algoritmus. Ten při přechodu z jedné úrovně detailu do další spojuje polygony nebo listy do jednoho polygonu. Zjednodušování stromu je vidět na Obr. 10.
Obr. 10: Zjednodušování stromu – převzato z [Inmacul02 ]
Při implementaci byly použity stromy, které byly vymodelovány pomocí komerční aplikace Xfrog. Stromy se skládaly z 4 791 listů tedy z 9 582 trojúhelníků. Počítač, na kterém byla implementace testována, obsahoval dva procesory Pentium III Xeon na 1.5GHz a grafickou kartu NVIDIA Quatro2 Pro s pamětí o velikosti 64MB. Při testu se pozorovatel ve scéně pohyboval a zároveň se v ní zvyšovalo množství stromů. Výsledky jsou vidět v Grafu 1.
9
Graf 1: Závislost frekvence vykreslování na počtu stromů – převzato z [Inmacul02 ]
Výsledky jsou vidět na Obr. 11.
Obr. 11: Výsledky použití listového zjednodušení - převzato z [Inmacul02 ]
2.5
Plátkování a prolínáním Přístup uvedený v [Jakulin2000] je založený na plátkování a prolínání. Přístup
vychází z obrazově založeného vykreslování, které se dále spojuje pouze s mícháním textur polygonů. Tento přístup rozděluje strom na dvě hlavní části: pevné a rozptýlené. Pevné části jsou tvořeny kmenem stromů a hlavními větvemi, druhou část stromu tvoří větvičky a listy. Rozptýlené části obsahují většinu geometrické složitosti modelu, a proto je tato část stromu zobrazována menším množstvím paralaxových vrstev, které poskytují plný vjem hloubky při pozorování stromu z přibližně stejného směru. Každá taková vrstva leží na pevném místě ve scéně. Všechny vrstvy jsou rovnoběžné a stejně vzdálené. Sada takových vrstev je v tomto přístupu nazývána slicing. 10
Slicing je zobrazován vykreslením všech vrstev, z nichž je složen. Orientace sady vrstev je stále stejná a nemění se vůči orientaci pozorovatele. Všechny vrstvy v sadě mají stejný normálový vektor a vzdálenost mezi vrstvami se rovná velikosti normálového vektoru. Slicing je obklopován slicing boxem (viz Obr. 12 vlevo) definovaným středem cs, výškou hs a šířkou ws. Každá vrstva v sadě je tvořena otexturovaným čtyřúhelníkem. Vrcholy vrstev leží na průsečících hran slicing boxu a jednotlivých ploch tvořících vrstvy. Množství vrstev tvořící slicing závisí na požadované kvalitě vykreslení, ale 3 až 7 vrstev je pro strom optimální. LOD jsou tvořeny používáním různého počtu vrstev ve slicing. Nejvíce vrstev je použito, je-li pozorovatel nejblíže stromu a při vzdálenosti, kdy není možné rozeznat paralaxu, je použita pouze jedna vrstva.
Obr. 12: Slicing box (vlevo) a primární a sekundární sada plátků (vpravo) – převzato z [Jakulin2000]
Jednotlivé sady plátků ale neobsahují dost informací pro pozorování stromu ze všech možných úhlů, proto musí být vypočítáno větší množství sad, jenž budou vytvořeny z různých úhlů, které jsou okolo modelu rovnoměrně rozloženy. Přepínání mezi jednotlivými sadami závisí na úhlu, který se vypočítává ze směrového vektoru sady a směrového vektoru ze středu sady k pozorovateli. To by vedlo k náhlým přepínáním mezi jednotlivými sadami, proto se zobrazují dvě sady stromu: první nejbližší, označována jako primární sada plátků, a druhá nejbližší, nazývaná sekundární sada plátků (viz Obr. 12 vpravo). Zároveň se rozlišuje jejich úroveň průhlednosti. Průhlednost sady je úměrná rozdílu úhlu mezi primární a sekundární sadou. Je-li úhel primární sady roven 0, pak je sekundární sada úplně průhledná. Jestliže jsou úhly primární a sekundární sady stejné, měly by být koeficienty neprůhlednosti obou sad
11
shodné. Koeficient neprůhlednosti primární sady, označován jako αp, se pohybuje mezi 1 a 0,5. U sekundární sady je koeficient označený αs a je roven 1- αp. Výše popsaná metoda byla implementována s využitím rozhraní OpenGL. Model stromu byl automaticky vygenerován a pak manuálně rozdělen na pevné a rozptýlené části. Trojúhelníková síť pevné části stromu byla manuálně zjednodušena, zatímco rozptýlené části stromu byly použity pro vytvoření textur. Jako software pro tvorbu textur byl využit nemodifikovaný POVRay ray tracing. Každá sada obsahovala 5 vrstev a pro jednotlivý strom bylo vytvořeno 6 sad po 60°. Koruna stromu byla tedy vykreslena ze 40 vrcholů, což znamená 10 trojúhelníků. Kmen a hlavní větve byly vykresleny přibližně z 200 trojúhelníků. Osobní počítač, na kterém byla tato metoda implementována, byl sestaven z procesoru Pentium II na 350 MHz a grafické karty NVIDIA GeForce256 DDR. Rozlišení aplikace bylo 640x480. Výsledky implementace jsou uvedeny v Tabulce 2. množství stromů
10
32
100
158
rychlost vykreslení [ms]
10
30
50
90
Tabulka 2: Výsledky v tabulce převzaty z [Jakulin2000 ]
12
2.6
Posouzení nalezených řešení Aby bylo možné posoudit nalezené přístupy, je nutné definovat pojem „vegetace na
rozsáhlém území“. Vzhledem k současným schopnostem hardwaru a požadavkům trojrozměrných GIS. Jako vhodný příklad pro další úvahy poslouží terén s rozlohou 50x50 km (2 500 km2). Hustota průměrného vzrostlého lesa mírného pásu je kolem 175 stromů na hektar1, tedy 17 500 stromů na 1 km2, což na uvažovaném terénu představuje pokrytí skládající se z 43 750 000 stromů. U algoritmů budeme sledovat počet trojúhelníků na jeden strom. Počet závisí na LOD každého přístupu a není možné ho zjistit bez implementace všech algoritmů, která však přesahuje rozsah této práce. Protože ve všech popsaných metodách jsou pro zobrazování předpokládány stromy různých úrovní detailu, postačuje pro posouzení použitelnosti metod pro vykreslování na rozsáhlém území odhad minimálního počtu trojúhelníků na jeden strom při nejnižší úrovni detailu všech stromů. Pro porovnání metod slouží Tabulka 3, která obsahuje pro každý přístup odhadované minimální množství trojúhelníků na jeden strom při nejnižší LOD a zároveň množství trojúhelníků potřebných na vykreslení dané vegetace při použití nejnižší LOD pro všechny stromy. Přístup
Billboardy
Objemové textury
Sprity a Listové impostory zjednodušení
Počet trojúhelníků na 2 0,25 2 jeden strom při nejnižší LOD Počet trojúhelníků 87 500 000 10 937 500 87 500 000 pro 43 750 000 stromů
2
54
87 500 000
2 362 500 000
Tabulka 3: Počty trojúhelníků
1
Dle údajů Správy Krkonošského národního parku
13
Plátkování a prolínání
Z Tabulky 3 vyplývá, že by každý přístup, až na Objemové textury, měl při nejnižší LOD nejméně dva trojúhelníky na jeden strom, protože by byl reprezentován např. pouze impostorem nebo billboardem. Objemové textury mají nižší množství trojúhelníků na jeden strom, bylo by je ale možné použít jen pro vegetaci, která by byla tvořena pouze poslední úrovní detailu tohoto přístupu. Kvalita takto vytvořené vegetace by byla nevyhovující a nepůsobila by realisticky. Běžně dostupné grafické akcelerátory střední třídy, jako jsou ATI Radeon 9800XT nebo nVidia GeForceFX 5950 Ultra, zobrazují teoretické maximum kolem 400 miliónů trojúhelníků za vteřinu. Pro udržení frekvence vykreslování alespoň 25 snímků za vteřinu by tedy složitost scény nesměla překročit 15 miliónů trojúhelníků. Z toho vyplývá, že žádný z nalezených přístupů není vhodný a je potřeba navrhnout nový. V následujících kapitolách bude popsáno autorem navržené a implementované řešení.
14
3
Navrhované řešení V předchozí kapitole bylo ukázáno, že pro zobrazení více jak jednoho miliónu
stromů vytvářejících vegetaci je potřeba zredukovat množství trojúhelníků tvořících strom ve scéně na méně než jeden trojúhelník. Toho lze dosáhnout použitím plátů. Plát je reprezentován čtyřmi koplanárními body ležící v rovině, která svírá pravý úhel s povrchem, na němž by měla být vegetace vykreslena. Z bodů se vytvoří dva trojúhelníky pomocí nichž je plát vykreslen (viz Obr. 13). Na tyto trojúhelníky je nakonec nanesena textura obsahující několik desítek až stovek stromů. Na tvorbu vegetace by bylo použito více plátů, které by byly rovnoběžné a uspořádané v řadě za sebou. To by ovšem bylo možné použít pouze tehdy, jestliže by se pozorovatel ve scéně nepohyboval a jeho směrový vektor pohledu by byl rovnoběžný s normálovým vektorem plátu. Jinak by při pohybu pozorovatele okolo stromů docházelo k jejich mizení (např. kdyby se úhel mezi směrovým vektorem pozorovatele a normálovým vektorem plátu pohyboval blízko pravému úhlu). Řešením tohoto problému je vytvořit stejné množství dalších plátů upevněných ve scéně tak, aby byly na předešlé pláty kolmé a navzájem se křížily v předem stanovených bodech. Tyto pláty budeme nazývat sekundární pláty a předešlé pláty primární. Počet primárních a sekundárních plátů je stejný a musí být zajištěno, aby se každý primární plát křížil se všemi sekundárními (viz Obr. 14).
vrcholy plátu
trojúhelníky
Obr. 13: Popis jednoho plátu buňky
Na jednu stranu ve vytvořené vegetaci zaniká problém s mizením stromu při pohybu pozorovatele okolo vegetace a množství trojúhelníků tvořící strom se pohybuje pod hranicí jednoho trojúhelníku (např. vegetace skládající se z jednoho miliónu stromů bude tvořena jedním tisícem primárních a stejným množstvím sekundárních plátů, na kterých bude textura obsahující tisíc stromů, a množství trojúhelníků na jeden stromu tedy
15
bude 0,004). Ale na druhou stranu je tu problém s povrchem, na němž se vegetace rozkládá. Tento povrch by musel být dokonale rovný, což v reálném světě neexistuje.
rohy buňky
sekundární pláty
střed buňky primární pláty Obr. 14: Popis půdorysu buňky
Kvůli tomuto problému byla vegetace rozdělena na jednotlivé buňky, které mají tvar čtverce. Buňky aproximují povrch, na němž se vegetace rozkládá. Každá buňka je charakterizována svým středem, výškou, šířkou, hloubkou, počtem plátů a čtyřmi vrcholy reprezentujícími rohy buňky. Výška buňky určuje výšku primárních a sekundárních plátů a zároveň velikost lesa v této buňce. Délka primárních plátů se rovná hodnotě šířky buňky a hloubka buňky udává délku sekundárních plátů. Další vlastností buňky je počet primárních respektive sekundárních plátů určující hustotu vegetace v dané buňce. Posledním parametrem jsou rohy buňky, ze kterých se vypočítávají vrcholy jednotlivých primárních a sekundárních plátů vytvářejících vegetaci v buňce. Při rozdělení vegetace na buňky se změní i počet trojúhelníků na jeden strom např. při zobrazení jednoho miliónu stromů by se vegetace rozdělila na 400 buněk a každá z nich by obsahovala 2 500 stromů, 50 primárních a 50 sekundárních plátů, poté by se počet trojúhelníků na jeden strom rovnal 0,08. Za předpokladu, že by všechny buňky měly shodné vlastnosti, by vytvořená vegetace nebyla dostatečně realistická, vypadala by příliš vyrovnaně. Pro vytvoření většího realistického vzhledu vegetace by bylo vhodné zavést variabilitu u vlastností výška buňky a počet primárních a sekundárních plátů. Tím bude dosaženo rozdílů ve
16
výšce a hustotě lesa mezi jednotlivými buňkami a vytvořená vegetace by již neměla tak nerealistický vzhled.
3.1
Tvorba vrcholů Vypočítávání vrcholů, ze kterých se vytvářejí pláty reprezentující vegetaci, je
jednou z nejdůležitějších částí algoritmu. Tvorba vrcholů je velice jednoduchá a používají se pro ní rohy buňky a lineární interpolace. Spodní vrcholy plátů leží na úsečce spojující každé dva sousední rohy buňky, takže pro výpočet jejich souřadnic bude použita lineární interpolace. Nejprve se spočítá vzdálenost mezi dvěma primárními nebo sekundárními pláty, kterou označíme jako d. Tato vzdálenost je mezi pláty všude stejná. Vypočteme ji jako poměr délky buňky a počtu jednoho druhu plátů (d = délka buňky/počet plátů). Pro další krok je důležité označit si rohy buňky. Spodnímu levému rohu přiřadíme číslovku jedna a následujícím rohům ve směru proti hodinovým ručičkám přiřazujeme číslovku o jednu vyšší (Obr. 15 – šedá šipka). Po označení rohů můžeme přejít k vytváření vrcholů. Vybereme si první dvojici rohů buňky (jedna a dva), poté mezi nimi vypočítáme, pomocí lineární interpolace, první bod, který by měl ležet v polovině vzdálenosti d od rohu buňky číslo jedna směrem k číslu dvě. Další bod bude ležet ve stejném směru, ale ve vzdálenosti, která je o d větší. Postup se opakuje pro ostatní body mezi vybranými rohy buňky. Vzdálenost d/2 pro výpočet prvního vrcholu mezi rohy buňky byla použita, aby nevznikaly pláty na hranách buňky. Takovéto pláty by se s pláty sousedních buněk, ležících na hraně, spojovaly a ve výsledku by vypadaly jako jeden plát. Použitím této vzdálenosti se splynutí plátů eliminuje a využijí se všechny pláty pro reprezentaci vegetace. Celý postup se zopakuje pro další hranu buňky, ale pro poslední dvě hrany buňky se obrátí pořadí rohů pro snadnější generování indexů. Oranžová šipka na Obr. 15 ukazuje směr vytváření vrcholů na jednotlivých hranách buňky. Takto by se vypočítaly pouze dolní vrcholy plátů. Horní vrcholy plátů vzniknou připočtením hodnoty výšky vegetace v dané buňce k jedné ze souřadnic vrcholu, která udává vertikální polohu bodu ve scéně.
17
4
3 d/2 d d d/2
1
2 Obr. 15: Tvorba vrcholů
Vypočtené vrcholy by se měly ukládat do jednoho vertex bufferu tak, aby za každým dolním vrcholem byl uložen vrchol ležící nad ním. Celý postup vytváření vrcholů je také ukázán v pseudo jazyku v následujícím odstavci. vzdálenost = 1 / pro i od 0 až do začátek h = 0; pro j od 0 začátek když
početplátů; 4 do početplátů
j = 0 pak h = h + (vzdálenost/2); jinak h = h + vzdálenost; konec když když i < 1 pak spodnívrchol=linInter(h,prvníroh,druhýroh); jinak spodnívrchol=linInter(h,druhýroh,prvníroh); konec když hornívrchol = spodnívrchol + výškavegetace; konec pro j konec pro i
Funkce linInter(h,prvníroh,druhýroh) představuje funkci lineární interpolace mezi rohy buňky a vrací vypočtený spodní vrchol. Parametr h udává vzdálenost v procentech od rohu buňky, který je na dané hraně buňky první v pořadí. Na postup vytváření vrcholů plátů těsně navazuje algoritmus pro vytváření indexů k jednotlivým vrcholům.
18
3.2
Tvorba indexů Další důležitou částí celého algoritmu je vytváření indexů k jednotlivým vrcholům
plátů. K vykreslování plátů v jedné buňce je použito dvou bufferů. Vertex buffer uchovává vrcholy všech plátů v buňce a index buffer uchovává indexy pro jednotlivé vrcholy. Indexy představují pozici vrcholu ve vertex bufferu. Aby bylo dosaženo maximálního využití grafického akcelerátoru, měly by být trojúhelníky vykresleny pomocí obou bufferů jedním voláním bez přerušení. Proto byla zvolena metoda jejich vykreslování nazvaná Triangle list, kde je každý trojúhelník tvořen třemi samostatnými body a do index bufferu se tedy zapisují tři indexy na každý trojúhelník (viz Obr. 16). Existují ještě další dvě metody Triangle strip a Triangle fan. Triangle strip je určen pro vykreslování pásů trojúhelníků, kdy je první trojúhelník pásu tvořen třemi vrcholy a další trojúhelníky se vytvoří pomocí jednoho nového bodu a dvou posledních bodů předchozího trojúhelníku (viz Obr. 16). Tato metoda není vhodná, protože by bylo nezbytné přerušit proces vykreslování po každém vykreslení dvou trojúhelníků tvořících jeden plát. Druhá nepoužitá metoda, Triangle fan, se používá pro popis vějíře složeného z trojúhelníků, kde je první trojúhelník vytvořen třemi body a další trojúhelníky jedním novým bodem, bodem ve středu vějíře a posledním bodem předchozího trojúhelníku (viz Obr. 16). Důvod nepoužití této metody pro vykreslování plátů je shodný jako u předchozí metody.
19
Triangle Strip 1
2
3
4
Index Buffer
5
1 6
7
8
9
6
2
7
3
8
3
4
6
7
3
4
5
6
4
9
5 10
7
8
9
10
Triangle Fan 3
2
Index Buffer
4 1
1
5 7
2
6
Triangle List 2
1
8
3
4
Index Buffer
5
6
1
7
2
9 Obr. 16: Typy vykreslování trojúhelníků
Pro každý plát je podle vybrané metody potřeba uložit do index bufferu šest indexů. Postup pro výběr indexů je svázán s algoritmem pro generování vrcholů. Do index bufferu se pro první trojúhelník libovolného plátu v buňce uloží pořadí spodních vrcholů ve vertex bufferu a přidá se index jednoho horního vrcholu. Pro druhý trojúhelník plátu se za uložené indexy prvního trojúhelníku umístí pořadí horních vrcholů a jako poslední index plátu se přidá pořadí vrcholu jehož horní vrchol netvoří první trojúhelník. Pomocí tohoto postupu naplníme celý index buffer všemi pláty buňky.
3.3
Textury Textura je popisem vlastností povrchu objektu a je důležitá pro vnímání jeho barvy
a struktury. Nanášení textury na objekt vede ke zvýšení jeho vizuální kvality a zároveň je to výpočetně nenáročný proces. Z tohoto důvodu je intenzivně používána zejména v časově náročných aplikacích. Důležitým krokem pro používání textur je jejich nanesení na objekt. Tento postup se nazývá mapování textury a je popsán například v [Žára2004]. O tento proces se v současné době starají grafické karty, kterým stačí pouze zadat požadovanou texturu
20
a body plochy, na níž má být textura nanesena. U bodů je navíc nutné určit jejich umístění v textuře. Toto umístění je v literatuře označováno jako u a v pro dvourozměrné a u,v a w pro trojrozměrné textury. Pro určení průhlednosti povrchu na otexturovaných objektech používáme alpha test. Test stanovuje část nebo části textury, které budou na základě hodnoty alpha průhledné. Alpha test je popsán v [DX9SDK]. Ve výsledku, při použití tohoto testu, jsou na obrazovce zobrazeny pouze stromy. Pro kvalitní vykreslení vegetace je potřeba vytvořit texturu, případně více textur, které nejvěrněji reprezentují vegetaci. Proto bylo vytvořeno a odzkoušeno několik druhů textur, které jsou popsány níže.
3.3.1 Textury jednotlivých stromů Grafické karty mají integrovanou funkci míchání textur. Tato funkce vytvoří z několika různých textur jednu výslednou texturu, která je použita pro zobrazení vegetace. Prvním krokem je vytvoření obrázků jednotlivých stromů, které jsou rozděleny na dvě poloviny, přičemž každá z nich je umístěna do jiné textury. Výchozí textury
Výsledné textury s neodfiltrovaným pozadím
Obr. 17: Textury jednotlivých stromů
Poté jsou pro každý plát náhodně vybrány dvě textury. První představuje levou a druhá pravou půlku stromu. Tyto textury jsou pak grafickou kartou smíchány a pomocí funkce kopírování textury, jež je také integrovaná v grafické kartě, nakopírovány do jedné výsledné textury vegetace pro daný plát. Při použití této textury a další, níže popsané, je
21
nutné, aby bylo zajištěno křížení primárních a sekundárních plátů ve středu každého stromu v textuře. Ukázky výchozích a výsledných textur pro jednotlivé pláty jsou na Obr. 17.
Obr. 18: Jedna buňka s texturou jednotlivých stromů
3.3.2 Dlouhá textura Pojem dlouhá textura představuje jednu texturu skládající se z mnoha různých stromů, které jsou symetrické. Stromy jsou v textuře rozmístěny, tak aby byly od sebe stejně vzdáleny. Abychom zajistili různorodost v otexturovaných plátech, musíme náhodně vygenerovat umístění textury na plátu tak, aby otexturovaný plát začínal a končil celým stromem. Ukázka textury je na Obr. 19. Na Obr. 20 je ukázka použití textury v buňce.
Obr. 19: Dlouhá textura
22
Obr. 20: Jedna buňka s dlouhou texturou
3.3.3 Neuspořádaná textura lesa Tento druh textury obsahuje veliké množství stromů umístěných neuspořádaně, které se dokonce mohou libovolně překrývat. Z toho vyplývá, že se nemusí zajišťovat křížení plátů ve středech stromů. Stejně jako v předchozí textuře i zde je nezbytné zabezpečit různorodost otexturovaných plátů pomocí náhodně vygenerovaného umístění textury na plátu. Na druhou stranu však není zapotřebí, aby otexturovaný plát začínal a končil celým stromem. Ukázka textury je na Obr. 21 a na Obr. 22 je opět ukázáno použití textury v buňce.
Obr. 21: Neuspořádaná textura lesa
23
Obr. 22: Jedna buňka s neuspořádanou texturou
Všechny výše popsané druhy textur byly implementovány. Na základě toho bylo zjištěno, že pro zobrazení vegetace pomocí našeho řešení je nejvhodnější použít poslední dva druhy textur. Při použití prvního druhu textury bylo docíleno variability v otexturovaných plátech, ale tato variabilita nebyla dostatečná. Proto je velice pravděpodobné, že by pozorovatel zanedlouho zaznamenal opakující se části textur. V otexturovaných plátech se totiž opakují vybrané půlky stromů, což vypadá velice nerealisticky. Používáním dalších druhů textur vzniká vysoká rozmanitost ve vytvořených stromech, která působí realisticky.
3.4
Úrovně detailu Zjednodušení scény je další nezbytnou součástí zobrazovacího procesu. Není totiž
nutné zobrazovat objekty situované ve velké vzdálenosti od pozorovatele s úplnými detaily, protože s rostoucí vzdáleností mezi pozorovatelem a objektem se pro daný objekt zmenšuje množství pixelů, které na obrazovce zabírá. Po zmenšení množství pixelů pak nelze rozeznat všechny detaily objektu. Navíc toto zjednodušení pomáhá urychlit proces vykreslování. 24
V našem řešení je zjednodušování scény prováděno pomocí diskrétních úrovní detailu, které jsou popsány v [Žára2004]. Nejvyšší úroveň vždy reprezentuje objekt s maximálními detaily a nejnižší představuje co nejvíce zjednodušenou reprezentaci objektu, která je ovšem akceptovatelná jako náhrada původního objektu. Pláty v buňce nelze víc zjednodušit, a proto se při různých úrovních detailu mění počet zobrazovaných primárních a sekundárních plátů. Kritéria, podle kterých stanovujeme úrovně detailu, jsou dvě: vzdálenost mezi pozorovatelem a buňkou a dále úhel mezi směrovým vektorem pozorovatele a normálovým vektorem plátů buňky. První kritérium se vypočítává jako vzdálenost mezi pozorovatelem a středem buňky. V závislosti na ní se mění počet primárních a sekundárních plátů, které mají být vykresleny. Druhé kritérium udává jaký druh plátů se má být zobrazen. Je totiž zbytečné zobrazovat oba druhy plátů u nižších stupňů detailu, protože jeden typ plátů při pohybu pozorovatele okolo buňky většinou mizí. Úhel pro přepínání mezi jednotlivými druhy plátů byl stanoven na 45 stupňů. Kdybychom ale toto přepínání použili, docházelo by k náhlému přepínání mezi jednotlivými druhy plátů, což by ve výsledku vypadalo velice nerealisticky. Proto je nutné zavést pro přepínání třetí stav, kdy se zobrazují oba druhy plátů. Pro tento stav je dobré stanovit rozmezí dvou úhlů ( např. 40 až 50 stupňů). Přidáním toho stavu se zamezí nerealistickému přepínání mezi jednotlivými druhy plátů. V našem řešení vytváříme n úrovní detailu. Při nejvyšším stupni detailu se vykreslují všechny pláty tvořící buňku. Při přechodu na nižší úroveň se ubírá 1/n celkového počtu jednoho druhu plátů z primárních a sekundárních plátů. Nejnižší úroveň je tedy tvořena 1/n množství obou druhů plátů.
3.5
Ořezávání Pro potřebu rychlého vykreslování scény s velikým množstvím objektů s ohledem
na viditelnost je potřeba stanovit, které objekty můžeme z dalšího zpracování v zobrazovacím řetězci vyloučit a které naopak podrobit důkladnému vyhodnocení viditelnosti. Dnes jsou již tyto postupy, jako např. odstranění odvrácených stěn a odstranění grafických primitiv pohledovým objemem (obě metody jsou vysvětleny v [Žára2004]), implementovány v grafickém procesoru, ale ten jejich vyhodnocení provádí poměrně pozdě v zobrazovacím řetězci. Většina moderních zobrazovacích systémů proto provádí odstranění grafických primitiv pohledovým objemem ještě před jejich posíláním do grafického procesoru. 25
Pro vyhodnocování viditelnosti jednotlivých buněk ve scéně byl nasazen pomocný pohledový objem. Jeho použití je velice jednoduché a výpočetně nenáročné. Nejprve se musí buňky umístit do obálky, která má tvar kulové plochy. Vytvoření obálky má v našem řešení dvě části: výpočet středu buňky a stanovení poloměru kulové obálky. Střed buňky je vypočítáván jako aritmetický průměr rohů buňky a poloměr kulové obálky je nejdelší vzdálenost od středu buňky k jejím rohům. Takto by ale vznikla kulová obálka pro každou buňku a pomocný pohledový objem by poté musel být vypočítáván a použit pro každou buňku. Proto jsme se rozhodli vybrat největší kulovou obálku a přiřadit její poloměr všem buňkám. Toto ovšem přináší jednu nevýhodu. Grafickému procesoru se posílají polygony buněk, které uživatel nemusí ve scéně vidět. Tyto polygony grafický procesor zbytečně zatěžují, ale není jich tolik, aby výrazně zpomalily vykreslování celé vegetace. Dalším důležitým krokem je sestavení pomocného pohledového objemu v závislosti na promítání. Pro středové promítání jej získáme posunutím pozice pozorovatele v pohledovém objemu středového promítání scény ve směru opačném k vektoru pohledu pozorovatele a posunutím bližší a vzdálenější ořezávací roviny. Velikost posunutí je závislá na kulové obálce buněk ve scéně a úhlu pohledu pozorovatele, označovaném jako
α. Velikost posunutí, označovanou c, vypočteme pomocí vzorce uvedeného níže.
r
α/2
c
c=
r
obálka buňky
α/2
r
sin (α /2)
střed buňky buňka
α
bližší ořezávací rovina
r
pohledový objem
c α
pomocný pohledový objem
Obr. 23: Pomocný ořezávací objem
Takto získáme pomocný pohledový objem, v němž by se měly nacházet všechny středy buněk, které jsou pro pozorovatele viditelné.
26
4
Implementace
4.1
Použité technologie Pro implementaci je v první řadě nutné vybrat vhodný programovací prostředek,
tedy vybrat programovací jazyk a vývojový nástroj. Zvolil jsem programovací jazyk C++, neboť se v současné době volí mezi objektovými programovacími jazyky. Tento jazyk má vytvořenou normu, což znamená, že lze zdrojový kód z velké části snadno přenést mezi vývojovými nástroji. Jako vývojový nástroj jsem zvolil Microsoft Visual Studio .NET 2003, protože je dostupný na UHK. V aplikaci je kladen důraz na interaktivitu s uživatelem, tedy na vykreslování vegetace s vysokou obnovovací frekvencí scény, pomocí které může aplikace okamžitě reagovat na pokyny uživatele a zároveň je uživatel schopen vnímat změny ve scéně. Z tohoto důvodu bylo zvoleno využití současných grafických akcelerátorů, neboť téměř všechny obsahují programovatelné procesory. Operace prováděné na vrcholech a pixelech nejsou vybírány z těch, které jsou pevně definovány v procesoru, ale jsou tvořeny jednoduchým programem kompilovaným za běhu aplikace. Programovatelné procesory tedy nabízí mnohem více možností a aplikaci lze jednoduše přizpůsobit pro potřeby uživatele. Aplikace vyžaduje grafický akcelerátor podporující vertexové a pixelové programy verze 2.0 a vyšší. Jestliže takovýto hardware daný osobní počítač neobsahuje, potom aplikace nic nevykreslí. V současné době existují pouze dvě rozhraní OpenGL a Direct3D, která poskytují přístup ke grafickému akcelerátoru. Otevřené rozhraní OpenGL dovoluje výrobcům grafických karet rozšiřovat standard o schopnosti akcelerátoru. Pokud se ale výrobci grafických karet nedohodnou na označení totožných funkcí, vede to k nepřehlednosti mezi rozšířeními jednotlivých verzí, k čemuž již došlo při značení vertexových a pixelových programů. Navíc toto rozhraní není objektově navrženo narozdíl od rozhraní Direct3D. Rozhraní Direct3D je částí multimediálního rozhraní DirectX společnosti Microsoft. Vždy je pevně definováno již při svém vzniku a obsahuje do jisté míry zpětnou kompatibilitu, ale pro využití jeho nových funkcí, které přicházejí vždy s novou verzí, je nutné přepsat některé části zdrojového kódu.
27
Rozhodl jsem tedy se použít rozhraní Direct3D 9.0, kvůli jednotnosti přístupu k funkcím grafického akcelerátoru a jeho objektové struktuře. Pokud není na osobním počítači nainstalován DirectX verze 9.0 nebo vyšší, aplikaci nebude možné spustit.
28
5
Výsledky Navržený algoritmus byl implementován do aplikace, která byla testována na dvou
osobních počítačích. První sestava obsahovala procesor Intel Pentium 4 na 2,8GHz, operační paměť o velikosti 1,5GB a grafickou kartu ATI Radeon 9800 Pro s velikostí paměti 256MB. Druhá počítačová sestava obsahovala procesor Intel Pentium 4 na 3,2GHz, operační paměť o velikosti 2GB a grafickou kartu nVidia GeForce 6800 Ultra s velikostí paměti 256MB. Pro testy byla vytvořena vegetace skládající se z 15 876 buněk (126x126 buněk), navíc měla vegetace stanovenou konstantní hustotu na 15 600 stromů na 1 km2. Testována byla dvě nastavení aplikace. V prvním nastavení byla délka buňky ve vegetaci stanovena na 400 m a v druhém na 800m. Tomuto nastavení odpovídalo i množství stromů na jeden plát. V prvním nastavení byla na plát nanesena textura skládající se z 50 stromů a ve druhém byla nanesena textura obsahující 100 stromů. V obou případech byla upravena výška stromů tak, aby odpovídala realitě. Při použití prvního nastavení aplikace byl rozsah vegetace 2 540 km2 (50,4x50,4 km) a celková vegetace byla tvořena 39,624 milióny stromů. V druhém nastavení aplikace se vegetace rozkládala na území o rozloze 10 160 km2 (100,8x100,8 km) a vegetaci tvořilo 158,5 miliónů stromů. Výsledky popisovaných nastavení aplikace jsou ukázány na Obr. 24 a 25. Při testování byla měřena obnovovací frekvence zobrazované scény a to ve dvou fázích: v klidu a při pohybu nad vegetací. Výsledky měření jsou uvedeny v Tabulce 4. Systém 1 při pohybu v klidu 1. Nastavení 29 27 2. Nastavení 38 37
Systém 2 při pohybu v klidu 48 60 68 73
Tabulka 4: Výsledky měření – obrázky za sekundu
Z naměřených hodnot v Tabulce 4 vyplývá, že navrhovaný přístup je schopný zobrazovat vegetaci na rozloze tisíců a desetitisíců km2 s obnovovací frekvencí větší než 25 snímků za vteřinu. Zobrazovaná vegetace působí realisticky a je vykreslována s dostatečnými detaily(viz Obr. 24 a 25).
29
Obr. 24: Vegetace s prvním nastavením
Obr. 25: Vegetace s druhým nastavením
30
6
Závěr Stanoveným cílem práce bylo najít nebo navrhnout vhodný algoritmus pro
zobrazování rozsáhlé vegetace, ve které není kladen důraz na detailní vykreslení jednotlivých stromů, ale na vykreslení vegetace jako celku. Nalezený nebo navržený přístup byl implementován do prototypu aplikace, ve které probíhalo vykreslování vegetace v reálném čase, aby mohl uživatel interaktivně komunikovat s aplikací. Žádný z nalezených existujících algoritmů nebyl pro vykreslování vegetace vhodným řešením, proto bylo navrženo nové. Toto řešení rozděluje vegetaci na jednotlivé buňky, které jsou odvozeny z povrchu, na němž se vegetace rozkládá. V buňkách je vegetace vykreslována pomocí určitého množství plátů, jež se navzájem kříží v předem stanovených bodech a na které je nanesena textura vegetace. Pomocí tohoto přístupu se podařilo snížit množství trojúhelníků potřebných na vykreslení jednoho stromu ve scéně hluboko pod hranici jednoho trojúhelníku na jeden strom. Díky takové redukci trojúhelníků je přístup schopen vykreslovat rozsáhlou vegetaci v reálném čase a s dostatečnými detaily. Pro další urychlení vykreslování vegetace ve scéně bylo zvoleno a v aplikaci implementováno
ořezávání
pomocným
pohledovým
objemem.
Toto
ořezávání
představuje velice jednoduchou a snadno implementovatelnou metodu, která ochrání grafickou kartu od zpracovávání informací o buňkách, jež uživatel ve svém pohledu nemůže vidět. Aby docházelo k rychlejší interakci mezi vytvořenou aplikací a uživatelem, byla v implementaci
použita
technologie
programovatelných
procesorů
grafických
akcelerátorů urychlujících vykreslování trojrozměrné scény. Vytvořený software byl testován na dvou osobních počítačích s grafickými čipy různých výrobců a na dvou vegetacích s odlišnou velikostí. Na testovaných vegetacích bylo pro oba počítačové systémy docíleno dostatečné obnovovací frekvence scény pro rychlou interakci mezi uživatelem a aplikací. V další práci by bylo vhodné zaměřit se na zlepšení aproximace povrchu vegetací. Nejvhodnější by bylo rozdělit vegetaci v buňce do dvou částí, které by měly půdorys ve tvaru trojúhelníku, neboť právě toto rozdělení bude nejlépe aproximovat povrch, na němž se vegetace rozkládá.
31
7
Odkazy
[Ati]
ATI Technologies Inc. [online]. Dostupný z WWW: < http://www.ati.com/Products/ >
[Decaudin04]
DECAUDIN, P., NEYRET, F. Rendering Forest Scene in RealTime [online]. In Rendering Techniques’ 04, Eurographics Symphosium on Rendering, page 93-102, květen, 2004 [citace říjen, 20. 2004]. Dostupný z WWW: < http://www-evasion.imag.fr/Publications/2004/DN04/>
[DX9SDK]
DirectX Documentation in C++. DirectX 9 Software Development Kit [online]. Microsoft, 2, 2005 [citace březen, 7., 2004]. Dostupný z WWW: < http://msdn.microsoft.com/downloads/>
[Inmacul02]
INMACULADA, R., CHOVER, M., BELMONTE, Ó., RIBELLES, REBOLLO, C. Real Time Tree Rendering [online]. Technical Report DLSI 01/03/2002, Departamento de Lenguajes y Sistemas Informaticos, Universitat Jaume I, Castellón, Spain, březen, 2002 [citace listopad, 20., 2004]. Dostupný z WWW:
[Jakulin2000]
JAKULIN, A. Interactive Vegetation Rendering with Slicing and Blending [online]. Eurographics Conference short paper, 2000 [citace listopad, 15., 2004 ]. Dostupný z WWW: < http://zeus.fri.uni-lj.si/aleks/slicing-and-blending/>
[nVidia]
NVIDIA Home [online]. Dostupný z WWW: < http://www.nvidia.com/Page/desktop.htm>
[Szijártó03]
SZIJÁRTÓ, G., KOLOSZÁR, J. Hardware Accelerated Rendering of Foliage for Real-Time Application [databáze online]. In International Conference on Computer Graphics and Interactive Techniques, Session: Rendering, page 141-148, Budmerice, Slovenia, 2003, [citace listopad, 13., 2004]. ISBN:1-58113-861-X. Dostupný z WWW: < htttp://portal.acm.org>
[Žára2004]
ŽARA, J., BENEŠ, B., FELKEL, P., SOCHOR, J. Moderní počítačová grafika. Computer Press, 2004. ISBN: 80-251-0454-0.
32
