České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačové grafiky a interakce
Diplomová práce
Detekce kolizí pro simulaci dynamických jevů v 3D scénách Bc. Krystl Filip
Vedoucí práce: Ing. Jiří Bittner, Ph.D.
Studijní program: Elektrotechnika a informatika, strukturovaný, Navazující magisterský Obor: Výpočetní technika 12. května 2010
iv
v
Poděkování Rád bych poděkoval vedoucímu této práce Ing. Jiřímu Bittnerovi, Ph.D. za velmi cenné a přínosné rady v průběhu práce a za dobré vedení. Děkuji i své rodině a blízkým za psychickou podporu a trpělivost.
vi
vii
Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).
Abstract This thesis work deals with design and implementation of collision detection system and physical simulation of dynamic phenomena in 3D world. The first goal of this work is to analyze different techniques for collision detection in large scale and complicated scenes and implement one of them. The second goal is to analyze implementations of dynamic phenomena simulation (physical engines) and to connect one of them to scene. Own implementation of physical engine is not a goal. This work includes also a brief overview of actual physical engines. Another purpose of this work is to explore possibilities of using different collision detection systems in the chosen physical engine.
Abstrakt Tato práce se zabývá návrhem a implementací detekce kolizí a fyzikálně přesné simulace dynamických jevů ve 3D světě. Práce má za cíl prozkoumat techniky detekování kolizí ve složitých a rozsáhlých scénách a vybranou techniku implementovat. Dále prozkoumat knihovny pro simulace dynamických jevů (fyzikální engine) a simulaci napojit na 3D scénu. Práce si nedává za cíl implementovat vlasní simulaci, ale pouze využít některou ze stávajících knihoven. Práce obsahuje i stručnou rešerši stávajících fyzikálních enginů. Dále se práce zabývá využitím externích knihoven detekce kolizí pro zvolený fyzikální engine.
Úvod, popis problému a specifikace cíle Téměř žádný systém pro virtuální realitu se neobejde bez detekce kolizí. Celkový dojem z aplikací silně ovlivňuje schopnost reálně simulovat skutečný svět. Uživatel by v krajním případě neměl vůbec rozeznat hranice mezi světem virtuálním a reálným. Detekce kolizí k tomuto dojmu výrazně přispívá, z prvního Newtonova zákona plyne: "Působí-li jedno těleso na druhé, působí i to druhé na první.". Detekovat kolize znamená určit kdy, kde a jak k tomuto působení dochází. Systém pak musí na tyto události vhodně reagovat. Reakce na tyto události může vytvářet buď přímo modul detekce kolizí, nebo nějaký na něho navázaný nástroj. Jestliže reakci bude obstarávat někdo jiný než samotný modul, je nutné, aby modul událost předal správnému cíly. Typickou reakcí na takovou událost je aplikace momentu síly na jeden nebo oba objekty v kolizi. Detekování kolizí v interaktivních systémech musí být ve velmi rychlé, aby nebyla ovlivněna plynulost simulace. Detekování se provádí po každém pohybu libovolného objektu, k tomu dochází velmi často. Pro dodržení minimálního počtu 25 snímků za vteřinu musí tedy detekce kolizí proběhnout ve zlomku tohoto času, aby zbyl čas ještě na vykreslování scény a různé další operace. Při použití naivního algoritmu, testování každého objektu s každým, bychom dosáhli kvadratické složitosti. To by bylo pro rozsáhlé scény obsahující milióny trojúhelníků nepoužitelné, bude tedy nutné nasadit nějakou urychlující metodu.
1.1
Specifikace cíle
Cílem práce je vyvinout modul do existujícího systému VRUT (Virtual Reality Universal Toolkit), který bude schopný detekovat vzájemné kolize objektů ve scéně. Modul poběží ve vlastním vlákně a bude na systému nezávislý. Uživatel bude moci vybrat ze seznamu scénu, pro kterou se mají kolize vypočítávat. Po zadání scény modul načte potřebná data a vytvoří potřebné datové struktury. Modul bude mít po celou dobu běhu aplikace přímý přístup do scény. Po zapnutí modulu se začnou detekovat kolize. Modul bude umět pracovat s bezpečnou vzdáleností objektů ve scéně. To znamená, že bude možné zadat minimální vzdálenost objektů, aby jejich pozice byla brána jako nekolizní. Jestliže se objekty přiblíží na vzdálenost menší než je zadaná, pak se situace vyhodnotí jako kolizní. V případě kolizní
1
2
KAPITOLA 1. ÚVOD, POPIS PROBLÉMU A SPECIFIKACE CÍLE
situace bude modul schopný určit, které objekty kolidují, vypočítat přesné místo kolize, normálu roviny oddělující kolizní objekty a hloubku průniku objektů. Tyto informace bude odesílat jádru aplikace VRUT. Úroveň informací, které modul bude počítat, bude možné nastavit přes jednoduché uživatelské rozhranní. Modul bude umět i reagovat na nastalé kolize udržením objektů v nekolizní pozici. Druhá část projektu se zabývá fyzikálně přesnými odezvami na nastalé kolize. Z rešerše dostupných řešení vyberu vhodnou knihovnu pro fyzikální simulaci dynamických jevů a tuto knihovnu integruji do systému. To obsahuje přidání knihoven pro chod modulu do aplikace, inicializování knihovny po spuštění modulu, načtení scény a projevení výsledků simulačních kroků zpět v aplikaci. Dále propojím modul detekce kolizí s fyzikálním enginem pro možnost vlastního výpočtu kolizí a tím pádem větší kontroly nad odezvou systému. Bude nutné najít způsob komunikace mezi moduly, protože VRUT přímo nepodporuje komunikaci modulů mezi sebou.
1.2
VRUT
Projekt s názvem VRUT [1] vznikl v rámci spolupráce katedry počítačové grafiky a interakce ČVUT FEL s firmou Škoda Auto. Jeho podstatou je zobrazení grafických dat a podpora modulů. Moduly umožňují rozšíření funkcí hlavní aplikace při relativní nezávislosti. Název VRUT je zkratkou anglického Virtual Reality Universal Toolkit a měl by zhruba evokovat, co aplikace nabízí, tj. univerzální a flexibilní nástroj pro práci s grafickými daty. VRUT může fungovat jako určitý spojovací článek mezi několika subjekty. Jednotlivé subjekty mohou zadávat různé úlohy týkající se zobrazení nebo jiných operací nad grafickými daty a řešitelé těchto úloh vytvoří kompatibilní modul (plugin). Nová funkčnost realizovaná formou modulu je poté použitelná všude tam, kde je VRUT nasazen. Zatímco na straně školy VRUT slouží spíše jako pomocný vývojový nástroj, ve Škoda Auto budou skrze něj uvedeny do praxe nejrůznější moduly vytvořené třeba právě studenty školy. Řešitelům úloh odpadla nutnost implementovat části, jako je vstup, výstup, grafický výstup, graf scény a mnohé další, které se netýkají přímo úlohy. Místo toho se mohou plně soustředit na řešení svého problému ve vlastním modulu.
1.2.1
Jádro systému
Jádro systému VRUT má za úkol spravovat všechny moduly a grafická data, poskytuje pomocné prvky pro správný běh a ovládání aplikace. Velmi podstatnou částí je také správa událostí tvořící centrální prvek komunikačního kanálu mezi jednotlivými částmi aplikace a moduly. O dostupnost modulů pro danou platformu a také o jejich kompatibilitu s jádrem se stará správce modulů. Poskytuje zcela transparentí uvedení dostupného modulu do života a jeho korektní spojení s jádrem. Moduly jsou aktivovány pouze na žádost v případě potřeby, navíc je možné více aktivací téhož modulu, aniž by se navzájem nechtěně ovlivňovaly. V případě více modulů poskytujících stejnou funkci se správce rozhoduje podle priorit, pokud jsou definovány. Vzhledem k potřebě obsloužit velmi rozličné požadavky směrované ve výsledku na různé typy modulů obsahuje správce modulů dílčí části, správce jednotlivých typů. Správci mají na
1.2. VRUT
3
Obrázek 1.1: Architektura aplikace VRUT
starosti určitou podskupinu modulů stejného nebo kompatibilního typu. Každý požadavek na funkčnost poskytovanou modulem je směrován odpovídajícímu serveru, který se snaží vyhovět podle daných pravidel a aktivovat příslušný modul. Provázanost některých typů modulů s jádrem vyžaduje zvláštní zacházení, proto typy správců do značné míry odpovídají typům podporovaných modulů.
4
KAPITOLA 1. ÚVOD, POPIS PROBLÉMU A SPECIFIKACE CÍLE
Obrázek 1.2: Aplikace VRUT
Kapitola 2
Analýza a návrh řešení 2.1
Detekce kolizí
Detekce kolizí je obecně velmi složitý problém. Je nutné zjistit kolize každého objektu ve scéně se všemi ostatními, a to při každém pohybu libovolného objektu. Při použití naivní metody je časová složitost O(n2 ), kde n je počet objektů ve scéně. Objektů ve scéně může být velmi mnoho, ale jejich počet nebude převyšovat řád desítek tisíc. Tyto geometrie jsou dále složené z primitiv, jako například trojúhelníků. Musíme proto počítat s triangulací objektů a testovat musíme prmitiva místo samotných objektů. Míra detailů jednotlivých objektů se čím dál tím více zvětšuje a dnes nejsou výjimky objektů tvořených milióny trojúhelníky. Když si tedy spočítáme celkový možný počet testů ve scéně nutných pro naivní algoritmus, dostaneme se na řád miliard. A to je pro případy, kdy se jedná o interaktivní systém virtuální reality, nepoužitelné. Je proto nutné použít některou z urychlujících metod, například hierarchii obálek (dále jen BVH) nebo kd-stromy. Obě metody umí velmi rychle odřezat části scén, ve kterých nemůže dojít ke kolizi, aniž by musely testovat jednotlivá primitiva. K testům primitiv dochází až tehdy, jsou-li objekty v opravdu těsné blízkosti. Obě metody využívají dělení prostoru na části. BVH dělí prostor se zbytkem, to znamená, že některé části scény, kde nejsou žádné objekty, nejsou v datové struktuře vůbec zahrnuty. Naopak kd-stromy dělí prostor bezezbytku. Je několik možných variant, ale základní myšlenka spočívá v dělení prostoru vždy podle jedné z rovin paralelních se systémem souřadnic. Rovina se volí buď náhodně, cyklicky, nebo s použitím heuristiky. Kd-stromy pro množinu bodů je podle [4] [5] možné implementovat časovou složitost dotazu O(n1−1/d + k), kde n je celkový počet bodů, d je dimenze problému a k je počet nalezených bodů vyhovujících dotazu. Existuje i několik dalších rychlejších algoritmů, které jsou ale více závislé na počtu reportovaných bodů. Pro více informací odkáži na [6] V systému VRUT je již BVH pro objekty implementováno, proto jsem zvolil stejnou metodu i pro výpočet kolizí ve scéně. Bude možné využít stávající implementaci a tu případně dále rozšířit.
5
6
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
Obrázek 2.1: Příklady objemových obálek ve 3D. a) Koule, b) Osově zarovnaný kvádr.
2.1.1
Obálka
Obálka je zjednodušení reálného objektu, který může být velmi složitý, na nějaký jednoduše popsatelný matematický model, pro rychlejší testy kolize. Obálka musí vždy obsahovat celý objekt a zpravidla obsahuje i nějaký prostor navíc. Čím obálka obsahuje méně prostoru navíc, tím je větší šance, že test kolize obálek odhalí nekolizní pozici objektů uvnitř. Pro test je pak možné nejprve pracovat s obálkami namísto složité sítě trojúhelníků. Jestliže nedochází ke kolizi obálek objektů, nemůže docházet ani ke kolizi jednotlivých objektů. Ale naopak jestliže jsou obálky v kolizi, nemusí to nutně znamenat, že v kolidující pozici se nacházejí i objekty uvnitř obálek. Obálky nám tedy zjednodušují a urychlují výpočet pro objekty, které jsou v dostatečné vzdálenosti od sebe. Když se ale jedná o objekty v těsné blízkosti, pak obálky zpravidla nedokáží kolizi vyloučit a musíme přejít k detailnějšímu prozkoumání.
Obrázek 2.2: Různé typy obálek.
Existuje několik základních typů obálek ve 3D, koule (Sphere), osově zarovnaný kvádr (AABB), objektově zarovnaný kvádr(OOBB) a další, ukázky jsou na obrázku 3.1. Liší se mírou aproximace skutečných objektů a složitostí výpočtů, ta se skládá z výpočtu pozice a
2.1. DETEKCE KOLIZÍ
7
velikosti obálky a z testů kolize mezi těmito obálkami. Vhodný typ obálky se určuje v závislosti na použití. Pro prostředí složené převážně z kulatých objektů, jako například simulace pohybu míčků v místnosti, je vhodné použít obálky typu koule. Ale naopak pro prostředí složené z kvádrů by bylo použití koulí značně nevhodné a výpočet by byl pomalejší, něž při použití například osově zarovnaného kvádru. Má práce bude v praxi využívána v automobilovém průmyslu, proto nepředpokládám velké množství kulatých objektů. Zvolil jsem tedy pro mou implementaci obálky typu osově zarovnaný kvádr. Objektově zarovnaný kvádr by sice pravděpodobně lépe aproximoval objekty, ale jejich výpočet a testy kolizí jsou značně náročnější. V budoucnu by ale bylo dobré vyzkoušet i tuto možnost, zdali by nedosahovala lepších výsledků.
2.1.2
Osově zarovnaný kvádr
Obrázek 2.3: Osově zarovnaný kvádr.
Osově zarovnaný kvádr (AABB - Axis Aligned Bounding Box) je jeden z nejjednodušších typů obálek. Je to kvádr, který má všechny osy paralelní s osami souřadného systému a obsahuje všechny zadané body, nebo jiná primitiva. Obálka musí být nejmenší možná, aby zabrala co nejméně volného prostoru. Je několik možností, jak je možné jej reprezentovat. V mé práci používám reprezentaci pomocí minimálního a maximálního bodu. Odečtením souřadnic obou bodů lze snadno získat velikost kvádru v každé ose. Test kolize těchto obálek je poměrně jednoduchý. Využívá se při tom "Separating axis theorem"[3], volně přeloženo jako teorém oddělující roviny. Teorém pro 2D říká: "Dva konvexní objekty se neprotínají, jestliže se neprotínají jejich projekce do libovolné přímky.". Když toto převedeme do 3D a použijeme AABB, pak stačí nalézt jednu osu, v níž se projekce obálek neprotínají. Takové osy mohou být pouze osy rovnoběžné se systémem souřadnic. Osu najdeme postupným procházením všech tří os, a jestliže min(X) > max(Y ) nebo
8
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
Obrázek 2.4: Separation Axis Theorem.
max(X) < min(Y ), pak je projekce AABB do této osy disjunktní. Stačí první taková nalezená osa a je jasné, že se obálky neprotínají. Naopak pokud takovou osu nenajdeme, pak se obálky protínají.
2.1.3
Hierarchie obálek
Použitím obálek místo samotných objektů pro prvotní test kolize bychom sice určitého urychlení dosáhli, ale pořád bychom museli testovat každý objekt se všemi ostatními, a to by bylo časově velmi náročné. Zásadní urychlení nám přinese až použití hierarchie obálek (BVH). Tím dokážeme ihned odříznout celou skupinu objektů, které nemohou být v kolizi s jinou skupinou objektů. A nemusíme se vůbec dostat až k testům obálek jednotlivých objektů. BVH je datová struktura typu strom, která je postavena nad obálkami primitiv. Primitiva se zabalí do obálek a vytvoří listy BVH stromu. Listy jsou pak seskupovány dohromady a tvoří vnitřní uzly stromu. Ty se dále seskupují, až vznikne jedna velká obálka obsahující všechna primitiva. Z té se udělá opět uzel a prohlásí se za kořen stromu. V listech nemusejí být primitiva samostatná, je možné v listech seskupit i více primitiv, a tím zmenšit hloubku stromu. Maximální počet primitiv v listech je buď nastaven přímo, nebo je možné nastavit maximální výšku stromu, počet primitiv v listech je pak různý. Čím bude strom vyšší, tím bude traverzace stromem náročnější, ale bude se testovat při případné kolizi listů více primitiv. Celkový čas testů je tedy velmi závislý na správném nastavení stromu. Obvykle se volí počet primitiv v listech jen v řádu jednotek [2]. Existuje několik pravidel, která by měl správný BVH strom splňovat [9]: 1. Uzly v každém podstromu BVH by měly být blízko sebe. Čím níže ve stromu, tím blíže sobě.
2.1. DETEKCE KOLIZÍ
9
Obrázek 2.5: Grafické znázornění testování kolize dvou AABB. a) Podmínka Ay-max < Bymin je splněna, proto AABB nejsou v kolizi. b) Ani jedna potřebná podmínka není splněna, proto AABB jsou v kolizi.
2. Každý uzel stromu by měl mít minimální objem. 3. Celková suma objemů všech uzlů stromu by měla být minimální. 4. Překrývání uzlů by mělo být minimální. 5. Strom by měl být vybalancován vzhledem k objemům vnitřních uzlů. Pro libovolnou BVH je možné určit očekávnou cenu dotazu. První taková funkce byla prezentována v [12] a byla dále rozšiřována do podoby T = NV CV + NP CP + NU CU + C0 , kde T je celková cena dotazu, NV je počet testovaných obálek na průnik, CV je cena za jeden test průniku obálek, NP je počet primitiv testovaných na průnik, CP je cena testu primitiv, NU je počet uzlů, které musejí být přepočítány, CU je cena přepočítání každého uzlu a C0 je jednorázová cena zpracování. Jenotlivé členy ve výrazu je možné minimalizovat různými způsoby, ale někdy minimalizace jednoho členu v součinu může způsobit nárůst druhého členu. Například NV je možné minimalizovat použitím lepších obálek, ale při použití lepších obálek se zvedne cena jejich testů CV . Je nutné vždy najít kompromis pro konkrétní případy použití, aby výsledek byl minimální. Důležitý parametr při volbě BVH je počet potomků jednotlivých uzlů. Teoreticky jich může být libovolný počet, ale je nutné se zamyslet nad tím, co bude nejlepší pro výpočet. Strom s větším stupněm bude sice nižší, ale expanze jednotlivých uzlů bude náročnější. Dosud nebylo publikováno žádné přesné vyřešení tohoto problému. Nejčastěji se používá
10
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
binární strom, který se dobře reprezentuje, staví i prochází. Například při stavbě od shora dolů je poměrně snadné rozdělit obálku na dvě podobné poloviny, než ji dělit na sobě podobné n-tiny.
2.1.4
Dvouúrovňová hierarchie BVH
Obrázek 2.6: Vlevo první úroveň BVH nad objekty ve scéně. Vpravo druhá úroveň nad primitivy objektu.
Pro správný a rychlý chod výpočtu kolizí ve scéně bude nutné spravovat dvě úrovně hierarchie BVH. První úroveň je hierarchie postavená nad celými objekty ve scéně a druhá úroveň hierarchie BVH bude postavena nad primitivy (nejčastěji trojúhelníky) jednotlivých objektů. Obě hierarchie budou velice podobné, budou mít odlišné pouze listy. V listech prní úrovně budou uložený objekty a s nimi i odkazy na hierarchie druhé úrovně. V listech druhé úrovně budou uloženy přimo jednotlivá primitiva, ze kterých je objekt složen.
2.1.5
Stavba BVH
Stavět BVH strom je možné několika způsoby, shora-dolů, od spoda nebo vkládáním, viz obrázek 2.7. Všechny metody mají své výhody i nevýhody. Metoda vkládáním není pro stavbu BVH až tak bězná, ale to neznamená, že výsledný strom by byl špatně vyvážený
2.1. DETEKCE KOLIZÍ
11
Obrázek 2.7: Dvě možné varianty stavby BVH.
nebo jeho cena dotazu příliž vysoká. Důvod je spíše v horší implementaci. Metoda se více využije, když se v průběhu času může počet objektů měnit. Metoda stavby shora dolů se snadno navrhuje pomocí rekurzivní metody. Na počátku je množina objektů, pro které se BVH staví, a metoda vrátí kořen BVH postaveného nad těmito objekty. Stavba probíhá tak, že pokud množina obsahuje více než jeden objekt, nebo pokud není řečeno jinak, rozdělí objekty na dvě podmnožiny a na tyto podmnožiny zavolá rekurzivně sama sebe. To, co jí metody vrátí, prohlásí za potomky nového uzlu, a ten vrátí. Jestliže množina obsahuje pouze jeden objekt, metoda vytvoří z tohoto objektu list, a ten vrátí. Při této stavbě je velice důležité, jak se bude množina objektů dělit na podmnožiny. Teoreticky je možné množinu o n prvcích rozdělit do dvou neprázdných podmnožin 2n−1 − 1 způsoby. Ale ani zdaleka ne všechny způsoby dosáhnou dobrého rozdělení množiny. Většinou se volí rozdělení podle některé řezné roviny. To je sice jednoduché na implementaci, ale ne vždy nám zaručí, že objekty budou rovnoměrně rozděleny na dvě poloviny. Někdy se může stát, že všechny řezné roviny budou procházet některým objektem, a pak musí jeden objekt být v obou podmnožinách, a to není žádoucí jev. Existuje mnoho dalších způsobů rozdělování objektů, které dávají lepší výsledky, ale za cenu složitější implementace a delší doby výpočtu. Rozdělení objektů je možné optimalizovat použitím jednoho z následujících kritérií: 1. Minimalizace součtu objemů potomků. Tím získáme rozdělení objektů, které zaujímá
12
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
kromě objektů i nejmenší část prázdného prostoru kolem nich. Tím minimalizujeme falešné pozitivní testy průniku obálek. 2. Minimalizace objemu největšího potomka. V předchozím případě může dojít k rozdělení, kdy jeden potomek je výrazně větší něz ostatní. Tím se stává strom hodně nevyváženým. Pokud rozdělujeme tak, aby největší potomek měl minimální objem, pak je BVH vyváženější. 3. Minimalizace překrytí potomků. Jestliže potomci jsou sice nejmenší možní, ale obsahují zároveň i velké překrytí mezi sebou, pak dochází k tomu, že se zbytečně prochází více potomků. Pokud minimalizujeme toto překrytí, minimalizujeme i možné procházení více potomků. 4. Maximalizace mezery mezi potomky. I když potomci neobsahují žádné překrytí, tak jejich větší rozestupy ještě více minimalizují procházení více potomků současně. 5. Kombinace předchozích. Kritéria pro rozdělování je možné různě kombinovat pro dosažení optimálního výkonu.
2.1.6
Přestavba BVH
V případě dynamické scény je potřeba BVH po každém pohybu jakéhokoli objektu přestavět, aby BVH vždy bylo korespondující s aktuálním světem. BVH je možné buď postavit úplně znovu, nebo je možné BVH jen modifikovat. Existuje spousta prací, které se zabývají tímto problémem, například [10], ale většina algoritmů pro přestavbu BVH je poměrně složitá.
2.1.7
Traverzace stromem
Traverzace stromem by se dala rodělit na dva hlavní přístupy, informované a neinformované prohledávání. Neinformované prohledávání se dále dá dělit na dvě hlavní skupiny, prohledávání do hloubky (DFS) a prohledávání do šířky (BFS). DFS nejprve prohledává strom až do listů, a až potom se vrací zpět k uzlům na vyšší úrovni. Oproti tomu BFS prohledává strom po úrovních. Neinformované prohledávání traverzuje strom pouze na základě jeho struktury, nezajímá se o vlastní data v uzlech. Na druhé straně informované prohledávaní traverzuje strom na základě dat uložených ve stromě. Jedním představitelem takové metody je například hladový algoritmus. Tato metoda expanduje uzly na základě hodnotící funkce. Uzel, který má největší potenciál uspěchu daný hodnotící funkcí, bude expandován. V praxi se používá často neinformované prohledávání, nebo hladový algoritmus s hodnotící funkcí danou například objemem potomků nebo hloubkou podstromu potomků. Jenoduché DFS prohledávání je možné zapsat do několika málo řádků pseudokódu. Mějme dva BVH stromy a jejich kořeny označme Q1 a Q2 . Traverzace stromů postupuje rekurzivním sestupem, jestliže dochází ke kolizi mezi Q1 a Q2 , expanduje se jeden z uzlů a jeho potomky postupně označíme Q1 nebo Q2 , podle toho, který z uzlů jsme expandovali, a opět testujeme. Expanze pokračuje, dokud jsou obálky uzlů v kolizní pozici a dokud je uzly možné expandovat. Výběr uzlu pro expanzi je zde jednoduchý, expanduje se vždy uzel prvního stromu, takže se pokračuje vždy, když je to možné, do leva. Jakmile expanzí dojdeme až do listů stromu, a i ty jsou v kolizní pozici, přejdeme k testu jednotlivých primitiv uložených
2.2. FYZIKÁLNÍ ENGINE
13
v listech BVH stromu. Z postupu je jasné, že ve vnitřním uzlu BVH stromu je nutné znát pouze obálku, ale v listech je nutné spolu s obálkou znát přímo i pozice jednotlivých primitiv v obálce.
bool Collide(Q_1, Q_2) { bool bCollision = false; if (Q_1 Intersects Q_2) { if (Q_1 IS NOT LEAF) { bCollision = bCollision bCollision = bCollision } else if (Q_2 IS NOT LEAF) { bCollision = bCollision bCollision = bCollision } else { bCollision = bCollision } } return bCollision }
OR Collide(Q_1.LeftNode, Q_2) OR Collide(Q_1.RightNode, Q_2)
OR Collide(Q_1, Q_2.LeftNode) OR Collide(Q_1, Q_2.RightNode)
OR (Q_1.Primitive
Intersects
Q_2.Primitive)
Rekurzivní postup je možné a doporučené modifikovat na traverzaci s použitím zásobníku, který je rychlejší než rekurze.
2.2
Fyzikální engine
Fyzikální engine je software, který provádí simulace jednoduchých fyzikálních jevů, jako například dynamiky tuhých i měkkých těles nebo dymiky kapalin. Podle vstupních informací o objektech (rozměry, hustota, tvrdost, drsnost povrchu a další) vypočítává jejich chování v prostoru a čase. Jednoduchá simulace tuhých těles, dále již jen těles, se řídí druhým Newtonovým zákonem síly. Jestliže na těleso působí síla, pak se těleso pohybuje se zrychlením, které je přímo úměrné působící síle a nepřímo úměrné hmotnosti tělesa. Těleso je určeno pozicí těžiště t, orientací v prostoru a rychlostí. Rychlost se dá rozdělit na složky translační (lineární) ~v (t) a rotační (angulární) ω ~ (t). Celková rychlost se vypočítá ze složek jako v~p (t) = ~v (t) + ω ~ (t) × r~P (t),
14
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
Obrázek 2.8: Ukázka z fyzikálního enginu Havok.
kde v~p (t) je celková rychlost bodu P a r~P (t) je polohový vektor bodu P [13]. Známe-li tedy pozice a rotace objektů v prostoru, jejich celkové rychlosti a všechny síly na ně působící v čase t, jsme schopni přesně spočítat pozice a rotace objektů a jejich nové celkové rychlosti v čase t + 1 z pohybové rovnice. Tato rovnice vychází z již zmíněného Newtonova zákona F~ (t) = m~a(t). F~ (t) je výslednice sil působících na těleso, m je hmotnost tělesa a ~a(t) je moment setrvačnosti. Moment setrvačnosti se dá napsat jako první derivace rychlosti podle času ~v˙ (t), jejím dosazením dostáváme vztah pro změnu lineární rychlosti tělesa F~ (t) ~v˙ (t) = . m Z nové rychlosti jsme pak schopni spočítat novou pozici objektu podle rovnice ~x˙ (t) = ~v˙ (t), kde ~x˙ (t) je změna polohy tělesa v závislosti na čase. Fyzikální engine se nejčastěji používá v herním nebo filmovém průmyslu, pro navození představy realného prostředí. Další možné využití je například vědecká činnost, simulace takových scénářů, které buď v reálném prostředí zatím provádět neumíme, nebo je to příliš drahé. Fyzikální enginy nám mohou přiblížit jevy, které v laboratorních podmínkách není možné provádět. Pro vědeckou činnost je fyzikální engine úzce profilovaný, aby simulace byla co nejpřesnější. Z příkladu použití vychází hlavní rozdělení na simulace v reálném čase a na simulace s vysokou přesností. V herním průmyslu, kde rychlost, v jaké se děj odehrává, je velmi
2.2. FYZIKÁLNÍ ENGINE
15
vysoká, je možné simulace počítat s mnohem menší přesností, než u vědeckých projektů, kde je hlavním faktorem přesnost simulace. Tam je možné si na výsledek počkat. Další velký rozdíl mezi fyzikálními enginy je v jejich zaměření. Engine pro herní průmysl má obvykle mnoho fyzikálních jevů, se kterými umí pracovat a simulovat je. Naopak engine s vysokou přesností je obvykle přesně cílen na konkrétní fyzikální obor, například dynamika kapalin, astro fyzika nebo deformovatelné objekty. Enginy, které jsou zaměřeny na herní průmysl, také nejsou tak náročné na výkon počítače a jejich vývoj není tak obtížný, proto některé takové enginy vznikají jako open-source projekty, které jsou volně k bezplatnému použití. Oproti tomu vývoj vysoce přesných enginů je velmi náročný a takové enginy stojí značné finanční přostředky. Dále se již budu zabývat pouze enginy zaměřené na herní průmysl. Fyzikálních enginů pro herní průmysl existuje celá řada, daly by se rozdělit do několika kategorií. Komerční nebo volně dostupné, platformově závislé a nezávislé, speciální nebo obecné. Pro potřeby tohoto projektu bylo nutné, aby engine byl volně šiřitelný pod nějakou licencí typu GNU nebo BSD a byl platformově nezávislý. Dále je potřeba, aby engine byl co nejvíce univerzální, použitelný v mnoha různých situacích, které mohou nastat. Další již ne nutnou podmínkou, ale hodnotícím kritériem, je rychlost výpočtů a stabilita enginu. Pro porovnání vlastností jsem vybral zástupce enginů ze všech zmíněných kategorií.
2.2.1
Bullet
Bullet je zástupce profesionálního open-source projektu, který je distribuován bod licencí ZLib. Knihovna je napsána v C++, je vícevláknová a multi-platformní, lze ji tedy využít nejen na klasickém PC pod Windows nebo LINUX, ale například i na herních konzolích Playstation 3, Xbox 360, nebo Wii. Obsahuje detekce kolizí nejen všech základních primitiv, ale i konkávní a konvexní sítě trojúhelníků. Má velmi rychlý a stabilní rešič dynamiky pevných částí a dynamiky vozidel. Součástí knihovny je i podpora měkkých látek jako například oblečení nebo provazy a také podpora deformovatelných objemů s obousměrnou interakcí s pevnými tělesy. Dále nabízí plug-in do systémů Maya, Blender a Cinema 4D. Knihovna je hodně využívaná vývojáři her pro herní konzole pro svou rychlost a stabilitu. V poslední době se využívá i ve filmovém průmyslu, například aktuální film „2012“ využívá tuto knihovnu pro simulace chování pevných těles[16].
2.2.2
ODE
16
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
Dalším zástupcem open-source projektu je ODE (Open Dynamics Engine)[8]. Velmi oblíbená knihovna pro svou jednoduchost a rychlost. Knihovna byla původně napsána pro osobní účely autora, ale začala být pro svou jednoduchost a obecnost velmi žádanou. Knihovna je platformě nezávislá a původně byla napsána v jazyce C, poté bylo API přepsáno do C++. Knihovna je volně distribuována pod BSD nebo GNU licencí. Obsahuje detekce kolizí pro všechna základní primitiva. Podporuje pouze dynamiku pevných těles. Původní zaměření knihovny bylo převážně na strojírenství, ale v současné době podporuje i dynamiku vozidel. Hlavní výhodou této knihovny je i fakt, že je možné ignorovat vestavěnou detekci kolizí a provádět detekci vlastní. Simulace není tak přesná jako v některých jiných projektech, ale je velmi rychlá a stabilní.
2.2.3
nVidia PhysX
Plně komerčním projektem původně od firmy Ageia, nedávno převzatá firmou nVidia, je PhysX. Původně to byla knihovna pevně spojená se speciální grafickou kartou pro výpočty fyzikálních jevů. Dnes již knihovna pro svůj chod nepotřebuje speciální hardware, ale stále je silně spojena s grafickou kartou, proto je i velice výkonná a nabízí jednu z nejlepších simulací fyzikálních jevů dneška, to je dáno především tím, že původní vývojáři byli přední matematici a fyzici. PhysX podporují grafické karty nVidia GeForce serie 8 a vyšší, grafické karty jiných výrobců nejsou podporovány. Je psána v C++ a je vícevláknová. Umí simulovat jak pevná, tak i měkká tělesa. Její kolizní systém obsahuje všechna primitiva a například i výškovou mapu. Jako jedna z mála knihoven se věnuje i simulaci tekutin. Je využívána především v herním průmyslu pro velmi reálné a rychlé simulace fyzikálních jevů. Například hra pro PC i herní konzole "Unreal Tournament 3", nebo "Batman: Arkham Asylum"[14].
2.2.4
Havok
Druhým zástupcem komerčního projektu je Havok. Existuje i verze zcela zdarma, ale pouze pro akademické nebo nekomerční účely. Knihovna je na velmi vysoké úrovni a říká o sobě, že je jedničkou na trhu. Těží hodně ze spolupráce s firmou Intel. Využívaná je opět hlavně v herním průmyslu. Její výhodou oproti PhysX je hardwarová nezávislost. Je
2.2. FYZIKÁLNÍ ENGINE
17
multi-platformní a vícevláknová. Detekce kolizí podporuje všechny primitiva a měkká tělesa. Knihovna obsahuje i velmi dobré ladící nástroje. Je i v podobě pluginu do modeláře Autodesk 3D Studio MAX. I Havok je, stejně jako nVidia PhysX, často využívána v herním průmyslu, například hra pro herní konzole PS3 "Just Cause 2"nebo "Bio Shock 2"[15].
2.2.5
Shrnutí
Projekt VRUT je vyvíjen ve spolupráci a pro společnost Škoda Auto, takže v mé práci nemohu používat komerční projekty podléhající licencím. Tím vypadávají Nvidia PhysX i Havok. Ze zbylých dvou projektů jsem si vybral ODE. Jeho výhody jsou hlavně jednoduchá integrace, stabilní a robustní rešič, dobrá dokumentace a v neposlední řadě i určité zkušenosti s tímto projektem na naší katedře. Mnoho mých kolegů ODE používá, nebo jej někdy v minulosti použilo. Díky tomu bude pro mne snazší řešit případné problémy s knihovnami.
2.2.6
Typy vazeb
Různé fyzikální enginy obsahují různé druhy vazeb pro simulovaní vztahů mezi objekty. Tyto vazby působí jako externí síly, které udržují dané objekty na určitých místech nebo v daném vztahu k nějakému bodu ve světě. Typů vazeb je celá řada, ale základních typů je jen několik. Ty složitější se pak dají těmito základními nakombinovat jejich spojením. Dále stručně popíši vlastnosti a funkce některých základních typů vazeb. Obrázky vazeb byly převzaty z manuálu ODE. [8]
2.2.7
Kloub
Obrázek 2.9: Vazba typu kloub.
Definuje bod mezi objekty, který se oba objekty snaží udržet pohromadě. Je možná rotace v jakékoli ose kolem tohoto bodu. Objekty ale zůstávají stále ve stejné vzdálenosti od bodu. Této vazbě není možné nastavit žádné limity pro rotace kolem osy. Touto vazbou je možné simulovat do jisté míry například lidský kyčelní kloub nebo zpětná zrcátka v autě.
18
2.2.8
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
Pant
Obrázek 2.10: Vazba typu pant.
Definuje bod mezi objekty, který se objekty snaží udržet pohromadě, stejně jako u vazby typu kloub, ale u této vazby je možná rotace pouze kolem právě jedné a přesně definované osy. Této vazbě je možné definovat maximální i minimální výchylku od původního úhlu a dále je možné nastavit chování pantu při dosažení této hodnoty. Zdali se bude vracet zpět, nebo setrvá v limitní pozici. Tato vazba se hodí pro simulování například lidského kolene nebo třeba dveří automobilu, ale možností použití této vazby je celá řada.
2.2.9
Píst
Definuje osu, po které se objekty mohou vzdalovat a přibližovat. Není dovolena žádná rotace v žádné ose, pouze změna vzdálenosti objektů. Opět je možné definovat maximální a minimální výchylky od původní pozice a chování pístu při dosažení této pozice. Pístem je možné simulovat například tlumiče automobilu nebo nějaké teleskopické rameno.
2.2. FYZIKÁLNÍ ENGINE
19
Obrázek 2.11: Vazba typu píst.
20
KAPITOLA 2. ANALÝZA A NÁVRH ŘEŠENÍ
Kapitola 3
Realizace Realizace projektu spočívá ve vytvoření dvou modulů do aplikace VRUT. Jeden modul se zabývá detekcí kolizí, spravuje si aktuální verzi scény a v určené době testuje scénu na přítomnost kolize. Při zjištění kolize na ni reaguje zadaným způsobem. Druhý modul integruje do systému knihovny ODE pro výpočet fyzikálně přesných dynamických jevů. Dokáže reagovat na zprávy od modulu detekce kolizí a umí přidat do scény gravitaci. V této kapitole podrobně popíši implementované metody a řešení nestandartních situací a požadavků. U každého modulu je také stručný popis jeho tříd a objektů, se kterými se pracuje.
3.1
Modul detekce kolizí
Tento modul má za úkol hledat kolize objektů ve scéně. V aplikaci VRUT se používá anglický jazyk jako primární, takže modul je tam nazván Collision_detection. Detekce by měla probíhat jak automaticky po jakékoli změně translace nebo rotace objektu ve scéně, tak i na žádost. Modul si musí udržovat aktuální BVH scény a objektů ve scéně. Z důvodu velkého množství detailních objektů, které mohou ve scéně být, by stavba hierarchií pro všechny objekty při inicializaci byla velmi časově i paměťově náročná. V praxi totiž zdaleka ne všechny objekty budou někdy opravdu v kolizi, nebo v blízkosti kolizní situace. Spousta objektů může ve scéně působit pouze jako kulisa mimo dosah pohybujících se částí scény. Stavba druhé úrovně tedy bude probíhat dynamicky za běhu aplikace. V případě detekování kolizní situace mezi listy obálek v hierarchii první úrovně, hierarchie postavené nad celými objekty, se teprve postaví hierarchie druhé úrovně nad oběma objekty. Tyto hierarchie se následně uloží pro další výpočty. Nicméně mohou nastat i situace, kdy je potřeba mít všechny objekty a jejich BVH předpočítané pro plynulý chod aplikace. Stavba BVH pro velmi složité objekty může zabrat i několik sekund. Proto je implementovaná i funkce načtení všech objektů ve scéně, která je volána pomocí GUI. BVH pro objekty ve scéně je již v jádře projektu VRUT implementované, takže tohoto budu co nejvíce využívat. Drobné změny budou pouze pro BVH jednotlivých objektů, například listy BVH budou u druhé úrovně obsahovat přímo primitiva, ze kterých je objekt složen. BVH v jádře je stavěno metodou shora dolů, a proto jsem i v mém modulu pro stavbu stromu druhé úrovně použil metodu shora dolů. Pro ukončení expanze uzlu mám podmínku maximálního počtu trojúhelníků v uzlu. Pokud je tedy jejich počet menší, uzel prohlásím
21
22
KAPITOLA 3. REALIZACE
za list stromu. Stavbu stromu začínám triangulací celého objektu. Pro všechny trojúhelníky poté spočítám inkrementální metodou obálku. Metoda spočívá v postupném přidávání trojúhelníků do obálky inicializované na minimální velikost. Přidáváním trojúhelníku se vždy obálka rozšíří maximálně na takovou velikost, aby obsahovala všechny již přidané, plus aktuálně přidávaný. Tím je zajištěna minimální velikost obálky. Poté jestliže počet trojúhelníků není menší než prahová hodnota, trojúhelníky rozdělím na dvě poloviny, z nich postavím dva nové uzly stromu a přidám je jako potomky aktuálního uzlu. Rozdělení trojúhelníků na dvě poloviny provádím nalezením nejvhodnější řezné roviny, paralelní se souřadnicovým systémem. Nejvhodnější rovinu určím jako nejdelší souřadnici diagonály obálky, dělím tedy nejdelší rozměr obálky. Bod řezu pak zvolím jednoduše ve středu tohoto rozměru, takže se mi obálka rozdělí na dvě stejné poloviny. Všechny trojúhelníky pak rozděluji podle toho, jestli střed trojúhelníku leží na kladné, nebo záporné straně řezné roviny. Z popisu je jasné, že obálky mohou mít určitý překryv. Jestliže se při použití této řezné roviny trojúhelníky nerozdělí, použiji jinou řeznou rovinu, druhou nejdelší v pořadí. Jestliže ani jednou ze tří možných řezných rovin (paralelní se souřadným systémem) nedojde k rozdělení trojúhelníků, rozdělím je pouze podle pořadí. Toto řešení je pouze záchranné, aby nedocházelo k selhání při stavbě stromu, a nemělo by k němu nikdy docházet, protože výsledné rozdělení bude s velkou pravděbodobností velmi nevhodné. Při přestavbě BVH po nějaké rotaci nebo translaci objektu opět využívám to, co je implementované v jádře VRUTu. Jádro staví znovu jen tu část BVH, která byla ovlivněna změnou pozice nebo rotace objektu. Proto jsem se rozhodl tohoto využít. Zbývá tedy navrhnout algoritmus pro přestavbu BVH druhé úrovně samotných objektů. Tato práce předpokládá nedeformovatelné objekty, takže změnit pozici nebo rotaci může pouze celý objekt, nikoli pouze některá jeho část. Proto jsem se rozhodl zvolit metodu spočívající pouze v přepočítání pozice a velikosti jednotlivých uzlů a přepočítání pozic jednotlivých trojúhelníků v listech stromu.
3.1.1
Výpočet parametrů kolize
V zadání této práce je požadavek na výpočet některých běžných parametrů kolize, jako jsou objekty, které jsou v kolizní pozici. Objekty jsou jednoznačně identifikovatelné pomocí jejich ID, takže modul bude vracet dvojice ID objektů, které jsou v kolizi. Další parametry jsou střed kolize v prostoru, dán bodem ve světovém souřadném systému, rádius kolize, normála oddělující roviny a hloubka průniku objektů. Výpočet všech těchto parametrů je časově náročný, proto výpočet bude probíhat pouze na vyžádání uživatele systému. Bude možné počítat pouze některé parametry, tedy ty, co budou důležité pro součásti, které budou přijímat události o nastalé kolizi. Střed kolize v prostoru Střed kolize je dán bodem ve světovém souřadném systému. Pro výpočet tohoto bodu je nutné, abych již při testování kolize počítal délku hranice kolidujících trojúhelníků. Tím získám celou křivku hranice průniku objektů, a z této křivky jsem schopný váženým průměrem středů úseků křivky získat jednu pozici udávající střed průniku objektů. Jako váhu pro jednotlivé středy úseků používám délku daného úseku. Tento algoritmus se mi jeví jako nejlepší. Kdybych nebral v úvahu délku úseků, mohl by být výsledek vychýlený k menším úsekům. Složitost výpočtu je rovna O(n), kde n je počet trojúhelníků v kolizi.
3.1. MODUL DETEKCE KOLIZÍ
23
Obrázek 3.1: Grafické znázornění parametrů kolize. Zleva pozice kolize, normála oddělující roviny, poloměr kolize a hloubka průniku objektů.
Poloměr kolize Poloměr kolize je daný kladným číslem ve světových souřadnicích. Definuje vzdálenost nejvzdálenějšího bodu kolize od středu kolize. Poloměr kolize vypočítám inkrementální metodou. Pro každý trojúhelník, který je v kolizi, vypočítám maximální vzdálenost od již vypočteného středu kolize. Maximální vzdálenost je vždy jeden z vrcholů trojúhelníku, stačí tedy počítat vzdálenost středu kolize ke všem vrcholům všech trojúhelníků a největší taková vzdálenost je poloměr kolize. Složitost výpočtu je rovna O(n), kde n je počet trojúhelníků v kolizi. Normála oddělující roviny Oddělující rovina je definována jako rovina, která při proložení středem kolize odděluje kolidující trojúhelníky obou objektů od nekolidujících. Normála roviny vždy směřuje k prvnímu z dvou objektů. Výpočet provádím randomizovaným algoritmem. Nejprve inicializuji normálu oddělující roviny na nulový vektor. Nyní náhodně vybírám trojice bodů ze všech bodů na hranici průniku. Jestliže je vybraná trojice bodů různá, vypočítám z ní normálu roviny definovanou těmito body a tuto normálu zprůměruji s normálou oddělující roviny. Toto opakuji n-krát,
24
KAPITOLA 3. REALIZACE
kde n je zadaná konstanta pohybující se v desítkách maximálně stovkách. Po výpočtu ještě musím zkontrolovat, jestli normála směřuje ke středu prvního objektu, jestliže ne, je nutné normálu invertovat. To zkontroluji jednoduše tak, že zjistím, jestli normála ze středu kolize směřuje ke středu prvního objektu. Hloubka průniku Poslední důležitý parametr kolize objektů je hloubka průniku. Je to zároveň také nejsložitější problém, kterým se zabývají výzkumné týmy po celém světě. Po prostudování různých algoritmů jsem se rozhodl pro implementaci dvou různých algoritmů. První algoritmus problém velmi zjednodušuje. Hloubku průniku vezmu jako nejmenší vzdálenost od středu kolize k bodu, ve kterém normála oddělující roviny, proložená tímto bodem, tvoří podpůrnou rovinu. Toto zjednodušení velmi zrychlí výpočet, ale výsledná hodnota průniku často nemusí být správná. Složitost tohoto algortimu je rovna O(n). Druhý algoritmus je založen na zjednodušeném inkrementálním algoritmu nazvaném "Deep Dual Space"[7]. Definujeme podpůrnou rovinu objektu A jako rovinu, která prochází minimálně jedním bodem objektu A, a všechny ostatní body leží buď v této rovině, nebo pouze na jedné straně roviny. Nechť Za b je množina všech dvojic rovin (Z1 , Z2 ), kde Z1 je podpůrná rovina objektu A a Z2 je podpůrná rovina objektu B a jejich normály směřují na opačnou stranu. Pak hloubka průniku je dána jako ρ(A, B) = min(Z1 ,Z2 )∈ZAB (d(Z1 , Z2 )), kde d(Z1 , Z2 ) je vzdálenost mezi rovinami Z1 a Z2 . Tento algoritmus prochází všechny podpůrné roviny, takže složitost algoritmu, bez použití nějaké heuristiky, má složitost O((n + m)2 ). Dále test, jestli je daná rovina podpůrná, má při použití hrubé síly složitost také O((n + m)2 ), kde n je počet bodů prvního kolizního objektu a m je počet bodů druhého objektu. V mé práci jsem tento algoritmus zjednodušil tak, že beru v potaz pouze část objektu, která je v kolizi. A i test, zdali je rovina podpůrná, testuji pouze v okruhu blízké kolizi. Definuji tedy k n, m, pak počet možných podpůrných rovin je O(k 2 ) a i test podpůrnosti je O(k 2 ). Toto zjednodušení ale může mít za následek nepřesný výpočet, který ale vynahrazuje mnohem jednoduší implementace a rychlost výpočtu i s použitím hrubé sily. Hrubou sílu zde mohu použít, protože k bude vždy v řádech maximálně desítek. Ve vlastní implementaci je k dáno počtem bodů všech trojúhelníků v kolizi, kterou označím jako b. Nejprve inicializuji pole všech trojúhelníků S, které jsou v kolizi a hodnotu hloubky průniku pd = inf. Do pole S zařadím všechny trojúhelníky v kolizi střídavě z obou objektů. Inkrementální algoritmus pak prochází následující kroky. 1. Vezmi trojúhelník ti z S na i-té pozici. Inicializuj j = 1 je-li i sudé a j = 0 je-li i liché. 2. Vezmi trojúhelník tj z S na j-té pozici. Pro všechny jeho vrcholy v opakuj. Otestuj, zdali je rovina definovaná normálou ti a bodem v podpůrnou pro všechny ostatní trojúhelníku z S incidující se stejným objektem jako v. Jestliže ano, vypočítej vzdálenost mezi touto rovinou a rovinou definovanou ti . Jestliže tato vzdálenost je menší než současná pd, přepiš pd pravě vypočtenou vzdáleností. 3. Jestliže j < b, pak j + + a pokračuj bodem 2.
3.1. MODUL DETEKCE KOLIZÍ
25
4. Jestliže i < b, pak i + + a pokračuj bodem 1. 5. Hodnota pd je výsledná hodnota hloubky průniku. Varianta výpočtu hloubky průniku bude volitelná uživatelem, aby si mohl zvolit, jestli chce rychlejší, nebo přesnější výpočet.
3.1.2
Reakce na zjištěnou kolizi
Kdykoli modul zjistí existenci kolize mezi objekty ve scéně, je nutné informovat ostatní součásti o této události. K tomu slouží jádro VRUTu a správce událostí. Moduly nebo jiné součásti, které chtějí být informovány, se zaregistrují v jádře k odebírání událostí o kolizi. Modul při zjištění kolize vytvoří novou událost o kolizi ve scéně. Vyplní všechny spočtené parametry kolize a odešle do jádra s nejvyšší prioritou, aby případní příjemci těchto zpráv byli informováni co nejdříve. To, co s událostí pak moduly a součásti udělají, již modul detekce kolizí neovlivňuje.
Obrázek 3.2: Životní cyklus modulu collision_detection.
3.1.3
Udržení v nekolizní pozici
Požadavek na detekci kolizí byla i schopnost udržovat objekty v nekolizních pozicích. Tento problém je poměrně složitý vzhledem k tomu, že VRUT je koncipován jako asynchronní. Každý modul je spuštěn ve svém vlastním vlákně, a proto při řešení tohoto problému nastávají problémy se synchronizací. Ve spolupráci s vedoucím této práce panem Bittnerem jsme
26
KAPITOLA 3. REALIZACE
navrhli 2 řešení. První řešení je zaměřeno na zachování asynchronnosti systému. Spočívá v implementaci zaznamenávání historie všech transformací objektů ve scéně. Jednotlivými transformacemi se zároveň celá scéna dá verzovat, a to je důležité pro udržování objektů v nekolizních pozicích. Modul detekce kolizí provádí testy po každé transformaci jakéhokoli objektu, ale před tímto testem si uloží aktuální verzi scény, a obnoví všechny pozice objektů ve scéně. Když žádná kolize ve scéně nenastala, modul si uloží aktuální verzi scény jako poslední nekolizní. Při zjištění kolize se z historie transformací najde poslední transformace objektů, které jsou v kolizi, a s pomocí těchto transformací se pak objekty transformují zpět do nekolizních pozic. Toto řešení nemá žádný vliv na rychlost a robustnost systému, ale její velkou nevýhodou je poskakování objektů na hranici kolize. Každý objekt se totiž nejprve vykreslí v kolizní pozici, a pak se přetransformuje do pozice nekolizní. To může působit trhaným a nereálným pohybem. Tento fragment je možné minimalizovat minimálními transformacemi objektů. Čím transformace budou menší, tím bude i přeskok menší a neznatelnější. Druhé navrhnuté řešení má za úkol eliminovat poskakování objektů. Toho je docíleno použitím synchronizace. Každá transformace je provedena a vykreslena pouze pokud je scéna po transformaci nekolizní. Před aplikací transformace se volá metoda modulu detekce kolizí, která testuje scénu na kolize. Jestliže je zjištěna kolize, transformace není aplikována na graf scény, a tím pádem se ani objekt nevykresluje v kolizní pozici. Tím se sice eliminuje poskakování objektů, ale za velké negativum považuji závislost rychlosti systému na detekci kolizí. Pro rozsáhlejší a složité scény je možné, že toto řešení nebude použitelné.
3.1.4
Přehled tříd
Modul je dědí ze třídy SceneM odule, aby měl přístup ke scéně a mohl s ní nezávisle pracovat. Rodič zajišťuje přidělení scény a přistupu do ní. SceneM odule je potomkem třídy M odule, která zajišťuje správné zavedení modulu do aplikace, její běh a komunikaci s jádrem. Obsahuje metody pro zasílání zpráv jádru. Implementace modulu je rozdělena na několik částí do souborů podle toho, čím se zabývají. Hlavní prvky modulu jako je komunikace, výpočet kolizí, uživatelské rozhraní a podobné jsou v hlavním souboru collision_detection.h. Část, která se zabývá matematickými testy primitiv na kolize nebo výpočty vzdáleností primitiv, je v samostatném souboru collision_detectors.h. Poslední částí modulu je část zabývající se uložením, stavbou a prácí s BVH nad primitivy objektů, je v souborech collisionDetection_BVH.h a collisionDetection_BVHNode.h. CollisionReport CollisionReport je struktura obsahující všechny potřebné informace o nastalé kolizi. Obsahuje ID uzlů, které jsou v kolizi, a obsahuje pole všech parametrů kolize, jak je popsáno v odstavci 3.1.1. Pokud uživatel nebude chtít vypočítat podrobné parametry kolize, zůstanou daná pole prázdná. Jednotlivá pole mají tolik položek, na kolik oblastí je kolize rozdělena. Navíc tato struktura obsahuje výčet trojúhelníků, které jsou v kolizi. To bude dále možné použít například pro zvýraznění místa kolize uživateli barvou. Tato struktura je definovaná v jádře systému, protože se posílá ve zprávě o nastalé kolizi. Collision_Detector_IFace Interface, který musí implementovat každá třída, která je použita pro testy kolizí primitiv. Interface má jedinou virtuální metodu FindCollision() a
3.1. MODUL DETEKCE KOLIZÍ
27
její parametry jsou dva ukazatele na objekty a ukazatel na objekt CollisionReport, kam se zapisuje výsledek testu. Objekty vstupující do metody mohou být jakékoli. Každá třída, která tento interface implementuje, si musí objekty přetypovat na takové, které očekává, a zkontrolovat jejich správnost. Takhle je možné implementovat více různých typů obálek a pro každý typ obálky mít třídu pro testování kolizí. CollisionDetector Při návrhu testů různých primitiv byl použit návrhový vzor "Factory". Třída CollisionDetector působí jako "továrna"na detektory kolizí. Má statickou metodu, která při zadání typu primitiv vrátí vhodný detector, který umí s těmito primitivy pracovat. Třída obsahuje i přímo metodu na zjištění kolize pro dva objekty při zadaném typu primitiv. Implementovány jsou zatím jen primitiva AABB, trojúhelník a trojúhelník s definovanou minimální vzdáleností. Další primitiva se mohou dodat s příslušnou třídou pro zajištění jejich testů. V budoucnu by bylo dobré implementovat lepší typy obálek jako například objektově orientovaný kvádr, který by mohl v určitých případech dosahovat lepších výsledků než samotný AABB. Collision_detector_AABB Jediná implementovaná podpora obálek je typu AABB a pro ni je vytvořena třída Collision_detector_AABB, která implementuje interface z odstavce 3.1.4. Pro test kolize je použit algoritmus SAT, viz sec:SAT. Collision_detector_Triangles Pro detekci kolize mezi dvěma trojúhelníky slouží třída Collision_detector_Triangles, která také implementuje opět interface 3.1.4. Test kolize je založen na tvrzení, že dva trojúhelníky jsou v kolizi právě tehdy, když jedna hrana z obou trojúhelníků protíná ten druhý, nebo dvě hrany z jednoho protínají druhý [9]. Collision_detector_Triangles_Distance Tato třída slouží pro test kolize mezi dvěma trojúhelníky s minimální vzdáleností. Třída v metodě FindCollision() zjistí minimální vzdálenost trojúhelníků a vyplní ji do pole f SqueredSeparationDistance u CollisionReport. Nejbližší body mohou na trojúhelnících ležet buď na jedné hraně a ploše druhého, to je případ kdy normály trojúhelníku jsou na sebe kolmé. Nebo body leží na plochách obou trojúhelníků, oba trojúhelníky jsou rovnoběžné, anebo jsou na hranách obou trojúhelníků, to jsou všechny ostatní případy. Zkontrolujeme tedy všechny možné varianty, kterých je právě 15 (9 pro test hrana-hrana a 6 pro test hranaplocha). Třída jako jediná mimo implementace interfacu obsahuje i další metody pro určení vzdálenosti bodu a trojúhelníku a vzdálenosti bodu a roviny. CollisionDetection_BVHNode Toto je třída, ze které se staví hierarchie obálek primitiv pro objekty ve scéně. Představuje jeden uzel stromu. Třída dědí ze třídy BVHNode obsažené v jádře systému. Uzel obsahuje odkaz na dva potomky, a jestliže se jedná o list stromu, obsahuje množinu trojúhelníků původního objektu. Dále obsahuje obálku AABB a současně typu koule.
28
KAPITOLA 3. REALIZACE
CollisionDetection_BVH Pro stavbu udržování hierarchie obálek pro jednotlivé objekty ve scéně slouží třída CollisionDetection_BV H. Obsahuje metody pro stavbu, obnovu i zrušení hierarchie obálek. Má odkaz na kořen stromu hierarchie obálek, ze kterého je možné se dostat na všechny uzly.
3.2
Modul výpočtu dynamiky
V aplikaci VRUT se modul nazývá Dynamics. Knihovny ODE jsou k dispozici jako zdrojové kódy ke stažení z webové adresy projektu[8]. Zdrojové kódy se přeloží na požadované platformě a výsledkem kompilace je jedna statická knihovna.
3.2.1
Integrace do VRUTu
Přidáním knihovny ODE do VRUTu integrace do systému nekončí. Je nutné, aby VRUT dokázal výsledky simulace správně prezentovat a aby celý systém spolupracoval. První problém je načíst do ODE objekty, pro které má simulace probíhat. Druhým krokem pak je vrátit výsledek simulačního kroku zpět do systému a prezentovat ho uživateli.
3.2.2
Přidání knihoven ODE
V současné době bude na knihovně ODE závislý ještě jeden jiný modul vyvíjený paralelně s tímto, takže je žádoucí, aby oba moduly mohly využívat stejné knihovny a nedocházelo k duplicitám. Knihovna tedy bude uložena v centrálním úložišti externích knihoven v jádře VRUTu. Všechny moduly využívající ODE pak budou odkazovat na jedno místo. Bude to ovšem zatěžovat jádro, které i bez použití těchto modulů bude obsahovat knihovnu ODE.
3.2.3
Načtení objektů
Načtení objektů by mělo probíhat co možná nejvíce automaticky. Modul by měl být po spuštění schopen provádět základní funkcionality bez dalšího nastavovaní. Pro toto bude sloužit načítání objektů pomocí dohodnuté konvence názvů objektů. Pokročilé funkce budou přístupné pokročilejším uživatelům a tyto funkce bude možné nastavit pomocí speciálního XML souboru. Struktura souboru je podrobně popsána v odstavci 6.2.1. Všechny objekty ve scéně se dají rozdělit do tří skupin ve smyslu jejich chápání pro fyzikálně přesné simulace. První skupinou jsou objekty takzvaně dynamické. Tyto objekty se mohou ve scéně pohybovat působením sil. Síly v systému mohou být buď externí (například gravitace, vítr apod.) nebo interní (kolize mezi objekty). Objekty musejí mít definovanou velikost, tvar, tvrdost, hmotnost a rozložení váhy. Tyto parametry jsou důležité pro správné výpočty kolizí a pro správný výpočet odezvy objektů na působící síly. Druhou skupinou jsou objekty takzvaně statické. Tam patří objekty, které se sice ve scéně pohybovat nebudou, ale mohou generovat nějaké síly do systému, například při kolizi těchto objektů s objekty dynamickými. Tyto objekty musejí mít definovanou pouze velikost, tvar a tvrdost. Váha zde nehraje roli, protože zde neprobíhá výpočet momentů sil. Příkladem
3.2. MODUL VÝPOČTU DYNAMIKY
29
použití takových objektů může být například prostředí, ve kterém se uživatel pohybuje. Budovy, brány, stromy a podobné objekty, které svou povahou nemohou být ovlivněny žádnými silami, které je uživatel schopen generovat. Poslední skupinou jsou objekty takzvaně neviditelné. Neviditelné proto, že pro fyzikální simulaci jsou tyto objekty opravdu neviditelné. Nepočítají se pro ně ani kolize a ani momenty sil. Přestože je uživatel může vidět, tak v simulaci figurovat nemusejí. To může být výhodné pro urychlení výpočtů. Objekty, které jsou ve velké vzdálenosti od pozorovatele, se nemusejí chovat fyzikálně tak přesně jako objekty pozorovateli blízko. Případné kolize takových objektů pozorovatel vůbec nezaregistruje a výpočetní kapacity se mohou soustředit pouze na důležité objekty.
3.2.4
Načtení objektů pomocí konvence názvů
Pro velmi snadné a na uživateli nezávislé načtení objektů jsem zvolil načtení pomocí konvence názvů objektů. Po zvolení scény uživatelem je modul automaticky informován a začne prohledávat všechny objekty. Jestliže název objektu začíná na ”d_”, pak se k němu systém bude chovat jako k dynamickému objektu. Všechny informace o tvaru objektu získá ze scény a jako tvrdost a hmotnost dosadí implicitní hodnoty. Jestliže začíná na ”x_”, pak bude objekt ignorován, bude tedy neviditelný pro systém. Všechny ostatní objekty budou načteny do systému jako statické a informace o tvaru objektu se opět získají ze scény. Pomocí konvence názvů tedy není vůbec možné nastavit a přidat do scény vazby. Toto nastavení bude přístupné pouze přes nastavovací XML soubor ve kterém bude možné nastavit i dynamické a statické objekty. Nastavení podle konvence názvů a pomocí konfiguračního souboru není možné kombinovat. Jakmile uživatel zadá načtení pomocí konfiguračního souboru, všechna doposud načtená data budou zahozena.
3.2.5
Nastavení pomocí XML souboru
Pokročilé nastavení bude možné nastavit pomocí XML souboru. XML soubor jsem zvolil pro jeho jednoduchou editaci, textovou podobu a rozšířenost. Pomocí něho bude možné nastavit načítání objektů ze scény, chování simulace a hlavně bude také možné vytvořit vazby. Toto nastavení bude nejspíše provádět zkušený uživatel. Vytvoří soubor potřebných nastavení pro různé scény a různé konfigurace stejné scény. Méně zkušený uživatel pak již bude jen načítat tato nastavení a pracovat se scénou místo zdlouhavého nastavování dynamiky.
3.2.6
Pracovní cyklus modulu
Jakmile je pro konkrétní scénu načteno nějaké nastavení, modul začne pracovat v pomyslné smyčce. V první fázi této smyčky nejprve vypočítám kolize objektů ve scéně a výsledek kolize předám jako vstupní parametry do ODE pro výpočet simulace. Dále proběhne výpočet simulace v ODE a po skončení výpočtu přetransformuji všechny objekty do nových pozic a pokračuji opět detekcí kolizí pro nový simulační krok. Jednotlivé fáze popíšu detailněji.
Před samotným simulačním krokem je nejprve nutné provézt detekci kolizí. Ta se provede buď integrovanou detekcí v ODE nebo pomocí samostatného modulu detekce kolizí implementovaného v první fázi této práce. Výsledek detekce kolizí se projeví aplikací takzvaných kontaktních bodů. Ty pak slouží v simulačním kroku pro výpočet nových pozic objektů. Kontaktní bod má celou řadu parametrů pro určení přesné reakce na kolizi. Definice kontaktního bodu vypadá následovně.
// Vlastnosti povrchu objektů // Informace o kolizi // Směr tření
Objekt typu dContactGeom se naplní informacemi o nastalé kolizi. Definuje se přesné místo kolize, hloubka průniku obou objektů a normála oddělující roviny a jednoznačně se určí objekty, které jsou v kolizi. Datové typy hodnot jsou uvedeny níže.
// Vektor normály // Hloubka průniku objektů // Identifikace objektů v kolizi
};
Tyto parametry musejí být nastaveny velmi přesně pro výpočet fyzikálně věrné simulace. Další méně důležité parametry, které spíše popisují fyzikální vlastnosti kolidujících objektů a jejich povrchů, jsou obsaženy v objektu typu dSurf aceP arameters. Definuje se typ kontaktního bodu, drsnost povrchu objektů, tvrdost objektů a odrazivost povrchu. struct dSurfaceParameters { int mode; dReal mu; dReal mu2; dReal bounce; dReal bounce_vel; dReal soft_erp; dReal soft_cfm; dReal motion1, motion2, motionN; dReal slip1, slip2;
// // // // //
Typ kontaktního bodu Koeficient tření (0...Inf) Coulombův koeficient tření Odrazivost povrchů (0...1) Minimální rychlost objektů pro efekt odrazu // Měkkost povrchů // Rychlost povrchu objektu // Skluz závislý na velikosti sil
};
3.2.8
Typ kontaktního bodu
Typy kontaktního bodu může být kombinace následujících parametrů: 1. dContactM u2 - Jestliže nastaveno, je parametr mu použit pro tření ve směru 1 a parametr mu2 použité ve směru 2. 2. dContactF Dir1 - Jestliže nastaveno, pak se bere f dir1 jako směr tření 1. Jinak je směr tření 1 vypočten jako kolmý na normálu kontaktního bodu. 3. dContactBounce - Jestliže nastaveno, pak budou objekty odrazivé a odrazivost se řídí parametrem bounce a bouncev el. 4. dContactSof tERP - Jestliže nastaveno, pak je možné nastavit "Redukci chyby měkkého odrazu"pomocí parametru sof te rp. 5. dContactSof tCF M - Jestliže nastaveno, pak je možné nastavit "Constraint force mixing"pomocí parametru sof tc f m. 6. dContactM otion1 - Jestliže nastaveno, pak povrch objektu 1 se bere jako pohyblivý nezávisle na pohybu celého objektu, jako například pohyblivé schody, a rychlost povrchu je možné nastavit parametrem motion1 ve směru tření 1. 7. dContactM otion2 - Stejné jako dContactM otion1, ale podél směru tření 2.
32
KAPITOLA 3. REALIZACE
8. dContactM otionN - Stejné jako dContactM otion1, ale podél normály. 9. dContactSlip1 - Jestliže nastaveno, pak je možné parametrem slip1 ovlivnit klouzavost povrchu podél směru tření 1. 10. dContactSlip2 - Stejné jako u dContactSlip1, jen pro směr tření 2. Poté co je kontaktní bod definován dle požadavků, zařadí se do simulace a v následujícím simulačním kroku se tyto kontaktní body zohlední při výpočtu nových pozic objektů. Po každém simulačním kroku se musejí tyto kontaktní body opět ručně vyjmout ze simulace a spočítat nové.
3.2.9
Simulační krok
Obrázek 3.4: Reakce na vzniklou kolizi produkuje sílu působící ve směru normály a její velikost závisí na hloubce průniku. Čím větší simulační krok, tím větší možná hloubka průniku a tím větší reakce na stejnou kolizi.
Knihovna ODE jako parametr simulačního kroku očekává časový interval od posledního kroku. Je nutné, aby simulační krok byl v systému prováděn po co nejmenších časových intervalech. Čím bude interval menší, tím bude simulace věrnější. Protože v případě kolize se zjistí a vyhodnotí včas. Aby simulace byla plynulá a stejně rychlá na všech scénách a na všech možných výpočetních systémech, je nutné časový krok vypočítat v závislosti na
3.2. MODUL VÝPOČTU DYNAMIKY
33
reálném čase. Po každém simulačním kroku uložím čas v milisekundách od spuštění aplikace a těsně před dalším krokem opět přečtu čas. Rozdíl těchto časů pak předám ODE, aby přesně spočetlo simulační krok. Pro případy buď velmi rozsáhlých scén, nebo pomalých výpočetních systémů, kde by mohl interval mezi simulačními kroky být příliš velký, a tím pádem simulace značně nepřesná, bylo nutné přidat do systému maximální časový krok, který může vstoupit do simulace. To může znamenat rozdíl v simulaci na pomalých výpočetních systémech a na rychlých. Simulace bude pomalejší, ale bude stále reálná. Kdybych ponechal časový krok velký, pak by simulace byla velmi nereálná. A na rozdílných systémech zcela odlišná. Knihovna ODE si po provedení simulačního kroku u všech objektů interně změní pozice a rotace, ale pro použití ve VRUTu je nutné tyto změny promítnout do scény. Knihovna ODE nám může pouze poskytnout aktuální informace o pozici ve světových souřadnicích o objektech. Abych tedy zjistili relativní transformační matici změny pozice, je nutné, abych před simulačním krokem uložil informace o pozici a rotaci pro všechny objekty. Po simulačním kroku provedu totéž ještě jednou a z transformačních matic před a po simulaci vypočtu relativní transformační matici. Tu pak můžu aplikovat na objekty ve scéně. Relativní matici získám podle vzorce R T Mr = (MiR ∗ MiT )−1 ∗ Mi+1 ∗ Mi+1 , kde Mr je hledaná relativní matice transformace objektu, MiT je matice translace v i-tém kroku simulace, MiR je matice rotace objektu v i-tém kroku.
3.2.10
Synchronizace s modulem detekce kolizí
Aplikace VRUT je navržena tak, aby jádro a moduly byly na sobě vzájemně nezávislé, a to platí i na modulech mezi sebou. Proto žádná přímá komunikace již z principu není možná. Aby mohl být u modulu dynamics použit k detekci kolizí modul collision_detection je nutné, aby všechny případné kolize byly zjištěny ještě před simulačním krokem. Kdybychom nechali oba moduly pracovat nezávisle na sobě a informace o kolizi by byly zasílány výhradně k tomu určenými zprávami, tak by výsledná simulace vůbec reálná nebyla. Mezi simulací a výsledky detekce kolizí by vznikala velká časová prodleva a kolizní body bychom generovali již v úplně odlišné situaci, než nastaly. Oba moduly tedy budou muset pracovat naprosto synchronně, aby nedocházelo k těmto zpožděním. Řešení této situace bude opět pomocí zpráv, protože jiný nástroj pro komunikaci ve VRUTu zatím není a ani se neplánuje. Vytvořím nový typ zprávy v systému, která bude sloužit pouze pro synchronizaci. Zpráva bude mít v sobě jen identifikační číslo. Moduly, který se bude chtít takto synchronizovat, v mém případě modul dynamics i collision_detection, si zaregistrují příjem těchto zpráv. V bodě synchronizace poté modul dynamics vyšle synchronizační zprávu s ID=0. Modul collision_detection, když obdrží tuto zprávu, provede detekci kolizí, a po jejím skončení zašle tutéž zprávu s ID=1. Když pak tuto zprávu obdrží modul dynamics, ví, že detekce byla provedena, a může pokračovat v simulačním kroku. Pomocí ID je tedy rozlišeno, jestli se jedná o žádost o deteci kolizí, nebo zda se jedná o potvrzení, že detekce byla provedena. Všechny zprávy o možných kolizích musejí přijít před synchronizační zprávou z důvodu toho, že zpracování zpráv probíhá systematicky bez předbíhání. Všechny zprávy z modulu tedy k jádru a k příjemci dorazí přesně v tom pořadí, jak byly vyslány. Rozlišení ID zprávy je nutné proto, že vyslaná zpráva se vrátí automaticky i modulu, který ji vyslal, když je zároveň i zaregistrován pro příjem této zprávy. Když tedy modul
34
KAPITOLA 3. REALIZACE
přijme synchronizační zprávu s ID opačným něz očekává, nebude provádět nic a stále bude čekat na zprávu s očekávaným ID.
Obrázek 3.5: Časová osa provádění synchronizace modulu dynamics s modulem collision_detection. Zpráva S(1) znamená synchronizační zpráva s ID = 1. Zpráva K(x) znamená zpráva o nastalé kolizi x.
3.2.11
Přehled tříd
Tento modul, stejně jako modul první, dědí ze třídy SceneM odule, proto má stejné vstupní vlastnosti a přístup do scény. Modul není nijak rozdělen a celá implementace je v jediném souboru. Implementace není nijak rozsáhlá a hlavní funkcionalita je jen jedna, takže ani žádné logické rozdělení nepřicházelo v úvahu. Soubor obsahuje několik podpůrných objektů pro načítání nastavení buď ze scény, nebo ze souboru. Objetk M yODEObject představuje jeden objekt ze scény figurující v simulaci. Obsahuje informace o ID, jméně, původní pozici a rotaci objektu při načtení scény a obsahuje identifikátory interních objektů v ODE, typ objektu, velikost v případě krychle a jestli je objekt statický. Typ objektu může být krychle, koule, nebo síť trojúhelníků. Pole objektu kopíruje možné nastavení v konfiguračním souboru pro pevné objekty.
3.2. MODUL VÝPOČTU DYNAMIKY
35
Obrázek 3.6: Životní cyklus modulu dynamics.
Tyto objekty je při inicializaci nutné vytvořit pro všechny simulované objekty, abychom byli schopni mapovat objekty ve scéně na objekty v ODE a naopak. Hodnoty původní rotace a pozice při načtení scény jsou dobré proto, abychom byli schopni simulaci resetovat a začít ji od počátku, bez nutnosti znovu načítat scénu a všechny objekty v ní.
ID objektu ve scéně Název objektu ve scéně Velikost, pouze u krychle nebo koule Tvrdost objektu Typ (krychle, koule, síť trojúhelníků) Statický/dynamický objekt
dBodyID odeBodyID; dGeomID odeGeomID;
// ID objektu v ODE // ID2 objektu v ODE
dTriMeshDataID triMeshDataId;
// Ukazatel na síť trojúhelníku pokud se jedná o objekt typu síť trojúhelníků
Vector3 position; Matrix rotation;
// Pozice objektu při inicializaci // Rotace objektu při inicializaci
36
KAPITOLA 3. REALIZACE
Matrix sceneInitLocalMatrix;
// Lokální transformační matice objektu při inicializaci
} Druhým pomocným objektem je M yODELink. Jeho vlastnosti opět korespondují s vlastnostmi linků, které jdou nastavit v konfiguračním souboru. Obsahuje ID objektů ve scéně, mezi kterými se má vazba vytvořit, typ vazby, její parametry a dorazy.
class MyODELink { NODE_ID Obj1ID; NODE_ID Obj2ID; LinkType Type;
// ID objektu 1 ve vazbě // ID objektu 2 ve vazbě // Typ vazby
// Hodnota spodního dorazu // Hodnota horního dorazu // Odrazivost v dorazech
dJointID odeJointID;
// ID korespondující vazby v ODE
}
Posledním pomocným objektem je objekt nesoucí data o chování simulace a jejích parametrech. Opět tento objekt koresponduje s možnými nastaveními v konfiguračním souboru. Protože tento objekt je při zvolení konfiguračního souboru ihned načten a data se dále používají při výpočtech simulace. V závorkách je u jednotlivých polí uvedena implicitně nastavená hodnota, která se použije, nedojde-li k jejímu nastavení konfiguračním souborem.
class MyODEGlobal { Vector3 Gravity; unsigned int WorldIterations; int iSurfaceMode; dReal rSurfaceMU; dReal rSoftERP; dReal rSoftCFM; }
// Vektor gravitace (0,0,-9.8) // Počet kroků simulace (64) // Typ povrchů pro kontaktní body (dContactApprox1) // Koeficient tření // Koeficient redukce chyb // Constrait force mixing koeficient
3.2. MODUL VÝPOČTU DYNAMIKY
3.2.12
37
Problémy při integraci
Při implementaci detekce kolizí pomocí ODE knihoven jsem narazil na problém, který spočívá v metodě, jak ODE výpočet kolize volá a zpracovává nastalé kolize. ODE volá metodu, která provádí detekci kolizí pro všechny objekty přidané do konkrétní skupiny. Tato metoda ale své výsledky posílá zpět pomocí statické metody. Ale statické metody a proměnné jsou v systému VRUT prakticky nepoužitelné. Systém je koncipován tak, aby bylo možné spustit libovolné množství modulů, a tím by docházelo ke kolizím mezi statickými objekty. Proto je tato metoda nepoužitelná. Pro výpočet kolizí jsem musel zvolit jediné možné alternativní řešení, provádět testy kolize pouze jednotlivě mezi objekty. To má negativní vliv na výkon u scén, kde je mnoho pohybujících se objektů. ODE pak totiž nemůže plně využít možnosti, které BVH nabízí. Dále je nezbytné při detekování kolizí mezi sítěmi trojúhelníků filtrovat generované kontaktní body. ODE při detekci kolizí generuje i velké množství chybných kontaktních bodů. Nejčastěji se chybný kontaktní bod projevuje velkou hloubkou průniku. Proto jsem musel přistoupit nastavení maximální přípustné hloubce průniku pro uznání kontaktního bodu jako korektního. Jestliže ale tato hranice bude nastavena příliš nízko, pak může nastávat při větších rychlostech objektů nebo při větším kroku simulace propadávání objektů skrz ostatní. Je-li kolize zjištěna až za nastavenou hranicí, žádný kontaktní bod pro tyto kolize nebude generován. Je možné nastavit, že po překročení hranice se bude kolize generovat pouze s hloubkou průniku danou hranicí, ale bohužel kontaktní body s chybně vypočítanou hloubkou průniku obsahují i chybně vypočítané ostatní hodnoty. Brát v úvahu i tyto kolizní body by pak velice znepřesnilo simulaci.
38
KAPITOLA 3. REALIZACE
Kapitola 4
Testování Pro ověření efektivity modulu detekce kolizí porovnám rychlost výpočtu s detekcí kolizí v ODE. ODE používá také BVH pro urychlení výpočtu, ale používá mnohem sofistikovanější urychlovací algoritmy a lepší typy obálek. Tato knihovna je také vyvíjena po několik let teamem nadšených programátorů, takže výkonově by měla můj modul předčit. Přesto ale použití mého modulu detekce kolizí by mělo mít pozitiva v možném využití detailů získaných o nastalé kolizi v rámci celého projektu VRUT, nebo v možnosti urychlit výpočet pokud nepotřebujeme všechny informace o kolizi a stačí nám pouze ID objektů. Měřit budu absolutní čas výpočtu všech kolizí ve scéně v modulu detekce kolizí a v ODE. Aby měly obě porovnávané metody stejné vstupní podmínky, budu provádět obě metody zároveň v každém kroku simulace. Obě metody tedy budou mít v každém okamžiku k dispozici přesně stejnou scénu. Přestavba BVH ve výpočtu nebude brána v úvahu, z důvodu toho, že toto probíhá v ODE současně se simulačním krokem a nebylo by proto možné určit přesný čas potřebný na přestavbu. U modulu detekce kolizí budu měřit čas výpočtu s rychlejším testem hloubky průniku3.1.1, protože první testy ukázaly, že čas výpočtu hloubky průniku v přesnější variantě několikanásobně převyšoval čas výpočtu celé kolize. Čas budu měřit i pro nastavení, kde se nepočitají bližší informace, aby byl vidět rozdíl. Testování jsem prováděl na stolním počítači s procesorem Intel Quad Core 2 o frekvenci 2,83 GHz s pamětí 3GB RAM a grafickou kartou nVidia GeForce 9800 GX2. Operační systém na počítaci byl Windows XP.
4.1
Dynamická zátěž
Pro testování jsem si připravil dva scénáře. V prvním případě bude testovací scénář vypadat tak, že do scény umístím jeden větší model a nechám na něj padat z výšky určitý počet poměrně jednoduchých předmětů. V tomto scénáři budu měnit počet padajících předmětů a úroveň detailu ústředního objekt. Budu se snažit porovnat oba moduly detekce kolizí, jak jsou schopné pracovat s velkým množstvím pohybujících se objektů a pak závislost na míře detailnosti ústředního objektu. Tomuto scénáři budu říkat dynamické zatížení, protože zdaleka ne všechny objekty, které jsou v pohybu, nutně kolidují s ostatními. Scéna dynamické zátěže obsahuje model čajové konvičky a různé počty kuliček složených z řádově pouze stovek trojúhelníků. Na začátku testu kuličky náhodně rozmístím nad konvičku
39
40
KAPITOLA 4. TESTOVÁNÍ
Obrázek 4.1: Dynamický test
a načtu všechny objekty do obou modulů jako síť trojúhelníků a nechám kuličky padat. Jakmile se nějaká kulička dostane pod úroveň konvičky, kde by již jen padala, tak ji opět náhodně vygeneruji pozici nad konvičkou a znovu ji nechám na konvičku padat. Tohle mi zajišťuje, že všechny kuličky ve scéně budou téměř vždy interakovat s konvičkou. Před každým krokem simulace nechám počítat kolize oběma metodami (modulem detekce kolizí a ODE) a zaznamenám si čas potřebný pro výpočet všech kolizí ve scéně. Po provedení určitého počtu simulačních kroků vypočtu průměrnou hodnotu času potřebnou pro detekování kolizí a tento čas zapíši do tabulky. Toto provedu s jednou scénou dvakrát abych otestoval i výpočet kolizí u modulu detekce kolizí s vypnutým výpočtem bližších informací. Tím mi vznikne několik tabulek, každá pro různou úroveň detailnosti čajové konvičky, kde řádky představují počet padajících předmětů a sloupce typ použité metody pro výpočet. Do práce jsem přiložil jen ukázku dvou výsledných tabulek 4.1 a jejích grafů 4.2, protože průběh všech ostatních testů s detailností čajové konvičky byl téměř shodný. Výsledkem tohoto testu je závislost doby výpočtu na počtu předmětů vstupujících do výpočtu a na míře jejich detailnosti. Křivky obou implementací se velice liší. Pro menší počet padajících objektů jsou implementace v modulu detekce kolizí a v ODE podobně rychlé, ale při rostoucím počtu objektů je ODE čím dál pomalejší a čas doby výpočtu roste poměrně strmě. Míra detailnosti objektů na doby výpočtu v obou implementacích nemá významný vliv a na výsledcích se nijak neukázala. Implementace v modulu detekce kolizí se jeví jako poměrně hodně odolná vůči počtu padajících předmětů i míře detailnosti ústředního objektu. Naproti tomu čas výpočtu u implementace v ODE je na počtu padajících předmětů velmi
Tabulka 4.1: Tabulky výsledků dynamických testů v milisekundách. Nadpis tabulky je počet trojúhelníků ze kterého je ústřední objekt složen. Hodnoty ve sloupci CD jsou hodnoty naměřené s použitím modulu detekce kolizí s podrobnými informacemi o kolizi a sloupec CD2 je bez těchto informací. Sloupec ODE jsou výsledky při použití implementace v ODE.
Obrázek 4.2: Časy výpočtu kolizí pro dynamické zatížení. Na vodorovné ose je počet padajících předmětů a na svislé průměrný čas potřebný pro výpočet všech kolizí ve scéně. Grafy jsou pro různě detailní ústřední objekt. CD je výpočet modulu detekce kolizí s podrobnými informace a CD2 je bez těchto informací. ODE je výpočet kolizí pomocí ODE.
závislý. To je ale do značné míry způsobeno nemožností použití metody pro zjištování kolizí pro celý svět najednou, byl jsem nucen testovat každý objekt zvlášť. A to výpočet pro mnoho předmětů výrazně zpomaluje 3.2.12.
4.2
Statická zátěž
Pro druhý scénář jsem si připravil scénu, kde jsou poskládány modely hracích karet do pyramidy. Budu sledovat opět absolutní čas detekování všech kolizí ve scéně v každém kroku simulace. Měnit budu počty karet v pyramidě a úroveň jejich detailu. V tomto scénáři bude řádově méně objektů než ve scénáři prvním, ale za to zde bude řádově více kolizních bodů v každém simulačním kroku. Tomuto scénáři budu říkat statické zatížení právě proto, že všechny objekty ve scéně jsou v každém okamžiku simulace v kolizi se skupinou jiných objektů. Scéna je složena z určitého počtu poskládaných karet do pyramidy na ploše. Karty jsou
42
KAPITOLA 4. TESTOVÁNÍ
Obrázek 4.3: Statický test
složeny z určitého počtu trojúhelníků. Na počátku testu načtu scénu do VRUTu a načtu všechny objekty do modulů. Zapnu simulaci a gravitace mi zajistí, že všechny karty začnou být přitahovány dolů a tím začnou kolidovat se sousedícími kartami. Vzájemným působením sil se síly vyrovnávají a celá pyramida po dobu testu zůstává stát nebo se pomalu bortí. Stejně jako v prvním testu v každém kroku simulace změřím čas potřebný pro výpočet všech kolizí ve scéně a čas si uložím. Po uplynutí určitého počtu kroků vypočtu průměrný čas potřebný pro výpočet u obou modulů a u modulu detekce kolizí pro podrobné informace o kolizi i bez nich. Výsledné časy jsem opět zanesl do tabulek a vynesl do grafů. Do práce jsem stejně jako v dymické zátěži přidal pouze výsledky pro dva různé počty karet, protože výsledky ostatních testů měly stejný průběh, pouze byly křivky posunuty do horších časů nebo lepších časů.
Obrázek 4.4: Čas výpočtu kolizí pro statické zatížení v milisekundách. Na vodorovné ose je počet trojúhelníků každé karty v tisících. Grafy jsou pro počty karet ve scéně.
Křivky výsledných časů pro všechny metody vycházejí velmi podobně. Pro jednoduché objekty jsou časy prakticky stejné. S nárůstem úrovně detailů se metody rozdělí do pořadí
Tabulka 4.2: Časy výpočtu kolizí pro statické zatížení. V řádkách jsou časy pro konkrétní stupeň detailu objektů karet. Hodnoty úrovně jsou v tisících trojúhelníků. Ve sloupcích jsou použité metody. CD je modul detekce kolizí, CD2 je tentýž modul bez podrobných informací o kolizi, ODE je výpočet pomocí ODE. Hodnoty časů jsou v milisekundách.
odpovídající předpokladům. Nejrychlejší je metoda detekce kolizí v modulu detekce kolizí při vypnutém výpočtu bližších informací o kolizi. Druhá je metoda v ODE a metoda v modulu detekce kolizí s informacemi je nejpomalejší, ale její rozdíl oproti ODE je poměrně malý. Pro testované scénáře to není více jak v řádech jednotek milisekund. Stejně tak rozdíl mezi ODE a modulem bez bližších informací je také poměrně malý. Rozdíly jsou tím větší, čím větší je úroveň detailů jednotlivých předmětů. Výsledek obou testů bych interpretoval tak, že implementace výpočtu kolizí v ODE je rychlejší než implementace má v modulu, ale výsledná výkonová mezera není nikterak zásadní. Musím ale dodat, že pro výpočet kolizí v ODE není použita nejrychlejší možná varianta, viz. 3.2.12. Při praktických testech, kdy jsou ve scéně v jednom okamžiku simulace řádově jen jednotky kolizních bodů, ale za to objekty enormně detailní, vykazují obě implementace velmi podobné výkony. S přibývajícími objekty má, ale návrh modul detekce kolizí.
4.3
Reálné scénáře
Další testy, které jsem prováděl nebyly zaměřeny na měření výkonu, ale na schopnosti splnit s pomocí modulů reálné požadavky a scénáře. Scénáře se týkaly výhradně automobilového průmyslu a přicházeli od pana Antonína Míška ze Škody Auto, který byl již od počátku koordinátorem projektu VRUT a nyní je i jeho spoluautorem. Pro všechny tyto scénáře je společná interakce uživatele se scénou. Uživatel má na ruce nebo v ruce trackovatelné zařízení, na které je navázaný model ruky ve scéně. Pohybem modelu ruky ve scéně probíhá interakcí s různými objekty ve scéně. Pro všechny scénáře jsou použil současně oba implementované moduly.
44
KAPITOLA 4. TESTOVÁNÍ
Prvním scénářem je nastavování zpětného zrcátka v kabině automobilu. Modul dynamics provádí výpočet reakce na nastalou kolizi mezi modelem ruky a zpětného zrcátka. Pro správnou reakci jsem použil vazbu typu kloub 2.9, která spojuje model zrcátka s modelem předního skla. Dále je spuštěn modul detekce kolizí pro výpočet kolizí mezi rukou a zrcátkem. Modul detekce kolizí má dále zapnutou funkci udržení objektů v nekolizní pozici, aby nedocházelo k žádným prolínáním objektů. Když nastane dotek ruky a zrcátka, modul detekce kolizí zastaví ruku před kolizí a vyšle zprávu mudulu dynamics, který zrcátko natočí do výsledné pozice. Praktické testy tohoto scénáře vyšly dobře. Moduly dobře a rychle reagují na nastalou kolizi a s dobrým nastavení parametrů jsem docílil velmi reálného výsledku.
Obrázek 4.5: Otevírání dveří s pomocí obou modulů.
Druhý typ reálného scénáře, který jsem obdržel je simulace otevírání dveří automobilu. Dveře budou opět reagovat na dotek s modelem ruky ve scéně a dotek bude opět převáděn na tlak na dveře. Dveře jsou spojeny s kostrou automobilu pomocí kloubu typu pant 2.10. Maximální úhel otevření dveři koresponduje s maximálním vychýlením vazby. Dále ale dveře automobilů mají aretace v mezipolohách. Toto je opět nastaveno přes parametry pantu i se sílou aretací. Dobré nastavení aretací dá určitou práci, ale po té se dveře opravdu chovají velice realisticky. Menší problémy se občas vyskytnou při držení rovnovážné pozice v úhlech aretace. Dveře občas stále překmitávají v malých úhlech kolem úhlu aretace.
Kapitola 5
Závěr V této diplomové práci jsem se zabýval návrhem a implementací detekce kolizí v rozsáhlých 3D scénách. Implementoval jsem metodu hierarchie obálek a plně integroval do aplikace VRUT jako jeden modul. Dále jsem provedl rešerši existujících fyzikálních enginů (Havok, ODE, PhysX, Bullet) a knihovny ODE jsem integroval do aplikace VRUT jako samostatný modul. Podařilo se mi oba moduly propojit v ramci aplikace VRUT a s jejich pomocí splnit zadané scénáře. Rychlost detekce kolizí u vlastní implementace je konkurence schopná s implementací v knihovně ODE, což bylo prokázáno v testech. Možné další pokračování této práce bych viděl v implementaci jiných typů obálek do modulu detekce a kolizí a hlavně v předělání algoritmu pro výpočet hloubky průniku, aby byl i rychlý i přesný. Dále je možné vylepšovat práci s dynamikou ve scéně, přidat některé druhy kloubů jako například píst s možností rotací kolem své osy a přidat podporu pro deformovatelné povrchy.
45
46
KAPITOLA 5. ZÁVĚR
Kapitola 6
Uživatelská příručka Popis spuštění a ovládání aplikace VRUT je podrobně popsán v [1], proto tuto část přeskočím. Budu předpokládat že aplikace VRUT je spuštěna a uživatel ví jak ovládat její základní funkce jako zadávańí příkazů a práce s okny aplikace.
6.1
Modul detekce kolizí
Obrázek 6.1: Grafické rozhranní modulu detekce kolizí
Modul se spustí příkazem "runmodule collision_detection". Po odeslání příkazu se zobrazí okno s jenoduchým uživatelským rozhranním modulu 6.1. Veškeré funkce modulu je možné zadávat buď pomocí příkazové řádky v aplikaci VRUT, nebo pomocí zmíněného grafického rozhranní. Nyní popíši všechny prvky možnosti nastavení modulu.
47
48
KAPITOLA 6. UŽIVATELSKÁ PŘÍRUČKA
1. Scene ID výběrem se zvolí scéna, pro kterou bude výpočet kolizí probíhat. 2. nodeID identifikační číslo uzlu se kterým bude možné pohybovat pomocí šipek a kláves "Home"a "End". 3. Enabled vypnutí/zapnutí modulu. Ve vypnutém stavu modul sice stále bude přijímat zprávy ale nebude na ně nijak reagovat. 4. Target Node 1 identifikačního čisla uzlů, pro které bude probíhat výpočet testu kolize vrámci této skupiny i testy kolizí s objekty definovanými v poli T argetN ode2. Do pole se jednotlivé uzly zadávají buď zadáním přímo ID uzlu obsahujícího geometrii, nebo ID jakéhokoli vnitřního uzlu grafu scény a modul načte všechny geometrie v podstromu tohoto uzlu. Do pole je možné zadat více uzlů pomocí odělovače ";". Je možné i zadat uzly, které se budou ignorovat. To je dobré pro případ kdy několik geometrii je pod jedním rodičem v grafu scény a my bychom chtělo provádět testy kolize pro všechny tyto geometrie krom jedné. Pro tento příklad zadáme do pole ID rodiče těchto všech geometrií a tu co chceme ignorovat tam napíšeme zvlášt se znaménkem "-". Například takto "2;-18". Při tomto zadání tedy bude modul počítat kolize pro všechny geometrie v podstromu uzlu 2, kromě geometrie ID=18. 5. Target Node 2 uzly se kterými se mají provádět testy kolize vůči uzlům definovaným v poli T argetN ode1. Jinými slovy, uzly definované v poli T argetN ode1 se budou testovat mezi sebou a s uzly definovanými v poli T argetN ode2. Uzly, které nebudou definovány ani v jednom poly budou modulem ignorovány. Pokud se obě pole nechají na počáteční hodnotě 0, pak se budou kolize počítat pro všechny objekty ve scéně. 6. Minimum separation distance definování minialní vzdálenosti objektů, kterou musejí objekty splňovat, aby byly prohlášeny za nekolizní. Tuto možnost není možné kombinovat s možností Collisiondetailinf o. 7. Load objects načtení všech definovaných objektů do modulu a vytvoření BVH pro jejich primitiva. Počáteční nastavení totiž provádí stavbu BVH pro objekty až v případě, že je BVH opravdu potřeba. To šetří čas načtení scény a paměť, ale stojí čas při samotném běhu aplikace. Stavba BVH může pro velmi velké objekty trvat i několik sekund. 8. TMP tlačítko nemá žádnou funkci, je zde pouze jako výplň volného prostoru, aby si grafické rozhraní udrželo přehlednost. 9. Collision detail info výpočet kolizního bodu a všech podstatných informací o tomto bodu, které jsou popsány v sekci 3.1.1. 10. Stop objects before collisions udržení objektů v nekolizní pozici. Při použití této možnosti se budou stále posílat informace o nastalé kolizi, přestože se objekty do kolize nedostanou. To je proto, aby ostatní moduly nebo jádro věděly, že ke kolizi došlo a mohly provádět některé své kroky, například zabarvení objektů, nebo reakce odražení objektů.
6.2. MODUL DYNAMIKY
49
11. Synchronized with dynamics pro použití synchronizace s moduly dynamics. Při zapnuté této funkci bude modul provádět detekce kolizí na vyžádání přes synchronizační událost a i synchronizační událost posílat zpět. Jestliže uživatel chce provádět detekci kolizí u modulu dynamics tímto modulem, musí být tato možnost zapnuta, jinak to nebude fungovat. 12. Collision events to LOG jestliže kolize nastala tak výsledek testu kolize zapsat do LOGu. 13. Messages to LOG vypisovat různé informativní zprávy o chodu modulu.
6.2
Modul dynamiky
Obrázek 6.2: Grafické rozhranní modulu dynamiky
Modul se spustí příkazem "runmodule dynamics", tím se otevře okno s grafickým rozhranním modulu 6.2. 1. sceneID scéna, pro kterou se budou dynamické fyzikální jevy počítat. 2. Enabled physics zapnutí/vypnutí modulu. 3. Reset resetování scény do původní pozice při načtení objektů do modulu. Tato funkce je dobrá pro situace, když chceme sledovat jeden krátký fyzikální jev více krát za sebou, třeba s různými nastaveními. Druhé tlačítko slouží pro krokování simulace. Tím se dá detailněji prozkoumávat celý jev. 4. Collision from module přepínač pro použití detekce kolizí z vlastního modulu detekce kolizí ve VRUTu. Detekování kolizí ve fyzikálním enginu bude tedy ignorováno a simulace bude probíhat pouze na základě informací o kolizích zasílaných v podobě událostí.
50
KAPITOLA 6. UŽIVATELSKÁ PŘÍRUČKA
5. Use gravity zapnutí/vypnutí gravitace ve scéně. 6. Enable logging Zasílání různých informativních zpráv o práci modulu. 7. Maximal penetration depth maximální povolená hloubka průniku proto, aby se kontaktní bod zahrnul do simulace. Je to z důvodu filtrování kontaktních bodů pro různé neošetřené singulární případy a nepřesně spočítané kontaktní body. 8. Xml settings cesta ke konfiguračním souboru s nastavením konkrétní scény a simulace. Cesta musí být zadána buď absolutní nebo relativní vůči adresáři, kde je uložena binárka aplikace VRUT. Soubor nemusí mít příponu xml, ale musí být textový a mít xml formát. O detail o vlastním souboru je v sekci 6.2.1. 9. Load XML načtení souboru z cesty uvedené v poli Xml settings. S načtením souboru seautomaticky provede i načtení objektů ze scény a upravení parametrů simulace podle konfiguračního souboru.
6.2.1
Konfigurační XML soubor
Konfigurační soubor má syntaxi jenoduchého XML souboru a jeho první řadka by měla vypadat takto . Soubor nemusí mít připonu XML, aby ho bylo možné načist. Ale musí být v textové podobě. Jeho hlavní uzel se musí jmenovat Dynamics. Tento uzel může obsahovat libovolné množství následujícich uzlů. Nezáleží na pořadí ve, kterém jsou uzly uvedeny. Existují tři různé typy uzlů pod kořenem. Jsou to Global, SolidObjects a Links.
6.2.2
Globální nastavení
Globální nastavení simulace se provádí v uzlu Global. Tento uzel by neměl mít žádné potomky, nastavení se provádí pomoci atributů přímo u uzlu. Jestliže se v jednom konfiguračním soboru objeví více globálních nastavení bude se brát vždy v úvahu poslední nastavení konkrétního atributu. Nyní vyjmenuji všechny atributy, které jsou u uzlu definovány. 1. Gravity , tímto atributem lze nastavit směr a sílu gravitace ve scéně. Síla musí být nastavena jako tří složkový vektor oddělený čárkou (","). Čísla mohou být i desetiná a k oddělení desetiné a celé časti používejte tečku("."). Počáteční nastavení této hodnoty je "0,0,-9.8". 2. WorldIterations tento atribut slouží pro nastavení výpočtu simulace. Čím větší celé čislo bude nsataveno, tím bude simulace teoreticky přesnější, ale pomalejší. Doporučuji tuto hodnotu ponechat na počáteční hodnotě, která je 64. 3. Scale slouží pro změnu měřítka scény. Je li napřiklad scéna modelovaná ve velkém měřítku, tak je možné tímto parametrem říci čím se mají hodnoty násobit aby scéna odpovídala metrům. Má li objekt ve scéně, který má realnou výšku 1m, hodnotu například 10, pak se atribut nastaví na 0.1. Hodnota musí být vždy větší než 0.
6.2. MODUL DYNAMIKY
6.2.3
51
Nastavení vazeb
Vazby mezi objekty se nastavují v uzlu s názvem Links. Tento uzel nemá žádné atributy a jeho potomci mohou mít pouze název Link a každý takový potomek odpovídá jedné vazbě v systému. Jedna vazba může být vázána na jednu nebo dvě geometrie ve scéně. Všechny vlastnosti a parametry vazby se uvedou jako atributy uzlu Link. Následuje výčet možných atributů. 1. Type je typ vazby, která bude vytvořena. Možnosti jsou "BallSocket", "Hinge", "Slider". Vazby jsou popsány v sekci 2.2.6. Atribut je povinný. 2. Obj1ID je ID první geometrie, která bude svázána vazbou. Atribut je povinný. 3. Obj1Name druhá možnost definování první geometrie, která bude ve vazbě, pomocí jména. Jméno musí být ve scéně unikátní. Jinak načtení neproběhne v pořadku. Atribut je povinný. 4. Obj2ID je ID druhé geometrie, která bude svázána vazbou. Atribut je nepovinný. 5. Obj2Name druhá možnost definování druhé geometrie, která bude ve vazbě. Atribut je nepovinný. 6. Compound1ID je ID složeného objektu, který bude ve vazbě. Atribut je nepovinný. 7. Compound2ID je ID složeného objektu, který bude ve vazbě. Atribut je nepovinný. 8. Axis tři složkový vektor osy vazby. Osu používá jen kloub typu pant. U jiných typů je tento atribut bezvýznamný. Počáteční nastavení je "0,0,1". Atribut je nepovinný. 9. Anchor tří složkový vektor pozice kloubu v prostoru. Pozici je nutné zadat ve světových souřadnicích. Atribut má význam pouze u vazby typu kloub a pant. Počáteční nastavení je přesně uprostřed objektů ve vazbě. V případě zadání obou objektů je nepovinný, ale při pouze jednom objektu je atribut povinný. 10. Lock je n-složkový vektor, kde každá složka definuje úhel při kterém dochází ve vazbě k zaseknutí (místo, kde v jeho okolí působí síli směřující do toho místa). Atribut má význam pouze pro pant a je nepovinný. 11. LockStrenght velikost síli působící v místech zaseknutí. Pouze kladná čisla a atribut je nepovinný. Počáteční nastavení je 2. 12. LockSize velikost okolí v jakém působí síly při zaseknutí. Musí být vždy větší než 0 a počateční hodnota je 0.1. Atribut je nepovinný. 13. Stiffness je tuhost vazby a její ochota ke změně úhlu. Počáteční nastavení je 0.5 a je to nepovinný atribut. 14. HiStop je maximální vychýlení pozice vazby od původní. U vazby typu pant je to úhel natočení a u vazby typu píst je to vzdálenost objektů. U vazby typu kloub tento parametr nemá význam. Počáteční nastavení je na nekonečno a atribut je nepovinný.
52
KAPITOLA 6. UŽIVATELSKÁ PŘÍRUČKA
15. LoStop je minimální vychýlení pozice vazby od původní. Ostatní vlastnosti stejné jako u HiStop. 16. BouncinessAtStops definuje, jak se bude vazba chovat při dosažení krajní pozice. Čím větší hodnota, tím bude větší odraz z krajní pozice směrem zpět. Počateční hodnota je 0.5 a je to nepovinný atribut.
6.2.4
Pevné objekty
Definice pevných objektů ve scéně se provádí v uzlu SolidObjects. Uzel nemá stejně jako Links žádné atributy a jeho potomci Object představují jednotlivá objekty ve scéně. 1. Name je název objektu ve scéně. Název musí být ve scéně unikátní, jinak nedojde k jeho správnému načtení. Není li nastaveno ID je atribut povinný. 2. ID je druhý způsob načtení objektu. Není li nastaveno N ame je atribut povinný. 3. LoadFromScene je parametr pro načtení objektu velikosti a tvaru objektu ze scény. Nabývá hodnot 0 a 1. Počáteční nastavení je 0 a atribut je nepovinný. 4. Type je typ načítaného objektu. Nabývá hodnot "Box", "Sphere", "TriMesh"a "Compound". Počáteční nastaveni je "TriMesh", ale pokud se objekt nepodaří načísta jako síť trojúhelníků, tak se z něho udělá "Box"a jeho velikosti se vezmou jako obálka uzlu, který geometrii obsahuje. Parametr je nepovinný, ale pokud je zvolený typ "Compound"tak je nutné zadat ID komponent ze kterých se skládá. 5. CompoundID je jméno podle kterého je možné se odkazovat na složený objekt v definici vazeb. 6. CompoundNames jsou jména objektů ze kterých je složený objekt složen. 7. CompoundIDs jsou ID objektů ze kterých je složený objekt složen. 8. Size je tří složkový vektor velikosti objektu. Má význam pouze pro typ objektu Box a pokud není nastaveno načítání objektu ze scény tak je atribut povinný. 9. Pos je tří složkový vektor pozice objektu ve scéně. Pozici je nutné zadat ve světových souřadnicích a pokud není nastaveno načítání objektu ze scény tak je atribut povinný. 10. Density je hustota objektu. Podle této hodnoty se vypočítává hmotnost objektu a to velmi ovlivňuje dynamické vlastnosti objektu. Počáteční nastavení je 0.01 a atribut je nepovinný. 11. IsStatic definuje, jestli bude objekt ve scéně pouze statický a bude pouze ovlivňovat ostatní objekty, nebo dynamický a bude i on sám ovlivňován ostatními objekty ve scéně. Nabývá hodnot 0 a 1. Počáteční nastavení je 0 a atribut je nepovinný. 12. Gravity definuje, jestli bude na objekt působit gravitace. Nabývá hodnot 0 a 1. Počáteční nastavení je 1 a atribut je nepovinný.
6.2. MODUL DYNAMIKY
6.2.5
53
Příklad konfiguračního souboru
Mějme scénu, ve které je libovolný počet objektů, ale dva objekty, mezi kterými chceme výtvořit vazbu typu píst. Takže se objekty budou moct k sobě přibližovat a vzdalovat působením některé externí síly, napřiklad gravitace. První objekt bude pouze statický takže se nebude pohybovat. U vazby nechám hodnotu osy nenastavenou, aby se vypočetla jako směr od jednoho obejktu ke druhému. Nastavím větší tuhost vazby a také minimální a maximální vychýlení od původní pozice. Odraz při dosažení krajních vychýlení nastavím na 0. Gravitaci a ostatní globální hodnoty ponechám na počáteční hodnotě.
<SolidObjects>
54
KAPITOLA 6. UŽIVATELSKÁ PŘÍRUČKA
Literatura [1] Václav Kyba: Modulární 3D prohlížeč, Diplomová práce , 2008 [2] Herman J. Haverkort: Introduction to bounding volume hierarchies, 2004 [3] Wikipedia: Separating axis theorem, http : //en.wikipedia.org/wiki/Separating_axis_theorem , 7.4.2010 [4] J. Matoušek: Range Searching with Efficient Hierarchical Cuttings. Discrete & Computational Geometry 10:157–182 (1993). [5] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational Geometry: Algorithms and Applications, Springer, 1997. [6] P. K. Agarwal and J. Erickson: Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack (eds.), Advances in Discrete and Computational Geometry, Contemporary Mathematics 223: 1–56, American Mathematical Society, 1998. [7] Shashidhara K. Ganjugunte: A Survey on Techniques for Computing Penetration Depth. 2007 [8] ODE Manual, http : //opende.sourcef orge.net/wiki/index.php/M anual, 7.4.2010 [9] Christer Ericson, Real-time Collision Detection, ISBN 1-55860-732-3, 2005 [10] Kirill Garanzha, Efficient Clustered BVH Update Algorithm for Highly-Dynamic Models [11] Weghorst, Hank. Gary Hooper. Donald Greenberg, Improved Computational Methods for Ray Tracing, ACMTransactions on Graphics, vol. 3, no. 1, pp. 52–69, Leden 1984. [12] Weghorst, Hank. Gary Hooper. Donald Greenberg, Improved Computational Methods for Ray Tracing, ACMTransactions on Graphics, vol. 3, no. 1, pp. 52–69, Leden 1984. [13] Lukáš Korba, Simulace řízení vozidla, Dilpomová práce, 2008 [14] Oficiální stránky společnosti nVidia, http : //www.nvidia.com/object/physxn ew.html, 3.5.2010 [15] Oficiální stránky společnosti Havok, http : //www.havok.com/, 3.5.2010 [16] Oficiální stránky projektu Bullet, http : //bulletphysics.org/wordpress/, 3.5.2010
Grafické znázornění testování kolize dvou AABB. a) Podmínka Ay-max < Bymin je splněna, proto AABB nejsou v kolizi. b) Ani jedna potřebná podmínka není splněna, proto AABB jsou v kolizi. . . . . . . . . . . . . . . . . . . . . .
9
2.6
Vlevo první úroveň BVH nad objekty ve scéně. Vpravo druhá úroveň nad primitivy objektu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Reakce na vzniklou kolizi produkuje sílu působící ve směru normály a její velikost závisí na hloubce průniku. Čím větší simulační krok, tím větší možná hloubka průniku a tím větší reakce na stejnou kolizi. . . . . . . . . . . . . . . 32
3.5
Časová osa provádění synchronizace modulu dynamics s modulem collision_detection. Zpráva S(1) znamená synchronizační zpráva s ID = 1. Zpráva K(x) znamená zpráva o nastalé kolizi x. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6
Životní cyklus modulu dynamics. . . . . . . . . . . . . . . . . . . . . . . . . . 35
Časy výpočtu kolizí pro dynamické zatížení. Na vodorovné ose je počet padajících předmětů a na svislé průměrný čas potřebný pro výpočet všech kolizí ve scéně. Grafy jsou pro různě detailní ústřední objekt. CD je výpočet modulu detekce kolizí s podrobnými informace a CD2 je bez těchto informací. ODE je výpočet kolizí pomocí ODE. . . . . . . . . . . . . . . . . . . . . . . . . . . Statický test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Čas výpočtu kolizí pro statické zatížení v milisekundách. Na vodorovné ose je počet trojúhelníků každé karty v tisících. Grafy jsou pro počty karet ve scéně. Otevírání dveří s pomocí obou modulů. . . . . . . . . . . . . . . . . . . . . . .
Tabulky výsledků dynamických testů v milisekundách. Nadpis tabulky je počet trojúhelníků ze kterého je ústřední objekt složen. Hodnoty ve sloupci CD jsou hodnoty naměřené s použitím modulu detekce kolizí s podrobnými informacemi o kolizi a sloupec CD2 je bez těchto informací. Sloupec ODE jsou výsledky při použití implementace v ODE. . . . . . . . . . . . . . . . . . . . . 41 Časy výpočtu kolizí pro statické zatížení. V řádkách jsou časy pro konkrétní stupeň detailu objektů karet. Hodnoty úrovně jsou v tisících trojúhelníků. Ve sloupcích jsou použité metody. CD je modul detekce kolizí, CD2 je tentýž modul bez podrobných informací o kolizi, ODE je výpočet pomocí ODE. Hodnoty časů jsou v milisekundách. . . . . . . . . . . . . . . . . . . . . . . . 43
