Hlavní navigace

Brownův pohyb a reálně vypadající modely rostlin

29. 8. 2006
Doba čtení: 11 minut

Sdílet

V dnešním pokračování seriálu, ve kterém popisujeme fraktály používané (nejenom) v počítačové grafice, si ukážeme dva významné způsoby modifikace původního postupu používaného pro simulaci difúze. Od poměrně nevýrazných obrázků prezentovaných v předchozí části se tak co nejvíce přiblížíme k reálným (přírodním) útvarům.

Obsah

1. První demonstrační příklad – vytváření sub-boxů uvnitř posuvných boxů
2. Simulace difúze na základě Brownova pohybu
3. Druhý demonstrační příklad – pohyb bodů v prostoru po spojité trajektorii
4. Obsah dalšího pokračování tohoto seriálu

1. První demonstrační příklad – vytváření sub-boxů uvnitř posuvných boxů

Dnešní díl poněkud netradičně zahájíme popisem demonstračního příkladu, na jehož uvedení nám v minulé části již nezbylo místo (popis metody však byl minule uveden ve třetí kapitole).

Zde popisovaný a demonstrovaný algoritmus difúze, jehož aplikací je možné vytvářet obrazce stromů, travin a keřů s fraktální strukturou, vznikl modifikací algoritmu druhého a algoritmu třetího, které byly uvedeny v předchozí části tohoto seriálu. Podobně jako u zmiňovaných algoritmů, i zde se postupně generují body na náhodné pozici v ploše E2 či prostoru E3 a je testováno, zda se tyto body nedotýkají stávajícího fraktálního obrazce, tj. zda se nenachází ve čtyřokolí či osmiokolí pixelů náležejících do fraktálního obrazce.

Plocha generování nových bodů je omezena dvěma oblastmi. Plošně větší oblast představuje posuvný box, který v průběhu růstu fraktálního objektu postupně projde všemi řádky v pomocné rastrové mřížce, ve které se fraktální obrazec vytváří. V posuvném boxu se postupně tvoří několik menších oblastí – sub-boxů – na náhodné pozici, přičemž je v každé této oblasti nalezen předem zadaný počet bodů, které se připojí k fraktálnímu obrazci (počet bodů zadává uživatel z grafického uživatelského rozhraní).

fractals44_1

Obrázek 1: Obrázek vytvořený pomocí prvního demonstračního příkladu (fraktál roste z jednoho bodu)

Odlišnost od předchozích algoritmů spočívá především ve způsobu vytváření podoblastí v posuvném boxu, ve kterých se vytváří nové body. Odlišné jsou také podmínky pro ukončení připojování bodů a výslednou změnu polohy posuvného boxu.

Před spuštěním hlavní výpočetní smyčky, ve které se provádí změna polohy posuvného boxu, se nejprve vygeneruje jeden nebo několik tzv. 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ů určených 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. Implicitním tvarem semínka je pouhý jeden bod (resp. v diskrétní rastrové mřížce pixel) nacházející se ve středu spodního okraje rastrové mřížky.

fractals44_2

Obrázek 2: Další obrázek vytvořený pomocí prvního demonstračního příkladu (fraktál roste ze čtyř bodů)

Po vytvoření semínka se začínají generovat a případně i připojovat body v předem zadaných oblastech (posuvných boxech), které mění při běhu algoritmu postupně svoji polohu. Body však nejsou generovány na ploše celého posuvného boxu, ale v menších podoblastech, kterých je v ploše posuvného boxu vytvořeno hned několik.

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. 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ázejí uvnitř podoblastí vytvářených v posuvném boxu. Velikost podoblastí (tj. jejich celkovou plochu uváděnou v pixelech) je možné měnit pomocí posuvníků Box width a Box height. Pomocí posuvníku Boxes in row se mění maximální celkový počet bodů vytvořených při každé změně pozice posuvného boxu směrem nahoru.

fractals44_3

Obrázek 3: Obrázek vytvořený pomocí prvního demonstračního příkladu (fraktál roste z celého spodního okraje plochy)

Pokud se nový 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 (větší krok při posunu není možný, jelikož by se narušila kontinuita obrazce).

Generování obrazce difúze je možné ukončit v okamžiku, kdy se posuvný box (resp. jeho horní okraj) dotkne horního okraje pomocné bitmapy (rastrové mřížky). Na rozdíl od prvního demonstračního příkladu (Diffuse1.java) 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 a třetímu (Diffuse2.java a Diffuse3.java), ovšem s tím rozdílem, že je možné generování obrazce předčasně ukončit po připojení Points bodů k fraktálnímu obrazci. Lze také zadat typ okolí pixelu, ve kterém se hledají body patřící do již vygenerovaného obrazce. Typ okolí zpracovávaných bodů (tj. buď čtyřokolí nebo osmiokolí) se specifikuje výběrem z ovládacího prvku (list boxu) Neighbourhood type.

Kompilace dnešního prvního demonstračního příkladu se provede příkazem:

javac Diffuse4.java 

Popřípadě je možná i specifikace cílového běhového prostředí (pro starší JRE):

javac -target 1.1 Diffuse4.java 

Zdrojový kód prvního demonstračního příkladu je dostupný ve formě zdrojového textu i ve formátu HTML se zvýrazněnou syntaxí.

fractals44_4

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

2. Simulace difúze na základě Brownova pohybu

V předchozích dvou částech tohoto seriálu jsem popsal metodu, pomocí které je možné generovat modely přírodních objektů algoritmem difúze, jenž je založen na několika předem stanovených heuristikách. Podle těchto heuristik je možné generovat nové body (částice) na náhodných místech prostoru nezávisle na polohách předchozích částic, čímž se napodobuje trajektorie částic v určitých časových intervalech. Při použití stanovených heuristik není zapotřebí simulovat veškerý pohyb částic, takže generování modelu probíhá poměrně rychle, zvláště při použití minule popsaných urychlujících metod, tj. použití oblastí Ω a Ω'.

Vytvořené modely přírodních objektů však nejsou zcela korektní (což je ostatně patrné z obrázků), protože vzhledem k zavedení pevných částic, tj. de facto stacionárních bodů, se trajektorie aproximuje pouze hrubě a z toho důvodu nejsou nalezeny všechny dotyky částic se stávajícím fraktálním objektem. Na druhou stranu jsou v některých oblastech obrázku částice velmi nahuštěny, což přispívá k tomu, že obrázky spíše připomínají chaluhy a ne suchozemskou flóru.

K zajištění tvorby korektních modelů je proto nutné zvolit přesnější simulaci difúze, jež bude přímo založená na Brownově pohybu jednotlivých částeček hmoty (hmotných bodů). Princip práce této metody spočívá v postupném vytváření částic, které se pohybují po trajektorii dané Brownovým pohybem do té doby, než se dotknou stávajícího fraktálního objektu. Tuto metodu je možné slovně popsat pomocí několika pravidel:

  1. V prvním, inicializačním kroku se v předem určeném prostoru vygeneruje jedna částice či skupina částic nebo surfelů (ploškových elementů). Tyto objekty představují základ pro další růst fraktálního útvaru a jejich účel je obdobný jako v případě simulace difúze založené na heuristice. Jak jsem již psal v předchozích podkapitolách, nazývám tyto objekty vzhledem k jejich povaze semínkem.
  2. Ve druhém kroku jsou postupně na náhodných nebo předem určených místech prostoru Ω0 generovány další částice (volba místa je dána typem modelu, který je zapotřebí vytvořit). Tyto částice se posléze pohybují po trajektorii, jež je určena Brownovým pohybem, resp. jeho programovou aproximací. Na částice je v jednotlivých časových intervalech aplikován posun, což je vektor, jehož směr, orientace a délka se vypočte tak, aby vlastnosti těchto posunů odpovídaly vlastnostem Brownova pohybu, které byly popsány v XXXXI části tohoto seriálu.
  3. Pokud se částice při svém pohybu dotkne stávajícího fraktálního objektu, tj. její vzdálenost od nejbližšího bodu objektu splňuje podmínku L≤Lmin, je částice k fraktálnímu objektu přidružena a stává se jeho nedílnou součástí. Pokud se částice objektu nedotkne, je pokračováno ve výpočtech její trajektorie v ploše či prostoru. Při připojení částice se zkontroluje celkový počet částic. Pokud tento nedosáhl maximálního zadaného počtu, pokračuje se ve vytváření modelu od druhého kroku.
  4. Částice se také může při svém pohybu dostat ke hranicím vyhrazené oblasti, ve které se má model vytvořit (oblast pohybu částic budu opět značit symbolem Ω, podobně jako v předchozích částech). V takovém případě se musí částice buď ze systému odstranit, nebo zajistit, aby se částice pohybovala pouze ve vymezených hranicích – aplikuje se omezení na hodnoty jednotlivých souřadnic. Pokud některá souřadnice si částice i leží mimo vyhrazenou hranici <smin, smax>, je této souřadnici přiřazena buď hodnota si=smin (pokud si<smin) nebo hodnota si=smax (pokud si>smax).
  5. Generování fraktálního objektu touto metodou může být ukončeno v případě, že některá částice, která byla k vytvářenému objektu připojena, dosáhne hranice plochy či prostoru Ω, ve kterém se fraktální objekt generuje. Tuto podmínku pro ukončení vytváření objektu je možné kombinovat s podmínkou, jež určuje maximální počet částic, které se mohou ve výsledném modelu vyskytovat. Konkrétní podoba ukončující podmínky závisí na účelu modelu, který je vytvářen: buď je omezen celkový počet bodů (částic, surfelů), ze kterých se má objekt skládat, nebo má být oblast vyplněna až ke svým hranicím.

Jestliže se má pomocí tohoto postupu rychle vytvořit věrohodně vypadající model rostliny, je vhodné zredukovat prostor generování nových částic Ω0 na jeden bod P0, protože se tím zjednoduší celý algoritmus difúze i formát vstupních parametrů. Pokud je prostor Ω, ve kterém se má model vytvořit, tvořen osově orientovaným kvádrem, jsou stěny tohoto kvádru omezeny hodnotami xmin, xmax, ymin, ymax, zmin a zmax. Polohu bodu P0 lze na základě těchto souřadnic vypočítat podle vztahu:

P0=[x0, y0, z0]=[(xmin+xm­ax)/2, (ymin+ymax)/2, zmax]

Přičemž rostlina bude „růst“ ve směru osy z. Pro účely korektního generování modelu rostliny je také vhodné vložit všechny body, které jsou omezené obdélníkem [xmin, ymin, zmin] – [xmax, ymax, zmin] do množiny semínek (seeds), protože se na těchto bodech bude fraktální obrazec postupně vytvářet, což je naznačeno na následujícím obrázku.

fractals44_5

Obrázek 5: Vyznačené body, ze kterých bude „růst“ třírozměrný fraktální obrazec

Postup vytváření modelu rostliny lze dále modifikovat tak, že se celá, původně spojitá plocha E2 či prostor E3, ve kterém se fraktální obrazec vytváří, diskretizuje. Částice se tedy pohybují pouze v diskrétní plošné či objemové mřížce. Taktéž pohyb částice je reprezentován přeskokem částice z jedné polohy v mřížce do některé polohy sousední – viz následující ilustrační obrázek, na kterém je prezentován rozdíl mezi pohybem částice ve spojitém a diskrétním prostoru.

fractals44_6

Obrázek 6: Rozdíl mezi pohybem částice ve spojitém a diskrétním prostoru

V tomto případě se částice mohou v každém kroku posunout pouze do okolí pixelu/voxelu, ve kterém se nachází. Tento typ okolí budu v dalším textu značit symbolem O'. V ploše mohou být v okolí O' umístěny čtyři či osm pixelů, v prostoru to může být šest, osmnáct, či 26 voxelů. Ukázka použití tohoto postupu bude ukázána v další kapitole na demonstračním příkladu (vytvořeném pro plochu E2, rozšíření na prostor E3 je poměrně přímočaré, i když časově mnohem náročnější).

3. Druhý demonstrační příklad – pohyb bodů v prostoru po spojité trajektorii

Algoritmus, který je v této kapitole prezentovaný, se zásadním způsobem odlišuje ode všech předchozích zmíněných algoritmů (tj. algoritmu prvního až čtvrtého – Diffuse1 – Diffuse4). Odlišnost spočívá ve způsobu vytváření a následného pohybu bodů, které se připojují ke vznikajícímu obrazci difúze. Zatímco se v předchozí čtveřici algoritmů body postupně vytvářely na náhodných místech v určené oblasti (například v celé ploše pracovní bitmapy či v posuvném boxu), pátý algoritmus se liší tím, že na sebe jednotlivé body postupně navazují a tvoří tak v bitmapě nepřerušovanou­ cestu.

Při vlastní inicializaci algoritmu, tj. před spuštěním hlavní výpočetní smyčky, je na základě uživatelem předem specifikovaných parametrů zvolena souřadnice počátečního bodu X0=(x0, y0) a je vytvořeno semínko stejným způsobem, jako u předchozích algoritmů. Tvar semínka, tj. rastrový obrazec, jímž je semínko v bitmapě reprezentováno, se volí pomocí výběrového seznamu (list boxu) Seed Shape. Implicitním tvarem semínka je pouhý jeden bod (pixel) na spodním okraji rastrové mřížky.

fractals44_7

Obrázek 7: Model vytvořený pomocí druhého demonstračního příkladu (fraktál roste z jednoho bodu)

Následně se počáteční bod začne v bitmapě pohybovat, a to tím způsobem, že se v každém kroku může změnit jeho jedna či obě souřadnice, ale pouze o jednotku, tj. o jeden pixel. Nová souřadnice bodu Xn+1 v bitmapě se tedy nachází v osmiokolí souřadnice bodu z předchozího kroku. Pokud se bod na nové souřadnici dotkne stávajícího fraktálního objektu, je k tomuto objektu připojen a následně jsou vypočteny souřadnice, ze kterých se začne pohybovat další bod, jež je adeptem na připojení ke vznikajícímu fraktálnímu objektu.

Maximální počet vygenerovaných počátečních bodů (a tím i počet bodů připojených) je specifikován pomocí ovládacího prvku (scroll baru) Points. Velikost oblasti, ve které se body mohou pohybovat, je zadána polohami posuvníků Area width a Area height. Počáteční bod se buď vytváří na řádku posledního připojení starého bodu nebo ve střední části bitmapy. Velikost této oblasti je možné nastavit posuvníkem Border size. Metoda vytváření y-ové souřadnice nových bodů je zvolena pomocí výběrového seznamu Y-coordinate. x-ová souřadnice je vždy volena na základě parametru Area width.

fractals44_8

Obrázek 8: Model vytvořený pomocí druhého demonstračního příkladu (fraktál roste ze čtyř bodů)

Generování obrazce difúze je možné ukončit v okamžiku, kdy se poslední připojený bod dotkne horního okraje pomocné bitmapy (rastrové mřížky). 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 a třetímu, ovšem s tím rozdílem, že je možné generování obrazce předčasně ukončit po připojení Points bodů k fraktálnímu obrazci. Lze také zadat typ okolí pixelu, ve kterém se hledají body patřící do již vygenerovaného obrazce. Typ okolí (tj. buď čtyřokolí nebo osmiokolí) se specifikuje výběrem z ovládacího prvku (list boxu) Neighbourhood type.

fractals44_9

Obrázek 9: Další model vytvořený pomocí druhého demonstračního příkladu (fraktál roste z celého spodního okraje plochy)

Způsob překladu a následného spuštění této demonstrační aplikace je stejný jako u všech aplikací předešlých, protože se opět jedná o applet spustitelný přímo z okna internetového prohlížeče nebo pomocí aplikace AppletViewer. Překlad se provede příkazem:

javac Diffuse5.java 

Případně lze specifikovat cílovou verzi virtuálního stroje jazyka Java:

javac -target 1.1 Diffuse5.java 

Zdrojový kód druhého demonstračního příkladu je – podobně jako u příkladu předchozího – dostupný ve formě zdrojového textu i ve formátu HTML se zvýrazněnou syntaxí.

UX DAy - tip 2

fractals44_a

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

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

V následujícím pokračování tohoto seriálu ukončíme část věnovanou simulacím difúze popisem vytváření obrazců všesměrové difúze (tak, jak ji znají lidé například z oblasti chemie a fyziky) a posléze se zaměříme na druhý typ stochastických fraktálů – objekty vytvářené metodou přesouvání prostředního bodu (Midpoint Displacement Method).

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.