Implementace L-systémů založená na želví grafice

Obsah

1. Vykreslování L-systémů pomocí želví grafiky a gramatik
2. Implementace želví grafiky
3. Interpretace zadaného řetězce želvou
4. Aplikace přepisovacího pravidla
5. Demonstrační příklad na vykreslení Kochovy křivky
6. Demonstrační příklad na vykreslení Kochovy sněhové vločky
7. Literatura a odkazy na Internetu
8. Obsah dalšího pokračování tohoto seriálu

1. Vykreslování L-systémů pomocí želví grafiky a gramatik

V předchozím pokračování tohoto seriálu jsme si uvedli základní informace o vytváření L-systémů za pomocí želví grafiky (turtle graphics) a regulárních gramatik. Také jsme si popsali pravděpodobně nejznámější fraktální objekty vykreslované pomocí L-systémů. Dnešní část již bude zaměřena více prakticky, protože si ukážeme implementaci želví grafiky a jednoduchých přepisovacích gramatik (podmnožina regulárních gramatik se sloučenými terminálními a nonterminálními symboly) v demonstračních příkladech vytvořených v programovacím jazyku C s využitím grafické knihovny OpenGL.

Jak bude patrné z následujícího textu i výpisu implementovaných céčkovských funkcí, je použití grafické knihovny OpenGL výhodné zejména z toho důvodu, že si nemusíme pamatovat starou pozici želvy pro účely vykreslení úsečky, tu si totiž knihovna „zapamatuje“ sama po zavolání funkce typu glVertex2d() nebo obdobné funkce, například glVertex3i() apod. To nám do značné míry zjednoduší celou řídicí část želví grafiky na sadu šesti několikařádkových funkcí a pětici proměnných sdílených těmito funkcemi. Více informací o grafické knihovně OpenGL se můžete dozvědět ze seriálu Grafická knihovna OpenGL.

Obrázek 1: Trojrozměrné L-systémy vytvořené programem LParser a vykreslené aplikací LViewer

2. Implementace želví grafiky

Začneme nejjednodušší částí, kterou je implementace želví grafiky. Jak již víme z předchozí části tohoto seriálu, je želva popsána svou pozicí a orientací v ploše. Úplný popis stavu želvy nám tedy zajistí trojice proměnných typu double (výpočty nové pozice želvy by měly probíhat s větší přesností, proto je použit tento zdánlivě naddimenzovaný datový typ):

double x, y, alpha;                             // souřadnice a natočení želvy 

Kromě toho si ještě musíme pamatovat krok želvy, který je použit při interpretaci příkazů draw forward, move forward a draw backward. Dále se jedná o úhel, o který se želva otočí při interpretaci příkazů turn left a turn right. K tomu nám poslouží dvojice proměnných step a delta, které by měly být nastaveny na „rozumné“ hodnoty; krok želvy by například mohl být odvozen z velikosti okna aplikace a úhel může odpovídat 30°, 45° nebo 60° (jak uvidíme v dalších kapitolách, může být úhel pro každý typ L-systému odlišný, u pravidelných tvarů se však používají výše uvedené hodnoty).

Dále musíme implementovat funkce, které budou provádět pětici základních želvích příkazů

K těmto příkazům ještě přidejme funkci zajišťující nastavení želvy do základní polohy, tj. na absolutní souřadnice [0, 0] s orientací želvy směrem doprava (LOGO v tomto případě používá natočení želvy směrem nahoru – na „sever“, ale to je v podstatě jedno). Celou sadu funkcí je možné implementovat překvapivě snadno:

//-----------------------------------------------------------------------------
// Nastavení želvy do počáteční (domácí) pozice specifikovanou souřadnicemi
// [xpos, ypos]
//-----------------------------------------------------------------------------
void logo_home(double xpos, double ypos)
{
    x=xpos;
    y=ypos;
    alpha=0.0;
}



//-----------------------------------------------------------------------------
// Posun želvy dopředu s kreslením
//-----------------------------------------------------------------------------
void logo_forward(void)
{
    glBegin(GL_LINES);
    glVertex2d(x,y);                            // pozice želvy před posunem
    x+=step*cos(alpha);                         // posun v zadaném směru
    y+=step*sin(alpha);
    glVertex2d(x,y);                            // pozice želvy po posunu
    glEnd();
}



//-----------------------------------------------------------------------------
// Posun želvy dozadu s kreslením
//-----------------------------------------------------------------------------
void logo_backward(void)
{
    glBegin(GL_LINES);
    glVertex2d(x,y);                            // pozice želvy před posunem
    x-=step*cos(alpha);                         // posun v zadaném směru
    y-=step*sin(alpha);
    glVertex2d(x,y);                            // pozice želvy po posunu
    glEnd();
}



//-----------------------------------------------------------------------------
// Posun želvy dopředu bez kreslení
//-----------------------------------------------------------------------------
void logo_move(void)
{
    x+=step*cos(alpha);                         // posun v zadaném směru
    y+=step*sin(alpha);
}



//-----------------------------------------------------------------------------
// Otočení želvy doleva
//-----------------------------------------------------------------------------
void logo_left(void)
{
    alpha+=delta;                               // změna orientace želvy
}



//-----------------------------------------------------------------------------
// Otočení želvy doprava
//-----------------------------------------------------------------------------
void logo_right(void)
{
    alpha-=delta;                               // změna orientace želvy
} 

Obrázek 2: Další trojrozměrné L-systémy vytvořené v programech LParser a LViewer

3. Interpretace zadaného řetězce želvou

Další funkcí, kterou je nutné vytvořit, je funkce interpretující zadaný řetězec a převádějící ho na sadu příkazů pro želvu. V této funkci se zadaný řetězec sekvenčně prochází a pokud jsou v něm nalezeny interpretovatelné znaky (tj. F, G, B, + či -), je zavolána jedna z předchozích funkcí provádějících změnu stavu želvy a popř. i vykreslení úsečky ze staré pozice želvy na pozici novou. Znaky, které nemůže želva interpretovat, jsou ignorovány:

//-----------------------------------------------------------------------------
// Překreslení L-systému na základě zadaného řetězce
//-----------------------------------------------------------------------------
void recalcLsys(const char *ret,                // řídicí řetězec
                double xpos,                    // posun obrazce
                double ypos)
{
    int i;
    logo_home(xpos, ypos);                      // inicializace želvy
    for (i=0; ret[i]; i++) {                    // projít celým řetězcem
        switch (ret[i]) {                       // a reagovat na příkazy v něm umístěné
            case 'F':                           // posun želvy v zadaném směru
                logo_forward();
                break;
            case 'B':                           // zpětný posun želvy v zadaném směru
                logo_backward();
                break;
            case 'G':                           // posun želvy v zadaném směru bez kreslení
                logo_move();
                break;
            case '+':                           // změna úhlu (orientace želvy)
                logo_left();
                break;
            case '-':                           // změna úhlu (orientace želvy)
                logo_right();
                break;
            default:
                break;
        }
    }
} 

Obrázek 3: Variace na Hilbertovu křivku, aneb křivka vyplňující plochu (L-systém nazvaný Foss2)

4. Aplikace přepisovacího pravidla

Aplikace přepisovacího pravidla je již poněkud složitější, a to z toho důvodu, že použitý programovací jazyk C nemá implementován datový typ řetězec (string), pouze rozpoznává řetězcové konstanty (při implementaci funkce pro aplikaci přepisovacího pravidla v jiném programovacím jazyce by se celá věc zjednodušila, například by bylo možné použít i regulární výrazy). Dále uvedená céčkovská funkce provádí náhradu znaku ‚F‘ za řetězec uložený v proměnné prepstr, rozšíření na více přepisovacích pravidel spočívá ve vytvoření tabulky (pole) těchto pravidel spolu s uvedením znaku, který je nutné přepsat. Při přepisu není pro jednoduchost kontrolováno překročení mezí řetězců:

//-----------------------------------------------------------------------------
// Aplikace přepisovacího pravidla na řetězec, výsledek je vrácen v řetězci ret
//-----------------------------------------------------------------------------
void applyRule(void)
{
    int i, j, k;                                // počitadla smyček a indexy znaků
    char src[MAX_LENGTH];                       // zdrojový řetězec
    char dest[MAX_LENGTH];                      // cílový řetězec
    int fcount=0;                               // počitadlo přepisů symbolu F
    strcpy(src, ret);
    puts(src);                                  // kontrolní výpis řetězce před přepisem
    for (i=0, j=0; src[i]; i++) {               // projít celým řetězcem
        if (src[i]=='F') {                      // tento symbol se má přepsat
            for (k=0; prepstr[k]; k++)          // provést přepis na základě obsahu
                dest[j++]=prepstr[k];           // řetězce prepstr
        }
        else {                                  // ostatní symboly pouze kopírovat
            dest[j]=src[i];
            j++;
        }
    }
    dest[j]=0;                                  // ukončení řetězce

    for (j=0; dest[j]; j++)
        if (dest[j]=='F') fcount++;
    puts(dest);                                 // kontrolní výpis řetězce po přepisu
    printf("fcount=%d\n", fcount);
    strcpy(ret, dest);                          // kopie výsledku
} 

Obrázek 4: Variace na sněhovou vločku Helge von Kocha

5. Demonstrační příklad na vykreslení Kochovy křivky

Dnešní první demonstrační příklad, který provádí vykreslení Kochovy křivky (Koch Curve) využívá všechny výše uvedené céčkovské funkce. O Kochově křivce již z předchozí části tohoto seriálu víme, že její startovní symbol je roven F, přepisovací pravidlo má tvar F→F=F+F–F+F a úhel otočení želvy je nastaven na 60°. Se znalostí všech funkcí a údajů o gramatice Kochovy křivky již můžeme vytvořit aplikaci, která tuto křivku vytváří a posléze vykresluje. Po překladu a spuštění této aplikace, která pro svůj běh vyžaduje knihovny OpenGL a GLUT, se zobrazí okno s vykreslenou křivkou.

Poměrně zajímavé je nastavení kroku želvy. Ten je vypočten ze znalosti velikosti okna aplikace (resp. pouze horizontálního rozměru) a také toho, že podle počtu iterací (přepisu symbolu F) můžeme zjistit, kolik kroků provede želva v horizontálním směru – s každou iterací je úsečkový segment rozdělen na třetiny a prostřední třetina je vyjmuta, což však nic nemění na tom, že se želva (byť „oklikou“) přes tento prázdný úsek také přesune. Vzorec pro výpočet kroku želvy má tvar:

step=WINDOW_WID­TH/(pow(3, rulesCount))

Kde WINDOW_WIDTH je šířka okna aplikace a rulesCount je počet přepisů symbolu F.

Ovládání této demonstrační aplikace je jednoduché, což ostatně dokládá i následující tabulka:

Zdrojový kód dnešní první demonstrační aplikace je dostupný jak v ASCII formátu, tak i jako HTML stránka se zvýrazněnou syntaxí.

Obrázek 5: Screenshot prvního demonstračního příkladu (inverzní barvy)

6. Demonstrační příklad na vykreslení Kochovy sněhové vločky

Druhý demonstrační příklad je v mnohém podobný příkladu prvnímu, pouze s tím rozdílem, že se vykresluje známá sněhová vločka Helge von Kocha (Koch Snowflake). Nejprve musí být modifikován startovací symbol, který již není nastaven na jediný znak F (vykreslí se úsečka), ale na řetězec F++F++F. Vzhledem k tomu, že úhel otáčení želvy je stále nastaven na 60°, znamená to, že se při interpretaci startovního symbolu vykreslí rovnostranný trojúhelník (symboly ++ způsobí otočení želvy o 120°).

Obrázek 6: Screenshot druhého demonstračního příkladu (inverzní barvy)

Přepisovací řetězec (reprezentující přepisovací pravidlo) je taktéž změněn, a to na hodnotu F-F++F-F. Pokud by tento řetězec nebyl změněn, jednotlivé části křivky by se kreslily směrem „dovnitř“ základního trojúhelníka, což sice také vede k zajímavému tvaru (to si ostatně můžete sami vyzkoušet), ale nejedná se o sněhovou vločku. Ovládání tohoto demonstračního příkladu je stejné jako u příkladu prvního. Zdrojový kód této demonstrační aplikace je dostupný jak v ASCII formátu, tak i jako HTML stránka se zvýrazněnou syntaxí.

Obrázek 7: Netradiční Kochova křivka při nastavení úhlu otáčení na 90°

7. Literatura a odkazy na Internetu

1. Stránka programu LParser
   http://home.wa­nadoo.nl/lauren­s.lapre/lparser­.html 
2. Wikipedia: „Helge von Koch“,
   http://cs.wiki­pedia.org/wiki/Hel­ge_von_Koch
3. Kolka Milan: „Spojování želv v jazyce založeném na L-systémech“,
   http://www.elek­trorevue.cz/clan­ky/01010
4. Tuček Vít: „Implementace L-systému v Prologu“,
   http://artax.kar­lin.mff.cuni.cz/~tu­cev2am/v0.9be­ta/
5. Mr. Zdeeck: „WWW L-System Explorer“ (česky),
   http://zdeeck­.borg.cz/wlse/in­dex.php?lang=cz
6. Hill, F. S. jr.: „Computer Graphics using OpenGL“,
   Prentice Hall, 2001
7. Prusinkiewicz Przemyslaw and Hanan James: „Lindenmayer Systems, Fractals, and Plants“,
   Springer-Verlag, New York, 1989.
8. Prusinkiewicz Przemyslaw and Lindenmayer Aristid: „The Algorithmic Beauty of Plants“,
   Springer-Verlag, NY, 1990. ISBN 0–387–97297–8
9. Weber J., Penn J.: „Creation and Rendering of Realistic Trees“,
   Proceedings of SIGGRAPH '95, volume 22(4), ACM SIGGRAPH, New York, 1995
10. Wegner Timothy, Peterson Mark: „Fractal Creations, First Edition“,
    The Waite Group Press, 1991
11. Wegner Timothy, Tyler Bert: „Fractal Creations, Second Edition“,
    The Waite Group Press, 1993
12. Žára J., Beneš B., Felkel P.: „Moderní počítačová grafika“,
    Computer Press, Praha, 1998, ISBN 80–7226–049–9
13. Žára J., Limpouch A., Beneš B., Werner T.: „Počítačová grafika – principy a algoritmy“,
    Grada, 1992

Obrázek 8: Sierpinského trojúhelník vykreslený L-systémem

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

Výše uvedené L-systémy sice byly tvarově zajímavé, neumožňovaly však vykreslení větvících se struktur. Pro tuto činnost je nutné rozšířit želví grafiku tak, aby si želva mohla do vhodné datové struktury (typicky zásobníku) ukládat – „zapamatovat“ – svůj stav a následně si tento stav obnovit, a tím se vrátit zpět k bodu větvení. Tímto tématem se však budeme zabývat až v navazující části tohoto seriálu, stejně tak způsobem zápisu více přepisovacích pravidel.

Obrázek 9: L-systém využívající zásobník pro ukládání pozice želvy