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
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)  are the simplest of them. They are defined as triplets.
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.
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 , 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
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.
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 . 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
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  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.
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 ).
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.
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.
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.
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.
The bottom layer is created by creating a spiral that sends "branches" upwards creating the fluffy area of a cumulus cloud.
The techniques above are just brief guidelines and can of course be changed and combined in many different ways.