Jana Dannhoferová Ústav informatiky, PEF MZLU

Počítačová grafika

Fraktál • Fraktální geometrie se zabývá nepravidelností! • s názvem přišel matematik B. Mandelbrot kolem roku 1980 (fractus – frangere – rozlámat, vytvořit nepravidelné úlomky)

• 1977: How long is the coast of Great Britain • vlastnosti: • vizuální modelování přírodních objektů • tvarová komplikovanost a nepravidelnost objektů • teorie chaosu • tvarová soběpodobnost nezávislá na měřítku • uplatnění: matematika, fyzika, výtvarná informatika, počítačové hry apod.

Fraktální geometrie Jana Dannhoferová

([email protected])

Ústav informatiky, PEF MZLU 2

© J. Dannhoferová, Počítačová grafika

Fraktál

Fraktál

• Fraktál = jakýkoliv geometricky nepravidelný útvar, ze kterého vznikne po rozdělení v ideálním případě několik soběpodobných kopií původního celku • matematická definice fraktálu dosud nebyla podána • nejvýstižnější – Mandelbrot (1977): „Fraktál je množina, jejíž hodnota Hausdorffovy-Besicovichovy dimenze přesahuje hodnotu dimenze topologické.“ • DT – topologická dimenze určuje klasický geometrický rozměr tělesa (např. bod: DT=0, přímka: DT=1, plocha: DT=2, prostorový objekt: DT=3)

• Haus.-Bes. dimenze D (tzv. fraktální dimenze) určuje míru nepravidelnosti tělesa z = z2 + c 3


Historie


4

Lorenzův atraktor

• teorie chaosu + fraktální geometrie + počítače • práce s chaosem – prozkoumávání mnoha grafů spočítaných jednoduchými rovnicemi, zato s velkou přesností • Edward Lorenz (50. a 60. léta): • předpověď počasí • chování vodního kola (první slavný chaotický systém)


5


6

1

Lorenzův atraktor

Historie • teorie chaosu a dynamické systémy: • James Yorke • Steve Smale • Benoit Mandelbrot • šum na telefonních linkách IBM (podobnost mezi Cantorovým mračnem a šumem) • v přírodě existuje skrytý fraktální řád • otázky: Kolik dimenzí má klubko provázku? • Mandelbrotovy množiny (staly se symbolem všech fraktálů) • Michael Barnsley


7


8

Cantorova množina

IFS fraktály

• nebo také Cantorovo mračno • rozdělení úsečky na stejné části a opakování tohoto procesu

• iterační funkční systémy (nejjednodušší) • po nekonečně mnoho opakováních vznikne nekonečně mnoho bodů

• zlomková dimenze – míra nepravidelnosti objektu © J. Dannhoferová, Počítačová grafika

9

Barnsleyho kapradina


10

Barnsleyho kapradina

• zabýval se problémem, jak nalézt u neznámého fraktálu jeho matematické vyjádření (tzv. kolážová věta, fraktálový řád) • každý lístek kapradiny je téměř kopií sebe sama • původní útvar byl postupně doplňován dalšími útvary, které byly zmenšenou kopií původního (menší útvary byly pokládány tak, že mohly i překrývat původní objekt)


11


12

2

Algoritmy větvení

Kochova vločka • Helge von Kocha • trojúhelník, k jehož každé straně „přilepíme“ k prostřední třetině další trojúhleník o třetinu menší (tento postup pak budeme aplikovat i na tento trojúhelník)

• po mnoha opakováních vznikne křivka s několika zajímavými vlastnostmi, která nikdy neprotne sama sebe, neboť nové trojúhelníky jsou příliš malé • plocha zůstává na rozdíl od křivky konečná


13

Kochova vločka


14

Sierpinského trojúhelník • z trojúhelníka vyřízneme trojúhelník tvořený středními příčkami trojúhleníka původního a tento postup dále opakuje pro zbylé trojúhelníky


15

16

Mengerova houba

Sierpinského koberec • vyřezávání ze čtverce



• obdobné operace na trojrozměrných objektech • trojrozměrná mřížka s nekonečně velkým povrchem, ale nekonečně malým objemem

17


18

3

Fraktální dimenze

Fraktální dimenze • D – míra nepravidelnosti útvaru • fraktály: fraktální dimenze je větší než topologická dimenze • ne-fraktály: zmenšováním délky měřidla se přibližuje délka objektu (obvod) k nějaké limitní hodnotě (u fraktálů to neplatí, délka se neustále zvětšuje – tzv. Richardsonův efekt) • příklad: „rozdělit úsečku o délce jedné jednotky na pět stejných dílů“

• N.r1=1

• N.r2=1

• N.r3=1

• délka jednoho dílku: r=1/5 • N je počet dílků, obecně: r=1/N

„rozdělit čtverec na dvacet pět stejných dílů“ • délka jednoho dílku: r=1/5 • po zobecnění: r=1/N1/2

• N x 1D kopie v měřítku r =1/N © J. Dannhoferová, Počítačová grafika

19


Fraktální dimenze

20

Juliova množina

• obecný zápis: r = 1 / N1/D (D je dimenze objektu)

• D můžeme vyjádřit jako: log r = - log N1/D • celkově tedy dostáváme: D = log N / log (1/r) (kde N označujeme faktor změny délky a 1/r faktor změny měřítka)

• Gaston Julia (práce okolo r. 1915) + Pierre Fatou • skupina polynomických fraktálů • chování komplexního polynomu při iteraci (z4+z3/(z-1)+z2/(z3+4z2+5)+c) • v současné době je Juliova množina definována jako množina bodů z=x+iy v komplexní rovině

• příklad: použití vzorce na Kochovu křivku • při každé transformaci je r=1/3 své původní hodnoty • počet samopodobných úseků je N=4 • dosadíme: D = log 4 / log 3 = 1.2618


21


22

Juliova množina

Juliova množina • metoda:

• zvolíme jedno náhodné komplexní čislo c, které bude charakterizovat množinu • pro každý bod komplexní roviny z zjistíme, zda neustálým mocněním z a přičítáním c konverguje výsledek k nule či ne. • pokud k nule konverguje, bod patří do Juliovy množiny • v praxi: zkoumané číslo umocníme a přičteme k němu konstantu c – pokud je výsledek větší než 2, bod nepatří do množiny, pokud je menší, zopakujeme výpočet – jestliže ani po několika iteracích nepřesáhne výsledek hodnotu 2, bod patří do Juliovy množiny • aby byly Juliovy množiny zajímavější, zobrazují se barevně – barvu zvolíme podle počtu iterací potřebných ke zjištění, zda číslo je či není prvkem Juliovy množiny


23


24

4

Mandelborotova množina

Mandelborotova množina

• Benoit Mandelbrot • pokoušel se zobecnit, sjednotit a popsat Juliovy množiny • 1979: objevil jakýsi „katalog“ Juliových množin (tím katalogem byla další množina v komplexní rovině, která popisovala v každém svém bodě určitou Juliovu množinu)

• tato množina se nazývá dle svého objevitele Mandelbrotova • tyto dvě množiny jsou spolu propojeny tak, že každý bod v Mandelbrotově množině určuje vzhled množiny Juliovy, která ke zvolenému bodu patří

25


• idea: • zkoumáme pro každý bod komplexní roviny, zda jeho neustálým umocňováním se vzdaluje od nuly a blíží k nekonečnu • na každý bod několikrát aplikujeme rovnici zn = zn-12 + c • výpočet: • vezmeme komplexní číslo a přičteme k němu jeho druhou mocninu • výsledek zase umocníme a přičteme k němu původní číslo • tento proces opakujeme, dokud výsledek výpočtu nepřesáhne hodnotu 2 • pokud ji přesáhne, výpočet končí, pokud ne, bod do množiny patří 26


Newton

Nástroje

• John Hubbard • Newtonova metoda řešení polynomů (postupné zpřesňování výsledku)

• zkoumal jednoduchou rovnici x3 - 1 = 0

(v oboru reálných čísel má jen jedno řešení, v komplexním oboru jsou řešení ovšem celkem tři)

• • • •

FractInt Fractal Explorer ChaosPro Ultra Fractal

• tato rovnice se stala základem pro fraktál s označením Newton


27

Hénonův atraktor

28

King’s dream

• vznikne natahováním a ohýbáním fázového prostoru • při postupném zjemňování fraktálu se objevují nové a nové detaily (nekonečně mnoho párů křivek vedle sebe) • xn=yn-1+1–(1.4(xn-1)1/2), yn=0.3xn-1



29

• vymyslel jej Clifford Pickover (kniha: Chaos in Wonderland) • xn=sin(yn-1b)+c sin(xn-1b) • yn=sin(xn-1a)+d sin(yn-1 a)


30

5

Literatura a zdroje

Přírodní fraktály • útvary vzniklé přírodní oscilací, turbulencí, chemickou reakcí

• Beneš, B., Felkel, P., Sochor, J., Žára, J. Moderní počítačová grafika. Computer Press: Brno, 2004. • Serba, J., Staudek, T., Žára, J. Výtvarná informatika. FI MU: Brno, 2003. • Sochor, J.: Počítačová grafika. FI MU: Brno, 2003.


31


32

6

Jana Dannhoferová Ústav informatiky, PEF MZLU

Recommend Documents