Drew Fulsom
GAME PROGRAMMER
Procedural Trees
About
-
Individual Project in Personal Engine
-
6 Week Development Time
High Concept
This was an attempt at creating trees procedurally using L-Systems. I focused on the general structure and appearance of the trees; considerable work needs to be done on their performance.
Notable Features
-
L-Systems
-
Swept Shapes
L-System
The overall structure of the generated trees are defined using L-Systems. L-Systems are a type of formal grammar that defines how characters can be replaced with other characters. For instance the rule: F -> FF says that any F's found are replaced with FF. This is done for a desired number of iterations.
The characters used in my generation each correspond to a way of altering the tree. F moves forward, adding vertices to the mesh along a swept circle. + and - turn, changing the angle of the next forward movement. [ and ] set a restore point and return to the last one respectively. This is what allows the L-System to create branching paths.
Implementing the L-System itself was fairly simple. The only thing of note is that the character replacement needs to happen "all at once" so that a character added in an iteration is not replaced in the same iteration.
Swept Shapes
Constructing the mesh of the tree is done by sweeping a circle forward and adding vertices at the beginning and end of its path. Using the position, heading, and width of both the start and end points, the world positions, normals, tangents, and texture coordinates can be calculated.
Cross products are used to calculate the two perpendicular vectors for each of the headings that are used to define a circle around those points. Quads are then added to the mesh by traversing those circles and connecting the corresponding points.