Graphics Reference
In-Depth Information
size increases, they predict the objects are getting closer and they keep the front for
the next query. If instead the size stays the same, they predict the objects are moving
away and the front is rebuilt from scratch in the next query. This way, parent nodes
of the nodes in the front are never examined, and thus the major cost is avoided. An
analysis similar to the previous gives the new cost function as
s
=
p
D
n
+
p
S
n
−
p
U
0,
which for
p
D
2
n
/3, a drastic improvement. More importantly,
this function is nonnegative for any probability distribution and thus this method
should never perform worse than a traversal from the root.
To avoid a full rebuild in volatile situations in which the front would move up
only to immediately move down, they further propose deferring the rebuild by one
query. In effect, the front is rebuilt from scratch if it has not grown for two consecutive
queries. From their tests on a sphere tree, Li and Chen report an average speedup of
40% for the basic front-updating method. With deferred updating, they achieved an
average speedup of 84%, not far from the optimal speedup of 100%. When updating
was deferred for more than one query, performance degraded.
Overall, because the saving is proportional to the number of leaf nodes in the
front maintaining a front is more useful for larger hierarchies. For small hierarchies in
which only a few nodes can be skipped, the overhead is likely to exceed any savings.
=
p
S
=
p
U
=
1/3 is
s
=
6.8
Summary
Bounding volume hierarchies can be used to accelerate both broad- and narrow-
phase processing. As a broad-phase method, BVHs are constructed to hold the objects
in a scene and to cull groups of distant objects (when the groups'bounding volumes
do not intersect the query object's bounding volume). As a narrow-phase method,
BVHs are constructed over the parts of an (often complex) object, allowing pairwise
tests to restrict primitive-primitive tests to those parts of the objects whose bounding
volumes overlap.
This chapter looked at desired characteristics for BVHs. It also explored three
classes of construction strategies for BVHs: top-down, bottom-up, and insertion-
based construction methods. For top-down methods it becomes important to perform
successive partitionings of objects into subgroups, and several partitioning strategies
were suggested. Three types of traversal methods were also explored: breadth-first,
depth-first, and best-first search orderings. When two BVHs are tested against each
other it is meaningful to consider in what order the subtrees are visited, and in this
regard several descent rules were stated.
The end of the chapter explored the efficiency of tree representations and traversals.
These topics are revisited in Chapter 13.
