Graphics Reference
In-Depth Information
5
4
3
2
B
D
F
1
A
C
E
AB
C
D
EF
Figure 7.8
A small 1D hierarchical grid. Six objects,
A
through
F
, have each been inserted in
the cell containing the object center point, on the appropriate grid level. The shaded cells are
those that must be tested when performing a collision check for object
C
.
hierarchy works well. Let the cells at level 1 just encompass the smallest objects. Then
successively double the cell size so that cells of level
k
+ 1 are twice as wide as cells
of level
k
. Repeat the doubling process until the highest-level cells are large enough
to encompass the largest objects. In general, this setup serves well to minimize the
number of cells an object overlaps. It is still possible to do better in specific instances,
however. For instance, if there are only two object sizes clearly two grid levels
suffice.
Testing whether an arbitrary object
A
is in collision with objects stored in the hgrid
is done by traversing through all hgrid levels. At each level,
A
is tested against not only
those grid cells its bounding volume overlaps but those neighboring cells that could
have objects extending into the cells that are overlapped (as discussed in Section
7.1.6). Note that it is not sufficient to check just the immediately neighboring cells to
the cell the object is in. A large object, when checked against the grid, would cover a
lot of cells at the lowest level and not just the immediate neighborhood.
If not just a single object, but all
n
objects are tested at the same time, testing does
not have to proceed over all hgrid levels. Instead, each object can start testing from
its insertion level. This follows, as smaller objects will test against the grid levels of
larger objects.
Overall, the hgrid structure is not much different from a tree structure, such as an
octree, implemented using arrays. However, one key feature that sets it apart from
the tree structures is the lack of a tree “top.” That is, the hgrid corresponds to just
the last few levels of the tree. The top levels of a tree rarely contain any objects and
are simply traversed just to reach the lower levels at which the objects reside. Hgrids
avoid these empty levels and gain extra speed in doing so.
To speed up the collision testing further, it is worthwhile keeping track of the total
number of objects on each grid level. Levels that contain no objects can then be
excluded from testing.
Hgrids can be very memory expensive when each grid level is allocated as a dense
array. For this reason they are best implemented using hashed storage, as described
in Section 7.1.3.
