CSCI 590 Directed Research

CSCI 590 Directed Research

Progress Report 1

L-Systems Tree and its Animation

By Tanasai Sucontphunt

Date: 3/4/2003

Contents

1) L-systems

2) Timed L-Systems Implementation

3) What’s Next?

1) L-Systems

Our research uses widely known L-systems invented by biologist Aristid Lindenmayer as the core of geometric modeling of plant system. The L-systems model is used for creating the pattern of the plant as the plant structure is somehow being pattern by its nature. This system can be viewed as parallel rewriting systems which rewrite the given string over and over again in parallel until reaching its defined length.

The L-systems consist of production rules which are the content of the new string to replace the existing string such as “F -> F+F” means replacing “F” by “F+F”, the left hand side(F) is called predecessor and the right hand side(F+F) is called successor.

The procedures of plant modeling with L-systems are first, giving the seed, which is called axiom, of the string (the very first string to be replaced); second, applying production rules to replace the string iteratively until reaching the limited sting length; third, after we got the final string, which is out plant structure now, we interpret them geometrically to be drawn on the screen.

To draw the geometric from strings, we use a turtle graphic technique. The turtle technique produces the geometric graphic by interpreting the string as the drawing commands.

The five major interesting L-systems variables are

1) D0L-System, this is the simplest class of L-system. This approach just replaces each string symbol by the defined production rules. It’s deterministic and context-free approach. It’s deterministic since in the production rules, there is only one possible predecessor. It’s a context-free since we can replace every single symbol in parallel regardless of its location.

2) Bracketed L-systems, this type use the bracket to define the branching such as “A -> [+FBF]” which means when it reach “[“, it push the current state in stack and when it reach “]”, it will pop the state back. It uses the stack operations (push/pop) to store and retrieve its state of branch. It’s nondeterministic since their can be more than one predecessor to be selected from the rules, but it’s a context-free.

3) Stochastic L-systems, this is the type of nondeterministic L-systems. If the rules have the same predecessor, we can define the probability of each rule to be selected in different manner. This will make the plant looked more realistic as in the nature.

4) Context-sensitive L-systems, this approach has many advantages. The production on this approach is not only depended on the string symbol but also the symbol’s location as well. We can use this approach to generate more realistic plant and also to simulate other aspects of plant such as cope with parametric values to create information flow in developing plant.

5) Parametric L-system, this approach is the essential of the plant animation, our research. We can define the parametric values in each branch to be passing to other branches and also to be updating its own values over time. The interesting one is the Timed L-systems which use timing value as its parametric value.

Our work will focus on the Parametric, bracketed, Stochastic, and context-sensitive L-systems. Our plant growth is simulated by using these approaches. We use the parametric to define the branches’ length, age, and thickness over time. We use the bracketed to define the branching level. We use the stochastic and context-sensitive to make our plant has more realistic feature. We will call these approaches as short as only Timed L-systems since the core of our work is on parametric timing.

2) Timed L-systems Implementation

For now, we implemented our program using the above approaches. However, we used the fixed production rules in order to focus on the growth simulation rather than the plant pattern. We have created 3 types of patterns using the bracketed, context-sensitive production rules which are:

Type 1:

S => I

I => TB

B => [-I][+I]

TB _last=> T _green

This type creates the branch of the plant in Y–shaped as its two children branches (internodes) are grow in opposite direction by given angle.

Note: S = Seed, I = internode, T = Stem, B = Bud, + = go clockwise in given angle, - = go counterclockwise in given angle, TB _last= TB symbol of the final string, T _green = Leave.

Type 2:

S => I

I => TB

B => [-I]TA

A => Y

Y => [-I][+I]

TB _last=> T _green

This type creates more complicated branch. It creates its two children branches one on the left and one on the same line as the parent stem. If the parent stem of the children is the latter case children from grand parent, then the branches grow as Y-shaped as in the first type.

Additional Note: A = Y–Shaped internode, Y = Y-shaped Bud

Type 3:

S => I

I => TB

B => [+I]TA

A => Y

Y => [-I][+I]

TB _last=> T _green

This type is much the same as type 2 but its one child is growing on the right.

From above defined three types, our program using the Stochastic approach by defining each type’s probability to create more realistic pattern. We set the chosen probability of type 1 to be 0.3, type 2 = 0.35, type 3 =0.35.

To be more realistic, each child will reduce its length and thickness by 0.8 and from its parent.

Now, the crucial method of simulating the plant growth is the timing parametric. The parametric values for each branch we used now are age, length, thickness, and split age. We set the parametric of the age to be the range from 0 to 1 in each branch. If the branch is fully growth, it will stay on the pre-defined “length” value. We use the age value to measure its length over time from 0 to 1 mapping length linearly from 0 to length, and in the same way as its thickness. We use the split age to define when to split its children. The split age is range from 0 to 1. If it set to 1, it means that the children will split when the parent is fully growth only.

So, the input that we need user to enter in the “input.txt” is

1) Number of generation to be created, N (2^N = number of maximum string length)

2) Speed which defined as number frames per branch creating

3) Split age

4) Angle of the branches to be split

5) Length of the first branch (main stem)

6) Type of the branches (Stochastic as a default)

Here are the sample screen shots of our program (C++/OpenGL) if we set

Number of generation to be created =10,

Speed = 10 frames,

Split age = 0.5,

Angle = 20,