Graphics Reference
In-Depth Information
intersection of each of the four grid cells (
r
i
,
c
j
), (
r
i
,
c
j
+
1
), (
r
i
+
1
,
c
j
), and (
r
i
+
1
,
c
j
+
1
). If
r[i]
and
c[j]
correspond to the bit masks of row cell
i
and column cell
j
, respectively,
this method gives the resulting union
b
of bits as
b = (r[i] & c[j]) | (r[i] & c[j+1]) | (r[i+1] & c[j]) | (r[i+1] & c[j+1]);
However, the distributive properties of the bitwise operators allow this expression
to be more efficiently computed as
b = (r[i] | r[i+1]) & (c[j] | c[j+1]);
This rewrite generalizes to an arbitrary number of cells overlapped, so that the
bitwise OR of all overlapped row cells and of all column cells is first computed. Then
the bitwise AND between the resulting bit fields gives the final result. This method
is illustrated by the following code.
// Define the two global bit arrays
const int NUM_OBJECTS_DIV_32 = (NUM_OBJECTS + 31) / 32;
// Round up
int32 rowBitArray[GRID_HEIGHT][NUM_OBJECTS_DIV_32];
int32 columnBitArray[GRID_WIDTH][NUM_OBJECTS_DIV_32];
void TestObjectAgainstGrid(Object *pObject)
{
// Allocate temporary bit arrays for all objects and clear them
int32 mergedRowArray[NUM_OBJECTS_DIV_32];
int32 mergedColumnArray[NUM_OBJECTS_DIV_32];
memset(mergedRowArray, 0, NUM_OBJECTS_DIV_32 * sizeof(int32));
memset(mergedColumnArray, 0, NUM_OBJECTS_DIV_32 * sizeof(int32));
// Compute the extent of grid cells the bounding sphere of A overlaps.
// Test assumes objects have been inserted in all rows/columns overlapped
float ooCellWidth = 1.0f / CELL_WIDTH;
int x1 = (int)floorf((pObject-
>
x - pObject-
>
radius) * ooCellWidth);
int x2 = (int)floorf((pObject-
>
x + pObject-
>
radius) * ooCellWidth);
int y1 = (int)floorf((pObject-
>
y - pObject-
>
radius) * ooCellWidth);
int y2 = (int)floorf((pObject-
>
y + pObject-
>
radius) * ooCellWidth);
assert(x1 >= 0 && y1 >= 0 && x2 < GRID_WIDTH && y2 < GRID_HEIGHT);
// Compute the merged (bitwise-or'ed) bit array of all overlapped grid rows.
// Ditto for all overlapped grid columns
for (int y = y1; y <= y2; y++)
