Graphics Reference
In-Depth Information
A
B
(a)
(b)
Figure 7.7
(a) In a regular grid, grid cell
A
has eight neighbors. (b) In a hexagonal-type grid,
grid cell
B
has just six neighbors.
7.2
Hierarchical Grids
The most significant problem with uniform grids is their inability to deal with objects
of greatly varying sizes in a graceful way. When objects are much larger than the grid
cell size and end up overlapping many cells, updating the position of a moving object
becomes very expensive. If the cell size is adjusted to hold the larger objects, the grid
becomes less spatially discriminatory as more small objects now end up in the same
cell, with loss of performance as a result. Fortunately, this size problem can effectively
be addressed by the use of
hierarchical grids
(or
hgrids
), a grid structure particularly
well suited to holding dynamically moving objects.
The hierarchical grid, as described here, consists of a number of grids of vary-
ing cell sizes, all overlapping to cover the same space. Depending on use, these
grids can be either 2D or 3D. Given a hierarchy containing
n
levels of grids and let-
ting
r
k
represent the size of the grid cells at level
k
in the hierarchy, the grids are
arranged in increasing cell size order, with
r
1
r
n
. Level 1 is the low-
est level, and level
n
is the highest level. The number of levels does not have to
be fixed.
To facilitate fast insert and delete operations, objects are inserted into a single
cell on just one of the levels. As the objects can still extend into other cells on that
level, to minimize the number of neighboring cells that have to be tested for colli-
sions objects are inserted into the hgrid at the level where the cells are large enough
to contain the bounding volume of the object. Given an object
P
, this level
L
is
denoted
L
<
r
2
<
...
<
Level
(
P
). This way, the object is guaranteed to overlap at most four
cells (or eight, for a 3D grid). At this point, the object is inserted into the cell in
which its center (based on the object bounding sphere) or top left-hand position
(based on the object AABB) is in. An example of an hgrid of this type is shown in
Figure 7.8.
The grid cells can assume any relative size and should ideally be selected with
respect to existing object sizes. In practice, a simple procedure for setting up the
=
