Graftal

From Wikipedia, the free encyclopedia

Merge arrows
 It has been suggested that this article or section be merged with L-system. (Discuss)

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.

Contents

[edit] 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:

<<image required>>

[edit] 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.

[edit] Stochastic 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.

[edit] 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.

[edit] 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.

[edit] References

Languages