Hlavní navigace

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

Pavel Tišnovský 26. 10. 2005

Dnešním dnem začíná na Root.cz nový seriál, ve kterém se budeme věnovat problematice fraktálů a fraktální geometrii spolu s jejich praktickou implementací, především v počítačové grafice a z ní vycházejících aplikací. S fraktály do jisté míry souvisí i teorie chaosu a chaotické systémy - i této problematice se budeme v pozdějších dílech věnovat.

Obsah

1. Úvodní informace
2. První stopy fraktální geometrie
3. Benoit B. Mandelbrot
4. Fraktální geometrie jako vědecký obor
5. Geometricky hladké útvary
6. Nekonečně členité útvary
7. Literatura a odkazy
8. Obsah dalšího pokračování tohoto seriálu

1. Úvodní informace

Jak již bylo zmíněno v perexu, je tento seriál zaměřen především na využití fraktálů v počítačové grafice. Mimo popisu programových metod pro generování fraktálních obrazců se také budeme zabývat dynamickými systémy a nelineárními systémy, jelikož při jejich teoretickém studiu i praktické aplikaci (a to nejenom v počítačové grafice) lze využít mnoho poznatků získaných pomocí fraktálů a fraktální geometrie. Okrajově se také zmíníme o takzvané teorii chaosu, která s fraktály v některých oblastech úzce souvisí.

V první části tohoto seriálu se budeme zabývat převážně základními pojmy z oboru fraktální geometrie. Bude zde naznačeno, jakým způsobem se mohou fraktály vytvářet a jak je možné zjistit, zda je daný geometrický či matematický objekt skutečně fraktálem. V další části budou uvedeny vybrané základní typy běžně používaných fraktálů. Jsou zde také vyjmenovány některé vědní i čistě praktické disciplíny, ve kterých se v dnešní době fraktálů a fraktální geometrie využívá.

Fraktály 1 - 1

Obrázek 1: Pravidelný plošný fraktální obrazec vytvořený rekurzivním dělením

Fraktály 1 - 2

Obrázek 2: Fraktál vypočtený v komplexní rovině

2. První stopy fraktální geometrie

Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line.

Fraktální geometrie je samostatná a dnes již poměrně rozsáhlá vědní disciplína zasahující do mnoha dalších oborů, která je intenzivně rozvíjena zhruba od šedesátých let minulého století. Za jejího zakladatele je dnes považován vědec polského původu a objevitel fraktálů Benoit B. Mandelbrot, který jako první matematicky definoval pojem fraktál (fractal). O definici fraktálu se sice vědci a umělci do jisté míry pokoušeli i před B. B. Mandelbrotem (fraktály jsou ostatně odnedávna patrné prakticky na každém kroku v okolní živé i neživé přírodě), jejich popis však byl velmi vágní a neúplný, proto je B. B. Mandelbrotovi právem připisováno prvenství. Pojďme si nyní říci něco o práci tohoto velmi zajímavého a talentovaného věd­ce.

Fraktály 1 - 3

Obrázek 3: Ukázka dalšího fraktálu v komplexní rovině

3. Benoit B. Mandelbrot

Benoit B. Mandelbrot (v některých pramenech také psáno jako Mandelbrojt) se narodil 20. ledna 1924 ve Varšavě. I když to byl rodilý Polák, žil od svých dvanácti let ve Francii. Mandelbrot studoval pod vedením Gastona Julii a především Paula Lévyho. Práce Gastona Julii, po němž byly později pojmenovány Juliovy množiny, by byla bez Mandelbrotovy rozsáhlé publikační činnosti pravděpodobně zapomenuta. Mandelbrot pracoval mimo jiné i ve firmě IBM (ve výzkumném a vývojovém oddělení, ale ne jako programátor), kde studoval rozložení chyb vznikajících na přenosové lince, tj. stavu, kdy jsou na začátku a konci jednobitové přenosové linky bity s inverzní hodnotou. Na první pohled náhodné rozložení chyb ve skutečnosti vykazovalo určité pravidelnosti a symetričnosti, protože se chyby vyskytovaly vždy v určitých shlucích, a to do značné míry nezávisle na časovém měřítku (při změně časového měřítka se objevovaly stále stejné vzory).

Podobnou symetrii a nezávislost na časovém měřítku objevil Mandelbrot i při studiu vývoje cen na burze, což bylo jistě překvapivé (a určitě to namíchlo spoustu „burzovních expertů“). Nalezení závislosti mezi těmito značně vzdálenými tématy Mandelbrota podnítilo k dalšímu výzkumu, při kterém mimo jiné popsal některé fraktální objekty (tak však byly pojmenovány později), jež se vyskytují v živé i neživé přírodě, při přenosech signálů po datových kanálech, v rozložení hmoty ve vesmíru aj. V tomto období také vznikly publikace „Fraktály“ (tato kniha vyšla před dvěma roky i v českém překladu) a především slavná „Fraktální geometrie přírody“ (The Fractal Geometry of Nature). V těchto publikacích Mandelbrot použil styl výkladu, který mu mnoho jeho kolegů matematiků vyčítalo (a někteří mu snad dodnes neodpustili :-).

Autor totiž bez dalších podrobností popsal a především porovnal mnoho – na první pohled vzájemně nesouvisejících – jevů a při výkladu si místo složitých vzorečků a vztahů pomáhal zejména geometrií a vytvářením analogií k podobným jevům či objektům. To se do značné míry liší od většiny rigorózních matematických publikací, které používají ustálený styl „definice, tvrzení, věta, důkaz, definice, tvrzení, věta, důkaz …“. Je pravda, že autor zde nehrál – alespoň z hlediska matematiků – férovou hru, protože doslova chrlil jedno tvrzení za druhým a přesné definice a důkazy (tj. onu mravenčí a mnohdy nezáživnou práci) přenechal jiným. Na druhou stranu mu to umožnilo věnovat svůj čas a nesporný talent vidět mnoho věcí v souvislosti zajímavému a přínosnému výzkumu.

Mandelbrot v průběhu své vědecké kariéry dosáhl titulu Sterling Proffesor, což je nejvyšší akademické ocenění na Yalské universitě. Toto ocenění bylo pojmenováno po Johnu Williamu Sterlingovi.

Benoit B. Mandelbrot je v dnešní době známý i mimo oblast matematiky. Byl po něm totiž pojmenován jeden z nejznámějších fraktálů – Mandelbrotova množina. Tímto jménem byl dynamický fraktál ležící v komplexní rovině (poprvé prezentovaný v roce 1979) pojmenován na počátku osmdesátých let minulého století Johnem Hubbardem. Ve skutečnosti však Mandelbrot nebyl první, kdo tento fraktál pomocí počítače vykreslil, jako první ho však publikoval.

Fraktály 1 - 4

Obrázek 4: Celkový pohled na Mandelbrotovu množinu

Fraktály 1 - 5

Obrázek 5: Detail Mandelbrotovy množiny

4. Fraktální geometrie jako vědecký obor

Jak již bylo řečeno v předchozí kapitole, i před zavedením pojmu fraktálu a fraktální geometrie docházelo k prozkoumávání vlastností geometrických útvarů, které dnes nazýváme fraktály. Jedná se například o známou sněhovou vločku Helge von Kocha nebo Sierpinského kobereček, které byly zkoumány a popsány o mnoho desítek let dříve, než se těmito zajímavými objekty začal zabývat Mandelbrot. Nikdo z vědců zkoumajících tyto útvary však fraktál matematicky obecně nedefinoval, ostatně i Mandelbrotova definice nepatří mezi čistě rigorózní matematické definice, což mu bylo často vyčítáno (viz předchozí kapitola).

Protože velká část fraktálů je využívána v počítačové grafice a fraktály lze nejlépe (tj. nejvíce intuitivně) popsat jako geometrické objekty, lze fraktál nejjednodušeji definovat jako nekonečně členitý útvar (některé fraktály lze ovšem definovat i odlišnými a značně přesnějšími způsoby – nutno však konstatovat, že všeobecně platná definice fraktálu prozatím neexistuje). Pro vysvětlení pojmu nekonečně členitý útvar musíme definovat pojem geometricky hladký útvar, který je jistým způsobem pravým opakem útvaru nekonečně členitého.

Fraktály 1 - 6

Obrázek 6: Vizualizace jednoduchého dynamického systému vykazujícího fraktální strukturu

5. Geometricky hladké útvary

Běžná tělesa a především umělé útvary v našem okolí se dají popsat nebo zobrazit jako jistý konečný počet parametrů, které tato tělesa z hlediska jejich tvaru plně charakterizují. Pro základní geometrické tvary, například pro krychli, kouli, válec, prstenec, úsečku, přímku či rovinu, známe vzorce a vztahy, ze kterých můžeme vypočítat jejich geometrické charakteristiky, například délku, plochu nebo objem. Jako samozřejmost přitom bereme to, že výsledek tohoto výpočtu je vždy stejný, i když výpočty provádíme v libovolných jednotkách. Je například nepodstatné, zda je poloměr koule zadaný v milimetrech či kilometrech; objem koule či její povrch vyjde vždy stejný (samozřejmě při přepočtu na stejné jednotky).

Výše zmíněné geometricky orientované veličiny (objem, povrch atd.) můžeme spočítat i pro poněkud složitější útvary, které vzniknou kombinací konečného počtu elementárních útvarů. Lze třeba spočítat délku Bézierovy křivky (i když se v tomto případě jedná o poněkud složitý výpočet) nebo objem osově symetrické láhve vzniklé rotací této křivky okolo osy rotace.

Výsledky těchto výpočtů jsou opět zcela nezávislé na použitých jednotkách. Všechny uvedené útvary mají jednu společnou vlastnost. Každému útvaru totiž můžeme přiřadit jisté celé číslo, které nazýváme počet rozměrů nebo také dimenze daného útvaru. Výklad pojmu dimenze bude uveden až po objasnění pojmu nekonečně členitý útvar.

Fraktály 1 - 7

Obrázek 7: Odlišný typ dynamického systému

6. Nekonečně členité útvary

Dnes již klasickým příkladem nekonečně členitého útvaru je břeh nějaké řeky či potoka nebo pobřeží nějakého libovolného ostrova. V obou případech se jedná o hranici mezi vodní hladinou a pevninou, pro zjednodušení můžeme předpokládat, že je hladina klidná a představuje dokonalou plochu (na zeměkouli spíše plochu kulového vrchlíku). Můžeme si zkusit vypočítat délku pobřeží tohoto ostrova. Je-li linie pobřeží zobrazena na nějaké mapě nebo na leteckém snímku, má tato mapa určité měřítko, například 1: 1 000 000. Pomocí kružítka můžeme (krokováním) délku pobřeží přibližně zjistit a přepočítat na kilometry, protože známe předem zadané měřítko mapy. Jestliže bude kružítko roztaženo tak, aby vzdálenost mezi jeho hroty byla rovna jednomu centimetru a měřítko mapy je rovno zmíněným 1 : 1 000 000, pak to znamená, že při jednom kroku kružítka se na mapě posuneme o 1 000 000 centimetrů, což po přepočtu dává deset kilometrů v reálném terénu.

Dostaneme-li však k dispozici přesnější mapu, která má měřítko například 1: 10 000 a budeme-li opět měřit délku toho samého úseku pobřeží, dostaneme délku odlišnou – větší. To znamená, že se spolu se změnou měřítka změnila délka obrazu toho samého objektu, v našem případě pobřeží. Důvod se zdá být jasný – při zmenšení měřítka vidíme i detaily pobřeží, které nebyly na mapě s větším měřítkem viditelné. Samozřejmě, že při cestě pěšky okolo ostrova bude délka ještě větší, ovšem za předpokladu, že půjdeme přesně na hranici pobřeží a nebudeme si cestu zkracovat. Se zmenšujícím se měřítkem by délka dále rostla, a při délce měření blížící se limitně k nule, by délka rostla dokonce až do nekonečných hodnot. Z toho vyplývá zajímavý a až do nedávné doby neznámý (či spíše ignorovaný) fakt, že ostrov o konečné plošenekonečnou délku pobřeží.

Výše uvedený příklad není pouhou myšlenkovou abstrakcí, ale vyskytl se v reálném světě při měření obvodu ostrova Korsiky. Čím více se zeměměřiči snažili zvýšit přesnost tohoto měření, tím větší byla naměřená délka. Tato skutečnost nebyla dlouhou dobu brána v úvahu, a proto se délky státních hranic po přesnějším měření lišily až o násobky očekávaných délek. V dnešní době se v moderních atlasech délka hranic většinou ani neuvádí, zejména pokud jsou hranice či jejich části určeny přírodními hranicemi – řekami, pohořím, údolím atd. (při pohledu na světovou mapu – například na některé africké země – však můžeme nalézt oblasti, kde jsou hranice vymezeny přesně, například rovnoběžkou nebo poledníkem – i zde však může délka neočekávaně narůst, zejména díky nerovnostem terénu).

Obvod ostrova Korsiky měřil Richardson, který také jako první zjistil, že obvod ostrova je závislý na délce tyče (či jiného měřidla), kterou se měří. Richardson také empiricky, bez dalších matematických důkazů odvodil následující vztah:

K=N(ε)εD

kde K značí délku celkového počtu N(ε) úseček nutných k aproximaci (tj. nejtěsnějšímu pokrytí) dané křivky. Délka pobřeží se ukázala být závislá na konstantě D, jejíž význam si však Richardson nedokázal vysvětlit. Až Benoit B. Mandelbrot dokázal souvislost této konstanty a Hausdorffovy dimenze. Bližší informace budou uvedeny v další části tohoto seriálu, který pojednává o dimenzích.

Také délka řek se musí měřit odlišným způsobem, než jaký byl běžně používán. Můžeme změřit délku řeky tak, že postupně změříme délku pravého a levého břehu a výslednou vzdálenost zprůměrujeme. Jak však již víme, v tomto případě by se při velmi přesném měření délka řek pohybovala v astronomických jednotkách a limitně by se dokonce blížila nekonečnu. Intuice nám ovšem říká, že délka řeky nemůže být nekonečná, protože jestliže na řece poplujeme konstantní nenulovou rychlostí, určitě doplujeme na konec řeky v konečném čase. Je tedy nutné měřit například po pevně daných krocích, nebo přímo v toku řeky (třeba v ose toku).

Plocha některých objektů nacházejících se v okolní přírodě, které mají konečný objem, může být nekonečná (nebo až o několik řádů větší, než bychom na první pohled očekávali). Například povrch jakékoli reálné planety je teoreticky nekonečný. Zdálky vypadá planeta jako dokonalá koule (či rotační elipsoid). Při určitém přiblížení rozeznáme vrcholky hor a velká údolí. Při dalším přiblížení zjistíme, že každá hora je velmi členitá a její plocha je obdobně členitá jako povrch celé planety, ovšem v jiných měřítkách. Každý kámen na planetě potom při zvětšení vypadá jako celá hora, ale je mnohem menší. S touto změnou měřítka můžeme pokračovat dále až prakticky do subatomárních struktur. Obrovská je i plocha plic či lidského mozku při relativně malém objemu.

Ve všech těchto případech jde o praktickou aplikaci fraktálů v přírodě, kde v těchto případech platí princip úspornosti.

Fraktály 1 - 8

Obrázek 8: Poměrně nový typ fraktálu – Flame

7. Literatura a odkazy

  1. Barnsley Michael: „Fractals Everywhere“,
    Academic Press Inc., 1988, ISBN 0–12–079062–9
  2. Barnsley Michael, Devaney R. L., Mandelbrot Benoit B., Peitgenn Heinz-Otto, Saupe Dietmar, Voss Richard: „The Science of Fractal Images“,
    Springer-Verlag, New York, 1988
  3. Mandelbrot Benoit B.: „The Fractal Geometry of Nature“,
    W. H. Freeman, New York; San Francisco, 1982, ISBN 0–7167–1186–9
  4. Peitgen Heinz-Otto, Richter Peter: „The Beauty of Fractals“,
    Springer-Verlag, New York, 1986, ISBN 0–387–15851–0
  5. Žára J., Beneš B., Felkel P.: „Moderní počítačová grafika“,
    Computer Press, Praha, 1998, ISBN 80–7226–049–9
  6. Žára J., Limpouch A., Beneš B., Werner T.: „Počítačová grafika – principy a algoritmy“,
    Grada, 1992

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

V dalším pokračování tohoto seriálu si vysvětlíme spojitost mezi dimenzí, fraktály a soběpodobností.

Našli jste v článku chybu?

26. 10. 2005 21:59

Ono je skoro jedno, jak se to pobrezi pro potreby mereni definuje. Dejme tomu, ze to muze byt hranice vznikla prumetem hmoty ostrova s rovinou z=0 (pokud povazujeme Zemi za placku) nebo prumetem hmoty ostrova s plochou koule o polomeru 6373 km.

Tady dokonce nejde ani o to, ze se meri zrovna pobrezi (taky hladina kolisa, nepocitaje v to vlny), muze to byt treba cesta mezi dvema libovolnymi body na zemi. Pobrezi ostrova jsem zminil hlavne z historickych duvodu - prave na nem Richardson objevil tu…

26. 10. 2005 12:46

Jasne, klidne muzou byt GPL, akorat nevim, jestli musim v preambuli kazdeho desetiradkoveho programu psat celou GPL licenci :-)))

S tim fraktalnim pluginem je to pravda, osobne to vsak resim po Unixovsku - fraktal vygeneruji specializovanym programem (FractInt, XaoS, Quat, moje vytvorky, ...) a potom to prenesu no GIMPu.

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

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

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

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

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

Podnikatelům dorazí varování od BSA

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

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

Jsou čajové sáčky toxické?

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

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

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

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

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

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

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

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie