Graphics Reference
In-Depth Information
for(inti=0;i<NUM_OBJECTS_DIV_32; i++)
mergedRowArray[i] |= rowBitArray[y][i];
for (int x = x1; x <= x2; x++)
for(inti=0;i<NUM_OBJECTS_DIV_32; i++)
mergedColumnArray[i] |= columnBitArray[x][i];
// Now go through the intersection of the merged bit arrays and collision test
// those objects having their corresponding bit set
for(inti=0;i<NUM_OBJECTS_DIV_32; i++) {
int32 objectsMask = mergedRowArray[i] & mergedColumnArray[i];
while (objectsMask) {
// Clears all but lowest bit set (eg. 01101010 -> 00000010)
int32 objectMask = objectsMask & (objectsMask - 1);
// Get index number of set bit, test against corresponding object
// (GetBitIndex(v) returns log_2(v), i.e. n such that 2
∧
n=v)
int32 objectIndex = GetBitIndex(objectMask)+i*32;
TestCollisionAgainstObjectNumberN(objectIndex);
// Mask out tested object, and continue with any remaining objects
objectsMask
∧
= objectMask;
}
}
}
A simplified version of implicit grids using bit arrays can be used as a coarse
broad-phase rejection method. Instead of having a bit array indicating exactly what
objects are in each row and column of the grid, a single bit can be used to indi-
cate the presence of an object in a row or column. If no bit is set for the rows and
columns an object overlaps, the object cannot be in overlap and no further testing is
necessary.
Table 7.1 illustrates memory use for three different grid representations: the implicit
grid using bit arrays, a dense array (with double-linked lists), and a sparse array (also
using double-linked lists). Up to roughly 1,000 objects and a grid size of 100
100,
the implicit bit grid uses less memory than the other two representations. The implicit
bit grid also uses memory in a cache-friendly way and is overall a very efficient spatial
partitioning method.
×
7.1.6
Uniform Grid Object-Object Test
As mentioned earlier, grid cell sizes are usually constrained to be larger than the
largest object. This way, an object is guaranteed to overlap at most the immediately
neighboring cells, thereby greatly simplifying the overlap testing code. Still, a few
key issues remain when it comes to assigning objects to cells and performing the
