Procedural Tree Generator
Language: C++, Middleware: OpenGL
Overview of the project
Motivation
- How to create natural looking trees.
Problem which I had
- Trees have stochastic features as well as structured features. Different species of tree should have completely different structure, but also there should be some variation even in same species of tree.
Which features are included in this project
- Generating different species of trees based on different generation rules
- Randomizing the shape of tree by stochastic values
How to solve the problem
- Used L-system to define different rules for trees and applied stochastic values to randomize angle or direction of tree branches. So L-system allows that trees actually grow based on rules. Also, the system supports the combination of different species.
Limitation
- Only 7 rules (species of tree) are supported in this project, because defining rules for realistic trees was very difficult.
Detail of the project
1.Objective
This project aims to generate natural-looking tree using L-system. As changing rules and applying random angle, we can generate various shape of tree. Rule can be related to species and random angle can affect the diversity in the same species of tree. In addition, rendering has been largely considered such as 3D tree, leaves and different radius of trunk because these feature plays significant role in the diversity of tree.
2.Introduction
L-system is the system which controls evolution of the shape using self-similarity feature and it is very useful to generate tree because similar features can be found from root to branches. L-system is a parallel rewriting system which consists of axiom, the number of iteration, angle and rules.
Axiom denotes initial state of tree which is same as a seed of tree. The number of iteration is related to how much the tree will grow which can be life expectancy of the tree. Angle denotes how the trunk of tree is branching and determines detail of the tree. Finally, rules determine general appearance of tree which is related to the species of tree.
This project consists of three stages to generate trees.
① Reading configuration file: Configurations such as axiom and rules are stored in text file which is defined by the user in advance. One of configurations will be chosen by user’s key input.
② Updating initial axiom and build the tree: Based on the axiom and rules from configuration file, new string will be constructed. After interpreting this string using predefined grammars, tree will be generated and the appearance of tree will be determined at this stage as well as 3D shape.
③ Rendering the tree: Rendering and optimization the tree will be considered at this stage.
3.Specification
Following diagram denotes operation flow of this project.
3.1. Intialisation
Data structure of tree and variables are initialised in this stage. Dynamic array is used for data structure of tree having stack structure. Root of the tree will be stored at the bottom of the tree and end of branch will be located at the top of the stack (see Figure 1). This structure is beneficial to keep track of the information about which trunk part is connected to which branch.
Figure 1. Stack structure for tree
Transformation matrix, which determines the location of next trunk part, is initialised and textures are loaded during initialisation stage.
Data structure of tree and variables are initialised in this stage. Dynamic array is used for data structure of tree having stack structure. Root of the tree will be stored at the bottom of the tree and end of branch will be located at the top of the stack (see Figure 1). This structure is beneficial to keep track of the information about which trunk part is connected to which branch.
Figure 1. Stack structure for tree
Transformation matrix, which determines the location of next trunk part, is initialised and textures are loaded during initialisation stage.
3.2. Read configuration
Configuration of the tree is stored in text file, which includes axiom, the number of iteration, angle for branching and rules. File stream library has been used for reading data file. File stream reads all data stream until file pointer reaches ‘Space’ or ‘Enter’ in the file. Figure 2 shows the contents of configuration file.
Figure 2. Contents of configuration file
The system looks up configuration index and then once the index is found, it loads number of iteration, degree, axiom and rules in order until file pointer meets the separator.
Configuration of the tree is stored in text file, which includes axiom, the number of iteration, angle for branching and rules. File stream library has been used for reading data file. File stream reads all data stream until file pointer reaches ‘Space’ or ‘Enter’ in the file. Figure 2 shows the contents of configuration file.
Figure 2. Contents of configuration file
The system looks up configuration index and then once the index is found, it loads number of iteration, degree, axiom and rules in order until file pointer meets the separator.
3.3. Update string
String is the list of characters which is used to generate tree as being interpreted by predefined grammars. The string will be written at this stage using axiom and rules. In addition, the number of iteration plays key role in tree growth. For example, if given axiom is ‘F’ and rule is ‘F→F[+F]F[-F]F, the string will be …
In each iteration, the letter will be replaced by the sentence in the rules.
String is the list of characters which is used to generate tree as being interpreted by predefined grammars. The string will be written at this stage using axiom and rules. In addition, the number of iteration plays key role in tree growth. For example, if given axiom is ‘F’ and rule is ‘F→F[+F]F[-F]F, the string will be …
In each iteration, the letter will be replaced by the sentence in the rules.
3.4. Compute depth
Computing depth of the tree is crucial to natural looking tree. The width of trunk part which is close to root will be thinker than that of branch part. In order to compute the depth of tree, the number of node (trunk part), which the system visited, has to be counted. In this project, it starts from root node and finishes at the node having maximum depth in tree structure, which is at the top of the stack. From this stage, formal grammar of L-System is used, but only push and pop operations are considered to trace depth of each branches. Figure 3 shows the process of depth counting.
Figure 3. Push / Pop operation (Left up/down) and depth counting (Right)
When the tree generates new branch, its depth counting has to be same with original’s trunk. In order to achieve this task, push/pop operation is used. When new branch is created, current depth will be stored in the stack and its depth continues to increase. When it reaches leaf node of new branch, it comes back to original branch and original depth will be restored. This method guarantees incremental order from the root to any leaf node.
As the depth of tree increases, its width will be decreased. Also, leaf nodes always have sharp tips for natural looking.
Computing depth of the tree is crucial to natural looking tree. The width of trunk part which is close to root will be thinker than that of branch part. In order to compute the depth of tree, the number of node (trunk part), which the system visited, has to be counted. In this project, it starts from root node and finishes at the node having maximum depth in tree structure, which is at the top of the stack. From this stage, formal grammar of L-System is used, but only push and pop operations are considered to trace depth of each branches. Figure 3 shows the process of depth counting.
Figure 3. Push / Pop operation (Left up/down) and depth counting (Right)
When the tree generates new branch, its depth counting has to be same with original’s trunk. In order to achieve this task, push/pop operation is used. When new branch is created, current depth will be stored in the stack and its depth continues to increase. When it reaches leaf node of new branch, it comes back to original branch and original depth will be restored. This method guarantees incremental order from the root to any leaf node.
As the depth of tree increases, its width will be decreased. Also, leaf nodes always have sharp tips for natural looking.
3.5. Generate tree
The string, which is written during ‘update string’ operation, will be interpreted in this stage using formal grammar of L-System. In this project, following grammars are defined to generate tree.
‘+’ : Plus rotation along z axis
‘-’ : Minus rotation along z axis
‘&’: Plus rotation along y axis
‘<’: Plus rotation along x axis
‘>’: Minus rotation along x axis
‘[‘ : Push (Save) matrix operation
‘]‘ : Pop (restore) matrix operation
‘F’: Growth operation
These grammars can be expressed using multiple transformation matrix operations. ‘F’ is growth operation which adds new trunk part using translate matrix along y axis (see Figure 4). ‘-‘, ‘+’, ‘&’, ‘<’ and ‘>’ are rotation operation and rotated trunk part will be added as combing with ‘F’ (see Figure 5).
Figure 4. Growth operation Figure 5. Rotation operation
Using these matrix, we can keep track of every points on the tree and make sure that each trunk parts are connected. For example, we have
Start point of trunk part : (0,0,0)
End point of trunk part : (0,5,0)
Transformation matrix: translate 5 along y axis.
, then next part can be found using simple matrix and vector multiplication.
New start point : start point * matrix = [0 0 0 1] * = (0,5,0)
New end point : end point * matrix =[0 5 0 1] * = (0,10,0)
Rotation is done same way (see Figure 6).
Push ( ‘[‘ ) and pop ( ‘]’ ) matrix operations are directly related to branching of tree. For push operation, transformation matrix is stored in the stack and new branch will be generated after that. The branch will be ended with ‘]’ and corresponding matrix will be restored from the stack so that we can easily find the location of original branch and the tree continues to grow from that position (see Figure 7).
The string, which is written during ‘update string’ operation, will be interpreted in this stage using formal grammar of L-System. In this project, following grammars are defined to generate tree.
‘+’ : Plus rotation along z axis
‘-’ : Minus rotation along z axis
‘&’: Plus rotation along y axis
‘<’: Plus rotation along x axis
‘>’: Minus rotation along x axis
‘[‘ : Push (Save) matrix operation
‘]‘ : Pop (restore) matrix operation
‘F’: Growth operation
These grammars can be expressed using multiple transformation matrix operations. ‘F’ is growth operation which adds new trunk part using translate matrix along y axis (see Figure 4). ‘-‘, ‘+’, ‘&’, ‘<’ and ‘>’ are rotation operation and rotated trunk part will be added as combing with ‘F’ (see Figure 5).
Figure 4. Growth operation Figure 5. Rotation operation
Using these matrix, we can keep track of every points on the tree and make sure that each trunk parts are connected. For example, we have
Start point of trunk part : (0,0,0)
End point of trunk part : (0,5,0)
Transformation matrix: translate 5 along y axis.
, then next part can be found using simple matrix and vector multiplication.
New start point : start point * matrix = [0 0 0 1] * = (0,5,0)
New end point : end point * matrix =[0 5 0 1] * = (0,10,0)
Rotation is done same way (see Figure 6).
Push ( ‘[‘ ) and pop ( ‘]’ ) matrix operations are directly related to branching of tree. For push operation, transformation matrix is stored in the stack and new branch will be generated after that. The branch will be ended with ‘]’ and corresponding matrix will be restored from the stack so that we can easily find the location of original branch and the tree continues to grow from that position (see Figure 7).
Figure 6. Finding next location
Figure 7. Push and Pop operations
Finally, in order to generate tree with random value, random angle rotation has been considered in this project. Certain amount of random value will be added to each rotation.
3.6. Rendering (Draw)
As a result of previous stage, the tree was formed from lines. We need 3D shape of trunk/leaves and lighting for natural looking tree.
After ‘Generate tree’ operation, we will have the location from transformation matrix and can generate 3D geometry using this information. The shape of trunk part is tube which is equivalent to cylinder without top and bottom circle (see Figure 8). In this project, only 10 points are sample on the circle for performance issue (20 points in total).
Figure 8. Trunk part
In order to draw leaves, I used some trick. Rather than drawing single leaf at a time, I used texture having many leaves. However, if we place this texture onto a plane, leaves will have very dull appearance. So I used 4 planes and they are 90 degree rotated along the line dividing plane into half (see Figure 9).
As a result of previous stage, the tree was formed from lines. We need 3D shape of trunk/leaves and lighting for natural looking tree.
After ‘Generate tree’ operation, we will have the location from transformation matrix and can generate 3D geometry using this information. The shape of trunk part is tube which is equivalent to cylinder without top and bottom circle (see Figure 8). In this project, only 10 points are sample on the circle for performance issue (20 points in total).
Figure 8. Trunk part
In order to draw leaves, I used some trick. Rather than drawing single leaf at a time, I used texture having many leaves. However, if we place this texture onto a plane, leaves will have very dull appearance. So I used 4 planes and they are 90 degree rotated along the line dividing plane into half (see Figure 9).
In order to draw leaves, I used some trick. Rather than drawing single leaf at a time, I used texture having many leaves. However, if we place this texture onto a plane, leaves will have very dull appearance. So I used 4 planes and they are 90 degree rotated along the line dividing plane into half (see Figure 9).
Figure 9. Creation of leaves
Finally, Phong shading has been used for lighting. Computation of normal direction can be done same way as finding points (see Figure 10).
Figure 9. Creation of leaves
Finally, Phong shading has been used for lighting. Computation of normal direction can be done same way as finding points (see Figure 10).
Figure 10. Phong shading
4.Result