Fraktály v počítačové grafice IV

Obsah

1. Dělení fraktálních objektů do kategorií
2. Dynamické systémy s fraktální strukturou
3. L-systémy
4. Systémy iterovaných funkcí IFS
5. Stochastické fraktály (nepravidelné fraktály)
6. Využití fraktální geometrie v jiných vědních disciplínách a v praxi
7. Fraktály v počítačové grafice
8. Obsah dalšího pokračování tohoto seriálu

1. Dělení fraktálních objektů do kategorií

Již v předchozím pokračování seriálu jsme si uvedli, že se jak matematicky definované fraktály, tak i fraktální objekty nacházející se v okolní přírodě dělí do několika kategorií, přičemž fraktály stejné kategorie mají shodné své nejvýznamnější charakteristiky. Z pohledu počítačové grafiky je důležité, že fraktální objekty spadající do stejné kategorie se vytvářejí podobnými algoritmy (jejich tvar se samozřejmě liší). Podle nejhrubšího dělení (které si budeme v dalších částech seriálu zjemňovat) rozlišujeme následující typy fraktálů:

1. Dynamické systémy s fraktální strukturou
2. L-systémy
3. Systémy iterovaných funkcí IFS
4. Stochastické fraktály (nepravidelné fraktály)

V následujících kapitolách budou jednotlivé kategorie fraktálů charakterizovány podrobněji.

2. Dynamické systémy s fraktální strukturou

Dynamické systémy tvoří tu skupinu (resp. kategorii) fraktálů, která má v technické praxi nejširší uplatnění. Dynamický systém je matematický model, jehož stav je závislý na nějaké nezávislé veličině, většinou to bývá na čase – odtud je také odvozován název těchto systémů. Dynamický systém vychází z počátečních podmínek a je jimi v čase determinován. Jak již víme z předchozího pokračování tohoto seriálu, existují dynamické systémy (a není jich málo), které se po určitém čase neustálí v pevném stavu, ale ani nedivergují. Tento případ, který v určitých ohledech připomíná iracionální čísla, má většinou fraktální dynamiku a označuje se (pro někoho nesmyslným) termínem deterministický chaos.

Dynamický systém je popsán pomocí dynamických podmínek, které popisují změnu tohoto systému v čase. Stav systému v libovolném časovém okamžiku je potom reprezentován vektorem, který leží ve stavovém prostoru dynamického systému – jedná se o takzvaný stavový vektor (viz předchozí část tohoto seriálu). Dynamické podmínky jsou většinou zadány soustavou diferenciálních rovnic, které popisují změnu stavového vektoru v čase. Změna stavu dynamického systému se děje provedením těchto diferenciálních rovnic a nahrazením starého stavového vektoru novým.

Typickým příkladem dynamického systému s fraktální dynamikou je výpočet populačního růstu, který má tu zajímavou vlastnost, že volbou jediného parametru lze určit, zda bude systém ustálený, oscilující, nebo chaotický. Při zkoumání dynamiky populačního růstu byly také objeveny některé konstanty, které mají obecnou platnost, podobně jako například konstanta π nebo základ přirozených logaritmů e. Dynamické systémy s fraktální strukturou existují i v komplexní rovině. Z těchto systémů jsou v počítačové grafice asi nejvíce známé Juliovy množiny a Mandelbrotova množina. Existuje i rozšíření Juliových množin a Mandelbrotovy množiny do hyperkomplexního (čtyřrozměrného) prostoru.

Obrázek 1: Dynamický systém: Juliova množina v hyperkomplexním prostoru

Znalost toho, zda nějaký systém je ustálený, či zda směřuje k chaosu, je velmi důležitá pro výpočty nad tímto systémem. Pro chaotický systém (nebo fraktálně dynamický systém) nelze předpovědět stav systému ve vzdálené budoucnosti, aniž by se musel simulovat celý vývoj systému. Taktéž platí, že dynamické systémy jsou obecně velmi závislé na počátečních podmínkách, takže i nepatrná změna počátečních podmínek má za následek odlišné chování systému v budoucnosti.

Z hlediska počítačové grafiky je však nejzajímavější vhodným způsobem vizualizovat nějakou vlastnost dynamického systému – v případě systémů v komplexní rovině se může jednat například o počet iterací apod. Pokud konečnou část komplexní roviny rozdělíme pravidelnou mřížkou, získáme rastrový obrázek dynamického systému. Tento rastrový obrázek lze použít například jako texturu nanesenou na prostorový objekt. Mezi výhody použití fraktálů pro generování textur patří úspora paměti (při uložení scény do externí paměti lze uložit pouze parametry fraktálu a ne celou bitmapu textury) a možnost dynamické změny rozlišení textury podle velikosti a vzdálenosti vykreslovaného objektu. Záporem jsou samozřejmě zvýšené požadavky na CPU, výpočet textury s vysokým rozlišením může být zdlouhavý.

Obrázek 2: Hvězdná obloha – netradiční pohled na Mandelbrotovu množinu

3. L-systémy

L-systémy, jež jsou v některé literatuře také označovány termínem Lindenmayerovy systémy, jsou skupinou fraktálů definovaných pomocí přepisovacích gramatik. Uvádí se, že název pochází z anglické zkratky LOGO-like turtle (ještěže LOGO i Lindenmayer začínají stejným znakem :-). LOGO je přitom známý programovací jazyk určený pro výuku programování, jež je založený na Lispu. V tomto jazyku se pomocí jednoduchých příkazů ovládajících virtuální želvu pohybující se po ploše dají kreslit různé obrazce složené povětšinou z úseček.

Podstatou tvorby L-systémů je přepisování řetězců podle určitých pravidel (gramatik). Každému terminálnímu symbolu – znaku, jež se nepřepisuje – v řetězci je přiřazen jistý geometrický význam, který odpovídá příkazu pro želvu v jazyce LOGO. Mezi tyto terminální symboly (tj. základní příkazy ovládající želvu) patří například znaky:

Pomocí posledních dvou příkazů (push a pop) lze generovat obrazce, ve kterých probíhá rozvětvení struktury, například u rostliny či stromu. Zajímavé obrazce s fraktální strukturou se začnou tvořit, jestliže v jazyce LOGO použijeme rekurzi, což odpovídá iteraci v gramatice (na pravé straně přepisovacího pravidla gramatiky je nonterminální symbol shodný se symbolem na levé straně pravidla). Jednou z možností, jak klasické L-systémy rozšířit, je použití více želv a zavedení nových symbolů pro souběžné nebo samostatné řízení těchto želv. Za pomoci L-systémů lze generovat fraktály, které se podobají rostlinám, stromům a dalším přírodním útvarům. Složitější aplikace směřují k využití těchto fraktálů ke generování plošných i prostorových (tj. objemových) textur.

Obrázek 3: L-systém: Hilbertova křivka tvořená nepřerušovanou­ linií

4. Systémy iterovaných funkcí IFS

Název IFS systémů je odvozen z původního anglického označení Iterated Function System, česky lze tento název přeložit jako systém iterovaných funkcí. První publikace, které se týkaly IFS systémů, vydali v roce 1985 Demko a následně pak v roce 1987 Barnsley. Tvorba obrázků pomocí IFS systémů patří mezi generativní metody vytváření fraktálů, kterou řadíme mezi metody deterministické. Algoritmus pro generování IFS fraktálů však může být jak deterministický, tak nedeterministický (tj. stochastický – viz v dalších dílech prezentovaný algoritmus RWA). Práce se systémy IFS představuje jednu z často používaných aplikací procedurálního modelování těles. Ve velkém množství případů se však jedná o pouhý podpůrný nástroj bez další návaznosti na celé trojrozměrné scény.

V systémech iterovaných funkcí IFS se pro tvorbu fraktálních obrazců používá takzvaná generativní metoda. Tato metoda je vhodná jak pro generování fraktálů, tak i pro kompresi bitmapových obrazů, zavedeme-li ke generativní metodě takzvanou inverzní úlohu. Zajímavé je, že metoda generování fraktálů pomocí IFS systémů může být jak plně deterministická, tak i stochastická (tj. při výpočtech se využívají náhodné prvky). Oboje však paradoxně vede ke stejnému výslednému fraktálu, ovšem použijeme-li dostatečný počet iterací.

Obrázek 4: Větev vytvořená pomocí IFS systému

5. Stochastické fraktály (nepravidelné fraktály)

Poměrně velkou skupinu fraktálů tvoří fraktály nepravidelné. Zatímco všechny předchozí skupiny (resp. typy) fraktálů byly v určitém smyslu symetrické, nepravidelné fraktály vnášejí při generování fraktálu do algoritmu náhodu. Tento typ fraktálů také umožňuje nejlepší popis přírodních objektů. Zatímco při generování stromu klasickým L-systémem nebo IFS koláží dostaneme jako výsledek perfektně symetrický strom, je skutečnost už na první pohled zcela jiná. Strom rostoucí v přírodě má nepravidelné délky a tloušťky větví, úhel růstu větví také není vždy stejný, strom rostoucí v lese má jiný tvar než tentýž druh stromu rostoucí osamoceně apod. Proto je velmi vhodné zavést do generování fraktálů náhodu. Způsob, jakým se náhodnost bude podílet při generování fraktálů, bude vždy určovat tvar fraktálu a mimo další charakteristiky i jeho Hausdorffovu dimenzi. Pro generování náhodných čísel se používá například Gaussovský generátor nebo generátor bílého šumu.

Náhodné fraktály můžeme vytvářet více způsoby. První způsob spočívá v simulaci Brownova pohybu buď v ploše, nebo v prostoru. Druhý způsob spočívá v použití metody přesouvání středního bodu a třetí způsob využívá spektrální syntézu. Simulace Brownova pohybu vytváří fraktální objekt, jehož Hausdorffova dimenze je úměrná absolutní velikosti změny při jednom kroku iterace. Tato metoda se používá například při generování toků řek, není však příliš vhodná pro trojrozměrné objekty. Také vytváření obrazů difúze je založeno na Brownově pohybu.

Mezi typické metody generování stochastických fraktálů patří metoda přesouvání prostředního bodu, a to jak na ploše, tak i v prostoru. Tato metoda se velmi často používá v počítačové grafice k vygenerování takzvaného výškového pole (height field) a následné vizualizaci přírodní krajiny. Volbou maximální odchylky při posunu prostředního bodu potom lze měnit celkový ráz krajiny od pouště až po velehory s rozeklanými vrcholky.

Další často používanou metodou je spektrální syntéza, která vychází z principu výpočtu Fourierovy řady. Metoda spočívá v tom, že náhodně vygenerujeme Fourierovy obrazy, které mají spektrální hustotu úměrnou zadané Hausdorffově dimenzi. Potom provedeme inverzní Fourierovu transformaci s těmito koeficienty (převod z frekvenční oblasti do oblasti časové). Výsledkem je fraktální objekt. Pomocí této metody lze generovat hory či povrchy planet. Výhodou je, že lze přímo zadat požadovanou Hausdorffovu dimenzi výsledného objektu.

Obrázek 5: Stochastický fraktál nazývaný ‚plasma‘

6. Využití fraktální geometrie v jiných vědních disciplínách a v praxi

V předchozí části tohoto seriálu jsme si řekli, že objekty s fraktální strukturou je možné objevit v živé i neživé přírodě. Dnes si popíšeme některé praktické aplikace fraktální geometrie ve fyzice a chemii.

Velmi zajímavou fyzikální oblastí, ve které byly objeveny fraktály, je zkoumání změny stavu některých materiálů. Podrobně byla studována například změna stavu magnetického materiálu na materiál nemagnetický. Materiál je uspořádán z elementárních magnetů, které v závislosti na teplotě určují, zda je materiál magnetický či nikoliv. Při nízkých teplotách je materiál jako celek magnetický, ale při mikroskopickém pohledu existují jisté lokální fluktuace, kde nejsou elementární magnety uspořádané. Naopak, za dostatečně vysoké teploty je materiál jako celek nemagnetický, ale existují domény, kde jsou elementární magnety uspořádány. Vlastnost magnetismu je tedy závislá na „měřítku pohledu“ na materiál. Při kritické teplotě (takzvaná Curieova teplota) materiál přechází z magnetického stavu do nemagnetického a naopak. Jestliže je materiál zahřán přesně na tuto teplotu, vypadá stejně ve všech měřítkách a má fraktální strukturu. Při této teplotě také nemůžeme jednoznačně dokázat, zda je materiál magnetický či nikoli.

Tato fraktální struktura existuje například i při změně skupenství látky, jako je tání ledu či vypařování vody. Základní stavy hmoty jsou z makroskopického hlediska tři (pevné, kapalné, plynné), můžeme však přidat i plazmu a další (například degenerovaná hmota). Z mikroskopického hlediska je ovšem těchto stavů mnohem více a přechody mezi těmito stavy nejsou skokové. Fraktální strukturu hmoty potom můžeme vidět při přechodu hmoty z jednoho stavu do druhého stavu.

Také Brownův pohyb má fraktální strukturu. Brownův pohyb vzniká chaotickým pohybem částeček v hmotě, který je způsoben nenulovou teplotou tělesa. Brownův pohyb lze sledovat například při míchání dvou kapalin či plynů, ale lze ho i poměrně věrně simulovat na počítači s využitím fraktální geometrie. Tímto fenoménem se budeme zabývat v dalších pokračováních seriálu.

Poslední dobou se fraktální geometrie využívá i v biologii a medicíně. Například při zkoumání vlastností krve se měří Hausdorffova dimenze jejích částeček. Někteří odborníci také zkoumají, zda má nějakou souvislost Hausdorffova dimenze povrchu mozku a inteligence člověka či jeho paměťové schopnosti (povrch mozku je tvořen mozkovými závity, které svým počtem a členitostí určují různé schopnosti mozku, například paměť či inteligenci).

Obrázek 6: Jedna z variací původní Kochovy křivky

7. Fraktály v počítačové grafice

Pravděpodobně největší uplatnění má fraktální geometrie a fraktály v počítačové grafice. Počítačová grafika dává vědcům aparát, pomocí kterého mohou fraktály detailně zkoumat, a naopak počítačová grafika hojně využívá poznatků vyplývajících ze zkoumání fraktálů. S rozvojem grafických schopností počítačů se stále více ukazovalo, že je zapotřebí objevit nové postupy, jak modelovat přírodní objekty. V principu jsou možné tři různé způsoby zadávání dat pro modely.

Prvním způsobem je modelování objektů animátorem. Pro tento způsob se dlouhou dobu vytvářely modelovací programy typu CAD a CAM. V případě modelování technických a geometrických předmětů je tento způsob ideální. Problém nastává v případě, že chceme modelovat nějaký složitější přírodní objekt, například hory nebo stromy. Množství vytvářených dat je obrovské a vynaložená práce většinou neodpovídá kvalitě a věrohodnosti výsledku.

Druhým způsobem je přímé snímání (skenování) daného objektu. Tato metoda má své uplatnění, ale není výhodná ve všech případech. Prostorové (trojrozměrné) skenery jsou drahá zařízení, která mají omezenou rozlišovací schopnost. Také jsou schopny skenovat pouze objekty určité velikosti a struktury. Například skenování hory či stromu je nemožné. Také objekty, které mají velkou členitost, je obtížné skenovat (hlava člověka s vlasy). Množství výstupních dat, která vycházejí po naskenování, je obrovské, protože je objekt reprezentován malými trojúhelníčky. Proto se tato metoda používá jen pro určitý okruh problémů a je vyhrazena jen CAD pracovištím, která mají možnost si toto drahé zařízení pořídit.

Třetí způsob spočívá ve využití takzvaného procedurálního modelování. Animátor nezadává přímo tvar objektu, ale způsob, jakým bude objekt generován. Tato metoda má tu přednost, že objem zadávaných dat je většinou malý a výsledný objekt lze modifikovat změnou počátečních podmínek (tak lze vytvářet zajímavé animace, jako je například růst stromů). Nevýhodou je nutnost výběru správné metody pro generování určité množiny objektů a také nutnost pochopit, co který parametr znamená a jak se projeví na výsledném tvaru objektu. Při vytváření objektu (zadávání parametrů) není přímo vidět výsledek, pracuje se tedy metodou pokus-omyl.

Při procedurálním modelování se mimo jiné používají i fraktály. Fraktály lze v počítačové grafice využít například ke generování přírodních útvarů, jako jsou stromy, rostliny, hory, mraky, kameny atd. V této oblasti neexistuje lepší způsob, který by dával věrohodnější výsledky.

Dále se fraktály hojně využijí při generování textur. Obrovskou výhodou fraktálů je jejich paměťová nenáročnost. Data pro texturu, která má být generovaná fraktálem, mají velikost několika bytů nebo desítek bytů, oproti běžné bitmapě s velikostí řádově stovky kilobytů. Také je možno texturu zobrazit v různých velikostech, aniž by bylo vidět nějaké zkreslení, které běžně nastává u bitmapových textur. Tato paměťová nenáročnost je využita při fraktální kompresi, o které se zmíníme v dalších pokračováních seriálu.

Fraktály lze také využít při animaci. Rozšíříme-li generování fraktálu o jeden rozměr, lze tento nadbytečný rozměr považovat za čas, a tímto způsobem fraktál animovat. Tato metoda je použita při zobrazování ohně nebo pohybujících se mraků. Lze ji také kombinovat se systémem částic (particles), což umožňuje animaci mnoha jevů, které nelze běžnými metodami ani zobrazit, ani odsimulovat.

Obrázek 7: Dračí křivka – další typ L-systému

Obrázek 8: Juliova množina

8. Obsah dalšího pokračování tohoto seriálu

V dalším pokračování tohoto seriálu se budeme věnovat praktickým ukázkám dynamických systémů s fraktální strukturou.