1
FRAKTÁLY
S názvem fraktál přišel matematik B. Mandelbrot ( IBM, Harvard univ.) kolem roku 1975.
Záhy fraktální funkce nacházejí použití v řadě oborů.
Aplikace v počítačové grafice:
Vizuální modelování přírodních objektů a textur.
Typické znaky přírodních objektů:
Tvarová komplikovanost a řád v ,,chaosu" (fractus).
Nepřehlédnutelná tvarová soběpodobnost nezávislá na měřítku.
Pro výtvarnou bohatost a atraktivnost jsou fraktály velkým tématem
Výtvarné informatiky (Mathematic Art).
2
Studium ,,divných" funkcí (1875 - 1925) Cantor, Peano, Sierpinski, Koch, ....
Iterace algebraických transformací
T :  d
 d
d dim. E. prostor
Posloupnost bodů v prostoru
x0 = x, x1 = T(x), x2 = T(T(x)), x3 = T(T(T(x))), ...
Zajímá nás: průběh xi, atraktory, atd.
Zobecníme x a T (iniciátor, generátor)
Př. Peanova křivka ( 1890 ),
Iterace zobrazení úsečky na plochu vede
k rozporu v topologických dimenzích.
Fraktální objekt je tvarově nezávislý
(invariantní) na měřítku.
Dimenze fraktálního objektu (Hausdorfova)
je ostře větší než jeho dimenze topologická.
3
Jinou cestou se k fraktální závislosti dostal Richardson
Délka pobřeží Korsiky ( L. F. Richardson, 1961)
L = k.a1 - D
a = 20 km a = 10 km
Mandelbrot dává do souvislosti D a
Hausdorfovu dimenzi.
Základní vlastnosti fraktálů si objasníme na tzv. křivkách vyplňujících prostor.
4
KŘIVKY VYPLŇUJÍCÍ PROSTOR (SFC)
Kochova sněhová vločka jako vzorový příklad fraktální funkce
5 6
7 8
JDE NEPOCHYBNĚ O DIVNOU FUNKCI (,,MATEMATCKÉ MONSTRUM") !
9
Příklady křivek SFC, které později zapisujeme pomocí přepisovacích gramatik
10
Jednoduché aplikace SFC do 3D:
11
Hilbertova křivka v 3D
12
13 14
15
Dimenze a soběpodobnost
Dimenze D Dělení Měřítko
1 N dílů N
s
1
= Ns1
= 1
2 N dílů N
s
1
= Ns2
= 1
3 N dílů 3
1
N
s = Ns3
= 1
Obecně NsD
= 1
S
N
D
1log
log
=
Veličinu D nazveme fraktální dimenzí.
Přesně je fraktální dimenze definována Hausdorfem (Hausdorf ­ Bezicovitchova dimenze).
16
17 18
Chyba počítání čtverečků je přijatelná !
19
Př 1:
Fraktální analýza obrazů
Jacksona Pollocka
Po separaci barev
počítáme čtverečky.
Výsledek:
20
Př 2. Test pravosti NonPollock:
Soběpodobnost
NonPollock: Pollock:
Výsledek
21
ESTETIKA VĚTVENÍ (výstupem BIOART, metodou FRAKTÁLY)
22
ALGORITMY VĚTVENÍ
Primitivní kódování větvení:
Příklad jednoduchého zápisu:
0 koncový úsek (pupen)
1 větvička (elementární úsek)
2 ...
3 návrat do místa větvení
4 místo větvení L
5 místo náhodného směru větvičky
6 místo větvení R
atd
Zákon růstu - kód větvičky:
0 0. generace
1 6 0 314 0 3 1 0 1. generace
116 3114 311 2. generace
atd.
Moderní grafické interprety pracují se zápisem větvení přepisovacími gramatikami:
23
L-systém a přepisovací gramatiky
A. Lindenmayer, P. Prusinkiewicz, J. Hanan, ... B. Beneš, D. Stuchlík, M. Psota, M. Kolka a další
Deterministický bezkontextový L-systém
Je dána uspořádaná trojice G = [V,P,S]
V ... je konečná abeceda symbolů A, B, X ...
P ... je konečná množina pravidel A  ; A  V;   V*
S ... je axiom: S  ; S  V+
Jestliže je A    P, kde   V*, pak neexistuje A    P :   ,   V* ­ determinismus.
Derivace  řetězce   V* znamená paralelní přepsání všech symbolů X   řetězci  z množiny
pravidel P, kde X    P.
Derivační hloubka je počet iterací  (přepisování se většinou omezuje stanovením počtu opakování).
Vygenerovaný řetězec se následně graficky interpretuje (želví grafika ­ 2D, 3D).
24
Želví grafika (2D, 3D)
Želva je reprezentována svým stavem
tj. polohou a orientací v kartézském souřadném systému
(příp. šířkou a barvou kreslicího pera).
Orientace ve 3D je definována pomocí navzájem kolmých vektorů jednotkové délky H(eading), L(eft), U(p).
Rotace želvy je vyjádřena rovnicí:
[ H' L' U' ] = [ H L U ] R ,
kde R je matice rotace 3×3.
25
Deterministický bezkontextový L-systém
Příklad - Kochova vločka:
G = [{S, F, ­, +}, {S  F ­ ­ F ­ ­ F, F  F + F ­ ­ F + F, +  +, ­  ­}, S]
1. derivace S  F ­ ­ F ­ ­ F
2. derivace F ­ ­ F ­ ­ F  F + F ­ ­ F + F ­ ­ F + F ­ ­ F + F ­ ­ F + F ­ ­ F + F
.........
dodefinujme
+ ... otočení o 60° doprava
­ ... otočení o 60° doleva
F ... posun dopředu (o zvolenou délku d)
26
Závorkové L-systémy (systémy se zásobníkem)
Obohacení L-systému o zásobník, který slouží k uložení pozice želvy.
Zápis:
[ ... uložení stavu do zásobníku
] ... vyzvednutí stavu ze zásobníku a následná aktualizace želvy
Příklad 1. Příklad 2.
Grafická interpretace řetězce F[+F]F :
27
Otevřené L-systémy
Otevřeností rozumíme schopnost obousměrné komunikace ,,generovaného objektu" s okolím
(př. modelování růstu rostlin).
Tyto systémy jsou rozšířené o tzv. komunikační moduly, které slouží k přenášení informací mezi
přepisovaným řetězcem a okolím:
Vstup informace do přepisovacího procesu (detekce kolize rostliny s překážkami, množství dopadajícího
světla, kvalita půdy, ...
Výstup informace ven z přepisovacího procesu (rozložení v prostoru, vylučování látek ...).
Stochastické L-systémy
V množině pravidel P může být více pravidel se stejnou levou stranou.
Např. pro symbol A platí:
A  1 : p1 ;   2 : p2 ; ...   n : pa ; kde A  V, i  V*, pi  <0,1>
pi ... pravděpodobnost, že se použije při přepisování A pravidlo   i : pi
 =
n
pi
1
1
28
Parametrické L-systémy
Parametrický L-systém pracuje s tzv. parametrickými slovy.
Parametrická slova jsou posloupnosti modulů a moduly jsou písmena abecedy rozšířená o parametry.
Modul má syntaktickou podobu A(x1, ..., xm). Množina parametrů modulu může být prázdná, ale musí být
konečná. Modul má ve své specifikaci formální parametry, které nabývají hodnot - skutečných parametrů
z množiny reálných čísel.
Z parametrů je možno tvořit aritmetické a logické výrazy.
Formálně zapsáno:
Parametrický L-systém je uspořádaná čtveřice G = (V, , , P), kde:
V je abeceda
 je množina formálních parametrů
P je konečná množina pravidel
  (V × R)+
je neprázdné parametrické slovo zvané axiom (R je množina reálných čísel)
Pravidla p  P v parametrických kontextových L-systémech mají tvar:
pred : cond  succ
kde:
pred je levá strana pravidla
cond je logický výraz nabývající hodnoty 1 nebo 0
succ je pravá strana pravidla
29
Příklad 3.
A(t) : t > 5  B(t + 1)CD(t ^ 0.5, t - 2)
pravidlo s levou stranou A(t),
podmínkou t>5
a pravou stranou
B(t + 1)CD(t ^ 0.5, t - 2).
Modul vyhovuje danému pravidlu, pokud:
Písmeno v modulu se shoduje s písmenem v pred.
Počet parametrů v modulu a počet parametrů na levé straně pravidla jsou si rovny.
Je splněna podmínka cond.
Pravidlo vyhovující danému modulu může být použito na ,,rozbalení" (nahrazení) modulu
řetězcem specifikovaným v části succ daného pravidla.
30
Příklad 4.
Definujme L-systém:
 : B(2)A(4,4)
p1 : A(a,b) : b < 3  A(a * 2, a + b)
p2 : A(a,b) : b >= 3  B(a)A(a / b, 0)
p3 : B(a) : a < 1  C
p4 : B(a) : a >= 1  B(a-1)
Odvození výsledného řetězce modulů z axiomu :
B(2) A(4,4)
 
B(1) B(4) A(1,0)
  
B(0) B(3) A(2,1)
  
C B(2) A(4,3)
 
B(1) B(4) A(1.33, 0)
31
Kontextový L-systém
Při přepisování symbolu se uvažují posloupnosti symbolů na levé a pravé straně.
Např.
lc<>rc  , kde , lc, rc  V*, A  V
Symbol A se přepíše na , jestliže se vyskytuje v levém kontextu lc a v pravém kontextu rc.
Kombinované L-systémy
Pravidla p  P v parametrických kontextových stochastických L-systémech mají tvar:
id : lc <A>rc : cond   : p
kde je:
id číslo pravidla
rc,lc pravý a levý kontext
A symbol, který se bude přepisovat
cond logický výraz nabývající hodnoty 0 nebo 1
 na co se A přepíše
p pravděpodobnost použití daného pravidla
32
Příklad 5.
Definujme L-systém
 : A(0)
p1 : A(x) : x = 0  FA(x+1)
p2 : F < A(x) : x = 1  [-L]FA(x+1)
p3 : F < A(x) : x = 2  [+L]FA(x+1)
p4 : A(x) : x = 3  B
Dodefinujme:
F posun dopředu
A(x) vrcholový pupen, x je jeho stáří Grafická interpretace:
B květ
L list
­ p1 probudí vrchol
­ p2, p3 růst a vyrašení listů
­ p4 přechod ve květ
33
Příklady podle D. Stuchlíka:
Notace symbolů:
f(a) Posun dopředu o krok délky a.
F(a) Posun dopředu o krok délky a; mezi původní a novou pozicí se vykreslí čára.
+(a) Rotace želvy kolem vektoru U o úhel a.
&(a) Rotace želvy kolem vektoru L o úhel a.
/(a) Rotace želvy kolem vektoru H o úhel a.
[ Uložení současného stavu na zásobník.
] Vybrání stavu ze zásobníku.
;(a) Nastavení barvy kreslícího pera na a.
#(a) Nastavení tloušťky kreslícího pera na a.
34
Příklad ,,Vločka Kocha"
(derivační hloubka 10)
#define J 4
#define LEN 2
{ axiom: }
B(J)
{ pravidla: }
B(t):*:V(t)+(120)V(t)+(120)V(t)
V(t):t = 0: A(LEN)
V(t):t > 0:V(t-1)+(-60)V(t-1)+(120)V(t-1)+(-60)V(t-1)
A(t):*:F(t)
Kochova vločka
35
Příklad ,,Květ černého bezu"
(derivační hloubka 10)
#define ANG 3
;(2)T(10)
T(t):t>0:#(t/3)F(t*5)[&(ANG*t)T(t-1)][&(-1*ANG*t)T(t-1)]F(t*5)T(0)
T(t):t=0:[#(3);(4)F(1)]
L(t):*:[&(25)T(t)]
R(t):*:[&(-25)T(t)]
Květ černého bezu
36
Příklad ,,Přeslička ve větru"
(derivační hloubka 12)
#define DELAY 1
#define RATE 1.5
#define ANG 30
#define WIND 10
;(0)/(90)A(0)
A(d):d>0:A(d-1)
A(d):d=0:F(0.5)+(WIND)[+(ANG)A(DELAY)][+(-1*ANG)A(DELAY)]F(1)A(0)
F(l):*:F(l*RATE)
Přeslička ve větru
37
Příklad ,,Strom"
(derivační hloubka 6)
#define DA 137.5
#define BA 40
#define BR 1.432
#define LR 1.155
#define WR 1.052
#(10)F(50)A(10)
A(w):*:#(w)F(30)[&(BA)A(w/BR)]/(DA)[&(BA)A(w/BR)]/(DA)[&(BA)A(w/BR)]
F(l):*:F(l*LR)
#(w):*:#(w*WR)
Strom
Atraktivnější jsou kreace ve 3D.
38
Příklad výtvarného pojetí LS:
39
Modelové pojetí LS
P. Prusinkiewicz
a jeho žáci:
40
Kvalita programu pro modelování je dána i kvalitou jeho komunikační vrstvy
Př.
Greenworks Organic Software
jazyk Xfrog
41
SYSTÉMY AFINNÍCH TRASFORMACÍ (IFS - BARNSLEY, DEMKO)
IFS{T,P}
T = {T1, T2 ,... ,Tn} Podmínky - transformace měřítka < 1,
P = {P1, P2 ,... ,Pn}
Zi+1 = Tj(Zi) , Z0
|
Pj
KOLÁŽNÍ TEORÉM
(ATRAKTORU)
INVERZNÍ PROBLÉM T1, T2 , ...., Tn = ?
Př. :
A1 = T1(A)
A2 = T2(A)
A3 = T3(A)
A4 = T4(A)
Transformaci definuje šest rovnic: Tj {aj, bj, cj, dj, ej, fj} <=    j j j
Poznámka: REDUKCE DAT ( > 1 : 10 000)
1P
n
1j j = =
fdycx
ebyax
y
x
:T
ii
ii
1i
1i
j
++
++
=
+
+
)A(T...)A(T)A(TA n21 =
A
A
P
j
j =
42
URČENÍ KOEFICIENTŮ AFINNÍ TRANSFORMACE
Pozn. a = r . cos b = -s . sin r - měř. x  - rot. y
c = r . sin d = s . cos s - měř. y  - rot . x

=
-
-
= n
1k k
c
k
b
k
d
k
a
j
c
j
b
i
d
i
a
i
p
43
Pro stanovení dílčích transformací T vlastně stačí ,,zastupující" trojúhelníky
Pro koeficienty a, b, c, d, e, f potřebujeme trojice bodů
44
Poznámka: neúplné pokryti a překrytí vylepšuje výtvarný efekt
45
Práce s trojúhelníky je však
náročnější na představivost:
46
Různé provedení IFS (textury
47
IFS ­ nic nového pod sluncem:
48
Podstatné vylepšení kreací pomocí IFS přinesl Scott Draves
- iteracemi vypočítané hodnoty podrobuje nelineárním transformacím
- jas (resp. barvu) pixelů řídí logaritmem počtu jeho ,,navštívení n" během výpočtu
- výsledek filtruje (rozmazává)
- dovoluje prolínání obrazů
- atd.
Př. Nelineární
Transformace
Podle těchto zlepšení realizoval Scott Draves program FLAME.
49
Př. Kreace S. Dravese:
Další vylepšení v programu
APOPHYSIS Marka Townsenda.
50
Fraktály v komplexní rovině
Mandelbrotova množina (Julia, Fatou, 1925, Mandelbrot, Douady,...1980)
Zn+1 = f(zn) = zn
2
+ c,
z, c jsou komplexní čísla
Př. Ať c = 0,
z0  z0
2
 z0
4
... Im
atraktor:
0 pro z0 < 1
nekonečno pro z0 > 1
kružnice pro z0 = 1
Re
B. Mandelbrot c  0, z0 = 0, c var. G. Julia c. 0, c fix. z0 var.
51
Hledáme hranici Mandelbrotovy množiny
Únikový potenciál
Únikový počet iterací vyznačíme barvou
,,Pracovní nekonečno" zn  = c + 2
analogie kondenzátoru
52
Efekt vnořování:
53
Připomeňme: B. Mandelbrot c  0, z0 = 0, c var. G. Julia c. 0, c fix. z0 var.
Juliovy množiny jako ,,atraktivní souputníci" :
54
Výpočet Mandelbrotovy a Juliovy množiny
55
Barvení fraktálů ­ barevné gradienty
V každém bodě komplexní roviny (pixelu) je generována řada f(zi) = z0, z1 ,z2, ..., zn.
Délku řady jsme omezili únikovým počtem iterací i = n, kdy zn > R. Zpravidla R = 2.
ˇ Základní kolorování
je nejjednodušší a proto časté.
color = g(n)
Funkce g kvantuje rozsah R, G, B
podle použité palety.
Palety můžeme vázat (opakovat).
Stačí 256 barev,
nevýhodou je ,,proužkování".
56
Základní princip barvení
- využití počítaných hodnot zi = zn
Pixel + zastupující bod C(Re,Im)
dostane barvu col(n) pro n = 11.
57
Př. Editor barev Programu FRACTINT.
Pro plný počet barev (true color) lze vytvářet barevný gradient prokládáním křivkou.
58
Př. Editor programu ULTRA FRACTAL
59
mizí proužkování
Složitější kolorování je založeno na hledání
vhodné Euklidovské vzdálenosti využívající
vypočítaných hodnot zn .
60
Výpočetně náročnější kolorovací algoritmy (J. Barallo, D.M. Jones: Math Art 2001)
ˇ Odhad vzdálenosti
ˇ Spojitý potenciál (,,v kondenzátoru")
Pro R=b
Můžeme zavést vyhlazovací funkci n= e- z
61
ˇ Výpočet únikového úhlu
Řadu zi vyhodnocujeme v polárních souřadnicích a sledujeme i.
Binární dekompozice Spojitá dekompozice
Poznámka: Podobně lze pracovat i s odvěsnami vzniklého trojúhelníka.
62
ˇ Výpočet ,,křivosti řady"
Počítáme ze tří následujících hodnot:
ˇ Výpočet statistických charakteristik apod.
Průměry, rozptyl, ...
Výpočetně náročnější je
fraktální dimenze, Ljapunovův exponent
apod.
Někdy je výhodné počítat inverzní hodnoty
(jsou ohraničené).
63
ˇ Výpočet pomocí řídicích oblastí ­ pastí (orbit traps)
V komplexní rovině vymezíme oblasti (body, úsečky, kružnice, n-úhelníky apod. )
Padne-li zi do této oblasti, pak zi = zn .
Oblasti s výhodou centrujeme k počátku. Tato metoda dovoluje řadu variant barvení.
Gaussova čísla
mohou vytvořit pravoúhlou síť pastí.
64
ˇ Vytváření 3D efektů
Současně počítáme tři ,,sousední body", tyto určí rovinu a k ní pak vypočítáme normálu.
Podle polohy zdroje světla určíme Gouraudovo stínování.
Poznámka: S výhodou umísťujeme světelný vektor L do reálné nebo imaginární osy.
Pak stačí paralelní výpočet jen dvou bodů.
65
Doplnění:
,,Konečné atraktory" počítáme stejně!
Sledujeme rozdíl dvou po sobě následujících členů řady zi. . Klesne-li pod určenou hodnotu,
výpočet řady ukončíme a bod obarvíme.
66
Skládání obrazů s různými
výřezy a průsvity vytváří další
výtvarné efekty.
67
Příklad monotónního vybarvení (3 tóny)
68
Příklad základního vybarvení (256 barev)
69
Opět jen
256 barev:
70
Známe více než sto fraktálních rovnic a objevují se další cesty a možnosti.
Př. NEWTONOVA METODA TEČEN JAKO FRAKTÁLNÍ ROVNICE ( ?! )
y (x) = f (x) + f `(x k) ( x - x k )
x k+1 = x k - f (x k ) / f `(x k )
Př 1:
f (z) = z 4
- 1 => kořeny +1, -1, +i, -i
z k+1 = ( 4 z k
3
+ 1 ) / ( 3 z k
4
)
Př 2: f (z) = z 5
- 1
z 0 , z 1 , z 2 , ....
Správná startovací hodnota ?
Podobně další výrazy:
z k+1 =  sin z k
n
, z .......... komplexní čísla
z k+1 =  (1 - z k ) 2
n .......... reálné číslo
71
Hry P. Bourkeho:
72
Inverzní výpočet Juliovy množiny (Inverse Iteration Method )
Dopředný výpočet z = z2
+ c. Připomeňme: z a c jsou komplexní čísla
Inverzní výpočet : iterace z =  (z - c).
Program startuje z pevného bodu výrazu F(z) = z2
+ c
z =1/2  (1/4 - c).
Poznámka: Odmocnina odpovídá obecnému zápisu (z - c) pro z =1/4.
Dostáváme dvě řešení, náhodně vybíráme jedno.
Úloha odpovídá IFS {ti, pi : i = 1,2 } t1 = +(z - c), t2 = - (z - c),
p1 = p2 = 0,5.
Body ,,skáčou" po hranici množiny s nestejnou hustotou,
řešení je pomalé. Př. |c | =konst.
Př. c = -1, i :
73
Př. Několik voleb (cr, ci), počet iterací n = 5 000
74
Př. Juliova množina počítaná inverzní metodou jako objekt 3D
Počet iterací 3 000 Počet iterací 20 000
Poznámka: Výpočet je často prováděn v polárních souřadnicích.
75 76
b) Juliovy množiny kvaternionů
Poznámka: 3D objekty získáme projekcí ze 4D, obraz generujeme pomocí metody Ray Casting
(paměti hloubky). Vhodné umístění zdroje světla může zjednodušit výpočet normál pro stínování.
77
Připomeňme: Analogicky bude platit |z|2
= a2
+ bi2
+ cj2
+ dk2
Výpočet subprostoru kvaternionu (3D objektu) bude respektovat zvolené natočení ,,scény":
Př. 1. Expanze Juliovy množiny f(z) = z2
­ 1 a její 3D obraz po rotaci kolem reálné osy
78
Př. 2. Oblastí planární Juliovy množiny v 3D subprostoru kvaternionu.
F(z) = z2
+ 0.2809 ­0.53i
Jiná pozice téže množiny:
79
Kvaterniony Juliovy množiny často počítáme inverzně a průsečík paprsku s plochou iterujeme).
Postup A. Nortona:
80
Kvaterniony A. Nortona
81
Zobrazení kvaternionů metodou Ray Casting (QUAT)
82
Pseudofraktály 3D (nedeterministické!)
Metoda přesouvání středního bodu (MPD)
83
Efekt parametru H:
84
Metoda MPD aplikovaná na trojúhelník ve 2D
85
Metoda MPD aplikovaná na trojúhelník ve 3D
varianty umístění středního bodu
ve čtyřúhelníkové síti:
výsledek
86
Konečný výsledek