L-systems

From GenerativeArt

Jump to: navigation, search

L-systems are used to describe and generate branching structures or geometric objects that exhibit self-similarity. Such structures may be 2D, 3D, or potentially in higher dimensions. L-systems are frequently used to generate computer graphic renderings of trees, bushes, grasses, and other plant life. L-systems can also be used in the exploration of fractals.

The "L" in "L-system" refers to its inventor Aristid Lindenmayer. Such systems produce a string expression that can be rendered into graphics. The string is essentially a series of commands for moving a virtual pen. The commands are executed from left to right. (From a historical perspective this is similar to Logo's "turtle graphics").

Contents

Rendering L-system Command Expressions

Introductory example

To render an L-system expression both a set of system constants and a set of command symbols must first be defined. The following example demonstrates the rendering of a typical basic L-system result.

System Constants

  • δ = angle increment
  • d = step size (length increment)


Basic Commands

  • F is move forward with length d with pen down
  • f is move forward with length d with pen up
  • + is turn left by angle δ
  • - is turn right by angle δ
  • [ pushes current state down the stack (i.e. saves position and heading)
  • ] pops the current state off the stack (i.e. gets position and heading)


Example - How to Interpret a String

δ = 45°
d = 2
F[+F]F[-F]F
01.png
Example showing string interpretation


How L-systems Grow

String rewriting/substitution

L-systems "grow" via iterative string substitution. The system initially has three components.


System Constants

  • n = number of times to apply production rules
  • δ = angle increment
  • d = step size (length increment)


Axiom

  • an initial string expression typically labeled as "w:"


Production Rules

  • rules for applying string substitutions typically labeled as p#: and applied "n" times.
  • uses the syntax "Sym1 → Str1" meaning "When Symbol 1 is found substitute String 1."


Example

n = 3
δ = 25.7°
d = 1

w: F (Axiom)

p: F → F[+F]F[-F]F (Production Rule)

n = 0; F
n = 1; F[+F]F[-F]F
n = 2; F[+F]F[-F]F[+F[+F]F[-F]F]F[+F]F[-F]F[-F[+F]F[-F]F]F[+F]F[-F]F
02.png
Example showing string substitution


Null Symbols

Adding complexity to production rules

L Systems can also have symbols that have no drawing operations associated with them, but add complexity when applying production rules.


Example

 w: X
p1: X → F[+X]F[-X]+X
p2: F → FF

n = 0; X
n = 1; F[+X]F[-X]+X
n = 2; FF[+F[+X]F[-X]+X]FF[-F[+X]F[-X]+X]+F[+X]F[-X]+X
03.png
Example showing string substitution with symbols


Examples of Branching Structures

How production rules create form


book1.jpg
Branching Structures


Stochastic L-systems

L-systems combined with chance operations

Like typical L-systems, but with multiple production rules for a single expression, each with a probability. The sum of all the probabilities must total to 1.


Syntax Added to the Production Rules

"Sym1 (.#)→ Str1" = "When Symbol 1 is matched there is a .# probability that String 1 should be substituted"



Example

w: F
p1: F (0.33)→ F[+F]F[-F]F
p2: F (0.33)→ F[+F]F
p3: F (0.33)→ F[-F]F
04.png
Stochastic L-system


Example

book2.jpg
Stochastic L-system


Context Sensitive L-systems

Simulating hormones and chemical triggers

Context sensitive L-systems can create signals (sub-strings) that travel the length of the branching structure string as it grows. The signals can, in turn, determine the location of new branches, flowers, buds, etc.


Syntax Added to the Production Rules

"*" = matches any symbol

"Sym1 < Sym2 > Sym3 → Str1" = "When Symbol 2 has Symbol 1 to the left and Symbol 3 to the right, substitute String 1 for Symbol 2."


book3.jpg
Context Sensitive L-systems


book4.jpg
Context Sensitive L-systems


Genetic L-systems

Systems that allow the evolution of form

L-systems can be combined with genetic algorithms. It is typically very difficult to start with a given plant or intended form and invent a set of production rules that will produce it. By encapsulating the L-system within an evolutionary system one can "navigate" the design space and guide the system towards the intended result without having to understand or inspect the actual production rules.

For genetic L-systems:

  • Initial condition, axioms and production rules must be translated into gene representation
  • Genetic operations must be adapted for L System genes
    • Mutation: mutations can be applied to a string converted to a parsed tree representation a la Karl Sims. Care must be taken to not generate syntactically incorrect command strings.
    • Crossover: crossover is even more prone to creating syntax problems. Note again Karl Sims' work with mathematical image processing expressions. Alternately, crossover can be achieved by swapping individual production rules without altering individual production rules.


Organizations, Exhibits, Conferences, Publications

Selected Links

The Algorithmic Beauty of Plants - the L-systems classic by Prusinkiewicz and Lindenmeyer now free! - click here
Algorithmic Botany at the University of Calgary - Professor Prusinkiewicz's research group - click here
Personal tools