Hlavní navigace

Stochastické fraktály

Pavel Tišnovský

V dnešní části seriálu se začneme zaobírat poměrně velkou a námi prozatím opomíjenou skupinou fraktálů. Jedná se o stochastické fraktály, při jejichž vytváření hraje nezanedbatelnou úlohu náhoda. Jelikož mají tyto fraktály v počítačové grafice své nezastupitelné místo, budeme se jimi zabývat i v několika následujících částech tohoto seriálu.

Obsah

1. Úvodní informace o nepravidelných (náhodných, stochastických) fraktálech
   1.1 Simulace Brownova pohybu (Brownian Motion)
   1.2 Metoda přesouvání prostředního bodu (Midpoint Displacement Method)
   1.3 Spektrální syntéza (Spectral Synthesis)
2. Simulace difúze
3. Princip práce metody aplikace Brownova pohybu
4. Trajektorie Brownova pohybu
5. Skalární Brownův pohyb
6. Zlomkovitý Brownův pohyb
7. Literatura a odkazy na internetu
8. Obsah dalšího pokračování tohoto seriálu

1. Úvodní informace o nepravidelných (náhodných, stochastických) fraktálech

Rozsáhlou a v tomto seriálu až do dneška zcela opomíjenou skupinou fraktálů jsou nepravidelné neboli náhodné či také stochastické fraktály. Zatímco všechny předchozí skupiny (resp. typy) fraktálních útvarů byly v určitém smyslu měřítkově symetrické, tj. soběpodobné, nepravidelné fraktály vnáší při svém generování do algoritmu náhodu, tj. jsou „pouze“ soběpříbuzné, nikoli soběpodobné). Při praktické implementaci algoritmů na počítačích se však místo pravé náhody musíme spolehnout na pseudonáhodné generátory čísel – PRNG. Tento typ fraktálů také umožňuje zdaleka nejlepší popis přírodních objektů.

Zatímco při generování stromu klasickým L-systémem nebo IFS koláží dostaneme jako výsledek perfektně symetrický strom, je skutečnost už na první pohled zcela jiná. Strom rostoucí v přírodě má nepravidelné délky a tloušťky větví, úhel růstu větví také není vždy stejný, strom rostoucí v lese má jiný tvar než tentýž druh stromu rostoucí osamoceně apod. Z těchto důvodů je velmi vhodné zavést do generování fraktálů náhodu. Způsob, jakým se náhodnost bude podílet na procesu generování fraktálů, bude vždy určovat tvar fraktálu a současně i jeho Hausdorffovu dimenzi. Pro generování náhodných čísel se používá například gaussovský generátor nebo generátor bílého šumu, některé postupy však vyžadují odlišný PRNG.

Náhodné fraktály můžeme vytvářet více způsoby. První způsob spočívá v simulaci Brownova pohybu buď v ploše nebo v prostoru. Druhý způsob spočívá v použití metody přesouvání středního bodu a třetí způsob využívá spektrální syntézu. Pojďme si nyní v krátkosti jednotlivé metody tvorby stochastických fraktálů popsat:

1.1 Simulace Brownova pohybu (Brownian Motion)

Během simulace Brownova pohybu (známého z molekulární fyziky a postupně zkoumaného mnoha světoznámými vědci) se vytváří fraktální objekt, jehož Hausdorffova dimenze je úměrná absolutní velikosti změny při jednom iteračním kroku. Tato metoda se používá například při generování modelů tekoucích řek. Není příliš vhodná pro trojrozměrné objekty, a to ze stejného důvodu, jaký vedl k problémům u trojrozměrných systémů iterovaných funkcí IFS – vytvořený model se skládá z jednotlivých bodů a dnešní grafické akcelerátory mají s těmito entitami značné problémy, protože jsou optimalizovány na vykreslování trojúhelníků a dalších plošných entit. Existují však i specializované postupy a dokonce hardwarové prostředky zaměřené na vykreslování jednotlivých bodů či orientovaných plošek (surfelů) v prostoru.

fractals41_1

Obrázek 1: Ukázka stochastického fraktálu napodobujícího travinu či keřík, který vznikl aplikací algoritmu difúze (simulací Brownova pohybu)

1.2 Metoda přesouvání prostředního bodu (Midpoint Displacement Method)

Mezi typické metody generování stochastických fraktálů patří metoda přesouvání prostředního bodu, aplikovatelná jak na ploše, tak i v trojrozměrném prostoru. Tato metoda se velmi často používá v počítačové grafice k vygenerování a následné vizualizaci přírodní krajiny, povrchů vesmírných těles apod. Volbou maximální odchylky při posunu prostředního bodu je možné lze měnit celkový ráz krajiny od pouště přes pahorkatinu až po vysokohorskou krajinu. Maximální odchylka a průběh jejího klesání také určuje Hausdorffovu dimenzi vytvořeného modelu.

fractals41_2

Obrázek 2: Postupné vytváření a zjemňování modelu krajiny pomocí metody přesouvání prostředního bodu

1.3 Spektrální syntéza (Spectral Synthesis)

Další často používanou metodou je spektrální syntéza, která vychází z principu výpočtu Fourierovy řady. Metoda spočívá v tom, že náhodně vygenerujeme Fourierovy obrazy, které mají spektrální hustotu úměrnou zadané Hausdorffově dimenzi. Potom provedeme inverzní Fourierovu transformaci s těmito koeficienty. Výsledkem je fraktální objekt. Pomocí této metody lze generovat – podobně jako metodou předchozí – krajiny, hory či povrchy planet. Výhodou je, že lze přímo zadat požadovanou Hausdorffovu dimenzi výsledného objektu.

fractals41_3

Obrázek 3: Model krajiny vytvořený pomocí stochastických fraktálů

2. Simulace difúze

Po krátkém seznámení se základními typy stochastických fraktálů se budeme věnovat velmi zajímavé a přitom téměř nepoužívané metodě, pomocí které je možné vytvářet tvarově složité přírodní útvary, například modely stromů, keřů nebo trávy. Prostorové útvary, jež jsou vygenerované touto metodou, se vyznačují částečnou (statistickou) soběpodobností (tj. soběpříbuz­ností), velkou tvarovou složitostí a fraktální strukturou (jak jsem se již zmínil v několika předchozích částech tohoto seriálu, patří soběpodobnost mezi význačné vlastnosti fraktálních objektů). Pro zvýšení modelovacích schopností popisované metody difúze a rychlosti vytváření modelu zde také bude popsána zcela nová metoda návrhu omezujících podmínek, které je zapotřebí při generování prostorových útvarů dodržet. Pomocí omezujících podmínek lze měnit charakteristiku vytvářených těles ve větší části prostoru, zatímco změnou parametrů algoritmu difúze se mění jak celkový vzhled modelu, tak i lokální hustota a charakter vytvářených tvarů.

Výsledkem aplikace dále popsaných metod, postupů a algoritmů jsou plošné či prostorové modely přírodních útvarů, které jsou pro účely zobrazení složeny z orientovaných elementárních prvků plochy (surfelů) či neorientovaných bodů, jež se nachází v prostoru E3 (částice) nebo na ploše E2 (body, speciálně po diskretizaci do pravidelné bitmapy pixely). Z geometrického hlediska jsou tyto modely tvořeny stochastickými fraktály, jejichž fraktální dimenze se může pohybovat v rozmezí od nuly do tří. Na dalším obrázku je zobrazen plošný (rastrový) model traviny, který vznikl aplikací dále popsaného algoritmu difúze. Mezi nejzávažnější důvody, kvůli kterým není tato metoda při tvorbě modelů přírodních těles více používaná, patří především dvě skutečnosti:

  1. Prvním důvodem je fakt, že proces vytváření trojrozměrného modelu je sice algoritmicky jednoduchý, ale extrémně časově náročný, zejména v případě tvorby prostorového modelu. Velkou časovou složitost je však možné částečně zmenšit vhodným omezením prostoru pro nově vytvářené body. Bližší informace o omezujících podmínkách, které pro urychlení vytváření modelu navrhuji, budou podány v dalších odstavcích a pokračováních, stejně jako další možné modifikace algoritmu difúze.
  2. Druhý důvod spočívá ve vlastní formě vzniklého modelu. Jedná se totiž o množinu jednotlivých bodů či elementárních plošek bez vzájemných explicitních vazeb, které je značně obtížné až nemožné efektivně převést do polygonální hraniční reprezentace – převod je samozřejmě možný, ale výsledkem je velké množství malých trojúhelníčků, které se musí vykreslovat. Zde se ukazuje velká výhoda použití bodových primitiv (orientovaných surfelů a neorientovaných částic), neboť body vytvářené algoritmem difúze můžeme za tyto stavební prvky scény jednoduše zaměnit a žádné složité převody neprovádět.

fractals41_4

Obrázek 4: Další model keře vytvořený metodou simulace difúze

3. Princip práce metody aplikace Brownova pohybu

Princip práce této metody pro vytváření fraktálních objektů vychází ze simulace difúze, což je (velmi zjednodušeně řečeno) přírodní jev, při kterém jsou pevné, kapalné či plynné částečky jedné hmoty postupně roznášeny v jiné kapalné či plynné hmotě. Pohyb těchto částeček, který se nazývá Brownovým pohybem (Brownian Motion), vzniká vlivem náhodných nárazů molekul jedné hmoty a hmoty druhé – viz další ilustrační obrázek. Poprvé byl Brownův pohyb popsán jako pohyb mikroskopických částeček pylu ve vodě. Zdůvodnění fyzikální podstaty tohoto pohybu však bylo podáno až Einsteinem v roce 1905.

Základem pro studium různých rozšíření a zobecnění Brownova pohybu je takzvaný Weinerův skalární Brownův pohyb. Jedná se o gaussovskou náhodnou funkci B(t) ze skaláru t do skaláru B, pro kterou musí platit následující rovnost:

E(B(t)-B(0))2 = t2H

Kde pro Weinerův skalární Brownův pohyb navíc platí omezení, že H=1/2:

E(B(t)-B(0))2 = t2×1/2 = t

Vzhledem k tomu, že Weinerův skalární Brownův pohyb představuje pouze dále neredukovatelný základ teorie Brownova pohybu, je možné provést několik zobecnění, z nichž ty nejvýznamnější jsou popsány v následujícím seznamu:

  1. První zobecnění Weinerova skalárního Brownova pohybu do obecnějšího tvaru spočívá v náhradě původního skaláru B n-dimenzionálním vektorem či bodem (v souvislosti s Brownovým pohybem není zapotřebí rozlišovat mezi bodem a vektorem) B, jehož všechny souřadnice představují samostatné, na sobě nezávislé Brownovy pohyby.
  2. Druhé zobecnění, které je však vytvořeno nezávisle na zobecnění prvním, protože B je v tomto případě opět skalár, spočívá v náhradě původně konstantní hodnoty H=1/2 za hodnotu jinou. Nová hodnota však vždy musí ležet v rozsahu od 0 do 1. Toto zobecnění vede k popisu takzvaného zlomkovitého Brownova pohybu fBm, jehož základní vlastnosti budou popsány v následujících odstavcích.
  3. Třetí zobecnění Weinerova skalárního Brownova pohybu spočívá v náhradě skaláru t bodem P. V dalším textu budu beze ztráty obecnosti předpokládat, že se jedná o bod z E2 nebo E3, Brownův pohyb je však možné specifikovat v libovolném prostoru, nad kterým je definována metrika (tj. pojem vzdálenosti dvou bodů).

Z hlediska využití Brownova pohybu při simulaci difúze je důležité, že lze všechna tři výše popsaná zobecnění vzájemně kombinovat a vytvořit tak například Brownův pohyb, ve kterém je B vektorem v E2 nebo E3 a konstanta H může nabývat libovolné hodnoty od 0 do 1. Možné jsou i další kombinace výše zmíněných zobecnění Brownova pohybu.

V dalším textu se budu zabývat především Brownovým pohybem BH(t), který může být popsán následovně: pro každou dvojici časových okamžiků ti a ti+Δt>ti se definuje vektor přemístění bodu (v reálném světě se bezrozměrný hmotný bod stává částečkou hmoty s nenulovým objemem) jakožto vektor vi jdoucí od bodu P(ti) do bodu P(ti+Δt):

vi=P(ti+Δt) – P(ti)

Tento vektor musí splňovat následující tři podmínky:

  1. Směr i délka vektoru vi není závislá ani na počáteční poloze bodu P(ti) ani na polohách bodu P(t) v okamžicích předcházejících času ti. Zjednodušeně řečeno lze říci, že systém nemá „paměť“ svých předchozích vztahů.
  2. Vektor vi je izotropní, tj. jeho velikost je nezávislá na směru a orientaci.
  3. Délka vektoru vi je taková, že průmět vektoru (resp. množiny vektorů) na jakoukoli souřadnou osu splňuje gaussovské rozdělení.

fractals41_5

Obrázek 5: Středový fraktál vytvořený pomocí simulace difúze

4. Trajektorie Brownova pohybu

Trajektorii Brownova pohybu, resp. pohybu jednotlivých částeček hmoty, jejichž polohu v rovině E2 či prostoru E3 je možné změřit, můžeme schematicky znázornit lomenou čarou (polyčarou – polyline), která vznikne spojením vrcholů představujících polohu částeček – hmotných bodů – P(ti), jež jsou změřené v konstantních časových intervalech. Počet bodů P(t) a tím i tvar a přesnost lomené čáry však závisí na zvolené časové posloupnosti T={t0, t0+Δt, … t0+n×Δt}, zejména na počátečním čase t0 a časovém intervalu Δt.

Pokud by byly časové intervaly Δt mezi měřením poloh částeček příliš velké, vznikla by lomená čára s malým počtem bodů, která by pouze hrubě odpovídala skutečné trajektorii částečky. Pokud by naopak byly zvoleny menší časové intervaly, zvětšil by se počet bodů tvořících vrcholy lomené čáry a tím by se obraz trajektorie Brownova pohybu zjemnil a současně i zpřesnil. Zmenšování časových intervalů lze teoreticky provádět až k limitnímu případu:

ti-ti+Δt → 0

V takovém případě se lomená čára, jež znázorňuje trajektorii Brownova pohybu, rozpadne na křivku reprezentovanou nekonečným počtem bodů a délka trajektorie je v tomto (ryze teoretickém) případě nekonečná, což implikuje fraktální podstatu trajektorie Brownova pohybu. Prakticky se však částečky hmoty pohybují po trajektorii, jejíž délka je konečná, tj. existuje určité měřítko pohledu, při kterém by bylo možné nalézt části trajektorie reprezentované úsečkou či spojitou křivkou (ve skutečnosti se však spíše bude jednat o skoky).

fractals41_6

Obrázek 6: Brownův pohyb jedné částice

5. Skalární Brownův pohyb

Mezi nejjednodušší Brownův pohyb patří skalární Brownův pohyb, u kterého jsou výsledkem funkce BH(t) jednorozměrné body – skaláry. Tento Brownův pohyb je možné zobrazit pomocí grafu, na jehož horizontální osu jsou vynášeny časové okamžiky ti a na vertikální osu polohy jednorozměrných bodů v těchto okamžicích BH(ti). Ukázka skalárního Brownova pohybu je zobrazena na následujícím obrázku. Skalární Brownův pohyb lze zobecnit do n-rozměrů tak, že každá souřadnice bodů trajektorie bude generovaná vlastní funkcí Brownova pohybu, která je nezávislá na funkcích ostatních.

fractals41_7

Obrázek 7: Skalární Brownův pohyb

6. Zlomkovitý Brownův pohyb

Zlomkovitý Brownův pohyb fBH(t) vzniká modifikací skalárního Brownova pohybu jeho zjemněním, čímž se ve všech měřítkách zmenšuje jeho nepravidelnost. Intenzita tohoto zjemnění, a tudíž i perzistence úrovní, závisí na jediném parametru HЄ(0,1). Hodnota H=1/2 je dohodou stanovena tak, že představuje nemodifikovaný Brownův pohyb, u kterého žádné zjemnění (či naopak zesílení) nepravidelnosti neexistuje – viz též předchozí rovnice. Perzistence úrovní vzrůstá s tím, jak hodnota H roste od 1/2 do 1, pro H jdoucí k nule perzistence úrovní naopak klesá. Dále platí důležité tvrzení, že fraktální dimenze zlomkovitého Brownova pohybu D odpovídá hodnotě 1/H. Pro nemodifikovaný skalární Brownův pohyb s H=1/2 tedy platí následující vztah:

D=1/H=1/(1/2)=2

Jelikož H je vždy menší než 1, musí nutně platit D>1, vždy se tedy jedná o spojitou křivku, nikoli o izolované body. Pro 0<H<1/2 se trajektorie Brownova pohybu „zamotává“ (jednotlivé body se překrývají) a její fraktální dimenze je větší než 2, tedy větší než topologická dimenze plochy E2!

fractals41_8

Obrázek 8: Stopa pohybu částice provádějící zlomkovitý Brownův pohyb

7. Literatura a odkazy na internetu

  1. Barnsley Michael, Devaney R. L., Mandelbrot Benoit B., Peitgenn Heinz-Otto, Saupe Dietmar, Voss Richard: <i>The Science of Fractal Images</i>,
    Springer-Verlag, New York, 1988
  2. Mandelbrot Benoit B.: <i>The Fractal Geometry of Nature</i>,
    W. H. Freeman, New York; San Francisco, 1982, ISBN 0–7167–1186–9
  3. Wegner Timothy, Peterson Mark: <i>Fractal Creations, First Edition</i>,
    The Waite Group Press, 1991
  4. Wegner Timothy, Tyler Bert: <i>Fractal Creations, Second Edition</i>,
    The Waite Group Press, 1993
  5. Wegner Timothy, Tyler Bert, Peterson Mark, Branderhorst Pierer: <i>Fractals for Windows</i>,
    The Waite Group Press, 1992
  6. Žára J., Beneš B., Felkel P.: <i>Moderní počítačová grafika</i>,
    Computer Press, Praha, 1998, ISBN 80–7226–049–9
  7. Žára J., Limpouch A., Beneš B., Werner T.: <i>Počítačová grafika &#8211; principy a algoritmy</i>,
    Grada, 1992

fractals41_9

Obrázek 9: „Plasma“ vytvořená metodou přesouvání prostředního bodu

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

V následujícím pokračování tohoto seriálu si popíšeme metodu pro simulaci difúze, která je založená na heuristice. Také si popíšeme některé způsoby urychlení celé simulace a její následné využití pro vytváření plošných i trojrozměrných modelů travin a keřů. Všechny popisované postupy budou samozřejmě implementované v demonstračních příkladech.

Našli jste v článku chybu?

29. 8. 2006 0:27

su - \mathfrak{M}&#294;&#274;&#458;MARCHON (neregistrovaný)
K Einsteinovi a chybe: fyzika je neuplna teoria a Godelova veta o neuplnosti je svina ;-) Sam Godel mal svoj model vesmiru, kde sa cas cyklil (dalo sa vratit v case idenim dopredu), podmienka bola 'specialny druh rotovania galaxii'. Vyhovovalo to Maxwellovym rovniciam a vsetkej tej srande okolo. Co AFAIK nikto nevyvratil, ale ani nepotvrdil. Jedna spominana moznost bola, ze sice rotuju tak ako to hovoril Godel, len ludia to za cas svojej existencie nemali sancu zmerat.

BTW: hadajte asi,…

29. 8. 2006 0:24

su - \mathfrak{M}&#294;&#274;&#458;MARCHON (neregistrovaný)
Heh :-)

Mozme povedat, ze hmotna castica konverguje k rychlosti svetla. Co by malo za nasledok, ze by sa vsetko blizilo nekonecnej hmotnosti. Otazka je: a neblizi sa? Supernovy napr...

Druha moznost je dvojita podstata castic: casticova a vlnova. Preco by sa castica iduca blizko rychlosti svetla nemohla premenit na energiu? Nie som fyzik, ale v knihe 'Cestovani casem v Einsteinove vesmiru' je to mozne - uvadza sa tam, ze akonahle sa hmotny objekt velmi priblizuje rychlosti sveta, tak z…



Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

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

Recenze Westworld: zavraždit a...

Podnikatel.cz: Změny v cestovních náhradách 2017

Změny v cestovních náhradách 2017

DigiZone.cz: TV Philips a Android verze 6.0

TV Philips a Android verze 6.0

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

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

Jsou čajové sáčky toxické?

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

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

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

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

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

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

Na ucho teplý, nebo studený obklad?

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

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

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

Spor o mortadelu: podle Lidlu falšovaná nebyla

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

Jak vymáhat výživné zadarmo?

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

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

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

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

Co všechno ovlivňuje ženskou plodnost?

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

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