Hlavní navigace

Stochastické fraktály - simulace difúze

15. 8. 2006
Doba čtení: 12 minut

Sdílet

V dnešní části 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.

Obsah

1. Simulace difúze založená na heuristice
2. Popis metody simulace difúze založené na heuristice
3. Algoritmus simulace difúze
4. Urychlení metody simulace difúze
5. Demonstrační příklad – simulace difúze
6. Obsah dalšího pokračování tohoto seriálu

1. Simulace difúze založená na heuristice

V předchozí části tohoto seriálu jsme si stručně vyjmenovali základní typy stochastických fraktálů. V dnešní části se zaměříme na popis metody simulace difúze, pomocí které je možné generovat velké množství zajímavě vypadajících obrázků s fraktální strukturou.

Simulaci difúze je možné založit na náhodném pohybu částic v omezeném či neomezeném prostoru. Jelikož však výsledkem simulace nemá být zobrazení trajektorií částic hmoty, jak je tomu v reálném světě, ale plošný či trojrozměrný model přírodního objektu, je nutné tuto simulační metodu poněkud modifikovat a rozšířit. Modifikace spočívá v postupném vytváření pevných bodů ležících v rovině E2 či prostoru E3, na nichž postupně „vyrůstají“ výčnělky tvořené z řady dalších bodů (či částic v prostoru). Body, které tvoří tyto výčnělky jsou, stejně jako body dříve vytvořené, nepohyblivé. Pevné body (částice – oba pojmy budu v dalším textu beze ztráty obecnosti zaměňovat) lze ke vznikajícímu fraktálnímu objektu přidávat dvěma způsoby:

  • Částice hmoty se vytvoří na náhodném místě a dále se simuluje její pohyb v prostoru, který byl znázorněn v předchozí části tohoto seriálu. Po doteku pohybující se částice a stávajícího fraktálu je částice k fraktálu připojena a generuje se další částice. Tento postup, který plně vychází z principů Brownova pohybu, bude podrobněji popsán v následujících kapitolách. Zde pouze předešlu, že výsledkem této metody jsou korektnější modely, ovšem za cenu větší časové náročnosti celého výpočtu.
  • Částice hmoty se postupně vytváří na náhodných místech, ale nepohybují se. Pokud se nově vygenerovaná částice stávajícího fraktálu dotkne, je k němu připojena; v opačném případě zanikne. Tento postup není v plném souladu s principem Brownova pohybu, ale závisí na stanovené heuristice: postupným vytvářením nových částic na náhodných místech se aproximuje trajektorie jedné částice, která se pohybuje Brownovým pohybem. Nejsou však zjištěny všechny body na trajektorii, ale pouze body zjištěné v určitých časových intervalech. Není tedy zaručeno, že se zjistí veškeré dotyky trajektorie částice se vznikajícím fraktálem, to je však částečně kompenzováno větším množstvím generovaných částic.

fractals42_1

Obrázek 1: Obrázek difúze, při kterém generování začalo z pouhého jednoho bodu umístěného uprostřed obrázku

2. Popis metody simulace difúze založené na heuristice

V dalším textu bude popsaná druhá výše uvedená metoda založená na heuristice. Postup při aplikaci metody simulace difúze, založený na heuristice, je možné slovně popsat následovně:

  1. Nejdříve se v předem určeném prostoru vygeneruje jedna částice či skupina částic nebo surfelů, které představují základ pro další růst fraktálního útvaru. Vzhledem k účinku takto vytvořených bodů na fraktální objekt budu tyto body v dalším textu nazývat semínkem – seed. Volba pozice těchto částic má vliv na celkový tvar výsledného fraktálu, neboť právě na těchto částicích se tvoří další výčnělky.
  2. Poté jsou postupně na náhodných místech prostoru generovány další částice. Pokud se tyto částice setkají s již vygenerovaným fraktálem (tj. jejich vzájemná vzdálenost l je menší než předem zadaná mez lmin), stanou se částice součástí fraktálu a vygenerují další částici na náhodném místě prostoru.
  3. V případě, že jsou nové částice vygenerovány ve velké vzdálenosti od vytvářeného fraktálního objektu, tj. platí nerovnost l>lmin, pak tyto částice zaniknou. Uvedeným způsobem fraktální útvar postupně roste až do splnění některé ukončující podmínky – viz další odrážky.
  4. Pokud je celkový počet částic, které tvoří fraktální útvar, menší než předem zadaná konstanta, pokračuje se v dalších výpočtech od druhého bodu postupu. V opačném případě simulace končí, přičemž jejím výsledkem je dvourozměrný nebo trojrozměrný fraktální objekt vytvořený z pixelů v E2, či částic nebo surfelů v E3.
  5. Generování fraktálního objektu může skončit také v případě, že některá částice, ze kterých se objekt skládá, dosáhne hranice plochy či prostoru, ve kterém se fraktální objekt generuje. Tuto podmínku pro ukončení generování je samozřejmě možné kombinovat s podmínkou předchozí.

fractals42_2

Obrázek 2: Obrázek difúze, počáteční body (seeds) tvořily všechny čtyři okraje obrázku

3. Algoritmus simulace difúze

Podle výše popsaného postupu lze v neformálním programovacím jazyce napsat algoritmus difúze, použitý pro generování stochastického fraktálního objektu. Implementace algoritmu difúze v programovacím jazyce Java je uvedena v dalším textu:

Vstupy programu:

  1. Množina souřadnic částic či bodů (semínek), které jsou vytvořeny před vlastním generováním fraktálního objektu S={S1, S2, … Sn}. Semínka leží buď v ploše E2 nebo prostoru E3.
  2. Maximální počet částic, které se mohou ve vygenerovaném fraktálním objektu vyskytovat. Tuto hodnotu označme symbolem itermax, protože ve skutečnosti specifikuje maximální počet provedených iterací.
  3. Oblast v ploše E2 či prostoru E3, ve které se může fraktální objekt generovat. Tuto oblast označme symbolem Ω. Oblast Ω může mít libovolný tvar, v praxi se však nejčastěji používá osově orientovaný obdélník, resp. kvádr.
  4. Vzdálenost, při které se může nový bod připojit k vytvářenému fraktálnímu objektu: lmin.

Výstup programu:

  1. Rastrový obrazec či prostorový objekt složený z množiny navzájem izolovaných bodů (pixelů či částic), který reprezentuje fraktální objekt.

Inicializační sekvence:

  1. Na souřadnicích uložených v množině S vytvoř body (pixely, částice či surfely), které představují základ pro dále generovaný fraktální objekt.
  2. Nastav čítač počtu iterací iter:=0.
  3. Vytvoř prázdnou množinu bodů Pf, které leží ve fraktálním objektu.

Hlavní programová smyčka:

  1. Pro iter probíhající od 0 do itermax-1 opakuj hlavní smyčku:
  2.   Opakuj vnitřní smyčku:
  3.     Vygeneruj dvojici náhodných čísel xiter a yiter: X2=(xiter, yiter)
  4.     Pro fraktál v E3 vygeneruj ještě třetí náhodné číslo ziter: X3=(xiter, yiter, ziter)
  5.     Vytvoř z dvojice X2 či trojice X3 bod P=[xiter, yiter] resp. P=[xiter, yiter, ziter]
  6.     Pokud bod P leží v oblasti Ω a vzdálenost bodu od obrazce Pf je menší než lmin:
  7.       Pak přidej do množiny Pf i bod P a ukonči vnitřní smyčku
  8.     Konec podmínky
  9.   Skok na začátek vnitřní smyčky
  10. Konec hlavní smyčky

Konec programu

fractals42_3

Obrázek 3: Obrázek difúze vzniklý stejným způsobem jako obrázek číslo 2, pouze se změnily podmínky hledání sousedních bodů

Z výše uvedeného algoritmu difúze je patrné, že generování fraktálního objektu je časově náročné, protože se ve vnitřní programové smyčce musí najít takový bod, který se přibližuje k již vygenerovanému fraktálnímu obrazci. Tato část algoritmu je obecně nedeterministická a celý algoritmus má časovou složitost O(|Ω|× itermax), kde |Ω| značí počet bodů, které vyplňují oblast Ω, přičemž vzdálenost mezi sousedními body je lmin.

Vygenerované body fraktálního objektu také velmi hustě vyplňují určenou oblast prostoru Ω, takže není patrný základní tvar fraktálu, zejména vytvořené větvení, protože se jednotlivé větve přes sebe překrývají – ukázka objektu vzniklého nemodifikovaným algoritmem difúze je zobrazena na následujícím obrázku. Pro urychlení generování bodů fraktálního obrazce a současně pro lepší prokreslení základního tvaru fraktálu zavádím omezující podmínky, které určují prostor, v němž se generují nové body, které budou k fraktálu připojeny. Tyto omezující podmínky budou popsány v následující kapitole.

fractals42_4

Obrázek 4: Objekt, který vznikl nemodifikovaným algoritmem difúze (jako semínko byly zvoleny tři body, jež tvoří vrcholy rovnostranného trojúhelníka)

4. Urychlení metody simulace difúze

Základní princip metody, který byl naznačený slovním popisem algoritmu v předchozích odstavcích, je implementačně velmi jednoduchý, protože se jedná o dvě vnořené smyčky a vyhodnocení jedné podmínky. Implementace tohoto algoritmu je však na i současných počítačích velmi neefektivní. Vygenerování výsledného obrazce pomocí této metody by trvalo extrémně dlouhou dobu. Je tedy nutné celý proces generování urychlit, čehož lze v první řadě dosáhnout omezením prostoru, ve kterém se mohou další body či částice generovat. Urychlení nastává z toho důvodu, že v předem omezeném prostoru se zvyšuje pravděpodobnost kolize či dotyku částice s již vygenerovaným fraktálem.

Pro vytváření modelů stromů a keřů pomocí algoritmu difúze je vhodné, aby se omezení prostoru postupně měnilo a docházelo tak k žádoucí deformaci modelu. Nejjednodušší omezení prostoru spočívá ve vytvoření osově orientovaného kvádru, ve kterém se nové částice vytváří. Pozice tohoto kvádru se může změnit (změna je typicky provedena postupným posunem kvádru nahoru od pomyslné podložky) například po vygenerování dostatečného množství částic. Tuto metodu lze dále rozšířit rozdělením celého kvádru na částečně se překrývající podoblasti, které se v průběhu simulace postupně mění. Podrobnější popis této metody bude uveden v navazující části tohoto seriálu.

Další urychlení generování výsledného modelu spočívá v diskretizaci prostoru, ve kterém jsou částice generovány. Místo spojitého prostoru (či jeho části), ve kterém mohou být částice generovány na libovolném místě, se použije pevně daná plošná či objemová mřížka. Pozice částice je poté plně specifikována indexy i, j a k, které jednoznačně udávají jednu konkrétní buňku mřížky. Vzdálenost částic potom není vyjádřena na základě Eukleidovské vzdálenosti (což je výpočetně poměrně náročná úloha), ale pomocí vzdálenosti vyjádřené nejmenším počtem buněk tvořících cestu mezi částicemi. Mřížku, ve které se budou částice generovat, lze vzhledem k jejím vlastnostem považovat za bitmapu (připomeňme, že bitmapou je myšlen rastrový obraz, jehož pixely mohou nabývat pouze dvou hodnot) v E2 či binární objemovou mřížku (každý voxel může v binární objemové mřížce nabývat pouze dvou hodnot, podobně jako pixely v bitmapě) v E3, v níž jsou pixely resp. voxely uloženy.

Vzhledem k tomu, že vygenerovaná částice se musí dotknout již vytvořeného fraktálního útvaru, je možné výpočet vzdálenosti eliminovat a testovat pouze nejbližší okolí částice. V ploše se může provádět velmi jednoduchý test na čtyřokolí nebo osmiokolí pixelů v bitmapě. V trojrozměrném prostoru lze podle charakteru vytvářené scény provádět test na šest nejbližších sousedů (indexy jejich buněk se liší o jednotku pouze v jednom směru), osmnáct sousedů (liší se indexy ve dvou směrech) nebo všech 26 sousedů (indexy ve všech třech směrech se mohou lišit o jedničku).

Během vytváření fraktálního útvaru je vhodné použít dvě datové struktury: lineárně vázaný seznam obsahující údaje o jednotlivých částicích, nebo rastrovou plošnou či objemovou mřížku, v jejíž buňkách je uložena informace o částicích a také příznak obsazenosti buňky. Ten může být uložen minimálně na jednom bitu, takže vlastní datová struktura s uloženými buňkami je paměťově velmi úsporná. Při aplikaci zde popsaného algoritmu difúze není zapotřebí k buňkám, kromě příznaku jejich obsazenosti, přidávat žádné další informace. Z hlediska výpočetní složitosti je výhodnější použití objemové mřížky, neboť se významně urychlí vyhledávání volného či obsazeného místa prostoru.

Urychlený algoritmus simulace difúze lze v neformálním programovacím jazyce popsat následovně:

Vstupy programu:

  1. Množina souřadnic částic či bodů (semínek), které jsou vytvořeny před vlastním generováním fraktálního objektu: S'={S1, S2, … Sn}. Středy semínek jsou umístěny v pravidelné diskrétní plošné mřížce – bitmapě, či pravidelné objemové mřížce.
  2. Maximální počet částic, které se mohou ve vygenerovaném fraktálním objektu vyskytovat. Tuto hodnotu označme symbolem itermax, protože ve skutečnosti specifikuje maximální počet prováděných iterací.
  3. Oblast v ploše E2 či prostoru E3, ve které se může fraktální objekt generovat. Tuto oblast označme symbolem Ω.
  4. Typ okolí pixelu nebo voxelu, ve kterém se hledají pixely či voxely, jež náleží do vytvářeného fraktálního objektu. V ploše E2 lze použít čtyřokolí nebo osmiokolí, v prostoru E3 může být testováno šest nejbližších sousedů, osmnáct sousedů či 26 sousedů. Typ okolí označme symbolem O.

Výstup programu:

  1. Binární rastrový obrazec (bitmapa) či binární objemová mřížka, v níž hodnoty jednotlivých pixelů/voxelů reprezentují tvar vznikajícího fraktálního objektu. Každý pixel či voxel může nabývat pouze dvou logických hodnot: true nebo false.

Inicializační sekvence:

  1. Vymaž bitmapu či objemovou mřížku, ve které jsou uloženy příznaky příslušnosti prvků k objektu – všechny pixely či voxely nastav na pravdivostní hodnotu false. V tomto okamžiku není součástí generovaného fraktálního objektu žádný prvek mřížky.
  2. Na souřadnicích uložených v množině S' nastav hodnoty pixelů či voxelů na pravdivostní hodnotu true, neboť tyto entity představují základ pro dále generovaný fraktální objekt. Ostatní pixely či voxely jsou stále nastaveny na pravdivostní hodnotu false.
  3. Nastav čítač počtu iterací iter:=0.

Hlavní programová smyčka:

  1. Pro iter probíhající od 0 do itermax-1 opakuj smyčku:
  2.   Opakuj vnitřní smyčku:
  3.     Vygeneruj dvojici celých náhodných čísel xiter a yiter.
  4.     Pro fraktál v E3 vygeneruj ještě třetí celé náhodné číslo ziter.
  5.     (souřadnice P=[xiter, yiter] resp. P=[xiter, yiter, ziter] musí ležet v oblasti Ω).
  6.     Vytvoř z dvojice či trojice bod P=[xiter, yiter] resp. P=[xiter, yiter, ziter]
  7.     Pokud v okolí bodu O(P) leží pixel či voxel s pravdivostní hodnotou true:
  8.       Pak nastav hodnotu pixelu/voxelu na pozici P na pravdivostní hodnotu true
  9.     Konec podmínky
  10.   Skok na začátek vnitřní smyčky
  11. Konec smyčky

Konec programu

fractals42_5

Obrázek 5: Objekt, jenž vznikl stejným způsobem jako objekt zobrazený na předchozím obrázku, pouze se změnily podmínky hledání sousedních bodů

5. Demonstrační příklad – simulace difúze

Dnešní demonstrační příklad je jednoduchá aplikace, jež slouží k simulaci difúze. Jedná se o prakticky nejjednodušší formu tohoto algoritmu. Nejprve se vygeneruje jeden nebo několik počátečních bodů, které představují základ generovaného obrazce. Tyto body se podle svého významu i chování nazývají semínko (seed). Tvar semínka, tj. rastrový obrazec, jímž je semínko reprezentováno, se volí pomocí výběrového seznamu Seed Shape.

Posléze jsou po celé ploše, ve které je plošný obrazec difúze vytvářen, postupně generovány body na náhodných pozicích. Pokud se v okolí (čtyřokolí nebo osmiokolí, podle nastavení algoritmu volbou z výběrového boxu Neighbourhood type) těchto bodů nachází část vytvářeného obrazce, je bod k obrazci připojen a algoritmus může ve smyčce pokračovat s novým bodem vygenerovaným na další náhodné pozici.

Generování obrazce difúze může být zastaveno po splnění alespoň jedné ze dvou podmínek: buď se vytvoří dostatečný počet bodů reprezentujících obrázek difúze, nebo poslední bod, který byl k obrazci připojen, překročil oblast, ve které se obrazec generuje. Volbu ukončovací podmínky je možné zvolit pomocí výběrového boxu Stop Condition.

Každý vygenerovaný bod může být reprezentován buď jedním pixelem nebo malým rastrovým obrazcem, jenž může být složen až z několika desítek pixelů – výběr požadovaného tvaru se provádí výběrovým boxem Point Shape. Aplikací konvolučního filtru (výběrový box Filter) je možné obrázek vyhladit, aby v něm nebyly patrné stopy jednotlivých bodů. Jak tvar jednotlivých bodů, tak i konvoluční filtr použitý pro rozmazání obrázku je možné nastavit z grafického uživatelského rozhraní demonstrační aplikace.

Bez dalšího podrobnějšího popisu jsou na následujících stránkách uvedeny výpisy zdrojových kódů nejdůležitějších me­tod:

  • initBitmap() – vytvoření a inicializace bitmapy, ve které se vytváří obrazec difúze
  • copyBitmapToPix­map() – kopie dat z pomocné bitmapy do pixmapy, která se bude zobrazovat
  • putPoint() – vykreslení jednoho bodu do temporální bitmapy podle zvoleného tvaru
  • initSeed() – inicializace semínka – počátečního bodu či bodů ve fraktálním objektu
  • neighboor() – test, zda se v okolí aktivního (právě vygenerovaného) bodu nachází body ze stávajícího obrazce difúze
  • checkStopCondi­tion() – test, zda se má generování difúze zastavit
  • applyDiffuse() – vlastní aplikace algoritmu difúze

Ukázka grafického uživatelského rozhraní (GUI) tohoto demonstračního příkladu i s vytvořeným objektem napodobujícím difúzi je uvedena na šestém obrázku, zdrojový kód programu je dostupný buď ve formě obarveného HTML kódu nebo v čistě textové formě. Po překladu pomocí javac je možné demonstrační příklad spouštět buď jako applet, nebo plnohodnotnou javovskou aplikaci.

root_podpora

fractals42_6

Obrázek 6: Screenshot demonstračního příkladu

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

Výše popsanou metodu simulace difúze je možné různými způsoby modifikovat a tím měnit i morfologii, fraktální dimenzi popř. hustotu vytvářených prostorových objektů. V následující části tohoto seriálu si povíme, jakým způsobem je možné metodu simulace difúze upravit tak, aby se pomocí ní daly vytvářet modely travin a keřů.

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.