body {margin-left: 15pt; margin-right: 15pt}
An Introduction to Lindenmayer Systems
Original URL: http://www.cogs.susx.ac.uk/users/gabro/lsys/lsys.html
An Introduction to Lindenmayer Systems
by Gabriela Ochoa
School of Cognitive and Computing Sciences
The University of Sussex
Contents
Overview
D0L-Systems
Fractals and Graphic Interpretation of strings
Bracketed L-systems and models of plants architecture
L-systems and Genetic Algorithms
Other Resources
Useful References
People
Software
On-line Resources
Overview
L-systems are a mathematical formalism proposed by the biologist Aristid
Lindenmayer in 1968 as a foundation for an axiomatic theory of biological
development. More recently, L-systems have found several applications in
computer graphics (Smith 1984; Prusinkiewicz and Hanan 1989; Prusinkiewicz
and Lindenmayer 1991) . Two principal areas include generation of fractals
and realistic modelling of plants.
Central to L-systems, is the notion of rewriting, where the basic idea
is to define complex objects by successively replacing parts of a simple
object using a set of rewriting rules or productions. The rewriting can
be carried out recursively.
The most extensively studied and the best understood rewriting systems
operate on character strings. Chomsky's work on formal grammars (1957)
spawned a wide interest in rewriting systems. Subsequently, a period of
fascination with syntax, grammars and their application in computer science
began, giving birth to the field of formal languages.
Aristid Lindenmayer's work introduced a new type of string rewriting
mechanism, subsequently termed L-systems. The essential difference between
Chomsky grammars and L-systems lies in the method of applying productions.
In Chomsky grammars productions are applied sequentially, whereas in L-systems
they are applied in parallel, replacing simultaneously all letters in a
given word. This difference reflects the biological motivation of L-systems.
Productions are intended to capture cell divisions in multicellular organisms,
where many division may occur at the same time.
D0L-system
The simplest class of L-systems are termed D0L-systems (D0L stands for
deterministic and 0-context or context-free). To provide an intuitive understanding
of the main idea behind D0L-systems , let us consider this example given
by Prusinkiewicz and Lindenmayer (1991) (see figure below).
Lets us consider strings built of two letters a and
b (they may occur many times in a string). For each letter we specify
a rewriting rule. The rule a -> ab means that the letter a
is to be replaced by the string ab, and the rule b -> a means
that the letter b is to be replaced by a. The rewriting process
starts from a distinguished string called the axiom. Let us assume that
it consist of a single letter b. In the first derivation step (the
first step of rewriting) the axiom b is replaced by a using
production b -> a. In the second step a is replaced by ab
using the production a -> ab. The word ab consist of two
letters, both of which are simultaneously replaced in the next derivation
step. Thus, ais replaced by ab , b is replaced by
a, and the string aba results. In a similar way (by the simultaneous
replacement of all letters), the string aba yields abaab
which in turn yields abaababa, then abaababaabaab, and so
on.
b
|
a
_|_
a b
_| \
a b a
_| | |_
a b a a b
_/ | |_ |_ \
a b a a b a b a
Formal definitions of D0L-systems and their operation can be found in (Prusinkiewicz
and Hanan 1989; Prusinkiewicz and Lindenmayer 1991)
Fractals and graphic interpretation of strings
Lindenmayer systems were conceived as a mathematical theory of development.
Thus, geometric aspects were beyond the scope of the theory. Subsequently,
several geometric interpretation of L-systems were proposed in order to
turn them into a versatile tool for fractal and plant modelling.
Many fractals (or at least their finite approximations) can be thought
of as sequences of primitive elements -line segments. To produce fractals,
strings generated by L-systems must contain the necessary information about
figure geometry. A graphic interpretation of strings, based on turtle geometry,
is described by Prusinkiewicz et al. (1989), (1990). This interpretation
may be used to produce fractal images.
A state of the turtle is defined as a triplet (x, y, a), where
the Cartesian coordinates (x, y) represent the turtle's position,
and the angle a, called the heading, is interpreted as the direction
in which the turtle is facing. Given the step size d and the angle
increment b, the turtle can respond to the commands represented
by the following symbols:
F Move forward a step of length d. The state
of the turtle changes to (x',y',a), where
x'= x + d cos(a) and y'= y + d sin(a). A li-
ne segment between points (x,y) and (x',y')
is drawn.
f Move forward a step of length d without
drawing a line. The state of the turtle
changes as above.
+ Turn left by angle b. The next state of
the turtle is (x,y,a+b).
- Turn left by angle b. The next state of
the turtle is (x, y,a-b).
All other symbols are ignored by the turtle (the turtle preserves its current
state).
Given a string v, the initial state of the turtle (x0,y0,a0),
and fixed parameters d and b, the turtle interpretation of
v is the figure (set of lines) drawn by the turtle in response to
the string v.
The above description gives us a rigorous method for mapping strings
to pictures, which may be applied to interpret strings generated by L-systems.
Next figure shows four approximations of the curve known as ``quadratic
Koch island''. These figures were obtained by interpreting strings generated
by the following L-system:
w: F+F+F+F
p: F -> F+F-F-FF+F+F-F
   
The images correspond to the strings obtained by derivations of length
n = 0, 1, 2 and 3 respectively. The angle increment b is equal to
90 degrees.
Bracketed L-systems and models of plants architecture
Following the previous section description, the turtle interprets a character
string as a sequence of line segments, connected ``head to tail'' to each
other. Depending on the segment lengths and angles between them, the resulting
figure would be more or less convoluted, but always remains just a single
line.
In his work, Lindenmayer, introduced a notation for representing graph-theoretic
trees using strings with brackets. The idea was to formally describe branching
structures found in many plants, from algae to trees, using the framework
of L-systems. Again, posterior geometric interpretations of strings with
brackets were proposed for realistic modelling of plants. Thus, to represent
branching structures, L-systems alphabet is extended with two new symbols,
`[' and `]', to delimit a branch. They are interpreted by the turtle as
follows:
[ Pop a state from the stack and make it
the current state of the turtle.
] Push the current state of the turtle
onto a pushdown stack.
An example of a bracketed string and its turtle interpretation, obtained
in derivations of length n = 1 - 5, are shown in the next figure . These
figures were obtained by interpreting strings generated by the L-system:
w: F
p: F -> F[-F]F[+F][F]
    
L-systems and Genetic Algorithms
The following pictures were created by the author, using a Genetic Algorithm
with genotypes inspired by L-systems. The fitness function employed was
based on current evolutionary hypotheses concerning the factors that have
had the greatest effect on plant evolution.
    
Visually appealing figures not resembling plants, were also obtained
using a Genetic Algorithm with a fitness function favouring bilateral symmetric
structures.
    
Other Resources
Useful References
Lindenmayer A (1968). Mathematical models for cellular interaction in development
I. Filaments with one-sided inputs. Journal of Theoretical Biology
18:280-289
Prusinkiewicz P, Hanan J (1989). Lindenmayer systems, fractals, and
plants. Lecture Notes in Biomathematics Springer-Verlag:Berlin
Prusinkiewicz P, Lindenmayer A (1990). The Algorithmic Beauty of Plants.
Springer-Verlag:New York
Smith AR (1984) Plants, fractals and formal languages. Computer Graphics
18:July 1-10
Prusinkiewicz, P. and Hammel, M. (1995) Visual
Models of Morphogenesis: A Guided Tour, Department of Computer Science,
University of Calgary.
Some downloadable L-systems
related publications
People
Przemyslaw
Prusinkiewicz is one of the most important researchers pursing the
application of L-systems for producing biologically realistic images.
Christian Jacob is interested in combining L-systems and Evolutionary Computation
Software
L-systems
Software: A comprehensive list of software for performing L-systems
simulations. Software is available for several platforms (Unix, Mac. and
PC).
LParser: A very good
program that includes 3D L-systems.
Fractint Homepage:
Fractint is a versatile and extensive fractal freeware program, available
for PC. Fractint allows for fractal and L-systems generation.
A L-systems implamentation
for Macintosh. The page also includes several figures, and links to
other L-systems resources.
On-Line Resources
An online
book by P. Prusinkiewicz with a lot of L-system information,images
and animations.
You can see the plants grow at: (1)
Virtual Plants description & animations, Centre for Tropical Pest
Management, Brisbane, Australia. (2)
L-system Plant Animations, U. Calgary, Canada.
L-system
Plant Geometry Generator: Is a complete and well described project
with a lot of figures included.
A L-systems
page, which is part of a course in computational morphogenesis at the
University of Aizu (Japan).
Gabriela Ochoa, gabro@cogs.susx.ac.uk
(12/02/98)
|
|
