L-systém: Porovnání verzí

Smazaný obsah Přidaný obsah

V textu

Aktuální verze z 19. 7. 2021, 13:08

L-systém nebo také Lindenmayerův systém je varianta formální gramatiky, vyvinutá pro modelování růstu rostlin. L-systém popisuje pravidla pro vývoj rostliny, která se opakovaně aplikují na vznikající model. Tato pravidla mohou např. popisovat, za jakých podmínek se stonek rostliny rozdvojí, zda má vzniknout list nebo zda má část rostliny uhynout. Výsledný model se může např. vykreslit jako obrázek nebo se z něj vytvoří počítačový 3D model rostliny. L-systémy se také dají použít pro generování různých křivek, fraktálů nebo pro modelování buněčných organismů. ^[1]

Historie[editovat | editovat zdroj]

L-systémy byly vyvinuty v roce 1968 maďarským biologem Aristidem Lindenmayerem jako matematický formalizmus pro popisování růstu řas. ^[2] Symboly představovaly jednotlivé buňky a přepisovací pravidla L-systému simulovaly jejich dělení. Později polský informatik Przemyslaw Prusinkiewicz interpretoval symboly L-systémů pomocí želví grafiky (tedy symboly představovaly grafické elementy jako např. úsečky). Touto metodou se již dalo modelovat širší spektrum rostlin a různé fraktálové křivky. ^[3] Lindenmayer spolu s Prusinkiewiczem publikovali knihu The Algorithmic Beauty of Plants^[4], která se dnes dá považovat za bibli L-systémů.

Postupem času se L-systémy začaly používat i pro další věci než je modelování rostlin a fraktálů. Například jde pomocí nich modelovat tok řek ve fraktálových horách^[5], ulice ve virtuálních městech^[6] nebo pomocí L-systémů lze popisovat podrozdělování (zjemňování) křivek^[7]. Nicméně L-systémy mohou být použity i v jiných oborech než je počítačová grafika, například lze pomocí nich generovat hudbu^[8]^[9].

Ve filmu Avatar z roku 2009 bylo přes 2000 stromů, rostlin a kapradin vymodelováno právě pomocí L-systémů.^[10]

Definice L-systému[editovat | editovat zdroj]

Základní typ L-systému je tzv. D0L-systém. D0 v názvu značí, že se jedná o deterministický bezkontextový L-systém. Formálně je to trojice $G=(\Sigma ,S,P)$ ^[4], kde

$\Sigma$ je abeceda, tj. neprázdná množina symbolů, $\Sigma ^{*}$ je množina všech slov nad abecedou $\Sigma$ , $\Sigma ^{+}$ je množina všech neprázdných slov nad abecedou $\Sigma$ ,
$S\in \Sigma ^{+}$ je semínko (z angl. seed) nebo také axiom, což je konečné slovo z abecedy $\Sigma$ , které definuje počáteční stav L-systému,
$P\subset \Sigma \times \Sigma ^{*}$ $P\subset \Sigma \times \Sigma ^{*}$ je konečná množina přepisovacích pravidel,
- přepisovací pravidlo se zapisuje ve tvaru $a\rightarrow S$ , kde $a\in \Sigma$ a $S\in \Sigma ^{*}$ , definuje tedy přepsání symbolu na slovo (které může být i prázdné),
- pro symbol $b\in \Sigma$ , který se neobjevuje na levé straně žádného přepisovacího pravidla, je definována identita ( $b\rightarrow b$ ) (takové symboly jsou často označovány jako konstanty).

D0L-systém je velice podobný deterministické bezkontextové gramatice. Liší se například v tom, že gramatika rozlišuje terminální a neterminální symboly, ale L-systém pro neterminály definuje identitu jako výchozí přepisovací pravidlo. Další rozdíl je v tom, že gramatika má jako semínko jeden neterminální symbol, ale L-systém povoluje neprázdné slovo (libovolný konečný řetězec symbolů).

Každý symbol z abecedy je obvykle reprezentován jedním znakem (písmenem), což značně ulehčuje a zrychluje zápis. Avšak existují i speciální symboly, které jsou zapsány více znaky. Jsou to většinou velmi specifické symboly pro interpretaci. Aby se rozlišily vícepísmenné symboly, dává se před ně nějaký speciální prefix, např. zavináč. Ten pak není součástí abecedy. ^[11]

Iterativní vývoj L-systému[editovat | editovat zdroj]

L-systém se vytváří po iteracích, někdy zvaných též generace. N-tá generace je definována rekurzivními pravidly:

nultá iterace je samotný axiom
n-tá iterace (pro $n>0$ ) vznikne paralelní aplikací přepisovacích pravidel na výsledek iterace $n-1$

Paralelní aplikace je nahrazení všech symbolů „najednou“. Paralelní přepsání se dá provést i sériově, a sice tak, že se postupně přepisují symboly zleva doprava, ale výsledek se ukládá na jiné místo (nevkládá se jako náhrada přepisovaného symbolu). Tak se docílí toho, že symboly vzniklé přepsáním se nepřepíší podruhé.

Příklad 1: růst řas[editovat | editovat zdroj]

Následující příklad je Lindenmayerův původní L-systém pro modelování růstu řas (konkrétně Anabaena catenula). Tato řasa má dva typy buněk, které tvoří řetízky. Každý typ se vyznačuje odlišným chováním, které probíhá ve fázích. Následující L-systém zachycuje právě toto chování.

gramatika
abeceda:	`A B`
axiom:	`A`
přepis. pravidla:	`A` → `AB`
	`B` → `A`

Jednotlivé iterace vypadají následovně:

i = 0 : A

i = 1 : AB

i = 2 : ABA

i = 3 : ABAAB

i = 4 : ABAABABA

i = 5 : ABAABABAABAAB

i = 6 : ABAABABAABAABABAABABA

i = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Procentuální zastoupení A : B inklinuje k poměru 61,8034 : 38,1966 %.

Příklad 2: Fibonacciho posloupnost[editovat | editovat zdroj]

Mějme následující gramatiku:

gramatika
abeceda:	`A B`
axiom:	`A`
přepis. pravidla:	`A` → `B`
	`B` → `AB`

Oproti 1. příkladu se liší pouze v prohození vzorů přepisovacích pravidel, nicméně výsledek bude odlišný.

i = 0 : A

i = 1 : B

i = 2 : AB

i = 3 : BAB

i = 4 : ABBAB

i = 5 : BABABBAB

i = 6 : ABBABBABABBAB

i = 7 : BABABBABABBABBABABBAB

Zajímavé na tomto L-systému je to, že délka výsledného řetězce v i-té iteraci je rovna i-tému číslu ve Fibonacciho posloupnosti (pro ${\text{fib}}(0)=1$ a ${\text{fib}}(1)=1$ ):

1, 1, 2, 3, 5, 8, 13, 21, …

Výstupní řetězec má stejnou vlastnost, která platí pro Fibonacciho posloupnost, tj. i-té číslo ( $i>1$ ) je součtem předchozích dvou. Tedy i-tá iterace tvořena spojením iterací $i-2$ a $i-1$ . Malou změnou druhého přepisovacího pravidla na (B → BA) bude výsledek splňovat stejné vlastnosti jako původní, jen se budou iterace spojovat „popořadě“, tedy i-tá iterace bude tvořena spojením iterací $i-1$ a $i-2$ . Z toho vyplývá i to, že délky jednotlivých iterací budou také odpovídat číslům ve Fibonacciho posloupnosti. Tato odlišnost ve Fibonacciho posloupnosti není, protože sčítání dvou čísel je komutativní.

Další zajímavou vlastností řetězců v příkladech 1 a 2 je úzká souvislost se zlatým řezem. Pro $i>0$ platí, že symbol na k-tém místě od neměnného konce („začátek“ u př. 1, „konec“ u př. 2) je buď A nebo B, podle toho, zda nějaký celočíselný násobek zlatého řezu padne (náleží) do otevřeného intervalu $(k,k+1)$ . Poměr počtu symbolů A a B tedy pro $i\rightarrow \infty$ konverguje k hodnotě zlatého řezu

$\varphi ={1+{\sqrt {5}} \over 2}\approx 1,618.$

V následující tabulce je tato vlastnost konkrétně ukázána na L-systému Fibonacciho posloupnosti.

k	k-tý symbol	interval	nás. zl. řezu	matematický důvod
1	B	(1, 2)	1	$\varphi \approx 1,6181\in (1,2)$
2	A	(2, 3)	neexistuje	$\varphi \approx 1,618\notin (2,3)$ a $2\varphi \approx 3,236\notin (2,3)$
3	B	(3, 4)	2	$2\varphi \approx 3,236\in (3,4)$
4	B	(4, 5)	3	$3\varphi \approx 4,854\in (4,5)$
5	A	(5, 6)	neexistuje	$3\varphi \approx 4,854\notin (5,6)$ a $4\varphi \approx 6,472\notin (5,6)$
6	B	(6, 7)	4	$4\varphi \approx 6,472\in (6,7)$

Interpretace symbolů[editovat | editovat zdroj]

Jednotlivé symboly L-systému se mohou interpretovat jakkoli. U některých L-systémů je podstatný pouze počet symbolů v i-té iteraci, u jiných se symboly chápou jako příkazy pro kreslení nebo dokonce mohou reprezentovat základní části rostliny (např. jako 3D modely), ze kterých se „poskládá“ výsledný model.

Vykreslování ve 2D[editovat | editovat zdroj]

Obvyklá (a jedna z nejjednodušších) je interpretace pomocí želví grafiky. Tato interpretace chápe symboly jako příkazy pro štětec (želvu nesoucí štětec), který podle nich kreslí úsečky a vyplněné polygony v rovině. Interpretace probíhá dvoufázově, nejprve se L-systém vygeneruje (vyiteruje) do požadované iterace a poté se výsledek interpretuje (kreslí). Pro první fázi musí být zadán počet iterací a pro druhou výchozí stav štětce (želvy). Ten v nejjednodušší variantě obsahuje délku kroku a úhel otočení štětce, ale může obsahovat i různé další údaje, jako např. barvu nebo šířku štětce. Během druhé fáze interpretace je také udržován stav štětce v rovině, tedy v jakém místě se nachází a jak je orientován. V následující tabulce je shrnuta obvyklá interpretace symbolů ve druhé fázi. Tyto příkazy dávají rozkazy štětci (želvě).

Symboly	Interpretace
`A`-`U`, `0`-`9`	„Nakresli úsečku.“, úsečka je nakreslena ve směru orientace štětce (délka úsečky je délka kroku)
`a`-`u`	„Pohni se vpřed (bez kreslení).“ (délka pohybu je délka kroku)
`V`-`Z`, `v`-z	„Nedělej nic.“, obvykle se jedná o písmena ke konci abecedy, hranice není ustálena (používá se pro potřeby vývoje L-systému)
`+`, `-`	„Otoč se doleva (resp. doprava) o předem stanovený úhel.“ (o úhel otočení)
`\|`	„Otoč se čelem vzad.“ (rotace o 180°)
`[`	„Zapamatuj si aktuální stav.“, přesněji řečeno „Ulož aktuální stav na zásobník.“ (stavem se myslí aktuální poloha a orientace v rovině)
`]`	„Přesuň se na naposledy zapamatovaný stav.“, přesněji řečeno „Přesuň se na pozici, kterou určuje stav na vrcholu zásobníku a ten z vrcholu odstraň“
`{`	„Ulož rozpracovaný polygon na zásobník a začni zaznamenávání bodů nového polygonu.“
`.`	„Přidej bod, na kterém stojíš do aktuálního polygonu.“
`}`	„Vykresli rozpracovaný polygon a načti polygon z vrcholu zásobníku jako aktuální polygon (pokud tam nějaký je).“

Pokud nebude uvedeno jinak, tato interpretace je použita u všech ukázek v tomto článku.

Vykreslování ve 3D[editovat | editovat zdroj]

Výše uvedená 2D interpretace se dá jednoduše rozšířit do 3D. Štětec se bude pohybovat v prostoru místo v rovině. Stav bude podobný, tedy bude to poloha a orientace v prostoru. Pro pohyb v trojrozměrném prostoru je třeba více příkazů pro otočení, protože se dá otáčet podle 3 os (ve 2D je pouze 1 osa). V následující tabulce je seznam interpretací symbolů, které je potřeba přidat.

Symboly	Interpretace
`+`, `-`	„otoč se doleva (resp. doprava) o předem stanovený úhel“ (stejné jako ve 2D), pokud si představíte štětec jako letadlo a směr štětce jako směr letu letadla, pak tyto symboly představují zahýbání letadla doleva a doprava, z pohledu pilota (angl. yaw viz obr.)
`^`, `&`	„otoč se nahoru (resp. dolů) o předem stanovený úhel“, u letadla by to znamenalo stoupání a klesání (angl. pitch viz obr.)
`/`, `\`	„otoč se doleva (resp. doprava) podle osy určené mým směrem o předem stanovený úhel“, u letadla by tyto příkazy vypadaly jako „výkrut“, otáčení podél osy letu (angl. roll viz obr.)

Příklady L-systémů[editovat | editovat zdroj]

Kochova vločka[editovat | editovat zdroj]

Animace interpretace L-systému želví grafikou

Následující předpis vygeneruje část Kochovy vločky.

gramatika
abeceda:	`F + -`
axiom:	`F`
přepis. pravidla:	`F` → `F+F--F+F`
interpretace
úhel otočení:	60°

pozn.: výchozí poloha štětce (želvy) je vlevo dole a štětec je orientován vpravo

i = 0: F

i = 1: F+F--F+F

i = 2: F+F--F+F + F+F--F+F-- F+F--F+F + F+F--F+F

i = 3: F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F + F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F -- F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F + F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F

Stromeček[editovat | editovat zdroj]

L-systémy byly vytvořeny pro modelování růstu rostlin. Vymodelovat jednoduchý stromeček je proto velmi jednoduché.

gramatika
abeceda:	`M S + - [ ]`
axiom:	`M`
přepis. pravidla:	`M` → `S[+M][-M]SM`
	`S` → `SS`
interpretace
úhel otočení:	45°

Přepisovací pravidla by se dala popsat slovy takto:

symbol M představuje mladou část rostliny (na obr. zeleně), symbol S starou část (hnědě)
první přepisovací pravidlo říká, že každá mladá část M se přepíše (nahradí) za starou část S, pak dvě mladé větvičky vlevo ([+M]) a vpravo ([-M]), dále starou část S a nakonec mladou část M
druhé říká pouze to, že každá stará část S se přepíše na dvě staré části SS, jinými slovy, délka starých částí se mezi iteracemi zdvojnásobí

Na následujícím obrázku můžete vidět prvních 6 iterací i s grafickým znázorněním přepisovacích pravidel.

Ostrovy a jezera[editovat | editovat zdroj]

Graficky znázorněné přepisovací pravidlo L-systému Ostrovy a jezera

Další fraktál generovaný pomocí L-systémů se jmenuje „Ostrovy a jezera“ (z angl. „Islands and lakes“). Jeho předpis můžete také nalézt v knize The Algorithmic Beauty of Plants na str. 9.^[4]

gramatika
abeceda:	`F f + -`
axiom:	`F+F+F+F`
přepis. pravidla:	`F` → `F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF`
	`f` → `ffffff`
interpretace
úhel otočení:	90°

Výše uvedený předpis pro jednoduchost kreslí pouze hranice ostrovů a jezer. Avšak pro lepší představu byl následující obrázek vygenerován rozšířeným předpisem o příkazy, které generují polygony.

Penroseovo dláždění[editovat | editovat zdroj]

Pomocí složitějšího L-systému se dá generovat Penroseovo dláždění.

{{L-systém | abeceda = M N O P + - [ ] { . } | axiom = [N]++[N]++[N]++[N]++[N] | rrp0 = M | rrr0 = O++{.P.----N.[-O.----M.}]++ | rrp1 = N | rrr1 = +{.O.--P.[---M.--N.}]+ | rrp2 = O | rrr2 = -{.M.++N.[+++O.++P.}]- | rrp3 = P | rrr3 = --{.O.++++M.[+P.++++N.}]--N | uhel = 36 }} pozn.: vykreslování úseček proběhne až po vykreslení všech polygonů (aby je polygony nepřekryly)

0. generace
1. generace
2. generace
3. generace
4. generace

Gosperova křivka[editovat | editovat zdroj]

Vizualizace přepisovacího pravidla Gosperovy křivky

Následující křivka, která je pojmenovaná po americkém matematikovi a programátorovi jménem Bill Gosper, splňuje definici plochu-vyplňující křivky a také FASS křivky.

gramatika
abeceda:	`L R + -`
axiom:	`L`
přepis. pravidla:	`L` → `L+R++R-L--LL-R+`
	`R` → `-L+RR++R+L--L-R`
interpretace
úhel otočení:	60°

Na následujícím obrázku je 5. iterace Gosperovy křivky plynule obarvena celým barevným spektrem od červené až po fialovou. Díky tomu lze vidět, kudy a jak křivka vede.

Parametrické L-systémy[editovat | editovat zdroj]

Parametrický L-systém (PL-systém) je rozšíření základního L-systému o parametry symbolu. Ke každému symbolu může být asociován libovolný konečný počet parametrů. Parametr je obvykle reálné číslo, se kterým se dají dělat běžné matematické operace. Jako parametr může být dosazen i aritmetický výraz, funkce nebo proměnná. Hodnota takového parametru se vyčíslí jako reálné číslo vždy, když je třeba.

Pro zápis parametrů se používá závorková syntaxe. Hodnoty parametru se za symbol píší do kulatých závorek. Tyto závorky, ani žádné symboly v nich, se nepovažují jako symboly L-systému. Jednotlivé parametry uvnitř závorek se oddělují čárkou. V následující tabulce je uvedeno několik příkladů zápisu.

Syntaxe	Popis
`F(1)`	symbol F s parametrem 1
`F(0, 1, √2)`	symbol F s parametry 0, 1 a √2
`F(, 1)`	symbol F s 1. parametrem nezadaným a 2. parametrem 1
`F(x)`	symbol F, který má jako 1. parametr proměnnou x

Zápis přepisovacího pravidla parametrického L-systému vypadá např. takto:

A(t) → B(t/2) C(5) D E(1/t, 8).

Slovní popis: „Symbol A s parametrem t (jehož hodnota se vyčíslí jako reálné číslo) se přepíše na symbol B s parametrem $t/2$ , symbol C s parametrem $5$ , symbol D bez parametru a symbol E s parametry $1/t$ a 8.“

Interpretace[editovat | editovat zdroj]

Parametry symbolů slouží zejména pro snadné předávání číselných hodnot pro interpretaci a pro řízení vývoje L-systému. Při interpretaci symbolů želví grafikou, která se používá v tomto článku, se 1. parametr symbolů chápe následovně:

Symboly	Interpretace, kde 1. parametr má hodnotu X
`A`-`U`,`0`-`9`	„nakresli úsečku ve směru natočení o délce X“
`a`-`u`	„pohni se ve směru natočení bez kreslení o X“
`+`, `-`	„otoč se doleva (resp. doprava) o X“

Pokud u výše uvedených symbolů není 1. parametr zadán, použije se výchozí hodnota (jako u D0L-systémů), pokud nejsou zadány ostatní parametry, mají nedefinovanou hodnotu (např. NaN). Příklady:

Zápis	Interpretace
`F(1, 2)`	„nakresli úsečku ve směru natočení o délce 1“
`+(80)`	„otoč se doleva (resp. doprava) o 80°“
`F` resp. `F()`	„nakresli úsečku ve směru natočení o výchozí délce“
`+(,0)`	„otoč se doleva (resp. doprava) o výchozí úhel zadaný L-systémem“

Příklady[editovat | editovat zdroj]

10. iterace H-stromu s parametry R = 1/√2 a U = 90

Jako jednoduchý příklad parametrického L-systému poslouží fraktál jménem H-strom. Říká se mu tak proto, že pro vhodně zvolené hodnoty proměnných vypadá jako písmena H tvořená z písmen H, tvořená z písmen H…

H-strom (L-systém)
gramatika
abeceda:	`F H + - [ ]`
axiom:	`F(200)`
přepis. pravidla:	`F(l)` → `H(l) [+F(l * R)] [-F(l * R)]`
interpretace
úhel otočení:	U°

R a U jsou proměnné L-systému (nejsou to symboly abecedy, ani nemají nic společného s parametrickými L-systémy). Pro jejich různé hodnoty bude výsledek vypadat odlišně. Obvyklými hodnotami jsou R = 1/√2 a U = 90. Zajímavé je, že s těmito hodnotami tvoří H-strom plochu-vyplňující L-systém (a je dokonce v kategorii FASS). Mírně odlišný výsledek vznikne s hodnotami R = 0,69 a U = 85, na následujícím obrázku je jeho 10. iterace. Pro hodnoty proměnných R = 1/√2 a U = 45 vznikne Pythagorův strom.

Praktičtější ukázkou parametrických L-systémů je následující předpis ze str. 123^[4] a jedná se o velmi jednoduchý L-systém modelující růst listu rostliny. Čím vyšší iterace, tím vyspělejší list. Tento předpis má i své nevýhody, růst se nikdy nezastaví a pro iterace větší než 20 není použitelný. Pro ovlivnění rychlosti růstu a jeho zastavení by se dal použít složitější předpis.

List rostliny (L-systém)
gramatika
abeceda:	`F S x y z [ ] { . }`
axiom:	`[\|S(K/2)] [x] [y]`
přepis. pravidla:	`x` → `[+x{.].z.}`
	`y` → `[-y{.].z.}`
	`z` → `zF(K)`
	`S(len)` → `F(len) +(1) S(len)`
interpretace
úhel otočení:	10°

pozn.: symboly x, y, z nedělají nic, symboly F, S kreslí úsečku, viz interpretace symbolů

K je konstanta představující délku kroku. Je použita jen kvůli tomu, aby stonek (tvořený symboly S) nebyl příliš dlouhý (roste 2× pomaleji než list), může se zvolit např. 1. Na obrázku níže je 5. až 21. iterace L-systému listu.

Podmíněná přepisovací pravidla[editovat | editovat zdroj]

Parametry symbolů se také dají použít k podmínění přepsání symbolu. K tomu slouží podmíněná přepisovací pravidla. Podmíněné přepisovací pravidlo je rozšířené běžné přepisovací pravidlo o podmínku. Přepisování pak probíhá tak, že se uvedená podmínka vyhodnotí, a když je pravdivá, přepisovací pravidlo se použije. Pokud pravdivá není, hledá se další vhodné přepisovací pravidlo. Pořadí ověřování přepisovacích pravidel musí být dáno (aby se zachoval determinismus), např. od dříve uvedených pravidel k později uvedeným. Pokud symbol není přepsán žádným přepisovacím pravidlem, platí pro něj identita jako výchozí přepisovací pravidlo (je tedy zkopírován do další iterace).

25. iterace L-systému modelující list růže

Ukázkou podmíněného přepisování je list růže ze str. 126.^[4]

List růže (L-systém)
gramatika
abeceda:	`g x y [ ] { . }`
axiom:	`[{x(0,0).}] [{x(0,1).}`
přepis. pravidla:	`x(t,d)` → `. g(5, 1.15, -1) . [+y(t) g(3, 1.19, t) .}] [+y(t) {.] x(t+1, d)` pokud d = 0
	`x(t,d)` → `. g(5, 1.15, -1) . [-y(t) g(3, 1.19, t) .}] [-y(t) {.] x(t+1, d)` pokud d = 1
	`y(t)` → `g(1.3, 1.25, -1) y(t-1)` pokud t > 0
	`g(s,r,t)` → `g(sr, r, t – 1)` pokud t > 1*
	`g(s,r,t)` → `g(sr, r, -1)` pokud t = -1*
interpretace
úhel otočení:	60°

Stochastické L-systémy[editovat | editovat zdroj]

Deterministické L-systémy se vyznačují tím, že je jednoznačně definováno, jak vypadá n-tá iterace a při opakovaném výpočtu je vždy stejná. Při modelování rostlin je však žádoucí, aby se na modelu promítl nějaký prvek náhody (stochastismu). Proto se používají stochastické L-systémy (0L-systémy), které v sobě mají určitý prvek náhody, díky kterému je výsledek vždy trochu jiný. Pak se dá pomocí jednoho stochastického L-systému modelující např. strom vymodelovat celý les, který vypadá přirozeně, protože každý strom je trochu jiný.

Randomizace při interpretaci[editovat | editovat zdroj]

Nejjednoduššího stochastismu se dosáhne randomizací („znáhodnění“) změny úhlu otočení a délky kroku. Kvůli tomu není nutné zasahovat do přepisovacího systému, ten zůstane nezměněn. Změna se projeví až při interpretaci symbolů. Jako příklad je uveden Pythagorův strom s randomizací úhlu a délky kroku o ±30%.

Randomizovaný Pythagorův strom 1 (L-systém)
gramatika
abeceda:	`F L + -`
axiom:	`F(50)`
přepis. pravidla:	`F(t)` → `L(t) [+F(t / √2)] -F(t / √2)`
interpretace
úhel otočení:	45°
randomiz. úhlu:	30%
randomiz. kroku:	30%

Výsledek vykreslení bude díky stochastismu pokaždé trochu jiný, na následujícím obrázku je 9 interpretací 6. generace, uprostřed je L-systém bez randomizace.

Náhodný výběr přepisovacího pravidla[editovat | editovat zdroj]

Pokročilejšího stochastismu se u L-systémů dosahuje náhodným výběrem mezi více přepisovacími pravidly. Každé takové pravidlo má určitou váhu, která určuje, s jakou pravděpodobností se vybere. Tato váha je uvedena u každého pravidla, které je náhodné. Pravděpodobnost vybrání konkrétního pravidla je určena hodnotou váhy onoho pravidla vydělené součtem vah všech pravidel, které připadají v úvahu pro přepsání konkrétního symbolu. Pokud váhy nejsou uvedeny, ale jedná se o stochastický L-systém, všechna pravidla mají váhu (a pravděpodobnost vybrání) stejnou.

Randomizovaný Pythagorův strom 2 (L-systém)
gramatika
abeceda:	`F L + -`
axiom:	`F(50)`
přepis. pravidla:	`F(t)` ${\xrightarrow {_{2}}}$ `L(t) [+F(t / √2)] -F(t / √2)`
	`F(t)` ${\xrightarrow {_{1}}}$ `L(t) +F(t / √2)`
	`F(t)` ${\xrightarrow {_{1}}}$ `L(t) -F(t / √2)`
interpretace
úhel otočení:	45°
randomiz. úhlu:	30%
randomiz. kroku:	30%

pozn.: pravděpodobnostní váhy jsou uvedeny nad šipkami u přepisovacích pravidel

8 různých výsledků je na obrázku níže (9. uprostřed bez stochastismu).

Kontextové L-systémy[editovat | editovat zdroj]

Kontextové L-systémy mohou obsahovat přepisovací pravidla, která specifikují, jaký musí být kontext přepisovaného symbolu, aby se pravidlo použilo. Kontextem se myslí symboly před a za přepisovaným symbolem. Tím se napodobuje mechanismus, kterým rostliny řídí svůj vývoj. Ty si dokáží vyměňovat informace mezi sousedícími buňkami ve formě živin nebo hormonů^[4]. Kontextovým mechanismem se také dá simulovat napadení rostliny parazitem. ^[12]

Kontextový L-systém je velice blízký kontextové gramatice, tedy každý přepisovaný symbol má levý a pravý kontext, který je pro přepsání nutný. kontextové přepisovací pravidlo má následující zápis:

lc < S > pc → nahrada, kde

lc je levý kontext, tedy výčet symbolů, které musí být bezprostředně vlevo od přepisovaného symbolu S,
S je přepisovaný symbol,
pc je pravý kontext, tedy výčet symbolů, které musí být bezprostředně vpravo od přepisovaného symbolu S,
nahrada jsou symboly, za které se S přepíše.

1L-systémy[editovat | editovat zdroj]

Označení 1L-systém se používá pro kontextový L-systém, který má kontextová přepisovací pravidla buď s levým nebo s pravým kontextem (nikoli s oběma najednou). Tyto L-systémy mohou obsahovat i bezkontextová pravidla. Při vyhodnocování mají však přednost kontextová.

gramatika
abeceda:	`a A`
axiom:	`Aaaaaa`
přepis. pravidla:	`A` < `a` → `A`
	`A` → `a`

Výsledek bude po iteracích vypadat následovně:

i = 0 : Aaaaaa

i = 1 : aAaaaa

i = 2 : aaAaaa

i = 3 : aaaAaa

i = 4 : aaaaAa atd.

Této technice se říká propagace signálu a používá se pro modelování pokročilých modelů rostlin.^[4]

2L-systémy[editovat | editovat zdroj]

2L-systémy obsahují i kontextová přepisovací pravidla, která mají oba kontexty. Krom nich mohou obsahovat vše co 1L-systémy.

L-systémy reagující na prostředí[editovat | editovat zdroj]

Základní L-systém se dá také rozšířit o speciální symboly, které se použijí pro obousměrnou komunikaci s prostředím. Prostředí je obvykle nějaká datová struktura, která je schopna odpovídat na dotazy typu „Jak moc je v tomto místě volno“ a dokáže přijímat příkazy typu „Na tomto místě je objekt velikosti x“. Pak se pomocí těchto L-systému dá vymodelovat rostlina, která se vyvíjí lépe tam, kde má více „místa“ nebo kde je výživnější půda. Pokud v přírodě rostou dva stromy blízko sebe, budou mít více větví na straně odvrácené od sousedního stromu a naopak málo větví bude směřovat do koruny sousedního. Toto chování se dá popsat právě pomocí L-systémů s prostředím. ^[13]

Aplikace generující L-systémy[editovat | editovat zdroj]

Fractint[editovat | editovat zdroj]

Fractint^[14] je freeware generátor fraktálů pro DOS (Windows) a Linux. Program podporuje pouze základní typ L-systémů (tj. D0L-systémy). Výstup programu je možné uložit do souborů BMP a GIF

Inkscape[editovat | editovat zdroj]

Inkscape je open source vektorový grafický editor používající SVG jako svůj nativní formát. Obsahuje skript pro generování základního typu L-systémů (tj. D0L-systémů). Jeho výhoda je však ta, že výsledek je vektorový a dá se s ním v programu dále pracovat.

Plugin pro Blender[editovat | editovat zdroj]

Blender je open-source program pro modelování a vykreslování 3D počítačové grafiky, do kterého se dá stáhnout plugin^[15], který generuje rostliny pomocí L-systémů. Odlišností tohoto pluginu od ostatních programů je ta, že grafik nezadává předpis L-systému, ale pouze vizuálně nastavuje parametry výsledného modelu rostliny.

Reference[editovat | editovat zdroj]

↑ BOEAR, Martin; FRACCHIA, David; PRUSINKIEWICZ, Przemyslaw. A model for cellular development in morphogenetic fields. [s.l.]: [s.n.] 20 s. Dostupné online. (anglicky)
↑ LINDENMAYER, Aristid. Mathematical models for cellular interactions in development. Svazek Journal of theoretical biology Parts I and II. [s.l.]: Elsevier, 1968. S. 280–315. (anglicky)
↑ PRUSINKIEWICZ, Przemyslaw. Graphical applications of L-systems. [s.l.]: Department of Computer Science, University of Regina (anglicky)
↑ ^a ^b ^c ^d ^e ^f ^g LINDENMAYER, Aristid; PRUSINKIEWICZ, Przemyslaw, a kol. The Algorithmic Beauty of Plants. [s.l.]: Springer, c1991 228 s. Dostupné online. (anglicky)
↑ PRUSINKIEWICZ, P.; HAMMEL, M. A fractal model of mountains and rivers. [s.l.]: Canadian Information Processing Society, c1993 S. 174–180. (anglicky)
↑ PARISH, Y.I.H.; MÜLLER, P. Procedural modeling of cities. [s.l.]: [s.n.], c2001 Dostupné online. ISBN 1-58113-374-X. S. 301–308. (anglicky)
↑ PRUSINKIEWICZ, Przemyslaw, a kol. L-system description of subdivision curves. Svazek International Journal of Shape Modeling. [s.l.]: [s.n.], c2003 S. 41–59. (anglicky)
↑ HAZARD, C.; CATHERINE, K.; JOHNSON, D. Fractal Music [online]. [cit. 2012-03-01]. Dostupné v archivu pořízeném dne 2012-02-22. (anglicky)
↑ MANOUSAKIS, S. Musical L-systems. [s.l.]: Nepublikovaná magisterská práce, Institute of Sonology, Hague, c2006 (anglicky)
↑ Avatar a Run for the Artefact: Goliáš a David počítačové animace
↑ FUHRER, Martin. Hairs, Textures, and Shades: Improving the Realism of Plant Models Generated with L-Systems. [s.l.]: [s.n.], c2005 121 s. Dostupné online. (anglicky)
↑ PRUSINKIEWICZ, Przemyslaw, a kol. L-systems: from the theory to visual models of plants. Calgary, Alberta, Canada: CSIRO Publishing 32 s. Dostupné online. S. 21–22. (anglicky)
↑ MECH, Radomir; PRUSINKIEWICZ, Przemyslaw. Visual Models of Plants Interacting with Their Environment. [s.l.]: [s.n.] Dostupné online. (anglicky)
↑ Domácí stránka freeware generátoru fraktálů Fractint: [1]
↑ Domácí stránka pluginu pro generování L-systémů v Blenderu: [2] Archivováno 15. 4. 2011 na Wayback Machine.

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Obrázky, zvuky či videa k tématu L-systém na Wikimedia Commons
Seriál o L-systémech na serveru root.cz: L-systémy: přírodní objekty i umělé artefakty
Část diplomové práce Pavla Tišnovského: L-systémy
(anglicky) Algorithmic botany – stránka Univerzity Calgary kde Dr. Przemyslaw Prusinkiewicz spolu s jeho studenty a kolegy publikuje své práce

[1] BOEAR, Martin; FRACCHIA, David; PRUSINKIEWICZ, Przemyslaw. A model for cellular development in morphogenetic fields. [s.l.]: [s.n.] 20 s. Dostupné online. (anglicky)

[2] LINDENMAYER, Aristid. Mathematical models for cellular interactions in development. Svazek Journal of theoretical biology Parts I and II. [s.l.]: Elsevier, 1968. S. 280–315. (anglicky)

[3] PRUSINKIEWICZ, Przemyslaw. Graphical applications of L-systems. [s.l.]: Department of Computer Science, University of Regina (anglicky)

[abop-4] ↑ ^a ^b ^c ^d ^e ^f ^g LINDENMAYER, Aristid; PRUSINKIEWICZ, Przemyslaw, a kol. The Algorithmic Beauty of Plants. [s.l.]: Springer, c1991 228 s. Dostupné online. (anglicky)

[5] PRUSINKIEWICZ, P.; HAMMEL, M. A fractal model of mountains and rivers. [s.l.]: Canadian Information Processing Society, c1993 S. 174–180. (anglicky)

[6] PARISH, Y.I.H.; MÜLLER, P. Procedural modeling of cities. [s.l.]: [s.n.], c2001 Dostupné online. ISBN 1-58113-374-X. S. 301–308. (anglicky)

[7] PRUSINKIEWICZ, Przemyslaw, a kol. L-system description of subdivision curves. Svazek International Journal of Shape Modeling. [s.l.]: [s.n.], c2003 S. 41–59. (anglicky)

[8] HAZARD, C.; CATHERINE, K.; JOHNSON, D. Fractal Music [online]. [cit. 2012-03-01]. Dostupné v archivu pořízeném dne 2012-02-22. (anglicky)

[9] MANOUSAKIS, S. Musical L-systems. [s.l.]: Nepublikovaná magisterská práce, Institute of Sonology, Hague, c2006 (anglicky)

[10] Avatar a Run for the Artefact: Goliáš a David počítačové animace

[11] FUHRER, Martin. Hairs, Textures, and Shades: Improving the Realism of Plant Models Generated with L-Systems. [s.l.]: [s.n.], c2005 121 s. Dostupné online. (anglicky)

[12] PRUSINKIEWICZ, Przemyslaw, a kol. L-systems: from the theory to visual models of plants. Calgary, Alberta, Canada: CSIRO Publishing 32 s. Dostupné online. S. 21–22. (anglicky)

[13] MECH, Radomir; PRUSINKIEWICZ, Przemyslaw. Visual Models of Plants Interacting with Their Environment. [s.l.]: [s.n.] Dostupné online. (anglicky)

[14] Domácí stránka freeware generátoru fraktálů Fractint: [1]

[15] Domácí stránka pluginu pro generování L-systémů v Blenderu: [2] Archivováno 15. 4. 2011 na Wayback Machine.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]