L-systems

From GenerativeArt

(Difference between revisions)
Jump to: navigation, search
m
Current revision (04:19, 21 November 2012) (view source)
(fix image urls)
 
-
== Rendering L-system command expressions ==
+
__FORCETOC__
-
<SPAN STYLE="font-size: larger;">Introductory example </SPAN>
+
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>
-
The "L" in "L-system" refers to its inventor <em>Aristid Lindenmayer.</em>
+
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>
-
An L-system is a grammar based system for describing and generating branching structures which (often) exhibit self-similarity. 
+
<SPAN STYLE="font-size: larger;"><u>System Constants</u></SPAN>
-
Such systems produce a string expression which 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.
+
* &#948; = angle increment
 +
* d = step size (length increment)
<SPAN STYLE="font-size: larger;"><u>Basic Commands</u></SPAN>
<SPAN STYLE="font-size: larger;"><u>Basic Commands</u></SPAN>
-
* n is number of iterations
 
-
* &#948; is angle increment
 
-
* d is step size (length increment)
 
* F is move forward with length d with pen down
* F is move forward with length d with pen down
* f is move forward with length d with pen up
* f is move forward with length d with pen up
  F[+F]F[-F]F
  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}}
+
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/01.png|caption=Example showing string interpretation}}
-
 
+
== How L-systems Grow ==
== How L-systems Grow ==
-
 
<SPAN STYLE="font-size: larger;">String rewriting/substitution </SPAN>
<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:"
-
L Systems can grow via iterative string substitution.  The system initially has three components and
 
-
Initial condition - n d and &#948;
+
<SPAN STYLE="font-size: larger;"><u> Production Rules</u></SPAN>
-
Axiom: a starting string
+
* 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."
-
Production Rules: specifies string substitution
 
  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
  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}}
+
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/02.png|caption=Example showing string substitution}}
 +
 
== Null Symbols ==
== Null Symbols ==
 +
<SPAN STYLE="font-size: larger;">Adding complexity to production rules</SPAN>
 +
<br><br>
-
<SPAN STYLE="font-size: larger;">adding complexity </SPAN>
+
L Systems can also have symbols that have no drawing operations associated with them, but add complexity when applying production rules.
-
 
+
-
 
+
-
L Systems can also have symbols which have no drawing operations associated with them, but which add to complexity in production
+
  n = 2; FF[+F[+X]F[-X]+X]FF[-F[+X]F[-X]+X]+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}}
+
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/03.png|caption=Example showing string substitution with symbols}}
-
== Branching Structures ==
 
-
<SPAN STYLE="font-size: larger;">by iteration</SPAN>
+
== 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}}
-
{{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>
-
== L Systems Combined with Genetics ==
+
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;">Systems that allow evolution of form</SPAN>
 
-
L Systems can be combined with genetic programming
+
<SPAN STYLE="font-size: larger;"><u>Syntax Added to the Production Rules</u></SPAN>
-
* Initial condition, axioms and production rules must be translated into gene representation
+
-
* Genetic operations must be adapted for L System genes
+
-
** Mutation: like Karl Simms, define mutations to parse and substitute so mutations do not "break" the grammar.
+
-
** Crossover: more complicated, allow for example, rule swapping.
+
-
 
+
-
This is an important conceptual leap than having genes for a specific phenotype (e.g. "red" or "tall") L-system genes would specify a mechanism which then creates form. Much more like real DNA.
+
-
 
+
-
 
+
-
== Stochastic L-systems ==
+
 +
"Sym1 (.#)&rarr; Str1" = "When Symbol 1 is matched there is a .# probability that String 1 should be substituted"
-
Like typical L-systems, but with multiple production rules for a single expression, each with a probability.
 
  p3: 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}}
+
{{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>
<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}}
+
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/lsys/book2.jpg|caption=Stochastic L-system}}
-
== Context Sensitive Stochastic L-systems ==
+
== 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>
-
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/lsys/book3.jpg|caption=Context Sensitive Stochastic L-systems rules}}
+
: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]
-
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/lsys/book4.jpg|caption=Examples of Context Sensitive Stochastic}}
+
[[Category:Complex systems]]
 +
[[Category:Systems]]
 +
[[Category:Systems used in Computer animation and effects]]
 +
[[Category:Systems used in Computer graphics]]
 +
[[Category:Systems used in Design]]

Current revision

Retrieved from "http://philipgalanter.com/generative_art/wiki/index.php5?title=L-systems"
Personal tools