Graphics Reference
In-Depth Information
There are two possible cache organizations for holding the stored primitives: a
shared or a distributed cache. A shared cache is a global cache that contains any
number of pair entries. A distributed cache is a local cache wherein the primitives are
stored within the objects themselves.
A shared cache is typically implemented as a hash table wherein the colliding
primitives are registered under a key constructed from the two object IDs (such as
their pointer addresses). The benefit with a shared cache is that the system easily
handles an object being involved in any number of collisions. Drawbacks include the
cost of performing a hash table lookup to see if there is a pair, and having to remove
the pair when the objects are no longer in collision. The latter can be a quite difficult
problem, and is typically handled using a lazy updating scheme in which the pair is
deleted only when a subsequent query fails. Unfortunately, this solution keeps dead
pairs in the cache for longer than necessary, filling the cache and potentially causing
degenerate behavior.
The benefit of a distributed cache is that cached primitives are instantly available.
However, if only a single primitive is cached per object the contact with multiple
objects will cause the cache to be prematurely flushed, rendering it useless. For
instance, assume there are three objects in a row:
A
,
B
, and
C
.
A
is in contact with
B
,
which in turn is in contact with
C
. When
A
and
B
are first tested, a witness primitive
from
A
is stored in
A
, and a witness primitive from
B
in
B
. Then
B
is tested against
C
,
and a different witness primitive from
B
is stored in
B
, flushing the previously stored
primitive. When
A
and
B
are tested again, the two cached primitives do not collide
and a full collision pass has to be performed [Rundberg99].
This problem can be addressed by increasing the number of primitives that can be
cached within an object. However, by allowing
n
primitives to be cached, up to
n
2
tests will now have to be performed to determine if the objects are colliding. As such,
n
is limited to about two to six primitives for practical reasons. A shared or global
collision cache could be implemented as in the following code fragment.
int ObjectsCollidingWithCache(Object a, Object b)
{
// Check to see if this pair of objects is already in cache
pair = FindObjectPairInCache(a, b);
if (pair != NULL) {
// Is so, see if the cached primitives overlap; if not,
// lazily delete the pair from the collision cache
if (PrimitivesOverlapping(pair-
>
objAPrimitives, pair-
>
ObjBPrimitives))
return COLLIDING;
else DeleteObjectPairFromCache(a, b);
}
// Do a full collision query, that caches the result
return ObjectCollidingCachePrims(Object a, Object b);
}
