This chapter contains background on Lindenmayer systems (L-systems for short) and description of several different types of L-systems. A new language for geometrical interpretation of the strings that are generated by L-systems is created which is also listed in this chapter. Finally, methods for generating clouds and mountains are described.

The notion of Lindenmayer systems was conceived in 1968 by Aristid Lindenmayer as a mathematical model of biological development. L-systems were developed in order to study the development of simple multicellular organisms. Later they were also used to investigate higher plants and plant organs. Once geometrical features were introduced, it became possible to graphically visualize plants.

The central concept of L-systems is that of rewriting. This is very useful when defining complex objects, and is done by successively replacing parts of an initial object according to a set of rewriting rules/productions/generators. The rewriting rules can be defined for geometrical objects, but the technique used here will only consider rewriting rules for character strings. This gives more flexibility since some letters will be given a geometrical representation, whereas others can get arithmetical meaning. A decade earlier Chomsky had already presented his work on context-free grammars that used rewriting rules. The difference between Chomsky's grammars and L-systems is that Chomsky's grammar productions are applied sequentially, whereas in L-systems they are applied in parallel, and therefore replace all characters in a string simultaneously. Most of the work behind L-systems is done by Lindenmayer himself and Przemyslaw Prusinkiewicz [19, 20], but research has been done by many more [21, 22, 23]. Some of the work can also be found on the internet [24, 25].

Several types of L-systems exist, DOL-systems (Deterministic context-free L-systems) [19] are the simplest of them. They are defined as triplets.

1. Alphabet: the set of characters that are used.
2. Axiom is the initial string of one or more characters.
3. Rewriting or production rules are a set of transitions from one character to a string of one or more characters.

Here is an example to illustrate how it works:

The last two rules are often omitted, since no actual rewriting is done.

By applying the rewriting rules a number of times we will get a larger and larger string.

Figure 33: Three generations of a DOL-system.

This technique can easily be extended to create graphical objects from the generated strings. There are several ways to do this, but the graphics we create in this thesis is obtained by using a LOGO-style turtle [26], where the turtle is defined by its position and orientation. The graphics is generated by translating each character in the alphabet into a turtle command. It should also be mentioned that sometimes it can be convenient to translate a character to "do nothing". The example above can be extended to a graphical representation as follows:

Commands represented by characters:

F Draw forward default length.

- Turn left default angle.

+ Turn right default angle.

The turtle can respond to these commands when default length and angle is set.

Default length = 10

Default angle = 60

Figure 34: Generations of Lindenmayer fractal. Koch curve.

The Koch curve in Figure 34 could also have been created using the IFS technique, but as mentioned earlier the DOL-systems are the simplest class of L-systems. A much more powerful class of L-systems is bracketed OL-systems. A turtle stack is added to DOL-systems thus allowing branching structures. Two new symbols are introduced with the following meanings:

[ Push the state of the turtle onto the stack. The data pushed onto the stack must contain turtle position and orientation. It can also contain information about color, size, default angle and length if this information is used.

] Pop a state from the stack. This will reset the state of the turtle to the state when it was pushed.

Figure 35: "Peacock". Bracketed OL-systems.

Bracketed OL-systems may look fairly similar to plants, but they still look too perfect. Further improvement in the modeling of nature is made when "chance" is used to affect the creation of objects [19]. This improvement is achieved with stochastic L-systems and allows several production rules for one and the same character. Chance will decide which production will take place.

(0.2) F -> [-F]F (The probability for this production to take place is 20%)

(0.2) F -> [+F]F (The probability for this production to take place is also 20%)

(0.6) F -> FF (The probability for this production to take place is 60%)

The sum of probabilities must be 1.

The plants will often look too perfect even when stochastic L-systems are implemented. The reason is that all angles have to be a multiple of the smallest angle, and lines have to be a multiple of the smallest line. In order to solve this problem, a numerical parameter is sent with the L-system symbols. In Figure 36, an image is created by moving the turtle forward by the default distance and by turning the turtle right or left 84° or 90°. Since only one default angle can be set, this is not feasible without the use of parameters. It is possible to use the parameters as absolute values (example: 90°) or as relative values (example: half the default value). Different symbols are to indicate if the following parameter is absolute or relative (See Section 7.9).

Figure 36: Peano-Cesàro curve can easily be generated by parametric L-systems, but is practically not feasible if modeled with L-systems without parameters.

The last extension is the braced L-systems. So far we have been concerned only with movement and drawing lines, but to be able to model objects correctly, we need to also create surfaces. There are several approaches available [19] that can be used, and their usefulness depends on the implementation. The first method is to use a symbol to mark the start of a polygon. Every movement by the turtle marks a surface node of a polygon, until the end of the polygon symbol is encountered. Another method uses a symbol to mark a polygon vertex; thus allowing several moves in a row before a vertex is marked. A third method is to use several predefined bicubic patches that can be drawn when a predefined surface symbol and a surface parameter are encountered. Surfaces like leaves, fruits and berries can be defined in this way. This makes it possible to write compact rewriting rules for detailed plants.

Three dimensional models are needed to create realistic models that can be fed to ray tracers as input for realistic images. The turtle's position must therefore be stored in three dimensions. What previously was labeled direction is in 3D called orientation. The orientation is stored as three vectors indicating Forward, Up and Right. These vectors have unit length and are perpendicular to each other. The turtle's orientation is changed by rotations around these three vectors.



Figure 37: Turtle orientation.

Rotation about the forward vector:

F = F

U = sin() * R + cos() * U

R = sin() * U - cos() * R

Rotation about the up vector:

F = sin() * R - cos() * F

U = U

R = sin() * F + cos() * R

Rotation about the right vector:

F = sin() * U + cos() * F

U = sin() * F - cos() * U

R = R

Once the string from the L-system is generated, the symbols must be translated into turtle commands according to a predefined pattern. There seems to be no standard for a translation of symbols into turtle commands. L-systems almost exclusively have been used to model plants. This thesis explores a method free of restrictions in the language. This freedom makes it possible to examine the ability of using L-systems for modeling mountains, clouds and water. Therefore is an own language created of turtle commands (which have similarities with the one found in [19]).

Turtle movements commands

Turtle rotation commands (FUR: Forward, Up, Right)

Thickness commands

General objects

Color commands

Angle commands

Length commands

test

The following input parameters are needed for all types of L-systems,: a start sentence, one or more rewriting rules, and the number of generations. Further parameters can be used for default setting of length, angle, thickness and color, transition probabilities and surface descriptions.

L-systems can really create realistic images despite the small number of input parameters. They are also very flexible. It seems that only imagination sets the limit for creation of the objects.

The number of objects that is created often varies exponentially with the number of generations. The time to generate an image of a model can therefore vary a lot. Most models will have less than 10,000 objects, and are generated in less than one minute. If the shape is really complex then it can take much longer. The best results are achieved if the model is fed through a ray tracer. The time to ray trace one image varies between ray tracers. The tree in Figure 38 is created by more than 3,000 cylinders and took 15 minutes to ray trace with a resolution of 640x480. It only took five seconds(!) for the L-system program to generate the 150 Kb large file used by the ray tracer. Both measurements are on a 100MHz 486 PC.

Most work on L-systems is entirely focused on modeling of plants. The following sections will show how to use this tool for modeling mountains and clouds. This method can also be extended for modeling fantasy animals but that is outside the scope of this thesis.

When modeling mountains, the generation of strings and movement through space in 3D is similar to that of plants. Instead of creating spheres, surfaces and other objects, shapes of hills and valleys are created. The height map technique, as explained in chapter 4, is again used for generating an L-system mountain. The shape of a hill or valley is defined so that the turtle's y-value (The logarithmic value of the y-position can also be used) specifies the height/depth, the thickness variable sets the width, and a set of symbols that trigger the generation of a mountain will specify the silhouette of the hill or valley. The x- and z-position of the turtle will determine the centerpoint of the hill or valley in the height map. All hills and valleys that are created are superimposed. Every hill and valley will "push" the surface up or down. A great amount of differently shaped mountains can be created in this way.

One has to be careful so that the shape does not get too high or low since this will create some extreme peaks. The best technique is to use a "core" that only moves in the horizontal plane. From this core branches are sent out which continue at most three moves away from the core and the ground surface. Branches are sent out in more or less random direction to create mountains and valleys. To create a ridge, the core be can moved straight ahead and the branches are sent upwards.

Figure 39: L-systems mountain ridge

We use L-systems to create a file that is fed to a ray tracer. The L-system will determine the shape of the cloud that is built up by a large number of semi-transparent spheres. These spheres are created by a specific symbol in the L-system ("O"). The settings of the ray tracer will decide the texture and color scheme of the cloud. We found several techniques to create clouds.

1. Explosion of clouds

This technique was first called tree crown technique since the rewrite rules to generate this kind of cloud are almost identical to the ones used to create the tree seen in Figure 38. The difference is that spheres are created instead of branches thus creating a fluffy cumulus cloud.


Figure 40: Explosion cloud

2. Curl of clouds

One disadvantage of the previous technique is that the bottom surface becomes rather uneven. This is because the "branches" are heading straight up first and then branch out and down. The idea with the curl technique is that the branches go straight out (horizontally) in all directions and then curl up and in.



Figure 41: Curly cloud

3. Spiral

The bottom layer is created by creating a spiral that sends "branches" upwards creating the fluffy area of a cumulus cloud.


Figure 42: Spiral cloud

The techniques above are just brief guidelines and can of course be changed and combined in many different ways.