Hlavní navigace

Závorkové a stochastické L-systémy

Pavel Tišnovský 14. 11. 2006

V dnešní části seriálu dokončíme popis tvorby dvourozměrných L-systémů. Ukážeme si práci s takzvanými závorkovými L-systémy, které je možné použít pro vytváření rozvětvujících se struktur, tj. zejména stromů a keřů. Na závorkové L-systémy navážeme popisem jednoduchých stochastických L-systémů a také si řekneme, jak lze alespoň přibližně simulovat vliv gravitace.

Obsah

1. Větvící se struktury – zásobník v želví grafice
2. Závorkové L-systémy
3. První demonstrační příklad – fraktální stromy a keře
4. Vnesení náhody do vytváření L-systému: stochastické L-systémy
5. Náhodná změna kroku želvy
6. Náhodná změna natočení želvy
7. Druhý demonstrační příklad – stochastické fraktální stromy
8. Obsah dalšího pokračování tohoto seriálu

1. Větvící se struktury – zásobník v želví grafice

V předchozích třech částech seriálu pojednávajícího o fraktálech jsme si podrobně popisovali některé významné fraktální útvary vytvořené pomocí L-systémů. Všechny uvedené L-systémy měly jeden společný příznak – netvořily a ani nemohly tvořit rozvětvující se struktury. Buď se jednalo o spojité křivky, například o dračí křivku (dragon curve), křivku Hilbertovu či křivku Helge von Kocha, nebo o úsečku „rozbitou“ do jednotlivých bodů v případě Cantorovy množiny. Tuto žádoucí funkcionalitu – tj. tvorbu větvících se struktur – jsme nemohli splnit z toho prostého důvodu, že želva, která L-systémy na základě vytvořeného řetězce vykreslovala, neměla k dispozici žádnou paměť, do které by si ukládala svůj předchozí stav (stavy), tj. pozici v rovině a svoji orientaci.

fractals55_1

Obrázek 1: Základní větvící se L-systém: binární strom

Samozřejmě je možné požadovanou paměť „nesystémově“ doplnit do ovládacího programu, například tak, že interpretace částí přepisovacího řetězce bude probíhat rekurzivně. Toto rozšíření má dosti závažnou nevýhodu v tom, že není popsatelné (nebo je velmi těžko popsatelné) pomocí přepisovacích pravidel v gramatice, což znamená, že pro každý L-systém by bylo zapotřebí upravit i generující program, nebo do tohoto programu kromě gramatiky předávat i další informace o tom, kdy má rekurze proběhnout. Ukazuje se však, že existuje jedno řešení, které je dostatečně jednoduché na programovou implementaci želví grafiky a přitom snadno pochopitelné i pro tvůrce L-systémů, kteří pracují s přepisovacími gramatikami. Zmiňované řešení spočívá v zavedení zásobníku (stack), do kterého je při interpretaci přepisovaného řetězce ukládán stav či více stavů želvy.

fractals55_2

Obrázek 2: Jednoduchý model keře vytvořený pomocí L-systému

Stavy želvy uložené na zásobník mohou být kdykoli později vybrány – při této operaci se želva vrátí na zapamatované místo v ploše či prostoru a obnoví přitom i svoji orientaci, tj. natočení svého těla vůči souřadným osám. Zásobník implementovaný v želví grafice se vyznačuje tím, že jsou nad ním definovány pouze dvě základní operace: uložení stavu želvy na vrchol zásobníku (push state) a vyjmutí nejpozději uloženého stavu želvy z vrcholu zásobníku spolu s případným posunem a natočením želvy (pop state). Další typické operace pro datovou strukturu zásobník, jak je můžeme znát například z programovacího jazyku PostScript či Forth, nemusí být v případě želví grafiky implementovány. Rozšíření želví grafiky o zásobník však nedostačuje, protože musíme patřičným způsobem rozšířit i gramatiku. To je téma následující kapitoly.

fractals55_3

Obrázek 3: Složitější model keře vytvořený pomocí L-systému

2. Závorkové L-systémy

předchozí kapitole jsme si řekli, že pro účely větvících se struktur byla želví grafika doplněna o zásobník fungující jako lokální paměť želvy. Na straně přepisovací gramatiky musí také dojít k rozšíření, které je však velmi jednoduché. Do množiny terminálních symbolů (symbolů, které nejsou přepisovány, tj. nevyskytují se na levé straně přepisovacích pravidel) jsou doplněny dva znaky. Prvním znakem je „[“, který při interpretaci řetězce přikazuje želvě, že má na zásobník uložit svůj stav (push state). Druhým znakem je „]“, který želvě říká, že má ze zásobníku získat posledně uložený stav a přesunout se na přečtené pozice spolu se změnou natočení (pop state). Poznamenejme, že i v případě trojrozměrných L-systémů mají tyto dva terminální symboly shodný význam, ovšem s tím, že stav želvy je popsán pomocí trojice vektorů.

fractals55_4

Obrázek 4: Větvička vytvořená závorkovým L-systémem

Tvar znaků určených pro popsání obou zmiňovaných „zásobníkových“ operací nebyl vybrán náhodně, protože při zápisu gramatik se mezi znaky [ a ] vkládají relativně samostatné sekvence příkazů, které ve výsledku neovlivní stav želvy – želva se po interpretaci řetězce uloženého mezi [] vrátí do původní pozice. Proto můžeme obě operace považovat za jakési instrukce skoku do podprogramu a návratu z podprogramu, což ostatně hranaté závorky evokují. V literatuře se L-systémy rozšířené o výše uvedenou dvojici terminálních symbolů nazývají závorkové L-systémy (bracketed L-systems), původní L-systémy popisované v předchozích dílech se pak označují jako dL0-systémy (deterministické L-systémy nultého řádu).

fractals55_5

Obrázek 5: Variace na binární strom

3. První demonstrační příklad – fraktální stromy a keře

V dnešním prvním demonstračním příkladu je ukázána implementace závorkového L-systému, který slouží pro vytváření několika jednoduchých plošných modelů stromů a keřů. Funkce určené pro provádění příkazů želví grafiky jsou rozšířeny o uložení stavu želvy a pro získání tohoto stavu ze zásobníku. Samotný zásobník je implementován pomocí jednosměrně vázaného lineárního seznamu obsluhovaného funkcemi stack_init(), stack_push() a stack_pop(). Každý prvek v tomto seznamu, jenž je představován datovou strukturou t_state, obsahuje ukazatel na prvek uložený v zásobníku o jednu pozici níže, prvně vložený prvek obsahuje ukazatel obsahující hodnotu NULL. V proměnné nazvané sp je uložen ukazatel na vrchol zásobníku (stack base).

Místo pouhého jednoho L-systému je možné pomocí tohoto demonstračního příkladu vytvářet L-systémů sedm. Každý ze zmíněných sedmi L-systémů má různý tvar a počet přepisovacích pravidel, rozdílné axiomy (řetězce, které se mají přepisovat) i úhly, o které se želva otáčí při provádění příkazů „+“ a „-“. Výběr L-systému, který se má zobrazit, se provádí pomocí funkčních kláves F1F7. Zápis více L-systémů je poměrně přímočarý – axiomy se zapisují do pole axioms, úhly natáčení želvy do pole deltas a přepisovací pravidla do dvourozměrného pole rules. O indexaci správného L-systému se stará proměnná currentSystem. Zdrojový kód prvního demonstračního příkladu je dostupný jak v ASCII podobě, tak i jako HTML stránka se zvýrazněnou syntaxí. Ovládání prvního demonstračního příkladu se provádí pomocí několika kláves vypsaných v následující tabulce:

Klávesa Význam
1–9 celkový počet iterací (přepisů řetězce) je nastaven na 1 až 9
Q okamžité ukončení běhu aplikace
Esc okamžité ukončení běhu aplikace
Page Up zvýšení hodnoty kroku želvy o 0,5 (zvětšení obrazce)
Page Down snížení hodnoty kroku želvy o 0,5 (zmenšení obrazce)
Left změna počátečního umístění želvy směrem doleva o 5 pixelů
Right změna počátečního umístění želvy směrem doprava o 5 pixelů
Up změna počátečního umístění želvy směrem nahoru o 5 pixelů
Down změna počátečního umístění želvy směrem dolů o 5 pixelů
F1 výběr závorkového L-systému číslo 1
F2 výběr závorkového L-systému číslo 2
F3 výběr závorkového L-systému číslo 3
F4 výběr závorkového L-systému číslo 4
F5 výběr závorkového L-systému číslo 5
F6 výběr závorkového L-systému číslo 6
F7 výběr závorkového L-systému číslo 7

fractals55_6

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

4. Vnesení náhody do vytváření L-systému: stochastické L-systémy

Pokud budeme pomocí prvního demonstračního příkladu vytvářet L-systémy v podobě stromů a keřů, zjistíme, že oproti přírodním objektům se algoritmicky vytvořené objekty liší především v tom, že přírodní objekty nejsou zcela pravidelné, ale obsahují jisté náhodné prvky (ty však nemění celkový geometrický ani topologický tvar objektu). V minulosti bylo navrženo i implementováno velké množství metod, které se snažily do co největší míry napodobit skutečný přírodní tvar objektů; L-systémy vybavené těmito metodami se nazývají stochastické L-systémy. Některé z metod simulujících určitou náhodnost přírodních objektů si popíšeme v následujících částech věnovaných prostorovým (3D) L-systémům. Jedná se například o takzvané mutace či simulaci vlivu gravitace při konstrukci 3D modelu. V dnešní části budou popsány dvě velmi jednoduché metody, které spočívají v úpravě příkazů pro želvu, samotná gramatika L-systému se přitom měnit nemusí.

fractals55_7

Obrázek 7: Vliv náhodných hodnot na tvar binárního stromu

5. Náhodná změna kroku želvy

Pravděpodobně nejjednodušší metodou, kterou je možné nějaký pravidelný L-systém do určité míry „znáhodnit“ (ne znárodnit :-), je úprava funkcí, které slouží pro posun želvy. Jedná se o funkce logo_forward(), logo_backward a logo_move(), jež odpovídají znakům „F“, „B“ a „G“, které želva při čtení výsledného řetězce dokáže interpretovat. Místo pevně zadaného a v rámci jednoho L-systému neměnného kroku, který byl původně uložen v proměnné step se při každém volání výše uvedené trojice funkcí vypočte částečně náhodná hodnota kroku rndStep a tato hodnota je použita při přímém či zpětném pohybu želvy. Výpočet částečně náhodného kroku želvy zajišťuje funkce randomStep(), která může mít následující tvar:

//-----------------------------------------------------------------------------
// Výpočet kroku želvy s využitím céčkovského generátoru náhodných čísel
//-----------------------------------------------------------------------------
double randomStep(double step, double stepDelta)
{
    return step*(1.0+stepDelta*((double)rand()/RAND_MAX-1/2.0));
} 

Ze zápisu funkce randomStep() vidíme, že se při výpočtu kroku využívá funkce rand() ze standardní knihovny programovacího jazyka C. Náhodná hodnota z rozsahu <0,1) je posunuta o 1/2, tj. ve výsledku získáme náhodnou hodnotu ležící v rozsahu ← 1/2, 1/2). Tato hodnota je vynásobena obsahem proměnné stepDelta, která udává míru náhodnosti výsledného obrazce. Funkce logo_forward(), logo_backward a logo_move() se změní pouze nepatrně:

//-----------------------------------------------------------------------------
// Posun želvy dopředu s kreslením
//-----------------------------------------------------------------------------
void logo_forward(void)
{
    double rndStep=randomStep(step, stepDelta);
    glBegin(GL_LINES);
    glVertex2d(x,y);                               // původní pozice želvy
    x+=rndStep*cos(alpha);                         // posun želvy v zadaném směru
    y+=rndStep*sin(alpha);
    glVertex2d(x,y);                               // nová pozice želvy
    glEnd();
}



//-----------------------------------------------------------------------------
// Posun želvy dozadu s kreslením
//-----------------------------------------------------------------------------
void logo_backward(void)
{
    double rndStep=randomStep(step, stepDelta);
    glBegin(GL_LINES);
    glVertex2d(x,y);                               // původní pozice želvy
    x-=rndStep*cos(alpha);                         // posun želvy v zadaném směru
    y-=rndStep*sin(alpha);
    glVertex2d(x,y);                               // nová pozice želvy
    glEnd();
}



//-----------------------------------------------------------------------------
// Posun želvy dopředu bez kreslení
//-----------------------------------------------------------------------------
void logo_move(void)
{
    double rndStep=randomStep(step, stepDelta);
    x+=rndStep*cos(alpha);                         // posun želvy v zadaném směru
    y+=rndStep*sin(alpha);
} 

6. Náhodná změna natočení želvy

Podobně jako náhodnou změnu kroku želvy při interpretaci řetězce můžeme měnit i úhel jejího natočení. V předchozích příkladech se želva při přijetí příkazů „+“ a „-“ vždy natočila o předem známý úhel, například o 60° v případě křivky Helge von Kocha. Ve stochastických L-systémech je možné úhel natočení želvy (přesněji řečeno změnu úhlu natočení) modifikovat náhodnou hodnotou tak, jak je naznačeno na níže uvedené funkci randomAngle():

//-----------------------------------------------------------------------------
// Výpočet změny úhlu želvy s využitím RNG
//-----------------------------------------------------------------------------
double randomAngle(double angle, double angleDelta)
{
    return angle*(1.0+angleDelta*((double)rand()/RAND_MAX-1/2.0));
} 

Tato funkce se v mnohém podobá funkci randomStep(), ovšem s tím rozdílem, že místo nastavené hodnoty kroku a maximální změny kroku se předávají hodnoty o úhlech. Funkce provádějící natočení želvy, tj. logo_left() a logo_right() se změní pouze nepatrně – místo přečtení a použití konkrétní hodnoty úhlu z pole deltas (to obsahuje úhly pro více L-systémů) je tento úhel modifikován podle obsahu proměnné angleDelta. Pokud je hodnota této proměnné nulová, zůstane načtený úhel nezměněn:

//-----------------------------------------------------------------------------
// Otočení želvy doleva
//-----------------------------------------------------------------------------
void logo_left(void)
{
    alpha+=randomAngle(deltas[currentSystem], angleDelta);  // změna úhlu
}



//-----------------------------------------------------------------------------
// Otočení želvy doprava
//-----------------------------------------------------------------------------
void logo_right(void)
{
    alpha-=randomAngle(deltas[currentSystem], angleDelta);  // změna úhlu
} 

7. Druhý demonstrační příklad – stochastické fraktální stromy

V dnešním druhém demonstračním příkladu jsou implementovány obě výše zmíněné metody tvorby stochastických L-systémů. Jedná se jak o náhodnou změnu kroku želvy (kapitola pátá), tak i o náhodnou změnu natočení želvy (šestá kapitola). Ovládání tohoto příkladu je rozšířené o čtyři klávesy: „A“, „S“, „Z“ a „X“. Tyto klávesy slouží ke změně hodnot proměnných stepDelta a angleDelta, celé ovládání je popsáno ve druhé tabulce:

Klávesa Význam
1–9 celkový počet iterací (přepisů řetězce) je nastaven na 1 až 9
Q okamžité ukončení běhu aplikace
Esc okamžité ukončení běhu aplikace
Page Up zvýšení hodnoty kroku želvy o 0,5 (zvětšení obrazce)
Page Down snížení hodnoty kroku želvy o 0,5 (zmenšení obrazce)
Left změna počátečního umístění želvy směrem doleva o 5 pixelů
Right změna počátečního umístění želvy směrem doprava o 5 pixelů
Up změna počátečního umístění želvy směrem nahoru o 5 pixelů
Down změna počátečního umístění želvy směrem dolů o 5 pixelů
A snížení hodnoty angleDelta o 0,1
S zvýšení hodnoty angleDelta o 0,1
Z snížení hodnoty stepDelta o 0,1
X zvýšení hodnoty stepDelta o 0,1
F1 výběr závorkového L-systému číslo 1
F2 výběr závorkového L-systému číslo 2
F3 výběr závorkového L-systému číslo 3
F4 výběr závorkového L-systému číslo 4
F5 výběr závorkového L-systému číslo 5
F6 výběr závorkového L-systému číslo 6
F7 výběr závorkového L-systému číslo 7

fractals55_8

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

Zdrojový kód druhého demonstračního příkladu je dostupný jak v ASCII podobě, tak i jako HTML stránka se zvýrazněnou syntaxí.

fractals55_9

Obrázek 9: Další screenshot druhého demonstračního příkladu

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

V následují části tohoto seriálu se začneme zabývat pravděpodobně nejpraktičtějším využitím L-systémů. Bude se jednat o trojrozměrné (3D) L-systémy, které se dnes používají pro tvorbu mnoha 3D modelů, jak v počítačových hrách, tak i například v architektuře. Na závěr si ukážeme rozšíření gramatiky o další dva důležité symboly „@“ a „C“ a využití těchto symbolů při tvorbě různých dlaždicovitých vzo­rů.

Našli jste v článku chybu?

20. 11. 2006 9:54

Ano, chapete to dobre, stacilo by ukladat pozici zelvy a pomoci trech uhlu jeji orientaci. Je to sice "datove" nejmensi mozne reseni, ale moc se neujalo, protoze pri implementaci je slozite zelvou dale natacet. Misto toho se voli vlastni souradny system zelvy urceny tremi vektory (forward, left, up). Nataceni zelvy pak zajisti matice rotace, kterou se dane vektory vynasobi. Vzhledem k tomu, ze ty vektory jsou jednotkove a na sebe kolme, je mozne jeden dopocitavat: forward x left=up.

16. 11. 2006 16:36

ph (neregistrovaný)
Aha, děkuji, četl jsem to jen zběžně a neuvědomil si, že tam ještě jde o orientaci želvy v prostoru. Ale stejně, k jejímu popisu by snad stačila rovina pohybu želvy (dva úhly) plus orientace v této rovině (třetí úhel)? Jinými slovy, ve 3D má želva 6 stupňů volnosti, nebo to pořád chápu špatně? -- Samozřejmě nechci polemizovat o tom, že může být jednodušší ukládat o tři čísla více než něco přepočítávat.
Vitalia.cz: Jak koupit Mikuláše a nenaletět

Jak koupit Mikuláše a nenaletět

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

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Vitalia.cz: Vláknina: Rozpustná, nebo nerozpustná?

Vláknina: Rozpustná, nebo nerozpustná?

Podnikatel.cz: Platební brány a EET? Stále s otazníkem

Platební brány a EET? Stále s otazníkem

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

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

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

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

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

Sony KD-55XD8005 s Android 6.0

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

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

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

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

Vypadl Google a rozbilo se toho hodně

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

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

Rakovina oka. Jak ji poznáte?

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

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

Podnikatel.cz: Dárky v podnikání. Jak je uplatnit v daních?

Dárky v podnikání. Jak je uplatnit v daních?

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

Jsou čajové sáčky toxické?