Hlavní navigace

Fractal Flames

Pavel Tišnovský 18. 7. 2006

Dnes se budeme věnovat popisu velmi zajímavé skupiny fraktálů. Jedná se o fraktální typ nazvaný Scottem Dravesem "Fractal Flames". Tato skupina fraktálů úzce souvisí s dříve popisovanými systémy iterovaných funkcí (IFS) - ve skutečnosti se jedná o několikerou generalizaci těchto systémů.

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“.

fractals38_1

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.

fractals38_2

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+byn+ci, dixn+eiyn+fi)

zatímco klasické systémy iterovaných funkcí jsou založeny na jednodušším vztahu:

(xn+1, yn+1)=(aixn+byn+ci, dixn+eiyn+fi)

tj. je použita pouze lineární transformace bez aplikace nelineárních funkcí.

fractals38_3

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)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)

fractals38_4

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.

fractals38_5

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.

fractals38_6

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.

Animace vytvořená pomocí postupných změn v parametrů IFS systému vykreslovaného pomocí algoritmu Fractal Flame

8. Literatura a odkazy na Internetu

  1. Scott Draves: <i>The Fractal Flame Algorithm</i>,
    http://flam3.com/fla­me_draves.pdf, May 18, 2005
  2. Barnsley Michael: <i>Fractals Everywhere</i>,
    Academic Press, San Diego, 1988.
  3. 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.
  4. Hutchinson, J.: <i>Fractals and Self-Similarity</i>,
    Indiana University Journal of Mathemtics, 30, 713–747, 1981.
  5. Gröller Eduard: <i>Interactive design of Nonlinear Functions for Iterated Function System</i>,
    Technical University Vienna, 1995.
  6. 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.
  7. B. W. Silverman: <i>Density Estimation for Statistics and Data Analysis</i>,
    Chapman and Hall, London, 1986.
  8. Chardonnet David: ''IFS Fractals Digital Encyclopedy '',
    http://www.chez­.com/fractals/ga­leries/gb_index­.html   (3.6.2006)
  9. Bowman Richard L.: ''IFS Fractal Generation Exercise '',
    http://www.brid­gewater.edu/de­partments/phy­sics/ISAW/Frac­talGenEx.html   (3.6.2006)
  10. Devaney Bob: ''Dynamical systems and Iterated Function Systems '',
    http://math.bu­.edu/people/bob/   (3.6.2006)
  11. Stránky o algoritmu Fractal Flame:
    http://flam3.com/   (16.7.2006)
  12. Stránka programu Apophysis:
    http://www.apop­hysis.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.

Našli jste v článku chybu?

1. 5. 2007 18:21

Pavel (neregistrovaný)
Ono byste tak jak to dělá fractal flames měl počítat všechny fraktály. Pokud totiž počítáte závislost lineárně, tak bod se sto zásahy dostane barvu dejme tomu 100 a bod s dvěmi sty zásahy dostane hodnotu 200. Jenže bod s hodnotou 100 má daleko nižší světelnost než 50% oproti bodu s hodnotou 200, takže výsledek není matematicky korektní.

18. 7. 2006 16:33

Za to RedSys nemuze, udelal jsem to sam pri vkladani obrazku do DB. U vsech, tj. i u tech prvnich dvou s rozlisenim 256x256 pixelu, jsem nastavil tvorbu nahledu, coz je v tomto pripade blbost (za coz se omlouvam). U ostatnich obrazku nahledy funguji, i kdyz u tretiho to nemusi byt tak patrne, protoze je zmensen na pouhych 80% sve velikosti.
Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

120na80.cz: Stoná vaše dítě často? Upravte mu jídelníček

Stoná vaše dítě často? Upravte mu jídelníček

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

120na80.cz: 5 přírodních tipů na bolest v krku

5 přírodních tipů na bolest v krku

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube