Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Martin Šik. Kabinet software a výuky informatiky

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Martin Šik Částicové systémy Kabinet software a výuky informatiky

Vedoucí bakalářské práce: RNDr. Josef Pelikán Studijní program: Informatika, Programování

2010

Na tomto místě bych rád poděkoval vedoucímu práce RNDr. Josefu Pelikánovi za jeho rady a náměty. Dále děkuji za neméně důležitou podporu své přítelkyni a rodině.

Prohlašuji, že jsem svou bakalářskou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce a jejím zveřejňováním. V Praze dne 21.5. 2010

Martin Šik

2

Obsah 1 Úvod 1.1 Realizace částicových systémů . . . . . . . 1.2 Částice . . . . . . . . . . . . . . . . . . . . 1.3 Emitory . . . . . . . . . . . . . . . . . . . 1.4 Externí síly . . . . . . . . . . . . . . . . . 1.5 Interakce mezi částicemi . . . . . . . . . . 1.6 Hierarchické struktury . . . . . . . . . . . 1.7 Aktualizace systému . . . . . . . . . . . . 1.8 Vykreslování . . . . . . . . . . . . . . . . . 1.9 Skriptování . . . . . . . . . . . . . . . . . 1.10 GPU implementace . . . . . . . . . . . . . 1.11 Offline simulace . . . . . . . . . . . . . . . 1.12 Cíle práce . . . . . . . . . . . . . . . . . . 1.13 Ukázky mnou implementovaných systémů 2 Základní architektura a algoritmy online 2.1 Reprezentace částice . . . . . . . . . . . 2.2 Typ částice . . . . . . . . . . . . . . . . 2.3 Buffer částic a urychlovací mřížka . . . . 2.4 Iterátory na mřížce . . . . . . . . . . . . 2.5 Hierarchický průchod mřížkou . . . . . . 2.6 Emitor částic . . . . . . . . . . . . . . . 2.7 Síly a interakce . . . . . . . . . . . . . . 2.8 Aplikace interakcí a sil . . . . . . . . . . 2.9 Vykreslovací buffer . . . . . . . . . . . . 2.10 Částicový systém . . . . . . . . . . . . . 2.11 Update systému . . . . . . . . . . . . . .

3

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

6 7 7 8 9 10 10 12 13 14 15 16 16 17

. . . . . . . . . . .

20 20 22 23 25 26 28 28 29 31 32 34

3 Základní architektura a algoritmy offline 3.1 Formát souboru offline simulace . . . . . 3.2 Uložení simulace . . . . . . . . . . . . . 3.3 Načtení a vykreslení rámce . . . . . . . . 3.4 Buffer rámců . . . . . . . . . . . . . . . 3.5 Přehrávání offline simulace . . . . . . . .

simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

36 36 38 38 39 40

4 Výkon

41

5 Závěr 5.1 Shrnutí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Splnění cílů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Směr další práce . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45 45 46 46

Literatura

47

A Obsah CD

48

B Uživatelská dokumentace B.1 Požadavky . . . . . . . . B.2 Konfigurační soubor . . B.3 Aplikace MSPS . . . . . B.4 SimulPlayer . . . . . . .

. . . .

. . . .

. . . .

. . . .

4

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

49 49 49 50 52

Název práce: Částicové systémy Autor: Martin Šik Katedra (ústav): Kabinet software a výuky informatiky Vedoucí bakalářské práce: RNDr. Josef Pelikán e-mail vedoucího: [email protected] Abstrakt: V předložené práci se zabývám vývojem knihovny na práci s částicovými systémy nezávislou na konkretní použité grafické knihovně. Částicové systémy slouží v různých grafických aplikacích k zobrazování zajímavých efektů (jako je například: oheň, vodopád, kouř, výbuchy, atd.), jež by se jinak velice těžko zobrazovaly stejným způsobem jako jiné běžné objekty ve scéně. Jelikož je toto velice rozsáhlé téma, rozhodl jsem se více zaměřit hlavně na interakce mezi jednotlivými částicemi, které by byly dostatečně rychlé na online vykreslování. Pro případné výpočetně náročné interakce zároveň umožňuji uložení vypočtených vlastností částic na disk a posléze jejich rychlé přehrání. Abych co nejvíce využil výkonu dnešních procesorů, probíhají některé výpočty paralelně na více jádrech. Klíčová slova: Particle systems, 3D grafika, interakce mezi částicemi Title: Particle systems Author: Martin Šik Department: Department of Software and Computer Science Education Supervisor: RNDr. Josef Pelikán Supervisor’s e-mail address: [email protected] Abstract: In the present work I concern myself with the development of Particle systems library independent on any concrete graphical library. Particle systems are used in various graphical applications to render interesting effects (for example: fire, waterfall, smoke, explosions, etc.) which are nearly impossible to be rendered the same way as other ordinary objects in scene. Given the fact that this is very complex theme I choose to concentrate mostly on interactions between particles that would be fast enough for online rendering. For possible hard to compute interactions I allow saving calculated properties of particles and afterwards their fast playback. Because many moderns processors have more than one core some calculations in my library can run parallel in more threads. Keywords: Particle systems, 3D graphics, interaction between particles 5

Kapitola 1 Úvod V moderní počítačové grafice se setkáváme s problémem jak zobrazovat různé nejasné a těžko přesně popsatelné jevy vyskytující se v přírodě jako například oheň, déšť, sníh, kouř, padající voda, mraky, tráva, srst, exploze, ohňostroje (ale také často i jevy méně reálné, chaotické vyskytující se v různých hrách a filmech, např.: kouzla, efekty zbraní ze science-fiction apod.) . Takovéto jevy nelze dobře reprodukovat konvenčními zobrazovacími technikami (pomocí více či méně pevně daných modelů), k jejich co nejreálněji vypadající simulaci se proto používají takzvané částicové systémy.

Obrázek 1.1: Oheň ve hře Half-Life (obrázek převzat z [6]) 6

1.1

Realizace částicových systémů

Částicový systém se skládá ze stovek či tisíců naprosto nezávislých částic (avšak k reprodukci složitějších efektů se mohou i jednotlivé částice navzájem ovlivňovat – více o tom dále), které mají individuální atributy, navenek ale tvoří částice určitý celek, který velice dobře simuluje požadovaný efekt. K tomu, aby částicový systém dobře fungoval, je třeba zajistit správný chod všech jeho částí, které si nyní probereme.

1.2

Částice

Již zmíněné částice jsou základním stavebním kamenem celé simulace. Každá z nich má různé atributy v závislosti na tom, co přesně chceme reprodukovat. Skoro pokaždé však budou mít jednotlivé částice následující tři vlastnosti: • Pozice Tato vlastnost nám udává pozici částice v prostoru (relativní nebo vůči pozici systému, záleží na implementaci). Často se uchovává celý seznam předchozích pozic částice, k dosažení jistých efektů (například stop, blesků apod.). • Rychlost a směr Ve většině simulací budeme chtít, aby se částice pohybovaly (pokud nepůjde například pouze o zobrazení statického hvězdného nebe), proto musíme o každé částici vědět její rychlost a směr (nejlépe reprezentované vektorem pro snadnou aktualizaci pozice částice). K dosažení složitějších efektů je často třeba i uchovávat zrychlení částice (opět ve formě vektoru). • Životní energie (Life span, energy . . . ) Životní energie nám udává, jak dlouho bude naše částice existovat. Nejvhodnější je tuto vlastnost reprezentovat na počet zbývajících snímků (tedy ještě tolikrát bude částice zobrazena, než přestane existovat). Tato hodnota může i nepřímo ovlivňovat další níže zmíněné vlastnosti a simulovat tak stárnutí částice. Dále mohou mít vlastnosti, které jsou buď společné všem částicím v systému (či jen určitým skupinám), a nebo mohou být opět nezávislé pro každou částici.

7

• Barva a průhlednost Například pro simulaci ohně budeme chtít, aby částice měly žlutou barvu a byly průhledné (plameny, jakožto většina dříve uvedených užití částicových systému, jsou průhledné). • Textura Pro zajištění větší reálnosti efektu se mohou na jednotlivé částice aplikovat textury (například textura sněhové vločky při simulaci sněžení). Většinou je textura globální vlastnost sdílená více částicemi. • Velikost Velikost částice slouží jednak při vykreslování a také ji lze použít při aplikaci různých externích sil na částici (více o externích silách později). • Váha a další fyzikální vlastnosti Jak už bylo řečeno u předchozí vlastnosti, částici mohou ovlivňovat externí síly, které vyžadují pro svůj výpočet další atributy. Mnohé z těchto vlastností mohou být ovlivněné stářím částice, čímž lze pak docílit efektů, jako je postupné vychladnutí jisker ohňostroje pomocí změny průhlednosti nebo velikosti. Abychom věděli, o kolik se má změnit dané hodnota, můžeme mít opět u částice uložené delta hodnoty a při každé aktualizaci přepočítávat hodnotu : nová hodnota = původní hodnota + delta hodnota .

1.3

Emitory

Emitory jsou myšlené objekty (tedy většinou nejsou nijak vyobrazené, slouží pouze k jednodušší práci s částicemi), které se starají o vytváření nových částic v systému. Mají opět několik základních vlastností jejichž užití závisí na implementaci: • Pozice Počáteční pozice částic vytvářených tímto emitorem, hodně souvisí s následující vlastností. • Tvar emitoru Tvar emitoru nám dále určuje pozici emitované částice. Pokud například chceme simulovat padající sníh, bude tvar emitoru obdélník umístěný ve 8

3D prostoru svojí plochou směrem dolů. Sněhové vločky se pak budou náhodně generovat po celé ploše emitoru. • Tempo emitování (Emission rate) Vlastnost udávající počet částic vygenerovaných za 1 snímek (případně i jiný časový údaj, který je ovšem poté nutné přepočítat). • Počáteční nastavení vlastností částic Emitor musí určit každé nově vygenerované částici všechny její počáteční vlastnosti (nejen dříve zmíněnou pozici). Pro dosažení co nejlepších simulací je potřeba přidat do simulace prvek náhody, který přichází na scénu právě zde. Částice mají sice pevně dané počáteční vlastnosti, ale většinou se k nim připočte malá náhodná hodnota vygenerovaná pro každou částici zvlášť. Často také chceme, aby se částice emitovaly na určité pozici dané konkrétní částicí (například při realizaci ohonu jednotlivých rachejtlí ohňostroje a nebo při jejich následné explozi emitující stovky jisker). Toho lze docílit například kombinací částice a emitoru (jak je tomu i v mé knihovně).

1.4

Externí síly

Často chceme, aby naše částice byly ovlivňovány externími silami. Například když simulujeme padající vločky sněhu, nemusíme dát vločkám počáteční směr dolů, ale můžeme použít stejně jako v přírodě gravitaci. Dále pak také můžeme chtít, aby si s vločkami pohrával vítr, což opět zajistíme externí silou. Pomocí externích sil se pak také dají simulovat různé interakce částic s ostatními objekty ve scéně (dopad vločky na zem). K realizaci sil je třeba zajistit mechanismus (nejspíše objekt), který na základě původních vlastností částice vypočítá nové, ovlivněné externí silou Většinou se mění pouze směr a rychlost částice (případně i energie, při nárazu částice do překážky a jejím následném zániku), avšak pro výpočet je potřeba více fyzikálních údajů o částici. Síly lze aplikovat postupně (tedy poslední síla vypočítá nové vlastnosti na základě vlastností již ovlivněných předchozími silami, což není úplně dobře), nebo lze použít dva stavy částice (stavem jsou myšleny hodnoty všech atributů) a jeden z nich použít jako původní pouze na čtení a druhý jako akumulátor změn původního stavu. Druhý způsob se pak dá i jednodušeji a rychleji paralelizovat. Protože vítr se v reálném světě neustále mění, mohou být také externí síly pružné a aktualizovat své vlastní atributy v každém snímku systému. 9

1.5

Interakce mezi částicemi

Jak již bylo řečeno dříve, pokud chceme simulovat složitější systémy (například reálnější vodu), nemůžou být částice mezi sebou úplně nezávislé. Interakce mezi jednotlivými částicemi probíhají obdobně jako aplikace externích sil na částici. Původní hodnoty částice budou pozměněné na základě vlastností druhé částice a atributů interakce. Opět se použije dvou stavový mechanismus aktualizace hodnot. Interakce se tedy na první pohled liší od externí síly jen tím, že výpočet vychází také z vlastností druhé částice, ale lze pomocí ní implementovat efekty jako je vzájemné přitahování, odpuzování, či kolize částic. Vzhledem k množství částic (stovky až tisíce) je téměř nemožné, aby šlo v reálném čase počítat interakce mezi všemi částicemi najednou (při jednom tisíci částic by šlo až o milion interakcí v jednom snímku). Proto je rozumné, aby částice ovlivňovala jen své nejbližší okolí (tedy jen určitý počet nejbližších částic nebo všechny částice do určité vzdálenosti, případně kombinace obojího). Tímto se dostáváme k problému, jak co nejrychleji získat všechny částice v nejbližším okolí dané částice. Musíme si vypomoci nějakou hierarchickou strukturou.

1.6

Hierarchické struktury

Existuje mnoho hierarchických struktur, které se používají pro rychlejší hledání nejbližších elementů nebo průchod všemi elementy seřazenými dle vzdálenosti od určitého bodu (roviny, objektu) v prostoru (pro naše účely jsou elementy pouze jednotlivé body). Zde si uvedeme několik z nich: • Octree Jedná se v podstatě o strom, který v každém uzlu dělí prostor (zde kvádr či krychle) na 8 částí (vždy jeden řez podle jedné osy, celkově tedy 3 řezy krychle). Uzel dělí prostor dokud to má smysl (tedy dokud je v dané části prostoru příliš mnoho bodů). Octree má mnoho variant, které se liší z hlediska umístění řezů (vždy v polovině prostoru, vedené nějakým bodem ve struktuře, či adaptivní – například medián pozice bodů), umístění bodů ve struktuře (v každém uzlu, nebo jen v listech) a maximálním počtem bodů uložených v jednom uzlu (takzvaná velikost bucketu). • K-D tree Opět jde o strom, který se však liší od octree tím, že je v každém uzlu dělen jen jedním řezem (opět podle jedné osy). Osy, podle kterých se dělí, 10

se pravidelně střídají. Existují různé varianty obdobně jako u octree. • BSP tree Další strom, sloužící jako hierarchická struktura, se liší od dvou předchozích tím, že nedělí v uzlu prostor řezem rovnoběžným s osou, ale libovolnou nadrovinou. Body jsou pak vždy uloženy v listech. • Grid Grid (mřížka) se od ostatních liší tím, že se nejedná o strom, ale pouze o rozdělení prostoru na stejně velké buňky. V každé buňce pak mohou být všechny body, nebo také žádný. Všechny struktury mají nějaké výhody a nevýhody. Na zde uvedených strukturách založených na stromech lze většinou implementovat mnohem rychlejší výše zmíněné algoritmy, než na mřížce a zároveň je počet bodů v jejich uzlech pevně omezený. Na druhou stranu se o mnoho pomaleji aktualizují při změně pozice částic (je pomalu lepší je postavit zcela znovu). Přesné znění algoritmu na průchod hierarchickou strukturou lze najít v kapitole 2 v sekci Hierarchický průchod mřížkou (algoritmy na průchod jiných struktur se příliš neliší).

Obrázek 1.2: 2D octree (quadtree, převzato ze [4]) 11

Obrázek 1.3: 2D K-D tree (převzato ze [4])

Obrázek 1.4: 2D BSP tree (převzato ze [4])

1.7

Obrázek 1.5: 2D grid (částečně převzato ze [4])

Aktualizace systému

Nyní již máme rozebrané jednotlivé části systému, můžeme se tedy podívat jak pracují dohromady. Aktualizace systému se dá rozdělit na čtyři části, které se opakují při každém snímku simulace: 1. Vygenerování nových částic v systému pomocí emitorů. 2. Aplikování externích sil a interakcí na jednotlivé částice. Při dvou-stavové aktualizaci se pouze akumulují změny v novém stavu. Původní stav částice, ze kterého výpočet sil a interakcí vychází, zůstává nezměněn. 3. Samotná aktualizace, čili změna původního stavu částic (nahrání akumulovaných vlastností do původního stavu, změna pozice v závislosti na rychlosti atd.) a případná aktualizace použitých hierarchických struktur, externích sil a interakcí. 4. Vykreslení. Pro větší rychlost částicových systémů lze některé kroky paralelizovat. V prvním kroku dochází k přidávání částic do systému, pokud by toto místo běželo na více vláknech současně, musely by se struktury určené na uložení částic neustále odmykat a zamykat, což by nebylo příliš efektivní. To samé platí o třetím kroku. 12

Druhý krok je naopak velice výhodné paralelizovat, protože pokud pouze jedno vlákno aplikuje interakce a síly na jednu částici, tedy mění pouze ono nový stav (akumulátor) a původní stav slouží ostatním vláknům pro čtení, nemusí se tedy jednotlivé částice zamykat. Vykreslení pak lze jednoduše spustit na více vláknech, pokud jdou částice vykreslovat v libovolném pořadí (viz další kapitola).

1.8

Vykreslování

Pro vykreslení jedné částice na obrazovku máme více možností, zde uvedu ty nejčastěji používané: • Body Body mohou být použity pro jednodušší simulace na pomalejší strojích, případně pro efekty, které jsou velmi vzdálené od pozorovatele. • Čáry Čáry se používají například na zobrazení blesků, laserů, apod. Většinou se jedná o úsečku mezi původní a novou pozicí částice. • Otexturované obdélníky Jedná se o nejčastěji používané řešení, protože je nejvíce flexibilní. Využívá se takzvaného billboardingu k tomu, aby čtverec byl vždy natočen směrem k pozorovateli (více o tom, jak se dá například implementovat billboarding, je v kapitole 2 sekci Vykreslovací buffer). Aby částice nevypadala jako čtverec, ale naopak jako například sněhová vločka, musí se využít alpha-blendingu (černá barva textury bude znamenat průhlednou nebo bude přímo použita RGBA textura s hodnotou průhlednosti alpha v každém pixelu). • Point sprites V některých grafických knihovnách (například OpenGL) je již billboarding implementován pomocí point sprites. Takovýto bod se zobrazí dostatečně tučně na to, aby mohl být otexturován. Díky tomu, že je přímo hardwarově podporován, se jedná o rychlejší variantu předchozích obdélníků, avšak má i některé nevýhody. Například při dávkovém kreslení nelze měnit jeho velikost a tudíž by musely být částice všechny stejně velké nebo být vykreslovány po jedné (toto však lze vyřešit pomocí vertex shaderů) a dále pak jakmile střed bodu není vidět, zmizí i jeho zbytek. 13

• Metaballs Jsou používané hlavně při offline renderovaní tekutin simulovaných částicovými systémy (použije se isosurface spočítaný právě z částic reprezentovaných metabally). • 3D Mesh 3D objekt složený z trojúhelníků může samozřejmě také sloužit k vykreslení částice, avšak nejedná se o příliš efektivní řešení. Při vykreslování průhledných otexturovaných obdélníků nebo point sprites je třeba dát pozor na jejich pořadí ve scéně. Aby byla správně vypočtena výsledná barva, musí být vykreslovány odzadu (nebo odpředu v závislosti na použitém výpočtu průhlednosti). Částice buď můžeme pokaždé setřídit běžným algoritmem nebo výhodně využít dříve zmíněných hierarchických struktur, které nám jejich setřídění urychlí.

1.9

Skriptování

Pro větší univerzálnost a flexibilitu částicového systému je vhodné přidat podporu skriptování, které umožní změnit parametry systému bez nutnosti rekompilace a umožní tak i oddělit programátora grafické aplikace a samotného grafika. Komplexní skriptování by mělo umožnit hlavně následující části: • Počáteční nastavení systému V této části skriptu by měly jít nastavit všechny počáteční vlastnosti částicového systému, jako je například: maximální počet částic, nastavení parametrů hierarchických struktur, způsob výpočtu všech externích sil a interakcí apod. • Emitory Pro každý emitor v systému by měly jít nastavit všechny jeho vlastnosti včetně počátečního nastavení jím emitovaných částic (s určenými náhodnými odchylkami vlastností). • Události Tato část by nám měla dovolit pozměnit chování systému v závislosti na jakékoliv události, například: dle aktuálního snímku, při určité změně dané vlastnosti systému (emitoru apod.) nebo při interakci (kolizi) dvou částic. 14

• Aktualizace Skript může definovat i přesně jak se mají jednotlivé částice (případně i externí síly, interakce) aktualizovat, pokud to již není pevně dáno vlastnostmi (například pokud máme definované delta hodnoty pro každou vlastnost). Pro potřeby skriptování je možné vymyslet si vlastní skriptovací jazyk a přesně definovat jeho syntax (jak je tomu například v [3]), nebo lze použít již existující jazyk (například python) a v něm volat potřebné metody napsané ve stejném jazyce jako zbytek implementace částicových systémů (C, C++ . . . ).

1.10

GPU implementace

Částicové systémy, které obsahují desítky tisíc částic, již mohou být velice pomalé, a to často z důvodů pomalého přesunu dat mezi CPU a GPU. Abychom odstranili tento bottleneck, můžeme část implementace přesunout na GPU. Částicové systémy běžící na GPU můžeme rozdělit na 2 druhy: • Bezstavový (Stateless) V tomto případě si gpu nepamatuje stav jednotlivých částic (pozici, rychlost, apod.), ale v každém novém snímku se musí spočítat pomocí funkcí, které jsou závislé jen na pár parametrech (samotný výpočet se definuje pomocí vertex shaderů). • Stavový (State-preserving) Jedná se o silnější metodu. Stav částicového systému je uložen ve floatingpoint texturách (jedna textura reprezentuje souřadnice částic, další pak vektor směru a rychlosti, nastavení systému, atd.), výpočet nové pozice pak probíhá ve fragment shaderu. Jakmile jsou textury s pozicí aktualizovány, jsou poslány do vertex bufferu, aby byly grafickou kartou interpretovány jako souřadnice. Abychom měli jednodušší práci ve vertex shaderu, je lepší použít point-sprites, jelikož máme definován vždy jen jeden bod na částici. Stavový částicový systém zároveň umožňuje i skriptování, v programu stačí jen měnit textury, ve kterých je uloženo nastavení systému. Více o tomto tématu se lze dočíst v [3].

15

1.11

Offline simulace

Často se stává, že částicový systém je natolik výpočetně náročný, že se nedá simulovat v reálném čase (online). Potom přichází na řadu offline simulace. Máme v podstatě dvě možnosti: • Předpočítání stavů Pokud nás netrápí výkon vykreslovací části (nemáme příliš mnoho částic), ale výpočet nové pozice částice a jejích další vlastností zabírá spoustu času, můžeme si předem spočítat stavy všech částic v průběhu času a uložit si jen data potřebná k vykreslení dané částice v každém snímku. Takto uložené stavy mezi sebou nemusí nijak korespondovat a navíc můžeme pro každý snímek při ukládání postavit zvlášť hierarchickou strukturu, která nám umožní rychlejší vykreslování. Při přehrávání pak můžeme takto uloženou simulaci libovolně natáčet, zrychlovat, přibližovat, ale i přehrávat pozpátku. Jedinou nevýhodou je často extrémně velké množství dat, která se musí uložit a následně i velice rychle nahrát. • Úplnou offline simulaci Pokud je nejen výpočet nových stavů částic příliš složitý, ale posléze také vykreslování je náročné na výkon, zbývá nám pouze možnost vykreslení jednotlivých snímků do paměti a posléze jejich překonvertování na video nebo jiné zpracování.

1.12

Cíle práce

Ve své práci jsem se zaměřil na implementaci knihovny, která by umožňovala vytvoření složitějších částicových systémů pomocí dědičnosti. Čili uživatel knihovny musí vytvořit celkem jednoduché objekty svých částic, emitorů, apod., které dědí od obecných tříd definovaných v mé knihovně. Dále jsem svou pozornost upíral na možnost přidání nejen externích sil, ale také interakcí a tudíž i využití urychlující hierarchické struktury. Rozhodl jsem se taktéž využít možnosti dnešních více jádrových procesorů k dalšímu urychlení výpočtu interakcí a externích sil. Pro obzvláště složité výpočty jsem pak implementoval možnost uložení spočítaných stavů jednotlivých částic a posléze jejich přehrání. Více o implementaci knihovny se dozvíte v kapitolách 2 a 3. K prezentaci knihovny jsem vytvořil dvě aplikace. První z nich slouží k přehrávání online simulací a jejich ukládání na pevný disk, druhá pak jako přehrávač 16

uložených částicových systémů. Jejich ovládání je podrobně rozebráno v dodatku B. Dále jsem připravil pět ukázkových simulací, které prezentují možnosti mé knihovny.

1.13

Ukázky mnou implementovaných systémů

• Colors Jedná se pouze o zátěžový test, ve kterém se vyskytuje až 40 tisíc průhledných částic, které jsou korektně zobrazené (čili setříděné odzadu dopředu). Simulace dovoluje jednoduché přepínání způsobu emitování částic (náhodné, kruhové, rotující).

Obrázek 1.6: Náhodné emitování 40 tisíc částic • Explosion Tato simulace zobrazuje jednoduchý systém reprodukující explozi.

Obrázek 1.7: Exploze 17

• Fireworks Simulace ohňostroje je již o něco málo složitější. Každých 500 snímků je vystřeleno směrem vzhůru 5 rachejtlí, ty se po čase rozletí na další menší rachejtle, které se nakonec rozprsknou na malé jiskry. Každá rachejtle má pak ohon z jisker, které se řítí zpět na zem pomocí gravitace implementované externí silou.

Obrázek 1.8: Rachejtle pozorované zespodu těsně před výbuchem • Bombardment Zde máme první simulaci, která prezentuje interakce mezi částicemi. Celkově jsou zde 3 typy částic: 1. Zelené částice – ty se mezi sebou přitahují, pokud jsou pak příliš blízko sebe, začnou se odpuzovat a udržují si tak ideální vzdálenost. 2. Střely – střela může být vyslána směrem k zeleným částicím, které po dopadu zničí a přitom následný výbuch emituje poslední uvedené částice. 3. Částice výbuchu – tyto částice míří směrem pryč od centra exploze a po cestě rozrážejí zelené částice.

18

Obrázek 1.9: Deformace objektu ze zelených částic • Liquids Poslední simulace se snaží reprodukovat dvě jednoduché tekutiny. Jednotlivé částice tekutin se přitahují a odpuzují obdobně jako zelená částice v předchozí simulaci, navíc však na ně působí gravitační a třecí síla. Obě tekutiny lze nalít do scény, ze které nevyskočí díky bariéře implementované externí silou.

Obrázek 1.10: Modrá tekutina reprezentovaná částicemi

19

Kapitola 2 Základní architektura a algoritmy online simulace 2.1

Reprezentace částice

Částice je reprezentována v systému pomocí abstraktní třídy Particle a tedy k vytvoření funkční částice je třeba od ní dědit. V této základní třídě je rovněž uložen nový a původní stav částice (reprezentován pomocí třídy ParticleState), který má v sobě uloženy její základní vlastnosti: 1. Pozici v systému (3D bod) 2. Rychlost a směr pohybu (třísložkový vektor) 3. Velikost a směr zrychlení (třísložkový vektor) 4. Velikost 5. Váhu 6. Energii (částice s energií větší než 0 budu dále nazývat živé, naopak částice s nulovou energií nazvu mrtvé a nebudu je nadále zobrazovat a aktualizovat) V potomkovi je rovnou přístupný nový stav částice na přímé změny, původní stav je přístupný všem, ale pouze pro čtení. Třída Particle má následující důležité metody :

20

• Particle (konstruktor): má pouze jeden nepovinný parametr, a to číselnou konstantu, která slouží jako rychlý identifikátor typu částice (o využití typu se dále mluví v sekci Síly a interakce). • Init: přijme jako parametr stav částice a nastaví podle něj nový i původní stav, zároveň zavolá CustomInit(viz popis níže). Tato metoda je důležitá pro inicializaci stavu částice bez volání konstruktoru (důvod k tomuto způsobu inicializace naleznete v sekci Typ částice). • CustomInit: virtuální metoda přijímající stav částice, která umožňuje inicializaci dalších jejích vlastností. Stav částice je navíc přijímán referencí, čili lze použít mechanismus dědění k možnosti poslání dalších vlastností skrze poděděný stav částice (uložení takovýchto vlastností v částici však již musí být realizováno jinak). • CollectForces: přijímá jako parametry všechny síly a interakce v systému, maximální dosah interakcí a iterátor procházející přes částice v okolí této částice(více o iterátorech v sekci Iterátory na mřížce). V základním provedení volá BasicCollectForces se stejnými parametry, ale díky tomu, že je virtuální, lze změnit její chování a kupříkladu posílat do BasicCollectForces pouze některé síly a interakce. • BasicCollectForces: přijímá stejná parametry jako CollectForces. Více o algoritmu v sekci Aplikace interakcí a sil. • Update: zaktualizuje stav částice : zavolá CustomUpdate(viz popis níže), změní v novém stavu částice pozici v závislosti na rychlosti, rychlost v závislosti na zrychlení a sníží energii o 1. Nakonec se okopíruje nový stav do původního. • CustomUpdate: virtuální metoda umožňující tvůrci nové částice update ostatních vlastností neuložených v základním stavu částice. • Draw : přijímá jako parametr odkaz na rozhraní ParticleDrawer, ve kterém je definována metoda DrawParticle sloužící k vykreslení částice do vykreslovacího bufferu (více o vykreslovacím bufferu v sekci Vykreslovací buffer). Tato metoda je čistě virtuální, proto musí být v potomkovi částice definována.

21

2.2

Typ částice

Kvůli zrychlení vytváření a odstraňování částic (částice se alokují po jedné na haldě) byla zavedena třída ParticleType. Tato třída se stará o to, aby částice po odstranění nebyly rovnou smazány z haldy, ale byly případně znovu inicializovány (viz metoda Init třídy Particle) při vytváření částice nového typu. Místo aby měl každý typ částice zvláštní buffer, používá se jen hlavní buffer uložený v mřížce (třída Grid - viz sekce Buffer částic a urychlovací mřížka) a pomocí ukazatelů je v něm uložen seznam částic stejného typu. Každá položka v bufferu má ukazatel na předchozí a následující částici stejného typu (jedná se vlastně o dva seznamy - dosud živé částice ukazují pouze na živé stejného typu, mrtvé částice pak zase pouze na mrtvé). V objektu typu částice si pak jen pamatujeme ukazatel na první živou a první mrtvou částici daného typu. Aby ParticleType mohl alokovat novou částici na haldě (pokud nemá žádné mrtvé v seznamu), musí umět zavolat správný konstruktor. K tomu slouží funkce typu AllocParticleFunction a AllocEmittingParticleFunction. První slouží k vytváření základních částic, kdežto druhá má parametr přijímající odkaz na objekt typu EmitterProtocol a slouží k vytvoření emitujících částic (více o takových částicích se dozvíte v kapitole Emitor částic). Funkci jednoho z těchto dvou typů musí dodat programátor do konstruktoru ParticleType (v případě, že chce vytvářet emitující částice, musí ještě dodat odkaz na objekt typu EmitterProtocol ). Třída ParticleType má pak následující metody, které umožňují vytvářet nebo mazat částice: • AwakeParticle: přijímá jako parametr stav částice a zkouší znovu inicializovat mrtvou částici daného typu, zařadit ji mezi živé a vrátit ukazatel na místo v bufferu, kde se nachází. Pokud není k dispozici žádná mrtvá částice daného typu, vrací nulový ukazatel. • CreateParticle: přijímá jako parametry referenci na volné místo v bufferu a stav částice. Alokuje částici na haldě pomocí jedné z výše zmíněných funkcí, zařadí ji mezi živé částice stejného typu a uloží do bufferu. • SuspendParticle: přijímá jako parametr referenci na místo s částicí daného typu v bufferu a přemístí částici ze živých mezi mrtvé (metodu lze volat jen na doposud živé částice). • DeleteParticle: přijímá jako parametr referenci na místo s částicí daného typu v bufferu, odstraní částici ze seznamu mrtvých i z haldy (metodu lze volat jen na mrtvé částice). 22

• PreallocateParticles: přijímá jako parametr seznam volných míst v bufferu (propojené ukazately), do kterých má vytvořit nové částice, které zatím nebudou inicializovány, ale budou připravené na rychlé oživení pomocí AwakeParticle. Díky této metodě lze emitování nových částic ještě zrychlit (pokud však známe zhruba přibližné počty částic jednotlivých typů v simulaci).

2.3

Buffer částic a urychlovací mřížka

O uložení částic se v mé knihovně při online simulaci stará třída Grid, které se v konstruktoru nastaví rozměr prostoru (mřížky), ve kterém se mohou částice pohybovat, jeho rozdělení na krabice (uvedené počtem krabic ve třech rozměrech) a maximální počet částic v celé simulaci. Takovéto rozdělení prostoru je důležité pro rychlejší hierarchické procházení (více o tom v sekci Hierarchický průchod), mřížku jsem si pak vybral z mnoha jiných struktur proto, že se nejrychleji ze všech aktualizuje (což je třeba kvůli časté změně pozic částic). Zvenku lze pak k částicím přistupovat pomocí iterátorů, o kterých si blíže povíme v následující sekci Iterátory na mřížce. Grid pak také implementuje rozhraní EmitterProtocol, které definuje metodu EmitParticle a PreallocateParticles. Tyto metody jsou pak používány všemi emitory (sekce Emitor částic) k emitování nových částic. Vnitřně jsou částice uloženy v bufferu pevně dané velikosti. Položky bufferu jsou struktury ParticleSlot, které v sobě drží tyto informace: • Ukazatel na částici (potomek Particle třídy). • Ukazatel na typ částice (ParticleType objekt viz sekce Typ částice). • Ukazatele na předchozí a další částici (slouží na vytvoření seznamů mrtvých částic a živých odděleně, to znamená, že živé částice ukazují pouze na živé a mrtvé naopak). • Ukazatele na předchozí a další částici stejného typu (použití viz kapitola Typ částice). • Ukazatele na předchozí a další částici ve stejné krabici (každá živá částice musí být právě v jedné krabici). • Ukazatel na krabici, ve které se částice nachází (nulový ukazatel, pokud je částice mrtvá). 23

Dále je v mřížce uložen seznam krabic (třída BoundingBox ), které se chovají jako sekundární úložiště částic, avšak ve skutečnosti se odkazují jen na hlavní buffer. Třída BoundingBox má definované metody, které umožňují přidání i odebrání částice do krabice, návrat první částice v krabici (a dále díky ukazatelům v ParticleSlot lze pak projít všechny částice v krabici), apod. Navíc je v mřížce uložen sekundární buffer ukazatelů částic pevné velikosti, který v sobě udržuje pouze živé částice pro rychlejší přístup. Tento buffer je postupně plněn při použití UpdateIterator (více viz kapitola Iterátory na mřížce) a při emitování nových částic. Nyní, když víme, jak jsou částice v mřížce uloženy, můžeme si povědět o jejich vytváření a mazání. Pro vytvoření částice se volá výše zmíněná metoda EmitParticle, která přijímá jako parametry typ částice, kterou chceme emitovat (ParticleType objekt) a počáteční stav částice (viz kapitola Typ částice). Funkce pak vrací ukazatel na vytvořenou částici nebo v případě nedostatku místa v bufferu nulový ukazatel a funguje dle následujícího schématu:

Obrázek 2.1: Emitování částice Protože například vytvoření prvních tisíců částic najednou může být pouze pomocí samostatného volání metody EmitParticle pomalé, může emitor využít metody PreallocateParticles, která dostane jako parametr typ částic a jejich počet a slouží k přípravě rychlejšího emitování částic. Uvnitř PreallocateParticles 24

se nejdříve zkontroluje dostupné místo v bufferu (pokud je menší než počet částic, připraví se jich pouze tolik, kolik se vejde), prodlouží se seznam mrtvých částic a poté pomocí metody stejného jména objektu typu ParticleType se do přidané části seznamu nahrají nově alokované částice. Po následujících volání EmitParticle se nemusí již nic alokovat a simulace je plynulejší. Ke smazání částice pak slouží metoda KillParticle, která přijímá jako parametr referenci na místo v bufferu s částicí. Tato metoda přesune částici mezi mrtvé, odstraní ji z krabice a zavolá na částici v objektu jejího typu SuspendParticle (čili částice není smazána uplně, ale pouze uschována pro budoucí znovupoužití). Pokud chceme smazat všechny částice, stačí zavolat metodu Clear. Jak již bylo řečeno v předchozí kapitole, lze alokovat částice dopředu kvůli zrychlení simulace. K tomu slouží metoda PreallocateParticles. Zbývající metody mřížky budou osvětleny v následující kapitole.

2.4

Iterátory na mřížce

Jak bylo zmíněno již v předchozí kapitole, iterátory slouží k průchodu částic uložených v mřížce. Všechny iterátory mají velice podobné základní rozhraní : • Init: inicializuje iterátor na začátek (kromě iterátoru LimitedIterator nepřijímá žádné parametry). • Current: vrací částici (odkaz na kvantum částic v případě iterátoru QuantumIterator ), na kterou právě iterátor ukazuje. • SelectNext: posune iterátor na další částici (nebo kvantum). • End : vrací true, pokud iterátor projel všechny částice. Na mřížce je definováno těchto 6 iterátorů: • BasicIterator : prochází skrze všechny živé částice (od nejmladší po nejstarší). • QuantumIterator : taktéž prochází skrze všechny živé částice (pořadí průchodu není definováno), ale skáče vždy po několika částicích (počet je definován nastavením velikosti kvanta v konstruktoru) a vrací ukazatel pomocí kterého lze iterovat přes částice v jednom kvantu.

25

• BoxIterator : prochází skrze všechny živé částice seřazené podle toho, v jaké krabici se nacházejí (zároveň vrací aktuální zpracovávanou krabici pomocí metody CurrentParticleBox ), což se hodí pro ukládání simulace na disk (více viz kapitola 3 sekce Formát souboru offline simulace). • UpdateIterator : navenek se chová stejně jako BasicIterator (iteruje přes všechny živé částice od nejmladší po nejstarší), ale jako jediný iterátor dovoluje změnu stavu právě zpracovávané částice. Při zavolání metody SelectNext se zkontroluje energie a pozice doteď zpracovávané částice. Pokud částice opustila mřížku nebo jí došla energie zavolá se na její slot KillParticle, jinak se pouze případně přesune částice do jiné krabice a zařadí se do sekundárního bufferu živých částic. • FromOriginIterator : prochází všechny částice seřazené dle vzdálenosti od zvoleného počátku (od nejbližší po nejvzdálenější). K nastavení a čtení aktuálního počátku (3D bod) slouží metody mřížky SetOrigin a GetOrigin. • LimitedIterator : stejně jako FromOriginIterator prochází částice seřazené dle vzdálenosti, ale počátek lze nastavit každému iterátoru zvlášť a navíc lze omezit maximální vzdálenost částic. Kvůli tomu, že se tento iterátor používá na procházení nejbližších částic od dané částice (viz sekce Aplikace interakcí a sil), lze i nastavit vynechání této částice z iterace. Všechny tyto parametry se nastavují v metodě Init. Od každého iterátoru lze vytvořit více instancí a procházet nezávisle na sobě, kromě iterátorů UpdateIterator a FromOriginIterator, které nelze vytvořit, ale pouze získat pomocí metod mřížky GetUpdateIterator resp. GetFromOriginIterator. Zároveň je důležité mít na paměti, že vyjma UpdateIterator nesnese žádný iterátor změnu stavu částice (řeč je o takzvaném původním stavu, viz sekce Reprezentace částice, nový stav se může měnit kdykoliv). Bližší informace o tom, jak uvnitř fungují iterátory FromOriginIterator a LimitedIterator, lze najít v následující sekci Hierarchický průchod mřížkou.

2.5

Hierarchický průchod mřížkou

Hierarchický průchod mřížkou se používá v mé knihovně jednak k aplikaci interakcí (zajištěno iterátorem LimitedIterator ) a také k zajištění správného vykreslení průhledných částic (čili odzadu dopředu - iterátor FromOriginIterator ).

26

Nejdříve si popíšeme základní myšlenku algoritmu, a pak si řekneme drobné odlišnosti dle použití průchodu. K provedení průchodu potřebujeme primární frontu, do které budeme vkládat částice i celé krabice s částicemi (to zajišťuje třída OWMD, která může v sobě obsahovat buď krabici nebo částici a má metody na zjištění jejich vzdálenosti od daného 3D bodu). Kvůli co nejvyšší rychlosti jsem použil klasickou haldu uloženou v poli pevné velikosti (třída PrimaryQueue), pomocí makra MSPS PRIMARYQUEUE 4ARY se dá pak nastavit 4-cestná halda místo 2cestné haldy (což ale podle mých pozorování má minimální vliv na výkon). Základní algoritmus: 1. Vlož všechny neprázdné krabice do primární fronty. 2. Dokud není prázdná fronta, opakuj kroky 2 až 4. 3. Vyber první prvek z fronty, pokud se jedná o krabici, vlož všechny částice z krabice do primární fronty, pokud je na vrchu částice, vrať ji pro další zpracování. 4. Vrať se do kroku 2. Algoritmus použitý v FromOriginIterator se liší od výše uvedeného tím, že první krok algoritmu se provádí pouze při změně počátku (metoda mřížky SetOrigin). Místo, abychom vkládali každou krabici zvlášť do fronty, vložíme je bez zatřiďování (jako bychom je vkládali za sebe do pole) a poté zavoláme metodu primární fronty makeHeap, která postaví haldu v lineárním čase. Při každé inicializaci iterátoru FromOriginIterator pak pouze nakopírujeme haldu krabic do haldy použité v algoritmu. Do haldy krabic je třeba dát i prázdné krabice, protože částice mohou měnit svou polohu, bez toho aby někdo změnil počátek zobrazování. Nyní si blíže popíšeme jak uvnitř pracuje LimitedIterator. Protože chceme většinou procházet pouze nejbližší okolí dané částice, nechceme přidávat do primární fronty všechny krabice (bylo by to příliš pomalé), stačí tedy přidat pouze krabice z okolí částice. Upravený algoritmus pak vypadá takto: 1. Zjisti krabici, ve které leží počátek průchodu (vždy je v mřížce). 2. Vezmi částice z prvotní krabice a dále vezmi okolní krabice, které jsou dostatečně blízko a vytvoř z nich haldu. 3. Dokud není prázdná fronta, opakuj kroky 3 až 5. 27

4. Vyber nejbližší prvek z fronty, pokud se jedná o krabici, vlož všechny částice z krabice do primární fronty, pokud je na vrchu částice, vrať ji. 5. Vrať se do kroku 3. Při kalkulaci vzdálenosti dvou bodů (i jednoho bodu od krabice) se musí použít odmocnina, která je výpočetně náročná, proto nebudeme počítat přesnou vzdálenost, nýbrž jen její druhou mocninu. Díky tomu, že platí vzdálenost(s, a) < vzdálenost(s, b) =⇒ vzdálenost(s, a)2 < vzdálenost(s, b)2 se nám nic nepokazí.

2.6

Emitor částic

K emitování nových částic je v mé knihovně zapotřebí vytvořit objekt, který dědí buď od třídy Emittor nebo od třídy EmittingParticle (každý částicový systém však potřebuje alespoň jednoho potomka Emittor ). K tomu, abychom mohli v emitoru říci, že chceme vytvořit novou částici, slouží objekt s rozhraním EmitterProtocol, který se musí předat emitoru skrze protected konstruktor. Objekt splňující toto rozhraní (což je třída Grid, jak jsme si již řekli v předchozí kapitole Buffer částic a urychlovací mřížka) lze získat od hlavního objektu částicového systému voláním metody GetEmitterProtocol. Rozhraní potom definuje metodu EmitParticle, které se předá reference na typ a počáteční stav částice, a ta vrátí ukazatel na nově vytvořenou částici, nebo nulový ukazatel v případě neúspěchu. Více o mechanismu vytváření nových částic (včetně další metody rozhraní PreallocateParticles) se dočtete v sekci Buffer částic a urychlovací mřížka). Programátor nového emitoru musí zajistit, že nové částice se emitují vždy ve virtuální metodě EmitParticles a emitor se dá resetovat do počátečního stavu pomocí metody Reset. Vytvořený emitor se potom předá pomocí metody částicového systému AddEmitter (společně se jménem, odstranit ho pak lze pomocí DeleteEmitter, částicový systém při tom sám uvolní paměť). V potomkovi EmittingParticle pak musí být všechny nové částice vytvořeny během metody CustomUpdate.

2.7

Síly a interakce

K přidání síly nebo interakce do částicového systému je třeba vytvořit potomka od příslušné třídy (Force, respektive Interaction) a toho předat metodě AddForce

28

(resp. AddInteraction) spolu se jménem (odebrat je lze pomocí DeleteForce, respektive DeleteInteraction). Dále si popíšeme, na co je potřeba dbát při vytváření těchto objektů. Co se týče objektu, který reprezentuje sílu, je potřeba implementovat 3 metody definované v třídě Force: • Update: metoda volaná pokaždé jednou za update cyklus (viz Update systému), umožňuje měnit sílu v průběhu simulace • Reset: metoda, kterou se resetují případné změny v síle • ApplyForceOn: nejdůležitější metoda, volá se na každou částici v systému, na kterou je aplikována tato síla. Přijímá jako první parametr původní stav částice pouze pro čtení, jako druhý parametr pak nový stav částice, který může síla libovolně pozměnit, a jako třetí jednoduchý typ částice (síla se například může chovat na různé částice jinak). Pokud nemá částice definovaný tento typ, dostane metoda jako hodnotu typu konstantu MSPS PARTICLE UNDEFINED TYPE. Objekt reprezentující interakci mezi dvěma částicemi je trochu složitější. Při vytváření interakce je potřeba předat konstruktoru Interaction maximální dosah interakce a maximální počet částic interagujících s jednou libovolnou částicí (tyto hodnoty lze pak nazpět získat pomocí metod getMaxDistance a getMaxParticles). Opět je nutné implementovat 3 metody, přičemž metody Update a Reset mají stejný význam jako u síly. Třetí metodou je Interact, která má jako parametry původní konstantní stav i měnitelný nový stav jedné částice a její typ a pouze pro čtení původní stav druhé částice a taktéž její typ, vždy lze tedy ovlivňovat pouze jednu částici tou druhou. Na konci metody při úspěšné interakci je potřeba zavolat protected metodu IncrementCount a tím oznámit objektu, že další částice byla zpracována (důležité pro omezení počtu interagujících částic). Další informace o silách a interakcích poskytne následující kapitola.

2.8

Aplikace interakcí a sil

Zde si popíšeme algoritmus aplikace všech interakcí a sil na jednu částici (v podstatě zde popíšeme metodu BasicCollectForces třídy Particle již zmíněné v kapitole Reprezentace částice). K dispozici máme seznam sil a seznam interakcí, největší hodnotu dosahu interakcí a iterátor LimitedIterator pro průchod blízkých částic (viz Iterátory na mřížce). Algoritmus se skládá z těchto kroků: 29

1. Nejdříve začneme zpracovávat interakce. Inicializujeme výše zmíněný iterátor počátkem určeným pozicí naší částice, největší hodnotou dosahu interakcí a odkazem na naši částici, aby se mohla přeskočit při iteraci. Nastavíme si ukazatel start na první interakci. 2. Zavoláme na každé interakci její metodu ResetCountParticles, která nastaví počet částic zpracovaných interakcí na nulu. 3. Dokud neskončí iterace (nebyly vráceny všechny částice z určeného okolí) opakuj kroky 3 – 9. 4. Pro každou interakci od start do poslední opakuj kroky 4 – 7. 5. Získáme vzdálenost právě zpracovávané částice (to jest ta vrácená iterátorem) od naší částice a zavoláme na ní metodu aktuální interakce OutOfLimits, která vrátí true pokud je částice příliš vzdálená nebo už byl zpracován maximální počet částic. 6. Jestliže OutOfLimits vrátila true a jedná se o interakci na kterou ukazuje start, posuň start na další interakci (jde o drobné zrychlení, již zpracované interakce nacházející se na začátku seznamu nebudu testovat znova). Naopak, vrátila-li false, zavolám metodu interakce Interact. 7. Návrat do kroku 4. 8. Pokud není ukazatel start roven konci seznamu interakcí (čili všechny byly zpracovány), posuň iterátor na další částici. 9. Návrat do kroku 3. 10. Nakonec aplikujeme postupně všechny síly na částici pomocí metody ApplyForceOn třídy Force. Jak se dozvíme později, je tento postup aplikován na částice paralelně, proto je zapotřebí, aby počet částic zpracovaných interakcí byl pro každé vlákno uložen zvlášť. To je zajištěno přímo v třídě Interaction, která používá třídy ThreadLocal knihovny ZThreads na vytvoření zvláštní proměnné pro každé vlákno. Je vidět z popisu algoritmu, že je výhodné mít setříděné interakce tak, aby na začátku byly ty, které se zpracují rychleji (tedy ty s menším maximálním počtem částic a menším dosahem). Proto jsou v částicovém systému interakce tříděny vzestupně podle dosahu a pak podle maximálního počtu zpracovaných částic. 30

2.9

Vykreslovací buffer

K vykreslování všech částic v systému se využívá buffer realizovaný třídou DrawBuffer. Pokaždé když je třeba překreslit scénu (update systému nebo třeba jen natočení scény s částicemi), zavolá uživatel knihovny metodu částicového systému RefreshDrawBuffer. K přístupu (pouze konstantnímu) k bufferu lze pak volat metodu GetDrawBuffer. Při vytváření DrawBuffer je třeba zadat maximální počet zobrazených částic a zároveň počáteční nastavení billbordu (více o tom dále). Uvnitř třídy DrawBuffer je každá částice uložena pomocí čtveřice bodů, které reprezentují čtverec. K tomu, aby tento čtverec (Billboard) byl vždy natočen směrem ke kameře a vytvářel tak dojem, že částice je 3D, musí buffer dostávat informace o natočení scény. Ty dostane pomocí metody SetBillboard (tu volá přímo částicový systém) v podobě dvou vektorů, které určují směr vzhůru a směr vpravo od kamery (viz obrázek).

Obrázek 2.2: Kamera a billboard vektory Z těchto vektorů se pak spočítají normalizované vektory mířící od středu ke krajům billboardu umístěného v počátku souřadného systému, které potom stačí vynásobit velikostí částice a přičíst k nim její pozici a získat tak souřadnice finálního billboardu. K uložení částice do bufferu se používá metoda DrawParticle definovaná v rozhraní ParticleDrawer, kterou musí volat částice ve své metodě Draw (ta dostane jako parametr právě rozhraní ParticleDrawer ). Metoda DrawParticle má následující parametry: 1. Pozici částice v systému (3D bod). 2. Pole texturových koordinát (4 složky definující 2D souřadnice textury ve formě horního levého rohu (0,1) a pravého dolního rohu (2,3)). 31

3. Velikost částice. 4. Barvu ve formátu RGBA (Red Green Blue Alpha v hodnotách od 0 do 255). Z takto získaných parametrů pak uloží 4 vrcholy billboardu do bufferu ve formátu 2 texturové koordináty, 4 barvy, 3D bod na každý vrchol (což při použití GLfloat jako přesnosti systému odpovídá formátu GL T2F C4UB V3F knihovny OpenGL). K datům uložených do bufferu pak může uživatel přistupovat různými metodami : 1. InterleavedBufferStart, která vrací odkaz na začátek bufferu s kompletní informací o vrcholech (viz výše zmíněný formát). 2. TextureCoordinatesBufferStart, která vrací odkaz na první dvojici texturových koordinát v bufferu. Na další dvojici se lze pak přesunout pomocí přičtení hodnoty vrácené metodou TextureCoordinatesStride k bufferu. 3. ColorsBufferStart, která vrací odkaz na první RGBA hodnoty v bufferu, další lze opět získat pomocí přičtení ColorsBufferStride k bufferu. 4. VertexBufferStart, která vrací odkaz na první souřadnice vrcholu v bufferu (další pomocí VertexBufferStride) Buffer navíc vrací aktuální počet částic v bufferu metodou GetParticlesCount a lze ho vyprázdnit pomocí ResetBuffer. Ve své implementaci jsem se tedy rozhodl upřednostnit otexturovaný čtverec před point sprites a to hlavně z důvodu nemožnosti měnit velikost point sprites při rychlejším dávkovém vykreslování (pokud však uživatel chce vykreslovat pomocí point sprites, nemusí používat vykreslovací buffer a volat kreslení spritů přímo v metodě částice Draw ).

2.10

Částicový systém

Zde si konečně popíšeme hlavní třídu knihovny ParticleSystem. Na začátku při vytváření částicového systému je potřeba předat konstruktoru tyto parametry: • Maximální počet částic (slouží k určení velikosti bufferů v mřížce a ve vykreslovacím bufferu).

32

• Počátek vykreslování (řídí se dle něj vykreslovací iterátor FromOriginIterator viz Iterátory na mřížce). • Vektory kamery (důležité pro vykreslovací buffer viz předchozí kapitola). • Velikost mřížky a počet krabic v mřížce (předáno mřížce viz Buffer částic a urychlovací mřížka). • Nastavení zapnutí/vypnutí aplikování sil a interakcí na částici. • Nastavení zapnutí/vypnutí rychlého vykreslování (to znamená, že se částice nekreslí od nejvzdálenější od počátku, ale nedefinovaně v lineárním čase). • A dále dva parametry pro případné použití více vláken (to se musí aktivovat makrem MSPS MULTI THREADING): nastavení počtu vláken a počet částic v jedné dávce zpracovávané jedním vláknem (viz následující kapitola). V konstruktoru se dále spustí všechna pomocná výpočetní vlákna, která se ihned uspí. Částicový systém má pak tyto důležité metody: • Metody Add* a Delete* na přidání (resp. odebrání) emitorů, sil a interakcí (viz předchozí kapitoly). • Metody na nastavení zapnutí/vypnutí rychlého vykreslování a aplikování sil (SwitchInteractions, SwitchFastDrawing, SwitchFastDrawing, AreForcesEnabled a GetFastDrawing). • Metoda SetOriginAndBillboard na případnou reakci na změnu kamery (předá se jí počátek a vektory kamery). • Metoda na smazání všeho ze systému ClearAll (částic, emitorů, sil a interakcí), smazání všech částic ClearParticles nebo restartování systému Reset. • Metody týkající se vykreslovacího bufferu (RefreshDrawBuffer a GetDrawBuffer viz Vykreslovací buffer). • Metoda GetEmitterProtocol vracející objekt splňující rozhraní pro emitování částic (viz Emitor částic).

33

• Metody na uložení přehrávané simulace do souboru (StartCaptureMode, CaptureFrame a StartCaptureMode popsané v kapitole 3 sekci Uložení simulace). • Metoda Update, která provede update všeho v systému (její popis najdete v další sekci). Na zobrazení online simulace je pak potřeba: 1. Přidat do systému emitory (interakce a síly) 2. Opakovat následující 3 kroky 3. Update systému 4. Případná změna nastavení kamery 5. Aktualizace vykreslovacího bufferu a samotné vykreslení (to si uživatel musí zajistit sám) V destruktoru uvolňuje částicový systém paměť všech objektů, které mu uživatel předal (částice, emitory, síly a interakce). Také se v něm probudí a následně ukončí všechna pomocná vlákna.

2.11

Update systému

Zde si popíšeme v jednotlivých krocích jak probíhá update celého systému (metoda Update částicového systému): 1. Zavoláme metodu EmitParticles na všech emitorech, čímž vytvoříme nové částice. 2. Aktualizujeme postupně všechny síly a interakce v systému pomocí jejich metody Update. 3. Provedeme aplikaci sil a interakcí na všechny částice, čímž změníme jejich nový stav. 4. Pomocí iterátoru UpdateIterator projdeme všechny živé částice a zavoláme jejich metodu Update (přímo v UpdateIterator pak dojde k aktualizaci mřížky), která již zajistí trvalé zapsání nového stavu částice, atd. (viz Reprezentace částice). 34

Aplikace sil a interakcí lze provést v jednom nebo ve více vláknech (pak musí být definována direktiva MSPS MULTI THREADING). Pokud tento proces běží v jednom vlákně, stačí projít pomocí BasicIterator všechny živé částice a zavolat na nich metodu CollectForces (viz Reprezentace částice a Aplikace interakcí a sil). V druhém případě je situace složitější. Na průchod částic použijeme QuantumIterator, který zinicializujeme, probudíme vlákna k aplikaci sil a interakcí a uspíme hlavní vlákno. Každé pracovní vlákno má k dispozici jeden LimitedIterator a k němu jednu primární frontu (aby se vlákna vzájemně neovlivňovala). Výpočet ve vláknu pak probíhá následovně: 1. Dokud není vlákno ukončeno zvenčí, opakuj následující kroky. 2. Spi a čekej. Po probuzení pokračuj dalším krokem. 3. Volej metodu částicového systému NextParticlesQuantum, která vrátí přidělené kvantum částic. Pokud nebylo vráceno žádné kvantum, vrať se do kroku 2. 4. Na každou částici z přiděleného kvanta aplikuj všechny síly a interakce. 5. Vrať se do kroku 3 (vyžádej si další kvantum). Jakmile NextParticlesQuantum oznamuje poslednímu neuspanému vláknu, že již byly zpracovány všechny částice, sama probudí hlavní vlákno a celkový update systému pokračuje. Díky tomu, že se zapisuje pouze do nového stavu částice (a to pro každou částici vždy v právě v jednom vláknu) a čte se z původního stavu, nemusí se zamykat částice.

35

Kapitola 3 Základní architektura a algoritmy offline simulace 3.1

Formát souboru offline simulace

Pro rychlejší zobrazení početně náročných simulací (složité interakce, apod.) lze uložit vypočtené vlastnosti částic na disk. Soubor se simulací je rozdělen logicky na 3 části: hlavičku, rámce s částicemi a seznam rámců. Hlavička obsahuje (řazeno dle výskytu v souboru): 1. Identifikaci souboru (20 ASCII znaků): MSPSSIMULATION000001. 2. Typ použitý při výpočtech offline simulace. Definovány jsou 3 (ve výčtu FilePrecisionEnum): 0 - long double, 1 - double a 2 - float. Výčet je uložen jako 4 bytové číslo. 3. Formát uložených koordinát (pozice i texturové koordináty částice). Opět uložen jako 4 bytový výčet CoordinatePrecision. Koordináty se mohou ukládat bez úprav (to znamená v typu uvedeném dříve v hlavičce, k tomu slouží hodnota NORMAL) nebo se ztrátovou komprimací. Při komprimaci se ukládá pevně určený počet bytů (hodnoty BYTE1 – BYTE4 ). Souřadnice částice jsou převedeny na relativní souřadnice v obklopující krabici a uloženy jako 3 celočíselné hodnoty (to znamená 0 reprezentuje jeden okraj krabice a nejvyšší možné celočíselné číslo s daným počtem bytů opačný okraj). Koordináta textury je pak uložena obdobně (předpokládá se omezení koordinát mezi 0 a 1, pokud toto neplatí, nelze ukládat komprimovaně). Celočíselné hodnoty jsou ukládány jako jednotlivé byty s pořadím big-endian. 36

4. Horní levý bližší roh mřížky uložený jako 3 hodnoty typu definovaného v bodu 2. 5. Dolní pravý vzdálenější roh mřížky (uložen stejně jako předchozí roh). 6. Počet krabic v mřížce (čili hustota rozdělení mřížky) podél jednotlivých os (x,y,z) uložené jako tři 4 bytová čísla. 7. Počet rámců, který by se měl zobrazit za jednu vteřinu při přehrávání běžnou rychlostí (uložen dle typu definovaného v bodu 2). 8. Jméno textury použité v simulaci (vždy je použita jen jedna, jednotlivé částice pak mohou mít jiné texturové koordináty a napodobit tak neomezené množství textur) uložené jako délka řetězce (4 bytové číslo bez znaménka) a řetězec obsahující cestu k textuře (relativní vzhledem k souboru se simulací). 9. Maximální počet částic, který se najednou objeví v jednom rámci (4 bytové číslo bez znaménka). 10. Adresa v souboru, na které se nachází seznam rámců. Po hlavičce následují jednotlivé rámce s částicemi. Rámce nejsou nijak od sebe oddělené, ukládají se jen jednotlivé částice, a to následovně: 1. Index krabice, která obsahuje danou částici (4 bytové číslo bez znaménka). 2. Pozice částice uložená dle formátu uvedeného v hlavičce (bod číslo 3). 3. Čtyři texturové koordináty (stejný formát jako pozice). 4. Velikost částice (uloženo jako typ uvedený v hlavičce v bodu 2). 5. Barva (RGBA, jeden byte na každou složku). Částice jsou navíc v rámci jednoho rámce uloženy seřazené dle indexu krabice (pro efektivnější načítání). Na konci souboru je pak uložen počet uložených rámců (4 bytové číslo bez znaménka) a následně pro každý rámec jeho pozice v souboru a počet částic v něm obsažených (4 bytové číslo bez znaménka). Výsledné soubory jsou značně velké, lze je však zmenšit použitím komprese koordinát (viz třetí bod hlavičky) s tímto kompresním poměrem: velikost komprimované koordináty×7+původní velikost+8 . původní velikost×8+8 Při použití dostatečně husté mřížky není horší kvalita pouhým okem znatelná. 37

3.2

Uložení simulace

Pro uložení simulace postupujeme obdobně jako při online simulaci (tak jak je uvedeno v kapitole Částicový systém). Ve chvíli, kdy chceme začít simulaci ukládat, musíme nejdříve zavolat metodu třídy Particle System StartCaptureMode, která přijímá tyto parametry: • Jméno souboru • Jméno souboru s texturou • Formát uložení koordinát (viz předchozí kapitola) • Doporučený počet fps (kolik rámců má přehrávač vykreslit za vteřinu) Poté, co je ukládání inicializováno, stačí volat metodu CaptureFrame pro uložení aktuálních vlastností částic (k jejichž získání se používá metoda částice Draw ). Tato metoda zároveň aktualizuje seznam již uložených rámců a maximální počet částic v simulaci, které se uloží na konci pomocí metody EndCaptureMode.

3.3

Načtení a vykreslení rámce

K načtení i vykreslení rámce při přehrávání simulace se používá třída Frame, která si na začátku připraví dostatečně velké buffery na částice a krabice, aby se do nich vešel libovolný rámec z uložené simulace (a tudíž nebylo potřeba alokovat paměť během přehrávání). Potřebné informace o simulaci získá Frame ihned v konstruktoru pomocí odkazu na třídu SimulationInfo, kde taktéž dostane jako další parametry primární frontu a odkaz na objekt splňující rozhraní ParticleDrawer (oboje slouží k vykreslování). Pro samotné načtení dat o konkrétním rámci ze souboru slouží metoda Load, která přijme jako argumenty soubor simulace (jako objekt typu FilePrecisionReader, s metodami určenými na snadné čtení koordinát částic, apod.) a číslo rámce (adresu v souboru pak zjistí pomocí dříve předaného SimulationInfo). Načtené částice se pak zobrazí pomocí metody Draw, které se předá počátek vykreslování (zobrazení pak probíhá pomocí stejného algoritmu jako při online simulaci, akorát zde máme pouze neprázdné krabice). Buffer rámců pak kvůli synchronizaci používá dvě separátní metody SetIndex a GetIndex na manipulaci s indexem načteného rámce.

38

3.4

Buffer rámců

Objekty typu Frame uvedené v minulé kapitole jsou spravovány třídou FramesBuffer, která dostane v konstruktoru soubor simulace (jako FilePrecisionReader ), informace o simulaci (SimulationInfo viz další kapitola), objekt na vykreslování (ParticleDrawer ) a počet rámců, které se budou načítat asynchronně dopředu. V konstruktoru se navíc vytvoří vnitřní buffer rámců a spustí vlákno na načítání rámců. Pro získání konkrétního načteného rámce (ve formě Frame) stačí zavolat metodu GetFrame, která přijímá jako parametry číslo rámce a směr přehrávání simulace. V této metodě se pak určí, které již načtené rámce se mohou zachovat (ty které mají index blízko chtěnému - viz obrázek) a které je třeba nahradit za jiné (ty se vloží do fronty volných rámců), a poté se počká, až vlákno pro nahrávání rámců načte požadovaný rámec. Postupně se pak pomocí vlákna nahrávají rámce od chtěného indexu dále ve směru přehrávání.

Obrázek 3.1: Asynchronní nahrávání rámců Chování samotného nahrávacího vlákna je pak následovné: 1. Dokud není stav nastaven na vypnutí (pomocí metody vlákna Kill ), opakuj kroky 2 – 4. 2. Pomocí metody bufferu NextFrameToLoad získej číslo rámce k načtení a volný objekt Frame. 3. Načti rámec (metoda Load třídy Frame). 4. Vrať rámec do bufferu metodou ReceiveLoadedFrame.

39

Pokud není co načíst, v metodě NextFrameToLoad se vlákno uspí, dokud ho neprobudí metoda GetFrame. Metoda ReceiveLoadedFrame pak probouzí hlavní vlákno, pokud čekalo na právě nahraný rámec. Původní myšlenka této třídy byla, aby se urychlilo přehrávání animace, avšak k tomu bohužel nedošlo (většinou se nestihl dopředu načíst řádný rámec, než bylo voláno další GetFrame). V ukázkové aplikaci proto používám nulový počet dopředu nahraných rámců.

3.5

Přehrávání offline simulace

K samotné manipulaci s offline simulací stačí uživateli knihovny použít pouze objekt typu Simulation, kterému se na začátku předá cesta k souboru se simulací a počet rámců, které se budou nahrávat asynchronně dopředu. Simulation pak otevře simulaci, načte hlavičku pomocí třídy SimulationInfo (která v podstatě obsahuje jen metody předávající informace z hlavičky), vytvoří buffer rámců a vykreslovací buffer. K další manipulaci s offline simulací pak slouží následující metody: • GetDrawBuffer vrátí konstantní referenci na vykreslovací buffer. • DrawFrameToBuffer, která očekává jako parametry index rámce, směr přehrávání, počátek vykreslení a vektory pro billboard. Metoda zajistí nahrání rámce (pomocí GetFrame) a jeho vykreslení do bufferu. • StopPreload zastaví nahrávání dalších rámců (pomocí GetFrame s indexem −1). • FramesCount vrátí počet rámců v simulaci. • ParticlesCount vrátí počet částic v aktuálním rámci. • FpsCount vrátí počet doporučených fps. • TextureName vrátí název textury. • FileName vrátí název souboru simulace.

40

Kapitola 4 Výkon V této kapitole se budeme zabývat tím, jaké prostředky moje knihovna obsahuje na vyladění výkonu částicových systémů a zároveň si u každé možnosti uvedeme, jaký má vliv na výkon vybrané ukázkové simulace. K měření výkonu byla využita sestava s procesorem Intel Core i7 (všechna čtyři jádra běžela na frekvenci 3,07 GHz, navíc byl podporován hyper-threading), operační pamětí 6 GB a grafickou kartou nVidia GeForce GTX 275. Nyní již následuje výčet možností: 1. Počet vláken Z druhé kapitoly víme, že aplikace interakcí a sil na částice může probíhat ve více vláknech (aktivuje se direktivou MSPS MULTI THREADING, počet vláken se pak nastaví v konstruktoru částicového systému). Abychom využili co nejvíce kapacity procesoru, můžeme experimentovat s větším počtem vláken než je počet jader. Na následujícím grafu si můžete prohlédnout, jak se měnila délka výpočtu 2000 snímků v simulaci Liquids při vypnutém vykreslování v závislosti na počtu vláken (při použití pouze 1 vlákna byly všechny částice v jednom kvantu). Jak je vidět, na testovací sestavě se nejlépe dařilo více než dvojnásobnému počtu vláken, než má výpočetních jader.

41

Obrázek 4.1: Vliv počtu vláken na rychlost výpočtu 2. Počet částic v jednom kvantu V kapitole o aktualizaci systému jsme se dozvěděli, že každé vlákno dostane přidělené jedno kvantum částic a po jeho zpracování si zažádá o další. Aby nedošlo k žádným problémům s race condition, je část, která přiděluje kvanta částic, zamykací. Při nastavení příliš malého počtu částic v jednom kvantu žádá vlákno často o přidělení nových částic a pomalý proces zamykání a odmykání brzdí aplikaci. Naopak při velikém počtu částic v kvantu je možné, že některá vlákna budou už mít dávno dopočítáno, zatímco jiná budou ještě dlouho počítat. Vliv velikosti kvanta testujeme stejným způsobem, jako v předchozím případě (jen máme pevně nastaveno 10 vláken). Dle výsledků je vidět, že nejlepší bude zvolit velikost kvanta okolo 50, samozřejmě výsledky se mohou lišit na jiných sestavách s různým počtem vláken.

42

Obrázek 4.2: Vliv velikosti kvanta na rychlost výpočtu 3. Velikost mřížky a její rozdělení Pro zrychlení algoritmů nad hierarchickou strukturou (ty ovlivňují rychlost interakcí a případně i vykreslování) lze měnit počet buněk (krabic) ve směru všech tří os v mřížce. Čím více máme krabic, tím pomalejší bude aktualizace pozic částic (bude častěji docházet k přechodu částic z jedné krabice do druhé), na druhou stranu při malém počtu krabic se bude v haldách mezi sebou porovnávat mnohem větší počet částic, což povede ke zpomalení interakcí i řazení při vykreslování (samozřejmě příliš velký počet krabic nepomůže ani haldě). Počet krabic lze tedy určit spíše experimentálně, můžeme však například vyjít z maximálního dosahu interakcí a určit podle něj velikost jedné krabice. I nyní zkoušíme vylepšit simulaci Liquids při nastavení 10 vláken a 50 částicích v jednom kvantu. Celková velikost mřížky je dána přímo simulací a to tak, že šířka a hloubka jsou stejné, ale výška je větší. Paradoxně nám však v testování vyjde, že na výšku budeme chtít dvakrát méně krabic než na ostatní dva rozměry. Pokud spočítáme velikost nejmenší strany jedné krabice z nejlepšího naměřeného výsledku, dostáváme opravdu zhruba stejné číslo, jako je maximální dosah interakcí částic. Pro přehlednost je následující graf pouze dvourozměrný, na ose x je zaznamenán počet krabic na šířku a hloubku, počet krabic na výšku je pak vždy poloviční.

43

Obrázek 4.3: Vliv rozdělení mřížky na rychlost výpočtu 4. Vykreslování bez řazení Jak již bylo řečeno dříve, knihovna před vykreslením seřadí všechny částice průchodem přes hierarchickou strukturu. Pokud používáme neprůhledné částice, nebo nepotřebujeme přesně spočítanou průhlednost, můžeme v částicovém systému vypnout řazení pomocí metody SwitchFastDrawing. Pokud pak nepoužíváme v simulaci ani interakce, můžeme nastavit nulové rozdělení mřížky (tedy jen 1 krabice na celou mřížku). Například v první ukázkové simulaci Colors to pak vede až na dvojnásobné zrychlení oproti původní mřížce o tisíci krabicích a na první pohled nelze poznat, že jsou částice špatně vykreslené. 5. Vícecestná halda Již bylo zmíněno dříve, že halda použitá při průchodu mřížkou je binární, avšak pomocí direktivy MSPS PRIMARYQUEUE 4ARY ji můžeme přepnout na 4-cestnou, při testování simulací bylo však zjištěno pouze mírné zrychlení. Protože je každá částice alokována zvlášť na haldě a poté také odstraňována, může trvat destrukce částicového systému celkem dlouho. Pokud například po destrukci ihned vypínáme aplikaci, můžeme nechat operační systém, ať za nás uklidí (a to mnohem rychleji). K tomu stačí definovat direktivu MSPS LEAKING.

44

Kapitola 5 Závěr 5.1

Shrnutí

V první kapitole jsme se dozvěděli, co to je částicový systém a že se používá k renderování jinak těžko zobrazitelných efektů jako jsou tekutiny, oheň, exploze atd. Probrali jsme jeho základní součásti, kterými jsou částice, emitory a externí síly, a že se dá případně urychlit pomocí různých hierarchických struktur. Dozvěděli jsme se také o možnostech skriptování, zlepšení výkonu pomocí GPU implementace a možnostech offline simulace. Na závěr první kapitoly pak byly stanoveny cíle práce, mezi které patřili hlavně co nejrychlejší interakce v online přehrávání a případné offline zobrazení náročnějších systémů, a představeny ukázkové simulace. Další kapitoly se pak věnovaly samotné implementaci knihovny na částicové systémy. Ve druhé kapitole byly rozebrány nejdůležitější objekty a algoritmy použitelné při online simulacích, v navazující třetí kapitole pak byla řeč hlavně o formátu ukládaných dat offline simulace a objektech sloužících k jejímu přehrávání. V poslední čtvrté kapitole pak byly prezentovány možnosti vylepšení výkonu simulací pomocí nastavení vlastností objektů knihovny, jako je například hrubost rozdělení mřížky, počet výpočetních vláken, apod. Zároveň se zde také nachází grafy a komentáře, ze kterých lze zjistit, jak se jednotlivé parametry projevily na vybraných simulacích.

45

5.2

Splnění cílů

V rámci práce byla implementována plně funkční knihovna na simulaci částicových systémů, jejíž jednotlivé součásti je možné naprosto flexibilně měnit pomocí dědičnosti a virtuálních metod. Hlavní síla knihovny spočívá v umožnění simulování fyzikálních interakcí mezi jednotlivými částicemi. Pro zajištění co nejvyšší možné rychlosti výpočtu těchto interakcí byla implementována hierarchická struktura Grid (mřížka), která navíc ještě umožněje rychlé setřídění průhledných částic pro správné vykreslení. Pro další zlepšení byla přidána možnost paralelního výpočtu externích sil a interakcí působících na částice. Knihovna je pak schopna vypočtené vlastnosti částic ukládat ve speciálním formátu na disk, který navíc umožňuje nastavení kvality pro menší nároky na zabrané místo a tato uložená data posléze znovu rychle přehrát. Moje implementace se ukázala jako vhodná pro výpočetně náročné simulace o méně částicích (maximálně desítky tisíc), ale naopak nevhodná pro výpočetně jednoduché, ale rozsáhlé systémy, pro které se spíše hodí GPU implementace.

5.3

Směr další práce

Další vývoj knihovny by se měl hlavně zaměřit na podporu skriptování, díky němuž bychom získali další flexibilitu bez nutnosti kompilace. Poté by mohla být implementována jiná hierarchická struktura speciálně pro offline simulace, u které by nevadila delší doba stavby, ale se kterou by se následně mnohem rychleji pracovalo. Následně by šlo přidat lepší podporu pro kolize částic s jiným objektem (nenáležícím do částicového systému), kde by šlo opět využít hierarchické struktury.

46

Literatura [1] Bourg D. M.: Physics for Game Developers, 2001. [2] Ebert S. David at al.: Texturing and Modeling, A Procedural Approach, 3rd edition, Elsevier Science, 2003. [3] Astle D.: More OpenGL Game Programming, Thomson Course Technology PTR, 2006 317–346. [4] Pelikán J.: Pokročilá 2D počítačová grafika: Datové struktury pro prostorové vyhledávání, http://cgg.mff.cuni.cz/˜ pepca/lectures/pdf/datasurvey.pdf. [5] Wikipedia: Particle system, http://en.wikipedia.org/wiki/Particle system. [6] Valve Software: Half-Life (hra), Sierra studios 1998.

47

Příloha A Obsah CD K bakalářské práci je přiložen disk CD-ROM, který je strukturován následovně: • /bin: Tato složka obsahuje dvě ukázkové aplikace, které si přiblížíme v příloze B • /data: Složka s konfiguračním souborem a texturami pro použití výše zmíněnými aplikacemi • /simulations: Adresář s uloženými offline simulacemi • /thesis: Adresář s textem bakalářské práce ve formátu pdf • /thesis-source: Adresář se zdrojový kódem bakalářské práce • /sources: Adresář se zdrojovými kódy aplikací

48

Příloha B Uživatelská dokumentace B.1

Požadavky

Pro běh aplikace musí Váš počítač splňovat následující požadavky: • Grafická karta podporující OpenGL verze 1.1 nebo vyšší. Pro použití antialiasingu je potřeba minimálně verze 1.3 (rozšíření WGL ARB multisample) • 384 MB RAM a více. • Dostatečně rychlý procesor (pro optimální přehrávání minimálně 2 GHz), v lepším případě více jádrový. • Operační systém Microsoft XP/Vista/Seven. Aplikace se nemusí instalovat, lze ji spustit přímo z CD. Obě dvě aplikace však vyžadují přítomnost složky data, ve které mají uložené textury a konfigurační soubor.

B.2

Konfigurační soubor

Ve složce data se nachází soubor settings.cfg, který slouží ke konfiguraci obou dvou přiložených aplikací. V souboru se nastavují hodnoty atributů následujícím způsobem : [ATRIBUT]=ČÍSELNÁ HODNOTA (každý atribut na zvláštní řádek, který neobsahuje žádné mezery ani tabulátory). Povinné jsou následující atributy: • [WIDTH] : šířka okna aplikace 49

• [HEIGHT] : výška okna aplikace • [COLORDEPTH] : barevná hloubka (počet bitů na pixel) • [FULLSCREEN] : celoobrazovkový mód (0 znamená vypnuto, 1 zapnuto) • [MULTISAMPLE] : multisampling (čili jedna z metod antialiasingu), hodnota udává počet fragmentů na pixel (0 znamená vypnuto) V souboru se dají dělat komentáře pomocí středníku na začátku řádku (komentář pak platí až do konce řádku).

B.3

Aplikace MSPS

Aplikace se spouští souborem /bin/MSPS.exe a má dva účely. Pokud se spustí bez parametrů, přehrává ukázkové online simulace se správnými parametry, pak ukládá soubor na disk. Při přehrávání online simulací ovládáme aplikaci následujícími klávesami: • ESC : ukončení aplikace • F1 : Zobrazí/schová nápovědu, ve které jsou vyjmenovány všechny tyto klávesy • P : Pozastaví nebo znovu spustí právě přehrávanou simulaci • F : Zobrazí/schová počítadlo fps (dole uprostřed) • C : Zobrazí/schová počítadlo aktuálně zobrazených částic (nahoře uprostřed) • 1–5 : Přepínání mezi ukázkovými simulacemi (vyjmenované níže) • I : Přiblížení scény • O: Oddálení scény • Q: Rotace scény okolo osy Z (ve směru do scény) proti směru hodinových ručiček • E : Rotace scény okolo osy Z po směru hodinových ručiček • A: Rotace scény okolo osy Y (směr nahoru) doprava 50

• D: Rotace scény okolo osy Y doleva • W : Rotace scény okolo osy X (směr vpravo) nahoru • S : Rotace scény okolo osy X dolů • N : Zrychlení simulace (a to až desetkrát - omezeno jen z důvodu přílišného zatížení procesoru) • M : Zpomalení simulace (a to až tisíckrát) • R: Původní natočení scény • U : Původní vzdálenost od scény • B : Normální rychlost simulace Aplikace obsahuje následující simulace: 1. Colors – náhodně barevné částice (spíše se jedná o zátěžový test zobrazující až 40 000 částic), šipkami (nahoru a dolů) lze přepínat způsob emitování částic (náhodný, kruhový a rotující) 2. Explosion 3. Fireworks 4. Bombardment (k vypuštení střely použijte klávesu enter) 5. Liquids (pokud držíte levou šipku, teče žlutá kapalina, pokud pravou teče modrá, při nahrávání offline simulace pak tečou obě najednou) Více o těchto simulacích najdete v první kapitole. Pro využití programu k uložení simulace na disk se musí definovat následující parametry : • -c: specifikuje, že se bude ukládat simulace na disk • -f : nastaví počet fps simulace a to minimálně 20, nejvíce 60 (60 je totiž základní počet fps při online simulaci, více fps by neznamenalo vyšší kvalitu)

51

• -p : nastavuje kvalitu uložení pozičních a texturových koordinát částice. Hodnota může být 0 (bez komprimace - uloženo jako float), nebo 1 až 4 pro počet bytů reprezentujících jednu koordinátu (více o komprimaci v kapitole 2 sekci Formát souboru offline simulace) • -l : počet ukládaných snímků • -d : ukládaná simulace (1 až 5) • -i : nepovinný argument, pokud je specifikován, zobrazí každých snímků průběžný stav o ukládání • jméno souboru se simulací (nezačínající pomlčkou nebo delší než 2 písmena) Například lze zavolat program s těmito parametry: -c -f 60 -p 0 -l 500 -d 2 -i 10 explosion.dat Takto programu oznámíme, že chceme ukládat simulaci při kvalitě 60 fps a žádné komprimaci koordinát. Celkově se má uložit 500 snímků simulace číslo 2 do souboru explosion.dat. Každých 10 uložených snímků se pak zobrazí počet již uložených snímků.

B.4

SimulPlayer

Aplikace se spouští souborem /bin/SimulPlayer.exe a očekává názvy uložených simulací jako jednotlivé parametry (kterých může být až 9). Aplikace se ovládá stejně jako online verze MSPS až na pár přidaných kláves : • 1–9 : Přepínání mezi nahranými simulacemi • →: Spuštění přehrávání v normálním směru • ←: Spuštění přehrávání v opačném směru • mezerník : Zobrazení/schování ukazatele přehrávání (dole uprostřed) • ↑: Rychlé přetáčení vpřed (na ukazateli přehrávání se zobrazí červeně kam se chceme posunout) • ↓: Rychlé přetáčení zpět

52