Hlavní navigace

Fraktály ve škatulkách

Pavel Tišnovský 24. 4. 2007

V dnešním článku bude uveden přehled typů fraktálů, které jsme si již popsali. Celkový počet popsaných typů je poměrně velký, takže celý přehled je rozdělen do dvou částí. Dnes budou popsány dynamické systémy vykreslované v ploše či trojrozměrném prostoru a dynamické systémy, jejichž mapy jsou vykreslovány v komplexní rovině.

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

fractals77_1

Obrázek 1: Bifurkační diagram logistické funkce pro kladné hodnoty Gr (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 Gr) a na vertikální osu vnitřní stavy dynamického systému, což je u logistické funkce hodnota xn, jichž systém nabývá pro daný počet kroků (iterací). Hodnota xn 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.

fractals77_2

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

fractals77_3

Obrázek 3: Bifurkační diagram funkce xn+1=Gr(x-sin x2)

fractals77_4

Obrázek 4: Bifurkační diagram funkce xn+1=Gr(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.

fractals77_5

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

fractals77_6

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.

fractals77_7

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

fractals77_8

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

fractals77_9

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

fractals77_a

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

fractals77_b

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

fractals77_c

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.

fractals77_d

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.

fractals77_e

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émdvacátém prvním dílu tohoto seriálu. Použitá iterační funkce komplexní paraboly má tvar:

zi+1=zi2+c

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

zi+1=ziw+c

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

fractals77_f

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

fractals77_g

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

fractals77_h

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 xi+1 použit pro výpočet v následující iteraci:

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

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 x2-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 x2+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 i2=-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ě (zi a zi+1 leží v komplexní rovině):

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

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ě z0. 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 z0 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.

fractals77_i

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

fractals77_j

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

fractals77_k

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 zn+1=zn2+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

fractals77_l

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

fractals77_m

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

fractals77_n

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

fractals77_o

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

fractals77_p

Obrázek 25: Detail Barnsleyova fraktálu M3

fractals77_q

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 zn 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:

zn+1=((zn2+c-1)×(2zn+c-2)-1)2

Ve výše uvedeném vzorci leží hodnoty proměnných zn, zn+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.

fractals77_r

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

fractals77_s

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:

zn+1((zn3+3(c-1)zn+(c-1)(c-2))×(3zn2+3(c-2)z+(c-1)(c-2)+1)-1)2

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

fractals77_t

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 zi, druhá část potom posloupnost hodnot pomocné komplexní proměnné nazývané podle notace použité ve výše uvedeném článku yi. 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):

zn+1=zn2+Re©+­Im©yn
yn+1=zn 

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.

fractals77_u

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

fractals77_v

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.

Našli jste v článku chybu?

1. 5. 2007 20:24

To bych taky bral. Náměty mě nenapadají, nic takového neznám.

1. 5. 2007 16:19

wdt (neregistrovaný)
K této prosbě bych se přidal. 10tis. prodaných výtisku je asi nereálné, ale 10tis. downloadů by se myslím našlo ;-).
Vitalia.cz: Vláknina: Rozpustná, nebo nerozpustná?

Vláknina: Rozpustná, nebo nerozpustná?

Vitalia.cz: Jak koupit Mikuláše a nenaletět

Jak koupit Mikuláše a nenaletět

Lupa.cz: E-shopy: jen sleva už nestačí

E-shopy: jen sleva už nestačí

Vitalia.cz: I církev dnes vyrábí potraviny

I církev dnes vyrábí potraviny

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

Přehledná titulka, průvodci, responzivita

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

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

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

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

DigiZone.cz: Další dva kanály nabídnou HbbTV

Další dva kanály nabídnou HbbTV

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

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

Vitalia.cz: Žloutenka v Brně: Nakaženo bylo 400 lidí

Žloutenka v Brně: Nakaženo bylo 400 lidí

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

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č?

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET