Graphics Reference
In-Depth Information
• Be careful about precision when splitting elements. Due to finite precision,
the new vertices introduced will rarely lie on a splitting plane, and will thus
cause the split primitives to poke slightly into the sibling node.
• Be careful about less-than versus less-than-or-equal-to comparisons. Con-
sider what happens to a point on a splitting plane and ensure that your
tree-building and tree-traversal algorithms are consistent with one another.
Unfortunately, a splitting plane passing exactly through a vertex or edge is
not a rare situation because you often chose splitting planes based on the
primitives themselves.
A
Bounding Volume Hierarchy
(
BVH
) is a spatial tree comprising recursively
nested bounding volumes, such as axis-aligned boxes [Cla76]. Figure 37.12 shows
a 2D axis-aligned box bounding volume hierarchy for a set of points. Listing 37.15
shows a typical representation of the tree.
Unlike a BSP tree, this type of tree provides tight bounds for clusters of primi-
tives and has finite volume. BVHs are commonly built by constructing a BSP tree,
and then recursively, from the leaves back to the root, constructing the bounding
volumes. The bounding volumes of sibling nodes often overlap under this scheme;
as with a BSP tree one can also create a BVH that splits primitives to maintain dis-
joint sibling spaces.
Spatial structure
g
b
a
e
c
d
f
Logical structure
a
b
c
d
e
f
g
Figure 37.12: A depiction of a 2D axis-aligned box bounding volume hierarchy (BVH). This
is an alternate form of tree to the binary space partition tree that provides tighter bounds
but does not allow updates without modifying the tree structure.
