L-Systems
Lindenmayer Systems, or just L-System, were discovered by botanist Aristid Lindenmayer and introduced to the world in 1968. He was interested in describing mathematically the evolution of plants. Firstly, he was interested in the topological description, but shortly after the introduction of this new technique, several geometric interpretations were proposed.
Description
L-Systems is a rewriting technique where the central concept is to define “complex objects by successively replacing parts of a simple initial object using a set of rewriting rules or productions” (ref). The most studied of these rewriting systems operate on character strings, and within these systems, the one that received a great amount of attention and interest were Chomzky’s Formal Grammars. In 1968, Lindenmayer propposed this rewriting system, later named L-Systems, based on Chomzky’s work but with a key difference: Chomzky’s grammars productions are applied sequentially, whereas L-Systems, to better reflect the biological evolution of plants, are applied in parallel and simultaneously, replacing all symbols in a given word at once.
There are many types of L-System: Stochastic, Context Sensitive, Parametric, among others. The simplest of them is the so called D0L-System, or Deterministic Context-free, and can be described as a Triplet G = {V, w, P}, where V is an Alphabet of Symbols, w is a start string (also called Axiom), and P is a Set of Rules describing how to replace symbols on the current string for others present in the alphabet. It is deterministic when there is one rule to apply for replacing each symbol, and context-free when there’s no need to know the symbols on the string close to the one being replaced.
As an example, consider this L-System:
V = {A, B}
w = A
P = {A -> AB}, {B -> A}
The rules mean: replace every A for AB and B for an A. If we run a simulation of this L-System, after some iterations we obtain:
- n = 0 : A
- n = 1 : AB
- n = 2 : ABA
- n = 3 : ABAAB
- n = 4 : ABAABABA
- n = 5 : ABAABABAABAAB
- n = 6 : ABAABABAABAABABAABABA
- n = 7 : ABAABABAABAABABAABABAABAABABAABAAB
Geometric Interpretation
The way it was proposed, L-System is restricted only to the topological description of plants, without applications in other areas. Many researches found that a geometric, or graphical, description can be used to visualize the evolution of a L-System. The most used are those based on a Turtle Graphics. In this interpretation, each symbol of the alphabet is associated with a movement of a Turtle (the idea for using a turtle to represent programming instructions were introduced by Seymour Papert, when he published The Logo Programming Language to help children learn programming). At each frame, the state of the Turtle is defined as a tripled (x, y, a), where (x, y) are the Cartesian Coordinates representing the turtle position (3D representation is also possible but needs more than just adding a third coordinate; precise rotation matrices are needed) and a is an angle representing the direction of the turtle. If you add to this description a step size d and an angle increment b, we can define a basic set of commands for the Turtle:
F Move the turtle 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 line segment between (x, y) is drawn.
f Move forward a step of length d without drawing a line.
+ Turn left by angle b. The next state of the turtle is (x, y, d + b). The positive orientation is counter-clockwise.
– Turn right by angle b. The next state of the turtle is (x, y, d – b).
For example, the image at the beginning of the post is an approximation to the Koch Island after 4 iterations. The axiom and the one rule is as follows:
w: F – F – F – F
P: F -> F – F + F + FF – F – F + F
The first iteration of the turtle draws a square. When each “F” is replaced by the sequence “F – F + F + FF – F – F + F” you get a figure that looks like the one on the top of the page. The exact figure can be obtained after 3 iterations.
The recursive aspect of L-System can be used as an approximation to a lot of Fractals. The fractals showed in the demo are taken from the best book about L-System, The Algorithmic Beauty of Plants, by Przemyslaw Prusinkiewicz and Aristid Lindenmyer (a free pdf version can be found here), and correspond to the D0L systems described in the book. The description of the remaining fractals are taken from Paul Bourk website.
To represent plants graphically (the original goal of Lindenmyer), one must recognizes the most of them have a “branching” structure. In order to model that, two more rules must be added to the turtle description:
] Push the current state of the turtle onto a pushdown stack. The information saved on the stack contains the turtle’s position and orientation, and possibly other at- tributes such as the color and width of lines being drawn.
[ Pop a state from the stack and make it the current state of the turtle. No line is drawn, although in general the position of the turtle changes.
A typical description of a plant (Three2 in the demo) is:
a: 20 degrees
w: F
P: F -> F[+F]F[-F][F]
As I said before, most part of the descriptions of the System, as well as all the theory on how to build a simple L-System modeller, can be found in the seminal book of Prof. Prusinkiewicz and Prof. Lindenmyer. I made the simulator (you can play with it here) using WebGL and ThreeJS. You need Chrome, FireFox or Safari to view the simulator. Internet Explorer doesn’t work very well with WebGL. I’ll be posting more experiments with ThreeJS/WebGL soon, so stay tuned if you like this one. Again, don’t forget to play around with the demo. The code for the demo can be found at my GitHub. Have fun.
End of Line