Mendelova univerzita v Brně Provozně ekonomická fakulta
Digitální krajina s fraktálově generovanými rostlinami Diplomová práce
Vedoucí práce: Ing. Mgr. Jana Dannhoferová, Ph.D.
Brno 2012
Bc. Zdeněk Pavlů
Děkuji vedoucí mé bakalářské práce Ing. Mgr. Janě Dannhoferové, Ph.D. za rady a podporu, které mi při tvorbě této práce poskytla. Dále bych rád poděkoval doc. Jiřímu Rybičkovi za tvorbu sazebního stylu pro diplomové a bakalářské práce.
Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně a že v ní uvádím veškerou použitou literaturu a jiné zdroje informací, ze kterých jsem čerpal.
Brno 24.5.2012
....................................................
4
Abstract Pavlů, Z. Digital landscape with fractal generated plants. Diploma thesis, Brno, 2012. The Diploma thesis is dealing with the use of L-systems for modeling trees and their placement in the digital landscape. The digital landscape is represent by a game engine. The thesis includes analysis of freeware engines. Trees are generated in the program created in OpenGL, using the Glui library and format Obj.
Abstrakt Pavlů, Z. Digitální krajina s fraktálově generovanými rostlinami. Diplomová práce, Brno, 2012. Práce se zabývá využitím L-systémů pro vytváření modelů stromů a jejich následné umístění v digitální krajině. Digitální krajinu reprezentuje herní engine. V práci je obsažena analýza volně dostupných enginů. Stromy jsou vytvářeny v programu, který je vytvořen v OpenGL, využívající knihovnu Glui a formát Obj.
5
OBSAH
Obsah 1 Úvod a cíl práce 1.1 Úvod práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Cíl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 7 8
2 Metodika řešení
9
3 Teoretická východiska práce 3.1 Grafické prostředí . . . . . . . . . . . . . . . 3.2 Základní vlastnosti 3D enginu . . . . . . . . 3.2.1 Grafické rozhraní . . . . . . . . . . . 3.2.2 Počítačová platforma . . . . . . . . . 3.3 Grafické vlastnosti 3D enginů . . . . . . . . 3.3.1 Osvětlení . . . . . . . . . . . . . . . 3.3.2 Stínování . . . . . . . . . . . . . . . 3.3.3 Texturování . . . . . . . . . . . . . . 3.3.4 Shadery . . . . . . . . . . . . . . . . 3.3.5 Renderování . . . . . . . . . . . . . . 3.3.6 Animace . . . . . . . . . . . . . . . . 3.3.7 Speciální efekty . . . . . . . . . . . . 3.3.8 Terén . . . . . . . . . . . . . . . . . 3.4 Fraktální geometrie . . . . . . . . . . . . . . 3.5 L-systémy . . . . . . . . . . . . . . . . . . . 3.5.1 D0L-sytémy . . . . . . . . . . . . . . 3.5.2 Závorkové L-systémy . . . . . . . . . 3.5.3 Stochastické L-systémy . . . . . . . . 3.5.4 Aplikování L-systémů . . . . . . . . . 3.5.5 Kontextové L-systémy . . . . . . . . 3.5.6 Parametrické L-systémy . . . . . . . 3.5.7 Interpretace gramatiky želví grafikou
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
4 Analýza 3D enginu 4.1 Stanovená kritéria . . . . . . . . . . . . . . . . . 4.2 Komerční engine . . . . . . . . . . . . . . . . . 4.2.1 Nástroj pro tvorbu stromu . . . . . . . . 4.3 Volně dostupné enginy . . . . . . . . . . . . . . 4.3.1 Detailnější popis enginů . . . . . . . . . 4.4 Matice hodnocení faktorů konkurenčních enginů
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . . . . .
10 10 10 10 11 12 12 13 14 15 17 17 17 17 18 18 19 20 20 22 24 27 29
. . . . . .
33 33 33 35 36 39 42
5 Nástroj pro vytváření modelů stromů 45 5.1 Příkazy želví grafiky . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.2 Knihovna pro grafické rozhraní . . . . . . . . . . . . . . . . . . . . . 48 5.3 Grafický formát .OBJ . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6
OBSAH
6 Metodika tvorby modelu stromu 51 6.1 Tvorba pravidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2 Aplikace monopodiální struktury větvení . . . . . . . . . . . . . . . . 54 6.3 Aplikace sympodiální struktury větvení . . . . . . . . . . . . . . . . . 55 7 Implementace modelu 7.1 Nástroj IrrEdit . . 7.2 Případová studie . 7.3 Program Blender . 8 Diskuze
v digitální . . . . . . . . . . . . . . . . . . . . .
krajině 58 . . . . . . . . . . . . . . . . . . . . . 58 . . . . . . . . . . . . . . . . . . . . . 59 . . . . . . . . . . . . . . . . . . . . . 61 62
9 Závěr 63 9.1 Přínosy diplomové práce . . . . . . . . . . . . . . . . . . . . . . . . . 63 10 Literatura
65
Přílohy
67
A Tabulka enginů
68
B Program Blender
69
1
ÚVOD A CíL PRÁCE
1 1.1
7
Úvod a cíl práce Úvod práce
Řecký matematik Euklides se snažil popsat svět pomocí primitivních objektů, jako jsou krychle, válec a další. Avšak příroda je v naprosté většině složena z nepravidelných útvarů, na první pohled s chaotickým uspořádáním. Přestože euklidovskou geometrií lze stěží popsat přírodní systémy, přetrval tento způsob vnímání reálného světa až do dvacátého století. S příchodem výpočetní techniky se velmi usnadnil rozvoj fraktální geometrie, která umožnila přesně popisovat přírodu novým způsobem. Od vidění světa jednoduchými geometrickými objekty se ustoupilo. Vegetace, toky řek, pohoří, ostrovy, mraky — to vše lze matematicky popsat fraktály. Při bližším pohledu na všechny tyto útvary zjistíme, že si jsou „soběpodobnéÿ. Jestliže na daný útvar nahlížíme v jakémkoliv měřítku nebo rozlišení, vidíme stále se opakující stejný tvar/vzor, což je jednou z definic fraktálu. Dnešní hardwarový výkon grafických karet již umožňuje pracovat se složitými trojrozměrnými modely ve fotorealistické kvalitě. V počítačové grafice se vytvořilo mnoho různých nástrojů a technik pro modelování různých přírodních útvarů. Avšak rostliny patří ke složitým přírodním objektům skládajícím se z několika typů fraktálových struktur, ať už jde o způsob větvení stromů, souměrnost listů nebo nepravidelnost kůry. Tato složitost znesnadňuje ruční tvorbu modelů rostlin využitím klasických modelovacích nástrojů. L-systémy (Lindenmayerovy systémy) jsou typem fraktálu, které svým způsobem tvorby připomínají reálný růst stromů a jsou tedy nejvhodnějším nástrojem pro jejich tvorbu v počítačové grafice. K definování jednoduchých L-systémů lze využít bezkontextové nebo regulární přepisovací gramatiky. Podstatu tvoří paralelní přepisování řetězců podle pravidel gramatiky. K tomu se často užívá tzv. želva. Předností L-systémů je také možnost měnit samotné generování fraktálu na základě zpětné vazby nebo podnětů z okolního prostředí, což umožňuje např. simulování působení gravitace. Kompletní realizace rostliny pomocí L-systému je poměrně složitá. Výsledkem však může být velmi propracovaný nedeterministický model téměř nerozeznatelný od skutečné rostliny. Využití modelů rostlin je nejčastější při tvorbě vizuálních efektů ve filmovém průmyslu a v počítačových hrách. Samotná realizace digitální krajiny v počítačových hrách se ale zcela liší od té určené pro vytváření videoanimací. Při vytváření animovaných sekvencí pro filmy většinou postačuje samotný editor pro vytváření modelů, který již obsahuje nástroje tvorby animace a její vykreslení do podoby videa. Toto řešení ovšem neumožňuje žádnou interakci s uživatelem. Pro počítačové hry je interakce uživatele s generovaným digitálním prostředím naprostou nutností. Toho se dosahuje využitím tzv. 3D grafického „enginuÿ, který umožňuje vykreslování scén „real-timeÿ, v reálném čase.
1.2
1.2
Cíl práce
8
Cíl práce
Cílem diplomové práce je navrhnutí metodiky pro tvorbu počítačově generových rostlin v digitální krajině. Digitální 3D krajina bude realizována prostřednictvím herního enginu. Ten bude vybrán na základě výsledků provedené analýzy dostupných herních enginů. Pokud žádný engine nebude mít vlastní nástroj využívající L-systémy k vytváření rostlin (bude v průběhu analýzy ověřeno), pak bude vytvořen vlastní program, který využívá knihovnu OpenGL. Modely rostliny budou generovány s využitím fraktálové geometrie a následně vkládány do digitální krajiny.
2
2
METODIKA ŘEŠENí
9
Metodika řešení
V prvním kroku byla provedena analýza současného stavu v oblasti počítačové grafiky, především real-time 3D grafická prostředí, a studium literatury zaměřené na fraktálovou geometrii. Na základě analýzy bylo vybráno grafické prostředí IrrEdit 1.4.2. Následně bylo přistoupeno k vlastnímu návrhu a tvorbě programu pro generování modelů rostlin. Program byl naprogramován v jazyce C++. Jako editor textu byl použit program Code::Blocks 10.05. Bylo využito grafické knihovny OpenGL a knihovny Glui 2.35 pro vytvoření grafického rozhraní. Pro následnou tvorbu stromu byl použit nově vytvořený program LS Generátor. Do programu IrrEdit je následně možné importovat modely stromů, uložené ve formátu .obj, vytvořené v LS Generátoru.
3
TEORETICKÁ VÝCHODISKA PRÁCE
3
10
Teoretická východiska práce
Teoretická východiska diplomové práce zahrnují popis vlastností grafických prostředí, která budou využívána při realizaci digitální krajiny v této práci. Stručně budou uvedeny informace o fraktálové geometrii, především L-systémech a jejich gramatikách.
3.1
Grafické prostředí
Digitální krajina bude realizována prostřednictvím počítačového herního enginu. Engine (hnací stroj, motor) je 3D grafický systém navržený pro tvorbu a vývoj počítačových her. Jedná se o jakési jádro počítačových her, mající sadu nástrojů a komponent, často spojených do vývojového prostředí, jejichž účelem je zjednodušený a rychlý vývoj her. Základní charakteristikou je schopnost real-time renderování 2D a 3D grafiky. Jedná se o nepřetržité vykreslování námi ovládané virtuální scény v reálném čase. Nejedná se tedy o již nasnímaný záznam scény, ve které nemáme žádnou možnosti interakce, jako je tomu např. ve videu. Také umožňuje simulaci fyzikálních zákonů, detekci kolizí, zvuky, animace, umělou inteligenci objektů a další. Například při použití částicových systémů, které prostřednictvím velkého množství malých částic vytváří tekoucí vodu nebo kouř, dochází k ovlivnění směru jejich pohybu vlivem vnějšího prostředí. Tím může být gravitace nebo vítr. Jejich pohyb tak simuluje reálné prostředí, např. voda padá k zemi a následně se odráží do určité výsky apod. Umělá inteligence objektů je pak předdefinovaná reakce na nějaký podnět. K dispozici je mnoho komerčních i nekomerčních herních enginů, které jsou určeny pro hrací konzole nebo osobní počítače. Pro výběr vhodného herního enginu bude nezbytné, aby mohl být využit bezplatně v rámci výuky.
3.2
Základní vlastnosti 3D enginu
Základní vlastnosti herních enginů jsou udány jejich samotnou implementací. Například v jakém programovacím jazyce jsou vytvořeny a pro jaké platformy jsou určeny. 3.2.1
Grafické rozhraní
Grafické rozhraní (Graphics Application Programming Interface, dále jen API) je klíčovým prvkem enginů. Jedná se o určité sady pravidel, podmínek a požadavků, které programy používají pro komunikaci mezi sebou. Podobně, jako uživatelské rozhraní usnadňuje interakci mezi člověkem a počítačem, API slouží jako rozhraní mezi různými druhy softwaru a usnadňuje jejich vzájemnou interakci. API je definováno sadami funkcí, procedur, tříd a knihoven, které bude moci programátor využívat. Také je specifikováno, jakým způsobem se budou funkce knihoven volat.
3.2
Základní vlastnosti 3D enginu
11
Mezi nejvíce používaná standardizovaná grafická API patří DirectX od společnosti Microsoft a OpenGL od konsorcia Khronos Group. DirectX DirectX je kolekce více API od společnosti Microsoft, poskytující herním vývojářům low-level rozhraní pro hardware, na kterém je spuštěn Windows. Ve verzi 9.0, každá komponenta API poskytuje přístup k rozdílným aspektům hardwaru. Toto rozhraní umožňuje vývojářům psát své hry využitím sady funkcí, bez ohledu na hardware, na kterém se provádějí. API DirectX je založeno na Component Object Model (COM), které umožňuje kompatibilitu s předchozími verzemi. Objekty COM obsahují kolekce rozhraní, která nabízí vývojářům metody užití pro přístup k DirectX. Objekty COM jsou DLL soubory, které se stanou součástí systému po nainstalování DirectX. Každá další verze DirectX obsahuje nové rozhraním DirectDraw, které obsahuje předcházející verzi, čímž se neruší funkčnost již existujících kódů. Vývojáři mohou pro práci s COM objekty využít více jazyků, např. C++, Visual Basic nebo C# (Jones W., 2004). Nejnovější verze má pořadové číslo 11. Budoucí verze DirectX 11.1 bude vydána společně s Windows 8. Zásadním omezením tohoto rozhraní je jeho výhradní použití na operačním systému Windows. OpenGL OpenGL (Open Graphics Library) je standardní specifikace definující multiplatformní rozhraní pro tvorbu 2D a 3D počítačové grafiky. Toto rozhraní obsahuje okolo 250 různých příkazů, kterými lze specifikovat objekty a operace potřebné k vytvoření interaktivní trojrozměrné aplikace. Složitější objekty musí být poskládány z malých geometrických objektů, jako jsou body, křivky a plochy. OpenGL je navrženo tak, aby bylo hardwarově nezávislé pro implementování na různé platformy. Této vlastnosti se dosahuje tak, že neobsahuje žádné příkazy pro vykreslování okna aplikace nebo k získávání vstupů od uživatele. OpenGL Utility Library (GLU) je knihovna, nabízející některé další modelovací funkce, jako jsou kvadratické povrchy a NURBS křivky a povrchy. GLU je standardní částí každé implementace OpenGL (Shreiner D., 2007). Nejnovější verze OpenGL byla uvolněna 8. září 2011 a má označení 4.2. 3.2.2
Počítačová platforma
Počítačová platforma je pracovní prostředí, dané zvolenou kombinací hardwaru a softwaru. Mezi nejčastější hardwarové typy platforem patří mobilní zařízení, hrací konzole, osobní počítače, notebooky a tablety. Softwarová část platformy je tvořena
3.3
Grafické vlastnosti 3D enginů
12
operačním systémem, knihovnami, použitými programovacími jazyky, nebo kompletním frameworkem1 . Pro některé hardwarové komponenty lze použít pouze jediný typ softwarové komponenty. Výrobce v tomto případě nabízí platformu s jasně definovanými vlastnostmi a možnostmi užití. Do této skupiny se řadí hrací konzole a většina mobilních zařízení. U osobních počítačů má uživatel možnost volby, byť s doporučeným nebo částečně omezeným výběrem softwaru. DirectX běží na operačním systému Windows a herních konzolích Xbox 360. OpenGL podporuje většina operačních systémů (Windows, Linux, MacOS), i některé herní konzole, např. Play Station. Programovací jazyk je dalším prvkem, který definuje grafické API. Nejčastějšími zástupci jsou Java, C, C++, C#, VB.NET, ale také ActionScript, Javascript a další. Spíše než samotné určení jazyka, jeho syntaxe a sémantika, je důležitá koncepce tvorby aplikací. Jedná-li se o objektově orientovanou nebo plug-in architekturu.
3.3
Grafické vlastnosti 3D enginů
K nejrozsáhlejší části herních enginů patří jejich možnosti pro realizaci grafického prostředí. Lze ho rozdělit do několika sekcí nabízejících způsoby, jak zrealizovat danou komponentu ve scéně s-cílem vytvořit co nejrealističtější simulované prostředí. 3.3.1
Osvětlení
Základními osvětlovacími mechanizmy v počítačové grafice jsou techniky pervertex a per-pixel. Osvětlení plochy per-vertex se počítá ze světelných hodnot vrcholů 3D objektů. Zbylé světelné hodnoty bodů mezi vrcholy jsou následně vypočítány interpolací2 . Označení per-pixel se používá pro soubor metod výpočtu osvětlení v každém bodě obrazu. Žádné hodnoty se tedy neurčují interpolací. Tyto metody výpočtu často vytváří mnohem realističtější obrázky než osvětlení per-vertex. Per-pixel se často používá ve 2D a 3D grafických aplikacích, které nevykreslují scénu v interaktivní snímkové rychlosti. Pro real-time aplikace se algoritmy per-pixel realizují s využitím pixel shaderů. Osvětlení Per-pixel je běžně používáno s dalšími technikami počítačové grafiky pro zlepšení kvality vykreslení, včetně tzv. bump mapping, specularity, phong shading a shadow volumes. Volumetrické osvětlení Světelné paprsky nejsou ve scéně viditelné. Viditelné bývají pouze plochy, na které dopadá světlo, případně světelný zdroj. Stejný princip platí i v přírodě. Avšak 1
Framework je softwarová struktura, která slouží jako podpora při programování, vývoji a organizaci jiných softwarových projektů. Může obsahovat podpůrné programy, knihovnu API, návrhové vzory nebo doporučené postupy při vývoji. 2 Interpolace - nalezení přibližné hodnoty funkce v daném intervalu.
3.3
Grafické vlastnosti 3D enginů
13
některé objekty mohou být vyplněny velkým množstvím malých částic, které umožňují pozorovateli vidět světelné paprsky procházející prostředím. K vytvoření tohoto světelného efektu se používá volumetrického osvětlení. Light mapping Light mapa je datová struktura obsahující údaje o jasu povrchu v grafických aplikacích. Zjednodušeně se jedná o druhotnou texturu, která se nanáší na objekt reprezentující intenzitu světla na povrchu. Light mapy jsou předpočítány a používají se u statických objektů. Light mapping umožňuje mnohem komplexnější a realističtější stínování (Schulz R., 2011). Radiozita Radiozita je algoritmus globálního osvětlení v počítačové grafice. Tato technika umožňuje vytvářet fotorealisticky věrné obrazy scény, ve kterých se správně simuluje fyzikální šíření světla, na rozdíl od metody sledování paprsku, která nepřímé difúzní osvětlení empirický odvozuje dosazením konstantní hodnoty pro celou scénu. Radiozita počítá cesty, které vycházejí ze světelných zdrojů a několikrát (třeba i nulakrát) se difuzně odrazí, než vletí do oka. (Žára J., 2004). Gloss maps Povrchy, jejichž lesk se může v určitých částech změnit, podobně jako mokrý mramor nebo mokrý papír, se dají modelovat s využitím „gloss mapsÿ. Gloss mapa je textura, která upravuje podíl spekulárního světla (odraženého světla) tak, aby některé body povrchu odrážely méně spekulárního světla než ostatní. Jedná se o texturu, která určuje oblasti se schopností odrážet světlo (Blythe D., 2011). Anizotropiní osvětlení Osvětlení typu per-vertex předpokládá, že je povrch objektu tvořen malými ploškami (aspekty), které jsou rovnoměrně rozmístěny v libovolném směru. To znamená, že se předpokládá izotropní (na směru nezávislá) světelné reakce. Jiné povrchy jsou vytvořeny z „usměrněného vláknaÿ vytvořeného z plošek, které jsou zformovány směrovým vychylováním, podobně jako se tvoří drážky broušením nebo obráběním. U těchto povrchů se projevuje anizotropní (opak izotropního na směru závislé) osvětlení. Mezi typické povrchy s anizotropními světelnými vlastnostmi patří vlasy, disky CD, činely bicí soupravy či vinylové desky (Blythe D., 2011). 3.3.2
Stínování
Shadow Mapping Shadow mapping (mapování stínů) je typická technika pro přidávání stínů v počítačové grafice. Publikoval ji Lance Williams v knize „Casting curved shadows on curved surfacesÿ v roce 1978. Základem je tzv. shadow mapa, která pro každý pixel ve scéně určí jeho vzdálenost od světelného zdroje3 . Shadow mapa je uložena v tzv. Z-bufferu (paměť, ob3
V anglické literatuře se vzdálenost od zdroje označuje jako depth value – hodnota hloubky.
3.3
Grafické vlastnosti 3D enginů
14
sahující údaje o vzdálenosti pixelů od zdroje). Při renderování pohledu z kamery se viditelnost objektů určuje porovnáváním hodnot obsažených v z-bufferu. Projected planar shadows Projected planar (rovinná projekce) je nejsnazší a nejrychlejší stínování užívané v real-time aplikacích. Objekt je jednoduše promítnut na plochu a poté samostatně vyrenderován jako objekt. Výpočet stínu zahrnuje vložení transformované ortografické nebo perspektivní projekční matice do pohledu z kamery, a poté vyrenderovat promítnutý objekt s požadovanou barvou stínu (Blythe D., 2011). Tato metoda poskytuje velmi nerealistické stínování a vržené stíny jsou použitelné pouze na rovných plochách. Shadow volume Shadow volume pracuje s vrhanými stíny jako s objekty s objemem. Využívá se přitom tzv. Stencil buffer4 pro nalezení průniku polygonů se shadow volume ve scéně.Stín je vytvářen od světelného zdroje z proudu paprsků, které protínají vrcholy objektů. Vytváří se tak nekonečný polygonový povrch, jehož vnitřní objem zastiňuje objekty nebo jejich části (Blythe D., 2011). Hlavní předností shadow volumes je jejich přesnost na pixel. Nicméně, tato technika je náročná na výpočet. 3.3.3
Texturování
Multitexturing Při základním texturování lze mapovat jedinou texturu na každý polygon. Technika multitexturing umožňuje aplikovat několik textur, jednu po druhé, na ten samý polygon. Multitexturing umožňuje pokročile vykreslovací techniky, jako jsou světelné efekty, obtisky a detailní prvky textur.(Shreiner D., 2007) Bump mapping Bump mapping (nanesení „boulíÿ) je způsob pro simulování nerovností a zvrásnění povrchu objektu nanesením textury, aniž by se změnila povrchová struktura geometrického objektu. Zobrazení povrchové hrbolatosti se tvoří 2D texturou, neboli bump mapou, kde barevná hodnota každého pixelu představuje nějakou výškovou hodnotu. Tato mapa narušuje směr povrchových normál, které ovlivňují, jakým způsobem se od povrchu odráží dopadající světlo. Světlo se tedy odrazí podobným způsobem, jakým by se odrazilo v případě zdeformovaného povrchu. Bump mapping je ideální na objekty, které mají opakující se zdrsněný povrch, např. dřevo, dlažba apod. (Eberly D. H., 2005). Mipmapping Mipmapping, nebo také MIP maps, je v počítačové grafice předem připravený soubor textur, které se mapují na objekty v závislosti na jejich vzdálenosti od kamery. Pokud se objekt vzdaluje od kamery, musí se spolu s ním zmenšovat i textura, 4 Stencil buffer neboli paměť šablony se využívá při uřčování, které části objektů ve scéně je zastíněny shadow volume.
3.3
Grafické vlastnosti 3D enginů
15
která je na něm nanesena. Při nadměrném zmenšování textury dochází ke vzniku tzv. vizuálních artefaktů, jako je míhání, blikání a třpytění. K zabránění jejich vzniku se specifikují sady textur s různým rozlišením, nazvané mipmapy (Shreiner D., 2007). Volumetrické textury Volumetrické (objemové) textury jsou trojrozměrné kolekce pixelů (texelů), které mohou být užity k namalování dvoudimenzionálních primitiv jako je trojúhelník nebo čára. Třírozměrné texturové souřadnice jsou vyžadovány pro každý vertex primitivního objektu, který má mít texturu s objemem. Při vykreslování objektu je každý pixel vyplněn barvou, kterou převzal od některého pixelu z objemu, v souladu s pravidly pro dvourozměrné textury. Objemy nejsou vykreslovány přímo, protože tam nejsou třídimenzionální objekty, které by mohly být nakresleny s nimi. Objemy jsou vytvořeny navršením dvourozměrných plátků o nějaké výšce a šířce. Volumetrické textury se užívají pro vykreslení speciálních efektů, např. výbuchů (Microsoft, 2011). Procedurální texturování Jednou z charakteristik definujících procedurální texturu je, že je uměle vytvořená programem, spíše než zdigitalizováním nebo nakreslením obrazu. Konkrétně se využívá matematických algoritmů za účelem vytvoření realistického znázornění přírodních útvarů jako je dřevo, mramor, žula, kov, kámen a další. Výhodou je jejich extrémní kompaktnost. Velikosti procedurálních textur je v řádech kilobytů (kB), zatímco obrázkové textury jsou obvykle v megabytech (MB). Dále nemají fixní rozlišení a mají nekonečný rozsah, aniž by hrozilo opakování vzoru. Nevýhodou je jejich těžké vytváření a ladění. Obtížněji se také odstraňují problémy spojené s různými druhy aliasingu, např. optický klam (Ebert David S., 2003). 3.3.4
Shadery
Současná generace uživatelského grafického hardwaru je programovatelná. Tyto programy se nazývají shadery. Shadery se dělí na dvě kategorie -– vertex shadery a pixel shadery a staly se součástí grafických karet od verze DirectX 8. Tyto programy umožňují větší kontrolu nad renderovacími procesy a nahrazují nebo výrazně rozšiřují standartní grafická API s funkčně-fixními procesy (fixed-function pipeline). Shadery umožňují používání speciálních efektů (Eberly D. H., 2005). Vertex shader Vertex shader je v pořadí první shader, který se používá při vykreslování objektů. Všechny vrcholy polygonů ve 3D scéně se transformují do 2D prostoru obrazovky. Na vrcholy lze aplikovat některé efekty a také se s nimi může manipulovat. Typickým příkladem je pohyb vodní hladiny. Nelze však polygony přidávat či ubírat, kostra objektu je neměnná. Při transformaci se také určují barvy vrcholů (Eberly D. H., 2005).
3.3
Grafické vlastnosti 3D enginů
16
Pixel shader Pixel shader slouží k vykreslení textury v jednotlivých polygonech. Vypočítává barvu a další atributy ke každému pixelu vykreslovaného trojúhelníku. Umožňují i další úpravy, jako je stínování, průhlednost, bump mapping, odrazy světla a další, čímž získá vykreslovaný objekt téměř finálovou podobu. Oproti vertex shaderu je pixel shader mnohem náročnější na výkon, jelikož pracuje se všemi pixely (Eberly D. H., 2005). Geometry shader Geometry shader je relativně nový typ shaderu. Používá se po vertex shaderu a umožňuje měnit geometrii objektu přidáváním nebo odebíráním vrcholů, nebo vytvářet nová primitiva. Uplatňuje se například při simulaci růstu, a to v reálném čase. Toto řešení je méně náročné na výpočetní výkon, než doposud používaná alternativní řešení. Geometry shader je k dispozici teprve od verze DirectX 10 a OpenGL 3.2 a na rozdíl od předchozích shaderů je volitelný a nemusí být vůbec použit (Šulc T., 2008). HLSL Pro doplnění ještě uvádím HLSL (High level shading language), což je jazyk sloužící k vytváření programovatelných shaderů pro Direct3D pipeline, který je podobný jazyku C.
Obr. 1: Shadery jako součást grafické pipeline (Angeulov B., 2011).
3.3
Grafické vlastnosti 3D enginů
3.3.5
17
Renderování
Renderování je proces generování reálného obrazu z počítačem vytvořeného modelu. Jedná se o zvláštní způsob vizualizace dat. Stereo renderování Stereo renderování je paralelní vykreslení dvou obrazů pro každé oko zvlášť. Využívají se při stereoskopii, která umožňuje různými technikami vyvolat trojrozměrný zrakový vjem ve dvourozměrné předloze. Ray tracing Ray tracing (sledování paprsku) je jednou z metod renderování. V přírodě se paprsky světla pohybují a odrážejí, dokud nedopadnou do oka pozorovatele. Jelikož ze světelného zdroje vyzařuje nekonečný počet paprsků, při metodě sledování paprsků se používá obráceného postupu, kdy z kamery vycházejí paprsky, u kterých se sleduje jejich průchod scénou, až do světelného zdroje (počet možných odrazů ale není nekonečný). Metoda umožňuje vytvářet velmi realistické obrázky, ale má větší výpočetní náročnost. Sledování paprsků umožňuje simulaci mnoha optických efektů, např. odraz, lom, rozptyl a disperzní jevy, jako je chromatická aberace5 (též barevná vada) (Žára J., 2004). Ray casting Ray casting (vržení paprsku) je renderovací metoda sledování paprsků z kamery, podobně jako u metody sledování paprsků. Rozdílné je to, že tato metoda zobrazuje pouze body na povrchu nejbližšího tělesa, které je zasaženo paprskem. Nesledují se žádné další odrazy paprsků (Žára J., 2004). 3.3.6
Animace
Animace je zaznamenání sekvence snímků k vytvoření zdánlivě se pohybujícího objektu. V 3D grafických enginech existuje několik typů animací, např. Inverse a Forward kinematics, Skeletal a Facial animation, Morphing a Animation blendig. Pro naše zadání jsou ale nepotřebné a postačuje klasická animace a Key frame animace, budou-li vůbec potřeba. 3.3.7
Speciální efekty
Speciální efekty jsou důležitou součástí počítačových her a tudíž je nezbytné, aby je 3D enginy umožňovali realizovat. Pro tuto práci ale nebudou potřebné. Mezi speciální efekty patří oheň, voda, exploze, mlha, obloha, zrcadlení a další. 3.3.8
Terén
Posledními grafickými vlastnostmi enginů je možnosti práce s terénem. 5
Barevná vada čočky, nebo objektivu, způsobená závislostí ohniskové vzdálenosti čoček na vlnové délce světla.
3.4
Fraktální geometrie
18
CLOD (Continuous level-of-detail, spojitý/dynamický LOD) je technika vykreslování scény, určující míru detailu modelů (počet trojúhelníků) v závislosti na jejich vzdálenosti od kamery. Čím větší vzdálenost od kamery, tím nižší míra detailu. Tato metoda má vyšší výpočetní nároky a menší nároky na paměť než diskrétní (statický) LOD, který má pro každý objekt definováno několik úrovní detailu. CLOD vytváří modely s vhodnou úrovní detailu za běhu. Splatting je technika pro texturování terénu ve vysokém rozlišení umožňující užití růžných textur v různých částech terénu, mezi kterými je vytvořen lineární přechod.
3.4
Fraktální geometrie
Základem fraktální geometrie jsou geometrické útvary zvané fraktály (z latinského fraktus – rozlámaný nebo rozbitý), které jako první definoval Benoit B. Mandelbrot v šedesátých letech dvacátého století. Jednoduchá definice fraktálu neexistuje. Definic je několik a žádná není schopna obsáhnout všechny druhy. Hlavní rozdíl mezi základními geometrickými objekty a fraktály je v tom, že tvar fraktálu je nekonečně členitý (Tišnovsky P., 1999). Důležitou charakteristikou fraktálního objektu je jeho fraktální dimenze. Tato dimenze, na rozdíl od obvyklých celočíselných dimenzí (1, 2, 3 . . . ), může mít hodnotu racionálního nebo dokonce iracionálního čísla, např. 12 , nebo pí (Mandelbrot, Benoıˆıt B., 2003). Typem fraktálu, který se používá v počítačové grafice k modelování rostlin, jsou L-systémy.
3.5
L-systémy
Pro napodobení růstu rostlin vyvinul biolog A. Lindenmayer (roku 1968) matematickou teorii – L-systém. Původně byl určen jen pro velké části rostlin nebo buňky mnohobuněčných organizmů. Šlo spíše o obecnou topologii. S přidáním geometrie a její interpretací se L-systémy staly univerzálním nástrojem pro modelování rostlin(Prusinkiewicz P., 1990). Základní myšlenka L-systému je založena na přepisovacím systému. Opakovaným paralelním přepisováním pravidel se vytvoří komplexní objekt, který je z principu samotné tvorby soběpodobný (tedy fraktální). L-systém je formální gramatikou. Skládá se z axiomu a pravidel, která se opakovaně aplikují na model. Na rozdíl od Chomského formální gramatiky, kde se přepisovací pravidla aplikují postupně, v L-systému se pravidla používají paralelně (Prusinkiewicz P., 1990). Typickým příkladem objektu, generovaným přepisovacími pravidly, je Kochova křivka, případně Kochova vločka. Obsahuje axiom a jediné pravidlo. Tento systém později rozšířil Benoit B. Mandelobrot, který přidal systémy podporující přepisování úseček s rozdílnou délkou a hlavně podporu větvení topologií
3.5
L-systémy
19
Obr. 2: Kochova křivka, nultá až čtvrtá iterace. Převzato a upraveno (Petr Pauš, 2012)
(Prusinkiewicz P., 1990). Pravidla tedy mohou popisovat, zda se stonek rostliny rozdvojí. 3.5.1
D0L-sytémy
L-systémy se dělí do několika typů. Nejjednodušší typ, původní Lindenmayerův systém, je deterministický6 a bezkontextový D0L-systém7 . Skládá se pouze z abecedy symbolů, přepisovacích pravidel a axiomu. Formální zápis D0L-systému je následující (Prusinkiewicz P., 1990): G = (V, ω, P) kde • V je konečná abeceda symbolů, • ω je axiom – posloupnost symbolů nad abecedou, ω ∈ V+, • P je konečná množina přepisovacích pravidel, zapsaná jako a → u, kde a je symbol náležící V a u je slovo náležící V*. Z abecedy symbolů, např. a a b, se tvoří řetězce (slova). S každým symbolem je spojeno právě jedno přepisovací pravidlo. Např. pravidlo a → ab znamená, že každý znak a bude nahrazen řetězcem ab a pravidlo b → a značí přepsání znaku b znakem a. Přepisovací proces začíná řetězcem nazvaným axiom, který v tomto 6
Determinismus značí, že pro každý symbol existuje maximálně jedno pravidlo. Nula v názvu znamená, že se jedná o tzv. bezkontextový přepis. 7 Čteme [dé nula el systém].
3.5
L-systémy
20
Obr. 3: Příklad derivace v D0L-systému. (Prusinkiewicz P., 1990).
případě obsahuje pouze písmeno b. V první derivaci (přepsání symbolů – značeno ⇒) je axiom b nahrazen znakem a, podle pravidla b → a. V druhé derivaci je znak a nahrazen řetězcem ab. Slovo ab obsahuje dva znaky, oba budou v dalším derivačním kroku současně nahrazeny podle daných pravidel. Po páté derivaci má slovo tvar abaababa. Formální zápis příkladu a jeho derivace: G = ({a,b}, b, {a → ab, b → a}) b ⇒ a ⇒ a b ⇒ ab a ⇒ ab a ab ⇒ ab a ab ab a
3.5.2
Závorkové L-systémy
K vytváření lepších modelů stromů je dále nutné využít L-systém se závorkami, který umožňuje generovat větvené topologie modelu. Ačkoliv D0L-systém umí vytvářet čáru, která může sama sebe překřížit v závislosti na úhlu a délce jednotlivých částí, stále se bude jednat o systém tvořený z jediné čáry. Do přepisovacích pravidel jsou přidány symboly hranatých závorek, které umožní reprezentovat stromovou strukturu. Ta část řetězce, která je uzavřena v závorkách, reprezentuje samostatnou část objektu (větev stromu). Hranaté závorky představují funkce vložení a vyjmutí hodnoty ze zásobníku. 3.5.3
Stochastické L-systémy
Deterministické L-systémy jsou schopny generovat pouze identické modely rostlin. Pokud je potřeba vytvářet rostliny, které si budou podobné, ne však identické, je nutné přejít na stochastické L-systémy. Při vytváření variací rostlin stejného druhu musí zůstat zachována stejná struktura modelů. Odlišovat se však musí v určité míře náhodnosti, kterou obsahují stochastické L-systémy. Formální zápis stochastické gramatiky L-systému je následující:
3.5
21
L-systémy
Obr. 4: Rostliny vytvořené závorkovým L-systémem (Prusinkiewicz P., 1990).
G = (V, ω, P, π) kde • V je konečná abeceda symbolů, • ω je axiom – posloupnost symbolů nad abecedou, ω ∈ V+, • P je konečná množina přepisovacích pravidel, • funkce π – pravděpodobnost přidělení (suma všech pravděpodobností je rovna 1). Jednoduchý příklad stochastického L-systému: (Prusinkiewicz P., 1990)
ω:F p1 : F → F [+F ] F [−F ] F : 0.33 p2 : F → F [+F ] F : 0.33 p3 : F → F [−F ] F : 0.34
3.5
L-systémy
22
Obr. 5: Stochasticky větvená struktura rostlin (Prusinkiewicz P., 1990).
3.5.4
Aplikování L-systémů
Již závorkové L-systémy jsou dostatečné pro generování reálně vypadajících stromů. Ovšem za předpokladu, že budou dodržena určitá definovaná pravidla a omezení. Ta umožňují vytvářet modely rostlin s typickou strukturou větvení. Tyto struktury, které se právě vyskytují v přírodě, se dělit do několik typů.
Obr. 6: Příklady monopodiálního struktury větvení (Prusinkiewicz P., 1990).
Monopodiální struktura V této struktuře je dominantní stonek, který je souvislý, má největší tloušťku a končí na vrcholu stromu. Z kmene vychází vedlejší větve, které mají stejnou strukturu větvení jako stonek. Do této skupiny patří především jehličnany.
3.5
L-systémy
23
Sympodiální struktura Oproti monopodiální struktuře, sympodiální struktura nemá souvislý kmen. Kmen bývá obvykle při prvním dělení ukončen a nahrazen dvěma silnými větvemi. Větvení je v této struktuře menší, ale více složité než v předchozím případě. Do této skupiny patří listnaté stromy.
Obr. 7: Příklady sympodiálního struktury větvení (Prusinkiewicz P., 1990).
Ternarová struktura Ternarová (trojitá) struktura je obdoba sympodiální struktury. Liší se především trojitým větvením. Navíc je u gramatiky této struktury možné dodatečně zvětšit šířku a délku již vytvořených segmentů. Toho ale nelze dosáhnout závorkovými L-systémy.
Obr. 8: Příklady ternarové struktury větvení (Prusinkiewicz P., 1990).
3.5
24
L-systémy
Pravidlo šíře větví při větvení Toho pravidlo popsal již Leonardo da Vinci, který si všiml, že obsah všech průřezů větví po dělení je shodný s průřezem větve před rozdělením. Toto pravidlo bylo rozšířeno o vztah mezi šířkou větví a jejich úhlem, který svírají větve při dělení. Matthew Holton tento vztah určil na základě znalostí vnitřní cévní struktury větví. Cévy, sloužící k rozvodu živin ve stromě, mají také funkci zpevňující. Toto pravidlo říká, že tloušťka větve je při dělení určena úhlem odchylky od původní osy. Čím větší úhel, tím menší průměr větve (Holton, M., 1994).
Obr. 9: Ukázka poměru šířky větve ve vztahu k úhlu.
3.5.5
Kontextové L-systémy
D0L-systémy jsou bezkontextové, vytváření následníků tedy není nijak ovlivněno okolními částmi. U kontextových L-systémů je specifikován kontext přepisovaného symbolu, pro použití pravidla gramatiky. Kontext jsou symboly před a za přepisovaným symbolem. Tento způsob je užitečný pro interakci mezi jednotlivými částmi rostlin, které si mohou mezi sebou předávat informace, jako jsou délky a výskyty jednotlivých částí rostliny, např. květy, listy. Možná je i interakce s okolím L-systému a simulovat tak lze např. překážku v růstu, vliv ročního období a množství světla. Implementací kontextových L-systémů je více. Nejčastěji se používají 2Lsystémy a 1L-systémy, patřící do obecnější třídy IL-systémů, také označované jako (k,l)-systémy. V (k,l)-systémech je levý kontext slovo o délce k a pravý kontext slovo o délce l. 2L-systémy berou ohled na levý i pravý kontext symbolu a mají pravidla ve tvaru: lc < S > rc → X, kde S (předchůdce) může být přepsán pravou stranou X právě tehdy když leží mezi levým kontextem (lc) a pravým kontextem (rc). Jednodušší varianta s označením 1L-systém se používá pouze levý nebo pravý kontext pro všechna pravidla gramatiky. Pravidla mají tvar:
3.5
25
L-systémy
lc < S → X nebo S > rc → X Při kombinaci kontextových a bezkontextových pravidel L-systémů mají ta kontextová přednost při přepisování. Jednou z technik, které se využívají při modelování některých složitějších rostlin, je propagace signálu. Ta umožňuje posílání informací skrz řetězec symbolů. Příklad na 1L-systému: (Prusinkiewicz P., 1990) ω : baaaaaaaa p1 : b < a → b p2 : b → a Několik prvních slov generovaných touto gramatikou: baaaaaaaa ⇒ abaaaaaaa ⇒ aabaaaaaa ⇒ aaabaaaaa ⇒ aaaabaaaa V každé derivaci se po aplikaci pravidla p2 písmeno b přesouvá zleva doprava. Na písmeno a se aplikuje pravidlo p1, pokud se před ním nahází písmeno b, jinak se přepíše na a (zůstává beze změny). Kontextové rozšíření stromu L-systému vyžaduje, aby sousední hrany nahrazených hran stromu byly testovány na odpovídající kontext. Kontextové pravidlo p se skládá ze tří částí: • cesta L, tvořící levý kontext, • hrana S, zvaná předchůdce, • a axiální strom R, představující pravý kontext. Rozdílnost mezi levým a pravým kontextem odráží skutečnost, že existuje pouze jedna cesta od kořene stromu k hraně S, zatímco z této hrany může vést více cest do koncových uzlů. Pravidlo p odpovídá danému výskytu hrany S ve stromě T, pokud cesta L končí v počátečním uzlu S, a R je podstrom vyrůstající z koncového uzlu S. Pravidlo poté může být použito při nahrazení S s axiálním stromem, označeným jako předchůdce. Zavedení kontextu do závorkových L-systémů je obtížnější, protože se při hledání kontextu musí pracovat se stromovou strukturou. Například pravidlo s předchůdcem BC < S > G[H]M se může aplikovat na symbol S v řetězci
ABC[DE][SG[HI[JK]L]M N O],
3.5
26
L-systémy
Obr. 10: Předchůdce kontextového stromu (a) odpovídá hraně S stromu T (b) (Prusinkiewicz P., 1990).
kdy dochází k přeskočení symbolů [DE] při hledání levého kontextu a I[JK]L při hledání pravého kontextu. Levý kontext může být využit k simulování kontrolních signálů od kořene nebo bazálních listů k vrcholu modelované rostliny. Pravý kontext reprezentuje signály propagace od vrcholů rostliny ke kořenu. Například, následující 1L-systém simuluje propagaci signálu shora dolů ve větvové struktuře: #ignore : + − ω : F b[+F a]F a[−F a]F a[+F a]F a p1 : F b < F a → F b Symbol Fb reprezentuje segment, který obdržel signál. Symbol Fa je segment, který signál neobdržel. Sdělení # ignore označuje, že geometrické symboly + a − by měly být považovány za neexistující během porovnávání kontextu. Propagace signálu zdola nahoru je možné simulovat obdobným způsobem: #ignore : + − ω : F a[+F a]F a[−F a]F a[+F a]F b p1 : F a < F b → F b
3.5
L-systémy
27
Obr. 11: Propagace signálu zdola nahoru (a), a shora dolů (b) (Prusinkiewicz P., 1990).
3.5.6
Parametrické L-systémy
Žádný z předchozích L-systémů není schopen měnit velikost jednotlivých kroků. Jeho velikost je na začátku pevně stanovena a nelze ji v průběhu přepisování měnit. Stejné je to i pro definované úhly. Řešením je přidání parametru ke každému symbolu. Tento L-systém se nazývá parametrický, nebo také pL-systém. Parametrický L-systém pracuje s tzv. parametrickými slovy, což jsou řetězce modulů, skládající se z symbolů abecedy s přiřazenými parametry. Písmena patří do abecedy V, a parametry patří do množiny reálných čísel (R). Modul s písmenem A ∈ V a parametry a1 , a2 , . . . ∈ R, je označeno A(a1 , a2 , . . . an ). Modul M = V ×R∗ , kde R∗ je množina všech konečných posloupností parametrů.(Prusinkiewicz P., 1990) Parametrický 0L-systém je definován jako uspořádaná čtveřice: P G = (V, , ω, P) kde • V je konečná abeceda symbolů, P • je množina formálních parametrů,
3.5
28
L-systémy
Obr. 12: Ukázky rostlin a jejich gramatik vytvořené 2L-systémem (Prusinkiewicz P., 1990).
• ω je nepráždné parametrické slovo zvané axiom, • P je konečná množina přepisovacích pravidel. Pravidla mají tvar: předchůdce:podmínka → následník Například, pravidlo s přepisovaným symbolem A(t), podmínkou t > 5 a pravou stranou B(t + 1)CD(t ∧ 0.5, t − 2)se zapisuje: A(t) : t > 5 → B(t + 1)CD(t ∧ 0.5, t − 2).
3.5
L-systémy
29
Následující ukázka jsou stromové struktury vytvořené pomocí jediného pravidla, ale s různým nastavením konstant.
Obr. 13: Stromy vytvořené pomocí parametrického L-systému (Prusinkiewicz P., 1990).
3.5.7
Interpretace gramatiky želví grafikou
Pro interpretaci L-systému se využívá tzv. želví grafiky (turtle graphics). V roce 1986 Przemyslaw Prusinkiewicz využil pohybu želvy, z programovacího jazyka LOGO, k interpretaci L-systémů. Želva představuje virtuální kurzor, který je ovládán příkazy pro posun nebo otočení. Želva svým pohybem kreslí spojitou čáru. Želva je definována svým stavem a tabulkou akcí. Stav želvy je v dvourozměrném prostředí určen trojicí (x, y, α), kde kartézské souřadnice (x, y) představují polohu želvy a úhel α představuje orientaci želvy, kterým směrem se želva dívá. S danou velikosti kroku d a úhlu δ čte postupně želva symboly abecedy, které interpretuje podle tabulky akcí následujícím způsobem: • F — posun želvy o krok d dopředu a vykreslení čáry mezi body (x, y) a (x’, y’), • + — otočení želvy doleva o úhel δ, • − — otočení želvy doprava o úhel δ. Příkladem interpretace gramatiky D0L-systému želví grafikou např. Kochova křivka (Obr. 1): G = ({F, A, +, −}, A, {A → F, F → F + F − −F + F }) A ⇒ F ⇒ F + F − −F + F ⇒ F + F − −F + F + F + F − −F + F − −F + F − −F + F + F + F − −F + F Pro symboly + a − nejsou definovaná žádná pravidla, jelikož se při derivacích přepisují na tentýž symbol. V těchto případech se pravidla neuvádějí (jejich zápis by byl + → + a − → −). Ve trojrozměrném prostoru je orientace želvy tvořena třemi vektory H, U, L a společně s polohou tvoří lokální souřadnicový systém. Vektory mají následující význam (Žára J., 2004):
3.5
L-systémy
30
Obr. 14: Vektory a rotace želvy pro 3D.
• H (heading) — směr, kterým se želvy pohybuje dopředu, • U (up) — směr, ve kterém má krunýř, • L (left) — na které straně má levou přední (i zadní) nožičku. Pro tabulku akcí jsou navíc definovány symboly rotací: • & — rotace dolů podle vektoru L, • ˆ — rotace dolů podle vektoru L, • / — rotace doleva podle vektoru H, • \ — rotace doprava podle vektoru H. Pro možnost větvení je abeceda rozšířena o hranaté závorky, používané v gramatikách závorkových L-systémů. Želva je obohacena o zásobník, do kterého si ukládá svůj stav, do kterého se později navrátí po přečtení obsahu závorky. Symbol [ reprezentuje uložení aktuálního stavu želvy na vrchol zásobníku, naopak symbol ] reprezentuje návrat želvy do posledního uloženého stavu z vrcholu zásobníku. Interpretací gramatiky se závorkami může být řetězec F[+F]F (Obr. 9). Želva začíná vykreslením čáry při posunu dopředu (symbol F) uloží svůj stav do zásobníku (symbol [) otočí se doprava (symbol +) opět se posune dopředu, načte stav ze zásobníku (symbol ]), což ji vrací zpět, a naposledy se posouvá dopředu (Žára J., 2004). Dalším rozšířením gramatik jsou otevřené L-systémy (Open systems), což je souhrnné označení pro stochastické, kontextové a parametrické L-systémy. Otevřené znamená, že mohou interagovat s okolím. Interakce je obousměrná.
3.5
31
L-systémy
Obr. 15: Interpretace řetězce F[+F]F.
Stochastický L-systém rozšiřuje gramatiku o pravděpodobnost, že bude nějaký symbol gramatiky přepsán právě tímto pravidlem. Tato pravděpodobnost musí být u stejných symbolů v součtu rovna jedné. A → B : pp Kontextový L-systém rozšiřuje levou stranu pravidel o řetězce symbolů vlevo a vpravo od přepisovaného symbolu. Tento kontext určuje, kdy může být symbol přepsán pomocí tohoto pravidla. lc < A > rc → B Parametrický L-systém přidává do gramatiky množinu formálních parametrů, které se přidávají k symbolům abecedy. Želva při postupném čtení jednotlivých symbolů interpretuje jejich parametry geometrickým způsobem, např. změnou velikosti kroku, úhlu natočení, tloušťky čáry a jiné. Pravidla v parametrických kontextových L-systémech mají tvar: (Žára J., 2004) id : lc < A > rc : cond → B : prob, kde • id je návěští — číslo pravidla, • lc, rc je levý a pravý kontext, • cond (comdition) je logický výraz nabývající hodnoty 1 nebo 0, • prob (probability) je pravděpodobnost, s jakou bude toto pravidlo aplikováno při shodě levých stran více pravidel. Příklad pravidla může vypadat takto: p1 : A(y) : y < 3 → B(x).
3.5
32
L-systémy
Toto pravidlo se provede pouze v případě, že je splněna podmínka y < 3. Otevřené L-systémy jsou rozšířené o tzv. komunikační moduly, které se využívají pro přenos informací mezi okolím objektu a jeho moduly. Obecný zápis modulů je následující: ?E(x1 , x2 , . . . , xm ). Než začne fáze přepisování, je potřeba doplnit hodnoty skutečných parametrů komunikačních modulů x1 , x2 , . . . xm , které nejsou v začátku známé. Prohlížením jednotlivých modulů zleva doprava se postupně vypočítává stav želvy v prostoru, aniž by docházelo k vytváření geometrického modelu. Při určení komunikačního modulu se vygeneruje zpráva dotazující se na hodnoty parametrů. Ta je poslána prostředí, které tyto parametry nastaví. L-systém pokračuje v prohlížení modulů, dokud nejsou nastaveny všechny parametry všech komunikačních modulů. Poté následuje shodná přepisovací fáze jako v případě parametrických L-systémů. Následující příklad L-systému (z knihy Moderní počítačová grafika) zabraňuje tomu, aby objekt vyrostl do větší výšky než dva:
ω : F (0, 0)A?E(0) p1 : A >?E(y) : y < 2 → F (x, y + 1)A p2 : A >?E(y) : y ≥ 2 → . Modul F(x,y) vykreslí úsečku v rovině z aktuálního stavu do bodu daného souřadnicemi x, y. První pravidlo má omezení pro vykreslování vrcholu. Pokud má být hranice y = 2 překročena, aplikuje se druhé pravidlo, které nedoplní symbol A při následné derivaci. Derivace má následující tvar: F(0,0)A?E(0) ⇒ F(0,0)F(0,1)A?E(1) ⇒ F(0,0)F(0,1) F(0,2)A?E(2) ⇒ F(0,0)F(0,1) F(0,2)?E(3).
4
ANALÝZA 3D ENGINU
4
33
Analýza 3D enginu
Výsledkem provedené analýzy herních enginů by měla být jasná volba konkrétního enginu, který má nejvhodnější vlastnosti a možnosti pro řešení zadání diplomové práce. Současně analýza poslouží k potvrzení nebo vyvrácení předpokladu, že dostupné enginy nemají k dispozici vlastní nástroj pro vytváření modelů rostlin, jejichž generování je založeno na možnosti přímo upravovat daný L-systém.
4.1
Stanovená kritéria
Začátkem analýzy je stanovení přehledu předpokládaných vlastností, které by měly zúžit seznam vhodných enginů na minimum, ideálně na jediný. Pořadí jednotlivých faktorů v seznamu neurčuje jejich důležitost a některé z nich nemusí být ve výsledku vůbec zohledněny pro určení výsledného enginu. Uvažované hodnotící faktory jsou následující: • Licence • Způsob instalace a konfigurace • API — DirectX nebo OpenGL • Operační systém • Podpora grafických formátů • Grafické vlastnosti • Stabilita • Rozšiřitelnost • Snadnost užití • Dokumentace a podpora Prvním krokem bude stažení a instalace některého z placených enginů, který bude dostupný např. ve trial-verzi. Dalším krokem analýzy bude zhodnocení volně dostupných enginů. Pro vyhodnocení nejvhodnějšího enginu bude také využito některé metody pro hodnocení variant, využívaných např. v managementu.
4.2
Komerční engine
Komerční engine, který jsem využil pro zjištění obecných vlastností a parametrů, je Unity 3.4.1., dostupný v plné verzi na oficiálních stránkách firmy Unity Technologies k 10. 11. 2011 (http://unity3d.com/). Velikost instalačního souboru byla 412 MB. Komerční enginy zpravidla nabízejí komplexní řešení pro vytváření počítačových her. V balíku aplikací se nejčastěji vyskytují různé editory, např. pro tvorbu
4.2
Komerční engine
34
prostředí, popř. i samotných modelů. Dále aplikace pro transformování formátů pro import nebo export objektů, aplikace pro práci se zvukem a další. Unity má do enginu integrovaný editor prostředí a modelů, který nabízí možnost modelovat stromy pomocí nástroje pro tvorbu vegetace.
Obr. 16: Program Unity.
Instalace enginu je stejná, jako u typických aplikací pro osobní počítače (tzv. wizzard) a není zde ani potřeba žádné dodatečné nastavení aplikace před zahájením práce. Tento uživatelky nejpřívětivější způsob instalace, včetně žádné konfigurace, však nepředpokládám u volně dostupných enginů. Při spuštění programu Unity se na úvod zobrazí uvítací okno, které nabízí prvotní informace o produktu a také webové odkazy na video tutoriály a dokumentaci. Možnost využití dokumentace, tutoriálů a diskuzního fóra je dobré pro rychlejší a snadnější nastudování daného programu, ač se nejedná o její přímou součást a nesouvisí přímo s jeho vlastnostmi. Při spuštění programu Unity se otevře okno editoru, který umožňuje kdykoliv se přepnout z režimu editace prostředí do enginem vytvořeného virtuálního prostředí. Při přeložení dokončené scény umožňuje Unity vytvořit program hry pro několik druhů platforem, konkrétně – Web player, Mac a Win standalone, iOS, Android, Xbox 360, PSP 3 a Wii.
4.2
Komerční engine
35
Mezi další přednosti patří podpora formátů obrázků a objektů. Již ve video tutoriálu je předvedena schopnost pracovat souběžně s programy, prostřednictvím graphic pipeline, které nejsou vyvíjené stejnou společností, např. 3D Studio MAX a Adobe Photoshop. Pro volně dostupně enginy bude potřebná alespoň možnost importování a exportování jednoho externího formátu objektů (např. obj) a podpora nejčastěji používaných grafických formátů (bmp, jpg, png a další). Základním prvkem každé scény je terén. Pro jeho vytvoření má Unity vlastní záložku v hlavním menu a propracované nástroje ve formě štětců pro vytváření nerovností terénu. Umožňuje také vytvořit souvislé plochy vegetace z předpřipravených modelů stromů. Jednotlivé modely stromů lze editovat a vytvářet v nástroji pro tvorbu stromů. Editor Unity má uživatelsky přívětivé rozhraní a poskytuje velké množství prvků k vytváření scény. Pro uživatele znalého některého z 3D nástrojů by neměl být problém naučit se s editorem pracovat. 4.2.1
Nástroj pro tvorbu stromu
Jak již bylo zmíněno víše, Unity obsahuje svůj vlastní nástroj pro vytváření modelů stromů. Nejedná se o zásadní prvek analýzy enginu, ale pro tuto práci je vhodné se zmínit, jakým způsobem jsou tyto typy modelů vytvářeny. Nástroj je rozdělen do tří různých částí: Okno hierarchické struktury stromu, Editační nástroje a Vlastnosti. Část panelu zobrazující hierarchickou strukturu stromu umožňuje jednoduše vytvořit a spravovat každou část stromu. Příklad z obrázku 13 ukazuje strom o jednom kmeni s 25 větvemi, každá mající 70 vějířovitých listoví, 280 listů jednoho typu a 25 větví s isty. Také kmen má dva druhy listů, přičemž jeden typ je skrytý.
Obr. 17: Okno hierarchické struktury stromu (Unity3D, 2011).
4.3
Volně dostupné enginy
36
Další částí jsou nástroje pro editaci modelu, umožňující ručně manipulovat vybranou části stromu, konkrétně uzly nebo body křivek. Nabízené možnosti jsou ruční kreslení, pohyb a rotace. První kořenový uzel určuje počáteční bod a globální vlastnosti stromu. Obsahuje parametry pro generování stromu jako celek. Nastavení materiálu, geometrie a rozložení částí stromu.
4.3
Volně dostupné enginy
Volně dostupné enginy se podstatně odlišují od placených verzí. Často bývají vyvíjeny malými skupinami nadšenců, případně i jednotlivci. Pokud není engine vyvíjen firmou, bývá velký rozdíl, oproti placeným, především v kvalitě grafiky. Podstatně se liší svojí velikostí a bývá potřebná konfigurace před prvním spuštěním. Je potřeba využít některého z textových editorů, např. Visual Studio, Code::Block, Eclipse a zřídka kdy je k dispozici nějaká forma grafického uživatelského rozhraní. Zpravidla neobsahují vlastní editory, pouze nejnutnější nástroje pro konverze formátů, přidání zvuků apod. Určité riziko představuje ukončení vývoje projektu ze strany tvůrců, kdy engine velmi rychle zastarává a přestává být „živýmÿ. Výhodu může představovat velké množství uživatelů, kteří společně vytváří rozsálá diskuzní fóra, tutoriály a návody. Začátkem analýzy je stanovení přehledu předpokládaných vlastností, které by měly zúžit seznam vhodných enginů na minimum, ideálně na jediný. Pořadí jednotlivých faktorů v seznamu neurčuje jejich důležitost a některé z nich nemusí být ve výsledku vůbec zohledněny pro určení výsledného enginu. Uvažované hodnotící faktory jsou následující: Devmaster (http://devmaster.net/) je webový portál určený pro vývojáře počítačových her, který mimo jiné obsahuje databázi veřejně dostupných herních enginů. Tato databáze obsahuje 334 položek (k 10.1.2012) a poslouží mi jako výchozí seznam možných enginů pro tuto práci. Databáze obsahuje i některé možnosti filtrování enginů podle jejich vlastností, např. licence, platforem na kterých fungují a programovací jazyky ve kterých je engine napsán a které podporuje. Těchto možností filtrace bude využito jako prvních. Prvním kritériem zužující počet vhodných enginů jsou licenční podmínky pro jeho užití. Pro užití v rámci výuky na univerzitě je nejvhodnější licence pro svobodný software. Databáze rozlišuje tyto druhy licencí: • GLP — všeobecná veřejná licence (General Public Licence), svobodný softwar • LGPL — permisivnější varianta GPL (Lesser GPL) • ZLIB — veřejně dostupný software, kompatibilní s GPL • MIT — svobodná licence pocházející z Massachusetts Institute of Technology
4.3
Volně dostupné enginy
37
• BSD — nejrozšířenějších a nejsvobodnější licence (Barkeleay Software Distribution) • Mozilla Public Licence — svobodná a open source licence, kombinace GLP a BSD • Commom Public License — svobodná a open source licence od IBM • Open Source • Proprietary — licence, která je definována vývojářem Dalším omezujícím kritériem je možnost užití pod OS Microsoft Windows, jelikož se jedná o nejrozšířenější systém u nás. Funkčnost i pod systémy Linux a MacOS není nezbytná. Poslední možností pro zúžení seznamu enginů je zvolení programovacího jazyka, ve kterém je engine napsán a které podporuje. Mým minimálním požadavkem je jazyk C/C++. Při zvolení platformy Windows, programovacím jazyku C/C++ je k dispozici na 233 možností. Výsledný počet možností pro jednotlivé licence je následující: • GLP — 25 • LGPL — 15 • ZLIB — 9 • MIT — 8 • BSD — 9 • Mozilla Public Licence — 4 • Commom Public License — 0 • Open Source — 171 • Proprietary — 2 V rámci webového portálu Devmaster byly následně zhodnoceny obecné vlastnosti u jednotlivých nabízených enginů a odstraněny nevyhovující. Následující seznam obsahuje vybrané enginy, které jsou neplacené, případně mohou být užity pro nekomerční účely bezplatně. Dále nebyly zahrnuty enginy, které byly zastaralé nebo se zcela nedostatečnou úrovní grafiky, případně enginy, které byly specializovány pouze na některou oblast z počítačové grafiky. Pro přehlednost ponechávám následující seznam enginů roztříděn podle jejich druhů licencí, přestože toto kritérium již není důležité.
4.3
Volně dostupné enginy
GPL • Cafu Enfine • DXQuake 3 • Blander Game Engine • Zythum Project LGPL • Crystal Space • OpenSceneGraph • Delta3D ZLIB • Irrlicht • Lightfeather 3D Engine • Cube 2: Sauerbraten • SoftPixel-Engine MIT • Ogre • Nebula Device 2 BSD • Panda3D • Syntensity Engine Proprietary • CryEngine 3 • C4 Engine • DX Studio Open Source • Unreal Engine 3 • Vital Engine 2 • Codecreatures
38
4.3
Volně dostupné enginy
39
• kjApi • Jolt3D! • Esperient Creator • Planta • Esenthel Engien • Infernal Engine • Vision Game Engine • CPAL3D • S2Engine HD V dalším kroku již nebyly nevyužity informace z portálu Devmaster. Jako zdroj informací byly využity oficiální stránky jednotlivých enginů. Tabulka obsahující informace o enginech je uvedena v příloze A. 4.3.1
Detailnější popis enginů
Do nejužšího seznamu se dostalo šest enginů. Následuje krátký popis jejich podstatných vlastností a možností.
Obr. 18: Cafu engine (Cafu, 2012).
Cafu Engine Engine vyvíjený společností Carsten Fuchs Software. Lze jej použít pod Windows a Linux (obojí dostupné pro 32-bit i 64-bit verze), a v budoucnu i pod Mac OS X. Software se neinstaluje (Software Development Kit, dále jen SDK) a k enginu jsou přidány další aplikace. Jednou z aplikací je Editor, mající možnost vytvářet scény, upravovat modely, herní GUI a Fonty. Editor modelů neslouží k vytváření nových modelů, ale pro jejich importování a převedení do vlastního formátu. Nabízí grafický a strukturní náhled modelů před použitím v enginu a úpravu některých parametrů, např. nastavení materiálu, animací, kolizí apod. Podporuje následujících deset formátů: • vlastní — .cmdl (native model file format), • herní — .md5 (Doom3, Quake4) a .mdl (Half-Life1), • grafických editorů — .3ds (3S Studio Max), .dfx (Autodesk AutoCAD), .fbx (Autodesk), .lwo (Lightwave Object),
4.3
Volně dostupné enginy
40
• značkovacích jazyků — .dae (Collada), .ase (Acsii Scene Export). Podporované souborové formáty jsou .jpg, .png, .tga a .bmp. K dispozici je také audio podpora a 3D zvukové efekty. Možné je vytvořit vlastní herní GUI a vlastní fonty. Cafu engine nabízí možnosti pro rozšíření, a to podporou skriptování, založeném na Lua Programming language, popřípadě využitím rozhraní jazyka C++ k vytvářením nových aplikací a her. Webové stránky obsahují dokumentaci a diskuzní fórum s necelými čtyřmi sty členy.
Obr. 19: IrrLicht engine (IrrLicht, 2012).
Irrlicht Engine vytvářený skupinou nadšenců. Open source a cross-platform (využívá OpenGL, Direct3D a vlastní softwarové rendery), napsaný v jazyce C++. Engine se neinstaluje a má širokou podporu formátů (.obj, .3ds, .lwo, .xml, .dae, .md3,. . . ). Podporované souborové formáty jsou .jpg, .png, .tga, .bmp, .pcx, .ppm, .psd, .wall a .rgb. Na stránkách jsou dostupné zdarma další nástroje – IrrKlang pro práci se zvukem, IrrEdit pro vytváření scén a xml parser pro C++, IrrXML. Samotní autoři se starají o vytváření tutoriálů, dokumentace a irrlicht wiki, a spravují také diskuzní fórum, do kterého se aktivně zapojují.
Obr. 20: Logo Ogre engine (Ogre3d ,2011).
Ogre Ogre (Object-Oriented Graphics Rendering Engine) je scénově orientovaný 3D engine, napsaný v C++. Není primárně orientovaný pro vytváření her. Jedná se o bezplatný, týmově vyvíjený engine. Podporuje OpenGL a DirectX, použitelný pod operačními systémy Windows, Linux a Mac OS X. Nejedná se o instalovatelný produkt SDK (je však potřeba naistalovat např. DirextX) a pod OS Windows je podporováno nastavení s aplikacemi Visual Studio, Code Blocks a QtCreator. Jsou podporovány i alternativní jazyky Python, Java, C#, .NET. Umožňuje import souborů z programů Miklshake3D (.ms3d), 3D Studio Max, Maya (.iff), Blender (.blend) a Wings3D (.wings). Podporované formáty jsou .png, .jpeg, .tga, .bmp, .dds, a také netypické 1D textury, volumetrické textury, cubemaps, HDR (Hight Dynamic Range) a komprimované textury (DXT/S3TC). V rámci oficiální dokumentace je k dispozici manuál, wiki i knihy.
4.3
Volně dostupné enginy
41
Obr. 21: Logo DxStudio (DxStudio, 2012).
DX Studio DX Studio je programový balíček pro vytváření interaktivní 3D grafiky. Obsahem je engine a několik editačních nástrojů. Jedná se o produkt od společnosti Worldweaver. Program se instaluje a po puštění se otevře okno real-time editoru. Real time editor umožňuje spojit prostředí, modely, zvuky a efekty do jediné scény a nastavit její vlastnosti. Podporovanými formáty editoru jsou .dxmesh (vlastní formát), .dae, .x a .3ds. Editor využívá JavaSript k nastavení událostí ve scéně využitím vlastního editoru. Dokumenty DX Studia lze také publikovat na webu. K dispozici je i rozsáhlá dokumentace s tutoriály a diskuzní fórum.
Obr. 22: Logo CryEngine 3 (CryEngine, 2012).
CryEngine 3 Placený profesionální engine, který lze užívat zdarma pro studijní účely. Vyvíjen společností Crytek. Engine je využíván některými komerčně známými herními tituly. Po nainstalování programu je k dispozici komplexní sada nástrojů pro vytváření her. Profesionální editor pro vytváření scén, včetně modelování objektů od základů, zvuky efekty i stereoskopické vykreslování obrazů. Nabídnuta je, v porovnání s ostatními enginy, nejvyšší úroveň grafiky. Engine není možné rozšiřovat. K dispozici je dokumentace a tutoriály.
Obr. 23: Esenthel engine (Esenthel, 2012).
4.4
Matice hodnocení faktorů konkurenčních enginů
42
Esenthel Engine ´ nski je jediným autorem a programátorem Esenthel engine. Grzegorz Slazi´ Jedná se o SDK s využitím Visual Studia. Mezi podporované platformy patří Windows, Mac OS X, iOS a Google Android. V balíčku aplikací se nachází Model Editor, World Editor, Gui Editor, Code Editor a další. Podporované formáty jsou .bmp, .png, .jpg, .tga, .dds, .psd a vlastní .gfx. K převodu je nutno použít nástroj pro konverzi formátů. Modely lze importovat z mnoha formátů, např. .3ds, .dae, .fbx, .obj, .x, .ms3d. Dokumentace je řešena prostřednictvím wiki a k dispozici je také diskuzní fórum. Oficiální webové stránky jednotlivých enginů: http://www.cafu.de/ http://irrlicht.sourceforge.net/ http://www.ogre3d.org/ http://www.dxstudio.com/ http://mycryengine.com/ http://www.esenthel.com/
4.4
Matice hodnocení faktorů konkurenčních enginů
Matice hodnocení faktorů konkurenčních enginů je mnou upravená Matice hodnocení faktorů vnějšího prostředí EFE (dále jen matice EFE), používaná např. v managementu. Důvodem volby této metody při porovnání jednotlivých enginu je její možnost zohlednit obecný vliv každé vlastnosti (faktoru) a to stanovením pořadí její důležitosti. To se značně projeví po stanovení úrovně naplnění vlastností u každého enginu. Úprava matice EFE spočívá v nahrazení vnějších faktorů prostředí za hodnocené vlastnosti enginů. Tabulka navíc hodnotí současně více enginů. Tudíž, na rozdíl od matice EFE, výsledná číselná hodnota nevyjadřuje žádnou míru reakce. Výsledem matice bude číselná hodnota pro každý engine. Čím vyšší číslo, tím lepší engine. Výsledky této metody budou sloužit jako pomocné kritérium při volbě nejvhodnějšího enginu. Prvním krokem bude stanovení faktorů, které budou hodnoceny u zbývajících enginů. Jedná se o vlastnosti, které doposud nebyly brány v potaz, především z důvodu časové náročnosti dohledávání údajů pro tak velké množství enginů. Faktory: • Instalace — velikost instalačního souboru a způsob instalace, konfigurace. • Rozšiřitelnost — možnosti rozšíření aplikace např. o další aplikace nebo moduly. • Snadnost užití — přenositelnost souborů z/do jiných aplikací (import/export objektů); dále také složitost samotného enginu a jeho ovládání (GUI vs. CLI).
4.4
43
Matice hodnocení faktorů konkurenčních enginů
• Dokumentace — oficiální i neoficiální návody pro práci s enginem včetně dostupných tutoriálů. • Podpora — zahrnuje možnost komunikace s jinými uživateli v rámci diskuzních fór, případně i s vývojáři. Postup vyplnění matice: Vliv faktorů Určuje obecný vliv faktoru, bez ohledu na jednotlivé enginy. Faktory se seřadí podle důležitosti (čísla od 1 do X). Následuje přiřazení vah přepočítáním bodového hodnocení využitím principu relativních četnosti. Váhy jsou v intervalu (0,1) a součet je roven 1. Zohlednění pro jednotlivé enginy Přiřazení známky faktoru konkrétního enginu podle toho, do jaké míry daný faktor naplňuje. Známky jsou z intervalu <1,4> (vhodná jsou celá čísla), přičemž 1 znamená nejnižší naplnění faktoru a 4 nejlepší možné naplnění faktoru. Posledním krokem je výpočet váženého skóre pro každý faktor (váha∗známka) a následně jejich součtem získáme celkové vážené skóre pro každý engine. Váhy: • 1 — velmi slabé • 4 — velmi silné
Tab. 1: Tabulka hodnocení variant
Engine
instal.
rozšířit.
bodové hodnocení vahy Cafu engine Irrlicht Ogre DX Studio CryEngine Esenthel Engine
4 0,27 2 0,53 2 0,53 2 0,53 4 1,07 4 1,07 3 0,80
1 0,07 0,27 0,27 0,27 0,07 0,07 0,07
4 4 4 1 1 1
snad. už.
2 2 2 3 2 3
3 0,20 0,40 0,40 0,40 0,60 0,40 0,60
dok. 5 0,33 3 1,00 4 1,33 4 1,33 2 0,67 2 0,67 1 0,33
podpora
3 3 3 2 2 2
2 0,13 0,40 0,40 0,40 0,27 0,27 0,27
suma 15 1 2,60 2,93 2,93 2,67 2,47 2,07
Shrnutí analýzy Analýza především ukázala, že je k dispozici velké množství herních enginů. Více než dvě stě z nich jsou k dispozici zdarma, nebo pro nekomerční účely a některé další jsou vyvíjeny pouze v rámci společností, podnikajících v herním průmyslu.
4.4
Matice hodnocení faktorů konkurenčních enginů
44
Mezi volně dostupnými enginy jsou velké rozdíly, a to především v úrovni grafiky a dodatečných nástrojích, které nabízejí. Někteří autoři své enginy propracovali na úroveň dostatečnou na to, aby založili menší společnost, která engine nabízí a dále rozvíjí na profesionální úrovni. Naproti tomu velká část volně dostupných enginů je vyvíjena „na koleněÿ a jejich využití je poměrně riskantní. Některé enginy jsou úzce specializované a slouží především k simulaci fyziky, např. chování světla. Dostupné jsou i verze profesionálních enginů, které nabízejí kompletní balík aplikací pro vytváření vlastních her. Zde nejsou potřeba téměř žádné znalosti programování. Mají propracované grafické prostředí na úrovní aplikací pro vytváření 3D grafiky, které je zpravidla velmi intuitivní a nečiní problém vytvořit velmi složité a veliké scény. Jako výchozí seznam enginů jsem využit server DevMaster.net. Z počáteční nabídky více než tří set enginů jsem snížil počet uvažovaných enginu na finálních šest, a to především vyřazením enginů, které byly zastaralé, specializované, určené pro webové aplikace, nebo byly komerční. Nejvhodnějším enginem pro tuto práci je IrrLicht. Především je graficky dostačující a s rozsáhlou dokumentací. Hlavní předností je jeho nástroj IrrEdit, který je dostačující pro účely této práce, bez nutnosti použití samotného engin. Dalším zvažovaným enginem byl Ogre, který je určen spíše pro experimenty a simulace. A také Cafu Engine, který obsahuje vlastní nástroj pro editaci. Na závěr analýzy musím konstatovat, že žádný engine, který jsem podrobněji studoval nebo testoval, neobsahoval nástroj pro přímé generování L-systémů.
5
NÁSTROJ PRO VYTVÁŘENí MODELŮ STROMŮ
5
45
Nástroj pro vytváření modelů stromů
Analýza neposkytla engine, který by obsahoval adekvátní nástroj pro generování stromů využívající L-systémy. Proto bylo nutné vytvořit vlastní program. Program jsem vytvořil v jazyce c++ s využitím grafické knihovny OpenGL (Open Graphics Library). Pro tvorbu grafického rozhraní jsem použil knihovnu Glui 2.36. Jako editor jsem použil program Code::Blokcs 10.05, pod operačním systémem Microsoft Windows 7.
Obr. 24: Program LSys Generator
5.1
Příkazy želví grafiky
L-Systém je generován definováním axiomu, pravidel a počtem iterací (opakování). Axiom je prvotní sekvence symbolů gramatiky, která by měla obsahovat alespoň jeden symbol z levých stran přepisovacích pravidel. Pravidla se skládají z levé a pravé strany, přičemž levá strana určuje znak, který se má přepsat symboly pravé strany.
5.1
46
Příkazy želví grafiky
Oddělujícím znakem je rovnítko („=ÿ). Počet iterací určuje, kolikrát se má cyklus přepisování zopakovat. Příklad: Axiom: FX Pravidlo: X = [+FX][-FX] Počet iterací: 2 F X ⇒ F [+F X][−F X] ⇒ F [+F [+F X][−F X]][−F [+F X][−F X]] Objektem, který se využívá jako stavební blok modelu, je válec. Ten se vykreslí při posunu želvy dopředu (F). U válce je možné stanovit jeho výšku a dolní a horní poloměr. Tab. 2: Tabulka základních symbolů gramatiky
Symbol F f + −
Funkce Posun želvy o jeden krok dopředu a kreslení válce Posun želvy o jeden krok dopředu bez kreslení válce Pootočení želvy doleva o zadaný úhel (rotace Z) Pootočení želvy doprava o zadaný úhel (rotace Z)
Další částí je stanovení velikostí úhlů pro rotace v L-Systému. V dvourozměrném systému stačí jediný úhel. Pro trojrozměrný prostor jsou potřeba úhly tři. Rotace se realizují kolem tří vektorů X, Y a Z8 , a společně s polohou želvy je určen její lokální systém. Vektor Y označuje směr pohybu želvy. V OpenGL se rotace okolo tří vektorů realizuje využitím následujících rotačních matic: cos(α) sin(α) 0 0 −sin(α) cos(α) 0 0 RZ (α) = 0 0 10 0 0 01 1 0 0 0 0 cos(α) −sin(α) 0 RX (α) = 0 sin(α) cos(α) 0 0 0 0 1 cos(α) −sin(α) 0 0 1 0 0 RY (α) = sin(α) 0 cos(α) 0 0 0 0 1 8
V literatuře se nejčastěji uvádějí vektory H, L, U. Já jsem ale pro jednoduchost ponechal označení využívaná v kartézské soustavě souřadnic.
5.1
47
Příkazy želví grafiky
Následující tabulka zobrazuje přehled znaků podporované gramatiky L-Systému pro pohyb želvy a její rotace v trojrozměrném prostoru: Tab. 3: Tabulka symbolů gramatiky pro pohyb želvy v trojrozměrném prostoru
Symbol
Funkce Pootočení Pootočení Pootočení Pootočení
^ & < >
želvy želvy želvy želvy
doleva o zadaný úhel (rotace X) dodoprava o zadaný úhel (rotace X) doleva o zadaný úhel (rotace Y) dodoprava o zadaný úhel (rotace Y)
Program umožňuje realizovat závorkové L-systémy, nutné pro vytváření rozvětvených struktur modelu. Využívá se zásobníku, který je v gramatice realizován symboly levé hranaté závorky „[ÿ a pravé hranaté závorky „]ÿ. Část pravidla, která je obsažena v hranatých závorkách určuje samostatnou část systému (např. větev). Tab. 4: Tabulka symbolů gramatiky pro práci se zásobníkem
Symbol [ ]
Funkce Uložení aktuálního stavu želvy Návrat želvy do posledního uloženého stavu
K dosažení větší reálnosti modelu je potřebná možnost změnit parametry jednotlivých elementů v průběhu jejich vykreslování. Základní možností jsou snižující se šířky a délky válce (kroku želvy). Míra změny se postupně zvětšuje v každém kroku želvy. K dalším možnostem uprav gramatiky a modelu L-systému patří nahodilost. A to možností náhodné změny ve velikosti úhlů a simulací působení gravitace. Tab. 5: Tabulka pomocných symbolů gramatiky
Symbol / * ! @ t
Funkce Otočení želvy o 180◦ (rotace Z) Návrat želvy na začátek Zmenšení délky válce Zmenšení šířky válce Zohlednění působení gravitace
Další možností gramatiky je přidání parametru k některým symbolům. Parametr je uveden v kulatých závorkách za znakem, ke kterému se vztahuje. Hodnota tohoto parametru se použije namísto globálně definované hodnoty. Číslo udávající hodnotu parametru je v programu omezeno formátem pěti číslic s desetinou tečkou (xxx.xx). Rozmezí je tedy od 000.01 do 999.99. Parametr nemění hodnotu globální proměnné. Znaky podporující parametry jsou uvedeny v tabulce 5.
5.2
Knihovna pro grafické rozhraní
48
Tab. 6: Tabulka parametrických symbolů gramatiky
Symbol F(x), f(x) +(α), −(α) ^(α), &(α) < (α), > (α) @(x) !(x)
5.2
Funkce Posun želvy o jeden krok dopředu o velikost x Otočení želvy kolem osy Z o úhel α Otočení želvy kolem osy X o úhel α Otočení želvy kolem osy Y o úhel α Snížení délky kroku želvy Zmenšení poloměru vykresleného válce
Knihovna pro grafické rozhraní
GLUI (GL User Interface) je na GLUT9 založená knihovna pro vytvoření základních ovládacích grafických prvků, jako jsou tlačítka, checkboxy a další, pro OpenGL aplikace. Je dostupná zdarma na oficiálních stránkách (http://www.cs.unc.edu/ rademach/glui/). Instalace knihovny v úvodu nebyla snadná, jelikož chyběla potřebná knihovna „libglui32.aÿ. Tu jsem musel vytvořit prostřednictvím importováním projektu z VisualStudia do Code::Blocks a následně zkompilovat. Následovalo nalinkování této nové knihovny a přidání hlavičkových souboru do projektu. Knihovna má dostačující možnosti k vytváření nejčastěji používaných prvků grafických rozhraní. Mezi základní prvky patří: • Tlačítka (Buttons) • Zaškrkávací políčka (Checkboxes) • Radio tlačítka (Radio Buttons) • Editační textová okna (Editable text boxes) • Spinner políčka • Statická textová pole • Panely pro seskupení ovládacích prvků • Oddělovací linky Nejnovější verze obsahují několik dalších ovládacích prvků. Některé z nich nejsou typické a po grafické stránce nabízejí možnost odlišit se od jiných gui knihoven. Těmito prvky jsou např. rotační koule. V programu lze vytvořit libovolný počet grafických oken, a to buď pohyblivá plovoucí, nebo pevně integrovaná do okna aplikace. 9
OpenGL Utility Toolkit — knihovna doplňující OpenGL, např. podpora pro práci s okny
5.3
Grafický formát .OBJ
49
Obr. 25: Oficiální ukázka možností knihovny GLUI
Po aplikování knihovny se objevily některé nedokonalosti v grafickém rozhraní programu. Asi nejvíce omezující je nemožnost vkládání znaků do řádků axiomu a pravidel prostřednictvím schránky (Ctrl+v).
5.3
Grafický formát .OBJ
Program umožňuje exportovat vytvořený model do formátu Wavefront .obj. Tento formát jsem zvolil proto, že má velmi jednoduchou strukturu a patří mezi snadno přenositelné a podporované formáty. Struktura souboru je jednoduchá. Na každém jednotlivém řádku je uvedena buď hodnota souřadnic vektoru, textury, normály nebo plochy. Odlišují se počátečním znakem na řádku. Vektory jsou uvedeny znakem „vÿ, normály „nvÿ, textury „vtÿ a plochy „fÿ. Komentáře lze napsat na řádek uvozený znakem mřížka „#ÿ. Plocha se vytváří stanovením nejméně tří vektorů, a to jejich pořadovým číslem jejich výskytu od začátku souboru. Ke každému vektoru plochy lze přiřadit jeden normálový vektor a texturovou souřadnici. Souřadnice lze zadávat na libovolný počet desetinných míst. Ukázka výpisu souboru ve formátu .obj: \# toto je jednoduchý ukázkový soubor formatu .obj v -51.41 23.07 465.84 v -51.41 23.07 465.84 v -53.53 -23.03 469.52 v -47.16 23.07 465.84 vn 0.00 0.50 0.86 vn -0.00 0.50 -0.86 vn -0.00 0.50 -0.86 vn -0.00 0.50 -0.86
5.3
Grafický formát .OBJ
50
vt -0.86 -0.09 vt -0.81 -0.10 vt 0.12 -0.13 vt 0.79 -0.13 f 1/1/1 2/2/2 3/3/3 f 4/4/4 2/2/2 5/5/5 f 1/1/1 2/2/2 4/4/4 První hodnota plochy určuje vektor, druhá hodnota texturu a poslední normálu. U plochy není povinné určit hodnotu normály nebo textury. \# plocha stanovena pouze vektory f 45 47 43 \# plocha stanovena vektory a texturou f 44/44 47/47 45/45/ \# plocha stanovena vektory a normálami f 41//41 42//42 40//40 V případě užití textury je nutné ji k souboru přidat a vložit na ní odkaz do souboru. Formát také umožňuje definovat použité materiály, a to v souboru .mtl (Material Template Library). Při aplikaci formátu .obj jsem zjistil, že v případě použití ploch složených z více než tří vektorů, programy neužívají definované hodnoty normál. To má za následek nezobrazování ploch v některých editorech.
6
METODIKA TVORBY MODELU STROMU
6
51
Metodika tvorby modelu stromu
Tato kapitola obsahuje navrhnutý postup pro sestavení pravidel gramatiky k vytvoření modelu stromu. Využitím gramatik L-systému lze generovat i jiné druhy rostlin, jako jsou keře nebo traviny. Ty ale nebudou přesně specifikovány, i když není obtížné je vytvořit některými menšími změnami postupu, použitém při tvorbě stromu.
6.1
Tvorba pravidel
Prvním krokem při vytváření modelu stromu je stanovení gramatiky L-systému, tedy axiomu a pravidel. Axiom První pravidlo, které je potřeba vytvořit, je axiom. Axiom může být, co se týče rozsahu, stejně složité jako ostatní pravidla. Axiom v modelu stromu představuje kmen, popřípadě hlavní větev. Generátor L-systému je nastaven tak, aby byl první vykreslený válec kolmý k podkladu. V případě, že chceme vytvořit model stromu, začíná axiom symbolem F (posun želvy dopředu ve směru osy Y s vykreslením válce). V opačném případě nastane větvení u podkladu a bude se jednat spíše o model keře. Následovat musí alespoň jeden symbol z levé strany některého z přepisovacích pravidel. Přepisovací pravidla Hlavním důvodem užití přepisovacích pravidel, namísto jednoho velkého nepřehledného axiomu, je možnost jejich opětovného užití, a to především uvnitř sebe sama. Není tedy nutné vytvořit pravidla pro každou část modelu, ale postačí základní opakující se struktura, která je typická pro větvoví stromů.
Obr. 26: Užití hranatých závorek při vytváření L-systému
Vytvoření nové větve v modelu stromu se v gramatice značí symbolem hranaté závorky. Otevírací závorka značí začátek větve a uzavírací konec, po kterém se želva
6.1
Tvorba pravidel
52
vrací na začátek větvení. Každá větev může obsahovat nekonečné množství dalších větví (samotný program je však omezen velikostí celkového řetězce). Obrázek 26 názorně ukazuje užití hranatých závorek při větvení modelu. V obrázku jsou požity symboly rotace želvy. V prostoru je želva schopna rotovat okolo tří os, X, Y a Z. Znaky plus (+) a mínus (−) značí rotaci okolo osy Z. Rotace okolo osy X je realizována znaky stříška (^) a ampersand (&). Rotování kolem osy Y se nijak neprojevuje při vykreslování válce, jelikož je osově souměrný. Rotace se projeví pouze v kombinaci s dalším úhlem, případně v dalším kroku při aplikaci větvení. Rotace okolo osy Y se realizuje znaky „ je menšíÿ (<) a „ je většíÿ (>). Pro rotaci kolem všech os je dále potřeba stanovit velikosti uhlů rotace. Velikost se zadává ve stupních.
Obr. 27: Rotace želvy v prostoru. Upraveno (Turtle 2, 2012).
Při rozšíření stávajícího příkladu o rotace v 3D prostoru můžeme vytvořit následující model stromu: Počet iterací: 3 A A = F [\&\&B]$>$[\&A] B = F [+B] [--A] Rotace Z = 37 Rotace X = 17 Rotace Y = 92 Dalšími symboly gramatiky jsou „zavináčÿ (@) a „vykřičníkÿ (!). Jejich funkcí je postupné snižování průměru a délky válců. Rozsah hodnot je v intervalu 1 == 0 a aplikaci válce se jejich parametry násobí těmito hodnotami. Např. při hodnotě 1 nedochází k žádné změně, při hodnotě 0,5 se průměr nebo délka sníží v následujícím kroku o polovinu. Nejčastější hodnota při vytváření modelu stromu je v rozmezí 0,89 == 0,7.
6.1
Tvorba pravidel
53
Obr. 28: Příklad větvení v prostoru v programu LS Generator.
Upravená gramatika předchozího příkladu: A B @ !
= = = =
F [\&\&@!B]$>$[\&@!A] F [+@!B] [--@!A] 0.66 0.6
Obr. 29: Příklad stromu se snižující se délkou a šířkou větví.
Při použití symbolů posunů želvy a rotací lze využít parametry, které se zapisují do kulatých závorek bezprostředně za znak gramatiky. Hodnota tehoto parametr se použije při aplikaci pravidla, namísto globálně nastavené hodnoty.
6.2
Aplikace monopodiální struktury větvení
54
Složitější příklady používající všechny možnosti symbolů gramatiky jsou uvedeny v následujících kapitolách monopodiání a sympodiální struktury větvení.
6.2
Aplikace monopodiální struktury větvení
V teoretické části práce jsou uvedeny některé druhy větvení, které se nacházejí v přírodě. Prvním typem je monopodiální větvení. Typický je přímý kmen, který má největší délku a šířku. Z něj vybíhají větve, které mají podobnou strukturu. Příklad gramatiky takového větvení je uveden na obrázku z knihy The Algorithmic Beauty of Plants.
Obr. 30: Příklad gramatiky monopodiální struktury větvení (Prusinkiewicz P., 1990).
Tento příklad si upravím a použiji v programu LS Generator. První úpravou je snížení počtu iterací na 8, které je dostačující. Axiom a pravidla upravím do formátu použitelného v programu. Oproti původnímu příkladu není nutné v definicích pravidel uvádět hodnoty předchozích délek a průměru kroku (l, w). Stačí uvést parametry změny (r1 , r2 , wr ). Přepis části pravidla vypadá následovně: B(l ∗r2 , w ∗wr ) → @(0.7)!(0.707)B. Úhly a0 , a2 , d jsou ekvivalentem rotací Z, X, Y. Hodnota výšky válce a radius 1 a 2 není nutné dodržet. Výsledkem je následující zápis: Iterace: 8 axiom: A
6.3
Aplikace sympodiální struktury větvení
55
pravidlo 1: A=[F[&@(0.7)!(0.77)B]>[@(0.9)!(0.77)A]] pravidlo 2: B=[F[-@(0.7)!(0.77)B]>[@(0.9)!(0.77)A]] pravidlo 3: C=[F[+@(0.7)!(0.77)B]>[@(0.9)!(0.77)A]] rotace Z: 45.0 rotace X: 45.0 rotace Y: 137.5 radius 2: 1.6 radius 1: 1.9 Výska válce: 19.0 Zjednodušení je i v případě začátku každého pravidla – „!(w)ÿ. Toto není potřeba uvádět, jelikož průměr je předán ze zásobníku. Dodatečnou úpravou v editoru je změna hodnoty wr 0.707 na 0.77. Výsledek v programu LS Generator je uveden na obrázku 31.
Obr. 31: Monopodiální struktura větvení v programu LS Generator.
Oproti vzorovému obrázku je zde patrný rozdíl.
6.3
Aplikace sympodiální struktury větvení
Druhou strukturou větvení je sympodiální vzor. Nemá již dominantní kmen, který nedosahuje vrcholu stromu. Příklad takové gramatiky je zobrazen na obrázku 32. Opět přepíši tento příklad po použitelného tvaru podobným způsobem, jako v přecházejícím příkladu. Není již potřeba uvádět úhly pro rotace Z a X, které jsou pevnou součástí pravidel. Výsledkem je následující zápis:
6.3
Aplikace sympodiální struktury větvení
56
Obr. 32: Příklad gramatiky sympodiální struktury větvení (Prusinkiewicz P., 1990).
Iterace: 10 axiom: A pravidlo 1: A=[F[&(10.0)@(0.9)!(0.707)B]>[&(60.0)@(0.7)!(0.707)A]] pravidlo 2: B=[F[+(10.0)@(0.9)!(0.707)B][-(60.0)@(0.7)!(0.707)A]] rotace Y: 180 radius 2: 1.8 radius 1: 2.0 Výska válce: 17.0 Programem vygenerovaný model stromu, při použití této gramatiky, je ukázán na obrázku 33. Na rozdíl od předcházejícího příkladu, sympodiální struktura větvení blíže odpovídá vzorovému obrázku.
6.3
Aplikace sympodiální struktury větvení
Obr. 33: Sympodiální struktura větvení v programu LS Generator.
57
7
IMPLEMENTACE MODELU V DIGITÁLNí KRAJINĚ
7
58
Implementace modelu v digitální krajině
Po vytvoření modelu stromu a jeho uložení ve formátu .obj následuje jeho vložení do digitální krajiny. Mnou vybraný engine, reprezentující digitální krajinu, je IrrLicht, potažmo jeho editor IrrEdit.
7.1
Nástroj IrrEdit
IrrEdit 1.4.2 je editační nástroj pro engin IrrLicht. Konkrétně 3D editor prostředí a generátor lightmapové radiosity. Je zdarma dostupný v několika verzích na webových stránkách (http://www.ambiera.com/irredit/downloads.html), a přiložen na CD k diplomové práci. Jeho hlavní předností je snadná implementace. Není potřeba jej instalovat a konfigurovat. Má intuitivní ovládací rozhraní a umožňuje okamžité spuštění scény v okně editoru.
Obr. 34: Ukázka spuštěného programu IrrEdit 1.4.2.
Popis editoru Editor je rozdělený na několik oken. V horní části se nachází typická nabídková lišta a některé sady tlačítek pro tvorbu a ovládání prvků. Např. sada tlačítek pro tvorbu objektů, jako je krychle koule, terén, světlo, kamera, částicový systém a další. V levé části panel SceneGraphExplorer, který obsahuje seznam všech objektů, které se ve scéně vyskytují. Jeho prostřednictvím se jednotlivé objekty spravují
7.2
Případová studie
59
a lze jím snadno vybírat požadované objekty. Vhodné například při problémech u překrývajících se objektů a neviditelných objektů. Pod ním se v levé části nachází panel Properties. Ten obsahuje informace a parametry zvoleného objektu. Rozdělen na čtyři části – Atributy, Materiály, Animace a Uživatelská data. V dolní části se nachází Message Log, který zobrazuje informace o prováděných úkonech a panel Textures. Zde jsou ikonicky zobrazeny náhledy textur, které lze ve scéně použít. Seznam těchto textur lze snadno rozšířit tlačítkem Add. Nejvýraznější částí editoru jsou okna pohledů na scénu. Hlavní okno zobrazuje perspektivní pohled a dvě menší okna vpravo ortografický horní a ortografický přední pohled. Importování modelu Vložení modelu do editoru se provádí přes nabídku File > Import > Static 3D mesh. Objekt se zobrazí ve scéně v náhodné pozici. V panelu Properties jej lze snadno umístit na vhodnou pozici, upravit rotaci nebo velikostní poměr. Aplikování textury na model stromu se provádí dvojklikem myši v panelu Textures. Pokud má textura rozměř 1:1, neměla by být potřeba žádná dodatečná úprava. Scénu lze uložit do formátu .irr a poté použít v IrrLicht engine, nebo jako .xml. Případně je možné objekty scény exportovat do formátu .dae (collada) a .irrmash. Herní Plagin Program obsahuje nástroj ExampleGamePlagin, umístěný v horní sadě nástrojů. Ten umožňuje simulovat chování herního enginu v okně perspektivy. Obsahuje pouze dvě tlačítka – Play a Stop pro spouštění a ukončení simulace. (pozn. Tlačítko Stop je po spuštění obtížně dosažitelné kurzorem myši, vhodnější je použití klávesy Esc.)
7.2
Případová studie
V poslední části metodiky tvorby uvedu příklad vytvoření modelu stromu a jeho aplikování do digitálního prostředí. U modelu L-systému by nemělo být pochyb, že se jedná o model stromu. V programu LS Generátor jsem vytvořil model stromu s následující gramatikou. Využil jsem všech čtyř pravidel i defaultních hodnot. Před vlastní prací je vhodné si určit, do jakého vzoru větvení bude modelovaný strom patřit. Při vytváření podoby modelu, který by měl být do značné míry chaotický není nutné příliš dbát na stavbu rovnic gramatiky. Nejdůležitější je dodržet, aby byl po rozdělení mateřské větve adekvátně snížen poměr velikostí dceřiných větví. Počet iterací = 7 Axiom: F[&@!A]<(180.0)[-&@(0.5)!B] A = [[&(20.0)@(0.7)!B]<(100.0)[&(45.0)@!(0.6)D]] B = [F[+(10.0)@!C]<(35.0)[-(30.0)@!(0.6)C]] C = [F[&<@!B]<(35.0)[-(20.0)>@!C][<@(0.5)!D]] D = [F[+(10.0)@(0.7)!A]<(45.0)[@!(0.6)B]]
7.2
Případová studie
60
Rotace Z = 25 Rotace X = 30 Rotace Y = 78 ! = 0.707 @ = 0.77 R1 = 2.0 R2 = 1.7 Výška = 42.5 Zvolil sem si sympodiální vzor větvení. Začal jsem axiomem, který vytváří kmen. Pokračoval jsem pravidlem A a B, až v závěru jsem vytvořil pravidlo D. Znaky @ a ! pro zkrácení a zužování válců je vhodné použít až po vytvoření základní struktury. Výsledný model jsem následně exportoval do formátu .obj. Program IrrEdit obsahuje několik připravených příkladů krajin. Použil jsem terrain.irr a přiblížil si pohled do údolí, kde jsou umístěné budovy a stromy. Již obsažené stromy jsem odstranil a importoval jsem svůj model.
Obr. 35: Model stromu vytvořený gramatikou v LS Generatoru.
7.3
Program Blender
61
Model bylo nutné zmenšit pomocí nástroje scale na 0.4 násobku původní velikosti. Modelu jsem přiřadil texturu kůry a několikrát jsem model rozkopíroval.
Obr. 36: Ukázka digitální krajiny v programu IrrEdir s vloženými modely stromů.
7.3
Program Blender
Model stromu jsem importoval také do programu Blender 2.60. Jedná se o open source 3D aplikaci, která je určená pro modelování, animace i vytváření her. Na rozdíl od IrrEdit, se jedná o velmi sofistikovaný nástroj. Je jednoduchý na instalaci bez nutnosti konfigurace. Nevýhodou může být jeho velká složitost. Program LS Generator lez využít pro vytvoření výchozího modelu stromu. Není nutné jej tedy modelovat od začátku. Lze jej využít například k dodatečným úpravám a zkvalitnění modelu stromu, např. úpravou povrchu, přidání lepšího materiálu, či textury. Upravený model je poté možné uložit do některého jiného vhodného formátu. Ukázka modelu stromu v programu Blender je v příloze B.
8
8
DISKUZE
62
Diskuze
Podstatnou částí diplomové práce byla tvorba programu, který generuje L-systémy podobné stromům. Přestože program není stěžejní částí této diplomové práce, ale pouze jedním krokem z metodiky, nabízí nejvíce možností pro další vývoj. Především ve vytvářených modelech stromů. Jednotlivé články (válce) modelu nejsou spojeny, a tak mohou vznikat viditelné mezery mezi nimi. Válce jsou vytvářeny prostřednictvím nadstavbové knihovny GLU jako objekty gluQuadric. To do značné míry ulehčuje práci při jejich vytvoření, ale současně omezuje jejich možnosti. Nejsnazším nabízeným řešením by bylo na konec každého válce přidat geometrický objekt koule, se shodným poloměrem, jaký má válec. Opticky by to problém s mezerami odstranilo. Lepší by ale bylo vytvářet spojité válce, které by musely být vypočítávány pro každý článek modelu zvlášť, a to bez využití již nadefinovaných objektů gluQuadric. Model stromu neobsahuje listy. Možnost generování listoví stromu nebyla uvažována již od samotného návrhu aplikace. Po dokončení programu se to jeví jako velký nedostatek. Listy lze generovat využitím fraktálů, podobně jako stromy, čehož se týká jedna kapitola fraktální geometrie. V rámci programu by bylo dostačující přidání jednoho typu objektu, který by tvarem připomínal list stromu. Jeho výskyt ve struktuře modelu by byl reprezentován znakem gramatiky, stejně jako část větve. Nedostatkem programu LS Generátor je nemožnost generování stochastických L-systémů, které umožňují generovat z jediné gramatiky podobné neidentické modely. Pro realizaci stochastických L-systémů lze využít funkce pro generování náhodných čísel v intervalu 0 až 1. Pravděpodobnost bude odpovídat velikosti intervalu a v závislosti na vygenerovaném náhodném čísle se provede to pravidlo, do jehož intervalu bude číslo patřit. Součet všech hodnot pravděpodobností musí být roven jedné. Příklad stochastické gramatiky je uveden v teoretické části práce. Předností programu je možnost exportovat model do formátu Obj. Díky tomu lze model použít nejen ve vybraném IrrLicht enginu, ale i v mnoha dalších programech, které tento formát podporují. Nevýhodnost tohoto řešení spočívá v náročnosti při rozšiřování modelu o nové typy objektů. Každé přidání nového prvku do scény se musí posléze doprogramovat i pro výstup. Další část práce se věnuje aplikace modelu do digitální krajiny. Zde bylo důležité zvolit program, který by byl uživatelsky nejsnazší na instalaci a ovládání. Byl zvolen IrrEdit, který není nutné instalovat a konfigurovat. Má snadné a intuitivní ovládání a obsahuje plugin, který simulujíce real-time prostředí herního enginu. V případě, že by simulace krajiny v IrrEdit nebyla dostačující, je možné celou scénu uložit do formátu Irr a použít ji v samotném enginu IrrLicht. Jeho instalace by ale byla pro mnoho uživatelů složitá.
9
ZÁVĚR
9
63
Závěr
Fraktály a fraktální geometrie patří k rozvíjející se oblasti matematiky a nabízí se čím dál více možností jejích uplatnění. Za rozvojem stojí především počítačová grafika, která je ve velké míře využívá pro nejrůznější způsoby modelování objektů. Cílem práce bylo vytvoření metodiky, která využije fraktální geometrie k vytvoření modelů rostlin a použije je v digitální krajině. V teoretické části byla uvedena teorie Fraktálů, především Lindenmayerovy systémy. Dále byl také představen pojem grafický 3D engine, který umožňuje vytvářet virtuální digitální krajinu, a také byly uvedeny základní vlastnosti a možnosti těchto nástrojů. V praktické části práce byl na základě výsledků provedené analýzy zvolen vhodný engine reprezentující digitální krajinu. Analýza využila databázi enginů, která je součástí webového serveru DevMaster. Zvoleným programem byl IrrEdit. Za účelem tvorby modelů stromů byl navrhnut a naprogramován nástroj LS Generator. Nástroj byl vytvořen prostřednictvím grafické knihovny OpenGL. Modely jsou generovány aplikací formální gramatiky (L-system) a vektorové grafiky (želví grafiky). Svojí kvalitou jsou tyto modely dostačující pro vizualizaci fraktálů. Pro potřeby užití v digitální krajině nejsou zcela vhodné a je nutné jejich další vylepšení. Pro jejich zdokonalení navrhuji rozšíření programu LS Generátor, případně využití jiných grafických editorů. Nicméně pro hrubou aplikaci v terénu jsou tyto modely dostačující. V závěru práce byl uveden vlastní příklad vymodelovaného složitějšího modelu stromu. Importování do jiného editoru není složité a nemělo by činit problémy. Přestože kvalita vytvořených stromů není vysoká, nástroj generující modely z gramatiky L-systému může být využit jako pomůcka v oblasti fraktálové geometrie.
9.1
Přínosy diplomové práce
1. Program LS Generátor. Umožňuje snadno vytvářet modely stromů a použít je v jiných aplikacích. Kromě generování modelů stromů jej lze využít i pro generování obecných Lsystémů. To by se mohlo využít při výuce Fraktálů, např. v počítačové grafice, popř. v matematice jako nástroj pro vizualizaci L-systémů. 2. Uložení modelu do formátu Obj. Přestože možnosti importování objektů uložených v tomto formátu do OpenGL je relativně dost, s exportem z OpenGL jsem se nesetkal. Jedná se o jednoduchý formát, který je podporován mnoha různými aplikacemi, a proto je velmi rozšířený. 3. Analýza herních enginů. Nabídka enginu je obrovská. Webový server DevMaster jich obsahuje více než tři sta. Jen během doby tvoření této práce vzrostl počet titulů o dvacet šest. Z tak
9.1
Přínosy diplomové práce
64
velkého seznamu není snadné vybrat vhodný nástroj. Analýza nabízí značné zúžení tohoto seznamu. V prvním kroku na třicet volně dostupných enginů, které splňují základní požadavky dnešní doby.
10
10
LITERATURA
65
Literatura
Žára J. a kol.Moderní počítačová grafika 2. vyd. Brno: Computer Press, 2004. 609 s. ISBN 80-251-0454-0. Prusinkiewicz P. a kol.The Algorithmic Beauty of Plants Publisher: Springer, 1990. 228 s. ISBN 978-0387972978. Mandelbrot, Benoˆit B.Fraktály 1. vyd. Praha: Mladá fronta, 2003. 206 s. ISBN 80-204-1009-0. Eberly D. H.3D Game Engine Architexture USA: Morgan Kaufmanm Publishers, 2005. 736 s. ISBN 0-12-229064-X. Shreiner D. a kol.OpenGLPrograming Guide Version 2. USA: Addison-Wesley, 2007. 838 s. ISBN 0-321-33573-2. Ebert David S.Texturing and modeling 3th Edition. USA: Course Technology PTR, 2003. 687 s. ISBN 1-55860-848-6. Jones W.Beginning DirectX 9 USA: Morgan Kaufmanm Publishers, 2004. 352 s. ISBN 1-59200-349-4. Holton, M.Strands, gravity and botanical tree imagery USA: Computer Graphics Forum, 1994. 67 s. DOI 10.1111/1467-8659.1310057. Blythe D.OpenGL.org [online]. 2011. Dokument ve formátu HTML. Elektronická adresa: http://www.opengl.org/resources/code/samples/sig99 /advanced99/notes/node1.html. Tišnovsky P.Fraktály [online]. 1999. Dokument ve formátu HTML. Elektronická adresa: http://www.fit.vutbr.cz/ tisnovpa/fract/clanky/1.htm. Schulz R. Ing.PC-guru.cz [online]. 2011. Dokument ve formátu HTML. Elektronická adresa: http://www.pc-guru.cz/lightmapping-v-opengl. Ogre3d.orgOgre - Deferred Shading [online]. 2011. Dokument ve formátu HTML. Elektronická adresa: http://www.ogre3d.org/tikiwiki/Deferred+Shading. MicrosoftVolume Texture Resources [online]. 2011. Dokument ve formátu HTML. Elektronická adresa: http://msdn.microsoft.com/enus/library/windows/desktop/bb206344(28v=vs.85)29.aspx. Šulc T.Unifikované shadery - co to vlastně je [online]. 2008. Dokument ve formátu HTML. Elektronická adresa: http://pcworld.cz/hardware/technologieunifikovane-shadery-co-to-vlastne-je-3865. Angeulov B.The Geometry Shader [online]. 2011. Dokument ve formátu HTML. Elektronická adresa: http://takinginitiative.net/2011/01/12/directx10tutorial-9-the-geometry-shader/.
10
LITERATURA
66
Unity3DTree Creator Structure [online]. 2011. Dokument ve formátu HTML. Elektronická adresa: http://unity3d.com/support/documentation/Components/ tree-Structure.html. Carsten Fuchs SoftwareCafu engine [online]. 2012. Dokument ve formátu HTML. Elektronická adresa: http://www.cafu.de/. Nikolaus Gebhardt a spol.IrrLicht engine [online]. 2012. Dokument ve formátu HTML. Elektronická adresa: http://irrlicht.sourceforge.net/. ´ ´ skiEsenthel engine [online]. 2012. Dokument ve formátu HTML. Grzegorz Slazi n Elektronická adresa: http://www.esenthel.com/. WorldweaverDxStudio [online]. 2012. Dokument ve formátu HTML. Elektronická adresa: http://www.dxstudio.com/. CtytekCryEngine 3 [online]. 2012. Dokument ve formátu HTML. Elektronická adresa: http://www.crytek.com/cryengine/cryengine3/overview. Petr PaušPočítačové generování fraktálních množin [online]. 2012. Dokument ve formátu HTML. Elektronická adresa: http://kmlinux.fjfi.cvut.cz / pauspetr/html/skola/fraktaly/reserse.htm. Turtle 2 [online]. 2012. Dokument ve formátu HTML. Elektronická adresa: http://www.charlesstone.com/5-animals-pastors-sometimes-act-like/turtle-2/.
Přílohy
A
A
TABULKA ENGINŮ
Tabulka enginů
Obr. 37: Tabulka enginů
68
B
B
PROGRAM BLENDER
Program Blender
Obr. 38: Ukázka modelu stromu v programu Blender 2.60.
69