Bounding Volume Hierarchies - Real-Time Collision Detection - page 254

(a) (b) (c)

Figure 6.4 (a) Breadth-first search, (b) depth-first search, and (c) one possible best-first search
ordering.

considered uninformed or blind search methods. Uninformed search methods do not
examine and make traversal decisions based on the data contained in the traversed
structure; they only look at the structure itself to determine what nodes to visit next.
In contrast to the uninformed methods is the group of informed search methods.
These attempt to utilize known information about the domain being searched through
heuristic rules. One such method is best-first search (Figure 6.4c). Best-first search is
a greedy algorithm that always moves to the node that scores best on some search
criterion (for example, distance to a set goal). It determines the best-scoring move
by maintaining a priority queue of nodes, expanding the currently best node (first on
the queue) and adding its children to the queue, repeating until the search fails (by
running out of nodes) or the goal is found.
DFS seems to be the most popular choice for collision detection systems. DFS is
often enhanced by a simple heuristic to guide the search along, improving on the
basic blind DFS approach without the overhead of, say, a full best-first search.
Compared to DFS, BFS suffers from the fact that stacking all nodes during traversal
requires a substantial amount of memory. For close-proximity queries, two binary
trees with n leaves each can require stack space for as many as n 2 node-node pairs at
one time. BFS is primarily used in interruptible collision detection systems for which
it is important that if (or when) a query is interrupted a roughly equal amount of time
has been spent in all parts of the hierarchy.
Similarly, BFS must be well tuned to give performance improvements over a
heuristic-guided DFS-based traversal method. Any extra time spent on performing
clever node reordering and managing a priority queue is time the depth-first method
has already had in descending into child nodes.

6.3.1 Descent Rules

Returning to the issue of how the hierarchies are descended, given two hierarchies A
and B there are several possible traversal alternatives. For instance, one can be fully
traversed before the other, or they can be descended simultaneously. As an illustrative
example (due to [Chung98]), consider a bird (hierarchy A ) weaving through the mile-
long pipes of an oil refinery (hierarchy B ). Several possible descent rules present
themselves.