Graphics Reference
In-Depth Information
Regardless of restrictions, there are still many choices of where to place a
partition:
• Mean split on extent
• Mean split on primitives
• Median split on primitives
• Constant ray intersection probability [Hav00]
• Clustering
Splitting along the mean of the extent of all primitives at a node along each
axis yields a set of nested
k
-cubes [RR78]. That is, each partition is at the center
of its parent's polyhedron. In 3D, this is called an
oct tree
(a.k.a. “octree”) (see
Listing 37.14). Although they can be represented using binary trees, for efficiency
oct trees are typically implemented with eight child pointers, hence their names.
They have 2D analogs in
quad trees
(see Figure 37.11), and can of course be
extended to 1D or 4D spaces and higher.
Listing 37.14: Oct tree representation.
1
2
3
4
5
6
7
8
9
10
11
12
13
template
<
class
Value
>
class
OctTree {
class
Node {
public
:
Node
*
child[8];
List<
Value
> valueArray;
};
Node
*
root;
Vector3
extent;
Point3
origin;
...
};
In general, building trees is a slow operation if implemented in a straightfor-
ward manner. It was classically considered a precomputation step. In that case,
one avoided changing the structure of the tree at runtime.
However, if you are willing to complicate the tree-building process and work
with a concurrent system, you can build trees fairly fast on modern machines.
Lauterbach et al. [LGS
+
09] reported creating trees dynamically on a GPU at about
half the speed of rasterization for a comparable number of polygons on that GPU.
Having tree-building performance comparable to rasterization performance means
that it can be performed on dynamic scenes. Furthermore, for many applications,
most of the geometry in a scene does not change position between frames. In
this case, only the subtrees containing dynamic elements need to be rebuilt. For-
tunately, although implementing a fast tree-building system is difficult, there are
libraries that implement the tree build for you.
Here are some conventional wisdom and details.
• Current hardware architectures favor very deep trees, so plan to keep sub-
dividing down to one or two primitives per node [SSM+05].
• As discussed, we often want the tree to be
un
balanced [SSM+05].
