Vytváření modelů travin a keřů pomocí algoritmu difúze

Obsah

1. Vytváření modelů travin a keřů
2. První demonstrační příklad
3. Rozdělení posuvné oblasti na menší podoblasti
4. Druhý demonstrační příklad
5. Obsah dalšího pokračování tohoto seriálu

1. Vytváření modelů travin a keřů

V předchozí části tohoto seriálu jsme si popsali základní metodu simulace difúze založené na náhodném generování a připojování statických (nepohyblivých) bodů k rostoucímu fraktálnímu obrazci. Tuto původně jednoduchou a přímočarou metodu je možné různými způsoby modifikovat a nepřímo tím měnit i morfologii, fraktální dimenzi, popř. hustotu vytvářených plošných či prostorových objektů. První modifikace původního algoritmu spočívá ve výběru počáteční generující skupiny bodů/částic, která zásadním způsobem ovlivňuje tvar výsledného fraktálního objektu. Pokud by existovala pouze jedna generující částice, fraktální útvar by vyrůstal přímo z této částice a podle dalších podmínek by se jednalo o jednoduchý středový fraktál nebo o fraktál rostoucí do výšky. Tímto způsobem se dají jednoduše vytvářet modely jednotlivých keřů či trávy.

Kromě volby generující skupiny částic (semínek – seeds) se použije posuvné plošné či prostorové okno, jež specifikuje oblast Ω', ve které se body/částice mohou generovat. Toto okno má při vytváření plošného obrazce stejnou šířku jako je šířka bitmapy, do které se obrazec generuje. V případě vytváření prostorového objektu odpovídá výška a šířka okna mezím, ve kterých má výsledný trojrozměrný fraktál ležet. Posuvná oblast je na začátku generování umístěna na povrchu země, tj. v místech, ze kterých má model traviny či keře vyrůstat – viz následující ilustrační obrázek.

Obrázek 1: Princip posuvného okna – oblasti Ω'

Generování fraktálního obrazce pak probíhá tím způsobem, že se po každém posuvu okna o předem daný krok ΔΩ, vygeneruje v programové smyčce zadané množství náhodně umístěných bodů i_Ω‚. Pokud se tyto body dotýkají již vytvořeného objektu, jsou k tomuto objektu připojeny, stejně jako při běhu nemodifikovaného algoritmu difúze. Vzhledem k tomu, že je množství i_Ω‘ náhodných bodů generovaných v oblasti Ω‚ konstantní, bude postupně klesat či naopak růst množství bodů, které se při každém posuvu okna připojí k vytvářenému objektu. To, zda nastane pokles či růst bodů připojovaných k objektu, závisí na velikosti oblasti Ω‘ a počtu bodů i_Ω', které se v této oblasti při každém posuvu oblasti generují. Průměrná hustota bodů je dána vztahem:

h_Ω‚ ~ i_Ω‘/Ω'

Ukázka dvou plošných obrazců vygenerovaných pomocí modifikovaného algoritmu difúze s posuvným oknem (oblastí) Ω‚ je zobrazena na dalších dvou obrázcích. Pro vytvoření těchto obrázků byl použit shodný algoritmus, pouze výška oblasti Ω‘ byla ve druhém případě větší. To se projevilo menší hustotou generovaných bodů h_Ω‚ v oblasti Ω‘ a užším tvarem vygenerovaných fraktálních objektů.

Obrázek 2: Model keře, který vznikl postupným vertikálním posuvem oblasti Ω'

Obrázek 3: Model, u nějž byla použita vyšší oblast generování nových bodů Ω' než u modelu zobrazeného na předchozím obrázku

Na dalších dvou demonstračních obrázcích je ukázáno, jakým způsobem se může změnit charakteristika vytvářeného fraktálního objektu v případě, ve kterém se postupně mění hodnoty parametru i_Ω‚. Tento parametr určuje počet nových bodů, jež se generují v oblasti Ω‘ – jedná se tedy o maximální hodnotu počitadla smyčky modifikovaného algoritmu difúze. U obou obrázků byla použita oblast Ω‚ o konstantní velikosti, i krok jejího posunu ΔΩ byl konstantní. Jediným rozdílným parametrem byly odlišné hodnoty i_Ω‘. Jak je z obrázků patrné, má změna hodnoty parametru i_Ω' vliv především na hustotu vygenerovaných modelů a také na celkový počet vytvořených rostlinek.

Obrázek 4: Model keře, u nějž je parametr i_Ω' nastavený na nízkou hodnotu

Obrázek 5: Model keře, u nějž je parametr i_Ω' nastavený na vysokou hodnotu

2. První demonstrační příklad

V dnešní první demonstrační aplikaci je použit modifikovaný algoritmus pro simulaci difúze, který pracuje poněkud odlišným způsobem než základní algoritmus použitý v demonstrační aplikaci uvedené v předchozí části tohoto seriálu. Body, které se při běhu algoritmu generují, nemohou být vytvářeny na libovolném místě prostoru, ale pouze v takzvaném posuvném boxu (oblasti generování nových bodů), jehož rozměry zadává uživatel pomocí posuvníků (scroll barů) nazvaných Box width a Box height. Posuvný box v kontextu aplikace odpovídá výše popisované oblasti Ω, která má tvar osově orientovaného obdélníka.

Před spuštěním hlavní výpočetní smyčky se nejprve 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 (list boxu) nazvaného Seed Shape. Posléze se začínají generovat a případně i připojovat body v předem zadané oblasti, která mění při běhu algoritmu postupně svoji polohu.

Maximální počet bodů vygenerovaných při každém posuvu boxu je specifikován pomocí ovládacího prvku (scroll baru) Points in box. Na začátku vytváření obrazce difúze se posuvný box nachází v dolní části pomocné bitmapy. Dále se ve vnitřní programové smyčce generují body, které se nachází uvnitř posuvného boxu. Pokud se bod dotkne stávajícího objektu, je k němu připojen. Po připojení předem zadaného počtu bodů se posuvný box transformuje o jeden pixel směrem vzhůru.

Generování obrazce difúze skončí v okamžiku, kdy se posuvný box dotkne horního okraje bitmapy. Na rozdíl od demonstračního příkladu uvedeného v předchozím pokračování se tedy nemusí zadávat dodatečná podmínka pro ukončení generování objektu. Lze však zadat typ okolí pixelu, ve kterém se hledají body patřící do již vygenerovaného obrazce. Typ okolí se specifikuje výběrem z ovládacího prvku (list boxu) Neighboor type.

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 seznamem Point Shape. Aplikací konvolučního filtru (výběrový seznam Filter) je možné vytvořený 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.

Následuje výpis nejdůležitějších metod použitých v první demonstrační aplikaci:

1. initBitmap() – vytvoření a inicializace bitmapy, ve které se vytváří obrazec difúze
2. copyBitmapToPix­map() – kopie dat z pomocné bitmapy do pixmapy, která se bude zobrazovat
3. putPoint() – vykreslení jednoho bodu do temporální bitmapy podle zvoleného tvaru
4. initSeed() – inicializace semínka – počátečního bodu či bodů ve fraktálním (difúzním) objektu
5. neighboor() – test, zda se v okolí aktivního (tj. právě vygenerovaného) bodu nachází nějaké body ze stávajícího obrazce difúze
6. applyDiffuse() – vlastní aplikace algoritmu difúze popsaného výše

Celý demonstrační příklad, který je napsaný v programovacím jazyce Java, si můžete stáhnout buď ve formě zdrojového kódu, nebo jako obarvený zdrojový kód v HTML. Po překladu vznikne několik souborů .class, spuštění demonstračního příkladu je možné provést buď pomocí webového prohlížeče s podporou Javy nebo Sunovského prohlížeče appletů nazvaného Applet Viewer (ten je dodávaný spolu s oficiálním Java Software Development Kitem).

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

3. Rozdělení posuvné oblasti na menší podoblasti

Další modifikací původní metody simulace difúze, jež využívá posuvné okno, je rozdělení celé oblasti, ve které se vytváří nové částice Ω‚ (tj. plochy posuvného okna) na menší podoblasti Ω₀, Ω₁, … Ω_n, jejichž umístění a velikost je zvolena náhodně z předem zadaného intervalu – vždy tak, aby plocha celé podoblasti ležela v oblasti Ω‘. Nové body, které se budou ke vznikajícímu fraktálnímu objektu připojovat, jsou generovány pouze v podoblasti Ω, která se po vygenerování daného počtu bodů může změnit.

Obrázek 7: Princip vytvoření podoblastí Ω₀,Ω₁,…Ω_n v posuvném okně – oblasti Ω'

Počet bodů generovaných v podoblasti Ω je zadán parametrem i_Ω. Tento parametr, spolu s počtem podoblastí Ω vytvořených v jedné oblasti Ω‚ (počet podoblastí Ω v posuvném okně Ω‘ budu značit symbolem n_Ω), nahrazuje parametr i_Ω‚, který není v takto modifikovaném algoritmu použit. Na předchozím (sedmém) ilustračním obrázku je vyobrazen způsob vytváření jednotlivých podoblastí Ω v oblasti Ω‘, která se sama postupně posunuje směrem vzhůru, avšak vždy až po zaplnění všech n_Ω podoblastí vygenerovanými body. Objekt vytvořený takto modifikovanou metodou je zobrazen na obrázku číslo 8.

Obrázek 8: Model keře, při jehož generování byla oblast Ω' rozdělena na několik podoblastí Ω₀,Ω₁,…Ω_n

Při pohledu na předchozí obrázek je patrné, že oproti dříve uvedeným modelům dochází k vyššímu nahuštění vygenerovaných bodů na menších místech prostoru. Velikost podoblastí, ve kterých jsou body nahuštěny, zhruba odpovídá velikosti plochy Ω_i. Počáteční rozmístění podoblastí Ω_i v prvních cyklech iterace má na rozmístění jednotlivých rostlinek největší vliv, protože v dalších iteracích se již body nabalují na dříve vytvořený základní tvar.

Zhruba v prostřední části obrázku je také ukázáno, že může dojít k ukončení generování jedné rostlinky – to se stane v případě, že se v daném místě prostoru nevytvoří žádná podoblast Ω, ve které by se nové body generovaly. Z tohoto důvodu je nutné zajistit, aby se při posunu celé oblasti Ω' testem zajistilo, že se v podoblastech Ω_i vygeneruje vždy stejný počet bodů. Pokud by se konstantní počet bodů nevygeneroval, znamenalo by to postupné ukončení růstu rostlinky, neboť by nebylo možné zajistit kontinuitu, tj. vzájemné propojení jednotlivých částí rostlinky.

4. Druhý demonstrační příklad

Algoritmus difúze, jenž je v této demonstrační aplikaci prezentován, vznikl modifikací druhého, tj. předchozího algoritmu difúze. Dvourozměrné body, které se při běhu algoritmu postupně generují, nemohou být vytvářeny na libovolném místě prostoru, ale pouze v takzvaném posuvném boxu (oblasti generování nových bodů), jehož rozměry zadává uživatel pomocí posuvníků (scroll barů) Box width a Box height.

Odlišnost od druhého algoritmu spočívá především v logice ukončování vnitřních smyček. Pro každou polohu posuvného boxu je nalezen minimálně jeden bod, který se stávajícího fraktálního objektu dotýká. Ihned po nalezení prvního bodu se nastaví příznak ukončení vnitřní smyčky, tato však probíhá dále s tím rozdílem, že se pouze testuje, zda se nově generované body obrazce dotýkají bez explicitního hledání bodu doteku. To znamená, že je zaručeno připojení pouze jednoho bodu, počet skutečně připojených bodů je náhodný, což nemalým způsobem zvyšuje i náhodnost vytvořeného fraktálního objektu.

Před spuštěním hlavní výpočetní smyčky se nejprve 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) a mají totožný význam, jako u všech dalších algoritmů pro simulaci difúze. Tvar semínka, tj. rastrový obrazec, jímž je semínko reprezentováno, se volí pomocí výběrového seznamu (list boxu) Seed Shape.

Po vytvoření semínka se v hlavní programové smyčce začínají generovat a případně i připojovat body v předem zadané oblasti, která mění při běhu algoritmu (programové smyčky) postupně svoji polohu.

Maximální počet bodů vygenerovaných při každém posuvu boxu je specifikován pomocí ovládacího prvku (scroll baru) Points in box. Na začátku vytváření obrazce difúze se posuvný box nachází v dolní části pomocné bitmapy. Dále se ve vnitřní programové smyčce generují body, které se nachází uvnitř posuvného boxu. Pokud se bod dotkne stávajícího objektu, je k němu připojen a současně se nastaví příznak ukončení vnitřní smyčky, ve které se vyhledávají body pro připojení k fraktálnímu obrazci. Po připojení či otestování předem zadaného počtu bodů se posuvný box transformuje o jeden pixel směrem vzhůru.

Generování obrazce difúze je možné ukončit v okamžiku, kdy se posuvný box dotkne horního okraje pomocné bitmapy. Na rozdíl od prvního demonstračního příkladu se tedy nemusí zadávat dodatečná podmínka pro ukončení generování objektu – tímto se zde popisovaný algoritmus podobá spíše algoritmu druhému. Lze však zadat typ okolí pixelu, ve kterém se hledají body patřící do již vygenerovaného obrazce. Typ okolí se specifikuje výběrem z ovládacího prvku (list boxu) Neighbourhood type.

Každý vygenerovaný bod může být v bitmapě reprezentován buď jedním pixelem nebo poměrně 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ý seznam Filter) je možné vytvořený obrázek vyhladit, aby v něm nebyly patrné stopy jednotlivých bodů, ze kterých je obrazec složen. 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.

Po stlačení tlačítka Recalc je celý algoritmus simulace difúze spuštěn s novými parametry. Prostého překreslení systému lze dosáhnout stiskem tlačítka Redraw. Při změně typu konvolučního filtru dojde k překreslení automaticky. Vykreslovaný obrázek má velikost 256×256 pixelů. Význam dalších tlačítek, tj. About, Info a Help je patrný již z jejich názvu.

1. initBitmap() – vytvoření a inicializace pomocné bitmapy, ve které se vytváří obrazec difúze
2. copyBitmapToPix­map() – kopie dat z pomocné bitmapy do finální pixmapy, která se bude zobrazovat
3. putPoint() – vykreslení jednoho bodu do pomocné bitmapy podle uživatelem zvoleného tvaru
4. initSeed() – inicializace semínka – počátečního bodu či bodů ve fraktálním (difúzním) objektu
5. neighboor() – test, zda se v okolí aktivního (tj. právě vygenerovaného) bodu nachází nějaké body ze stávajícího obrazce difúze
6. applyDiffuse() – vlastní aplikace algoritmu difúze popsaného v textu výše

Zdrojový kód druhého demonstračního příkladu je opět dostupný ve formě plaintextu i jako HTML kód s obarvenou syntaxí. Druhý demonstrační příklad je vytvořen (podobně jako příklad první) tak, aby ho bylo možné spustit jako applet buď přímo z webového prohlížeče, nebo pomocí prohlížeče appletů nazvaného Applet Viewer.

Obrázek 9: Screenshot druhého demonstračního příkladu

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

V následující části tohoto seriálu budu popisovat poněkud odlišnou metodu simulace difúze, která bude založena na přímém napodobování Brownova pohybu pomocí pohyblivých částic (tím se tato metoda výrazně odlišuje od metod popsaných minule a dnes). Objekty vytvořené touto metodou si však stále zachovávají svou fraktální charakteristiku.