Graphics Reference
In-Depth Information
int ObjectCollidingCachePrims(Object a, Object b)
{
if (BVOverlap(a, b)) {
if (IsLeaf(a) && IsLeaf(b)) {
if (CollidePrimitives(a, b)) {
// When two objects are found colliding, add the pair
// along with the witness primitives to the shared cache
AddObjectPairToCache(a, b);
return COLLIDING;
} else return NOT_COLLIDING;
} else {
...
}
}
...
}
[Rundberg99] goes further than just testing the cached primitives. When the
cached primitives do not overlap, he argues there is a chance that their neigh-
boring primitives might be in collision and proceeds to test primitives around the
cached primitives before eventually giving up and testing from the root. This of
course assumes a representation in which neighboring primitives are easily acces-
sible. Rundberg reports an average speedup of 1.1 to 2.0, with no slowdowns.
6.7.2
Front Tracking
A number of node-node comparisons are made when two object hierarchies are
tested against each other. These node pairs can be seen as forming the nodes of a
tree, the
collision tree
. For informed and alternating descent rules, the collision tree is
binary; for the simultaneous descent rule, it is a 4-ary tree.
When the two objects are not colliding, as tree traversal stops when a node-node
pair is not overlapping, all internal nodes of the collision tree correspond to colliding
node-node pairs, and the leaves are the node-node pairs where noncollision was first
determined.
Consequently, the collection of these leaf nodes, forming what is known as
the
front
of the tree, serves as witness to the disjointedness of the two objects
(Figure 6.9).
As objects typically move smoothly with respect to each other, this front can for
the most part be expected to stay the same or just change locally. Therefore, instead of
repeatedly building and traversing the collision tree from the root, this coherence can
be utilized by keeping track of and reusing the front between queries, incrementally
updating only the portions that change, if any.
