L-System Generated Trees

Matthew Kehrt and Ben Lerner

Background

Lindenmayer Systems or L-Systems are grammars originally used to describe growth of biological structures, expecially those of plants [1]. They can be used to produce images of plants as well as more mathematical objects such as fractals.

L-Systems consist of a series of productions of the form

predecessor -> successor

where each of predecessor or successor is a series of symbols drawn from some alphabet. From a given start symbol or string, these rules are applied in parallel to produce a new string. This process can be repeated indefinitely. Given appropriate initial strings and rules, the resultant strings model various biological structures. This basic system can be augmented with randomness, paramaterized properties and nondeterminism.

Once this machinery is in place, various ways of visualizing the strings can be added. One of the easiest of these is turtle graphics, where the produced string is a program describing the path of a pen drawing an image. Pictures of plants and other recursive structures can be produced this way. A more complex method of visualization is converting the produced string into a three dimensional model of the structure.

Problem

We investigated how to use L-System descriptions to animate plants using OpenGL. We created an L-System parser to produce OpenGL hierarchical models of plants, and we used a system similar to a particle system to animate them.

Work

We implemented two major components. The first is a parser for L-Systems which produces a hierarchical model. The language used is based on one from [1]. In this language, strings describe the structure of plants by specifying a series of cylindrical segments in three dimentions. Capital letters {A,B,C,...} indicate segments to be represented by cylinders in our model, and lowercase letters {a,b,c} indicate segments which are invisible. At a given point in a string, there is a current segment length and angle at which to draw the segment. Other characters in the string act as operators to change these parameters. The current segment is drawn with these settings, and the following segment begins where this one ends.

For instance, a simple exampe would be the rule

A -> AA

This would draw simply a straight line, which would be subdived multiple times. Two useful operators are + and -, which rotate the angle at which to draw the next segment. These are used in

A -> A+A--A+A

which, at one itereation, draws a line with a triangular bump in it. Iterated multiple times, it draws the Koch curve.

Another pair of useful operators are [ and ]. The first pushes the current settings (angle and length) onto a stack and the second pops the top off the stack and replaces the current settings with it. This allows us to save points to return to in the future. An example using this is

A->BB+[+A-A-A]-[-A+A+A]

After converting our L-Systems into hierarachical models, we may wish to animate them. We do this in a similar manner to a particle system. Each segment lives n its own space with the origin and the end of its parent. Each segment experiences several torques which may cause it to rotate. One of these is a torque back towards the position it belongs. Other forces can be added, such as wind or drag. Using these, we can simulate trees blowing in the wind.

Tree with force vectors

Tree without force vectors

Notes

Przemyslaw Prusinkiewicz, Mark Hammel, Jim Hanan, and Radomir Mech. L-systems: from the theory to visual models of plants. In M. T. Michalewicz, editor, Proceedings of the 2nd CSIRO Symposium on Computational Challanges in Life Sciences. CSIRO Publishing, 1996.