Graphics Reference
In-Depth Information
In that this test relies on knowing which pairs to test, pair information has to be
tracked separately. Whenever an object
A
is stored in a grid cell containing another
object
B
, a counter corresponding to the pair (
A
,
B
) is incremented, and the pair
is added to the tracking data structure. When either object moves out of one of
their common cells, the counter is decremented. When the counter reaches zero, the
pair is removed from the tracking data structure because they are no longer close.
Only pairs in the tracking data structure undergo narrow-phase collision detection
checking. The cost of moving an object is now much larger, but thanks to spa-
tial coherence the larger grid cells have to be updated only infrequently. Overall,
this scheme trades the cost of updating cells for the benefit of having to test fewer
grid cells.
7.2.3
Other Hierarchical Grids
As presented, a drawback with the hierarchical grid is that it is not very appropriate
for handling world geometry, which often consists of large amounts of unevenly
distributed small static data. Representing the lowest-level grid as a dense grid will
be extremely expensive is terms of storage. Similarly, a sparse representation using
hashing is likely to cause slowdown when a large number of cells is intersected due to
cache misses and the extra calculations involved. For this particular type of problem,
other types of hierarchical grids are more suited. Many of these have their origins in
ray tracing.
Of these, the most straightforward alternative is the
recursive grid
[Jevans89]. Here,
a uniform grid is constructed over the initial set of primitives. For each grid cell
containing more than some
k
primitives, a new, finer, uniform grid is recursively
constructed for that cell. The process is stopped when a cell contains less than some
m
objects or when the depth is greater than
n
(usually 2 or 3). Compared to the
original hgrid, the lowest-level grids no longer span the world and they will require
less memory for a dense grid representation.
Two other grid alternatives are
hierarchy of uniform grids
[Cazals95] and
adaptive
grids
[Klimaszewski97]. Both of these use object clustering methods to identify groups
of primitives that should be contained within their own subgrids inside a larger
uniform grid. More information and a thorough comparison of these two and other
methods can be found in [Havran99].
7.3
Trees
Trees were discussed in the previous chapter in the context of bounding volume
hierarchies. Trees also form good representations for spatial partitioning. This section
explores two tree approaches to spatial partitioning: the octree and the
k
-d tree.
