Obsah
1. Dynamické systémy generované v hyperkomplexním prostoru
1.1 Použití kvaternionové algebry
1.2 Použití hyperkomplexní algebry
2. Systémy iterovaných funkcí (IFS)
2.1 IFS systémy vytvořené algoritmem náhodné procházky
2.2 Linearizované IFS systémy
2.3 Trojrozměrné systémy iterovaných funkcí
3. Fractal Flames
4. Obsah dalšího pokračování tohoto seriálu
1. Dynamické systémy generované v hyperkomplexním prostoru
Velmi zajímavou, i když doposud málo známou skupinou fraktálních útvarů jsou fraktály vytvářené ve čtyřrozměrném prostoru (4D fraktály, 4D-F). V předchozí části tohoto seriálu jsme si zopakovali, že významnou skupinou fraktálů kreslených v ploše jsou mapy dynamických systémů ležících v komplexní rovině, mezi něž patří i známá Mandelbrotova množina, Juliovy množiny, fraktály typu Magnet, Barnsley, Lambda, Phoenix atd. Zdaleka nejpoužívanějším způsobem vizualizace těchto dynamických systémů je barevné zvýraznění počtu iterací, tj. celkového počtu opakování iterační funkce dynamického systému do té doby, než je splněna nějaká předem známá podmínka (například překročení bailout u Mandelbrotovy množiny a množin Juliových). Tyto množiny je poměrně snadné převést do 3D prostoru; typicky převodem na výšková pole (height field). To však není vše – tyto fraktální útvary je možné zobecnit i do prostoru čtyřrozměrného.
Jedním ze způsobů přechodu od těchto původně plošných fraktálů k fraktálům trojrozměrným (popř. čtyřrozměrným) je náhrada komplexních čísel a komplexních iterovaných funkcí čísly a funkcemi hyperkomplexními. Příklad fraktálu (konkrétně Juliovy množiny) vytvořeného ve čtyřrozměrném prostoru s provedenou projekcí do trojrozměrného prostoru je ukázán na následujícím obrázku. Jedná se o model vytvořený v programu Quat, který je dostupný jak pro unixové systémy (s plnohodnotným grafickým uživatelským rozhraním i jako program ovládaný z příkazové řádky), tak i pro operační systémy MS-DOS a Microsoft Windows (DOSová verze grafické uživatelské rozhraní neobsahuje). Na první pohled vypadá přidaný (tj. čtvrtý) rozměr nadbytečný – ve skutečnosti však díky němu získáváme možnost provádění jednoduché animace celého fraktálu popř. i další parametry ovlivňující jeho tvar.
Úloha zobrazení 4D fraktálů je však poněkud komplikována zejména kvůli existenci „přebývajícího“ čtvrtého rozměru a dále také kvůli tomu, že většinou chceme vhodným způsobem zviditelnit povrch těchto objektů metodami založenými na existenci normálových vektorů. Mezi tyto metody patří i raycasting (zpětné sledování paprsku) a raytracing (rekurzivní zpětné sledování paprsku). Povrch čtyřrozměrných fraktálů je však obecně nediferencovatelný, tj. nelze u něj analyticky vyjádřit parciální derivace v bodech na povrchu, proto je nutné použít numerické techniky, které však nejsou ani přesné ani rychlé. V praxi se používají tři možné způsoby vykreslování čtyřrozměrných fraktálních obrazců: výčíslení plošných řezů původně čtyřrozměrným objektem (s jejich zobrazením například formou textur), metoda integrace podél paprsku, raycasting a raytracing a konečně převod objemového modelu na polygonální síť.
Tento typ fraktálních objektů byl popsán v části 62 až 68, spolu s popisem známého raytraceru POV-Ray a GNU aplikace Quat, které je možné použít pro generování zajímavých statických obrázků i animací původně čtyřrozměrných těles s fraktální strukturou.
1.1 Použití kvaternionové algebry
Kvaterniony (quaternions) a kvaternionovou algebru vymyslel v roce 1843 známý matematik William Rowan Hamilton, který původně hledal rozšíření komplexních čísel z 2D plochy do 3D prostoru. Takové rozšíření však není možné vytvořit, nejbližší ekvivalent komplexních čísel jsou až čtyřrozměrné struktury. Hamilton provedl revoluční krok v tom, že jím vymyšlené kvaterniony nesplňovaly vlastnost do té doby považovanou za naprostou samozřejmost – komutativitu. Později se objevily i další užitečné struktury, které komutativitu nesplňují, například matice. Kvaterniony jsou obdobou komplexních čísel, ovšem s tím rozdílem, že mají čtyři na sebe kolmé jednotky, které označujeme symboly 1, i, j a k. Jednotka 1 se někdy nazývá skalární složkou, zbylé tři jednotky i, j, k pak složkami vektorovými (to souvisí s využitím kvaternionů při popisu rotací). Každý kvaternion lze popsat lineární kombinací všech čtyř jednotek: q=x+yi+zj+wk.
1.2 Použití hyperkomplexní algebry
Hyperkomplexní čísla jsou v mnohém podobné kvaternionům. Není divu, protože je taktéž vynalezl William Rowan Hamilton. Opět se jedná o čísla, jež můžeme vyjádřit jako lineární kombinaci čtyř jednotek 1, i, j a k. Pro hyperkomplexní algebru platí, že je sice splněn komutativní zákon, tj. ab=ba, ale pro všechny prvky nemusí (ale v některých případech může) existovat inverzní prvek. Výsledkem aplikace hyperkomplexní algebry při výpočtu čtyřrozměrného fraktálu je objekt obsahující „čtvercové“ části, narozdíl od „kruhových“ či „elipsovitých“ částí v případě fraktálů vypočtených za pomoci algebry kvaternionové. Tento rozdíl je způsobem odlišnými multiplikativními operacemi v obou algebrách (v kvaternionové algebře odpovídá násobení dvou čísel jejich rotaci).
2. Systémy iterovaných funkcí (IFS)
Systémy iterovaných funkcí (IFS), které je možné použít pro vytváření procedurálních modelů těles s fraktální charakteristikou, zejména soběpodobností a invariancí ke změně měřítka, tvoří velmi významnou skupinu fraktálů, jejíž varianta je použita i ve fraktální komprimaci obrazu. 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 už v roce 1985 Demko a následně pak v roce 1987 Michael Barnsley (knihy Fractals Everywhere, Science of Fractal Images, Fractal Image Compression). Tvorba obrázků pomocí IFS systémů patří mezi generativní metody vytváření fraktálů, kterou řadíme mezi metody deterministické (stejně jako minule popsané metody pro vytváření fraktálních objektů v komplexní rovině). Algoritmus pro generování IFS fraktálů však může být jak deterministický, tak nedeterministický (tj. stochastický – viz algoritmus náhodné procházky – RWA).
2.1 IFS systémy vytvořené algoritmem náhodné procházky
Princip generování IFS fraktálu je v nejjednodušším případě založený na takzvaném algoritmu náhodné procházky, který iterativně provádí následující výpočet: na bod Piter, který se nachází v rovině R2 nebo v prostoru R3, jsou buď deterministicky nebo náhodně (oním algoritmem náhodné procházky) aplikovány jednotlivé transformace φn. Výsledkem je nová pozice bodu Piter+1. IFS fraktál je poté zobrazen jako koláž složená ze všech vygenerovaných bodů Pi, i=(1..maxiter). Před vlastním generováním je zapotřebí určit počáteční pozici startovního bodu P0. Všechny transformace v IFS systému jsou zároveň i transformacemi změny měřítka s koeficientem menším než 1 – jde tedy o kontrahující transformace zajišťující směřování systému ke svému atraktoru (ve skutečnosti je toto příliš silná podmínka, mnohdy postačí použít pouze průměrné kontrahující transformace).
Proto je možné pozici startovního bodu P0 zvolit libovolně, protože po několika počátečních iteracích se díky kontrahujícím transformacím posloupnost generovaných bodů Pi samovolně dostane do atraktoru IFS. Většinou se volí P0=[0, 0] v rovině R2 resp. P0=[0, 0, 0] v prostoru R3. Transformace, které se budou v daném iteračním kroku aplikovat na bod Pi lze vybírat buď deterministicky nebo náhodně. V případě náhodného vybírání transformací (s uvažováním pravděpodobností jednotlivých transformací) potom mluvíme o algoritmu náhodné procházky. Tento algoritmus je s IFS neodmyslitelně spjatý a – i když jsou v něm použita náhodná čísla – vede k vytváření pravidelných, nestochastických (deterministických) fraktálů. Tento algoritmus je popsaný v třicáté až třicáté třetí části seriálu.
2.2 Linearizované IFS systémy
Linearizované systémy iterovaných funkcí (Linearized Iterated Functions Systems: L-IFS), pomocí nichž je možné vytvářet a především iteraktivně měnit tvar a strukturu velmi pěkně vypadajících plošných i prostorových obrazců, se vyznačují fraktální strukturou, tj. jsou soběpodobné a obsahují nekonečně mnoho detailů v různých měřítkách zobrazení. Jedná se o upravené klasické systémy iterovaných funkcí IFS; úprava spočívá v omezení typů transformací, zavedení řídicích bodů a rozšíření IFS systémů o takzvanou matici posloupnosti transformací, která slouží k další modifikaci výsledného plošného či prostorového obrázku. Oproti aplikacím, které využívají klasické systémy iterovaných funkcí je možné s pomocí linearizovaných systémů iterovaných funkcí vytvářet obrazce interaktivně a s okamžitou zpětnou odezvou uživateli.
Z praktického hlediska spočívá zásadní odlišnost L-IFS systémů oproti IFS systémům ve skutečnosti, že uživatel nemusí při tvorbě obrazce zadávat žádné číselné hodnoty jednotlivých transformací ani jejich pravděpodobností. Místo toho může interaktivně měnit polohu řídicích bodů v ploše či prostoru. S tímto způsobem editace objektů je uživatel většinou dobře obeznámen, protože se v počítačové grafice velmi často používá, například pro vytváření parametrických křivek a ploch. Jak uvidíme v dalším textu, existují i další souvislosti mezi parametrickými křivkami a fraktálními obrazci generovanými pomocí systémů L-IFS. Jedná se například o existenci konvexní obálky tvořené řídicími body. Tento typ fraktálů jsme si popsali v třicáté páté a třicáté šesté části tohoto seriálu.
2.3 Trojrozměrné systémy iterovaných funkcí
Trojrozměrné systémy iterovaných funkcí vznikly rozšířením transformačních matic použitých u dvourozměrných IFS o další dimenzi. Tím se místo postupné aplikace transformací na 2D bod provádí aplikace transformací na bod ležící v trojrozměrném prostoru. Jiné změny vlastně samotný algoritmus generování jednotlivých bodů nepostihly, zcela odlišný je však způsob vykreslení těchto systémů. Při vizualizaci systémů iterovaných funkcí jsou postupně, tj. po aplikaci jednotlivých lineárních či nelineárních transformací, generovány body Pn. U 2D IFS jsme tyto body, jež ležely v rovině E2, považovali za souřadnice v rastrovém obrázku a na jejich zaokrouhlenou pozici jsme pomocí předem definovaného postupu změnili barvu pixelu (například v závislosti na počtu „zásahů“ daného pixelu, vybrané lineární transformaci apod.).
Prakticky nic nám nebrání v rozšíření již prezentovaných algoritmů tak, aby se místo bodů v rovině E2 vytvářely body ležící v trojrozměrném prostoru E3. Rozšíření spočívá v tom, že se transformační matice příslušející každé transformaci zvětší – místo matice o velikosti 3×3 prvky musí být použita matice 4×4 prvky, ovšem s tím, že poslední sloupec transformační matice má vždy hodnotu [0, 0, 0, 1]T a tím pádem nemusí být explicitně ukládán v operační paměti počítače. Samotné vykreslování vypočtených bodů může být založeno například na vytvoření malého čtverce s nanesenou bitmapou či na vykreslení bodu ve 3D prostoru se zadanou velikostí. Alternativně je také možné použít blending, tj. míchání barev bodů, které po projekci leží na stejném místě obrazovky.
3. Fractal Flames
Fraktální typ (resp. přesněji řečeno algoritmus) „Fractal Flames“ vytvořil před poměrně nedávnou dobou Scott Draves. Tento typ fraktálů vznikl několikerou generalizací klasických systémů iterovaných funkcí (IFS). Je to vlastně opak postupu, který jsme použili při vytváření linearizovaných systémů iterovaných funkcí L-IFS, v tomto případě jsme však byli vedeni snahou o interaktivní vytváření fraktálních obrazců. Vraťme se však k popisu základních vlastností algoritmu „Fractal Flame“. Zajímavé – a pro počítačovou grafiku bezesporu přínosné – přitom je, že algoritmus tvorby „Fractal Flame“ byl vytvořen přímo s ohledem na estetickou kvalitu vytvářených obrázků, bez ohledu na matematickou korektnost, jako je tomu u původních IFS systémů. Tomu odpovídá výběr nelineárních funkcí (zde nazývaných podle pravidel svého výběru variace), logaritmická závislost světlosti pixelu na počtu jeho „zásahů“ při vytváření obrazce, použití symetrie při vykreslování obrazce atd.
Nejvýraznější rozdíl mezi klasickými systémy iterovaných funkcí a Fractal Flames tkví v tom, že se místo původních lineárních resp. afinních transformací používají lineární transformace kombinované s nějakou složitější nelineární funkcí, zde nazvanou variace. Díky nelineárním funkcím se mohou v obrázku objevovat i velmi složité části ve tvaru spirál, oblouků, vln apod. Další rozdíl spočívá v použití symetrie, pomocí které je možné z původního nezajímavého obrázku vytvořit obrázek mnohem zajímavější. Symetrie může být dvou typů: rotační (okolo středu obrázku) nebo zrcadlová (okolo jedné ze souřadných os probíhajících středem obrázku, obecně kolem jakékoli přímky procházející středem obrázku). Symetrii je možné vytvořit buď při specifikaci lineárních funkcí nebo až při vykreslování jednotlivých pixelů na základě vypočtených souřadnic bodu Xn+1.
Posledním rozdílem mezi systémy iterovaných funkcí a Fractal Flames je rozšířený způsob obarvování jednotlivých pixelů. Lineární závislost mezi barvou pixelu a počtem „zásahů“ tohoto pixelu je změněna na závislost logaritmickou, což způsobuje zvýraznění zajímavých části ve vytvářeném obrazci. Také je možné jednotlivé části obrazce obarvovat v závislosti na použité transformaci – ve skutečnosti je totiž původně dvojrozměrný prostor obrázku rozšířen o třetí rozměr, kterým je index do barevné palety či přímo barvový odstín. Tímto typem fraktálů, které jsou dokonce podporovány jedním zásuvným modulem známého grafického programu GIMP (GFlare), jsme se podrobněji zabývali v části třicáté osmé a třicáté deváté.
4. Obsah dalšího pokračování tohoto seriálu
V následujícím pokračování tohoto seriálu dokončíme „škatulkování“ fraktálů. Popíšeme si stochastické fraktály (zejména fraktály vzniklé simulací difůze a plasmy), dále dvourozměrné i trojrozměrné L-systémy a Markus-Ljapunovovy fraktály. Nakonec si připomeneme význam šumové Perlinovy funkce.
