L-Systems

L-systems were introduced in 1968 by Aristid Lindenmayer. Originally designed for the modelling of plant topology, their capabilities have been extended enormously over the years to transform them into a widely used modelling tool for plant geometry capable of producing botanically realistic results.

L-systems are a special kind of string rewriting grammars. They rewrite a given string (a sequence of symbols) according to a grammar, i.e. a set of rules. To give an example, the single rule a → b a b transforms the string "a b a c" into "b a b b b a b c".

Such an example may seem academic, but when a meaning is given to the symbols, such grammars turn into a powerful and intuitive tool for the description of models of botany and other disciplines. Usually, a geometric meaning is given to the symbols, the so-called turtle interpretation. For example, the symbol F commands a virtual turtle to move forward and draw a line, the symbols +/- lead to a left/right turn by a given angle. The snowflake (Koch-) curve can be generated using only these three symbols and an angle of 60°: An initial triangle is represented as the string "F + + F + + F", Koch's replacement step is coded by the single rule F → F - F + + F - F. The first two derivation steps of this simple L-system are shown in the following figure.

Most plants (if not all) exhibit branching structures. In order to represent branches within the concept of string-based L-systems, Przemyslaw Prusinkiewicz introduced bracketed L-systems which use the brackets [ and ] as delimiting symbols for branches. A simple binary tree is produced out of the initial string X by the rule X → F[+X][-X], a two-dimensional plant-like structure by the two rules X → F[+X]F[-X]+X and F → FF, see the following picture. X is a symbol without a geometric meaning.

Over the years, the set of turtle commands has been considerably enlarged with sophisticated computer graphical elements: Prusinkiewicz and others have defined commands for polygons, extrusion surfaces, textures etc. Here are some L-system-generated images. For more "pretty pictures", have a look at the gallery.

There are constraints inherent in the formalism of pure L-systems which limit their field of application. Especially the modelling of global interactions like shadowing or environmental influences is difficult within the scope of pure L-systems. To overcome these problems, extensions have been made:

• Open L-systems allow the coupling with external programmes by special communication symbols. They were introduced by Prusinkiewicz and coworkers and implemented in their software cpfg.
• Sensitive growth grammars provide globally-sensitive functions within the formalism itself. They were introduced by Winfried Kurth and implemented in the software GROGRA.
• Relational growth grammars leave the restrictions of string grammars behind by taking the step to graphs and graph rewriting rules. The programming language XL is our implementation of relational growth grammars, this language is used as modelling language within the software GroIMP.
• L+C integrates L-systems into the programming language C++. It was designed by Prusinkiewicz, Sievänen and coworkers and implemented in the software lpfg.