Overview
In this paper, and cooresponding project, I present a working model of an L-system used to model plant-like structures, based on the work of Prusinkiewickz, Lindenmayer, and Hanan. The L-system is an ideal representational model for computer generated plants, in that by varying the programs used to define the plant's growth, various representations can be achieved.
Previous work
Prusinkiewickz, Lindenmayer, and Hanan [3] proposed a similar (and admittedly more advanced) system for modeling the growth of plants. They promoted the idea of using L-systems as a modeling system, and provided a very similar grammar system, to which this work owes a lot. They also provided methods for stochastic variance, enabling more realistic plant-forms, as well as tropism, simulating the directed growth of plants toward a light source.
Prusinkiewickz, James, and Mech [4] further expanded the plant-growth model to simulate environmentally sensitive L-systems, so that plants grow in accordance to their surroundings. Plants also are sensitive to pruning, reflecting their modifications in their growth patterns.
Featherstone's [1] work with robotic dynamics could be useful in the modeling of gravity on a plants limbs, to simulate the pull and bending in a natural environment.
Motivation
My motivation for this project arose from an interest in fractal growth patterns, as well as [3]. I was interested in the idea of using grammars as programs for graphical development because of the way they lend themselves to a variety of uses. I wanted to design a project that would not only be expandable, in its capabilities, but also one that would allow many variations, simply by adjusting the controls, which in this case, are the plant grammars. The two most important aspects of a system such as this are the capabilities of the language and the "prettyness" of the graphical rendering. Because of the rule based system described below, adding additional features to the abilities of the language is fairly trivial. The graphical rendering in this case is very simple -- the plants merely consist of three-dimensional white lines -- but can easily be expanded to provide color, depth-buffered renderings of stalks with various thicknesses.
Techniques
The core of the program is based around the idea and implementation of an L-system, and a set of C++ classes to represent the various components of the system. The L-system contains a series of rules and associated replacement strings that define the behavior of the system.
On startup, the program reads in a grammar file that defines the behavior of the plant. The grammar file is parsed and rejected if there are any errors in the grammar, so as not to disrupt the growth of the plant once the replacement is under way. The grammar defines the starting string of the grammar, as well as the replacement rules. The rules are organized by letter in a linked list, so that multiple rules corresponding to different instances of the letter can share a common space. If the grammar definition of the tree is quite large, this helps to cut down on the time spent searching for the appropriate rules. Once the rules and their replacement strings are organized, the L-system can begin working on the iterative replacement process. The L-system contains an entry for each letter of the alphabet. When a rule is parsed, it is added to a linked list which contains all the rules for that letter. The replacement strings are attached to their corresponding rules for easy access once a rule has been located.
[representation of l-system]
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |
v v v
Rule -> Replacement String
|
v
Rule -> Replacement String
The replacement process works as follows:
For each character in the current string, examine the character, and see if there is a replacement. Determining whether a replacement exists consists of examining the current state of the character. The rule list for the current character is determined, and the rules on the rule list are examined one by one to see if the rule matches the character's state. Once a rule is matched, then the appropriate replacement string is converted to a regular string and is inserted into the current string. If no rules match, then the character is left as is. If the character matches a special symbol, the character is left as is, and an appropriate action will be taken.
This simple system can be used to represent many different plant structures.
Grammar description
The structure for the tree grammar files is as follows:
w: <STARTING STRING>
<STARTING STRING> : corresponds to the starting string to be used for the plant development.
p##: <LET>[<SUB>] [<RANGE>]-> <REPLACEMENT STRING>
<LET> : the uppercase character associated with the rule.
Example: A
<SUB> : (optional) the subscript of the letter, enclosed
in curly braces. The subscript can either be a positive number, indicating
the subscript value, or an 'x', indicating that the rule is not tied to a
particular number. If it is the latter, the rule will usually have a
<RANGE> (see below). Examples : {0} or
{x}
<RANGE> : a range of numbers enclosed in parenthesis,
separated by a dash. Example: (0-10)
<REPLACEMENT STRING> : A replacement string is simply a
list of <LET>[<SUB>]s, with the exception that
the subscript can also be a {x+}, indicating that the current
subscript of the character being replaced should be incremented.
plant2
it is clear to see that the stalk will exponentially grow out of control:
In order to control the growth, the stalk should be replaced with "dead"
stalks that will not continue to grow, so that only the tip of the stalk
is growing. The letter
resulting in:
Although with a statement like this, left alone, the stalk will curl into a
loop, so it makes more sense to put a bounding condition on the rule, so
that it only operates for a few iterations before doing something else:
The above code segment would iterate for 4 segments before falling out of
the range of the rule (where x > 3):
In this case, F turns into four buds, and each bud turns into a petal.
Internally, a better parser would be utilized in later editions. Currently,
the program parses through a hierarchy of conditions to determine whether
the string is valid or not, rejecting the invalid strings that would cause
the program to fail. For the relatively simple cases involved, this is
not a problem, but a better system would be needed as the language
develops in complexity. A better system for organizing the rules in the
L-system would have to be developed, with a form of order of operations,
to sort the rules by priority. This way, if a rule should have precedence
over other rules (such as two similar rules, where one has a neighbor
condition, and the other doesn't), the higher rule with the higher
precedence would go first.
It is obvious that this is a "first-try" system, but I am confident in
the design of the program that it could be readily expanded into a more
full-featured system. The integration of the various parts of the system
works quite nicely (C++ classes representing the entire L-system, linked
lists of strings, the rules involved, and the replacement strings).
1. Featherstone, R., Robot Dynamics Algorithms Kluwer
Academic Publishers, Norwell 1987
2. Prusinkiewicz, P. and Lindenmayer, A. The Algorithmic Beauty of
Plants Springer-Verlag, New Tork, 1990. with J.S. Hanan,
F.D. Fracchia, D.R. Fowler, M.J.M. de Boer, and L. Mercer.
3. Prusinkiewicz, P., Lindenmayer, A., and Hanan, J. Developmental
Models of Herbaceous Plants for Computer Imagery Purposes ACM SIGGRAPH
(1988) 141-150
4. Prusinkiewicz, P., James, M., and Mech, R. Synthetic Topiary ACM
SIGGRAPH (1994) 351-358
Special symbols
The following special symbols are legal in the grammar's alphabet, and have
the following uses:
[ : push matrix -- used to preserve the current matrix position,
in order to allow branching
] : pop matrix -- used to retrieve previous matrix position in
order to come off a branch
/ : rotate u -- rotate clockwise around u
\ : rotate -u -- rotate counterclockwise around u
' : rotate v -- rotate clockwise around v
` : rotate -v -- rotate counterclockwise around v
| : rotate w -- rotate clockwise around w
_ : rotate -w -- rotate counterclockwise around w
Some example grammars (with example pictures):
Flowering stalks
w: A
p1: A -> `[///B][''''///B][''''''''///B][''''''''''''///B]Z
p2: B -> ZC{0}
p3: C{x} (0-2) -> Z\C{x+}
p4: C{3} -> ZD{0}
p5: D{x} (0-2) -> ZD{x+}
p6: D{3} -> Z[F]
p7: F -> [P]''''[P]''''[P]''''[P]
p10: P -> //||Z__Z__Z__Z__Z__Z__Z__Z
Branched tree
w: A{0}
p1: A{x} (0-2) -> ZA{x+}
p2: F -> [//A{0}]''[//A{0}]''[//A{0}]''[//A{0}]''[//A{0}]''[//A{0}]''[//A{0}]''[//A{0}]
p3: A{3} -> ZF
Describing controlled growth
One of the most enjoyable, and sometimes surprising aspects of creating a
plant grammar is the visualization of the result. Without proper planning,
however, the plants do not usually appear as the user desires. In order
to create a controlled plant, linear, rather than exponential, growth must
be controlled. If a grammar specifies a rule such as:
p1: A -> AA
A -> AA -> AAAA -> AAAAAAAA -> AAAAAAAAAAAAAAAA -> etc.
Z is used as a convention to represent
a fixed, non-growing piece of stalk:
p1: A -> ZA
A -> ZA -> ZZA -> ZZZA -> ZZZZA -> etc.
Curved branches
In order to define a curving branch, such as the base of the stalks in the
first example above, all that is needed is an extension to the above method
for linear growth of stalks. A rotation element is added to the linear
growth as such:
p1: A -> Z\A
p1: A{x} (0-3) -> Z\A{x+}
A{0} -> Z\A{1} -> Z\Z\A{2} -> Z\Z\Z\A{3} -> Z\Z\Z\Z\A{4} -> stop
Simple Hacks
Simple flowers or leaves can be simulated by converting a character into
a series of segments with rotations:
p1: F -> [P]''''[P]''''[P]''''[P]
p2: P -> //||Z__Z__Z__Z__Z__Z__Z__Z
Future work/Conclusions
There are many additions I'd like to add to the system, in order to really
make it useful. First and foremost, the graphical representations of the
plants would have to be enhanced. Color, depth buffering, and diminishing
width would have to be added, all of which are trivial, and may show up
shortly. The inclusion of rules based on neighboring nodes in the string,
as well as stochastic variations would help (the latter, more so) to render
less rigid, and more natural looking plants. Environmental effects, such
as sunlight, gravity, and contact with other objects would also further
enhance realism.
References