Vysoké učení technické v Brně
Fakulta
elektroniky a informatiky
Ústav informatiky a
výpočetní techniky
Ročníkový projekt
Jan Pečiva
2001
Datové struktury a importní
filtry
pro prohlížeč prostorové scény
- Prostudujte zadanou literaturu a seznamte se s problematikou načítání prostorových scén a jejich uložení pro rychlé vykreslení. Seznamte se s prohlížečem prostorových scén vyvinutém na ÚIVT v rámci předmětu POG.
- Navrhněte způsob načítání scény a datovou strukturu vhodnou k uložení načtené scény pro její vykreslení pomocí OpenGL.
- Implementujte načítání scény ze souborů ve formátu 3DS do vámi navržených datových struktur. Integrujte vaše řešení do stávajícího prohlížeče prostorových scén a ověřte funkčnost.
- Prozkoumejte vizuální kvalitu vykreslených testovacích scén a rychlost vykreslování.
- V závěrečné zprávě zhodnoťte dosažené výsledky, identifikujte případné nedostatky a navrhněte jejich zlepšení.
Prohlášení
Prohlašuji, že jsem tento ročníkový projekt vypracoval samostatně pod vedením Ing. Marka Křejpského a že jsem uvedl všechny literární prameny a publikace, ze kterých jsem čerpal.
Jan Pečiva
Abstrakt
Cílem tohoto projektu bylo vyvinout nástroj pro zobrazování prostorové scény přes rozhraní OpenGL. Později jsem se rozhodl realizovat za pomoci tohoto projektu počítačovou hru. Tehdy se do projektu zapojilo 17 studentů předmětu počítačová grafika a pod mým vedením jsme se pokusili realizovat něco na téma vesmírné bitvy. Jako dílčí úkoly se zpracovávaly: načtení scény, její zobrazení, pohyb uživatele, pohyb ve scéně, kolize, exploze, kouř za raketou, menu, 2d grafika pilotní kabiny a další.
Klíčová slova
3D engine, OpenGL, virtuální realita, textury, 3D efekty
Obsah
Úvod
Virtuální realita je dnes velkým pojmem, neboť otevírá člověku nový svět. Tento svět má jednu velmi důležitou vlastnost – není skutečný. To sebou přináší nebezpečí odcizení se člověka reálnému světu. Na druhé straně to přináší obrovské výhody. Tím, že je tento svět fiktivní, nestojí člověka nic. Mohu si zahrát tenis s virtuální kopií vítěze Davisova poháru a nic to člověka nestojí. Člověku se tedy otevřou obrovské možnosti. Osobně se domnívám, že virtuální realita brzy změní svět podobným způsobem, jako to udělal internet.
Dnes by se dalo dokonce tvrdit, že virtuální realita je teprve v plenkách, a myslím, že s odstupem času se to bude opravdu tak jevit. Vývoj v této oblasti probíhá opravdu velmi rychle a neustále se zde otevírají nové prostory pro vlastní výzkum. Toto byly jedny z důvodů, díky kterým jsem se začal velmi zajímat o počítačovou grafiku a virtuální realitu. Můj zájem nakonec vyústil až do tohoto projektu, který si dal za cíl vytvořit otevřený systém pro virtuální realitu. A jako konkrétnější cíl jsme si dali hru na téma vesmírných válek.
Na projektu jsem během zimního semestru pracoval sám a dalo by se říci, že jsem naplnil zadání. Během letního semestru byli do projektu za mého vedení zapojeni i studenti předmětu počítačová grafika. Řešili projekty zadané tak, aby projekt posunuly spíše k počítačové hře. Tak se do projektu dostalo několik speciálních efektů, pohyb, menu a mnoho dalšího. Kromě toho byla má předchozí práce otestována. Bylo odstraněno mnoho chyb a celkově bych řekl, že již máme solidní projekt, který je funkční pod systémem Windows i Linux. Zbývá mu jen dát konečný tvar a můžeme se chlubit novou počítačovou hrou.
Výchozí stav
Když jsem začínal pracovat na ročníkovém projektu, měl jsem k dispozici kód, který vznikl v rámci předmětu Počítačová grafika minulý rok. Dalo by se říci, že se jednalo o neodladěný prohlížeč modelů 3D Studia. Především bylo potřeba vyčistit kód a zajistit stabilní běh aplikace. Po zhruba měsíční práci na kvalitě kódu jsem měl projekt, na kterém se již dalo stavět. Pustil jsem se tedy do modulu logování a textur.
Textury
Texturami jsem se začal zabývat hned, ze začátku svého ročníkového projektu. Začalo to dvoutýdenním studiem možností správy textur v paměti a končilo to kódováním jednoduchého rozšířitelného správce textur.
Při návrhu správce textur jsem se soustředil především na efektivní využívání texturovací paměti. Po nastudování funkcí OpenGL pro podporu textur z [1] jsem navrhl jednoduchý systém tříd: Třída Texture reprezentující samotnou texturu a TextureLOD jako úroveň detailu textury. Tento systém umožňuje vytvořit systém uvolňování a načítání úrovní detailů textury podle potřeby a šetřit tak paměť. Správa texturovací paměti je poměrně komplexní problém, jeho některé detailnější popisy jsou v [3] a [2].
HW akcelerace
Jistou dobu jsem se dosti potýkal s problémem neakcelerovaného OpenGL na svém počítači i ve škole. Výsledky mého průzkumu jsou zde. U klasických ne příliš starých karet se často jedná o problém ovládačů. Většinou pomůže nová verze. Výjimku tvoří Voodoo 1 a 2 karty, pro které je třeba drobně upravit program. Dokonce jsem nabyl dojmu, že Voodoo katry se chovají různě podle toho, jaká verze ovladačů je nainstalována. Další problémy se objevují s barevnou hloubkou. Ne všechny barevné hloubky jsou vždy akcelerovány. Velmi často je akcelerovány pouze 16-ti bitové barvy. Program by měl mít možnost v případě, že není aktuální barevná hloubka nebo aktuální rozlišení hardwarově akcelerované, přepnout se do celoobrazovkového režimu a změnit nastavení podle potřeby.
Další kapitolou je hardwarová akcelerace při používání speciálních technik. Často můžeme při použitím méně obvyklých postupů při renderování scény spadnout zpět do softwarového renderování. U novějších karet s kvalitními ovladači se to často nestává, u mě například při zapnutí blendingu pro kouř za raketou klesne na mém Intelu 740 výkon zhruba na polovinu. Přestože poloprůhledný kouř tvoří pouze přibližně 100 trojúhelníků z celkových 8000, které jsou ve scéně, klesne počet snímků za sekundu z 30 na 15. To znamená polovina renderovacího času vezme 200 poloprůhledných trojúhelníků, přičemž zbylých 7800 neprůhledných je vyrenderováno za stejnou dobu. Uvedená čísla jsou pouze přibližná a demonstrační. Řešení vede dvěma cestami. Před spuštěním hry si otestovat rychlost používaných efektů a případně použít méně náročné efekty nebo je úplně zakázat. Druhá cesta je v udržování konstantního počtu snímků za sekundu. Pokud počet snímků klesne, zjednodušíme scénu – ubereme detaily, zjednodušíme nebo vypneme efekty, nerenderujeme vzdálené objekty a podobně.
Okenní systém projektu
Náš projekt používal od svého počátku okenní systém GLUT především protože zjednodušoval portování aplikace. Po delší době jsme však narazili na jeho poněkud problematické chování při chybách. GLUT totiž v případě chyby, například pokud nemůže otevřít okno, ukončí celou aplikaci. Programátorovi tak nezbývá ani možnost, jak oznámit chybu uživateli. Přidaly se i další problémy, a tak jsme se rozhodli přejít na nový okenní systém. Na doporučení na diskusní skupině comp.graphics.api.opengl jsme okenní systém realizovali přes knihovnu SDL (http://www.libsdl.org), přičemž knihovnu GLUT lze i nadále používat. Nicméně SDL se ukázala jako velmi silná a stabilní knihovna, která mnohem lépe vyhovuje požadavkům našeho projektu.
Graf scény
Graf scény byl navržen s ohledem na jednoduchost a rychlost. Nejjednodušší prvky ve scéně nemají dokonce ani souřadnice. Složitější prvky obsahují v sobě i funkce pro realizaci pohybu a zrychlování. Základní chování prvků je realizováno funkcemi Render, která vykreslí objekt, a funkcí TimeTick, která slouží pro aktualizaci stavu objektu scény. Protože momentálně nezobrazujeme žádné rozsáhlé a složité scény, byla scéna uložena pouze do třech seznamů: První seznam tvoří statické objekty scény. Pro ně lze zjednodušit mnoho operací, proto jsou v odděleném seznamu. Druhý seznam tvoří pohyblivé objekty. Pro ně je nutné provádět detekci kolizí a synchronizovat jejich stav po síti, pokud je hra v režimu „multiplayer“. Poslední seznam tvoří poloprůhledné objekty. Mezi ně zatím patří pouze kouř a exploze. Důležitost vyčlenit tyto objekty do speciálního seznamu je, že musí být renderovány jako poslední, aby je bylo možno správně zobrazit.
V budoucnosti plánujeme použít některý z již hotových grafů scény jako je Open Scene Graph nebo Open Inventor. Tyto grafy jsou velmi pečlivě navrženy a přinesly by nám do naší scény nové možnosti, bez kterých by jsme se ve složitějších scénách neobešli.
|
Exploze
Speciální efekt explozí řešil za mé asistence trojce studentů – Dušan Makovský, Petr Martiňák a Vladimír Florian. Zvolili jsme, řekl bych, nejjednodušší přístup k vytváření efektů exploze: Exploze je vytvořena jako posloupnost obrázků, které jsou postupně promítány na billboard. Jako rozšíření této základní techniky se momentálně pracuje animovaných billboardech a na procedurálně generovaných texturách exploze. |
|
Mapa scény
Mapa scény dává uživatelovi přehled o objektech ve svém okolí. Pracoval na ni Jaroslav Kadlec. K renderování mapy byly použity 2D možnosti rozhraní OpenGL. Objekty scény jsou nejprve transformovány aktuálními zobrazovacími maticemi, potom seřazeny do správného pořadí, a na závěr jsou za vypnutého z-bufferu vykresleny. Pracuje se i na druhé verzi mapy, která bude mít podobu spíše radaru. Ta však ještě není hotova. |
|
Kouř za letící raketou
Na efektu kouře za letící raketou pracovali Leoš Kučera a Roman Lukáš. Ti za mé „technické asistence“ vytvořili kouř za pomoci billboardů, které sledují stopu letící rakety. Pro tento efekt byly použity texturované i netexturované poloprůhledné billboardy. Textury kouře jsou generovány jako soustředné kruhy s klesající intenzitou ke krajům. Otevřena zatím zůstává nějaká fluktuační funkce, která by z kouře odstranila jeho symetrii a zrealističtěla celkový dojem. Druhou otázkou je, zda řadit ve scéně všechny poloprůhledné objekty, aby bylo zajištěno jejich korektní vykreslení. To může být výkonově dosti náročné při vyšším počtu objektů ve scéně. Prozatím řadíme billboardy pouze v rámci jedné kouřové stopy. |
|
Menu a fonty
Menu jsme se prozatím rozhodli realizovat sami vlastními silami. Pro výpis textu by se měla používat knihovna GLF, o jejíž začlenění do projektu se stará Pavel Faltýnek. Tuto knihovnu Pavel Faltýnek zhodnotil jako „knihovnu, na které se ještě pracuje“. Na menu pracuje Tomáš Procházka, který realizoval základ menu. Na něj by měl Michal Pecho umístit tlačítka a veškerou potřebnou grafiku menu. Do budoucnosti uvažujeme spíše o využití nějaké knihovny pro budování menu. Konkrétně zřejmě knihovnu GLUI. |
Kamery
Modul kamer měl rozšířit možnosti pozorovatele. Pozorovatel má nyní možnost dívat se z rakety a to i do různých směrů, další možností je dívat se zpoza rakety, nebo prohlížet si svou loď z vnějšku. Co se zatím nepovedlo implementovat je možnost sekundárních kamer. Na nich stále ještě pracuje Pavel Erlebach. Tyto kamery by měly například do rožku obrazovky renderovat pohled z vystřelené rakety nebo ukazovat pohled z kamarádovy rakety.
Při implementaci tohoto modulu bylo potřeba striktně od sebe oddělit jednotlivé transformační matice – projekční matice, matice pozorovatele a matice kamery. Po radách, které jsem se dozvěděl na různých místech na internetu, zůstává projekční matice nemodifikována kamerami, a slouží pouze k projekční transformaci. Modelview matice je pak používána k veškerým transformacím při renderování vlastní scény. Tyto operace skrývají několik problémů, na které většina programátorů narazí. Já je vyřešil takto: Do modelview matice je nejprve načtena transformační matice kamery. Po té se aplikuje vlastní matice pozorovatele. První zádrhel, který se objevil, byl v nutnosti oddělit translaci a rotaci z matice pozorovatele. Nejprve je potřeba aplikovat rotaci, a pak teprve translaci. Při renderování scény se používá opačné pořadí transformací a je možné ho provést pouze násobením matic. Zde musíme translaci vyjmout z matice, vynásobit současnou matici touto maticí, a pak provést translaci. Vše se zdálo funkční až do chvíle, kdy se začaly objekty pohybovat. Tehdy se ukázalo, že objekt pozorovatele se pohybuje jinak, než ostatní. Proto je potřeba rotační matici pozorovatele nejprve transponovat, a pak teprve odeslat do OpenGL.
Pohyb
Implementace pohybu, na které pracoval Robert Mackovik, se zdála zpočátku triviální, ale se zapojením kolizí, explozí a speciální dynamiky pro rakety se celá věc poněkud zkomplikovala a bude potřeba ji vyřešit zřejmě dokonalejším návrhem tříd scény.
Kolize
Původně jsme chtěli pro detekci kolizí použít nějakou kolizní knihovnu z internetu, ale ukázalo se, že nám bohatě stačí nahradit objekty ve scéně koulemi a provádět detekci kolizí mezi nimi. Tohoto zadání se ujal Roman Král a dalo by se říci, že úspěšně. Po každém vyrenderovaném snímku se provede detekce kolizí mezi všemi objekty scény. Jsou implementovány jen nejjednodušší algoritmy pro urychlení této činnosti. Přesto kolize zpomalují běh aplikace minimálně. Odhadujeme, že problémy se objeví až při stovkách objektů. Momentálně se pohybujeme o řád níže. Celkově se dá říct, že implementovaný modul kolizí splnil vše, co jsme od něj očekávali. Je možné vystřelovat střely a ty zasahují cíle. Rakety, které do sebe narazí, vybuchují a při načítání scény se objekty rozmísťují náhodně tak, aby se nedotýkaly.
Do budoucna plánujeme provádět přesnější detekci kolizí. Pro objekty, které neprojdou testem kolizí koulemi, provedeme časově náročnější detekci kolize mezi trojúhelníky, ze kterých se jednotlivé objekty skládají.
Komunikace po síti
Cílem tohoto projektu bylo vytvořit možnost zobrazovat jednu scénu na více počítačích, v případě hry tedy možnost hrát po síti s kamarády. Tento projekt v současné době řeší Adam Herout. Mým úkolem je pouze přizpůsobit scénu novým požadavkům rozdistribuování řízení objektů a interpolace jejich pohybu.
Momentálně nejsou ještě žádné výsledky, máme navržen princip komunikace a momentálně se pracuje na její implementaci.
Hvězdné pozadí
Tomuto projektu jsem se věnoval osobně. Požadavky
na výsledek byly rychlost vykreslení, co nejmenší výkonová náročnost
a realistický vzhled. Pro pozadí se obvykle používají dva přístupy –
textura namapovaná na kouli v jejímž středu je uživatel, druhá možnost
je stejná, ale používá krychli. Výhoda krychle je v nízkém počtu
trojúhelníků, v podstatě pouze 12. Zásadní nevýhoda krychle je zase
v nepřirozené projekci, kterou musí být textury na krychli vytvořeny,
aby vypadaly realisticky.
Zvolena byla metoda mapování textur na krychli. Problém se správnou perspektivou se u hvězdného pozadí ukázal jako vcelku nepodstatný, větší problém bylo požadované textury vůbec sehnat. Nakonec byly vygenerovány v astronomickém programu pro simulaci hvězdné oblohy. Navíc tento program zobrazoval hvězdy v podobné perspektivě, jakou potřebujeme pro naše textury. Další problém vyvstal s podporou textur v grafických akcelerátorech. Textury, které nanášíme na krychli by totiž měly být podobného rozlišení jako obrazovka. Rozměr textur byl zvolen 512x512 bodů. Tyto rozměry však nemusí podporovat některé akcelerátory. Běžné rozlišení je totiž 256x256. Prozatím byl tento problém ošetřen tak, že pokud nejsou 512x512 textury podporovány, není pozadí vykreslováno. Nejjednodušší řešení, které se nabízí, by bylo rozdělit texturu na čtvrtiny a zečtyřnásobit počet trojúhelníků.
Spolu s vykreslováním pozadí se nabídla další možnost zvýšení výkonu a tou je vynechat mazání framebufferu a z-bufferu. Zároveň s vykreslování pozadí je totiž možné tuto činnost provést. U některých grafických karet přináší tento postup poměrně značné zvýšení výkonu.
Umělá inteligence
Umělá inteligence se v počítačových
hrách využívá pro inteligenci hráčů, za které hraje počítač.
Někdy pro inteligenci nepřítele stačí jednoduchý algoritmus.
Ale dnešní moderní hry, kdy v 3D bludišti hraje profesionální hráč
a chce mít proti sobě rovnocenné soupeře, stává se tento problém
dosti komplikovaným. Dnes se pro počítačem řízené hráče
používají hlavně neuronové sítě především pro jejich schopnost
vyvíjet se.
Pro počítačem řízené rakety v našem projektu jsme také použili neuronové sítě. Na jejich vývoji jsem pracoval osobně. Implementována byla síť typu BPN (backpropagation neural network). Síť se nejprve inicializuje – přiřazení náhodných vah mezi neurony. Prozatím používáme pouze třívrstevné sítě. Po jejich vytvoření se síť naučí základnímu chování. Velké problémy se objevily při přivádění informací ze scény do neuronové sítě. Počet objektů ve scéně totiž není konstantní, ale neuronová síť má pevně daný počet vstupů. První pokus o řešení byl, přivést na vstup neuronové sítě data pouze o prvních čtyřech nejbližších objektech. Pro každý objekt se přiváděly na vstup sítě zhruba čtyři různé informace, celkově tedy šestnáct vstupů. Při učení sítě ale nastaly problémy. Síť se těžko učila a množina dat, která by byla potřebná k dobrému naučení, by byla příliš velká. Navíc doba učení sítě by byla obrovská. Nakonec byl zvolen nový přístup: Všechny objekty scény jsou postupně ohodnoceny prioritou. To provede speciální neuronová síť s jedním výstupem. Po té se vezme objekt s nejvyšší prioritou a informace o něm se přivedou na síť, která řídí chování dané vesmírné lodě.
Systém umělé inteligence je ještě stále pod intenzivním vývojem. Do konce semestru by mělo být dosaženo cíle, aby počítačem řízené rakety byly schopny samostatně útočit a pohybovat se. Do budoucnosti pak uvažujeme o nějakém genetickém vývoji sítí, což by mělo přinést další zvýšení inteligence.
Shrnutí dosažených výsledků
Výsledky, kterých jsme dosáhli, jsou, myslím, více než uspokojující. Oproti zadání bylo vytvořeno něco víc než prohlížeč prostorové scény. Podařilo se zorganizovat tým 17 studentů, kteří ve svých projektech dosáhli dobrých, někteří i výborných výsledků. Pro dotažení do finální podoby publikovatelné hry chybí dle mě měsíc práce a jeden měsíc testování, pokud by se našla parta třech až čtyřech lidí, kteří by na tom pracovali.
Byly snahy udělat z tohoto projektu otevřený projekt nebo knihovnu, která by byla publikovatelná na internetu. V současné době se nedá říct, že by projekt měl čistý návrh a jasné rozhraní, se kterým by mohl programátor pracovat. Pomohlo tomu také to, že na projektu dělalo tolik lidí, z nichž mnozí s C++ teprve začínali. Toto je zřejmě výchozí bod pro další vývoj projektu – ve světle nabytých zkušeností navrhnout novou strukturu projektu a tu znova realizovat.
Budoucnost
V budoucnu mám v úmyslu, pokud to bude možné, pokračovat na tomto projektu v rámci diplomové práce. Chtěl bych vytvořit kvalitně navržený 3D engine pro otevřené rozsáhlé scény. Dále bych se chtěl věnovat Open Inventoru a eventuálně bych ho chtěl použít jako graf scény. Více bych se chtěl zabývat světly ve scéně a některými speciálními technikami. Výsledný projekt bych rád publikoval na internetu jako opensource.
Literatura
[1] Segal,
M., Akeley, K.: The OpenGL® Graphics System: A Specification (Version 1.2.1)
Silicon
Graphics, Inc., 1600 Amphitheatre Pkwy., Mountain View, CA 94043, U.S.A., April
1, 1999, dokument dostupný na URL: http://www.opengl.org/developers/documentation/Version1.2/OpenGL_spec_1.2.1.pdf
[2] Silicon Graphics, Inc., 1600 Amphitheatre Pkwy., Mountain View,
CA 94043, U.S.A.,
SGIS_texture_lod - The Texture LOD Extension, 1998,
k dosažení na: http://toolbox.
sgi.com/TasteOfDT/documents/OpenGL/OGLonSGS/OpenGLonSGI-55.html
[3] Tringham,
N.: Textures in OpenGL Games Programming, k dosažení na: http://www.pseudonymz.demon.co.uk/gentex.html
[4] École
Polytechnique Montreal: New Functionality for Working With Textures,
kdysi k dosažení na: http://www.gegi.polymtl.ca/info/granger/cours/3.430/OpenGL/
[5] Silicon Graphics, Inc.,
1600 Amphitheatre Pkwy., Mountain View, CA 94043, U.S.A.,
Optimizing OpenGL Coding and Performance, 1997, dokument
dostupný na:
http://toolbox.sgi.com/TasteOfDT/documents/OpenGL/OptimOGL.html
[6] Kilgard, M.: Virtualized
OpenGL Light Sources for Efficient Multi-Light Source Lighting, k dosažení
na: http://reality.sgi.com/mjk/tips/VirtualizedLights/VirtualizedLights.html
[7]
informace o grafických
procesorech NVIDIA: http://www.nvidia.com/developer.nsf
Příloha
– ovládání programu
směr rakety myš
pohyb dopředu e, šipka nahoru
pohyb dozadu d, šipka dolů
pohyb doleva s, šipka doleva
pohyb doprava f, šipka doprava
pohyb nahoru r
pohyb dolů x
střelba mezerník
přerušení hry F2
menu F3
skrytí/zobrazení FPS F1
ukončení programu ESC