úloha 041: Lindenmayerovy systémy

Úvod: v této úloze budete rozšiřovat jednoduchý generátor stromů založený na L-systémech. K dispozici dostanete aplikaci, která dokáže na základě zadaných gramatických pravidel generovat řídící řetězec využívaný rendererem, který umí vykreslovat větve stromů pomocí komolých jehlanů. Vaším základním úkolem bude upravit rendering tak, aby šlo vytvářet realističtější obraz stromu včetně listů a plodů.

Co to jsou L-systémy? Nejlepší je si přečíst článek na wikipedii. Ve stručnosti - jde o speciální typ gramatiky, kde se v každé iteraci aplikují všechna možná přepisovácí pravidla najednou na celý zpracovávaný řetězec. Když se přepisovací pravidla navrhnou šikovně, lze pomocí nich popsat rozličné děje a struktury - v našem prípadě simulaci růstu rostlin (k tomu byly i původně navrženy). S formálním popisem růstu rostliny si nevystačíme, pokud chceme rostlinu vykreslit. Musíme tedy navrhnout sadu terminálů a proměnných použitých v L-systému tak, aby sloužily jako jednoduché příkazy pro nějaký renderer (viz želví grafika), či navrhnout renderer, který dokáže interpretovat strukturu popsanou botanicky (pupen, větvení, apod.).

Zadání: rozšířit renderer z projektu 041lsystems tak, aby dokázal vykreslit strom s listy a plody a jeho struktura vypadala co nejrealističtěji. Úloha je cílena jako cvičení pro manipulaci s transformačními maticemi. Plody/šišky by tedy neměly směřovat v závislosti na lokální orientaci někam obecně do prostoru, ale směrem dolů, případně nahoru, když se zaměříte na jedlovité. Ve vám dostupné verzi renderer dokáže zpracovat tyto instrukce:

F .. vykreslí komolý jehlan z aktuální pozice ve směru aktuálního natočení a přesune se na jeho konec (velikosti podstav a výška jsou určeny vnějšími parametry)
+ .. natočení okolo osy y o úhel určený vnějším parametrem v kladném směru
- .. natočení okolo lokální osy Y o úhel určený vnějším parametrem v záporném směru
/ .. otočení o +90° okolo lokální osy Z
\ .. otočení o -90° okolo lokální osy Z
[ .. uložení současného stavu na zásobník
] .. obnovení stavu ze zásobníku

Tato sada je dosti chudá a instrukce jsou také celkem triviální a neodpovídají růstové struktuře stromu. Ke splnění zadání tato sada nestačí. Navrhněte novou sadu instrukcí. Dále vytvořte několik sad přepisovacích pravidel - každou pro jiný druh stromu (ideálně modelující nějaký skutečný druh) - využívajících navržené instrukce jako symboly.

Spojitost větvení: typickým problémem jednoduchého vykreslování L-systému je problematické generování geometrie v místech, kde dochází k větvení. Pokud je objekt vykreslován pomocí nějakých základních primitiv (válce, jehlany,..), dochází v místech větvení k nehezkému překrývání geometrií. Zřejmě nejjednodušším způsobem jak toto řešit je přidání speciálního objektu "větvení", jehož tvar bude záviset na počtu a směru větví vycházejících z daného uzlového bodu - tyto informace jsou ale k dispozici až po tom, co byly všechny větve zpracovány - typický příklad průchodu stromu v post-orderu (viz základní kurz programování).
Mnohem lepším řešením, než je přidání speciálního objektu, by bylo generování jednolité souvislé geometrie pro celý strom - toto je výrazně složitější, jelikož se musí řešit plno problémů s topologií (správné navazování trojúhelníků, řešení ruzných degenerovaných případů). S výslednou geometrií by se pak ale snadno pracovalo v různých 3D editorech.

Implementace: jako kostru aplikace použijte projekt 041lsystems z repository grcis. Zajímat vás bude hlavně soubor LSystemRenderer.cs a v něm metoda stejnojmenné třídy Render(). V této metodě nahradíte switch ošetřující jednotlivé instrukce vlastní verzí. Ve stejném souboru je také třída VisualisationParameters, která obsahuje sadu parametrů použitých rendererem pro modifikaci vzhledu - tyto parametry jsou v GUI nastavovány pomocí sliderů vpravo dole. Pokud tedy bude chtít použít jinou sadu parametrů, budete muset dle toho upravit i GUI aplikace.

Odevzdání: jako řešení úlohy posílejte mailem modifikované soubory a soubory se sadami přepisovacích pravidel. Postupy a nápady, na které jste pyšní a chcete za ně bonusové body, řádně popište. Příklad souboru s pravidly naleznete zde (shodný soubor je i v repository v adresáři data).

BODY: 8 až 19b + bonus:

8-10b - rozšíření rendereru o kreslení struktur jako jsou listy/jehličí a plody/šišky včetně tří ukázkových LSystémů popisující různé druhy stromů - ne variaci na jedno téma. Není nutné starat se o texturování a super kvalitní geometrii. Plody musí být vykreslovány vzhledem ke globálnímu souřadnému systému, nikoli lokálnímu jako větve nebo pupeny!
4b - randomizované vykreslování geometrie, POZOR - geometrie se nemůže nahodile měnit mezi překreslením - nutno použít předgenerovaná náhodná čísla, inicializovat seed na stejnou hodnotu, apod.
3-5b - aspoň částečné řešení spojitosti geometrie v místech větvení
bonus - za inovativní a funkční řešení, povedená ukázková data, apod.

TERMÍN: do 12. 1. 2014

PROJEKT: 041lsystems

ZDROJOVÝ SOUBOR: LSystemRenderer.cs, případně i jiné upravené (pokud obohatíte GUI)

[Cvičení NPGR003] [Návody k zápočtům v C#] [Přednášky a semináře] [Odkazy na demonstrace]

Copyright (C) 2011-2013 J.Pelikán, last change: $Date: 2014-10-03 15:44:39 +0200 (Fri, 03 Oct 2014) $
Send comments/requests to pepca.at.cgg.mff.cuni.cz