Pine tree from
a closed view point
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.
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
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
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
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.
Hierarchy for LOD
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
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
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
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
Figure 4. Pine
tree at level-of-Detail 0
5. Tree Builder (Linux
Figure 5. Pine tree at level-of-Detail 0
tree at level-of-Detail 1 (~3,000 polygons)
tree at level-of-Detail 2 (~1,000 polygons)
V. Sims, J. Moshell, C. Hughes, J. Cotton,
Jiangjian Xiao, "Recognition of Computer-Generated Trees",
46th proceeding of the Human Factors and Ergonomics Society,
V. Sims, J. Moshell, C. Hughes, J. Cotton,
Jiangjian Xiao, "Salient characteristics of virtual trees",
the 45th proceeding of the Human Factors and Ergonomics
Society, Minneapolis, Minnesota, October, 2001.