náhled|300px|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ů.
Historie L-systémy byly vyvinuty v roce 1968 maďarským biologem Aristidem Lindenmayerem jako matematický formalizmus pro popisování růstu řas.
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.
Lindenmayer spolu s Prusinkiewiczem publikovali knihu The Algorithmic Beauty of Plants, 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, ulice ve virtuálních městech nebo pomocí L-systémů lze popisovat podrozdělování (zjemňování) křivek. 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.
Ve filmu Avatar z roku 2009 bylo přes 2000 stromů, rostlin a kapradin vymodelováno právě pomocí L-systémů.Avatar a Run for the Artefact: Goliáš a David počítačové animace
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 , kde je abeceda, tj. neprázdná množina symbolů, je množina všech slov nad abecedou , je množina všech neprázdných slov nad abecedou , je semínko (z angl. seed) nebo také axiom, což je konečné slovo z abecedy , které definuje počáteční stav L-systému, je konečná množina přepisovacích pravidel, přepisovací pravidlo se zapisuje ve tvaru , kde a , definuje tedy přepsání symbolu na slovo (které může být i prázdné), pro symbol , který se neobjevuje na levé straně žádného přepisovacího pravidla, je definována identita () (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.
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 ) vznikne paralelní aplikací přepisovacích pravidel na výsledek iterace 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 a ):
1, 1, 2, 3, 5, 8, 13, 21, …
Výstupní řetězec má stejnou vlastnost, která platí pro Fibonacciho posloupnost, tj. i-té číslo () je součtem předchozích dvou. Tedy i-tá iterace tvořena spojením iterací a . 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í a . 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 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 . Poměr počtu symbolů A a B tedy pro konverguje k hodnotě zlatého řezu
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 2 A (2, 3) neexistuje a 3 B (3, 4) 2 4 B (4, 5) 3 5 A (5, 6) neexistuje a 6 B (6, 7) 4
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 náhled|200px|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ě).
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 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.
náhled|200px|Graficky znázorněné otáčení ve 3D 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ů Kochova vločka náhled|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 0. generace (axiom) Kochovy vločky
i = 1: F+F--F+F 1. generace Kochovy vločky
i = 2: F+F--F+F + F+F--F+F-- F+F--F+F + F+F--F+F 2. generace Kochovy vločky
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 3. generace Kochovy vločky
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.
Prvních 6 iterací fraktálu stromečku
Ostrovy a jezera náhled|200px|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.
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.
400px|3. iterace L-systému Ostrovy a jezera
Penroseovo dláždění Pomocí složitějšího L-systému se dá generovat Penroseovo dláždění.
pozn.: vykreslování úseček proběhne až po vykreslení všech polygonů (aby je polygony nepřekryly)
Gosperova křivka náhled|200px|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.