L-systém

Traviny vymodelované pomocí L-systémů ve 3D

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

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

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 ${\displaystyle G=(\Sigma ,S,P)}$^[4], kde

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

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 ${\displaystyle n>0}$) vznikne paralelní aplikací přepisovacích pravidel na výsledek iterace ${\displaystyle 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

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

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

Mějme následující gramatiku:

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 ${\displaystyle {\text{fib}}(0)=1}$ a ${\displaystyle {\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 (${\displaystyle i>1}$) je součtem předchozích dvou. Tedy i-tá iterace tvořena spojením iterací ${\displaystyle i-2}$ a ${\displaystyle 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í ${\displaystyle i-1}$ a ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (k,k+1)}$. Poměr počtu symbolů A a B tedy pro ${\displaystyle i\rightarrow \infty }$ konverguje k hodnotě zlatého řezu

${\displaystyle \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.

Interpretace symbolů

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

Představa, jak želva něco kreslí (želví grafika)

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

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

Vykreslování ve 3D

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.

Graficky znázorněné otáčení ve 3D

Příklady L-systémů

Kochova vločka

Animace interpretace L-systému želví grafikou

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

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

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

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

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]

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í

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

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.

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

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.

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 ${\displaystyle t/2}$, symbol C s parametrem ${\displaystyle 5}$, symbol D bez parametru a symbol E s parametry ${\displaystyle 1/t}$ a 8.“

Interpretace

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ě:

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:

Příklady

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…

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.

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

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]

Stochastické L-systémy

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

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

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

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.

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

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

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

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

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í

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

Fractint

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

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

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

Související články

• Fraktál
• Formální gramatika
• Počítačová grafika

Externí odkazy

• 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