Hlavní navigace

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

Pavel Tišnovský

V dnešním článku si nejprve ukážeme rozšíření přepisovacích gramatik dvourozměrných L-systémů o symboly "@", "C" a "|". Tyto symboly je možné použít například při tvorbě různých dlaždicovitých vzorů, které proslavil sir Roger Penrose. Dále se začneme zabývat pravděpodobně nejpraktičtějším využitím L-systémů.

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 

fractals56_1

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 

fractals56_2

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= 

fractals56_3

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.

Symbol Příkaz pro želvu Význam symbolu
F draw forward posun želvy dopředu s kreslením úsečky
G move forward posun želvy dopředu bez kreslení úsečky
B draw backward posun želvy dozadu s kreslením úsečky
+ turn left natočení želvy doleva o předem známý počet stupňů (úhel)
- turn right natočení želvy doprava o předem známý počet stupňů (úhel)
[ push state uložení stavu želvy na zásobník
] turn right vyjmutí stavu želvy ze zásobníku
@ change step změna kroku želvy o zadanou hodnotu
| turn around otočení želvy o 180°
C set color nastavení barvy, kterou želva kreslí

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= 

fractals56_4

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= 

fractals56_5

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

fractals56_6

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

fractals56_7

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+51/2)/2.

fractals56_8

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 

fractals56_9

Obrázek 9: Kites and Darts, verze 1

fractals56_a

Obrázek 10: Kites and Darts, verze 2

fractals56_b

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ýř)

fractals56_c

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.

fractals56_d

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ý (_).

Symbol Příkaz Úhel
F draw forward
G move backward
g,f jump
+ turn left RU(α)
- turn right RU(-α)
& pitch down RL(α)
^ pitch up RL(-α)
< roll left RH(α)
> roll right RH(-α)
| turn around RU(π)
_ roll around RH(π)
* home
[ push state
] pop state

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

fractals56_e

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.

Našli jste v článku chybu?

22. 11. 2006 11:35

Diky za pochvalu. Je trosku skoda, ze se pod timto clankem nerozpoutala vetsi diskuse, napriklad problem mozaiek je dost zajimavy a ani se nemusi pouzivat nejaka slozitejsi matematika.

P.S.: taky delam neco podobneho, konkretne Oracle+JSP, ale i nejaka grafika & spol. se do toho vleze (i kdyz malo).

21. 11. 2006 8:11

Veselý programátor (neregistrovaný)
Je to krása.
Pane Tišnovský, děkuji za vaše pěkné seriály, těším se na každé další pokračování.

P.S. V práci se teď bohužel musím živit databázovou nudou na microtfujsoftu, ale tyhle články mi vždycky připomenou to skutečné pěkné programování.


DigiZone.cz: SES zajistí HD pro M7 Group

SES zajistí HD pro M7 Group

DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

Lupa.cz: Levný tarif pro Brno nebude, je to kartel

Levný tarif pro Brno nebude, je to kartel

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

Vitalia.cz: 7 originálních adventních kalendářů pro mlsné

7 originálních adventních kalendářů pro mlsné

DigiZone.cz: V Plzni odstartovalo Radio 1

V Plzni odstartovalo Radio 1

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

Podnikatel.cz: E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

Vitalia.cz: Jak vybrat ořechy do cukroví a kde mají levné

Jak vybrat ořechy do cukroví a kde mají levné

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

DigiZone.cz: Ohrozí Freedom TV přechodové sítě?

Ohrozí Freedom TV přechodové sítě?

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

DigiZone.cz: Sat novinky: slovenská TV8 HD i ruský NTV Mir

Sat novinky: slovenská TV8 HD i ruský NTV Mir

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

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

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