Obsah
1. Úvodní informace o fraktálech nazývaných „Fractal Flame“
2. Rozdíl mezi „Fractal Flame“ a klasickými systémy iterovaných funkcí
3. Rozšíření afinních transformací – variace
4. Funkce použité při výpočtu variací
5. Logaritmická závislost při vykreslování plošného histogramu
6. Způsoby obarvení jednotlivých pixelů při vykreslování Fractal Flames
7. Symetrie a její vliv na generovaný obrazec
8. Literatura a odkazy na Internetu
9. Obsah dalšího pokračování tohoto seriálu
1. Úvodní informace o fraktálech nazývaných „Fractal Flame“
Fraktální typ (resp. přesněji řečeno algoritmus) „Fractal Flame“ vytvořil před poměrně nedávnou dobou Scott Draves (viz literatura uvedená v osmé kapitole). Tento typ fraktálů vznikl, jak již bylo ostatně uvedeno v perexu tohoto článku, 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 variace), logaritmická závislost světlosti pixelu na počtu jeho „zásahu“ při vytváření obrazce, použití symetrie při vykreslování obrazce atd. Největší rozdíly mezi fraktály typu „Fractal Flame“ a systémy IFS jsou popsány ve druhé kapitole, v kapitolách navazujících se již budeme zabývat jednotlivými rozdíly a způsobem vytváření obrazců fraktálů „Fractal Flame“.
Obrázek 1: Obrázek vytvořený pomocí algoritmu „Fractal Flame“
2. Rozdíl mezi „Fractal Flame“ a klasickými systémy iterovaných funkcí
Mezi klasickými systémy iterovaných funkcí (IFS) a fraktály typu „Fractal Flame“ existuje poměrně velké množství rozdílů, které spočívají v rozšíření schopností původních IFS o další funkcionalitu. Základ generování je však kupodivu shodný: v obou případech je použit algoritmus náhodné procházky (RWA – Random Walk Algorithm), pomocí kterého se vybírají a následně aplikují transformace na bod Xn ležící v rovině. Nově vygenerovaný bod Xn+1 je použit při obarvení pixelu ve vytvářeném rastrovém obrázku.
Nejvýraznější rozdíl mezi IFS a Fractal Flame 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 – viz třetí a čtvrtá kapitola. 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). 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ě souřadnic bodu Xn+1.
Posledním rozdílem mezi IFS a Fractal Flame 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.
Obrázek 2: Další obrázek vytvořený pomocí algoritmu „Fractal Flame“
3. Rozšíření afinních transformací – variace
Již v předchozí kapitole jsme si řekli, že nejvýraznějším rozdílem mezi klasickými systémy iterovaných funkcí IFS a fraktály typu Fractal Flame je kombinace lineárních a nelineárních funkcí pro každou transformaci. Zatímco v systémech iterovaných funkcí určených pro dvojrozměrnou rovinu je možné každou transformaci popsat šesticí reálných koeficientů (ai, bi, ci, di, ei, fi) tvořících transformační matici A, je u fraktálů typu Fractal Flame k těmto šesticím koeficientů přidána ještě nějaká nelineární funkce nazývaná variace (poslední tři koeficienty transformační matice A není zapotřebí udávat, protože ty jsou vždy rovny vektoru [0, 0, 1]). Scott Draves navrhl několik vhodných nelineárních funkcí, které jsou uvedeny v následující kapitole. Výpočet nové pozice bodu s využitím lineární transformace a nelineární funkce se řídí následujícím vztahem:
(xn+1, yn+1)=Vj(aixn+biyn+ci, dixn+eiyn+fi)
zatímco klasické systémy iterovaných funkcí jsou založeny na jednodušším vztahu:
(xn+1, yn+1)=(aixn+biyn+ci, dixn+eiyn+fi)
tj. je použita pouze lineární transformace bez aplikace nelineárních funkcí.
Obrázek 3: Nelineární funkce umožňují vytvářet obrazce se zajímavými tvary
4. Funkce použité při výpočtu variací
Scott Draves pro svoje demonstrační příklady ukazující možnosti algoritmu Fractal Flame navrhl a otestoval několik nelineárních funkcí, pomocí nichž je možné tvořit zajímavé obrazce. Tyto nelineární funkce (které se, jak již víme, nazývají variace) jsou označeny symbolem Vn(x,y), kde n je index od 0 do 20. Ve skutečnosti však bylo z možných 21 kombinací vybráno 16 variací. Seznam všech variací V0(x,y) až V20(x,y) je uveden v následující tabulce.
Všimněte si, že hned první variace označená symbolem V0(x,y) je vlastně identitou, tj. funkcí, která je implicitně použita u všech klasických systémů IFS (a samozřejmě také linearizovaných systémů iterovaných funkcí L-IFS). Dále stojí za povšimnutí použití různých typů goniometrických funkcí a současně i absence funkcí logaritmických, se kterými jsou (vzhledem k omezenému definičnímu oboru) při praktické implementaci problémy a k tomu ještě nepřináší do obrázku žádné zajímavé tvary.
| Označení funkce | Výrazy pro výpočet souřadnic | Originální název |
|---|---|---|
| V0(x,y) | (x,y) | linear |
| V1(x,y) | (sin x, sin y) | sinusoidal |
| V2(x,y) | (x/r2, y/r2) | spherical |
| V3(x,y) | (r×cos(φ+r), r×sin(φ+r)) | swirl |
| V4(x,y) | (r×cos(2φ), r×sin(2φ)) | horseshoe |
| V5(x,y) | (φ/π, r-1) | polar |
| V6(x,y) | (r×sin(φ+r), r×cos(φ-r)) | handkerchief |
| V7(x,y) | (r×sin(φr), -r×cos(φr)) | heart |
| V8(x,y) | (φ×sin(πr)/π, φcos(πr)/π) | disc |
| V9(x,y) | ((cos φ+sin r)/r, (sin φ-cos r)/r) | spiral |
| V10(x,y) | ((sin φ)/r, (cos φ)r) | hyperbolic |
| V11(x,y) | ((sin φ)(cos r), (cos φ)(sin r)) | diamond |
| V12(x,y) | (r×sin3(φ+r), r×cos3(φ-r)) | ex |
| V13(x,y) | (r1/2×cos(φ/2+Ω), r1/2×sin(φ/2+Ω)) | julia |
| V14(x,y) | ||
| V15(x,y) | ||
| V16(x,y) | (2r/(r+1)x, 2r/(r+1)y) | fisheye |
| V17(x,y) | ||
| V18(x,y) | ||
| V19(x,y) | ||
| V20(x,y) | (cos(πx)×cosh(y), -sin(πx)×sinh(y)) | cosine |
Ve výše uvedené tabulce mají symboly r a φ následující význam:
r=(x2+y2)1/2
φ=arctan(y/x)
Ω=0 nebo π (na základě náhodného čísla)
Obrázek 4: Kombinace několika nelineárních funkcí v jednom systému IFS
5. Logaritmická závislost při vykreslování plošného histogramu
Další změnou oproti původním systémům iterovaných funkcí je použití logaritmické závislosti při vykreslování plošného histogramu. V předchozích částech tohoto seriálu jsme si řekli, že při vykreslování IFS systémů je možné buď přímo nastavit barvu jednotlivých pixelů odpovídajících pozicím bodů Xn, nebo je možné použít plošný histogram, tj. postupně zvyšovat intenzitu barvy jednotlivých pixelů v závislosti na jejich zásazích body Xn. Scott Draves ideu plošného histogramu dále rozšířil tak, že se při zobrazování histogramu nepoužívá lineární závislost mezi počtem zásahů pixelu a jeho barvovou intenzitou, ale závislost logaritmická. To s sebou přináší dvě výhody. První předností je, že se zvýrazní i poměrně tmavé části fraktálu, tj. pixely, které mají nízký počet „zásahů“. Druhá přednost spočívá v tom, že se obrázek zdánlivě stává trojrozměrným.
Je to způsobeno jednoduchým efektem: pokud se v obrázku překrývají dva výrazné motivy, z nichž jeden k sobě body Xn přitahuje více, je při použití logaritmické závislosti oblast překryvu zdánlivě tmavším motivem nedotčena. Vysvětlení tohoto efektu je snadné. Předpokládejme, že motiv s vyšší „přitažlivostí“ (tj. motiv vzniklý transformací s vyšším kontrakčním faktorem) je tvořen pixely s počtem zásahů rovným 1000 a motiv s menší přitažlivostí pixely s počtem zásahů rovným 100. V oblasti překryvu obou motivů vznikají pixely s počtem zásahů rovným 1100, ovšem rozdíl mezi log(1000) a log(1100) je velmi malý a pro uživatele takřka neviditelný. To je ostatně jeden z důvodů, proč se někteří uživatelé domnívají, že obrázky vytvořené algoritmem „Fractal Flames“ jsou trojrozměrné, i když z předchozích kapitol víme, že se jedná o obrázky plošné, resp. o obrázky vzniklé aplikací 2D transformací.
Výpočet logaritmické závislosti je poměrně jednoduchý, postačuje vytvořit framebuffer pro vykreslovanou pixmapu z pixelů, jejichž hodnoty nejsou celočíselné, ale např. typu float. Po vykreslení celého obrázku se zjistí maximální hodnota uložená v některém z pixelů, tj. maximální počet „zásahů“ jednoho pixelu. Následně jsou hodnoty všech pixelů s nenulovým počtem zásahů ve framebufferu zlogaritmovány, vyděleny logaritmem maximální hodnoty, čímž se hodnoty pixelů dostanou do rozsahu 0,0 až 1,0; a následně převedeny na celočíselné hodnoty v požadovaném rozsahu (tj. většinou vynásobeny hodnotou 255.0). Výsledkem je obrázek využívající plný barvový rozsah, o čemž se můžeme přesvědčit spočtením a zobrazením klasického 1D histogramu.
Obrázek 5: Vliv logaritmické závislosti světlosti pixelů na zdánlivý 3D obraz
6. Způsoby obarvení jednotlivých pixelů při vykreslování Fractal Flames
Také způsob obarvení jednotlivých pixelů při vykreslování se v algoritmu Fractal Flames oproti původním IFS systémům rozšířil. U klasických IFS systémů se barva pixelů volila buď konstantní (s případným použitím plošného histogramu), nebo se pixel obarvil podle toho, která transformace byla pro jeho vygenerování použita. Algoritmus Fractal Flames přináší významné rozšíření, které spočívá v tom, že se transformace neprovádí pouze v 2D rovině, ale v 3D prostoru, přičemž třetí souřadnicí je právě barva pixelu – a to buď jeho intenzita nebo index do barvové palety. Index je však v tomto případě reálné číslo v rozsahu 0,0–1,0, protože mezi jednotlivými položkami v barvové paletě je možné provádět lineární interpolaci. Výpočet barev pixelů se tedy provádí až v průběhu iteračního cyklu.
Počáteční intenzita barvy či index do barvové palety c je zvolen náhodně v rozsahu od 0,0 do 1,0. Posléze se v každém iteračním kroku získá na základě zvolené funkce (transformace) hodnota ci a provede se výpočet intenzity barvy/indexu podle následujícího vztahu:
c=(c+ci)/2
Tento výpočet má zajímavou vlastnost: nejvíce používané funkce, tj. funkce s nejvyšší váhou také nejvíce ovlivňují výslednou barvu pixelů. Součet barvy odpovídající zvolené funkci s barvou předchozí dodává celému iteračnímu procesu jakousi paměť předchozích stavů, takže výsledkem není obraz složený z různobarevných teček, ale naopak tvary s postupnými barvovými přechody.
Obrázek 6: Další příklad zdánlivě trojrozměrného modelu získaný použitím logaritmické závislosti světlosti pixelů
7. Symetrie a její vliv na generovaný obrazec
Vhodným výběrem funkcí použitých při specifikaci fraktálu je možné vytvářet symetrické obrazce. V případě „Fractal Flames“ jsou rozlišovány dvě symetrie: rotační a zrcadlová. Symetrii lze zaručit dvěma způsoby. Buď se po výpočtu souřadnic pixelů v každém iteračním kroku nevykreslí pixel jeden, ale hned několik pixelů rotačně či zrcadlově symetrických, nebo se symetrie zaručí již výběrem funkcí při vytváření IFS systému pro algoritmus Fractal Flame. Druhý způsob je preferovaný, protože nevede ke zcela symetrickému obrázku, který by byl poněkud umělý, ale k obrázku, kde je sice symetrie jasně patrná, ale není zcela dokonalá.
Výběr funkcí pro dosažení symetrie je poměrně snadný. Zrcadlová symetrie spočívá ve funkci, která změní znaménko x-ové či y-ové souřadnice, jedná se tedy o transformaci změny měřítka. Středová symetrie je založena na funkci, která provede rotaci bodu okolo počátku souřadné soustavy. Jediný problém spočívá ve výpočtu pravděpodobností aplikace těchto funkcí. Ta by měla být nastavena na hodnotu rovnou součtu pravděpodobností všech ostatních funkcí, a to i v případě vícenásobných symetrií (trojná atd). Vzhledem k tomu, že pravděpodobnost transformace pro symetrii je rovna součtu pravděpodobností všech ostatních transformací, bude transformace symetrie zvolena s padesátiprocentní pravděpodobností, tj. průměrně každý druhý (či n-tý) pixel bude transformován.
8. Literatura a odkazy na Internetu
- Scott Draves: <i>The Fractal Flame Algorithm</i>,
http://flam3.com/flame_draves.pdf, May 18, 2005 - Barnsley Michael: <i>Fractals Everywhere</i>,
Academic Press, San Diego, 1988. - Barnsley Michael, Devaney R. L., Mandelbrot Benoit B., Peitgenn Heinz-Otto, Saupe Dietmar, Voss Richard: <i>The Science of Fractal Images</i>,
Springer-Verlag, New York, 1988. - Hutchinson, J.: <i>Fractals and Self-Similarity</i>,
Indiana University Journal of Mathemtics, 30, 713–747, 1981. - Gröller Eduard: <i>Interactive design of Nonlinear Functions for Iterated Function System</i>,
Technical University Vienna, 1995. - Jack Tumblin, Holly Rushmeier: <i>Tone Reproduction for Realistic Images</i>,
IEEE Computer Graphics and Applications, November/December 1993 (Vol. 13, No. 6) pp. 42–48. - B. W. Silverman: <i>Density Estimation for Statistics and Data Analysis</i>,
Chapman and Hall, London, 1986. - Chardonnet David: ''IFS Fractals Digital Encyclopedy '',
http://www.chez.com/fractals/galeries/gb_index.html (3.6.2006) - Bowman Richard L.: ''IFS Fractal Generation Exercise '',
http://www.bridgewater.edu/departments/physics/ISAW/FractalGenEx.html (3.6.2006) - Devaney Bob: ''Dynamical systems and Iterated Function Systems '',
http://math.bu.edu/people/bob/ (3.6.2006) - Stránky o algoritmu Fractal Flame:
http://flam3.com/ (16.7.2006) - Stránka programu Apophysis:
http://www.apophysis.org/ (16.7.2006)
9. Obsah dalšího pokračování tohoto seriálu
V následujícím pokračování tohoto seriálu dokončíme poměrně rozsáhlou část věnovanou systémům iterovaných funkcí (IFS) a jejich modifikacím. Okomentujeme demonstrační příklad určený pro vykreslování fraktálů typu Fractal Flame a ukážeme si, jakým způsobem je možné vytvářet trojrozměrné modely těles pomocí systémů iterovaných funkcí IFS a linearizovaných systémů iterovaných funkcí L-IFS.
