Graphics Reference
In-Depth Information
When, as here, a callback is used to call a function to handle two colliding objects
it is important that the callback function not change the hgrid data structure itself.
Because
CheckObjAgainstGrid()
is in the middle of operating on the data structure,
such changes would cause reentrancy problems, leading to missed collisions at best
and crashes at worst.
7.2.2
Alternative Hierarchical Grid Representations
Even though the hgrid is a great improvement over the basic nonhierarchical grid, a
problem remains. When objects are tested one at a time, a large object could cover a
lot of cells on the lowest levels, making for an expensive test in that it is intersected
against the contents of all of these cells. Two hgrid schemes that address this problem
are given in [Mirtich96b, Mirtich97], by whom the hgrid is referred to as a
hierarchical
spatial hash table
.
The first scheme is to insert the objects in order of decreasing size, such that all
objects going into grid level
k
are inserted before those that go into level
k
1. With
this restriction, the newly inserted object has to be tested only against cells on the
level at which it is being inserted and against cells on higher levels. Lower levels
do not have to be tested because they are by order of insertion empty. To handle
the dynamic addition and deletion of objects, a separate data structure would be
necessary to maintain the sorted insertion and testing order of existing objects. An
example of this scheme is shown in Figure 7.9.
For the second scheme, objects are no longer inserted in a single cell on just one
level. Instead, the object is inserted in
all
cells it overlaps, starting at the lowest
grid level at which the cells are large enough to contain the object, repeating for all
overlapped grid cells of higher-level grids.
In the second scheme, given a pair (
A
,
B
) of objects in the grid, determining if
they overlap can now be done by testing if they share a common cell at level
L
−
=
max(
Level
(
A
),
Level
(
B
)). In other words, the test is if they overlap on the larger of the
two initial insertion levels for the objects. No other levels have to be tested.
5
4
3
2
B
B
D
F
1
A
A
CC
EE
AB
C
D
EF
Figure 7.9
In Mirtich's (first) scheme, objects are inserted in all cells overlapped at the
insertion level. As in Figure 7.8, the shaded cells indicate which cells must be tested when
performing a collision check for object
C
.
