Hlavní navigace

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

Pavel Tišnovský 22. 8. 2006

V dnešní části seriálu pojednávajícího o fraktálech používaných (nejenom) v počítačové grafice si povíme, jakým způsobem je možné minule popisovanou a demonstrovanou metodu simulace difúze upravit takovým způsobem, aby se pomocí ní daly vytvářet realisticky vypadající plošné či prostorové modely travin a keřů.

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.

fractals43_1

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ů.

fractals43_2

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

fractals43_3

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.

fractals43_4

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

fractals43_5

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).

fractals43_6

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 Ω0, Ω1, … Ω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.

fractals43_7

Obrázek 7: Princip vytvoření podoblastí Ω01,…Ω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.

fractals43_8

Obrázek 8: Model keře, při jehož generování byla oblast Ω' rozdělena na několik podoblastí Ω01,…Ω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ě plaintextujako 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.

fractals43_9

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.

Našli jste v článku chybu?

23. 8. 2006 11:50

Obávám se, že byste ten článek o modelování ženských orgánů stejně nepochopil - samozřejmě se to ve světě a částečně i u nás řeší včetně simulací :-) Ale je to tak specializovaná oblast, že se o tom v obecných i-časopisech nic nedozvíte.
Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

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

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Lupa.cz: Slevové šílenství je tu. Kde nakoupit na Black Friday?

Slevové šílenství je tu. Kde nakoupit na Black Friday?

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

Jsou čajové sáčky toxické?

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

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

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

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

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

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

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

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET

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

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

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

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

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

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

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

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

Recenze Westworld: zavraždit a...