Fraktály ve škatulkách

Obsah

1. Dynamické systémy vykreslované v 2D ploše i 3D prostoru
   1.1 Bifurkační diagram
   1.2 Orbity dynamických systémů v rovině
   1.3 Orbity dynamických systémů v prostoru
2. Mapy dynamických systémů vykreslované v komplexní rovině
   2.1 Mandel­brotova množina a Juliovy množiny
   2.2 Newtonova fraktální množina
   2.3 Fraktální množiny Michaela Barnsleye
   2.4 Fraktály typu Magnet
   2.5 Fraktály typu Phoenix
3. Obsah dalšího pokračování tohoto seriálu

1. Dynamické systémy vykreslované v 2D ploše i 3D prostoru

První obrázky obsahující objekty s fraktální charakteristikou, které jsme si v tomto seriálu ukazovali, byly založené na dynamických systémech, konkrétně na nelineárních dynamických systémech se zpětnou vazbou, pomocí níž se budoucí stav dynamického systému odvozoval od stavu současného. Vizualizace chování dynamického systému v čase se může provádět různými způsoby, my jsme se v praktických příkladech zaměřili především na zobrazení množiny stavů dynamického systému v závislosti na jednom parametru v dvourozměrném grafu (jedná se o bifurkační diagram použitý například u logistické funkce) a také na zobrazení takzvaných orbitů (orbits) dynamického systému, a to jak v ploše, tak i v prostoru (samozřejmě v závislosti na tom, kolik složek obsahuje stavový vektor daného systému, většinou se jedná o dvě či tři složky, které ztotožňujeme s jednotlivými souřadnicemi).

Obrázek 1: Bifurkační diagram logistické funkce pro kladné hodnoty G_r (bez použití filtrace)

1.1 Bifurkační diagram

Pro jasnější představu o chování jednorozměrného dynamického systému se používá vizuální nástroj nazvaný bifurkační diagram. V bifurkačním diagramu jsou na horizontální osu naneseny hodnoty některého vstupního parametru (v případě logistické funkce, tj. velmi jednoduché funkce s chaotickým chováním, se jedná o míru růstu G_r) a na vertikální osu vnitřní stavy dynamického systému, což je u logistické funkce hodnota x_n, jichž systém nabývá pro daný počet kroků (iterací). Hodnota x_n je vykreslena triviálním způsobem pomocí jednoho bodu (pixelu), nedochází tedy k tvorbě spojitého grafu. V některých případech se bifurkační diagram dále upravuje, například tak, že se vykreslují hodnoty až po předem zadaném počtu iterací, kdy je systém již částečně ustálen (jedná se o takzvané „počáteční“ nebo „startovní“ iterace). Podrobnější údaje o logistické funkci a bifurkačním diagramu najdete v páté části tohoto seriálu.

Obrázek 2: Bifurkační diagram logistické funkce pro záporné hodnoty G_r (bez použití filtrace)

Obrázek 3: Bifurkační diagram funkce x_n+1=G_r(x-sin x²)

Obrázek 4: Bifurkační diagram funkce x_n+1=G_r(x-cos x)

1.2 Orbity dynamických systémů v rovině

Pro vybranou skupinu dynamických systémů s podivnými atraktory (strange attractors) je pro účely počítačové grafiky vhodné zobrazovat jejich orbity, což není ve své podstatě nic jiného, než obraz stavového vektoru systému (resp. hodnot složek tohoto vektoru) v dvojdimenzi­onálním nebo třídimenzionálním prostoru. Při vykreslování dvojdimenzionálního orbitu (tj. orbitu zobrazeného v rovině) je použit velmi jednoduchý postup založený na sekvenčním výpočtu a následném vykreslení orbitu, který si můžeme představit jako bod ležící v rovině. V nejjednodušším případě se každá hodnota orbitu zobrazí pomocí jednoho vysvíceného pixelu, je však možné použít i sofistikovanější techniky používající antialiasingu, výpočtu plošného histogramu, nahrazení jedné složky stavového vektoru barvou apod.

Obrázek 5: Orbity dynamického systému nazvaného Hopalong

Obrázek 6: Orbity dynamického systému nazvaného Chip

Mezi nejznámější a v zahraniční literatuře také nejčastěji citované dynamické systémy vykreslované v rovině patří Lorenzův atraktor, Hénonův atraktor, dynamické systémy zveřejněné A. K. Dewdneym (nazvané Martin a Hopalong), Michaelem Petersem (s názvy Chip a Quadruptwo) a plošné varianty původně trojrozměrných dynamických systémů (Latoocarfian, Pickover a Kamtorus). Zvláštní variantou dvoudimenzionálního dynamického systému je systém nazvaný Popcorn, u něhož se v jedné bitmapě zobrazují orbity pro různé počáteční podmínky. Výsledkem je objekt zdánlivě nakreslený štětcem – viz osmý ilustrační obrázek. Tyto dynamické systémy jsou podrobněji popsané v šesté, sedmé a osmé části seriálu o fraktálech, spolu s několika demonstračními příklady.

Obrázek 7: Orbity dynamického systému nazvaného Quadruptwo

Obrázek 8: Orbity dynamického systému nazvaného Popcorn

1.3 Orbity dynamických systémů v prostoru

Orbity některých dynamických systémů je možné zobrazit i v trojrozměrném prostoru. My jsme si v sedmém pokračování tohoto seriálu popsali tři takové systémy, které se jmenují Kamtorus 3D, Pickover a Latoocarfian. Mezi trojrozměrné dynamické systémy patří i známý Lorenzův atraktor, jehož prostorová varianta byla uvedena v osmé části tohoto seriálu. Při vykreslování orbitu dynamického systému v prostoru (s projekcí do plochy) je možné na vypočtenou pozici v ploše [x, y] uložit buď barvu odpovídající provedené iteraci, nebo na této pozici zvýšit intenzitu barvy, tj. světlost pixelu (plošný histogram). Při použití druhé metody, která vlastně zajistí zobrazení hustoty vypočtených bodů, vypadají výsledné orbity lépe, ovšem pouze za předpokladu, že se provede mnohem větší počet opakování iterační smyčky – řádově se jedná o stovky tisíc iterací pro rastrový obrázek o velikosti 512×384 pixelů.

Obrázek 9: Orbity dynamického systému Pickover po projekci do plochy

Obrázek 10: Orbity dynamického systému Latoocarfian po projekci do plochy

Obrázek 11: Alternativní forma projekce trojrozměrného dynamického systému do plochy (plošný histogram+obar­vení bodů)

Obrázek 12: Lorenzův atraktor

2. Mapy dynamických systémů vykreslované v komplexní rovině

Pravděpodobně největší množství obrázků s tematikou fraktálů bylo vytvořeno vizualizací dynamických systémů v komplexní rovině. Namísto drah orbitů jsou v tomto případě zobrazovány takzvané mapy dynamických systémů. Mapou je zde myšlen rastrový obrázek (bitmapa, pixmapa), ve kterém barva každého pixelu odpovídá vybranému stavu dynamického systému v bodě, jehož souřadnice jsou do pixelu mapovány – pixmapa je tedy „položena“ do komplexní roviny tak, že každému pixelu z pixmapy můžeme jednoznačně přiřadit jedinou komplexní hodnotu, tj. reálnou a imaginární složku (transformace bodů z komplexní roviny do bitmapy je většinou lineární).

Zdaleka nejpoužívanějším způsobem vizualizace dynamických systémů v komplexní rovině je zvýraznění počtu iterací, tj. počtu opakování funkce dynamického systému do té doby, než je splněna nějaká předem známá podmínka. Mezi takto vykreslované dynamické systémy patří Mandelbrotova množina, Juliovy množiny, Newtonova fraktální množina, fraktální množiny Michaela Barnsleye atd.

Obrázek 13: Detail Mandelbrotovy množiny

2.1 Mandelbrotova množina a Juliovy množiny

Mandelbrotova množina je – spolu se slavnou Newellovou čajovou konvicí – považována za jeden ze symbolů počítačové grafiky. Jak Mandelbrotova množina, tak i množiny Juliovy jsou založeny na dynamickém systému, ve kterém se iterativně počítá funkce komplexní paraboly. Juliovy množiny jsou pojmenovány po francouzském matematikovi, který se jmenoval Gaston Julia. Tento matematik se začal v roce 1917 zabývat problematikou analýzy chování funkce komplexní paraboly při opakované iteraci, tj. při zavedení zpětné vazby do výpočtu (výpočty totiž pro některé hodnoty vykazovaly chaotické chování, které si nikdo bez možnosti vizualizace nedokázal vysvětlit). Posléze na této problematice pracovali jak Gaston Julia, tak i další francouzský matematik Pierre Fatou, podstatná část jejich společné vědecké práce je datována do roku 1920.

Obrázek 14: Juliova množina (Cantorův resp. Fatouův prach)

Na tyto práce, které byly většinou vědců prakticky zapomenuty (převažoval totiž mylný názor, že do matematiky nic podstatného nepřináší), navázal v osmdesátých letech minulého století Benoit B. Mandelbrot, který problematiku analýzy komplexní paraboly spojil s fraktální geometrií (po Mandelbrotovi se tímto fenoménem zabýval zejména A. Douday a J. Hubbard) a především zkoumáním jevů za pomoci počítačové grafiky, protože tímto způsobem je možné najít i některé skryté souvislosti mezi různými počátečními podmínkami.

Po Gastonu Juliovi jsou pojmenovány Juliovy množiny, po Pierre Fatouovi jejich speciální podtyp, takzvaný Fatouův prach (Fatou dust). To však platí zejména pro evropskou literaturu, v americké se tento podtyp Juliových množin nazývá zobecněný Cantorův prach (Cantor dust). Mandelbrotovy a Juliovy množiny jsou (spolu s jejich různými variantami) popsány v desátém až dvacátém prvním dílu tohoto seriálu. Použitá iterační funkce komplexní paraboly má tvar:

z_i+1=z_i²+c

Popř. v obecném tvaru (pro různé mocniny – zde již samozřejmě nemusí jít pouze o parabolu):

z_i+1=z_i^w+c

Kde w může být celé číslo, reálná konstanta či dokonce konstanta komplexní.

Obrázek 15: Juliova množina s jinými parametry a odlišnou barvovou paletou

Obrázek 16: Kubická Mandelbrotova a Juliova množina

Obrázek 17: Mandelbrotova a Juliova množina s neceločíselnou mocninou

2.2 Newtonova fraktální množina

Jednou z nejpoužívanějších a současně i nejznámějších numerických metod určených pro vyhledávání reálných i komplexních kořenů polynomů je Newtonova iterační metoda, která se stala populární zejména díky tomu, že se numerické řešení poměrně rychle přibližuje ke kořenu. V mnoha případech je pro dosažení požadované přesnosti řešení nutné provést pouze několik iterací, přičemž v každé iteraci se výsledek zpřesňuje o jedno až dvě desetinná místa. Newtonova iterační metoda, kterou je možné jednoduše vysvětlit i geometricky (ve své podstatě vypočítává průsečík tečny v nějakém bodě grafu funkce s horizontální osou), spočívá v opakovaném výpočtu rovnice, kdy je výsledek x_i+1 použit pro výpočet v následující iteraci:

x_i+1=x_i-f(x_i)/f'(x_i)

Kořeny polynomu mohou být v některých případech reálné, tj. budou ležet pouze na reálné ose. Reálné kořeny má například polynom x²-1=0. U velké části polynomů však leží některé nebo dokonce všechny kořeny v komplexní rovině. Typickým příkladem může být polynom x²+1=0, který sice nemá v oboru reálných čísel žádný kořen (rovnici tudíž nelze v oboru reálných čísel řešit, protože neexistuje takové x, pro které by byla rovnost zachována), ale v komplexní rovině je samozřejmě možné kořeny nalézt, zejména když si uvědomíme platnost známého vztahu i²=-1, kde i je imaginární jednotka. Newtonovu iterační metodu je možné použít i v oboru komplexních čísel, příslušný iterační vztah se přitom změní pouze nepatrně (z_i a z_i+1 leží v komplexní rovině):

z_i+1=z_i-f(z_i)/f'(z_i)

Mohlo by se zdát, že všechny výše uvedené vlastnosti Newtonovy iterační metody zůstanou zachovány i pro komplexní kořeny, například vlastnost nalezení nejbližšího kořenu k zadané hodnotě z₀. Ve skutečnosti to však není zdaleka pravda, protože takový výpočet je pro některé počáteční podmínky nestabilní a vede až k chaotickému chování (pro některé počáteční hodnoty z₀ tedy řešení neexistuje). Na hranici mezi řádem a chaosem potom můžeme objevit fraktální struktury tvořené oblastmi patřícími do různých atraktorů – Newtonovu fraktální množinu. Tuto množinu, kterou je možné vykreslit několika způsoby, jsme si popsali v části 22 a 23.

Obrázek 18: Zobrazení atraktorů Newtonovy fraktální množiny

Obrázek 19: Zvýraznění počtu iterací v Newtonově fraktální množině

Obrázek 20: Kombinace zvýraznění atraktorů i počtu iterací u Newtonovy fraktální množiny

2.3 Fraktální množiny Michaela Barnsleye

Tyto fraktály popsal Michael Barnsley (který se stal světoznámým zejména po vynalezení IFS a podání patentu na fraktální komprimaci obrazů) ve své známé knize Fractals Everywhere. Konkrétně se jedná o tři modifikace Mandelbrotových množin a k nim příslušející trojici Juliových množin. Modifikace spočívá v náhradě původního iteračního vztahu z_n+1=z_n²+c vztahem složitějším, ve kterém se navíc vyskytuje podmínka. Tím se původní zaoblený („organický“) tvar Mandelbrotovy varianty množiny i varianty Juliovy změní takřka k nepoznání, výsledné obrazce spíše připomínají krystalické a jiné anorganické struktury. K označení všech šesti fraktálů jsem zvolil jména použitá mj. i v programu FractInt. Modifikované Mandelbrotovy množiny se nazývají M1, M2 a M3, k nim příslušející Juliovy množiny mají název J1, J2 a J3. Barnsleyovy fraktální množiny jsou podrobněji popsány v části 24 a 25.

Iterační vztah pro množinu M1 a J1 má tvar funkce s podmínkou:

    if (real(z) >= 0)
        z(n+1)=(z-1)*c
    else
        z(n+1)=(z+1)*c

Obrázek 21: Barnsleyova fraktální množina J1

Obrázek 22: Barnsleyova fraktální množina J1 s odlišnou konstantou C

Pro množiny M2 a J2 je tvar iterované funkce poněkud odlišný, protože je použita složitější podmínka, v níž se rozhoduje, která větev výpočtu se použije:

    if (real(z)*imag(c) + real(c)*imag(z) >= 0)
        z(n+1) = (z-1)*c
    else
        z(n+1) = (z+1)*c

Obrázek 23: Detail Barnsleyova fraktálu M2

Nejsložitější je funkce použitá u množin M3 a J3, která má následující tvar:

    if (real(z(n) > 0)
        z(n+1) = (real(z(n))^2 - imag(z(n))^2 - 1)
               + i * (2*real(z((n)) * imag(z((n)))
    else
        z(n+1) = (real(z(n))^2 - imag(z(n))^2 - 1 + real(c) * real(z(n))
               + i * (2*real(z((n)) * imag(z((n)) + imag(c) * real(z(n))

Obrázek 24: Barnsleyův fraktál M3

Obrázek 25: Detail Barnsleyova fraktálu M3

Obrázek 26: Barnsleyova fraktální množina J3

2.4 Fraktály typu Magnet a Phoenix

Posledním typem popsaných fraktálních množin vytvořených v komplexní rovině, jsou množiny nazvané Magnet a Phoenix. Fraktály typu Magnet byly podrobněji popsány v části 26 a 27, fraktální množina Phoenix spolu se svojí Juliovou variantou pak v části 28.

Fraktální množina Magnet 1 je v komplexní množině počítána a následně vykreslována způsobem, který jsme si podrobně popsali u klasické Mandelbrotovy množiny a množin Juliových. Každému bodu (tj. pixelu) zobrazenému na obrazovce je jednoznačně přiřazena určitá komplexní hodnota. Tato hodnota je považována za vstupní parametr iterační smyčky, která slouží k provedení testu, zda komplexní hodnota příslušná k danému pixelu vede ke konvergenci k fixním bodům množiny, nebo zda naopak posloupnost hodnot z_n diverguje (resp. se posloupnost stala periodickou, což se obecně nedá v konečném čase zjistit).

Iterační vztah pro fraktální množinu Magnet 1 je mnohem složitější, než tomu bylo u dříve popisovaných množin, tj. množin Mandelbrotových a Juliových nebo i Barnsleyových množin (tam se sice vyskytovala podmínka, ale poměrně jednoduchá), protože je použito dělení komplexních čísel. Celý iterační vztah je možné zapsat následujícím způsobem:

z_n+1=((z_n²+c-1)×(2z_n+c-2)^-1)²

Ve výše uvedeném vzorci leží hodnoty proměnných z_n, z_n+1 a c v komplexní rovině. Oproti množinám Mandelbrotovým a Juliovým se mění i podmínka pro ukončení iterační smyčky, protože fraktální množina Magnet 1 má jeden z fixních bodů ležících na souřadnici 1+0i – „klasická“ Mandelbrotova množina má naopak fixní bod nulový, což se projeví zjednodušením všech výpočtů. Nenulový fixní bod má za následek změnu konkrétní implementace iterační smyčky.

Obrázek 27: Fraktální množina nazvaná Magnet 1

Obrázek 28: Fraktální množina Magnet 1 s nenulovou hodnotou perturbace

Fraktální množina nazvaná Magnet 2 používá následující poměrně složitý vztah v iterované funkci:

z_n+1((z_n³+3(c-1)z_n+(c-1)(c-2))×(3z_n²+3(c-2)z+(c-1)(c-2)+1)^-1)²

Je jisté, že takto složitá iterovaná funkce vede také k delší době trvání celého výpočtu obrázku s fraktálem. Zpomalení výpočtu je (v porovnání s klasickou Mandelbrotovou množinou) až desetinásobné.

Obrázek 29: Fraktální množina Magnet 2

2.5 Fraktály typu Phoenix

Fraktální množina nazvaná Phoenix byla objevena autorem, který se jmenuje Shigehiro Ushiki. Iterační vzorec, pomocí kterého je tato množina vytvořena, byl poprvé zveřejněn v časopise IEEE Transactions on Circuits and Systems, Volume 35, číslo 7, červenec 1988 na stranách 788–789. Za povšimnutí stojí, že se ještě v roce 1988 zveřejňovaly odborné články o počítačové grafice v „nepočítačových“ časopisech – dnes je díky SIGGRAPHu samozřejmě všechno jinak a na světě vychází přes dvě desítky specializovaných časopisů o počítačové grafice (k tomu ještě rozdělených podle určitých oblastí).

Vraťme se však k iteračnímu vzorci, kterým jsou popsány body ležící uvnitř fraktální množiny Phoenix. Zajímavé je, že vzorec je vlastně tvořen dvěma částmi. První část určuje změnu posloupnosti hodnot z_i, druhá část potom posloupnost hodnot pomocné komplexní proměnné nazývané podle notace použité ve výše uvedeném článku y_i. Iterační funkcí (resp. dvojici vzorců) je možné zapsat následujícím způsobem (bližší informace jsou uvedeny v dvacáté osmé části tohoto seriálu):

z_n+1=z_n²+Re©+­Im©y_n
y_n+1=z_n 

Na první pohled je Mandelbrotova varianta fraktální množiny Phoenix nezajímavá, vše se však změní po zvětšení oblastí ležících na hranici mezi body uvnitř množiny a vně množiny. Ještě zajímavější je však Juliova varianta, ve které se dají nalézt velmi zajímavé spirálovité tvary – viz obrázek číslo 31.

Obrázek 30: Fraktální množina Phoenix (Mandelbrotova varianta)

Obrázek 31: Juliova varianta fraktální množiny Phoenix

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

V následujícím pokračování seriálu o fraktálech používaných v počítačové grafice budou popsány zbylé „škatulky“, do kterých je možné fraktály roztřídit. Krátce si popíšeme dynamické systémy generované v hyperkomplexním prostoru za použití kvaternionové či hyperkomplexní algebry, systémy iterovaných funkcí (IFS), fraktály generované algoritmem Fractal Flames, stochastické fraktály (difúze, plasma), L-systémy a nakonec Markus-Ljapunovovy fraktály.