L-System Plant Geometry Generator

by Hung-Wen Chen
hwchen@cs.cornell.edu
JAN, 1995. EDT 
 	        		
            Figure 1. 3D-1 brcketed OL-system tree          
                For more pictures. Click Here.
Start sting="F" 

Change string="F [- & < F][ < + + & F ] | | F [ - - & > F ]
[+ & F ]"

Count="3"

Angle="22.5"

Set View: Off Diagonal

Table of Contents

Figures


INTRODUCTION


There is nothing more beautiful than scenes involving nature. In nature, the growth of the plant seems to grow in randomness. But if you look carefully, you will find the seemingly random shapes of plant are actually based on a extremely ordered, recusive foundation.

In this project,I use the L-system to generate plant. The L-system were conceived as a mathematical theory of Formal Lanauage, and in this project,its emphasis was on plant topology ,that is , the neighborhood relations between cells or large plant modules.

The purpose of my Master Project in Computer Graphics is to automatically generate realistic trees for use in computer generate pictures. Using the method of Formal Language and beautiful plant, along with some personal additions, realistic trees can be created and include for images.


GOAL


The goal of this project is to create a C module (named tree) for IBM Data Explorer [3].

This module takes a number of parameters as input, such as initial string, change string,the angle of the branch, and the size(depth of recusive) of the plant. The output is a field, consisting of segments,that build the tree. Using Data Explorer, the output combined with other objects and rendered. For ease of use, the module is an Outboard module.


APPROACH


The basic idea of turtle interpretation described by Prusinkiewicz[2] is given below. A state of the turtle is defined as a triplet state (X,Y,Alfa), where the Cartesian coorfinates(x,y) represent the turtle's position , and the angle Alfa ,called the heading , is interpreted as the direction in which the turtle is facing. Given the step size N and the angle increment angle Delta ,the turtle can respond to commands represented by the symbols : F , + , and -.

However, the three symbols can only generate 2 dimensional graphic trees. If we want to generate 3 dimensional graphics, these two operators are not enough.
Therefore ,for 3D graphics, We have to change the tutle's state to (X,Y,Z,Angle_U,Angle_L,Angle_H).

In addition, there are seven operators to deal with the freedom of the 3 dimensions graphics space, such as turn left or right, pitch down or up,and roll left or right, and turn around. All these operators are used to generate the graphics not only in flat plant but also in 3D space.

Angle_U,Angle_L and Angle_H are the three free angle in space, and we increase the number of operators to seven symbols: + , - , & , ^ , < , > , |. In 3D,the key concept is to represent the current orientation of the turtle in space by three vectors H,L,U, indicating the turtle's heading, the direction to the left and the direction up.These vectors have unit length, are perpendicular to each other ,and satisfy the equation H cross L = U. Rotatations of the turtle are then expressed by the equation: 

               [H' L' U' ] = [ H L U]R

where R is a 3*3 rotation matrix. Specifically, rotations by angle Alfa about vectors U ,L ,H are represented by the following matrices: 

                    |  cos(Alfa)   sin(Alfa)     0     |  
     R_U (Alfa ) =  | -sin(Alfa)   cos(Alfa)     0     |  
                    |     0           0          1     | 

                    |  cos(Alfa)      0      -sin(Alfa)| 
     R_L (Alfa ) =  |     0           1          0     |
                    |  sin(Alfa)      0       cos(Alfa)| 

                    |     1           0          0     | 
     R_H (Alfa ) =  |     0        cos(Alfa) -sin(Alfa)|
                    |     0        sin(Alfa)  cos(Alfa)|

All these symbols are described as following :

TREE MODULE DESIGN

The TREE module is designed to be used in IBM DX Explorer.
There are four inputs as following that user can set to generate any tree graphics or complicated pattern.
The key concept is using the change string to recursively replace the start sring, according to the angle , size , and operators we input to generate a tree graphic in DX Explorer.

Initial string

This string is used to set the start status of the tree. Every start stem is located at the origin (0,0,0), and pointed towards the positive Y axis (UNIT VECTOR: [0 1 0]).
The three angle for 3D space, (Angle_U,Angle_L,Angle_H) are set to 0 for the initial state.
The default value is "F", but you can change any pattern as you want.

Change string

This string is used to set the shapes of tree you want. You can choose the seven operators (+ , - , & , ^ , < , > , | ) to generate a 3D space tree , use the bracket ( " [ "and " ] " ) to set the degree of the tree branch , or use "F" to grow stem in the original direction.
The default value is "F [F] F [-F]", but you can change it.

Angle

This angle (Delta) is used to set the angle of the branch.
(For example, " + " is to turn left by angle Delta. " ^ " is to pitch up by angle Delta. " < " is to roll left by angle Delta.)
The default value is "22.5", but you can change it.

Count

This iuput sets the size of tree you want. The recommendation of this value is 3 to 5.
(warning) If the value is too large, the resolution of this graphic will be worse or cause error because the memory space is not enough.
The default value is "3", but you can change it.


RESULTS

 Figure 2. 3D-2 brcketed OL-system tree 
Start sting="F" 

Change string="F [ & + F] F [ - > F][- > F][& F]"

Count="3"

Angle="28"

Set View: Front  

--------------------------------------------------------------------

Figure 3. 2D brcketed OL-system (page 25)Ref[2] 

Start sting="F" 

Change string="F[+F]F[-F]F"

Count="5"

Angle="23.5"

---------------------------------------------------------------------

Figure 4. 2D brcketed OL-system (page 25)Ref[2] 

Start sting="F" 

Change string="FF-[-F+F+F]+[+F-F-F]"

Count="4"

Angle="23"

---------------------------------------------------------------------

Figure 5. Koch curve (page 10) Ref[2] 

Start sting="F-F-F-F" 

Change string="FF-F-F-F-F-F+F"

Count="4"

Angle="90"

CODE OF THE MODULE

There are three source codes written in C language for this module. It will be necessary to edit the Makefiles to reflect the locations of libraries on your system, then compile the code.
These programs as follows are Makefile, plant.c, and plant.mdf.

USING THE MODULES & EXAMPLES

Be sure to load module descriptor(plant.mdf) before you use this module.
The only difference between the 3D and 2D tree are theoperators and the unit vector.

Start with the default count and increase it slowly. The table below shows how execution time depends on Count. 

Example: Start sting="F" 

         Change string="F [< F] F [> F][ F ]"

         Count="n"

         Angle="23.5"
         Time:   n= 1 -->  2.71 sec
                 n= 2 -->  2.78 sec 
                 n= 3 -->  3.10 sec 
                 n= 4 -->  3.15 sec 
                 n= 5 -->  5.37 sec 
                 n= 6 --> 16.14 sec  
                 n= 7 --> 61.40 sec
                 
                 in a IBM RS6000/560

The following examples are correspond to the images shown in this document. For each of these examples,there are control panels to easily change the inputs. Be sure to load these files before you use it.

3D Tree Examples

2D Tree Examples

Complicate Graphics Example

CONCLUSIONS & FUTURE WORK

The 2D version is a special case of the 3D code. The Unit Vector we use is [0 1 0] to let the tree growing in the Y direction. However, if we use the pair operators (+,-) or (<,>), we can generate same trees in different directions in 2D space.For example,the input string:F[+F]F[-F] on XY-Plane, and the input string: F[<F]F[>F] on YZ-Plane, except direction, the shape of two trees are no difference. Therefore, if we define the different Unit Vector, and use the different pair operators, We can generate same trees in different directions.

In this module, all plants generated by the same deterministic L-system are identical. To extend the module function, we can use the concept of the probability, we can generate different tree graphics. It is necessary to introduce specimen-to-specimen variations that will preserve general aspects of a plant but will modify its details. For example, F-->F[+F][F] (P=0.33) and F-->F[-F][F](P=0.67). Moreover, if we introduce more Variables, not only F variable ,for example, the following variables: A,B,C,D,E,F...., we will generate more complicate trees in space.

ACKNOWLEDGEMENT

My faculty advisor,Bruce Land, helped me develop the initial idea and gave me direction throughout.

REFERENCES

[1] John E. Hopcroft, and Jeffrey D. Ullman [1979], "Introduction to Automata Theory, Languages,and Computation.", pp 55-100.

[2] Prusinkiewicz,Przemyslaw [1990], "The Algorithmic Beauty of Plants", pp 1-50.

[3] IBM Visualization Data Explorer 4th Edition, User's Guide and Programmer's reference. For more information, click Here.