Graphics Reference
In-Depth Information
const int32 MAX_OBJECT_PAIRS = MAX_OBJECTS * (MAX_OBJECTS - 1) / 2;
int32 bitflags[(MAX_OBJECT_PAIRS + 31) / 32];
...
void TestObjectPair(int32 index0, int32 index1)
{
assert(index0 != index1);
// Find which object index is smaller and which is larger
int32 min = index0, max = index1;
if (index1 < index0) {
min = index1;
max = index0;
}
// Compute index of bit representing the object pair in the array
int32 bitindex = min * (2 * MAX_OBJECTS - min - 3)/2+max-1;
// Look up the corresponding bit in the appropriate word
int32 mask = 1L << (bitindex & 31);
if ((bitflags[bitindex >> 5] & mask) == 0) {
// Bit not set, so pair has not already been processed;
// process object pair for intersection now
...
// Finally mark object pair as processed
bitflags[bitindex >> 5] |= mask;
}
}
Although this works well for object-object testing, it is less than ideal in the ray-
shooting case. In the object-object scenario, the array of bit flags would have to be
reset once per frame, which is not too bad. For ray shooting, however, the array
would have to be reset for each ray tested! In a typical game there might be tens
or hundreds of ray-like tests performed each frame. Even for a modest number of
objects, this operation now quickly becomes very expensive.
7.7.2
Time Stamping
An alternative way of keeping track of already-tested objects that works better for
the ray-shooting scenario is to keep a running counter that increments for each ray
query and assign the counter number, commonly referred to as a
time stamp
, to each
object after it has been tested. Then, just before an object is to be tested the time
stamp is checked to see if the object has already been tested in the current frame and
can therefore be ignored.
Figure 7.23 illustrates how time stamping works. First, consider the interaction with
object
A
only. In cell 1, the ray is tested against
A
. Because there is no intersection
