Fraktály v počítačové grafice III

Obsah

1. Soběpodobnost
2. Atraktor
3. Lorenzův atraktor a problém tří těles
4. Bifurkace
5. Chaos
6. Stručné vyjmenování typů fraktálních objektů
7. Literatura a odkazy
8. Demonstrační příklady
9. Obsah dalšího pokračování tohoto seriálu

1. Soběpodobnost

Kromě pojmu dimenze uvedeného v předcházející části je dalším důležitým pojmem, který se velmi často při popisování abstraktních matematických fraktálů i přírodních útvarů s fraktální strukturou používá, soběpodobnost. Soběpodobnost (v matematice se setkáme spíše s přesnějším a korektnějším pojmem invariance vůči změně měřítka) je taková vlastnost objektu, jež způsobuje, že objekt či jeho část vypadá podobně (ne však nutně stejně!) při pohledu v různém zvětšení, tj. při rozdílných měřítkách. Soběpodobnost je jedním z hlavních znaků fraktálních útvarů, v některých publikacích jsou dokonce fraktály definované jako soběpodobné množiny; to však není zcela korektní, protože to vylučuje některé náhodné – stochastické – fraktály. Soběpodobný je například kámen, hory, mraky, stromy, rostliny ale i krátery atd., tedy objekty živé i neživé přírody.

Soběpodobnou množinu lze matematicky definovat následujícím způsobem: soběpodobná množina A z n-dimenzionálního Euklidovského prostoru dále označovaného Eⁿ je taková množina, pro kterou existuje konečně mnoho kontrahujících zobrazení φ₁, φ₂, … φ_n (jedná se o takové zobrazení zEⁿ do Eⁿ, které zmenšuje vzdálenost mezi dvěma body ležícími v prostoru Eⁿ) takových, že A vznikne jako:

Pro E² a E³ (v dalším textu bude E² značit Euklidovskou rovinu a E³trojrozměrný prostor) mohou být zobrazení φ_i v předchozím vztahu transformacemi posunutí, zkosení nebo otáčení a každá transformace je navíc i změnou měřítka s koeficientem S_1..n v (0,1). V tomto případě mluvíme o takzvaných lineárních transformacích. Tyto transformace jsou mimochodem použity i při generování klasických IFS fraktálů, kterými se budeme podrobněji zabývat v některém z dalších pokračování tohoto seriálu.

Obrázek 1: Klasický soběpodobný fraktál: kapradina

Množina definovaná pomocí předchozího vztahu má několik velmi zajímavých vlastností, které jsou typické pro velkou většinu fraktálních objektů:

• Soběpodobná množina vzniká opakováním sebe sama při určité transformaci. Transformací v tomto kontextu rozumíme například změnu měřítka, rotaci, posunutí či zkosení. Všechny tyto transformace (které jsou lineární) jsou definovány nad prostorem Eⁿ. Kromě lineárních transformací se samozřejmě používají i transformace nelineární, vždy však musí jít o transformace kontrahující, tj. vzdálenost libovolných dvou nestejnolehlých bodů se po aplikaci transformace musí zmenšit.
• Soběpodobné množiny jsou invariantní vůči změně měřítka. Při libovolném zvětšení či naopak zmenšení vypadají podobně. Tato vlastnost z velké části vyplývá už ze samotné definice soběpodobné množiny, která se skládá ze zmenšených kopií sebe sama.
• Soběpodobná množina vzniká sama ze sebe, respektive vzniká opakováním téhož základního motivu. Blíže viz předchozí vlastnost.

Princip opakování podobných tvarů ve zmenšené podobě je vidět prakticky u jakékoliv komplexní, složité struktury, která je vytvářena i pomocí velmi jednoduchých pravidel. Způsob, jakým probíhá větvení stromů či cév a žil v tělech živočichů nebo hromadění baktérií a řas v koloniích, se dá matematicky uspokojivě popsat pouze fraktální geometrií, pokusy o popis pomocí klasické Euklidovské geometrie ztroskotaly (tj. byly buď neúměrně komplikované, a/nebo neodpovídaly realitě). Fraktály však slouží i k modelování a pochopení složitých dějů, které se odehrávají v čase, jedná se tedy o jevy dynamické.

Obrázek 2: Soběpodobný systém IFS

Při používání pojmu soběpodobnosti si musíme uvědomit, že se jedná o podobnost objektu pouze při změně měřítka. Existuje mnoho geometrických útvarů, které jsou podobné (nebo dokonce shodné) při aplikaci jiné transformace. Například čtverec je invariantní vůči středovému zrcadlení, kruh je invariantní vůči stranovému i středovému zrcadlení a přímka je invariantní vůči posunu ve směru jejího vektoru (a také vůči zrcadlení). Tato invariance, pokud není doprovázena invariancí vůči změně měřítka, v žádném případě nedefinuje fraktál, ale „obyčejný“ objekt Euklidovské geometrie.

2. Atraktor

Zejména při popisu dynamických systémů a systémů iterovaných funkcí (IFS) se často setkáme s termínem atraktor. Při zobrazování IFS systémů většinou vykreslujeme právě atraktor tohoto dynamického systému.Atraktor (anglicky attractor) dynamického systému je množina stavů, do kterých systém směřuje. Jinými slovy se jedná o množinu hodnot, kterých může nabývat stavový vektor dynamického systému po dostatečně dlouhém časovém úseku od počátečního impulzu (resp. od chvíle, kdy je systém inicializován). Atraktory rozdělujeme do několika základních tříd:

• atraktorem systému může být množina pevných bodů (fixed points)
• atraktorem může být množina periodických bodů
• atraktorem může být množina kvaziperiodic­kých bodů
• atraktor je chaotický
• atraktor je „podivný“ (strange attractor)

Jsou-li atraktorem dynamického systému pevné body(resp. množina pevných bodů), jedná se o nejjednodušší případ, protože se systém v nekonečném čase ustálil v nějakém stabilním stavu, který je možné dopředu vypočítat.

Jsou-li atraktorem periodické (resp. kvaziperiodické) body, jde také o vcelku jednoduchý případ. Systém se totiž po určité době ustálí tak, že osciluje mezi několika stavy. Ty mohou být buď spočitatelné (astabilní klopný obvod), nebo nespočitatelné (dráha osamělé planety okolo slunce).

Je-li atraktor chaotický, znamená to, že výsledný stav systému nelze v podstatě nijak dopředu předpovědět. To může být způsobeno mimo jiné tím, že je systém velmi citlivý na počáteční podmínky. Chaotičnost v tomto případě neznamená náhodnost (stochastický systém), protože se stále bavíme o systémech deterministických.

Podivný atraktor (anglicky strange attractor) je z hlediska fraktální geometrie nejzajímavějším případem atraktoru. Tento typ atraktoru může vzniknout tehdy, je-li systém popsán minimálně třemi navzájem souvisejícími diferenciálními rovnicemi (v případě, že funkce použité v rovnicích není možné invertovat, může být rovnic i méně – příkladem je bifurkační diagram). Takový systém může mít velmi komplikovaný atraktor, který sice bude vykazovat vlastnosti pravidelného, ale současně i chaotického atraktoru. Termín podivný atraktor není ještě přesně matematicky definován (definice sice existují, ale nezahrnují všechny typy podivných atraktorů), ale považujeme za něj takový atraktor, který vykazuje vlastnosti do jisté míry shodné s těmi, jaké mají fraktály. Dále platí, že všechny chaotické atraktory jsou současně podivnými atraktory, opačná implikace však neplatí.

Obrázek 3: Systém s podivným atraktorem

3. Lorenzův atraktor a problém tří těles

Na dalším obrázku je zobrazen první detailně popsaný dynamický systém s podivným atraktorem. Tento systém sestávající ze tří dynamických rovnic použil Edward Lorenz v roce 1963 při simulaci vývoje počasí (resp. ve velmi zjednodušeném modelu počasí). Na tomto systému byla také numericky a analyticky ověřena velká citlivost na počáteční podmínky (někdy také nazývaná „motýlí efekt“). Pro upřesnění je však nutné říci, že při simulaci na počítači vlastně získáme atraktor, jenž je periodický. Je to z toho důvodu, že pro zobrazení číselných hodnot je použito konečného počtu bitů, z toho nutně vyplývá, že se po určitém počtu kroků (který je však obrovský, takže tento jev mnohdy nezaregistrujeme) začne dráha Lorenzova atraktoru překrývat. V matematicky přesném modelu však tato situace nenastane, každá smyčka bude mít unikátní tvar a dráhy se nebudou překrývat, pouze protínat. Diferenciální rovnice Lorenzova atraktoru mají po převodu na diferenční tvar následující formát:

x_n=x+(-axdt)+(aydt)
y_n=y+(bxdt)-(ydt)-(zxdt)
z_n=z+(-czdt)+(xy*dt)

Obrázek 4: Lorenzův atraktor

Jedním z často citovaných problémů, které úzce souvisejí s podivnými atraktory a dynamickými systémy obecně, je takzvaný problém tří těles. Jedná se o úlohu pocházející z klasické newtonovské fyziky. Problém tří těles je nastolen tak, že máme ve vesmíru tři tělesa a dané počáteční podmínky (tedy polohu těles, jejich hmotnost, počáteční rychlost a směr – vektor – pohybu). Máme za úkol analyticky vypočítat polohu těles v libovolném časovém okamžiku.

Bylo dokázáno, že tento problém není řešitelný, což je jistě velmi zajímavé, protože problém dvou těles je až triviálně jednoduchý (alespoň v newtonovské mechanice). Při studiu pohybu tří těles se totiž ukázalo, že se tělesa pohybují po částečně chaotických drahách a jsou přitahována k určitým bodům na své dráze. Tyto body se pro svou vlastnost (přitažlivost, anglicky attraction) nazývají atraktory, z toho také vyplývá i výše uvedené označení. Reálných systémů s podivnými atraktory je velmi mnoho a z tohoto důvodu je zde nemůžu všechny popsat.

4. Bifurkace

Termínem bifurkace se značí jev, při kterém dochází k velkým změnám vnitřního stavu ve sledovaném systému v případě, že se vstupní parametry nepatrně změní. U některých systémů k bifurkacím (alespoň za běžných podmínek) nedochází, protože se s postupným zvyšováním či snižováním hodnot vstupních parametrů (například teploty při chemických reakcích) systém mění pouze nepatrně – ve značně jednoduchých případech se dokonce jedná o lineární závislost na vstupních parametrech. Existují však systémy, u nichž po dosažení určitých (kritických) hodnot na vstupu dochází k prudké změně vnitřního stavu. Může se například jednat o vznik turbulence v potrubí při dosažení určité rychlosti proudění kapaliny, o fázový přechod látky při změně teploty, změny magnetických vlastností materiálu po dosažení Courieovy teploty atd.

Bifurkace do značné míry souvisí s chaosem, nejedná se však o stejné termíny (chaos nastává v případě, že v systému začíná docházet k velkému množství na sebe navazujících bifurkací). Jedním z nástrojů pro studium bifurkace je takzvaný bifurkační diagram, který je zobrazen na následujícím obrázku. V bifurkačním diagramu jsou na horizontální osu naneseny hodnoty vstupního parametru, ve vertikálním směru jsou vyneseny hodnoty jednoho z vnitřních stavů, jichž systém v po sobě následujících krocích nabývá. Všimněte si, že pro některé vstupní hodnoty je systém stabilizován, pro další hodnoty dochází k periodickému překmitávání mezi několika stavy a pro zbylé hodnoty se systém chová chaoticky (nepředvídatelně).

Obrázek 5: Bifurkační diagram

5. Chaos

Termínem chaos je označena taková vlastnost nějakého dynamického a současně i deterministic­kého(!) systému, při jejíž platnosti je nemožné vypočítat budoucí stav systému. Chaos nastává zejména u těch dynamických systémů, které vykazují velkou citlivost na počáteční podmínky. V takových systémech se při volbě minimálně dvou nekonečně blízkých počátečních bodů (reprezentujících počáteční podmínky systému) tyto dva body posléze exponenciálně vzdalují, takže budoucí stav systému není možné žádným způsobem předpovědět.

Typickým představitelem chaotického systému je jakýkoli relevantní model počasí (dokonce i reálné počasí). I malé změny v počátečních podmínkách vykazují v budoucnosti dramatické změny – z toho také vyplývá i známá věta, že pouhé mávnutí motýlím křídlem může o týden později způsobit hurikán (butterfly effect). Dalším systémem citlivým na počáteční podmínky je systém složený z kužele a kuličky postavené na vrcholu tohoto kužele. V závislosti na nekonečně malých změnách počátečních podmínek kulička spadne do libovolného směru, a může tak dramaticky ovlivnit další chování systému. U obou zmíněných systémů dokonce platí věta, že stav systému není možné změřit naprosto přesně, protože již samotné měření chování systému ovlivňuje (mnohem precizněji je toto tvrzení uvedeno pro kvantové jevy v učebnicích kvantové fyziky).

6. Stručné vyjmenování typů fraktálních objektů

Podobně jako v ostatních vědních disciplínách se i ve fraktální geometrii začaly po určitém čase rozlišovat jednotlivé typy fraktálů, přičemž fraktály stejného typu mají shodné své nejvýznamnější charakteristiky. Toto rozlišování není zavedeno pouze kvůli systematičnosti („škatulkování“), ale i proto, že jednotlivé typy fraktálů jsou vhodné pro řešení pouze určitého okruhu problémů, které se vyskytují v jednom nebo více oborech. Také vlastní způsob generování (vytváření) fraktálů se liší podle typu fraktálu, přičemž fraktály stejného typu se většinou generují s využitím podobných algoritmů.

Podle nejhrubšího dělení rozlišujeme následující typy fraktálů:

• Dynamické systémy s fraktální strukturou
• L-systémy
• Systémy iterovaných funkcí IFS
• Stochastické fraktály (nepravidelné fraktály)

Jednotlivé typy fraktálů budou popsány v dalším pokračování tohoto seriálu.

Obrázek 6: Dynamický systém s fraktální strukturou vytvořený v hyperkomplexním prostoru

7. Literatura a odkazy

1. Devaney Robert L.: „A First Course In Chaotic Dynamical Systems“,
   Addison-Wesley, Reading, MA, 1992
2. Gleick James: „Chaos: Making a New Science“,
   Viking Press, Penguin, New York, 1987
3. Gleick James: „Chaos: Vznik nové vědy“ (český překlad předchozí knihy),
   Ando Publishing, Brno, 1996
4. Peitgen Heinz-Otto, Jurgens Hartmut, Saupe Dietmar: „Chaos and Fractals: New Frontiers of Science“,
   Springer-Verlag, New York, 1992
5. Pickover Clifford: „Computers, Pattern, Chaos and Beauty: Graphics from an Unseen World“,
   St. Martin's Press, New York, 1990
6. Pritchard Joe: „The Chaos Cookbook: A Practical Programming Guide“,
   Butterworth-Heinemann, Oxford, 1992, ISBN 0–7506–0304–6
7. Elert Glenn: „Chaos, Fractals, Dimension“,
   http://www.co­lumbia.edu/~ga­e4/chaos/

8. Demonstrační příklady

V této chvíli ještě nemáme potřebné informace, které by nám umožnily generování fraktálních obrazců. Níže uvedené demonstrační příklady jsou zde uvedeny pouze pro otestování hlavních částí demonstračních příkladů prezentovaných v dalších pokračováních. V hlasování s přehledem vyhrála kombinace C+OpenGL+GLUT, ale i další výsledky jsou zajímavé, zejména to, že Atari Basic předběhl Javu s AWT – s tím se nedá než souhlasit :-). V prvním příkladu je ukázána práce s rastrovým obrázkem (pixmapou), ve druhém příkladu práce s obrázkem vektorovým. Stisknutím klávesy [S] se pixmapa či vektorový obrázek uloží do souboru typu TGA (Targa). Způsob překladu se liší podle používaného operačního systému a překladače.

Operační systém Unix/Linux:

gcc -L/usr/X11R6/lib fractals03_1.c -lglut -lGL -lGLU -lm -lX11 -lXmu 

popř:

gcc -L/usr/X11R6/lib fractals03_1.c -lglut -lGL -lGLU -lm -lX11 -lXmu -lXi 

Operační systém Windows a překladač GCC (MinGW):

gcc fractals03_1.c -lglut32 -lopengl32 

Operační systém Windows a překladač BCC (Borland C++):

bcc32 fractals03_1.c glut32.lib 

• zdrojový kód prvního demonstračního příkladu
• obarvený zdrojový kód prvního demonstračního příkladu
• zdrojový kód druhého demonstračního příkladu
• obarvený zdrojový kód druhého demonstračního příkladu

Obrázek 7: Screenshot prvního demonstračního příkladu

Problémy s překladem či spouštěním snad vyřešíme v diskusi pod článkem.

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

V dalším pokračování tohoto seriálu budou podrobněji popsány jednotlivé typy fraktálů, rozvedeme si tedy informace uvedené v šesté kapitole.