hwchen@cs.cornell.edu

JAN, 1995. EDT

Figure 1.For more pictures. Click Here.3D-1 brcketed OL-system tree

Start sting="F"

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

Count="3"

Angle="22.5"

Set View:Off Diagonal

- Introduction
- Goal
- Approach
- Tree module design
- Results
- Code of the Module
- Using the Modules & Examples
- Conclusions & Future Work
- Acknowledgment
- References

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.

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.

The basic idea of turtle interpretation described by Prusinkiewicz[2] is given below. A state of the turtle is defined as a triplet state

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 :

- "
*F*" : Move forward a step of length d. A line segment between points**(X,Y,Z)**and**(X',Y',Z')**is drawn. - "[" and "]": bracket - push and pop the current state , in this project it is used to generate the tree branchs.
- "
*+*" :**Turn**left by angle Delta, Using rotation matrix**R_U**(Delta). - "
*-*" :**Turn**right by angle Delta, Using rotation matrix**R_U**(-Delta). - "
*&*" :**Pitch**down by angle Delta, Using rotation matrix**R_L**(Delta). - "
*+*" :**Pitch**up by angle Delta, Using rotation matrix**R_L**(-Delta). - "
*<*" :**Roll**left by angle Delta, Using rotation matrix**R_H**(Delta). - "
*>*" :**Roll**right by angle Delta, Using rotation matrix**R_H**(-Delta). - " | " :
**Turn around**, Using rotation matrix**R_H**(180).

There are four inputs as following that user can set to generate any tree graphics or complicated pattern.

- "
**Initial string**": To set the start stem of the tree. - "
**Change string**": To set the direction in 3D space and the shapes of the tree you want to generate. - "
**Angle**":(delta) To set the branch angle. - "
**Count**":(N) To set the size of the tree.(depth of recursion)

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.

The three angle for 3D space, (Angle_U,Angle_L,Angle_H) are set to 0 for the initial state.

The default value is "

The default value is "

(For example, " + " is to

The default value is "

(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 "

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)*

Start sting="F"

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

Count="5"

Angle="23.5"

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

*Figure 4. 2D brcketed OL-system (page 25)*

Start sting="F"

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

Count="4"

Angle="23"

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

*Figure 5. Koch curve (page 10) *

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

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

Count="4"

Angle="90"

These programs as follows are

The only difference between the 3D and 2D tree are the

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.

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.

[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.