Graphics Reference
In-Depth Information
C
C
E
D
C
E
D
B
D
B
A
A
D
D
E
E
B
A
C
Figure 7.4 A4× 5 grid implicitly defined as the intersection of 9 (4 + 5) linked lists. Five
objects have been inserted into the lists and their implied positions in the grid are indicated.
4
11000
3
1
01010
00100
2
0
00101
10000 00010 00110 00101 01001
Figure 7.5 A4
5) bit arrays. Five
objects have been inserted into the grid. The bit position numbers of the bits set in a bit array
indicate that the corresponding object is present in that row or column of the grid.
×
5 grid implicitly defined as the intersection of 9 (4
+
A more novel storage approach is to allocate, for each row and column of the grid,
a bit array with 1 bit for each object in the world. Placing an object into the grid now
simply involves setting the bit in the bit array in both the row and column bit arrays
for the grid cell corresponding to the object (Figure 7.5).
An object exists in a grid cell if and only if the bit arrays of the row and column of
the cell both have the bit corresponding to that object set. Testing for the presence of
objects in a cell is therefore as simple as performing a bitwise AND operation on the
two bit arrays.
When the query object overlaps several grid cells, the distributive properties of
bitwise operators can be used to reduce the amount of computation needed. For
example, assume an object overlaps rows r i and r i + 1 and columns c j and c j + 1 . The
objects potentially intersected are given by the union of all bits set in the bitwise
 
Search WWH ::




Custom Search