Hlavní navigace

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

Pavel Tišnovský

Ve druhém pokračování seriálu o fraktálech používaných v počítačové grafice jsme si vysvětlili základní pojmy, které se vztahují k fraktální geometrii. Jedná se o topologickou a Hausdorffovu dimenzi. V dnešní části se budeme zabývat dalšími důležitými pojmy, zejména soběpodobností, atraktorem, stavovým prostorem, bifurkací a deterministickým chaosem. Také si ukážeme prototypy demonstračních příkladů.

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 En je taková množina, pro kterou existuje konečně mnoho kontrahujících zobrazení φ1, φ2, … φn (jedná se o takové zobrazení zEn do En, které zmenšuje vzdálenost mezi dvěma body ležícími v prostoru En) takových, že A vznikne jako:

Fraktály 03 - 1

Pro E2 a E3 (v dalším textu bude E2 značit Euklidovskou rovinu a E3trojrozmě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 S1..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.

Fraktály 03 - 2

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

Fraktály 03 - 3

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

Fraktály 03 - 4

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:

xn=x+(-axdt)+(aydt)
yn=y+(bxdt)-(ydt)-(zxdt)
zn=z+(-c
zdt)+(xy*dt)

Fraktály 03 - 5

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

Fraktály 03 - 6

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.

Fraktály 03 - 7

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 
Fraktály 03 - 8

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.

Našli jste v článku chybu?

13. 12. 2005 13:13

rofl (neregistrovaný)
jj, a v javě to taky nefunguje. ZX spectrum mi to taky nevzalo.... ještě to skus zkompilovat fortranem....

24. 11. 2005 12:30

uživatel si přál zůstat v anonymitě
v delphi mi to nejde zkompilovat
Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

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

Vitalia.cz: 7 druhů hotových těst na vánoční cukroví

7 druhů hotových těst na vánoční cukroví

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

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

Jsou čajové sáčky toxické?

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

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

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

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

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

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

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

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

Podnikatelům dorazí varování od BSA

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

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

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

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

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

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