Graphics Reference
In-Depth Information
7.7
Avoiding Retesting
A potential concern with partitioning schemes in which a single object may overlap
multiple partitions is that the same two objects can be subject to testing against each
other multiple times. This is clearly a problem when the pairwise test is expensive. If
not handled correctly, it could also lead to collision-resolution code being run for the
objects more than once. A similar problem occurs in ray-tracing applications, wherein
shooting a ray through a uniform grid can result in the ray being tested multiple times
against the same object located in several grid cells. In both cases, it would be wasteful
to perform the same tests multiple times because the same objects are encountered
again. Depending on the situation, a few alternative solutions are available.
7.7.1
Bit Flags
A straightforward solution to the retesting problem is to use a bit flag for indicating
whether an intersection test has already been performed. In the case of shooting rays
through a grid, there would be one bit per object. For object-object intersection tests,
there would be a bit for every pair of objects. If the bit is set, the object (or pair of
objects) in question has already been tested and any further testing can be skipped.
If the bit is not set, the full test must be performed, after which the bit would be set
to indicate the completion of the test.
In the object-object case, the bit flags are easily stored in an array indexed by the
two object indices. In that the array entries (
a
,
b
) and (
b
,
a
) would represent the same
pair, to avoid wasting memory only the upper triangular half above the diagonal
would actually have to be stored. With a maximum of
n
objects, the array would then
only have to hold
n
(
n
−
1)/2 bits instead of
n
2
bits. Given two object indices
a
and
b
,
with
a
<
b
, the index of the corresponding bit is now computed as
3)
2
bitindex
=
a
(2
n
−
a
−
+
b
−
1
instead of
bitindex
=
an
+
b
.
The following code illustrates a possible implementation of a bit flag array for object-
object intersection testing.
// Allocate enough words to hold a bit flag for each object pair
const int32 MAX_OBJECTS = 1000;
