Graphics Reference
In-Depth Information
G
F
C
A
H
B
G
F
C
A
H
B
I
E
D
I
E
D
(a)
(b)
Figure 7.3
(a) A grid storing static data as lists. (b) The same grid with the static data stored
into an array.
is allocated. Each cell is also associated with an index number
b
k
into this array,
where
b
0
=
0
b
k
=
b
k
−
1
+
a
k
−
1
.
The data is then in a second pass iterated over again. This time, the
a
k
objects over-
lapping cell
C
k
are stored with help from the associated index number into the array
at indices
b
k
through
b
k
+
1. Because all data for each cell is stored contigu-
ously in the array, and because no links are needed between the contiguous entries,
the resulting array-based grid uses less memory and is more cache efficient than a
representation based on linked lists.
a
k
−
7.1.5
Implicit Grids
An alternative to storing a grid explicitly is to store it implicitly, as the Cartesian
product of two or more arrays. That is, the grid is now represented by two arrays
(three in 3D), wherein one array corresponds to the grid rows and the other to the
grid columns. As before, each array element points to a linked list of objects. An object
is inserted into the grid by adding it to the lists of the grid cells it overlaps, for both the
row and column array (Figure 7.4). Overlap testing for an object is now performed
by checking to see if the object overlaps another object in
both
the row cells and the
column cells it straddles.
Compared to the dense array representation, this scheme can result in either fewer
or more list insertions. If the object is fully contained within a single grid cell of the
implicit grid, it is inserted into two lists (one row and one column list), whereas in
the previous scheme it would have been inserted in just one list. However, if the
object were to overlap, say, 4
4 grid cells, it would be inserted into eight lists for
the implicit grid (four row lists and four column lists) instead of 16, improving on the
worst case. When objects overlap few cells the overlap test for this approach becomes
more costly, not only because there are more objects in the lists that are being tested
but because (many) more lists have to be checked.
×
