Table of Contents:

Brief Introduction to Lindenmayer Systems:

Lindenmayer Systems are a textual substitution system similar to fractal systems. The basic idea is that you have a group of symbols, each of which represents a specific object, say a leaf.  Also associated with each symbol is a substitution rule. This rule specifies which group of symbols would replace the symbol associated with it. You would start with an initial string of these symbols.  After one time step, each symbol would be replaced with the string specified by its substitution rule. The following example illustrates the idea.

a -> a [ ' a ' ] a

initial string = a

time step 1: a

time step 2: a [ ' a ' ] a

time step 3: a [ ' a ' ] [ ' a [ ' a ' ] a ' ] a [ ' a ' ] a

...

The idea can be further complicated by adding multiple substitution rules to some or all symbols. The appropriate rule can then be chosen in many ways. It could be chosen iteratively based upon previous symbols in the string, or stochastically based upon a random process.. This leads to plants that all share a similar structure yet do NOT look like exact copies of each other.

Objective:

The objective of this project was to build an L-Systems generator, using visual C++ and OpenGL under Windows, that would read a list of symbols, a list of substttutions, an initial string, and then render a realistic looking plant. The engine would be capable of being modified so that it could render any number of plants or any other applicable organism, as well as give a better grasp of OpenGL programming under Windows.

Implementation:

The generator is basically divided up into three parts, a data file, a parser, and a renderer. We will describe them one at a time.

Data File:

The file format for the Generator can be broken down into several major sections which together comprise all information required to draw an L-System. In order of appearance within the file,

Parser:

The parser first reads in symbols section of the data file. Internally, each symbol is represented by an integer. The class representing th symbol contains all of the information regarding the individual symbols that is given in the datafile. In order, they are the token-type, translation matrix, rotation angle, rotation matrix, scaling vector, and finally two booleans that specify whether or not the rule pushes onto the stack or pops from the stack. Next, the rules are read in. The class representing the rules has two major data elements, the internal integer representation of the symbol to be replaced, and an array of integers to replace it. Finally, the parser reads in a list containing the initial string for the object to be rendered. It converts the list into an array of integers just like for the other two. Then, after a single time step, it looks through the array for the initial string. For each symbol it looks in the rule table for the appropriate substitution rule. If it finds it, it then replaces the symbol with the appropriate rule. It does this for all the rules. Then it sends the array to the renderer.

Renderer:

The renderer accepts a string containing the current state of the L-system, and access to the rule table, which contains drawing information for all the symbols. The rendering engine for L-Systems is based upon a turtle graphics engine. The Turtle always faces the positive Y-axis. It draws upwards in this direction, based on what type a symbol is. Rotating and scaling affect all future draws. When the position of the turtle is pushed to or popped from the stack, its orientation and scaling are transferred as well. OpenGL makes this system easy to implement with driect functional implementation of translation, rotation, scaling, and matrix stack operations. Functions like glTranslate(), glPopMatrix(), and many others made this Turtle engine relatively simple to implement.

Results:

Here are some images of the resulting Dragon Curve and a trifurcating Plant.

Further Information:

You can find a wealth of information on L-Systems in the books at the end of the page. A few ideas would be to use the generator to create bacteria or models of tissue or cells. This would mostly involve writing the correct initial string and symbols/substitutions. You could also try to extend the type of substitution done. As we implemented it, each symbol is paired with a single rule. A potential problem stems from this. Every plant generated with the same intial string will have the exact same appearance. Thus if you wanted to create a field of flowers for a particular scene, every flower would look like a mirror image of every other flower. This can be remedied by having several rules for each symbol. You could choose through the different rules stochastically, generating variations in the flowers rendered. (Note: There are many other ways to choose between several rules such as weighted average or simple iteration.) These resulting variations make different versions of the same plant actually look different.

Download:

The generator has one executable, two sample files, and requires versioe 4.2 of the Microsoft Foundation Classes, as well as Opengl for Windows 95. These last three documents should go in the WINDOW\SYSTEM directory.

lparse.exe,   plant.l, fractal.l,  MFC42.DLL,   OPENGL32.DLL, GLU32.DLL

Acknowledgements:

We would like to thank Prof. Bruce Land for his time and patience in helping us through this project. Without his support and guidance, this could not have been completed. We would also like to mention our appreciation of the books mentioned in the References at the end. Without their clarity and wealth of information, we would not have had the information needed to finish this project. We would also like to thank PepsiCola Inc. for being able to produce enough Mountain Dew to meet our demanding needs. Remember, if you call yourself a CS person and you don't drink Mountain Dew, you're living a lie.

References:

Rozenberg, G., and Salomaa, A. eds. The Book Of L. Springer-Verlag. Berlin: 1986.

Prusinkiewicz, P. and Lindenmayer, Aristid. The Algorithmic Beauty of Plants. Springer-Verlag. New York: 1990.