TreeBuilder

  Pine tree from a closed view point

Most of vegetations grow in such a way named self-similarity. To represent and describe the properties of vegetations, computer scientists use a fractal-pattern technique to recursively generate them, such as the famous L-system. Here I introduce a novel hierarchical approach to build a fast 3D tree model with different details.

1. Introduction

In this area, many researches focus on how to model a realistic tree, or simulate plant growth and movement, where the tree model may have lots of polygons. As a result, the time to render one frame for such tree mode may need several seconds or even more. For a forest with hundreds of trees, the rendering time may spend more than one hour even for one frame. Hence, it is impossible to use this technique to simulate a forest scene in real-time. With the aim of speeding the rendering process and performing a large scale forest simulation in real-time, here I present a  hierarchical approach to create a set of Level-of-Detail (LOD) in a single tree model, which can adaptively reduce the polygons of the models according to the detail level. In general, LOD only can be applied to a continuous mesh or a closed surface, such as the surface simplification technique. However, tree is a non-regular object with a number of stems and surfaces. It is very difficult to employ a continuous surface to model a tree. Fortunately, the similarity information is always available in most kinds of trees, which can be used to reduce the structure redundancy.

2. The Structure and Definition of Tree

In most of trees, we consider that there is a certain similarity among their structures. According to this similarity property, we can even distinguish and identify the category of a tree. Based on the self-similarity of a general tree shape, we construct our tree our model with four levels: main trunk, branch, sub-branch, and twig. The leaves usually grow on the twig, sub-branch, and branch as Figure 1.

Figure 1. The structure of a tree

Due to self-similarity of the tree structure, we use a same set of parameters, such as spread and roll angles, to control the growing direction of each level branch. Notice that for a different level, the value of spread and roll angles may have different ranges.

3. Tree Hierarchy for LOD

According the structure of tree, we can easily construct a tree-shape hierarchy from root node to leaf nodes to implement the LOD of the tree. Similar as Figure 1, we build a hierarchy from root node as shown in Figure 2. The branch nodes are divided into two classes: The first one is the common node which have one same level child and 1-6 next level side children; the second one is the side node which has the same properties with common node, but is added an additional field to identify the side sequence. For each common node, a data structure is used to record level and depth (m: level, n: depth). When the depth is increased, the length and diameter of the branch will become bigger. At each side node, a new branch is started and the sequence information will be recorded in the third field (m: level, n: depth, k: sequence). Each node has one link pointing to parent node and several links pointing to children nodes, which can speed up the node searching from any location.

 Figure 2. The hierarchy for a tree

To implement LOD of the tree model, our algorithm merges some nodes and replaces them by a new geometric object. The new object can be two across polygons or one billboard. These merged nodes should be nodes at the same level and come from the same side node parent. For example, at the level 5, we can merge the twigs to a new object on that level to achieve the LOD as shown in Figure 3. If we use two across polygons to replace the twig, the polygon number will be dramatically reduced from 30 per twig to 2 per twig.  Using the similar method, we can implement the LOD for level 4, 3, 2, 1. When the distance between the tree and view point is increased to a very large value, we even can replace some branch polygons by several lines, which can further improve the simulation speed.

  Figure 3. Merging nodes at level 5

In order to obtain realistic effect for the new object, we generate a new texture for the object dynamically from the rendering image, such as the twig. Therefore, the rendering effect after LOD reduction looks still similar as the original one even from the same view point. The detailed results are shown in Figure 4, 5, 6, 7.

4. Tree Builder (Windows version)

Figure 4. Pine tree at level-of-Detail 0

 5. Tree Builder (Linux version)

 Figure 5. Pine tree at level-of-Detail 0 (~10,000 polygons)

Figure6. Pine tree at level-of-Detail 1 (~3,000 polygons)

Figure7. Pine tree at level-of-Detail 2 (~1,000 polygons)

Related Publications: