Graftal

Graftal

A graftal or L-system is a formal grammar used in computer graphics to recursively define branching tree and plant shapes in a compact format. The shape is defined by a string of symbols constructed by a graftal grammar. A graftal grammar consists of an alphabet of symbols that can be used in the strings, a set of production rules which translate each symbol into a non-empty string of symbols, and an axiom from which to begin construction.

Example

:axiom: 0
:rules:
:1 -> 11
:0 -> 1 [0] 0
: [ -> [
:] -> ]

The graftal is built by recursively feeding the axiom through the production rules. Each character of the input string is checked against the rule list to determine which character or string to replace it with in the output string. In this example, a '1' in the input string becomes '11' in the output string, while ' [' remains the same. Applying this to the axiom of '0', we get:

:axiom: 0
:1st Recursion: 1 [0] 0
:2nd Recursion: 11 [1 [0] 0] 1 [0] 0
:3rd Recursion: 1111 [11 [1 [0] 0] 1 [0] 0] 11 [1 [0] 0] 1 [0] 0
:...

We can see that this string quickly grows in size and complexity. This string can be drawn as an image by using turtle graphics, where each symbol is assigned a graphical operation for the turtle to perform. For example, in the sample above, the turtle may be given the following instructions:

:0: draw a line segment ending in a leaf
: [: push position and angle, turn left 45 degrees;
:] : pop position and angle, turn right 90 degrees;

The push and pop refer to a LIFO stack (A more technical grammar would have separate symbols for "push position" and "turn left"). When the turtle interpretation encounters a " [," the current position and angle are saved, and are then restored when the interpretation encounters a "] ." If multiple values have been "pushed," then a "pop" restores the most recently saved values. Applying the graphical rules listed above to our earlier recursion, we get:

:"<>"

Variations

A number of elaborations on this basic graftal technique have been developed which can be used in conjunction with each other. Among these are stochastic, context sensitive, and parametric grammars.

tochastic grammars

The grammar model we have discussed thus far has been deterministic -- that is, given any symbol in the grammar's alphabet, there has been exactly one production rule, which is always chosen, and always performs the same conversion. One alternative is to specify more than one production rule for a symbol, giving each a probability of occurring. For example, in the above grammar, we could change the rule for rewriting "0" from:

:0 -> 1 [0] 0

To a probabilistic rule:

:0 (0.5) -> 1 [0] 0
:0 (0.5) -> 0

Under this production, whenever a "0" is encountered during string rewriting, there would be a 50% chance it would behave as previously described, and a 50% chance it would not change during production. When a stochastic grammar is used in an evolutionary context, it is advisable to incorporate a random seed into the genotype, so that the stochastic properties of the image remain constant between generations.

Context sensitive grammars

A context sensitive production rule looks not only at the symbol it is modifying, but the symbols on the string appearing before and after it. For instance, the production rule:

:b < a > c -> aa

transforms "a" to "aa", but only If the a occurs between a "b" and a "c" in the input string:

:...bac...

As with stochastic productions, there are multiple productions to handle symbols in different contexts. If no production rule can be found for a given context, the identity production is assumed, and the symbol does not change on transformation. If context-sensitive and context-free productions both exist within the same grammar, the context-sensitive production is assumed to take precedence when it is applicable.

Parametric grammars

In a parametric grammar, each symbol in the alphabet has a parameter list associated with it. A symbol coupled with its parameter list is called a module, and a string in a parametric grammar is a series of modules. An example string might be:

:a(0,1) [b(0,0)] a(1,2)

The parameters can be used by the functions drawing the graftal, and also by the production rules. The production rules can use the parameters in two ways: first, in a conditional statement determining whether the rule will apply, and second, the production rule can modify the actual parameters. For example, look at:

:a(x,y) : x = 0 -> a(1, y+1)b(2,3)

The module a(x,y) undergoes transformation under this production rule if the conditional x=0 is met. For example, a(0,2) would undergo transformation, and a(1,2) would not.

In the transformation portion of the production rule, the parameters as well as entire modules can be affected. In the above example, the module b(x,y) is added to the string, with initial parameters (2,3). Also, the parameters of the already existing module are transformed. Under the above production rule,

:a(0,2)

Becomes

:a(1,3)b(2,3)

as the "x" parameter of a(x,y) is explicitly transformed to a "1" and the "y" parameter of a is incremented by one.

Parametric grammars allow line lengths and branching angles to be determined by the graftal grammar, rather than the turtle interpretation methods. Also, if age is given as a parameter for a module, rules can change depending on the age of a plant segment, allowing animations of the entire life-cycle of the tree to be created.

References

* "The Algorithmic Beauty of Plants" by Przemyslaw Prusinkiewicz and Aristid Lindenmayer.
* "Texturing and Modeling: A Procedural Approach" by D.S. Ebert, F.K. Musgrave, et.al., ISBN 0-12-228730-4


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Fractal — A fractal is generally a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced size copy of the whole, [cite book last = Mandelbrot first = B.B. title = The Fractal Geometry of… …   Wikipedia

  • L-system — An L system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a …   Wikipedia

  • List of fractal topics — This is a list of fractal topics, by Wikipedia page, See also list of dynamical systems and differential equations topics.*1/f noise *Apollonian gasket *Attractor *Box counting dimension *Cantor distribution *Cantor dust *Cantor function *Cantor… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • компьютерная графика — визуализация изображения информации на экране дисплея (монитора). В отличие от воспроизведения изображения на бумаге или ином носителе, изображение, созданное на экране, можно почти немедленно стереть или (и) подправить, сжать или растянуть,… …   Энциклопедический словарь

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”