For my technical piece, I had to draw trees. I searched the web for different kinds of tree drawing programs. Through by research, I found out that L-Systems are a way to represent tree structures easily. The implemented Lsystem is based on the one described in the book : The Algorithmic Beauty of Plants by P. Prusinkiewicz and A. Lindenmayer (this is where the L from Lsystems comes from).
LSystems was a system designed to represent plants. If you look at plants carefully, you would notice that plants are comprised of repeating simple patterns. They are not all randomly composed as we might initially think. Good looking plants have this repeated pattern to them. So a way to capture this repeated looking pattern is through control rules. These production rules are very similar to a context-free language. For instance, we first start out with a axiom string that represents the initial plant, then we will apply the rules. For example:
FAA
A=F+B
B=F-A
| Iteration: | Resulting String: |
| Start | FAA |
| 1 | FF+BF+B |
| 2 | FF+F-AF+F-A |
| 3 | FF+F-F+BF+F-F+B |
| 4 | FF+F-F+F-AF+F-F+F-A |
| 5 | FF+F-F+F-F+BF+F-F+F-F+B |
We would use the final production string to draw a picture. To save space and speed up parsing, each rule is only one character long. See "LSystem Commands" for the drawing commands implemented in my system.
1. The number of times to apply the rules (or the recursion depth.)
2. The default angle for any turn/pitch/roll.
3. The thickness of the cylinder as a ratio of the height. (50 => 50% thickness of height)
4. Axiom is the first rule asserted. (Example: FAA)
5. The following lines indicate the rules used. (Example: A=F++B)
6. Finally, the '@' character indicates the end of the file and stop parsing.
# Sample of a LSystem File: sample.ls # - Lines that start with '#' are consider comments 5 # Recursion Depth: Apply the rules 5 times 30 # Default Angle: Default turn/pitch/roll is 30 degrees 50 # Thickness variable: width as % of height # Axiom: FAA # The axiom - The first rule asserted # Rules: A=F<B # Rule 1 B=F>AA # Rule 2 @ # end of file mark |
Each character in the LSystem represents a drawing command. The following drawing commands are implement in my system:
| Turtle Orientation commands | ||
|---|---|---|
| + | turn left around up vector | |
| +(x) | turn x left around up vector | |
| - | turn right around up vector | |
| -(x) | turn x right around up vector | |
| & | pitch down around left vector | |
| &(x) | pitch x down around left vector | |
| ^ | pitch up around left vector | |
| ^(x) | pitch x up around left vector | |
| > | roll left (counter clockwise) around forward vector | |
| >(x) | roll x left around forward vector | |
| < | roll right (clockwise) around forward vector | |
| <(x) | roll x right around forward vector | |
| Special Orientation commands | ||
| | | turn 180 deg around up vector | |
| % | roll 180 deg around forward vector | |
| $ | roll until horizontal | |
| ~ | turn/pitch/roll in a random direction | |
| ~(x) | turn/pitch/roll in a random direction with a maximum of x degrees | |
| t | correction for gravity with 0.2 (Not Implemented) | |
| t(x) | correction for gravity with x (Not Implemented) | |
| Movement commands | when {} active | |
| F | move forward and draw full length | record vertex |
| F(x) | move x forward and draw | record vertex |
| Z | move forward and draw half length | record vertex |
| Z(x) | move x forward and draw | record vertex |
| f | move forward with full length | record vertex |
| f(x) | move x forward | record vertex |
| z | move forward with half length | record vertex |
| z(x) | move x forward | record vertex |
| g | move forward with full length | don't record vertex |
| g(x) | move x forward | don't record vertex |
| . | don't move | record vertex |
| Structure commands | ||
| [ | push current state | |
| ] | pop current state | |
| { | start polygon shape | |
| } | end polygon shape | |
| Inc/Dec commands | ||
| " | increment length with 1.1 | |
| ' | decrement length with 0.9 | |
| "(x) | multiply length with x also '(x) | |
| ; | increment angle with 1.1 | |
| : | decrement angle with 0.9 | |
| :(x) | multiply angle with x also ;(x) | |
| ? | increment thickness with 1.4 | |
| ! | decrement thickness with 0.7 | |
| ?(x) | multiply thickness with x also !(x) | |
| Additional commands | ||
| c | increment color index (Not Implemented) | |
| c(x) | set color index to x (Not Implemented) | |
| @ | end of object | |
Note:
Front Vector = Y-Axis
Left Vector = X-Axis
Up Vector = Z-Axis
The two commands I did not impalement were gravity and color. I did not implement color because the trees should be textured using Maya's Hyper shade colors. And I did not adjust for gravity because I did not know what they mean by adjusting for a gravity of .2. The trees I used do not use this command anyways. Any none recognized characters are ignored.
I wrote my own LSystem Parser from scratch using Microsoft String class instead of the primitive C-Style character arrays. This might be more inefficient but I removed the need to keep track of different buffer sizes or the need to dynamically allocate/deallocate character array space. I speedup the parsing by using temporary smaller stings while concatenating production strings. When a small string reaches a certain size, I concatenation it to the final string.
Okay, I will admit that this part took a lot longer then I though it would. Initially, I created the Maya plugin using NURBS surfaces. But I found out that each NURBS skins would have to created separately, and that cracking could occur when trying to attach surfaces. After creating the NURBS surface implementation, I switched to using a polygon mesh to draw the tree. To try to reduce the cracking and the number of data points used, I tried to reuse the last data points used. This caused some problems when the turtle would "roll" more then 45 degrees. This would cause a twisted looking cylinder at the rotation, which was unacceptable. To solve this problem, I tried to realign the cylinder up as closely as possible from the previous points after a rotation.
To introduce more randomness to tree, I introduced a small amount of "wiggle" to all rotations. But I wanted rotations that were pretty close to the original rotation, but varied slightly. I found a program on the web that would produce non-uniform random numbers using a uniform distribution of random numbers. The distribution I wanted was close to a normal distribution of numbers. Here is the probability function used:
Normal distribution definition (mean m and standard deviation s):
f(x) = (2*pi*s)-0.5*exp(-0.5*s-2*(x-m)2)
For my trees, I set the following parameters:
Mean = m = 0
Standard Deviation = s = 2.5
Meaning a majority of the random numbers produced will be generated between -2.5 and +2.5 degrees from zero. The probability of having numbers greater then +/-5 is very slim. In the end, the resulting trees generated will be slightly different from each other.
There are a lot of ways to mutate an LSystem string. For my mutations, I just change the basic rules or axiom strings. Here are a few ways:
1. You can add an extra rule to a random place within the Axiom or an rule
2. You can change one of the characters in the production string to something else.
3. You can randomly remove a character from the any of the rules or axiom string.
The resulting production strings can be quit dramatic. Some changes are more dramatic then others. There is a parameter in the the command line that indicates how many times to mutate the production string.
Since we need a forest of trees, I wrote a script that would produce a forest of trees in Maya. Unfortunately, this script was never used in the final rendered scene because the scenes were already rendered by time I developed the script. The script uses a tiled grid of hexagonal shapes. I would find the center of the hexagonal shape. Using the Non-Uniform random number generator, I would randomly place the tree around the center location of the hexagonal shape. There is a higher probability that the tree would be placed nearer to the center location then to its edges. All the user would have to specify is the grid width and length.
| Flag Name | Flag | Example |
| Filename | -f [Filename] | tree -f "U:\\trees\\tree01.LS" |
| Output Filename | -o [Output Filename] | tree -o "U:\\trees\\treeOutput1.LS" |
| Number of Slices per Cylinder | -s [Integer #] | tree -s 8 |
| Minimum Thickness | -th [Float #] | tree -th .5 |
| Angle (Overriding default angle) | -a [Float #] | tree -a 30 |
| Forward Length (default) | -l [Float #] | tree -l 1.0 |
| Number of Mutations | -m [Integer #] | tree -m 5 |
| Pre-made tree types | -t [Integer # between 0-15] | tree -t 0 |
| Amount of Jitter | -j [Double #] | tree -j 2.5 |
| Trees (creating a forest) | -ts [Width] [Length] | tree -ts 100 200 |
1. Sample of command line based LSystem parser (also include sample LSystem trees):
Laurens Lapre: DOS based Lparser
2. Breeding different LSystems:
3. Uniform and Non-Uniform random number generators: