Hlavní navigace

Fraktály ve škatulkách 2

Pavel Tišnovský

Dnes budeme pokračovat v přehledu dříve popsaných typů fraktálů. Popíšeme si dynamické systémy generované v hyperkomplexním prostoru za použití kvaternionové či hyperkomplexní algebry, systémy iterovaných funkcí (IFS a L-IFS) a fraktály generované algoritmem Fractal Flames.

Obsah

1. Dynamické systémy generované v hyperkomplexním prostoru
   1.1 Použití kvaternionové algebry
   1.2 Použití hyperkomplexní algebry
2. Systémy iterovaných funkcí (IFS)
   2.1 IFS systémy vytvořené algoritmem náhodné procházky
   2.2 Lineari­zované IFS systémy
   2.3 Trojroz­měrné systémy iterovaných funkcí
3. Fractal Flames
4. Obsah dalšího pokračování tohoto seriálu

1. Dynamické systémy generované v hyperkomplexním prostoru

Velmi zajímavou, i když doposud málo známou skupinou fraktálních útvarů jsou fraktály vytvářené ve čtyřrozměrném prostoru (4D fraktály, 4D-F). V předchozí části tohoto seriálu jsme si zopakovali, že významnou skupinou fraktálů kreslených v ploše jsou mapy dynamických systémů ležících v komplexní rovině, mezi něž patří i známá Mandelbrotova množina, Juliovy množiny, fraktály typu Magnet, Barnsley, Lambda, Phoenix atd. Zdaleka nejpoužívanějším způsobem vizualizace těchto dynamických systémů je barevné zvýraznění počtu iterací, tj. celkového počtu opakování iterační funkce dynamického systému do té doby, než je splněna nějaká předem známá podmínka (například překročení bailout u Mandelbrotovy množiny a množin Juliových). Tyto množiny je poměrně snadné převést do 3D prostoru; typicky převodem na výšková pole (height field). To však není vše – tyto fraktální útvary je možné zobecnit i do prostoru čtyřrozměrného.

f781
Obrázek 1: Mandelbrotova množina použitá jako výškové pole

Jedním ze způsobů přechodu od těchto původně plošných fraktálů k fraktálům trojrozměrným (popř. čtyřroz­měrným) je náhrada komplexních čísel a komplexních iterovaných funkcí čísly a funkcemi hyperkomplexními. Příklad fraktálu (konkrétně Juliovy množiny) vytvořeného ve čtyřrozměrném prostoru s provedenou projekcí do trojrozměrného prostoru je ukázán na následujícím obrázku. Jedná se o model vytvořený v programu Quat, který je dostupný jak pro unixové systémy (s plnohodnotným grafickým uživatelským rozhraním i jako program ovládaný z příkazové řádky), tak i pro operační systémy MS-DOS a Microsoft Windows (DOSová verze grafické uživatelské rozhraní neobsahuje). Na první pohled vypadá přidaný (tj. čtvrtý) rozměr nadbytečný – ve skutečnosti však díky němu získáváme možnost provádění jednoduché animace celého fraktálu popř. i další parametry ovlivňující jeho tvar.

f782
Obrázek 2: Původně čtyřrozměrný fraktál po promítnutí do trojrozměrného prostoru

Úloha zobrazení 4D fraktálů je však poněkud komplikována zejména kvůli existenci „přebývajícího“ čtvrtého rozměru a dále také kvůli tomu, že většinou chceme vhodným způsobem zviditelnit povrch těchto objektů metodami založenými na existenci normálových vektorů. Mezi tyto metody patří i raycasting (zpětné sledování paprsku) a raytracing (rekurzivní zpětné sledování paprsku). Povrch čtyřrozměrných fraktálů je však obecně nediferencovatelný, tj. nelze u něj analyticky vyjádřit parciální derivace v bodech na povrchu, proto je nutné použít numerické techniky, které však nejsou ani přesné ani rychlé. V praxi se používají tři možné způsoby vykreslování čtyřrozměrných fraktálních obrazců: výčíslení plošných řezů původně čtyřrozměrným objektem (s jejich zobrazením například formou textur), metoda integrace podél paprsku, raycasting a raytracing a konečně převod objemového modelu na polygonální síť.

Tento typ fraktálních objektů byl popsán v části 62 až 68, spolu s popisem známého raytraceru POV-Ray a GNU aplikace Quat, které je možné použít pro generování zajímavých statických obrázků i animací původně čtyřrozměrných těles s fraktální strukturou.

f783
Obrázek 3: Plošný řez čtyřrozměrnou Juliovou množinou s nastavením cx=-0,13 cy=0,18 c­z=0,0 cw=1,0

1.1 Použití kvaternionové algebry

Kvaterniony (quaternions) a kvaternionovou algebru vymyslel v roce 1843 známý matematik William Rowan Hamilton, který původně hledal rozšíření komplexních čísel z 2D plochy do 3D prostoru. Takové rozšíření však není možné vytvořit, nejbližší ekvivalent komplexních čísel jsou až čtyřrozměrné struktury. Hamilton provedl revoluční krok v tom, že jím vymyšlené kvaterniony nesplňovaly vlastnost do té doby považovanou za naprostou samozřejmost – komutativitu. Později se objevily i další užitečné struktury, které komutativitu nesplňují, například matice. Kvaterniony jsou obdobou komplexních čísel, ovšem s tím rozdílem, že mají čtyři na sebe kolmé jednotky, které označujeme symboly 1, i, j a k. Jednotka 1 se někdy nazývá skalární složkou, zbylé tři jednotky i, j, k pak složkami vektorovými (to souvisí s využitím kvaternionů při popisu rotací). Každý kvaternion lze popsat lineární kombinací všech čtyř jednotek: q=x+yi+zj+wk.

f784
Obrázek 4: Fraktální objekt vypočtený pomocí kvaternionové algebry

1.2 Použití hyperkomplexní algebry

Hyperkomplexní čísla jsou v mnohém podobné kvaternionům. Není divu, protože je taktéž vynalezl William Rowan Hamilton. Opět se jedná o čísla, jež můžeme vyjádřit jako lineární kombinaci čtyř jednotek 1, i, j a k. Pro hyperkomplexní algebru platí, že je sice splněn komutativní zákon, tj. ab=ba, ale pro všechny prvky nemusí (ale v některých případech může) existovat inverzní prvek. Výsledkem aplikace hyperkomplexní algebry při výpočtu čtyřrozměrného fraktálu je objekt obsahující „čtvercové“ části, narozdíl od „kruhových“ či „elipsovitých“ částí v případě fraktálů vypočtených za pomoci algebry kvaternionové. Tento rozdíl je způsobem odlišnými multiplikativními operacemi v obou algebrách (v kvaternionové algebře odpovídá násobení dvou čísel jejich rotaci).

f785
Obrázek 5: Fraktální objekt vypočtený pomocí hyperkomplexní algebry

2. Systémy iterovaných funkcí (IFS)

Systémy iterovaných funkcí (IFS), které je možné použít pro vytváření procedurálních modelů těles s fraktální charakteristikou, zejména soběpodobností a invariancí ke změně měřítka, tvoří velmi významnou skupinu fraktálů, jejíž varianta je použita i ve fraktální komprimaci obrazu. Název IFS systémů je odvozen z původního anglického označení Iterated Function System, česky lze tento název přeložit jako systém iterovaných funkcí. První publikace, které se týkaly IFS systémů, vydali už v roce 1985 Demko a následně pak v roce 1987 Michael Barnsley (knihy Fractals Everywhere, Science of Fractal Images, Fractal Image Compression). Tvorba obrázků pomocí IFS systémů patří mezi generativní metody vytváření fraktálů, kterou řadíme mezi metody deterministické (stejně jako minule popsané metody pro vytváření fraktálních objektů v komplexní rovině). Algoritmus pro generování IFS fraktálů však může být jak deterministický, tak nedeterministický (tj. stochastický – viz algoritmus náhodné procházky – RWA).

f786
Obrázek 6: Několik „klasických“ IFS systémů

2.1 IFS systémy vytvořené algoritmem náhodné procházky

Princip generování IFS fraktálu je v nejjednodušším případě založený na takzvaném algoritmu náhodné procházky, který iterativně provádí následující výpočet: na bod Piter, který se nachází v rovině R2 nebo v prostoru R3, jsou buď deterministicky nebo náhodně (oním algoritmem náhodné procházky) aplikovány jednotlivé transformace φn. Výsledkem je nová pozice bodu Piter+1. IFS fraktál je poté zobrazen jako koláž složená ze všech vygenerovaných bodů Pi, i=(1..maxiter). Před vlastním generováním je zapotřebí určit počáteční pozici startovního bodu P0. Všechny transformace v IFS systému jsou zároveň i transformacemi změny měřítka s koeficientem menším než 1 – jde tedy o kontrahující transformace zajišťující směřování systému ke svému atraktoru (ve skutečnosti je toto příliš silná podmínka, mnohdy postačí použít pouze průměrné kontrahující transformace).

Proto je možné pozici startovního bodu P0 zvolit libovolně, protože po několika počátečních iteracích se díky kontrahujícím transformacím posloupnost generovaných bodů Pi samovolně dostane do atraktoru IFS. Většinou se volí P0=[0, 0] v rovině R2 resp. P0=[0, 0, 0] v prostoru R3. Transformace, které se budou v daném iteračním kroku aplikovat na bod Pi lze vybírat buď deterministicky nebo náhodně. V případě náhodného vybírání transformací (s uvažováním pravděpodobností jednotlivých transformací) potom mluvíme o algoritmu náhodné procházky. Tento algoritmus je s IFS neodmyslitelně spjatý a – i když jsou v něm použita náhodná čísla – vede k vytváření pravidelných, nestochastických (deterministických) fraktálů. Tento algoritmus je popsaný v třicátétřicáté třetí části seriálu.

f787
Obrázek 7: IFS systém vytvořený algoritmem náhodné procházky

f788
Obrázek 8: IFS systém vykreslený pomocí M-RWA

2.2 Linearizované IFS systémy

Linearizované systémy iterovaných funkcí (Linearized Iterated Functions Systems: L-IFS), pomocí nichž je možné vytvářet a především iteraktivně měnit tvar a strukturu velmi pěkně vypadajících plošných i prostorových obrazců, se vyznačují fraktální strukturou, tj. jsou soběpodobné a obsahují nekonečně mnoho detailů v různých měřítkách zobrazení. Jedná se o upravené klasické systémy iterovaných funkcí IFS; úprava spočívá v omezení typů transformací, zavedení řídicích bodů a rozšíření IFS systémů o takzvanou matici posloupnosti transformací, která slouží k další modifikaci výsledného plošného či prostorového obrázku. Oproti aplikacím, které využívají klasické systémy iterovaných funkcí je možné s pomocí linearizovaných systémů iterovaných funkcí vytvářet obrazce interaktivně a s okamžitou zpětnou odezvou uživateli.

Z praktického hlediska spočívá zásadní odlišnost L-IFS systémů oproti IFS systémům ve skutečnosti, že uživatel nemusí při tvorbě obrazce zadávat žádné číselné hodnoty jednotlivých transformací ani jejich pravděpodobností. Místo toho může interaktivně měnit polohu řídicích bodů v ploše či prostoru. S tímto způsobem editace objektů je uživatel většinou dobře obeznámen, protože se v počítačové grafice velmi často používá, například pro vytváření parametrických křivek a ploch. Jak uvidíme v dalším textu, existují i další souvislosti mezi parametrickými křivkami a fraktálními obrazci generovanými pomocí systémů L-IFS. Jedná se například o existenci konvexní obálky tvořené řídicími body. Tento typ fraktálů jsme si popsali v třicáté páté a třicáté šesté části tohoto seriálu.

f789
Obrázek 9: Ukázka linearizovaných IFS systémů

2.3 Trojrozměrné systémy iterovaných funkcí

Trojrozměrné systémy iterovaných funkcí vznikly rozšířením transformačních matic použitých u dvourozměrných IFS o další dimenzi. Tím se místo postupné aplikace transformací na 2D bod provádí aplikace transformací na bod ležící v trojrozměrném prostoru. Jiné změny vlastně samotný algoritmus generování jednotlivých bodů nepostihly, zcela odlišný je však způsob vykreslení těchto systémů. Při vizualizaci systémů iterovaných funkcí jsou postupně, tj. po aplikaci jednotlivých lineárních či nelineárních transformací, generovány body Pn. U 2D IFS jsme tyto body, jež ležely v rovině E2, považovali za souřadnice v rastrovém obrázku a na jejich zaokrouhlenou pozici jsme pomocí předem definovaného postupu změnili barvu pixelu (například v závislosti na počtu „zásahů“ daného pixelu, vybrané lineární transformaci apod.).

Prakticky nic nám nebrání v rozšíření již prezentovaných algoritmů tak, aby se místo bodů v rovině E2 vytvářely body ležící v trojrozměrném prostoru E3. Rozšíření spočívá v tom, že se transformační matice příslušející každé transformaci zvětší – místo matice o velikosti 3×3 prvky musí být použita matice 4×4 prvky, ovšem s tím, že poslední sloupec transformační matice má vždy hodnotu [0, 0, 0, 1]T a tím pádem nemusí být explicitně ukládán v operační paměti počítače. Samotné vykreslování vypočtených bodů může být založeno například na vytvoření malého čtverce s nanesenou bitmapou či na vykreslení bodu ve 3D prostoru se zadanou velikostí. Alternativně je také možné použít blending, tj. míchání barev bodů, které po projekci leží na stejném místě obrazovky.

f78a
Obrázek 10: Trojrozměrný IFS systém

3. Fractal Flames

Fraktální typ (resp. přesněji řečeno algoritmus) „Fractal Flames“ vytvořil před poměrně nedávnou dobou Scott Draves. Tento typ fraktálů vznikl 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 podle pravidel svého výběru variace), logaritmická závislost světlosti pixelu na počtu jeho „zásahů“ při vytváření obrazce, použití symetrie při vykreslování obrazce atd.

f78b
Obrázek 11: Fractal Flame vytvořený v grafickém editoru GIMP

Nejvýraznější rozdíl mezi klasickými systémy iterovaných funkcí a Fractal Flames 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. 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, obecně kolem jakékoli přímky procházející 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ě vypočtených souřadnic bodu Xn+1.

f78c
Obrázek 12: Druhý Fractal Flame vytvořený v GIMPu

Posledním rozdílem mezi systémy iterovaných funkcí a Fractal Flames 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. Tímto typem fraktálů, které jsou dokonce podporovány jedním zásuvným modulem známého grafického programu GIMP (GFlare), jsme se podrobněji zabývali v části třicáté osmé a třicáté deváté.

f78d
Obrázek 13: GIMP a Fractal Flame dotřetice

f78e
Obrázek 14: Objekt Fractal Flame s trojrozměrným vzhledem

f78f
Obrázek 15: Další Fractal Flame s trojrozměrným vzhledem

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

V následujícím pokračování tohoto seriálu dokončíme „škatulkování“ fraktálů. Popíšeme si stochastické fraktály (zejména fraktály vzniklé simulací difůze a plasmy), dále dvourozměrné i trojrozměrné L-systémy a Markus-Ljapunovovy fraktály. Nakonec si připomeneme význam šumové Perlinovy funkce.

f78g
Obrázek 16: Model křoviny vzniklý simulací difůze

f78h
Obrázek 17: Plasma vygenerovaná algoritmem iterativního dělení prostoru

f78i
Obrázek 18: Plasma vygenerovaná pomocí dvourozměrné šumové Perlinovy funkce
Našli jste v článku chybu?

2. 5. 2007 21:43

mr ip (neregistrovaný)
Vize podobne obrázkum 10, 14, 15 jsou mozne 'videt' se zavrenyma ocima behem psychedelickeho zazitku (da se navodit pomoci holotropniho dychani, LSD, lysohlavek atp.). Tak me napada, zdali nemaji funkce mozku (behem vnimani sveta) a fraktaly neco spolecneho.

2. 5. 2007 9:46

Tim Kutil Taylor (neregistrovaný)
covece, ja taky!
DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

DigiZone.cz: V Plzni odstartovalo Radio 1

V Plzni odstartovalo Radio 1

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

DigiZone.cz: SES zajistí HD pro M7 Group

SES zajistí HD pro M7 Group

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

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

Podnikatelům dorazí varování od BSA

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

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

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

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

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

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

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Vitalia.cz: Jak vybrat ořechy do cukroví a kde mají levné

Jak vybrat ořechy do cukroví a kde mají levné

Lupa.cz: Obchod budoucnosti je bez front, košíků i pokladen

Obchod budoucnosti je bez front, košíků i pokladen

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

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

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

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

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

DigiZone.cz: Sat novinky: slovenská TV8 HD i ruský NTV Mir

Sat novinky: slovenská TV8 HD i ruský NTV Mir

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

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

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D