Graphics Reference
In-Depth Information
It is interesting to compare the number of operations involved in the various types
of traversals. As it would take two additional recursive calls for the previous meth-
ods to examine the same four node-node pairs the simultaneous traversal descends
into, simultaneous traversal can be expected to require about two-thirds the work of
the directed methods (which is strictly true only in the case in which all nodes are
visited).
Specifically, consider the worst-case scenario in which two complete binary trees
of
n
levels each are in a relative position such that all bounding volume leaves are
overlapping but there is no collision. For this case it can be shown that a simultaneous
traversal will perform (2
2(
n
−
1)
1)/3 internal node-node tests and 2
2(
n
−
1)
leaf-node,
node-leaf, and leaf-leaf tests, totaling (2
2
n
−
1)/3 tests.
In comparison, the leaf-directed “descend
A
” and “descend
B
” rules perform
2
n
−
1
−
1 internal node-node tests and (2
n
1)2
n
−
1
leaf-node, node-leaf, and leaf-leaf
−
−
tests for a total of 2
2
n
−
1
1 tests. The limit as
n
gets large between these two totals
verifies the two-thirds ratio informally stated previously.
It is more difficult to provide any specific numbers for the informed traversal
method, as the traversal pattern is completely dependent on the descent rule used.
One thing that can be said for sure is that the total number of tests performed will be
the same as for the leaf-directed traversals, as the code has the same structure and all
possible traversal paths are formed. It is difficult to say whether using a simultaneous
traversal saves anything over using a directed method such as “descend larger,”
which performs a more effective search by guiding it to where it is best needed.
−
6.3.4
Optimized Leaf-direct Depth-first Traversal
A drawback with simultaneous and heuristically guided methods is that collision tests
involving the same leaves are likely to be spread out over time. If these tests involve
some sort of transformation of the leaf data or the leaf bounding volumes (as is likely),
these transformations have to be repeated each time the leaf is involved in a query.
If these transformations are expensive, a caching mechanism can be implemented to
hold the data after it has been initially transformed.
A compromise alternative to implementing a sophisticated caching scheme is the
“descend
A
”rule. By traversing down to the leaves of hierarchy
A
before hierarchy
B
is descended into, it becomes very easy to transform the leaves of
A
just once. This
compromise does not serve as a full replacement for a caching mechanism, as only
the
A
hierarchy will effectively be cached this way. However, as it is so simple to
implement it can serve as an indication of how much of an improvement a caching
scheme would actually bring. A code fragment follows.
// This routine recurses over the first hierarchy, into its leaves.
// The leaves are transformed once, and then passed off along with
// second hierarchy to a support routine
