Graphics Reference
In-Depth Information
The
BoxTree
presented in [Zachmann95] is also a recursively constructed hierarchy
of AABBs defined in the object's coordinate frame. Here, however, as a bounding box
is cut into two (not necessarily equal size) parts by a splitting plane the resultant sub-
boxes directly form the AABBs. Primitives fully inside either sub-box are assigned to
the corresponding set. Any primitives straddling the splitting plane are sent to both
boxes, resulting in a duplication of primitives. Overall, the construction is very similar
to that of a
k
-d tree.
As primitives straddling the splitting plane are duplicated, the choice of splitting
plane is made in an attempt to balance the tree and to minimize the number of
straddling primitives. Before attempting to find this splitting plane, Zachmann first
checks to see if there is a splitting plane that trims away a“large”(as large as possible)
part of empty space from the AABB, making it fit the contained geometry better.
Large is here defined by the ratio of the empty box to its parent being greater than
a preset constant. All three AABB axes are tested during this operation and the one
with the best result is used. In addition to stopping the recursion when a certain
depth has been reached or the set of primitives is less than some particular limit,
it is also stopped if one of the sub-boxes contains almost as many primitives as its
parent box.
As the BoxTrees are constructed in model space, during testing they have to be
transformed as the objects are transformed. However, as all AABBs share the same
orientation as the top node, most calculations can be reused during the hierarchy
traversal. To test the rotated AABBs (now OBBs), the separating-axis test can be used,
now greatly simplified by the fact that the 15 axes remain the same throughout the test.
Zachmann also describes an alternative clipping-based overlap test. For traversing
the trees, Zachmann uses the simultaneous traversal method.
In a later presentation, Zachmann describes an alternative implementation in
which instead of directly using the splitting plane to determine the boundary of the
sub-boxes he determines the two planes that bound the straddling primitives on
either side along the splitting axis. The“left”sub-box then becomes the left part of the
parent AABB, split at the position of the rightmost of the two planes, and vice versa
for the “right” sub-box. In other words, the child AABBs are identical to the parent
AABB except for one side. In this representation both children are represented using
just two (float) values, given the parent volume [Zachmann00].
Both van den Bergen's and Zachmann's methods work on arbitrary polyhedra or
polygon soups. As such, they will only reliably detect surface collisions. They do not
detect when one object is fully inside the other.
6.4.3
Sphere Tree Through Octree Subdivision
Thanks to its simplicity, a popular approach to building a sphere tree is to construct
it from an octree subdivision of the object volume [Tzafestas96]. First, the object
is enclosed in the smallest encompassing bounding cube. This cube is recursively
subdivided into eight equal-size parts, or octants. Any octant that contains part of
