Mozaiky s L-systémy a trojrozměrné L-systémy

Obsah

1. Doplnění gramatiky o symboly „@“, „C“ a „|“
2. Výpis všech terminálních symbolů pro 2D L-systémy
3. Periodické a aperiodické mozaiky
4. Kites & Darts
5. L-systémy vytvářené v trojrozměrném prostoru
6. Pozice a orientace želvy v 3D prostoru
7. Nové symboly v gramatice ovlivňující pohyb želvy v prostoru
8. Odkazy na Internetu
9. Obsah dalšího pokračování tohoto seriálu

1. Doplnění gramatiky o symboly „@“, „C“ a „|“

V předchozích částech tohoto seriálu jsme si popsali dvě základní a současně i nejznámější skupiny L-systémů. První – implementačně nejjednodušší a nejméně sémanticky vybavenou – skupinu tvořily takzvané dL0 systémy, pomocí kterých je možné tvořit obrázky různých křivek (Kochovy, Hilbertovy, Sierpinského atd.) i Cantorovu množinu (dL0–deterministické L-systémy nultého řádu). Druhou skupinou L-systémů jsou závorkové L-systémy (bracketed L-systems), které již umožňují tvorbu složitějších geometrických struktur, například obrázků stromů či keřů.

Tyto systémy vznikly z původních dL0 systémů rozšířením gramatiky o dva symboly „[“ a „]“; želva přitom získala lokální paměť ve formě zásobníku stavů. Určitým rozšířením závorkových L-systémů byly minule popisované stochastické systémy, ve kterých se však neměnily vlastnosti přepisovací gramatiky, ale „pouze“ způsob interpretace symbolů přepisovacího řetězce želvou. V obou popisovaných variantách L-systémů však můžeme postrádat další vyjadřovací schopnosti gramatik, zejména možnost změny délky kreslené úsečky či její barvy.

Tyto vlastnosti je poměrně jednoduché do L-systémů přidat, musíme si však pamatovat, že každá úprava by měla být provedena ve dvou oblastech – změnou/rozšířením gramatiky a změnou funkcí, které provádí vykreslování L-systému s využitím želví grafiky (zjednodušeně můžeme říkat, že rozšiřujeme funkcionalitu želví grafiky). V dalším textu si ukážeme vliv přidání tří symbolů do přepisovací gramatiky. Jedná se o symboly „@“, „C“ a „|“. Kromě těchto symbolů je grafika rozšířena o terminální (nepřepisované) znaky, které tvoří číselnou hodnotu. Tato hodnota zůstává při přepisování řetězců zachována. Existuje však i varianta takzvaných otevřených L-systémů (open L-systems), ve které je povolena i řízená změna numerických hodnot.

Pravděpodobně nejpraktičtějším rozšířením L-systémů je přidání terminálního (nepřepisovatel­ného) symbolu „@“ do přepisovací gramatiky. V případě, že želva při interpretaci řetězce narazí na tento symbol, přečte číselnou hodnotu, která je za symbolem uvedena a následně touto hodnotou vynásobí délku svého kroku. Pokud se například v řetězci vyskytují znaky „@0.5“, želva změní délku kroku na polovinu. Délka kroku je ukládána na zásobník stavů znakem „[“ a vybírána ze zásobníku při přijetí znaku „]“, tj. pouze část obrazce se vykresluje s modifikovanou délkou kroku.

Na prvním obrázku je ukázán L-systém v podobě binárního stromu, který je vytvářen velmi jednoduchou přepisovací gramatikou používající symbol „@“ (modifikovanou verzi této gramatiky jsme si ukázali v předchozí části tohoto seriálu). Jak je ze zápisu L-systému patrné, je změna úhlu natočení želvy při interpretaci symbolů „+“ a „-“ nastavena na 30°:

angle=30°
axiom +++FX
X=@.6[-FX]+FX 

Obrázek 1: Binární strom, v jehož gramatice je použit symbol „@“

Dalším symbolem, který může do značné míry zjednodušit zadávání gramatik, je symbol „|“ (pipe). Jeho funkce je celkem jednoduchá: pokud želva při interpretaci přepisovacího řetězce narazí na tento znak, provede otočení o 180° bez ohledu na nastavení jejího úhlu. Předností tohoto symbolu je, že je použitelný i v případě, že úhel natočení želvy (resp. změna úhlu) není celočíselným dělitelem 360°. Ukázka gramatiky a k ní příslušného L-systému je zobrazena na druhém obrázku (všimněte si použití symbolů „Q“ a „I“, ty slouží pro zadání odmocniny a převrácené hodnoty místo číselných hodnot, jedná se o rozšíření gramatik zavedené programem FractInt):

angle=30°
axiom F
F=++!F!F--F--F@IQ3|+F!F--
F=F--F!+++@Q3F@QI3|+F!F@Q3|+F!F 

Obrázek 2: Sněhová vločka, v jejíž gramatice je použit symbol „|“

Posledním rozšiřujícím symbolem přepisovacích gramatik dvourozměrných L-systémů je symbol „C“. Ten slouží pro změnu barvy želvy, která probíhá následujícím způsobem: pokud želva v přepisovacím řetězci narazí na symbol „C“, přečte numerickou hodnotu uloženou ihned za tímto znakem a tuto hodnotu následně interpretuje jako index do barvové palety. Želva barvu na daném indexu přečte a začne touto barvou L-systém vykreslovat. Ukázka poměrně složitého L-systému se třemi barvami (s indexy 10, 11 a 12) je ukázána na třetím obrázku. Gramatika tohoto systému je následující:

angle=36°
axiom +WC10FC12F--XC11FC10F---YC10FC11F--ZC12FC10F
W=YC10FC11F++ZC12FC10F----XC11FC10F[-YC10FC11F----WC10FC12F]++
X=+YC10FC11F--ZC12FC10F[---WC10FC12F--XC11FC10F]+
Y=-WC10FC12F++XC11FC10F[+++YC10FC11F++ZC12FC10F]-
Z=--YC10FC11F++++WC10FC12F[+ZC12FC10F++++XC11FC10F]--XC11FC10F
F= 

Obrázek 3: Tříbarevný L-systém

2. Výpis všech terminálních symbolů pro 2D L-systémy

V první tabulce jsou vypsány všechny terminální symboly, které jsme doposud použili pro vytváření dvourozměrných L-systémů (dL0, závorkových i stochastických). V dalších kapitolách si ukážeme, jakým způsobem bude nutné tabulku změnit (rozšířit) v případě, že se želva pohybuje v trojrozměrném prostoru.

3. Periodické a aperiodické mozaiky

Velkou úlohu v počítačové grafice, geometrii, umění i architektuře hrají obrazce (říkejme jim dlaždice), ze kterých je možné sestavovat mozaiky beze zbytku vyplňující nějakou předem známou plochu či dokonce celou rovinu. Dlaždicové vzory se mohou buď opakovat (jsou periodické) nebo mohou být složeny z náhodných či nepravidelných tvarů. Speciální formou dlaždic, ideově ležící na pomezí mezi periodickými a nepravidelnými tvary, jsou aperiodické vzory, které se sice skládají z konečného množství základních tvarů, ale tyto tvary jsou poskládány takovým způsobem, že se tvar vytvořené mozaiky nikdy neopakuje (je možné matematicky dokázat, že pro některé pečlivě vybrané základní tvary je možné sestavit nekonečné množství možností, jakými tyto tvary vyplňují rovinu).

Periodickými a aperiodickými vzory se zabývalo mnoho umělců i vědců, mezi jinými i Johannes Kepler, který je známý zejména díky svým (Keplerovým) zákonům. Tento vědec si zaslouží obdiv nejenom kvůli dosaženým teoretickým výsledkům, ale především proto, že dokázal (jistě s těžkým srdcem) zahodit svoji představu vesmíru řízeného geometrií, zejména dokonalými tělesy, a tuto představu nahradil něčím na první pohled méně „ušlechtilým“ – drahami ve tvaru elips. Dokázal tak odvrhnout sice velmi propracovanou a z geometrického hlediska elegantní, ale mylnou teorii na základě měření, které ukazovaly, že skutečnost se od této teorie odlišuje.

Nicméně se vraťme k periodickým a aperiodickým mozaikám. Ukazuje se, že zejména periodické dlaždicové vzory je možné generovat pomocí L-systémů. Na čtvrtém obrázku je zobrazen L-systém definovaný gramatikou popsanou v dalším odstavci. Tvar tohoto L-systému je vyobrazen po jedné až pěti iteracích, tj. přepisech axiomu. Úhel natáčení želvy je nastavený na 36°, což je, jak si povíme v následující kapitole, úhel typický pro mnoho dlaždicovitých vzorů. Za povšimnutí stojí, že celý obrazec je složen pouze ze dvou kosočtverců, které mají stejně dlouhé hrany a odlišují se pouze svými vnitřními úhly. Gramatika tohoto L-systému má tvar:

Axiom +WF--XF---YF--ZF
W=YF++ZF----XF[-YF----WF]++
X=+YF--ZF[---WF--XF]+
Y=-WF++XF[+++YF++ZF]-
Z=--YF++++WF[+ZF++++XF]--XF
F= 

Obrázek 4: Mozaika vytvořená po jedné až pěti iteracích L-systému

Podobný L-systém je zobrazený i na pátém obrázku, tentokrát pro 1–6 iterací, tj. axiom je na základě přepisovací gramatiky přepsán jedenkrát až šestkrát. Gramatika tohoto L-systému je poněkud odlišná, základní úhel natočení želvy (36°) však zůstává zachován.

Axiom ++ZF----XF-YF----WF
W=YF++ZF----XF[-YF----WF]++
X=+YF--ZF[---WF--XF]+
Y=-WF++XF[+++YF++ZF]-
Z=--YF++++WF[+ZF++++XF]--XF
F= 

Obrázek 5: Mozaika vytvořená po jedné až šesti iteracích L-systému

Obrázek 6: Pravidelnější mozaika (Penroseova práce)

Obrázek 7: Další ukázka Penroseovy mozaiky

4. Kites & Darts

Vědec Roger Penrose zkoumal, pomocí jakých základních tvarů je možné vytvořit aperiodické mozaiky, tj. vzory, které se nikde (na nekonečné ploše/rovině) neopakují. Některé z jeho děl jsou zobrazeny na šestém a sedmém obrázku. Zpočátku Penrose používal sadu cca dvanácti základních tvarů (ty se trošku podobaly dnešním puzzle, ale měly rovné hrany), později počet základních tvarů neustále snižoval, až došel k překvapivému závěru – aperiodické mozaiky je možné vytvořit pouze skládáním dvou základních dlaždic. Ty lze získat rozdělením kosočtverce s vnitřními úhly 72° a 108° tak, jak to naznačuje osmý obrázek. Symbol Φ představuje hodnotu zlatého řezu (golden mean), který má hodnotu (1+5^1/2)/2.

Obrázek 8: Dva tvary dlaždic, pomocí kterých je možné vytvářet aperiodické mozaiky

Modrý tvar se nazývá kite, fialový tvar dart. Vytvořené mozaiky se z tohoto důvodu nazývají Kites and Darts. Jednoduchým tvarem, který je možné složit ze dvou kites a jednoho dart, je ace (eso) – to představuje základ pro tvorbu složitějších mozaiek. Na dalších třech obrázcích je zobrazeno několik variant mozaiek vytvořených pomocí tvarů kite a dart. Všimněte si neobyčejně vysoké variability při skládání těchto tvarů. Přepisovací gramatiky těchto mozaiek mají tvar:

Axiom k
k=+[@.618034a]f@.618034---[-k]f-f---[-k]@i.618034f[@.618034|a]
a=[@.618034k]+f@.618034[|a]----f+f----[a]@i.618034f
f=g

Axiom [k]++[k]++[k]++[k]++[k]
k=+[@.618034a]f@.618034---[-k]f-f---[-k]@i.618034f[@.618034|a]
a=[@.618034k]+f@.618034[|a]----f+f----[a]@i.618034f
f=g

Axiom [a]++[a]++[a]++[a]++[a]
k=+[@.618034a]f@.618034---[-k]f-f---[-k]@i.618034f[@.618034|a]
a=[@.618034k]+f@.618034[|a]----f+f----[a]@i.618034f
f=g 

Obrázek 9: Kites and Darts, verze 1

Obrázek 10: Kites and Darts, verze 2

Obrázek 11: Kites and Darts, verze 3

5. L-systémy vytvářené v trojrozměrném prostoru

Popisem mozaiek generovaných pomocí 2D L-systémů jsme sice nevyčerpali všechny varianty tvarů, které je možné vytvářet v rovině (nad mozaikami je možné například hrát obdobu známé hry Life), ale podle reakce čtenářů už je nejvyšší čas, abychom se podívali na způsob vytváření L-systémů v trojrozměrném prostoru. Trojrozměrné L-systémy totiž mají mnohem širší možnosti použití, než jejich plošní předchůdci. Na první pohled by se mohlo zdát, že postačuje přidání jedné souřadnice při generování obrázků pomocí želví grafiky, skutečnost je však mnohem složitější. Celou problematiku si přiblížíme v šesté a sedmé kapitole, ve kterých si popíšeme způsob ovládání želvy v 3D prostoru a nové symboly, které je zapotřebí doplnit do gramatiky tak, aby želva mohla vykonávat v prostoru požadované „cviky“.

6. Pozice a orientace želvy v 3D prostoru

Pravděpodobně největší změnou při přechodu z plochy do trojrozměrného prostoru je mnohem větší volnost želvy. V ploše se želva mohla pohybovat směrem dopředu či dozadu (tato možnost v 3D samozřejmě zůstává) a dále se mohla otáčet okolo své osy. Pro popis stavu želvy nám z tohoto důvodu dostačovaly tři hodnoty:

1. x-ová souřadnice
2. y-ová souřadnice
3. úhel natočení želvy

V trojrozměrném prostoru je situace složitější, protože želva může být umístěna i natočena zcela libovolně. Stav želvy se v tomto případě popisuje již složitějším způsobem (například vektorem polohy a trojicí úhlů), my se budeme držet techniky používané v mnoha animačních i simulačních programech (včetně mnoha her, například leteckých simulátorů) – každému objektu je přiřazen lokální souřadný systém popsaný trojicí vektorů a otočení vektoru může být chápáno jako natočení lokálního souřadného systému vůči systému globálnímu. V takovém případě želvu popíšeme čtyřmi hodnotami:

1. pozicí v prostoru (jedná se o bod, ale pro zjednodušení popisu ho můžeme považovat za vektor – počátek systému nebudeme měnit)
2. vektorem forward (směr hlavičky želvy)
3. vektorem left (směr, kterým míří levý bok želvy)
4. vektorem up (směr, ve kterém má želva krunýř)

Obrázek 12: Orientace želvy v 3D prostoru

Vzhledem k tomu, že každý ze čtyř zmíněných vektorů má tři složky, znamená to, že pro úplný popis pozice a orientace želvy potřebujeme 4×3=12 reálných hodnot (oproti pouhým třem hodnotám v 2D případě). Situace však není tak špatná, protože si můžeme všimnout, že vektory forward, left a up jsou jednotkové a k tomu na sebe kolmé (ortogonální). Pro na sebe kolmé vektory platí vztah:
forward×left=up
(symbol „ד značí vektorový součin). Z toho dále plyne, že jeden vektor lze z popisu želvy odstranit, neboť ho můžeme vždy dopočítat ze zbývajících dvou. Popis polohy a orientace želvy tedy můžeme uložit do 3×3=9 reálných hodnot.

Obrázek 13: 3D L-systém zobrazený v AutoCADu (skrytí neviditelných hran)

7. Nové symboly v gramatice ovlivňující pohyb želvy v prostoru

Vzhledem k tomu, že stav želvy je v trojrozměrném prostoru popsán složitějším způsobem než v 2D případě, musel se rozšířit i repertoár příkazů, které může želva provádět. Kromě známých symbolů pro kreslení a přesun želvy (F, G, f, g – pozor na změnu významu symbolů!) a symbolů pro práci se zásobníkem ([, ]) se setkáme se symboly, které želvu natáčí podle jednoho z jejích vektorů o zadaný úhel. Jedná se o symboly +, -, &, ^, <, >. Kromě toho je gramatika rozšířena o symboly, které mají pomocný (ale velmi významný) charakter. Jedná se o návrat želvy do domovské pozice (*) na počátek souřadnic a symboly pro otočení želvy o 180° (π). Jeden z těchto symbolů už známe (|), druhý je nový (_).

Přesný význam všech symbolů uvedených v této tabulce si řekneme v navazující části tohoto seriálu.

Obrázek 14: Další 3D L-systém zobrazený v AutoCADu (použit interní modul Render)

8. Odkazy na Internetu

1. http://en.wiki­pedia.org/wiki/Ro­ger_Penrose Roger Penrose na Wikipedii
2. http://en.wiki­pedia.org/wiki/Pen­rose_tiling Penrose Tiling
3. http://www.uw­gb.edu/DutchS/sym­metry/penrose­.htm Penrose Tiling 2
4. http://en.wiki­pedia.org/wiki/Jo­hannes_Kepler Johannes Kepler

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

V následují části tohoto seriálu si podrobněji popíšeme princip práce s programem L-parser a ukážeme si další způsoby využití vytvořených 3D modelů L-systémů, včetně jejich vykreslení pomocí známého raytraceru POV-Ray.