Graphics Reference
In-Depth Information
(a)
(c) (b)
Figure 6.3
(a) Splitting at the object median. (b) Splitting at the object mean. (c) Splitting
at the spatial median.
split position, this brute-force alternative simply tests some small number of
evenly spaced points along the axis, picking the best one.
Splitting between (random subset of) the centroid coordinates.
Similar to the previous
method, splitting between the projected centroids attempts to minimize the
number of primitives straddling the splitting plane, at the expense of projecting
and sorting the centroids.
●
Figure 6.3 illustrates some of these splitting choices. Instead of directly selecting
a splitting point, the subsets can be built incrementally. For instance, [Zachmann98]
splits along the axis through the two most distant points,
a
and
b
. Starting by adding
the faces associated with
a
and
b
to the two different subsets, he assigns the remaining
primitives to the subset whose bounding volume increases less with the primitive
added. If both volumes increase by the same amount or do not increase at all (due
to the primitive being fully inside the volume), the primitive is added to the set with
fewer primitives.
Top-down construction is by far the most common approach to building bounding
volume hierarchies. The advantages include ease of implementation and fast tree
construction. The disadvantage is that as critical decisions are made early in the
algorithm at a point where all information is not available the trees are typically not
as good as possible.
6.2.2
Bottom-up Construction
In contrast to top-down methods, bottom-up methods are more complicated to
implement and have a slower construction time but usually produce the best trees
[Omohundro89]. To construct a tree hierarchy bottom up, the first step is to enclose
each primitive within a bounding volume. These volumes form the leaf nodes of the
tree. From the resulting set of volumes, two (or more) leaf nodes are selected based
on some
merging criterion
(also called a
clustering rule
). These nodes are then bound
within a bounding volume, which replaces the original nodes in the set. This pairing
