A graftal is a grammarbased model[?] 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 nonempty string of symbols, and an axiom from which to begin construction. For 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 is drawn as an image by using a turtle graphical interpretation, 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:
<<As soon as I figure out how to upload the image, I will)

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.
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 contextsensitive and contextfree productions both exist within the same grammar, the contextsensitive production is assumed to take precedence when it is applicable.
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 lifecycle of the tree to be created
For more information, see:
Search Encyclopedia

Featured Article
