View source

__FORCETOC__
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 <em>Aristid Lindenmayer.</em>  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").

== Rendering L-system Command Expressions ==
<SPAN STYLE="font-size: larger;">Introductory example </SPAN>
<br><br>

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.
<br><br>

<SPAN STYLE="font-size: larger;"><u>System Constants</u></SPAN>

* &#948; = angle increment
* d = step size (length increment)


<SPAN STYLE="font-size: larger;"><u>Basic Commands</u></SPAN>

* 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 &#948;
* - is turn right by angle &#948;
* [ 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)


<SPAN STYLE="font-size: larger;"><u>Example - How to Interpret a String</u></SPAN>

 &#948; = 45°
 d = 2
 F[+F]F[-F]F

{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/01.png|caption=Example showing string interpretation}}


== How L-systems Grow ==
<SPAN STYLE="font-size: larger;">String rewriting/substitution </SPAN>
<br><br>

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


<SPAN STYLE="font-size: larger;"><u>System Constants</u></SPAN>

* n = number of times to apply production rules
* &#948; = angle increment
* d = step size (length increment)


<SPAN STYLE="font-size: larger;"><u>Axiom</u></SPAN>

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


<SPAN STYLE="font-size: larger;"><u> Production Rules</u></SPAN>

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



<SPAN STYLE="font-size: larger;"><u>Example</u></SPAN>

 n = 3
 &#948; = 25.7°
 d = 1
 
 w: F (Axiom)
 
 p: F &rarr; 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

{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/02.png|caption=Example showing string substitution}}


== Null Symbols ==
<SPAN STYLE="font-size: larger;">Adding complexity to production rules</SPAN>
<br><br>

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


<SPAN STYLE="font-size: larger;"><u>Example</u></SPAN>

  w: X
 p1: X &rarr; F[+X]F[-X]+X
 p2: F &rarr; 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

{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/03.png|caption=Example showing string substitution with symbols}}


== Examples of Branching Structures ==
<SPAN STYLE="font-size: larger;">How production rules create form </SPAN>
<br><br>


{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/book1.jpg|caption=Branching Structures}}


== Stochastic L-systems ==
<SPAN STYLE="font-size: larger;">L-systems combined with chance operations </SPAN>
<br><br>

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.



<SPAN STYLE="font-size: larger;"><u>Syntax Added to the Production Rules</u></SPAN>

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




<SPAN STYLE="font-size: larger;"><u>Example</u></SPAN>

 w: F
 p1: F (0.33)&rarr; F[+F]F[-F]F
 p2: F (0.33)&rarr; F[+F]F
 p3: F (0.33)&rarr; F[-F]F

{{SingleImage|imageWidthPlusTen=600|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/04.png|caption=Stochastic L-system}}



<SPAN STYLE="font-size: larger;"><u>Example</u></SPAN>

{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/book2.jpg|caption=Stochastic L-system}}


== Context Sensitive L-systems ==
<SPAN STYLE="font-size: larger;">Simulating hormones and chemical triggers </SPAN>
<br><br>

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.


<SPAN STYLE="font-size: larger;"><u>Syntax Added to the Production Rules</u></SPAN>

"*" = matches any symbol

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



{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/book3.jpg|caption=Context Sensitive L-systems}}



{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/book4.jpg|caption=Context Sensitive L-systems}}


== Genetic L-systems ==
<SPAN STYLE="font-size: larger;">Systems that allow the evolution of form</SPAN>
<br><br>

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 ==
<SPAN STYLE="font-size: larger;">Selected Links</SPAN>
<br><br>

:The Algorithmic Beauty of Plants - the L-systems classic by Prusinkiewicz and Lindenmeyer now free! - [http://algorithmicbotany.org/papers/#abop click here]
:Algorithmic Botany at the University of Calgary - Professor Prusinkiewicz's research group - [http://algorithmicbotany.org/papers/ click here] 

[[Category:Complex systems]]
[[Category:Systems]]
[[Category:Systems used in Computer animation and effects]]
[[Category:Systems used in Computer graphics]]
[[Category:Systems used in Design]]