3D Trees Generator
Generation of 3D tree models using L-Systems on DirectX
This tool was commissioned to Manas to be part of a larger 3D universe rendering engine for a major game console manufacturer. You can read more about it in our blog.
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:
- Create a language that allows specifying an L-System.
- Write a lexer and a parser for it.
- Interpret the language and create a 3D model from it.
- Give the model life: create branches and leaves.
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 around a given axis relative to the turtle, for example up, left or head. A number between parenthesis indicates the amount 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 interpret). 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 interpretation 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 interpreting an action, so a step or a rotation becomes a little longer or shorter. This is all handled by the ITurtle implementation.