L-Systems
Simulation of
development and
growth
The algorithmic beauty of plants
L-Systems
The central concept of L-Systems is that of rewriting
A classical example of an object defined using
rewriting rules is the von Koch snowflake
Mandelbrot states it as a rewriting system
– One begins with two shapes, an initiator and a generator.
– The latter is an oriented broken line made up of N equal
sides of length r.
– Thus each stage of the construction begins with a broken
line and consists in replacing each straight interval with a
copy of the generator, reduced and displaced so as to have
the same end points as those of the interval being replaced.
B. B. Mandelbrot. The fractal geometry of nature. W. H. Freeman,
San Francisco, 1982.
Iterations of the von Koch snowflake
Other rewriting systems
Rewriting systems on graphs
Rewriting systems on rectangular arrays and
matrices ( Cellular automata)
Rewriting systems on character strings
History of string rewriting
Begin 19th century: Thue provided first formal definition of a
string rewriting system (srw)
Late 50ties: Chomsky investigated syntactical features of
natural languages using srw
1960: Backus and Naur used rewriting notation in the definition
of programming language ALGOL
1952: Equivalence between Backus Naur form and context free
class of Chomsky’s grammar (ccg) was realized
1968 the biologist A. Lindenmayer introduced L-Systems to
model multicellular plant growth
As opposed to ccg rewriting rules are applied to all letters in the
string simultaneously; there are languages that can be
expressed in L-Systems but not in ccg
S. Ginsburg and H. G. Rice. Two families of languages related to
ALGOL. J. ACM, 9(3):350–371, 1962.
Relation between Chomsky classes
and L-systems
Relations between Chomsky
classes of languages and
language classes generated
by L-systems.
The symbols OL and IL
denote language classes
generated by context-free
and context-sensitive L-
systems
DOL-systems
simplest class of L-systems, Letters are simultaneously
those which are deterministic replaced in an derivation step
and context-free, called DOL-
systems.
consider strings (words) built of
two letters ‘a’ and ‘b’, which first five
may occur many times in a derivations of the
string. described DOL-
Each letter is associated with a system with
rewriting rule.
axiom ‘b’
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.
Formal definition of a DOL-System
Let V denote an alphabet, V* A production (a, χ) ∈ P is
the set of all words over V, written as a → χ. The letter
and V+ the set of all a and the word χ are called
nonempty words over V. A the predecessor and the
string OL-system is an successor of this production,
ordered triplet G = (V,ω,P) resp.
where V is the alphabet of It is assumed that for any
the system, letter a ∈ V , there is
ω ∈ V+ is a nonempty word exactly one word* χ ∈ V*
called the axiom and P ⊂ V such that a → χ. (if not we
× V∗ is a finite set of assume a → a)
productions.
*if we say ’at least one word’ it is a OL system, but not a deterministic one DOL.
Derivation
Let µ = a1 . . . am be an
arbitrary word over V axiom ω
The word ν =χ1 . . . χm ∈ V∗
is directly derived from (or derivation from a
generated by) µ, noted µ ⇒
ν, if and only if ai → χi for all
i = 1, . . . , m.
Developmental
A word ν is generated by G
in a derivation of length n if sequence
there exists a developmental
sequence of words µ0, µ1, . .
. , µn such that µ0 = ω, µn = ν
and µ0 ⇒ µ1 ⇒ . . . ⇒ µn
Example: Development of a filament of
the bacteria Anabaena catenula
The symbols a and b
represent cytological states
of the cells
The subscripts l and r
indicate cell polarity, ar
specifying the positions in
which daughter cells of type al br
a and b will be produced.
L-system describes
blarar
development alalbralbr
– ω : ar
– p1 : ar → albr blarblararblarar
– p2 : al → blar
– p3 : br → ar
···
– p4 : bl → al
Model validation
Under a microscope, the filaments
appear as a sequence of cylinders
of various lengths, with a-type cells
longer than b-type cells.
Letters of the L-system alphabet
are represented graphically as
shorter or longer rectangles with
rounded corners
generated structures are one-
dimensional chains of rectangles
Schematic image of filament
development resembles observed
multi-cellular patterns that can be
compared to observed patterns
Intermediate continuous cell growth
is not modeled.
More sophisticated graphical
representations
For modelling phenomena Work on relating L-systems
such as branching in plants to fractals, space filling
of higher order we need curves, and indian art kolam
more sophisticated graphical patterns and music
representions. followed*
The first results in this Prusinkiewicz focused on an
direction were published in interpretation based on a
1974 by Frijters and LOGO-style turtle
Lindenmayer, and Hogeweg
and Hesper.
D. Frijters and A. Lindenmayer. A model for the growth and flowering of Aster novae-angliae on the basis of table
(1,0) L-systems. In G. Rozenberg and A. Salomaa, editors, L Systems, LNCS 15, 24–52. Springer-Verlag, Berlin,
1974.
P. Hogeweg and B. Hesper. Pattern Recognition, 6:165–179, 1974.
P. Prusinkiewicz (1987). Applications of L-systems to computer imagery. In H. Ehrig, M. Nagl, A. Rosenfeld, and
G. Rozenberg, editors, Graph grammars and their application to computer science; LNCS 291
The basic idea of turtle interpretation
A state of the turtle is defined F Move forward a step of length
as a triplet (x, y, α) d. The state of the turtle
the Cartesian coordinates (x, y) changes to (x, y, α), where x =
represent the turtle’s position, x + d cos α and y = y + d sin α.
and the angle α, called the A line segment between points
heading, is interpreted as the (x, y) and (x, y) is drawn.
direction in which the turtle is f Move forward a step of length d
facing. without drawing a line.
Given the step size d and the + Turn left by angle δ. The next
angle increment δ, the turtle state of the turtle is (x, y, α+δ).
can respond commands The positive orientation of
represented by the following angles is counterclockwise.
symbols − Turn right by angle δ. The next
state of the turtle is (x, y, α − δ).
Example for turtle graphics
interpretation
L-systems as codings of geometrical
constructions
This method can be applied to
interpret strings which are
generated by L-systems.
Approximations of the quadratic
Koch island taken from
Mandelbrot’s book [95, page
51].
The initiator corresponds to the
axiom and the generator
corresponds to the production
successor.
L-systems specified in this way
can be perceived as codings for
Koch constructions.
ω:F−F−F−F
p : F → F − F + F + FF − F − F + F
δ= 90º, d is decreased 4 times per derivation, n = number of derivations
More L-systems coding fractals with
initiator and generator
Combinations of islands and lakes
A complication occurs
when the curve is not
connected
A second production
rule with predecessor is
then required
More L-systems coding fractals (1)
The ease of modifying L-
systems makes them
suitable for developing new
von Koch curves.
Try to gradually develop by
inserting, deleting, replacing
symbols!
A sequence of Koch curves
obtained by successive
modification of the
production successor
Similar L-systems can give
rise to very dissimilar
graphical representations
L-system synthesis
we often wish to construct an L-system which
captures a given structure or sequence of structures
representing a developmental process
This is called the inference problem in the theory of
L-systems.
Although some algorithms for solving it were
reported in the literature*, they are still too limited to
be of practical value in the modeling of higher plants
Edge rewriting and node rewriting are more intuitive
approaches to this problem
*H. Jürgensen and A. Lindenmayer. Modelling development by OL-systems: Inference algorithms for developmental systems with cell
lineages. Bulletin of Mathematical Biology, 49(1):93-123, 1987
*A. Lindenmayer. Models for multicellular development: Characterization,inference and complexity of L-systems. In A. Kelmenov
´a and J. Kelmen, editors, Trends, techniques and problems in theoretical computer science, Lecture Notes in Computer Science 281,
pages 138–168. Springer-Verlag, Berlin, 1987.
.
Edge rewriting and node rewriting
Terminology is borrowed from graph theory
In the case of edge rewriting, productions substitute
figures for polygon edges
in node rewriting, productions operate on polygon
vertices ( in L-systems symbols are needed for
them)
Both techniques capture the recursive structure of
the figures
the concepts are illustrated using abstract curves,
they apply to branching structures found in plants as
well.
Fl Fl+Fr+ Fl+Fr+-Fl-Fr
Edge rewriting
Edge rewriting can be viewed as an
extension of Koch constructions.
The figure shows the dragon curve
and the L-system that generated it.
Both the Fl and Fr symbols
represent edges created by the
turtle executing the “move forward”
command.
The productions substitute Fl or Fr
edges by pairs of lines forming left
or right turns.
Many interesting curves can be
obtained assuming two types of
edges, “left” and “right.”
Dragoncurve can be also obtained
by paper-folding and looks similar
to Julia set
Example
Synthesis of an
Sierpinski gasket using
left turn right turn
system
Edge rewriting makes
synthesis more intuitive
F: space filling
A: self-avoiding
S: simple
S: self-similar
FASS curve construction
Hexagonal Gosper-curve Quadratic Gosper or E-curve
FASS curves
can be thought of as finite, self-avoiding
approximations of curves that pass through all points
of a square (space-filling curves).
McKenna presented an algorithm for constructing
FASS curves using edge rewriting.
It exploits the relationship between such a curve and
a recursive subdivision of a square into tiles.
Later we will see an node-replacement algorithm for
FASS curves.
Why is the E-Curve space filling?
The polygon replacing an edge Fl (a) approximately fills the square on the left
side of Fl (b).
Similarly, the polygon replacing an edge Fr (c) approximately fills the square on
the right side of that edge (d).
In the next derivation step, each of the 25 tiles associated with the curves (b) or
(d) will be covered by their reduced copies.
A recursive application of this argument indicates that the whole curve is
approximately space-filling.
(a) (b) (c) (d)
Left and right
edges are distinguished
by the direction of ticks.
Why is the E-curve self-avoiding
the generating polygon is self-avoiding, and
no matter what the relative orientation of the polygons lying on
two adjacent tiles, their union is a self-avoiding curve.
The first property is obvious, while the second can be verified
by considering all possible relative positions of a pair of
adjacent tiles:
Optimality of the E-curve
The simplicity of a generating polygon can be
measured by the number of edges in the production
Using a computer program to search the space of
generating polygons, McKenna found that the E-
curve is the simplest FASS curve obtained by edge
replacement in a square grid
The relationship between edge rewriting and tiling of
the plane extends to branching structures, providing
a method for constructing and analyzing L-systems
which operate according to the edge-rewriting
paradigm
Node rewriting
The idea of node rewriting is to substitute new polygons for nodes of
the Subfigures predecessor curve.
Turtle interpretation is extended by symbols which represent arbitrary
subfigures.
Each subfigure A from a set of subfigures A is represented by:
• two contact points, called entry point PA and exit point QA, and
• two direction vectors, called entry vector pA and exit vector qA.
During turtle interpretation of a string ν, a symbol A ∈ A incorporates
the corresponding subfigure into a picture.
To this end A is translated and rotated in order to align its entry point
PA and direction pA with the current position and orientation of the
turtle
Having placed A, the turtle is assigned the resulting exit position QA
and direction qA.
Node rewriting - example
For example, assuming that
the contact points and
directions of Recursive
subfigures Ln and Rn are as
in the figure and figures Ln+1
and Rn+1 formulas are
captured by the following
formulas:
Ln+1 = +RnF − LnFLn − FRn+
Rn+1 = −LnF + RnFRn + FLn−
Suppose that curves L0 and
R0 are given.
Ln+1 = +RnF − LnFLn − FRn+
Rn+1 = −LnF + RnFRn + FLn−
Node rewriting and recursion
One way of evaluating the The substitution proceeds in
string Ln (or Rn) for n > 0 is a parallel way with F,+ and −
to generate successive replacing themselves.
strings recursively, in the Since all indices in any
order of decreasing value of given string have the same
index n. (see formula below) value, they can be dropped,
the generation of string Ln provided that a global count
can be considered as a of derivation steps is kept.
string-rewriting mechanism, Consequently,string Ln can
where the symbols on the be obtained in a derivation
left side of the recursive of length n using the
formulas are substituted by following L-system:
corresponding strings on the
right side.
Pure curves and subfigures
In order to further reduce the node rewriting system to an L
system we have to replace L and R by subfigures
In the ideal case the subfigures reduce to single points (pure
curves), and are replaced by empty string
Alternatively, they can be left in the string and ignored by the
turtle during string interpretation.
As in the case of edge rewriting, the relationship between node
rewriting and tilings of the plane extends to branching
structures (see next part).
It offers a method for synthesizing L-systems that generate
objects with a given recursive structure, and links methods for
plant generation based on L-systems with those using iterated
function systems
FASS curve construction technique
Consider an array of m×m square To this end, the array of m × m
tiles, each including a smaller connected tiles is considered a
square, called a frame. macrotile which contains an open
Each frame bounds an open self- polygon inscribed into a
avoiding polygon. macroframe
The endpoints of this polygon An array of m × m macrotiles is
coincide with the two contact formed, and the polygons inscribed
vertices of the frame. into the macroframes are
Suppose that a single-stroke line connected together.
running through all tiles can be This construction is carried out
constructed by connecting the recursively, with m × m macrotiles
contact vertices of neighboring at level n yielding one macrotile at
frames using short horizontal or level n + 1.
vertical line segments
A FASS curve can be constructed
by the recursive repetition of this
connecting pattern.
Construction of FASS curves
Sample FASS curve
constructed using tiles
with contact points
positioned along a tile
edge using a 3x3
macrotile
Relationship between edge and
node rewriting
The classes of curves that can Consider a production can have
be generated using the edge- a string consisting of more than
rewriting a node-rewriting one predecessor
techniques are not disjoint. (such systems are called
We illustrate this by means of pseudo L-systems)
an example the symbols l and r are not
Reconsider the L-system that interpreted by the turtle.
generates the dragon curve
using edge replacement:
Production p1 replaces the
letter l by the string l +rF− while
the leading letter F is left intact
Edge rewriting and node rewriting
In practice, the choice between edge rewriting and node
rewriting is often a matter of convenience.
Neither approach offers an automatic, general method for
constructing L-systems that capture given structures.
the distinction between edge and node rewriting makes it easier
to understand the intricacies of L-system operation
Specifically, the problem of filling a region by a self-avoiding
curve is biologically relevant, since some plant structures, such
as leaves, may tend to fill a plane without overlapping
3-D L-Systems
3-D L-systems
Turtle interpretation of L- Rotations of the turtle are then
systems can be extended to expressed by the equation
three dimensions following the
ideas of Abelson and diSessa. [H’ L’ U’] [H L U] R
The key concept is to represent
the current orientation of the
turtle in space by three vectors with rotation matrix R
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 and
satisfy the equation H×L = U.
H. Abelson and A. A. diSessa. Turtle geometry. M.I.T. Press,Cambridge,
1982.
Rotation matrix R
3-D L-system
+ turn left by angle δ, using rotation
matrix RU(δ)
- turn right by angle δ, using
rotation matrix RU(−δ).
& Pitch down by angle δ, using
rotation matrix RL(δ).
^ Pitch up by angle δ, using
rotation matrix RL(−δ).
\ Roll left by angle δ, using
rotation matrix RH(δ).
/ Roll right by angle δ, using
rotation matrix RH(−δ).
| Turn around, using rotation
matrix RU(180º).
three-dimensional extension of the Hilbert curve. Colors
represent three-dimensional “frames” associated with symbols A (red), B
(blue), C (green) and D (yellow).
Branching systems
According to the rules presented so far, the turtle interprets a
character string as a sequence of line segments.
The edge sequences form paths from a distinguished node,
called the root or base, to the terminal nodes.
In the biological context, these edges are referred to as branch
segments
A segment followed by at least one more segment in some path
is called an internode.
A terminal segment (with no succeeding edges) is called an
apex.
Axial trees
An axial tree is a special type of
rooted tree
At each of its nodes, it has most
one outgoing straight segment.
All remaining edges are called
lateral or side segments.
A sequence of segments is
called an axis, if:
– the first segment in the
sequence originates at the root
of the tree or as a lateral
segment at some node.
– each subsequent segment is a
straight segment
– the last segment is not followed
by any straight segment in the
tree.
Branches of axial trees
Together with all its
descendants, an axis
constitutes a branch.
A branch itself is an axial tree
Axes and branches are
ordered.
– The axis originating at the root
of the entire plant has order
zero.
– An axis originating as a lateral
segment of an n-order parent
axis has order n+1.
– The order of a branch is equal
to the order of its lowest-order
or main axis.
Axial trees as topological objects
Axial trees are purely topological objects.
The geometric connotation of such terms as straight segment,
lateral segment and axis should be viewed at this point as an
intuitive link between the graph-theoretic formalism and real
plant structures.
The proposed scheme for ordering branches in axial trees was
introduced originally by Gravelius.
MacDonald [94, pages 110–121] surveys this and other
methods applicable to biological and geographical data such as
stream networks.
N. Macdonald. Trees and networks in biological models. J. Wiley &
Sons, New York, 1983.
Horton and Strahler analysis
Of special interest are
methods proposed by
Horton and Strahler, which
served as a basis for
synthesizing botanical trees
The left figure displays a
tree obtained using Horton
and Strahler analysis of
branching patterns
R. E. Horton. Hypsometric (area-altitude) analysis of
Erosional topology. Bull. Geol. Soc. America, 63:1117–1142, 1952.
G. Eyrolles. Synthese d’images figuratives d’arbres par des methodes combinatoires. PhD thesis,
Universite de Bordeaux I, 1986.
Tree OL-systems
In order to model development of branching structures, a rewriting
mechanism can be used that operates directly on axial trees.
A rewriting rule, or tree production, replaces a predecessor edge by a
successor axial tree in such a way that the starting node of the
predecessor is identified with the successor’s base and the ending
node is identified with the successor’s top
A tree OL-system G is specified by three components:
– a set of edge labels V
– an initial tree ω with labels from V
– a set of tree productions P
Given the L-system G, an axial tree T2 is directly derived from a tree
T1, noted T1 ⇒ T2, if T2 is obtained from T1 by simultaneous
replacing each edge in T1 by its successor according to the production
set P.
A tree T is generated by G in a derivation of length n if there exists a
sequence of trees T0, T1, . . . , Tn such that T0 = ω, Tn = T and T0 ⇒
T1 ⇒ . . . ⇒ Tn.
Axial tree production systems
is transformed
to
production rule
production rule
applied
Bracketed 0L Systems
The definition of tree L-systems They are interpreted by the
does not specify the data turtle as follows
structure for representing axial [ Push the current state of the
trees. turtle onto a pushdown
One possibility is to use a list operations stack.
representation with a tree The information saved on the
topology (initiator, generator) stack contains the turtle’s
position and orientation. and
Alternatively, axial trees can be
possibly other attributes.
represented using strings with
brackets (e.g. in bracketed OL- ] Pop a state from the stack and
systems) make it the current state of the
turtle. No line is drawn,although
New symbols ‘[‘ and ‘]’ are
in general the position of the
introduced to delimit a branch.
turtle changes.
Example
Bracketed OL-systems
Derivations in bracketed OL-systems
proceed as in OL-systems without brackets.
The brackets replace themselves.
Examples of two-dimensional branching
structures generated by bracketed OL-
systems are shown in the figure
Edge rewriting bracketed L systems
Node rewriting bracketed L-systems
3-D Bush-like structure
p1 creates three new branches
from an apex of the old branch.
A branch consists of an edge F
forming the initial internode, a leaf L
and an apex A (which will
subsequently create three new
branches).
p2 and p3 specify internode growth
In subsequent derivation internode
steps get longer and acquire new
leaves
Production p4 specifies the leaf as
a filled polygon with six edges. Its
boundary is formed from the edges
f enclosed between the braces {
and }
The symbols ! and are used to
decrement the diameter of
segments and increment the
current index to the color table,
respectively.
A flowering plant generated by an L-
system
Note that the plant was generated in
5 iterations.
Consider, the amount of information
needed for directly describing the
plant
Summary L-Systems
L-Systems are based on string rewriting using production rules
( graph grammars)
Turtle graphics give them a graphical interpretation
L-Systems serve as models of development in biology, but also
in other areas.
Small changes of rules have often surprisingly large impact.
Branching structures can be implemented using stacks
Axial trees are important branching structures in nature (rivers,
botanical trees, …)
Edge and node rewriting in 3-D bracketed L-Systems can
model complex self-similar objects such as flowering plants and
bushes in a extremely compact way.
Outlook
Realistic simulation systems of growing systems can
consider production rules as used in L-Systems
L-Systems show the deep connection between
language, dynamical systems, and graphical/real-
world objects
L-Systems are still a relatively young research
discipline, and for the future many applications of it
are expected, not at least in systems simulation.
