VYSOKÉ U ENÍ TECHNICKÉ V BRN FAKULTA INFORMA NÍCH TECHNOLOGIÍ
Zobrazování terénu Bakalá ská práce
2005
Roman Schulz
str. 1
Zobrazování terénu © Roman Schulz, 2006. Tato práce vznikla jako školní dílo na Vysokém u ení technickém v Brn , Fakult informa ních technologií. Práce je chrán na autorským zákonem a její užití bez ud lení oprávn ní autorem je nezákonné, s výjimkou zákonem definovaných p ípad .
Prohlášení Prohlašuji, že jsem tuto bakalá skou práci vypracoval samostatn pod vedením pana Ing. Jaroslava Kadlece a uvedl v ní veškerou literaturu a zdroje, ze kterých jsem erpal.
V Letovicích, dne 20. 4. 2006 …………………………………..
str. 2
Abstrakt Cílem této práce je navrhnout a implementovat systém pro zobrazení krajiny na po íta i ve 3D prostoru s použitím rozhraní OpenGL. Systém by m l umož ovat zobrazení terénu, vegetace a dalších objet , jako jsou ásticové systémy, budovy, vozidla atd. Uživatel by m l mít možnost terén editovat a po spušt ní programu se v n m libovoln pohybovat. Dále je pot eba mít možnost pro demonstraci zobrazit drát ný model terénu a objekt . tená by m l být schopen porozum t princip m zobrazení reáln vypadajícího terénu a m l by se seznámit s algoritmy pro zobrazení 3D scény a povrchu z výškových map.
Klí ová slova Po íta ová grafika, terén, generování terénu, ROAM, binární strom, zobrazení terénu, zobrazení objekt , výšková mapa, textury, detailní textury, GIS, OpenGL, šumová funkce, interpolace.
Pod kování Cht l bych tímto pod kovat svému vedoucímu bakalá ské práce Ing. Jaroslavu Kadlecovi, za jeho rady a p ipomínky k bakalá ské práci.
str. 3
Abstract The purpose of this work is to design and implement system for display of landscape on personal computer in 3D space using OpenGL interface. This system should allow to display terrain, vegetation and other objects, like particle systems, buildings, cars etc. and have option to show wire model of terrain and objects for demonstration purpose. User should have option to edit terrain and while running of the program, support free movement. Reader should be able to understand principles of display realistic landscape and should learn algorithms for display of 3D scene and surface from height maps.
Keywords Computer graphics, terrain, terrain generating, ROAM, binary tree, display of terrain, display of models, height map, textures, detail textures, GIS, OpenGL, noise function, interpolation.
str. 4
Obsah 1. Úvod...........................................................................................................................................6 1.1. Rozhraní pro zobrazení 3D scény.....................................................................................7 1.2. Reprezentace terénu jako výškové mapy .........................................................................7 2. Algoritmy pro zobrazení terénu .................................................................................................8 2.1. Algoritmus ROAM...........................................................................................................8 2.1.1. P íprava binárního stromu .............................................................................................8 2.1.2. Rozložení na optimální trojúhelníkovou sí ................................................................11 2.1.3. Úprava hrani ní hodnoty .............................................................................................12 2.1.4. Zamezení vzniku chyb.................................................................................................12 2.1.5. Vykreslení optimální sí ............................................................................................13 2.2. Generování výškové mapy .............................................................................................13 2.2.1. Popis algoritmu Perlin noise........................................................................................13 3. Dosažení reálnosti zobrazení ...................................................................................................14 3.1. Textura terénu.................................................................................................................14 3.2. Textura okolí ..................................................................................................................15 3.3. Stromy ............................................................................................................................16 3.4. Další objekty...................................................................................................................17 3.5. Vodní hladina .................................................................................................................17 3.5. ásticové systémy ..........................................................................................................18 4. Implementace...........................................................................................................................20 4.1. Zobrazení terénu.............................................................................................................20 4.2. Editor terénu...................................................................................................................22 5. Záv r ........................................................................................................................................25 5.1. Možné využití aplikace a další vývoj projektu...............................................................25 6. Literatutra.................................................................................................................................27 7. P íloha 1 - Editor terénu...........................................................................................................28
str. 5
1. Úvod Po íta ová grafika je obor informatiky, který využívá po íta ovou techniku na vytvá ení um lých snímk (tzv. renderování). Tento obor je možné d lit na n kolik oblastí: 3D rendering v reálném ase ( asto využívaný v po íta ových hrách), po íta ová animace, video, st ih speciálních efekt ( asto využívané ve filmu a televizi), oditování obrázk a modelování. V grafických aplikacích, jako jsou nap íklad letecké simulátory nebo po íta ové hry, je asto pot eba zobrazit terén. Ten m že být vytvo en z dat o skute né krajin nebo m že být kompletn celý vygenerován na po íta i. P i zobrazení rozsáhlého terénu se d íve i pozd ji narazí na problém spo ívající v tom, že terén obsahuje obrovské množství dat a jejich zobrazení v reálném ase (p i vysokém po tu zobrazených snímk za jednu sekundu) je v sou asných podmínkách tém nemožné. Proto bylo vyvinuto n kolik algoritm , které tento problém eší tím, že r zné ásti terénu zobrazí v r zném stupni detailu. Hlavním cílem této bakalá ské práce je vytvo it aplikaci která umožní v rohodné zobrazení terénu. S tímto souvisí jednak implementace algoritmu pro vykreslení terénu, tak i zobrazení dalších objekt , které podpo í reálný vzhled, jako jsou nap . budovy, vozidla, vegetace atd. Vstupní data bude možno zadávat v editoru, který bude sou ástí odevzdaného projektu. Dalším cílem je zpracování teoretické ásti, která by m la poskytnout tená i ucelený p ehled o možnostech zobrazení realistického terénu ve 3D grafice a popis principu nej ast ji používaných algoritm . Naopak si tato bakalá ská práce neklade za cíl shromáždit vy erpávající teoretickou studii, která by se zabývala podrobným popisem všech algoritm a jejich variantami, deformacemi terénu v reálném ase atd. Samoz ejmostí je popis d ležitých ástí zdrojového kódu, použitých t íd, metod, funkcí a struktur. V první kapitole se tená seznámí s reprezentací terénu v po íta ové grafice. Ve druhé kapitole jsou popsány nejpoužívan jší algoritmy používané p i zobrazení terénu a jeho generování. Ve t etí kapitole je seznámen s možnostmi vylepšení vzhledu terénu po vizuální stránce. Ve tvrté kapitole je podrobn ji rozepsána implementace a struktura programu. Následuje záv r, vyhodnocení výsledk a popis možného využití aplikace. Za t mito kapitolami následuje seznam použité literatury a p íloha.
str. 6
1.1. Rozhraní pro zobrazení 3D scény Zobrazení objekt ve 3D je výpo etn velmi náro né, proto je vhodné využít n které již existující rozhraní. Rozší ená jsou v dnešní dob rozhraní DirectX a OpenGL. Ob dv jsou ve v tšin dnešních po íta ích hardwarov akcelerovaná a tudíž velmi rychlá. Já jsem se pro zobrazení scény použil rozhraní OpenGL. Hlavním d vodem k tomuto výb ru bylo to, že jej dob e znám a díky tomu jej mohu pln využít, narozdíl od konkuren ního DirectX. Program byl vytvo en pro opera ní systém MS Windows, ale není problém jej upravit tak aby fungoval i v dalších opera ních systémech, protože implementace OpenGL existují pro prakticky všechny platformy.
1.2. Reprezentace terénu jako výškové mapy Nej ast ji se v po íta ové grafice na terén pohlíží jako na dvojrozm rné pole hodnot, které udávají výšku terénu v bod daném dv ma sou ednicemi. Tomuto poli se íká výšková mapa a jedná se vlastn o pravidelnou matici hodnot. Výhodou je možnost velmi rychle zjistit výšku terénu ve kterémkoliv bod . Výšková mapa slouží jako vstupní data pro naprostou v tšinu algoritm ur ených pro zobrazení terénu. Její hodnoty je možné pro lepší názornost také považovat za barvy šedi od erné až po bílou, kde erná barva jsou nejnižší místa terénu a bílá barva jsou nejvyšší místa terénu. Jedná se tedy vlastn o bitmapu a pro její editaci je možné využít libovolný dostupný grafický editor. Z výškové mapy lze snadno vytvo it trojúhelníkovou sí a zobrazit ve 3D.
Obrázek 1. Výšková mapa jako bitmapa
str. 7
2. Algoritmy pro zobrazení terénu Algoritm pro zobrazení terénu existuje celá ada, velice se ale liší efektivitou, množstvím zabrané pam ti, škálovatelností atd. Algoritmus hrubé síly ne eší v bec nic a vykreslí všechny trojúhelníky, ze kterých se terén skládá. Jméno tohoto algoritmu p esn vystihuje jeho nevýhodu. V p ípad rozsáhlého terénu je tento p ístup velice nevhodný, protože je ve skute nosti vid t jen malá ást toho, co algoritmus vykresloval. Proto je vhodný jen pro testovací ú ely a nebude zde dále popisován.
2.1. Algoritmus ROAM Algoritmus ROAM (Real-time Optimally Adapting Meshes) byl vyvinut v roce 1997 pro zobrazení terénu v leteckých simulátorech. Je použit v simulátoru T3SIM p i simulaci vzdušných souboj stíhacího letadla JAS 39 Gripen. Hlavní výhodou tohoto algoritmu je možnost p izp sobení lenitosti terénu na základ výkonu PC. Algoritmus je založen na struktu e binárního stromu.
2.1.1. P íprava binárního stromu Tento strom se vyzna uje tím, že každý uzel má práv dva potomky. Každý uzel tohoto stromu musí obsahovat ukazatel na dva jeho potomky, jednoho p edka a t i jeho sousedy (viz. obrázek 6, který je p evzat z literatury [4]). Strom je vytvo en tak, že se z celé výškové mapy vytvo í dva základní pravoúhlé trojúhelníky. Tyto trojúhelníky jsou rekurzivn p leny do té doby, než se p i p lení dostane na nejmenší možný trojúhelník. Pr b h vytvá ení binárního trojúhelníkové stromu je znázorn n na obrázku 6 (p evzato z literatury [10])
str. 8
Obrázek 6. Struktura uzlu binárního stromu(vlevo) a p lení trojúhelník (vpravo).
Obrázek 7. Kroky p i tvorb binární trojhelníkové sít
Po vytvo ení binárního trojúhelníkového stromu je pot eba tento strom celý projít metodou post-order a n jakou funkcí ohodnotit d ležitost každého trojúhelníku. Pro výpo et je vytvo ena funkce, která spo ítá odchylku ve st edu p epony každého trojúhelníku mezi p ípadem, že je trojúhelník rozp lený a nerozp leným trojúhelníkem. Každý rodi obsahuje sou et hodnot obou jeho potomk . Tuto hodnotu je vhodné v každém snímku doladit podle vzdálenosti daného trojúhelníku od pozorovatele.
2.1.2. Rozložení na optimální trojúhelníkovou sí
Rozložením terénu na optimální trojúhelníkovou sí se získá jen tolik trojúhelník , kolik je t eba, p i emž se vyberou jen ty které jsou nejd ležit jší z daného pohledu na terén. S tím vzniká problém, že se musí v každém snímku optimální rozložení p epo ítat. D vod je ten, že se pozorovatel po terénu pohybuje, rozhlíží atd a tím se m ní d ležitost jednotlivých trojúhelník . Pro rozložení terénu je t eba zvolit hrani ní hodnotu, která ur uje, kdy se má trojúhelník dále rozp lit nebo naopak z stat nerozp lený. Postupuje se od hlavního nejv tšího trojúhelníku, a pokud je jeho d ležitost tohoto trojúhelníku nižší než zvolená hodnota, trojúhelník již dále není p len. Jinak dojde k rozp lení a rekurzivn se otestují oba dva jeho potomci. Tímto vznikne optimáln vytvo ená trojúhelníková sí .
str. 9
2.1.3. Úprava hrani ní hodnoty Hrani ní hodnotu, která udává v jakém p ípad se má trojúhelník dále rozd lovat, lze m nit pro každý snímek a udržovat tím plynulý po et snímk za jednu sekundu i p i velmi odlišných scénách. To znamená že když je vykreslení scény pomalé a je zobrazeno p íliš mnoho trojúhelník , je možné snížit hrani ní hodnotu a v p íštím snímku tak vykreslit mén trojúhelník . Nebo naopak, pokud je vykreslení rychlé, je možné zobrazit více trojúhelník . Proto m že být ze za átku hodnota zvolena zcela libovoln , po n kolika zobrazených snímcích se ustálí na optimální hodnot (požadovaný po et snímk za sekundu nebo požadovaný po et vykreslených trojúhelník ) a p i pohybu pozorovatele se automaticky p izp sobí. V tom je obrovská výhoda tohoto algoritmu oproti ostatním. Tento algoritmus m že být dále optimalizován tak, aby se p i pohybu nebo rozhlížení pozorovatele v terénu p epo ítala jen zm n ná data.
2.1.4. Zamezení vzniku chyb S rekurzivním d lením binární trojúhelníkové sí na optimáln rozloženou sí souvisí problém s nuceným p lením trojúhelník . Vždy, když je trojúhelník p len, musí být p len i jeho soused se kterým sdílí p eponu. Pokud by se tak nestalo, v terénu by byly vid t trojúhelníky, které na sebe nenavazují. D vodem je to, že se st ed p epony trojúhelníku nevyskytuje p esn v p vodním bod (m že být umíst n výš nebo níž než p vodní bod). Na obrázku 8 je znázorn n p íklad nuceného rozp lení n kolika trojúhelník tak, aby nedocházelo k výskytu chyb. Obrázek je p evzat z literatury [4].
Obrázek 8. Zamezení vzniku chyb p i p lení trojúhelník
str. 10
2.1.5. Vykreslení optimální sí
Nyní jsou p ipravena veškerá data pro zobrazení terénu. Jsou známy všechny trojúhelníky ze kterých se terén složí a nic nebrání jej p edat rozhraní OpenGL, které je zobrazí. Na obrázku 9 jsou zvýrazn ny trojúhelníky, které byly použity p i vykreslení terénu v r zném stupni detailu.
Obrázek 9. Stejný terén v r zném stupni detailu
2.2. Generování výškové mapy Vytvo it výškovou mapu je možné v libovolném grafickém editoru, jak bylo napsáno v úvodní kapitole. Mnohem lepší možností ale je nechat si výškovou mapu vygenerovat n kterým algoritmem pro generování šumu a výsledek jenom lehce upravit v grafickém editoru. K dispozici jich je velké množství, jedním z nejpoužívan jších je algoritmus Perlin Noise, který podává pom rn kvalitní výsledky generování. Další asto používané algoritmy pro generování výškové mapy jsou Rided Perlin, Multi Perlin, Fractal Generation, Midpoint Displacement, Fault Formation, Spectral Synthesis Noise atd.
2.2.1. Popis algoritmu Perlin noise Na tomto míst je popsáno z d vodu lepší srozumitelnosti pouze vytvo ení jednorozm rného šumu. Pro víc rozm r je princip úpln stejný, jen je pot eba 1 rozm r p idat do všech následujících funkcí. K vytvo ení generátoru Perlin Noise šumu je pot eba v podstat jen funkce diskrétního šumu a interpola ní funkce. Funkce diskrétního šumu je v podstat generátor náhodných ísel, který má jediný parametr, a vrací náhodné íslo v rozsahu 0-1, které závisí na parametru. Funkce musí vrátit stejné hodnoty v p ípad , že se zavolá dvakrát se
str. 11
stejným parametrem. Interpola ní funkce je kompromisem mezi rychlostí a kvalitou výstupu. Vygenerovaná šumová funkce je znázorn na na obrázku 2 (obrázky 2, 3, 4, 5 jsou p evzaty z literatury [9]). Je možné sice použít lineární interpolaci, ale mnohem lepší výsledky lze dosáhnout použitím bilineární nebo kosinové interpolace. Dále je možné použít nap íklad kubickou nebo kvadratickou interpolaci.
Obrázek 2. Generátor náhodných ísel a interpolovaná funkce Zde se jedná o základní frekvenci. Frekvence této interpolované funkce se dá zm nit velice jednoduše násobením požadovaného bodu na vodorovné ose (osa x). V p ípad že je pot eba 2 krát vyšší frekvence, sta í pouze najít bod s 2krát vyšší x-ovou sou adnicí. Šum s r znými frekvencemi je znázorn n na obrázku:
Obrázek 3. Šum se základní, dvou a ty -násobnou frekvencí
str. 12
Obrázek 4. Šum s osmi, 16-ti a 32-ti násobnou frekvencí Každá následující frekvence se nazývá oktáva. Nyní je možné vypo ítat hodnotu Perlin Noise šumu. Samotná funkce pro výpo et Perlin Noise šumu má 2 parametry, po et oktáv a po áte ní frekvenci. Výpo et je velice jednoduchý, k šumu s po áte ní frekvencí se p i te 1/2 hodnoty šumu s dvojnásobnou frekvencí. K výsledku se p i te 1/4 hodnoty šumu se ty násobnou frekvencí a celý cyklus se opakuje pro každou další oktávu. Podrobn jší informace viz reference [9]. Všechny metody pro generování tohoto šumu jsou umíst ny v souborech CNoiseGenerator.cpp a CNoiseGenerator.h.
Obrázek 5. Perlin noise pro 6 oktáv a frekvenci 1.0
str. 13
3. Dosažení reálnosti zobrazení Jelikož se samotná trojúhelníková sí moc nepodobá skute nému terénu a pozorovatel si st ží dokáže p edstavit terén, je nutné zobrazit n kolik dalších detail . Každá mapa, která se na terén nanese mu mnohonásobn p idá na detailu. Nanesená m že být nap íklad textura, bump mapa, detailní mapa atd.
3.1. Textura terénu Ve v tšin grafických rozhraních m že být povrch trojúhelníku popsán nejen barvou, ale také rastrovým obrazem. Takový obrázek se nazývá textura a udává, jak budou trojúhelníky nakonec vypadat. V tšina dnešních grafických karet má omezenou maximální velikost textury, proto je nutné zobrazit bu menší ásti terénu s r znými texturami, nebo zobrazit jednu hrubou texturu, a k ní p i íst detailní mapu. Z d vodu nižší pam ové náro nosti byl zvolen druhý zp sob. Navíc je detailní mapa na terén aplikována tak, že není roztáhnuta po celém terénu jako hlavní textura, ale pravideln se opakuje. Výhodou tohoto ešení jsou malé rozm ry detailní textura.
Obrázek 10. Terén bez textury (vlevo) a s texturou (vpravo) Na obrázku 10. vlevo je zobrazen terén bez textury jen se stínováním a v pravo je zobrazena ta samá ást terénu s nanesenou texturou. Rozdíl je patrný hned na první pohled a výhoda je v možnosti barevného rozlišení jednotlivých ástí terénu (hory, pole, lesy atd.). Na obrázku 11 je k textu e p idána detailní mapa, která op t terénu p idala na reálném vzhledu.
str. 14
Obrázek 11. Terén s detailní texturou
3.2. Textura okolí Dalším prvkem, kterým lze zlepšit vizuální dojem, je zobrazit texturu okolí. Jiste si každý dokáže p edstavit jak by vapadal terén, kdyby na pozadí nebyla obloha, ale jen erná barva? Vše spo ívá v tom, že se vytvo í krychle, na jejíž strany se zobrazí textura. Tato textura zpravidla obsahuje bu oblohu, nebo oblohu a vzdálenou ást krajiny. P íklad textur, které se zobrazí na krychli je na obrázku 12. St ed této krychle se umístí do pozice o sou adnicích kamery.
Obrázek 12. Textury okolí
str. 15
Výhoda tohoto ešení je ve velmi snadné zm n textury okolí v závislosti na denní dob a po así. Nap íklad za svítání je vhodné zobrazit texturu s vycházejícím sluncem, naopak v noci je možné zobrazit hv zdy a m síc.
3.3. Stromy Zobrazení strom je nedílnou sou ástí zobrazení terénu. Proto byl navržen systém, kde každý strom m že být reprezenovaný n kolika objekty v r zném stupni detailu. Pokud je tento strom zobrazen v dálce, je vykreslen jako 2 obdelníky pokryté texturou. Naopak pokud je zobrazen t stn p ed pozorovatelem (kamerou), m že být zobrazen jako objekt složený z n kolika tisíc trojúhelník (tím pádem má mnohem vyšší detail). P epínání stupn detailu závisí na d ležitosti stromu (malé stromky a ke e mají menší d ležitost než obrovské stromy) a vzdálenosti stromu od pozorovatele (vzdálen jší stromy jsou zobrazeny v menším detailu). P epínání stupn detailu probíhá automaticky, pokud jsou definovány objekty pro r zné stupn detailu. Jelikož nejsou k dispozici voln dostupné modely strom ve vyšším detailu, jsou sou ástí projektu jen stromy v nižším stupni detailu.
Obrázek 13. Zobrazení terénu bez strom (vlevo) a se stromy (vpravo)
Stromy obohatí terén o další d ležité detaily a pro pozorovatele zajímavá místa. Jejich zobrazení mnohonásobn zlepší dojem samotného terénu, jak lze vid t na obrázku 13.
str. 16
3.4. Další objekty Zlepšení reálného vzhledu je možné dosáhnout také p idáním dalších objekt . Takové objekty mohou být nap íklad auta, budovy, zem d lské stroje, mosty, lávky, zdi atd. Tyto objekty by m ly vtáhnout pozorovatele do d je a do doby ve které se scéna odehrává. Nap íklad je možné zobrazit historické vozy nebo futuristické zbran . Objekty mohou být bu sv tla, ásticové systémy, modely, kamera nebo skupina objekt . Všechny objekty jsou ve scén hierarchicky uspo ádány, tzn. je možné vytvo it skupinu objekt a p i zm n polohy této skupiny se zm ní poloha všech objekt , které skupina obsahuje. Pro bezproblémové vykreslení všech objekt je pot eba rozd lit ásti objektu na ásti nepr hledné a pr hledné. To je nutné z principu vykreslování rozhraním OpenGL. Nejd íve je nutné nastavit všechna sv tla, potom kreslit pevné objekty a nakonec objekty s definovanou pr hledností (nap íklad ásticové systémy, pr hledné ásti objekt - sklo atd.).
Obrázek 14. Objekty umíst né na terénu. Ho ící tanker (vlevo) a d m (vpravo)
Objetky umíst né ve scén mohou být nadefinovány v n kolika r zných stupních detailu a p i jejich vykreslení na obrazovku se vybere optimální stupe detailu. Tímto lze op t dosáhnout zrychlení vykreslování objekt které jsou umíst ny daleko od pozorovatele. Na obrázku 14 je uveden p íklad dvou objekt umíst ných na terénu.
3.5. Vodní hladina Nedílnou sou ástí terénu by také m la být možnost zobrazení menší vodní hladiny. Pro jednoduchou vodní hladinu bez vlnek sta í zobrazit rovnou plochu s polopr hlednou texturou. Pro lepší dojem jsem nastavil texturu tak, aby se pohybovala ve sm ru v tru.
str. 17
Obrázek 15. Zaplavené nížiny (naho e) a malé jezírko (dole)
3.5. ásticové systémy ásticové systémy jsou zásobníky mnoha malých ástic zobrazených jako tverce s áste n pr hlednou texturou. Díky nim je možné snadno naprogramovat kou , exploze, efekty zásah st el, vodní fontány a jiné efekty. Tyto systémy se proto využívají ve v tšin dnešních her. Mnou navržený ásticový systém se skládá ze t ídy CEmitor, která se stará o správu ástic (jejich vytvá ení, rušení a aktualizaci v ase), a struktury TParticle, která uchovává informace o každé ástici (pozice, barva, rychlost, sm r atd.) ástic mohou být zobrazeny tisíce a velmi asto dochází k vytvá ení nových a rušení starých. Alokování pam ti pro každou zvláš by zabralo p íliš mnoho asu. Proto jsem použil datovou stukturu dvojitého lineárního seznamu. Pri vytvo ení nové ástice se alokuje pam (pokud je seznam s nepoužívanými ásticemi prázdný) a uloží se na po átek lineárního seznamu s aktivními ásticemi. Jakmile vyprší platnost ástice, nedojde k uvoln ní pam ti ale ástice se pouze p esune do druhého lineárního seznamu, ve kterém jsou uloženy struktury nepoužívaných ástic. Pokud je v tomto seznamu uložena alespo jedna ástice tak se p i vytvá ení nové ástice
str. 18
použije (tj. pro novou ástici se použije d íve alokovaná pam ). Výhoda tohoto ešení je efektivita ásticového systému p i práci s pam tí.
Obrázek 16. P íklady ásticových systém (fontána, ho ící d m, sníh, ohnivý kruh)
str. 19
4. Implementace 4.1. Zobrazení terénu Program, který zobrazuje scénu ve 3D rozm ru se jmenuje 3Dengine-release.exe. Tento program se ovládá pomocí konfigura ního souboru. V n m lze nastavit výšku a ší ku výsledného okna, barevnou hloubku, hloubku Z-Bufferu, zda se má program spustit v režimu celé obrazovky, kvalitu zobrazení objekt , reakce na pohyby myši a soubor se skriptem. Jako skriptovací jazyk jsem použil jazyk LUA, který je pom rn rozší ený. Vybral jsem jej proto, že jej lze snadno integrovat s programem C++. P íklad použití skriptu uvedu pozd ji v textu. Hlavní funkce programu je umíst na v souboru main.cpp. Nejd íve je vytvo en soubor pro ukládání kontrolních výpis (log.txt). Pro snadnou práci s ním byla implementována t ída CLog v sobuoru CLog.cpp a CLog.h. Poté jsou na teny údaje z konfigura ního souboru. T ída pro na ítání *.ini souboru se jmenuje CIniFile a je umíst na v souborech CIniFile.cpp a CIniFile.h. Následn je vytvo eno hlavní okno aplikace podle požavk v nastavení. Pro tento ú el byla vytvo ena t ída CWindow v souborech CMyWindow.cpp a CMyWindow.h. Okno je vytvo eno pomocí Win API funkcí a je možno nastavit hodnotu gamma, která ur uje k ivku jasu. Dále je inicializováno rozhraní OpenGL. Celé nastavení bylo zahrnuto do jedné t ídy CRenderDevice která je uložena v souborech CRenderDevice.cpp a CRenderDevice.h. Tato funkce vytvo í rendering context pot ebný pro OpenGL a inicializuje toto rozhraní. T ída dále obsahuje metody pro nastavení rozší ení OpenGL - multitexturingu, kompresi textur a anizotropního filtrování. Dále jsou implementovány metody pro uložení aktuálního snímku a testování chyb. Poté je vytvo en objekt typu CDirectInput pro ovládání vstupu (myši a klávesnice) a CSoundManager pro zvukový výstup. Další bod inicializace je vytvo ení rozhraní pro spoušt ní skript LUA. Toto rozhraní je umíst no ve t íd CScriptManager v souborech CScriptManager.cpp a CScriptManager.h a práv zde jsou definovány funkce, které lze z jazyka LUA volat. Poté se spustí funkce Init ze skriptovacího souboru, tím dojde k na tení
str. 20
všech objekt do hierarchické struktury scény (kamery, modely, sv tla, skybox, terén, emitory atd.). Následuje vytvo ení dialog pro nastavení n kterých hodnot p ímo z programu bez nutnosti spoušt t program znovu. Tyto dialogy mohou obsahovat okna, tla ítka, checkboxy, listboxy, panely, posuvníky a další prvky. Dialogy jsou zobrazeny p ímo rozhraním OpenGL. Pro správu dialog slouží všechny soubory a t ídy v adresá i source/GUI. Poté následuje smy ka, která se opakuje pro každý vykreslený snímek do té doby, než program skon í. V první ásti této smy ky dojde ke zpracování zpráv windows, aktualizaci vstupu od uživatele a vygenerování n kterých fyzikálních veli in (vítr). Následuje aktualizace scény v závislosti na pohybu uživatele. Poté dojde k zjišt ní viditelnosti všech objekt z pohledu uživatele. a vypo ítá se detekce kolizí. Následuje rozložení terénu na optimální trojúhelníkovou sí a poté za ne vykreslování. Nejd íve je vykreslena textura pozadí, poté jsou nastavena všechna sv tla a dojde postupn k vykreslení terénu, všech pevných objekt , pr hledných objekt a ásticových systém . Poté jsou vykresleny v p ípad pot eby i další data (drát né modely, obálky objekt , normály trojúhelník atd.). Následn dojde k vykreslení dialog a informací na obrazovku ve 2D režimu zobrazení. Toto celé se opakuje do té doby, než uživatel klikne na tla ítko konec. Poté dojde k uvoln ní veškeré alokované pam ti. Pro testování zda všechna pam uvoln na byla do projektu zahrnuta knihovna Memory manager (MMGR) od Fluid Studios. Implementace terénu je umíst na ve t ídách CTerrain a CPatch v souborech CTerrain.h a CTerrain.cpp. T ída CTerrain má za úkol spravovat terén jako celek, narozdíl od t ídy CPatch, která souvisí s ástmi terénu o p edem dané velikosti (nap íklad 32x32 bod ). CTerrain obsahuje metody pro inicializaci terénu, na tení dat ze souboru vygenerovaného editorem, výpo et normál, správu všech dlaždic, ze kterých se terén skládá a vykreslení terénu, strom a vody. Pro na tení terénu ze souboru vygenerovaného editorem slouží metoda Load, která nastaví všechny vlastnosti terénu, jako je velikost rastru, na te textury, výškovou mapu a všechny stromy, následn dojde k výpo tu normálových vektor a inicializaci dlaždic, ze kterých se struktura terénu skládá. Metoda LoadHeightMap na te výškovou mapu z obrazového souboru, alokuje pam pro všechny trojúhelníky a nastaví správné sou adnice všech bod , ze kterých je terén složen. Alokování veškeré pam ti je uloženo v metod Init. V každém snímku je volána nejd íve metoda Reset a následn metoda Render. Metoda Reset otestuje viditelnost všech dlaždic z
str. 21
pohledu pozorovatele, rozloží terén na optimáln vytvo enou trojúhelníkovou sí a vypo ítá úrove detailu všech viditelných strom . V metod Render je z optimáln rozložené sít vygenerováno pole trojúhelník , které je následn vykresleno na obrazovku. Zobrazení textury a detailní mapy sou asn na každém trojúhelníku je provedenou technikou tzv. multitexturingu, která spo ívá v zobrazení n kolika textur sou asn . Tuto techniku musí podporovat grafická karta po íta e. Pokud ji po íta nepodporuje, je každý trojúhelník vykreslen 2krát po sob , p i emž dojde k se tení hodnot obou textur. Tato technika se nazývá míchání barev (z angl. blending). Výsledek je v tomto p ípad mírn pomalejší, protože tato operace není hardwarov akcelerovaná, ale lze ji použít na všech grafických kartách. Navíc oba dva algoritmy poskytují naprosto stejný výsledek. Po vykreslení terénu je volitelná možnost vykreslení drátového modelu terénu a normálových vektor v každém bod . Následn je podle požadavku na po et zobrazených trojúhelník upravena hodnota, která udává hranici zda se má každý trojúhelník p i vytvá ení optimální sít dále p lit nebo už nikoliv. Dále jsou v této t íd k dispozici metody RenderTrees a RenderWater, které na obrazovku vykreslí stromy a vodu. T ída ješt obsahuje metodu GetHeight, která vypo ítá interpolací výšku terénu v libovolném bod mezi známými hodnotami. T ída CPatch obsahuje metody pro výpo et d ležitosti jednotlivých trojúhelník , rozložení na optimální trojúhelníkovou sí a p ipravení trojúhelník do pole pro vykreslení. Metoda Reset provede inicializaci dlaždice, vytvo í dva její hlavní trojúhelníky a provede napojení t chto trojúhelník s okolními dlaždicemi. Metoda Split provede rozp lení libovolného trojúhelníku a v p ípad pot eby se postará o rozp lení sousedních trojúhelník tak, aby nedocházelo k žádným chybám (viz. kapitola 2.1.4). Metoda ComputeBoundingBox vypo ítá obálku dané dlaždice, podle které se po ítá viditelnost celé dlaždice. Metody ComputeVariance(Recurse) jsou vytvo eny pro výpo et d ležitosti všech trojúhelník . Metody Tesselate(Recurse) slouží k rozložení terénu na optimální trojúhelníkovou sí v závislosti na poloze pozorovatele a lenitosti terénu. Metody Render(Recurse) provedou transformaci vytvo ené trojúhelníkové sí na jedno velké pole trojúhelník , které na dnešních grafických kartách možné vykreslit mnohonásobn rychleji než každý trojúhelník samostatn .
4.2. Editor terénu Editor terénu je program, který umož uje vizuální návrh terénu. Program umí na ítání a ukládání výškové mapy a textury terénu z obrazového souboru, zobrazení mapy v nastavitelném m ítku, snadé vkládání p eddefinovaných objekt na libovolné místo (stromy, ke e atd.),
str. 22
nastavení základních parametr terénu (vzdálenost rastru, p evýšení atd.) a vizuální nastavení výšky vodní hladiny. Výslednou práci je možné uložit (nap . do XML souboru) a zp tn na íst. Pro vytvo ení programu jsem se rozhodl využít rozhraní zvané WinAPI. Vypo ítání vrstevnic terénu je operace hodn náro ná na výkon po íta e a p i pohybu v map i zm n m ítka je nutné vrstevnice vždy p epo ítat. Toto se mi díky rychlosti WinAPI poda ilo implementovat bez zbyte ného ekání. Pro vstup a výstup dat jsem se rozhodl použít informace uložené v XML souboru, protože je p ehledn jší než oby ejný textový nebo binární soubor a lze jej ru n editovat, což bylo nutné p i lad ní výsledného formátu tohoto souboru. Editor využívá ásti kódu napsané pro samotnou bakalá skou práci, využil jsem nap íklad kód pro na ítání textur r zných druh formát (JPG, BMP, TGA). Toto je nutné pro slad ní možností editoru a samotného programu, který zobrazuje terén ve 3D.
4.2.1. P íklad práce s programem Po spušt ní programu je vhodné nejd íve na íst ze souboru výškovou mapu nebo ji vygenerovat. Na tenou výškovou mapu je možné zobrazit ernobíle (tmavé body znamenají nižší místa a sv tlé body znamenají vyšší místa) nebo pro lepší názornost obarven . Zárove je možné zapnout zobrazení vrstevnic a vodní hladiny. Vrstevnice nad vodní hladinou jsou zobrazeny hn d a vrstevnice pod vodní hladinou jsou zobrazeny mod e.
Obráezk 17. Zobrazení výškové mapy, obarvené výškové mapy a mapy s vrstevnicemi Po na tení výškové mapy je vhodné na íst texturu terénu a potom vygenerovat n jaké stromy
str. 23
Obrázek 18. Mapa s na tenou texturou a mapa se stromy Poté sta í terén uložit do XML souboru. Výsledek je zobrazen na obrázku níže:
Obrázek 19. Výsledná scéna
4.2.2. Vlastnosti programu Editor terénu je program, který je ur en pro vizuální návrh terénu. Hlavní vlastnosti programu jsou: - Na ítání výškové mapy a textur ze soubor BMP, TGA a JPG - Umíst ní jednoho nebo více strom pouhým kliknutím myši - Zobrazení vrstevnic z výškových map - Nastavení výšky vodní hladiny - Generování výškové mapy algoritmem fBm (fractional Brownian motion) - Import a export všech dat z/do XML souboru - Nastavení vlastností terénu: P evýšení, velikost rastru atd.
-
P ibližování mapy a pohyb v ní
str. 24
5. Záv r Velká výhoda v použitém algoritmu ROAM je v jeho obrovské škálovatelnosti podle po íta e na kterém b ží. Není žádný problém zobrazit terén na po íta i se slabým CPU a integrovanou grafickou kartou v nízkém detailu a na jiném po íta i s rychlým CPU a moderní grafickou kartou ve velmi vysokém detailu. Tato práce mi byla p ínosem v tom, že jsem si prakticky nap íklad vyzkoušel práci se strukturami dvojitého lineárního seznamu, binárního a obecného stromu a jejich návrhu. Také jsem se díky ní velmi zdokonalil v používání rozhraní OpenGL a blíže jsem se seznámil s funkcemi Win API. Díky zvolenému typu aplikace (zobrazení dat v reálném ase) jsem mnohokrát musel kód p episovat tak aby byly funkce, metody a struktury efektivní. Poznal jsem, že programování není jen zábava ale i ešení r zn složitých problém . Návaznost programu na další projekty podobného typu je možná, nap íklad jej lze využít pro zobrazení výškových map získaných z vytišt né mapy (práce Vytvo ení výškové mapy z vrstevnic v rastrové map z roku 2006).
5.1. Možné využití aplikace a další vývoj projektu S rostoucím výkonem po íta se zlepšují možnosti p i zobrazení velkého množství dat. V sou asné dob je možné zobrazit stále více dat v reálném ase, a tudíž lze dosáhnout velmi kvalitních výsledk . Tím pádem je dobré uvažovat na smysluplném využití tohoto výkonu. Zobrazení terénu je možné využít v pr myslu, nap íklad v leteckých simulátorech p i výuce pilot . V tomto p ípad je zobrazení na po íta i jedinou možností, jak bezpe n nau it pilota ovládat daný stroj na zemi, ješt p ed tím než poprvé vzlétne. V poslední dob dochází velmi asto k záplavám. P i návrhu protipovod ových opat ení by mohlo pomoci zobrazení výsledk simulace záplavových oblastí v blízkosti vodních tok . Další možné využití zobrazení terénu by mohlo být v kartografii a GIS. P i spojení programu s reálnými mapami by jejich zobrazení ve 3D by mohlo být být využito nap íklad p i sledování polohy dopravních prost edk , polohy chrán ných živo ich (která by se získala p es vysíla ku), navigaci a plánování trasy p i procházení turistických cest a cyklistických stezek.
str. 25
Aktuální poloha se získá p es GPS a mapa by byla zobrazená na p enosném po íta i nebo pocket PC (pop ípad v telefonu s v tším displejem).
Obrázek 20. Porovnání letecké fotografie a výsledné scény Zobrazení terénu m že být využito i v zábavném pr myslu v po íta ových hrách nebo nap íklad p i to ení nákladných filmových scén (vytvo it po íta ový model terénu m že být mnohem levn jší varianta než výprava p es p l sv ta na požadované místo nebo nap íklad do vesmíru - v p ípad sci-fi terénu). Další možností je využití v reklam , nap íklad p i prodeji objekt nebo stavebních pozemk . Zájemce si m že stáhnout data a po pozemku se projít, aniž by musel odejít od po íta e. Aplikaci lze využít dále nap íklad pro armádní ú ely, p i zobrazení rozmíst ní vojenských jednotek. Myslím si, že program který jsem vytvo il je pro demonstraci postup zobrazení terénu ve 3D grafice pln vyhovující. Snažil jsem se o co nejvyšší možnost budoucí rozši itelnosti, efektivní provád ní operací a co nejjednoduší ovládání. Poda ilo se mi implementovat algoritmus ROAM a pom rn efektivn zobrazovat terén o velikosti 2x2km s rozlišením 5m. Díky editoru lze terén snadno vytvá et a modifikovat. Pro reáln jší vzhled jsem p idal možnost na ítat další objekty, modely a p idal jsem r zné speciální efekty, jako jsou ohe , voda, dým atd. Terén by do budoucna bylo možné vylepšit v kvalitn jším zobrazení vodní hladiny, zobrazením vržených stín pod objekty, podporováním moderních pixel a vertex shader (to jsou programy které neb ží na CPU ale na grafickém procesoru). Dále by bylo možné implementovat knihovnu pro fyzikální výpo ty a lépe po ítat kolize objekt mezi sebou. Nakonec by bylo dobré uvažovat o implementaci prostorového zvuku a deformaci terénu (p i výbuchu atd.)
str. 26
6. Literatura [1] Mark Duchaineau, Murray Wolinsky, David E.Sigeti, Mark C. Miller, Charles Aldrich, Mark B.Mineev-Weinstein, ROAMing Terrain: Realtime Optimally Adapting Meshes, IEEE Visualization '97 Proceedings, 1997 [2] Trent Polack,Game Development Series: Focus on 3D terrain programming, Premier Press, USA, Ohio, 2003, 239 stran, ISBN 1-59200-028-2 [3] Tom Davis, Jackie Neider, Dave Shreiner, Mason Woo, OpenGL Programming Guide, Addision Wesley, 1997, 410 stran, ISBN: 0-201-63274-8 [4] Bryan Turner, Real-Time Dynamic Level of Detail Terrain Rendering with ROAM, Gamasutra, 2000, dostupné na adrese http://www.gamasutra.com/features/20000403/turner_01.htm, 17.4.2006 [5] Yordan Gyurchev, ROAM Implementation Optimizations, Flipcode, 2001, dostupné na adrese http://www.flipcode.com/articles/article_roamopt.shtml, 17.4.2006 [6] Microsoft software development network, Microsoft Corporation, 2006, dostupné na adrese http://msdn.microsoft.com [7] Encyklopedie Wikipedia, 2006, dostupné na adrese http://en.wikipedia.org, http://cs.wikipedia.org [9] Hugo Elias, Perlin Noise, 2003, dostupné na adrese http://freespace.virgin.net/hugo.elias/models/m_perlin.htm, 17.4.2006 [10] Virtual Terrain Project, dostupné na adrese http://www.vterrain.org, 17.4.2006
str. 27
7. P íloha 1 - Editor terénu 7.1. Hlavní okno editoru Aplikaci tvo í okno, které je rozd leno na n kolik ástí: Menu, Nástrojová lišta, Záložky z edita ními funkcemi, Mapa s posuvníky, Zobrazení stavu úlohy (je viditelné jen když je t eba) a Stavový ádek
Obrázek 21. Hlavní okno editoru terénu
7.2. Menu Menu programu se skládá z 5 položek (File, Terrain, Display, View, Help). Popis jednotlivých položek:
str. 28
-
File/New
-
File/Open... File/Save As... Terrain/Size
-
Terrain/Height
-
Terrain/Grid Size
-
Terrain/Contour Height
-
Display/Water Display/Trees Display/Contour Display/Height Map Display/Texture Display/Color Map
-
View/Put Near View/Take Away View/Take Max Away Help/About
Za ne editovat nový terén. Všechna d íve vytvo ená data budou smazána Otev e z XML souboru d íve terén Uloží do XML souboru práv vytvo ený terén Nastaví velikost terénu a pot ebné rozlišení výškové mapy. Možnosti jsou 128x128, 256x256, 512x512 a 1024x1024 Nastaví p evýšení terénu (rozdíl mezi nejnižším a nejvyšším bodem). Možnosti jsou 20m, 50m, 100m, 200m. Tato položka má vliv pouze pro export dat a je využívána až p i zobrazení v 3D enginu. Nastaví vzdálenost dvou sousedních bod v rastru. Možnosti jsou 1m, 2m, 5m, 10m. Tato položka má vliv pouze pro export dat a je využívána až p i zobrazení v 3D enginu. Nastavení této položky má vliv na zobrazení vrstevnic. Ty mohou zobrazovat p evýšení 1m, 2m, 5m, 10m nebo 20m Nastaví, zda se má v 3D enginu zobrazovat vodní hladina Nastaví, zda se mají v editoru zobrazovat stromy Nastaví, zda se mají v editoru zobrazovat vrstevnice Nastaví, zda se má v editoru zobrazovat výšková mapa Nastaví, zda se má v editoru zobrazovat textura terénu Nastaví, zda se má v editoru zobrazovat obarvená výšková mapa P iblížení mapy Oddálení mapy Maximální oddálení mapy Zobrazí informace o programu
7.3. Mapa Ovládání mapy je intuitivní. Pro posun v map slouží posuvníky po stranách mapy. Mapa se dá p iblížit nebo oddálit tla ítky „+“ a „-“ v nástrojové lišt nebo otá ením kole kem myši p i sou asn stisknuté klavese CTRL. V levém spodním rohu mapy se zobrazuje m ítko, které se automaticky p izp sobuje p iblížení mapy (a také v závislosti na velikosti rastru):
str. 29
Obrázek 22. M ítko s automatickým p izp sobením p iblížení
7.4. Záložky s edita ními funkcemi Program obsahuje 4 záložky pro editaci a nastavení r zných vlastností terénu. Pat í mezi n záložka Terrain, Trees, Water a Statistics.
Obrázek 23. Záložky Terrain, Trees Záložka Terrain - V této záložce jsou v sekci Perlin Noise Generator parametry pro vygenerování výškové mapy algoritmem fractional Brownian motion. Položka Frequency udává lenitost terénu a položka Octaves udává vrás itost terénu. Tla ítkem Generate! se spustí generování terénu, které m že podle velikosti terénu trvat n kolik desítek sekund. V sekci Load & Save Maps jsou umíst ny tla ítka pro na ítání a ukládání výškové mapy a textury z/do obrazového souboru.
str. 30
Záložka Trees – V této záložce je jediná sekce Tree Generator. Tato sekce je ur ena pro nastavení vkládání strom do mapy. Je nutné nejd íve ze seznamu vybrat typ stromu, který se bude do mapy vkládat. V sou asné dob je k dispozici kolem 40 druh strom . Potom se v položce Min Tree Distance nastaví minimální vzdálenost strom od sebe. Tato položka m že nabývat kladných i záporných hodnot. V p ípad kladných hondot udává jak nejblíže budou generované stromy od sebe. V p ípad záporných hodnot mohou být generované stromy áste n prolnuty, nap íklad korunami. Položka Max Generating Distance udává, jak daleko budou stromy generovány od pozice kliknutí myší. Po stisknutí tla ítka Add Tree je možno generovat stromy kliknutím do mapy nebo tažením myši se stisknutým levým tla ítkem. Nové stromy se generují do vzdálenosti Max Generating Distance od pozice myši a s minimální vzdáleností od ostatních strom Min Tree Distance. Po stisknutí tla ítka Delete Tree je možné mazat stromy do vzdálenosti Max Generating Distance. Záložka Water – Tato záložka obsahuje jedinou sekci Water Settings ve které je posuvník Water Height, kerým se nastavuje výška vodní hladiny. Zm na hodnoty posuvníku se okamžit projeví v map za p edpokladu že je v menu zapnuta položka Display/Water. Záložka Statistics – Tato záložka je prozatím bez významu.
str. 31
