Graphics Reference
In-Depth Information
Table 7.1
Memory use (in bytes) for three different grid representations: implicit grid (with bit arrays),
dense array (with double-linked list), and a sparse array (with double-linked list).
Grid size (
m
×
n
)
10
×
10
50
×
50
100
×
100
500
×
500
10
40
200
400
2,000
100
260
1,300
2,600
13,000
Implicit grid (bit arrays):
bytes
=
objects
/8
(
m
+
n
)
1,000
2,500
12,500
25,000
125,000
10,000
25,000
125,000
250,000
1,250,000
10
480
10,080
40,080
1,000,080
100
1,200
10,800
40,800
1,000,800
Dense array (double-linked list):
bytes
=
4
mn
+
objects
·
(
4
+
4
)
1,000
8,400
18,000
48,000
1,008,000
10,000
80,400
90,000
120,000
1,080,000
10
240
560
960
4,160
100
1,680
2,000
2,400
5,600
Sparse array (double-linked list):
bytes
=
4(
m
+
n
)
+
objects
·
(
4
·
2
+
4
·
2
)
1,000
16,080
16,400
16,800
20,000
10,000
160,080
160,400
160,800
164,000
object-object tests. Should objects be placed in just one representative cell or all cells
they overlap? If just one cell, what object feature should be used to determine which
cell the object goes into? The next two sections look at these issues in the context of
how the test queries are issued: if they are issued one at a time (allowing objects to
move between successive tests) or if they are all issued simultaneously.
7.1.6.1 One Test at a Time
Consider the case in which objects are associated with a single cell only. When a given
object is associated with its cell, in addition to testing against the objects associated
with that cell additional neighboring cells must also be tested. Which cells have to
be tested depends on how objects can overlap into other cells and what feature has
been used to associate an object with its cell. The choice of feature generally stands
between the object bounding sphere center and the minimum (top leftmost) corner
of the axis-aligned bounding box.
If objects have been placed with respect to their centers, any object in the neighbor-
ing cells could overlap a cell boundary of this cell and be in collision with the current
