Obsah
1. Stochastické fraktály – difúze a plasma
2. Algoritmy pro vykreslení difúze
3. Algoritmy pro vykreslení plasmy
4. Plasma a tvorba trojrozměrných modelů terénu
5. L-systémy
6. Markus-Ljapunovovy fraktály
7. Perlinova šumová funkce
8. Obsah dalšího pokračování tohoto seriálu
1. Stochastické fraktály – difúze a plasma
Rozsáhlou a také různorodou 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ů. V tomto seriálu jsme si popsali dvě velké skupiny stochastických fraktálů – fraktální objekty napodobující difúzi a fraktální objekty nazývané obecně „plasma“.
2. Algoritmy pro vykreslení difúze
Algoritmy generující obrazce difúze vychází ze sledování Brownova pohybu. Pomocí těchto metod je možné vytvářet tvarově složité přírodní útvary, například modely stromů, keřů nebo trávy. Prostorové útvary, které jsou vygenerované touto metodou, se vyznačují částečnou (statistickou) soběpodobností (tj. soběpříbuzností), 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ů). Výsledkem aplikace těchto 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ů, které 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ří. 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é.
Tyto rozmanité fraktální objekty byly popsány – samozřejmě s velkým počtem demonstračních příkladů (vytvořených v Javě) – ve čtyřicáté první až čtyřicáté páté části tohoto seriálu.
3. Algoritmy pro vykreslení plasmy
V počítačové grafice, zejména demech, je velmi oblíbený efekt plasmy, ať už vykreslený jako statický obrázek či animovaná sekvence postupně se měnící plasmy. Plasmu je možné vytvořit několika způsoby, typicky metodou rekurzivního dělení čtverce, Fourierovou syntézou či rekurzivním dělením plochy. Nejdříve si stručně popíšeme metodu rekurzivního dělení čtverce, kterou jsme se podrobně zabývali v čtyřicáté šesté části tohoto seriálu.
Obrázek plasmy se v tomto případě generuje upraveným midpoint algoritmem (algoritmem posunu středního bodu) rozšířeného do dvourozměrného prostoru, přičemž čtverec je nahrazen rastrovým obrázkem (pro jednoduchost ve stupních šedi), kde pozice každého pixelu odpovídá souřadnicím bodu v rovině x-y a barva pixelu, tj. úroveň šedé, zbývající z-ové souřadnici bodu. Generování plasmy začíná v rozích rastrového obrázku a v jednotlivých krocích rekurze je obrázek dělen na čtvrtiny až do chvíle, kdy se dojde k velikosti jednoho pixelu, který se již dále samozřejmě nedělí. Kromě obrázků ve stupních šedi je možné generovat i barevné obrázky. Ty se tvoří dvojím způsobem – buď aplikací barvové palety (tak je plasma implementována například v programu FractInt), nebo vytvořením tří obrázků, z nichž každý odpovídá jednomu barvovému kanálu R, G, B.
Pomocí výše uvedené metody je možné vytvářet působivé obrázky plasmy; pro některé vstupní parametry však mohou být na obrázcích patrné vodorovné a svislé přechody mezi barvami, které tvoří hranice mezi čtverci na několika nejvyšších úrovních dělení. Na nižších úrovních, cca od čtvrté iterace, hranice splývají, neboť dochází ke snižování „amplitudy“ odchylky Δ. Opticky rušivé přechody vznikají z toho důvodu, že se při každém rozdělení čtverce posune pouze jeho prostřední bod (střed) a nikoli prostřední body jeho hran – pro jejich posun nemáme dostatek informací, protože nevíme, jakým způsobem budou rozděleny čtyři sousední čtverce. Existuje několik způsobů, jak nežádoucí přechody odstranit. Některé způsoby spočívají v odlišném dělení čtverce, například střídavě po úhlopříčkách a vodorovných/svislých hranách, jiné způsoby zavádí „paměť“ posuvu prostředních bodů okolních čtverců apod.
Zajímavější (a poněkud neznámá) alternativní metoda, která už nespočívá v rekurzivním dělení čtverce, je založena na iterativním generování různě orientovaných přímek, které rozdělují obraz na dvě (obecně) nestejně velké poloviny. Tento postup byl popsán v čtyřicáté sedmé části seriálu. Po vygenerování náhodné přímky (ta po protnutí hranic obrázku vytvoří úsečku) se provedou následující operace: 1) intenzita všech pixelů ležících nalevo od přímky se sníží o jedničku a 2) intenzita všech pixelů ležících napravo od přímky se naopak o jedničku zvýší.
Pro vygenerování věrohodného obrázku plasmy je zapotřebí vytvoření přímky a snižování/zvyšování intenzity pixelů provádět v iterační smyčce mnohokrát, typická hodnota bývá 1 000 – 10 000 iterací. Po provedení takto vysokého množství iterací již hranice mezi různě orientovanými přímkami (resp. polorovinami) nejsou patrné (na obrázcích 6 a 7 je schválně počet iterací nižší, aby byla struktura obrázku vzniklého postupným dělením prostoru na dvě části jasně patrná). Po provedení všech iterací je nutné obrázek normalizovat, tj. nejnižší intenzitě pixelů (ta může být díky odčítání i záporná) přiřadit černou barvu a nejvyšší intenzitě barvu čistě bílou. Výsledkem těchto operací je plasma bez znatelných horizontálních či vertikálních hran.
V mnoha počítačových demech se často můžeme setkat s různými formami animované plasmy. Animace v tomto případě není představována ničím jiným než průběžnou změnou jednoho parametru či několika parametrů při procedurálním generování plasmy; volba logicky padá na takové parametry, které nevyžadují nový výpočet plasmy v každém kroku animace, to by totiž bylo časově velmi náročné, zejména na pomalejších počítačích (animovanou plasmu totiž můžeme vidět i na osmibitových počítačích – Atari, Commodore C64 apod.). V jednodušších případech (dema vzniklá v rozmezí cca 1990–1995) se dokonce setkáváme pouze s tím, že jsou přes sebe posouvány dva obrázky plasmy, přičemž dochází k součtu „barev“ jejich pixelů nebo k operaci XOR mezi jednotlivými pixely.
Poněkud kvalitnější animace je založena na vzájemném překrytí dvou stejných či naopak různých obrázků plasmy. Před vlastní animací je zapotřebí provést výpočet dvou obrázků plasmy. Tyto obrázky jsou při animacích přes sebe navzájem posunovány a indexy pixelů, jež leží přesně nad sebou, jsou sečítány s tím, že při přetečení hodnoty indexu přes 255 se začíná opět od nulové hodnoty (tomu musí odpovídat i použitá barvová paleta). Tuto operaci je možné provádět různým způsobem, nejjednodušeji tak, že se sčítají dvě bytové hodnoty s ignorováním přenosu. Další způsob spočívá ve využití instrukcí MMX, pomocí kterých lze spočítat hodnoty několika pixelů současně (typicky osmi pixelů) a to i s využitím sčítání se saturací, tj. bez přetečení.
4. Plasma a tvorba trojrozměrných modelů terénu
Metody pro generování fraktálů se velmi často a s úspěchem používají pro tvorbu trojrozměrných modelů terénu, dokonce se říká, že je to jediná metoda, pomocí které je možné vytvořit věrné modely krajiny. Většinou se terény vytváří pomocí výškových polí. Výšková pole (heightfield, height-field) představují ve své podstatě velmi specifický druh pravidelných trojúhelníkových sítí (TRN – triangular regular network). Tato pole jsou většinou použita pro úspornou reprezentaci části zemského povrchu nebo povrchu jiné (fiktivní) planety, u kterého neuvažujeme zaoblení, tj. danou planetu považujeme za „placku“, což však přináší pouze zanedbatelné chyby, která se u dnes používaných rozlišení pohybuje v řádu sotva jednoho či dvou pixelů.
Výšková pole přináší oproti obecné trojúhelníkové síti jedno zásadní, ale relativně snadno splnitelné omezení – jednotlivé trojúhelníky se nesmí po projekci do roviny x-y překrývat (při reprezentaci zemského nebo mimozemského povrchu jsou osy x a y orientovány vodorovně, kdežto osa z svisle vzhůru). Toto omezení však na druhou stranu přináší možnost reprezentace povrchu pomocí výšek uložených v pravidelné rastrové mřížce (bitmapě, pixmapě), což je výhodné především z hlediska značně snížených paměťových nároků, ale i z hlediska rychlosti vykreslování. I přes dnešní výraznou dominanci polygonových modelů trojrozměrných těles se výšková pole pro svoje dobré vlastnosti stále používají.
Převod výškových dat do rastrové mřížky je proveden diskretizací souřadnic ve směru všech tří souřadných os (v každé ose je možné provést diskretizaci s jiným krokem) a uložením výšek, tj. z-ových souřadnic do rastrové mřížky, kterou lze považovat za bitmapu/pixmapu, ve které hodnota každého pixelu neodpovídá barvě (jak je u klasických pixmap zvykem), ale výšce z předem zadaného rozsahu (použitím barev a textur se budeme zabývat v následujících kapitolách). Výšková pole bývají na externích datových médiích uložena většinou v některém bitmapovém formátu, například BMP, PNG či TGA, čímž je umožněn jejich snadný přenos do jiných systémů a aplikací, zejména do GIS systémů a renderovacích programů typu POVRay.
V případě, že se výšková mapa generuje přímo z obrázku plasmy – viz předchozí kapitolu – , je samozřejmě možné diskretizaci (v tomto případě spíše pouhé převzorkování) vynechat, a to za předpokladu, že rozlišení plasmy bude odpovídat požadovanému rozlišení výškové mapy, tj. počtu uložených výšek v obou směrech. Jedinou další činností tak je volba vhodného měřítka z-ové osy, tj. výšky výsledného terénu. Úpravou parametrů generované plasmy se mění také charakter terénu, od středočeské pahorkatiny po velehory. Různými způsoby vytváření 3D terénu jsme se zabývali v části 49, 50 a 51.
5. L-systémy
L-systémy, v minulosti též známé pod názvem Lindenmayerovy systémy, jsou skupinou fraktálů definovaných ve své nejjednodušší podobě pomocí regulárních nebo bezkontextových přepisovacích gramatik. Název této skupiny fraktálů, na jejichž výzkumu má největší podíl Aristid Lindenmayer a Przemyslaw Prusinkiewicz, pochází ze zkráceniny anglického sousloví LOGO-like turtle. LOGO je velmi zajímavý programovací jazyk vycházející z funkcionálního programovacího jazyka LISP (syntaxe je však „přezávorkovanému“ LISPu vzdálená), ve kterém se, kromě snadného zpracování datových struktur, dají s využitím jednoduchých příkazů pomocí takzvané želvy kreslit různé obrazce složené z úseček (už jednou jsem slíbil, že se tomuto jazyku budu na Rootu věnovat, a ta chvíle se blíží).
Podstatou tvorby těch nejjednodušších a v současnosti pravděpodobně nejpoužívanějších L-systémů je přepisování řetězců podle určitých pravidel, která jsou buď předem zadaná množinou přepisovacích pravidel (gramatiky), nebo se mění v průběhu generování fraktálního obrazce, například na základě zpětné vazby či na podněty okolního prostředí (gravitace, dopadající světlo apod.). Přepisování některých symbolů řetězce je většinou pevně dané, ale může být také určeno na základě generátoru náhodných čísel (stochastické L-systémy). Každý symbol v řetězci má přiřazen jistý geometrický význam, například transformaci či generování/nakreslení objektu. V případě použití želví grafiky se jedná o příkazy pro posun a natočení želvy.
Zajímavé obrazce se začnou tvořit, jestliže v programu určeném pro LOGO použijeme iteraci resp. rekurzi, což odpovídá iteraci v gramatice, tj. stavu, kdy na pravé straně přepisovacího pravidla je nonterminální symbol shodný se symbolem na levé straně téhož pravidla. S pomocí L-systémů lze generovat fraktální objekty, které se podobají rostlinám, stromům a dalším přírodním útvarům. Poslední aplikace také směřují k využití těchto fraktálů při generování 3D modelů technologických artefaktů a dokonce i textur. Z toho, jak se fraktál pomocí L-systémů generuje, je zřejmé, že se jedná o deterministický postup (pokud se při aplikaci přepisovacích pravidel nepoužije generátor náhodných čísel) a výsledný fraktál je tedy též deterministický. Těmto velmi pravidelným a mnohdy i symetrickým fraktálům se také někdy říká graftály.
Zájemci o L-systémy se mohou zaměřit na části 52, 53, 54, 55, 56, 57, 58, 59, 60 a 61 tohoto seriálu.
6. Markus-Ljapunovovy fraktály
Markus-Ljapunovovy fraktály jsou vytvářené v pravidelné rastrové mřížce většinou zobrazované ve formě bitmapy či pixmapy (podobně jako známá Mandelbrotova množina a množiny Juliovy), ve které je každému pixelu přiřazena barva v závislosti na numericky vypočtené hodnotě takzvaného Ljapunovova exponentu. Pomocí tohoto exponentu je v matematice i fyzice určována (velmi zjednodušeně řečeno) míra lineární stability či naopak nestability atraktoru nějakého dynamického systému pro dané vstupní podmínky; dokonce se jedná o jeden z nejdůležitějších parametrů mnoha nelineárních dynamických systémů (včetně modelů počasí, modelů populačního růstu, modelů pohybů cen na burze atd.).
Ljapunovův exponent je poměrně složité analyticky vypočítat (je počítán pomocí limity pro t jdoucí k nekonečnu), většinou si však vystačíme s prostým numerickým přiblížením přesného výpočtu. Markus-Ljapunovovy fraktály jsou odvozeny z jednorozměrných bifurkačních diagramů a logistické mapy – oba dva termíny jsme si (spolu s několika praktickými příklady) popsali v prvních částech tohoto seriálu. Markus-Ljapunovův fraktál přímo vychází z výpočtu Ljapunovova exponentu, pouze ho nápaditým způsobem rozšiřuje do dvou dimenzí. Vzhledem k tomu, že se má vytvořit plošný obrázek (bitmapa, pixmapa), použijí se při výpočtech dva dynamické systémy modelu růstu, přičemž se v každém pixelu zkoumá Ljapunovův exponent pro jinou hodnotu míry růstu Gr.
Ve směru horizontální osy se zvětšuje míra růstu prvního dynamického systému, ve směru osy vertikální pak míra růstu druhého systému. V demonstračních příkladech jsou tyto hodnoty uloženy v proměnných nazvaných startx a starty, samotná hodnota xn je pak uložena v proměnné z, aby se zdůraznilo, že se vlastně jedná o třetí souřadnici odpovídající barvě pixelu. Při iterativním výpočtu Ljapunovova exponentu se v iterační smyčce pravidelně střídají vzorce obou dynamických systémů, což v důsledku vede k tvorbě zdánlivě „trojrozměrných“ obrázků. V případě, že je výsledná hodnota Ljapunovova exponentu kladná (chaos), je daný pixel vykreslený konstantní barvou (například černou), v opačném případě je obarven na základě vypočtené hodnoty exponentu. Do celého výpočtu je ještě vložena podmínka, která zabrání růstu xn nade všechny meze.
Markus a Hess rozšířili výše popsaný výpočet Markus-Ljapunovova fraktálu o další možnost, resp. o další stupeň volnosti. Místo pevně dané posloupnosti funkcí růstu při iterativním výpočtu Ljapunovova exponentu, které můžeme označit například symboly a a b, je možné použít posloupnost libovolnou. Specifikace vybrané posloupnosti může být zadána buď pomocí řetězce (například řetězec „abba“ značí postupný výběr funkcí a, b, b, a, a, b, b, a …), nebo i decimálním číslem, které vznikne po převodu binárních symbolů (0=a, 1=a) do sekvence bitů chápané jako binární zápis celého nezáporného čísla. Tímto způsobem se posloupnost zapisuje například i ve známém programu FractInt, konkrétně se jedná o parametr Order u typu fraktálu nazvaného Lyapunov.
7. Perlinova šumová funkce
Perlinova šumová funkce byla s velkým úspěchem použita v mnoha aplikacích počítačové grafiky; například prakticky každý film, ve kterém je použita renderovaná grafika, tuto funkci nějakým způsobem použil. Její úspěch spočívá v tom, že se pomocí ní dají do původně přesných a „počítačově chladných“ modelů vnést náhodné prvky, takže se model či celá vytvářená scéna přiblíží realitě. Podobný princip vnesení náhodnosti ostatně umožňují i fraktály, zejména ty vytvářené na stochastickém základě (plasma, stochastické L-systémy apod.). Perlin šumovou funkci navrhl už v roce 1983, v roce 1985 o její aplikaci vznikl článek prezentovaný na SIGGRAPHu (jedna z nejvýznamnějších konferencí počítačové grafiky) a v letech 1986 až 1988 tuto funkci s některými modifikacemi používaly takové firmy jako Pixar, Alias, SoftImage apod.
Při tvorbě textur, které by měly reprezentovat přírodní vzorky, jako je mramor, dřevo či mraky, není možné použít ani klasický generátor pseudonáhodných čísel RNG (tím je myšlena například funkce rand() ze standardní céčkové knihovny), ale ani základní matematické funkce. V minulosti byly prováděny pokusy o využití goniometrických funkcí, které posléze vyústily v úspěšnou metodu generování plasmy pomocí Fourierovy syntézy. Tuto metodu jsme si již popisovali v předcházejících kapitolách spolu s metodou přesouvání prostředního bodu (midpoint displacement). Při přímé aplikaci generátorů pseudonáhodných čísel sice získáme šum, ten je však příliš náhodný a vůbec se nehodí pro generování textur, a to ani po své filtraci.
Perlin pro účely vytváření přírodních textur navrhl výpočet, který sice využívá generátor pseudonáhodných čísel, ale mezi jednotlivými vypočtenými náhodnými hodnotami je prováděna interpolace, která výsledný průběh funkce vyhladí, takže se již nebude jednat o zcela náhodný šum. Pro vyhlazení je možné použít velké množství matematických funkcí, od jednoduché lineární interpolace přes kvadratické a kubické funkce až po funkce goniometrické a jejich vzájemné kombinace. Perlin použil (pokud celý popis jeho postupu značně zjednodušíme) dvojici funkcí, první nazvanou s_curve() a druhou nazvanou lerp(). Při výpočtu šumu je nejdříve použita funkce s_curve(), posléze se získají dvě náhodné hodnoty a na výsledek je aplikována funkce lerp().
Takto vypočtený šum se však většinou nepoužívá přímo; místo toho je sečteno více těchto šumů s rozdílnou „frekvencí“ (nejedná se však o periodickou funkci, proto ty uvozovky). Čím vyšší je frekvence šumových průběhů, tím nižší je i jejich amplituda. Zájemci o Perlinovu šumovou funkci se mohou podívat na 71 a 72 část tohoto seriálu, kde jsou uvedeny i demonstrační příklady napsané v céčku a podrobnější vysvětlení práce šumové funkce.
8. Obsah dalšího pokračování tohoto seriálu
V následujícím pokračování tohoto seriálu si řekneme, kde se můžeme (samozřejmě kromě počítačové grafiky) setkat s fraktály, resp. s objekty či jevy, které vykazují fraktální charakteristiky. Uvidíme, že fraktální struktury lze nalézt jak v živé, tak i v neživé přírodě, a jejich využití je možné v technice, medicíně i biologii.
