Graphics Reference
In-Depth Information
Descend A before B is descended. Fully descending into the leaves of A before
starting to descend into B can be quite bad. In terms of the example, if the bird
is somewhere in the middle of the oil refinery the leaves of the bird hierarchy will
all overlap the top volume of the refinery. This descent rule is the worst possible
choice, as hierarchy B will be recursed over as many times as there are leaves in
hierarchy A . The hierarchy for A is clearly counterproductive here, resulting in
more work than not having a hierarchy at all!
Descend B before A is descended. Descending the larger refinery hierarchy before
descending the hierarchy of the bird is slightly better. However, the refinery
model could still contain many parts (such as nuts and bolts) quite a bit smaller
than the bird, resulting in a similar situation as before, only reversed. Many
leaves of B still end up being tested against the whole of A .
Descend the larger volume. By dynamically determining which hierarchy is cur-
rently the larger one and descending into it, the problems with the two previous
methods are circumvented. Initially, the refinery hierarchy is descended into, but
when the small nuts and bolts parts are encountered the traversal switches over
to descend the bird hierarchy, then back again when the bird parts become
smaller than the nuts and bolts. This is one of the most effective descent rules in
that it provides the largest reduction of total volume for subsequent bounding
volume tests. As before, useful metrics for the size comparison include volume,
surface area, and the maximum dimension length.
Descend A and B simultaneously. Instead of just descending one hierarchy, both
hierarchies can be descended into at the same time. Simultaneous descent has
the benefit of more quickly traversing to the leaves, making fewer internal node-
node (as well as node-leaf) overlap tests and involving no evaluation overhead
for the descent criterion. However, in the bird-refinery example this rule will
not prune the search space as effectively as the previous rule.
Descend A and B alternatingly. The hierarchies can also be descended into in a
lock-step fashion, in which first A is descended into, then B , then A again, and so
on. This descent rule is very simple to implement, and just as with simultaneous
traversal no descent criterion need be evaluated.
Descend based on overlap. Another option is to prioritize descent to those parts
in which the hierarchies overlap more before descending parts in which there is
less overlap. The idea is that the more two bounding volumes overlap the more
likely their objects are colliding.
Combinations of the previous or other complex rules based on traversal history.
Which type of traversal is most effective depends entirely on the structure of the
data, as indicated by the refinery example. The following sections explore framework
implementations for the previous rules based on depth-first traversal. For very large
Search WWH ::




Custom Search