Generátor virtuální městské zástavby
Výtvarná informatika - školní projekt
O mě Moje zájmy Projekty a tvorba Různé designy Univerzální instalační program AlešGame


Diplomová práce

Optimalizace detekce kolizí ve virtuální městské zástavbě


Pohled do virtuálního města

Práce obsahuje




Algoritmy detekce kolizí

- QuadTree
- OctTree
- Triangle-to-Triangle

Generování virtuální městské zástavby

- Rozmístění objektů
- Náhodou řízené generování

Prohlížení scény a letecký simulátor

- Pohyb kamery
- Fyzikální model

Grafický výstup

- Implementace v COIN3D
- Tvorba textur a modelů
- Optimalizace

Měření výkonu

- Počet snímků za sekundu - Fps
- Doba trvání detekce kolizí


Trojúhelníková síť

Podrobněji



Algoritmy detekce kolizí QuadTree a OctTree
- Algoritmy pracující na principu dělby prostoru
- Iterativní tvorba stromu
- Přesun z kvadratické složitosti k logaritmické


Obrázek ukazuje dělení prostoru algoritmem QuadTree
Tvorba stromu algoritmem QuadTree


Generování virtuální městské zástavby
- Generování do čtvercové sítě
- Pokládání silnic
- Tvorba budov
- Načítání parametrů ze souboru
- Oddělení generování od grafické implementace


Jeden z pohledů do virtuálního města Jeden z pohledů do virtuálního města


Použití detekce kolizí a pohyb objektů



- Použitá varianta OctTree:

- Je použit OctTree, jehož uzly mají nastavitelnou kapacitu počtu objektů, které mohou obsahovat.
- Pokud je kapacita překročena, pak se objekty rozdělí do nových pod-uzlů.
- Všechny objekty jsou pouze v listových uzlech.

- Způsob detekce kolizí

- Testují se jednotlivá obalová tělesa na průnik.
-Upravená funkce testu na průnik.

- Pohyb objektů

- Pohybující se objekt je vždy vyjmut z OctTree. Potom je spočtena jeho nová pozice a objekt je vložen zpátky do OctTree na novou pozici. Při tomto vkládání se detekuje zda nedochází ke kolizi.

- Reakce na jednotlivé kolize

- Pokud je kolize detekována, pak je objekt vrácen na své původní místo a vynulována jeho rychlost. Dynamickým objektům je vypnut motor a vlivem gravitace padají k zemi.


Dynamický objekt „Ufo“ dopadnuvší na budovu


Grafická Implementace
- Coin3D a tvorba stromu scény- Sestavení budov z trojúhelníkovésítě
- Tvorba jednotlivých textur  


Tvorba textur pomocí 3dsMax


- Nanášení textur, rotace a scale
- Tvorba modelu „Ufo“
- Import modelů a textur ze souborů


Tvorba modelu ufo v 3dsMax


Proměření výkonnosti
- Proměření vlivu velikosti scény na výkon
- Proměření vlivu počtu pohyblivých objektů na výkon
- Proměření výkonu v závislosti na typu detekce kolizí
- Znatelné zrychlení detekce kolizí při použití OctTree


Kvadratická složitost bez OctTree x logaritmická složitost s OctTree


Spustitelnou verzi aplikace naleznete zde.
Zdrojové soubory aplikace naleznete zde.

Aplikace potřebuje ke svému běhu knihovny Coin3D, které můžete stáhnout na stránkách firmy Systems in Motion

Text diplomové práce a popis projektu.






Jan Kytýr