mario::konrad
programming / C++ / sailing / nerd stuff
Lindenmayer System
© 2003 / Mario Konrad

Introduction

A L-System (Lindenmayer System) is a mathematical formal system. Its name comes from the biologist Aristid Lindenmayer (1925-1989), who founded a formal system to study the evolution of cell organism.

Another article wrote Alvy Ray Smith 1984, in which he questioned the usability of L-Systems to create realistic plants. An L-System is able a lot more than that. It is able to create numerous of different fractal forms.

Its functionality is based on replacing rules and those rules apply all at the same time (parallel). According to the desired number of replacing iterations, the replacements take place in every iteration even recursively to itself.

Since this is only a very short introduction into L-Systems, this site isn't going further into details. Please read other resources about this topic to get more information.

OpenGL Demo

This demo (comes with source code as well), shows a plant using OpenGL. The Page also explains what to do interactively with the demo and also goes through the source code (but it is not a complete tutorial).

Read the page for the requirements for the demo. It will also explain what to do do compile and run.

Requirements

Operating System: Linux
::: Windows 9x/NT/2k with Cygwin
OpenGL Library: Mesa (for example)
Misc Dev. Tools: GCC 2.95 or newer
::: make (optional)

Source Code

It is only a single source file: lsystem.c

Maybe you like to compile using the make utility, you will need one of the following files, depending on which system you are compiling:

TODO

Compile and Run

Proceed to one of the following chapters (depending on which system you work).

Linux and gcc

Assuming you use the make utility:

$ make -f Makfile.gcc

If you don't use the make utility:

$ gcc -c lsystem.c
$ gcc -o lsys lsystem.o -lglut -lGLU -lGL

Windows 9x/NT/2k and Cygwin

You will need to start the bash in order to compile the demo:

    ..\demo> bash

Using the make utility:

$ make -f Makefile.cygwin

Comiling without make:

$ gcc -c lsystem.c
$ gcc -o lsys lsystem.o -lglut32 -lglu32 -lopengl32

Usage

After you have successfully compiled and linked (or used the make utility), you're able to start the demo:

$ ./lsys

The following table shows which keys you can use to interact with the demo:

Key Description
+ Zoom in (picture gets bigger)
- Zoom out (picture gets smaller)
a Use recursive depth of 1
s Use recursive depth of 2
d Use recursive depth of 3
f Use recursive depth of 4
ESC Exit

Future

There are some things left to do, if I find time and passion. The source code already contains all features of a 3D system. You are not able to rotate the figure yet (but hopefully soon), but the figre you can see is acutally already in 3D (!). If you are interested in this feature do it or contact me.

Source Code Walkthrough

Let's have a look at the source code.

First there are some header to include.

#include <stdio.h>
#include <math.h>
#include <strings.h>
#include <unistd.h>
#include <GL/gl.h>
#include <GL/glu.h>
#include <GL/glut.h>

Some define's to make:

#define MAX_EXPAND 128

Now we need some data structures.

/* 3D vector, holds position information */
struct Vec3
{
    float x[3];
};

/* Context of a state */
struct Pos
{
    struct Vec3 vec;
    float xy_angle;
    float yz_angle;
    struct Pos * prev;
    struct Pos * next;
};

/* Configuration of the production */
struct LSystem
{
    char func;
    char expand[MAX_EXPAND];
    int n;
    float dist;
    float phi;  /* angle on the x-y-plane */
    float rho;  /* angle on the y-z-plane */
    struct Pos * current;
};

/* Structure for a stack */
struct PosStack
{
    struct Pos * anchor;
    struct Pos * top;
    int count;
};

I don't like global variables, but we need some. It simplifies the program.

struct LSystem * lsys;
struct PosStack * stack;
float scale = 1.0;

Now, there are some functions which do nothing really heavy. They initialize one of the structures above, destroy them or fill them with data, easy. Sorry I haven't sorted them.

void copy_pos(struct Pos * dest, struct Pos * src)
{
    int i;
    for (i = 0; i < 3; i++) dest->vec.x[i] = src->vec.x[i];
    dest->xy_angle = src->xy_angle;
    dest->yz_angle = src->yz_angle;
    dest->prev = 0;
    dest->next = 0;
}

void set_pos(struct Pos * pos, float x, float y, float z)
{
    if (!pos) return;
    pos->vec.x[0] = x;
    pos->vec.x[1] = y;
    pos->vec.x[2] = z;
}

void set_vec3(struct Vec3 * dest, struct Vec3 * src)
{
    int i;
    if (!src || ! dest) return;
    for (i = 0; i < 3; i++) dest->x[i] = src->x[i];
}

void set_pos_vec(struct Pos * pos, struct Vec3 * vec)
{
    if (!pos) return;
    set_vec3(&pos->vec, vec);
}

void add_to_pos(struct Pos * pos, float x, float y, float z)
{
    if (!pos) return;
    pos->vec.x[0] += x;
    pos->vec.x[1] += y;
    pos->vec.x[2] += z;
}

struct Pos * create_pos(float x, float y, float z, float xy_angle, float yz_angle)
{
    struct Pos * pos = (struct Pos *)malloc(sizeof(struct Pos));
    set_pos(pos, x, y, z);
    pos->xy_angle = xy_angle;
    pos->yz_angle = yz_angle;
    pos->prev = pos->next = 0;
    return pos;
}

struct Pos * create_default_pos()
{
    return create_pos(0, 0, 0, 0, 0);
}

void destroy_pos(struct Pos * pos)
{
    if (!pos) return;
    free(pos);
}

void reset_lsys(struct LSystem * lsys)
{
    if (!lsys) return;
    destroy_pos(lsys->current);
    lsys->current = create_pos(0.0, 0.0, 0.0, M_PI * 90.0 / 180.0, 0.0);
}

struct LSystem * create_lsys(char func, const char * expand, int n, float dist, float phi, float rho)
{
    struct LSystem * lsys = (struct LSystem *)malloc(sizeof(struct LSystem));
    lsys->func = func;
    strcpy(lsys->expand, expand);
    lsys->n = n;
    lsys->dist = dist;
    lsys->phi = phi;
    lsys->rho = rho;
    reset_lsys(lsys);
    return lsys;
}

void destroy_lsys(struct LSystem * lsys)
{
    if (!lsys) return;
    destroy_pos(lsys->current);
    free(lsys);
}

The following function deal with the position stack. Quite more interesting than the above, but not heavier either.

struct PosStack * create_pos_stack()
{
    struct PosStack * s = (struct PosStack *)malloc(sizeof(struct PosStack));
    s->anchor = s->top = create_default_pos();
    s->count = 0;
    return s;
}

void push_pos_stack(struct PosStack * stack, struct Pos * item)
{
    if (!stack || !item) return;
    stack->top->next = item;
    item->prev = stack->top;
    stack->top = item;
    stack->count++;
}

struct Pos * pop_pos_stack(struct PosStack * stack)
{
    struct Pos * tmp;
    if (!stack) return 0;
    if (stack->top == stack->anchor) return 0;
    tmp = stack->top;
    stack->top = stack->top->prev;
    stack->top->next = 0;
    stack->count--;
    return tmp;
}

void destroy_pos_stack(struct PosStack * s)
{
    if (!s) return;
    while (s->top != s->anchor)
    destroy_pos(pop_pos_stack(stack));
    free(s);
}

The next two functions draw some lines, but don't deal with the production itself.

void draw_line(float x0, float y0, float z0, float x1, float y1, float z1)
{
    glColor3f(0.5f, 0.5f, 0.5f);
    glBegin(GL_LINES);
    glVertex3f(x0, y0, z0);
    glVertex3f(x1, y1, z1);
    glEnd();
}

void draw_line_vec(struct Vec3 * v0, struct Vec3 * v1)
{
    glColor3f(0.5f, 0.5f, 0.5f);
    glBegin(GL_LINES);
    glVertex3fv(v0->x);
    glVertex3fv(v1->x);
    glEnd();
}

Let's have a look at the most interesting part: the production. We will go more into details for this one.

void production(struct LSystem * lsys, int level, const char * str)
{
    int i;
    int len;
    struct Vec3 vec;
    struct Pos * tmp;

So far nothing spectacular. Since this is a recursive function we need a termination (not let going the function even deeper in the recursion):

    if (level < 0) return;

Now we need a loop to do something for each item of the production rule (field struct LSystem { ... char expand[...]; ... }).

    len = strlen(str);
    for (i = 0; i < len; i++)
    {

Now we have access to every item of the rule: str[i], and are able to process it.

        if (str[i] == lsys->func) /* draw a visible line */
        {

If it is already at the bottom of the desired recursion depth draw it, otherwise call the function recursively with one level less.

            if (level) production(lsys, level-1, lsys->expand);
            else
            {

We have reached the bottom, so let's draw that line. First calculate the new 3D coordinates then draw from the last point to the current and set the calculated point as current.

                vec.x[0] = lsys->current->vec.x[0] + lsys->dist * cos(lsys->current->xy_angle);
                vec.x[1] = lsys->current->vec.x[1] + lsys->dist
                  * sin(lsys->current->xy_angle) * cos(lsys->current->yz_angle);
                vec.x[2] = lsys->current->vec.x[2] + lsys->dist * sin(lsys->current->yz_angle);
                draw_line_vec(&lsys->current->vec, &vec);
                set_pos_vec(lsys->current, &vec);
            }
        }
        else if (str[i] == islower(lsys->func)) /* draw a hidden line */
        {

If it is already at the bottom of the desired recursion depth draw it, otherwise call the function recursively with one level less.

            if (level)
            {
                production(lsys, level-1, lsys->expand);
            }
            else
            {

We have reached the bottom, but we must not draw the line. So we set the calculated coordinates as current point.

                add_to_pos(lsys->current,
                  lsys->dist * cos(lsys->current->xy_angle),
                  lsys->dist * sin(lsys->current->xy_angle) * cos(lsys->current->yz_angle),
                  lsys->dist * sin(lsys->current->yz_angle));
            }
        }

The last part of this function is the handling of the other items in the rule.

        else
        {
            switch (str[i])
            {
                case '+':
                    lsys->current->xy_angle += lsys->phi;
                    break;
                case '-':
                    lsys->current->xy_angle -= lsys->phi;
                    break;
                case '*':
                    lsys->current->yz_angle += lsys->rho;
                    break;
                case '/':
                    lsys->current->yz_angle -= lsys->rho;
                    break;
                case '[':
                    tmp = create_default_pos();
                    copy_pos(tmp, lsys->current);
                    push_pos_stack(stack, tmp);
                    tmp = 0;
                    break;
                case ']':
                    tmp = pop_pos_stack(stack);
                    copy_pos(lsys->current, tmp);
                    destroy_pos(tmp);
                    tmp = 0;
                    break;
                default: /* illegal character */
                    break;
            }
        }
    }
}

The following parts are used to set up the graphics part. Initialisation, reshaping and drawing are their businesses. The keyboard handler is also in this section, but does not do really interesting things.

void init()
{
    glClearColor(0.0, 0.0, 0.0, 0.0);
    glShadeModel(GL_SMOOTH);
    glFrontFace(GL_CCW);
    glEnable(GL_CULL_FACE);  /* enable culling */
    glEnable(GL_DEPTH_TEST); /* enable depth testing */
    glPolygonMode(GL_BACK, GL_LINE);
    glPolygonMode(GL_FRONT, GL_FILL);
}

void reshape(int width, int height)
{
    glViewport(0, 0, (GLint)width, (GLint)height);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluPerspective(45.0, (float)width/(float)height, 1.0, 100.0);
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
}

void display()
{
    destroy_pos_stack(stack);
    stack = create_pos_stack();
    reset_lsys(lsys);

    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glLoadIdentity();
    glTranslatef(0.0, -15.0, -50.0f);
    glScalef(scale, scale, scale);
    production(lsys, lsys->n, "F");
    glFlush();
    glutSwapBuffers();
}

void keyboard(unsigned char key, int x, int y)
{
    static const float angle_step = 2.0;
    switch (key)
    {
        case 27: exit(0);
        case 'a': lsys->n = 1; glutPostRedisplay(); break;
        case 's': lsys->n = 2; glutPostRedisplay(); break;
        case 'd': lsys->n = 3; glutPostRedisplay(); break;
        case 'f': lsys->n = 4; glutPostRedisplay(); break;
        case '+': if (scale < 3.0) scale += 0.25; glutPostRedisplay(); break;
        case '-': if (scale > 0.5) scale -= 0.25; glutPostRedisplay(); break;
        default: break;
    }
}

Last but not least: the main function.

int main(int argc, char ** argv)
{
    lsys = create_lsys(
      'F',
      "FF+[+*F-/F-/F]-[-/F+*F+*F]",
      4,
      0.5,
      M_PI * 22.5 / 180.0,
      M_PI * 22.5 / 180.0);

    glutInit(&argc, argv);
    glutInitWindowSize(500, 500);
    glutInitWindowPosition(0, 0);
    glutCreateWindow("L-System");
    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE);
    init();
    glutReshapeFunc(reshape);
    glutDisplayFunc(display);
    glutKeyboardFunc(keyboard);
    glutMainLoop();

    destroy_lsys(lsys);
    destroy_pos_stack(stack);
    return 0;
}

Demo Applet

Source of the demo applet, use it at your own risk for whatever purpose you like.

All files in one archive: