3D L-System Trees Generator
Posted November 1st, 2007
Description:
Generation of 3D tree models using L-Systems on DirectX.
Summary:
The goal of the project was to generate 3D trees programatically rather than using a design tool. A tree is a complex model, containing thousand of vertices, which are both hard to create and inneficient to store. By saving just the information necessary to generate them we save memory and make their creation easier. The steps to accomplish this are:
<ul>
<li>Create a language that allows specifying an L-System, and write a lexer and a parser for it.</li>
<li>Interpret the language and create a 3D model from it.</li>
<li>Give the model life: create branches and leaves.</li>
images:
The tree is drawn using a "turtle" method. The turtle starts at a certain position, for example (0, 0). The turtle follows the actions given by a rule of the L-System.
If it encounters f, it advances a step. +, -, <, >, v and ^ tell the turtle to turn clockwise or counterclockwise aroung a given axis relative to the turtle, for example up, left or head. A number between parenthesis indicates the ammount to step or turn. For example, f(2) advances two steps instead of one.
s, h, u, l and r are multipliers. s multiplies the current step by the given number. h, u and l multiplies the turn angle along each of the axis. r multiplies the trunk radius.
A branch tells the turtle to push it’s state into a stack, do the actions inside the branch, and then pop the state. This effectively allows making many branches from a given point.
If the name of a rule is found, it is consumed (interpreted again by the turtle). Since this may lead to infinite recursion, a number of iterations is defined: each time a rule is consumed, the number of iterations is decremented, until no further rules are consumed.
A TurtleCommander interprets the rules, starting by an axiom (the name of the first rule to intepret). As it interprets the rules and actions, it notifies an ITurtle what to do. An ITurtle is an interface that has methods like Advance, RotateAlongAxis, MultiplyCurrentStep, etc. In this way, the intepretation of the rules is decoupled from their processing. A 2D ITurtle will ignore the rotation axis because there is only one in a 2D plane.
Another important aspect is to give realism to the generated trees. If the rules are obeyed without modification, the trees will look too symmetric, too perfect. To fix this, we introduce randomness when intepreting an action, so a step or a rotation becomes a little longer or shorter. This is all handled by the ITurtle implementation.