Graphics Reference
In-Depth Information
A third solution is to use the open hashing method but exclude the first-level
linked list and have the buckets directly contain a list of objects. This results in very
simple code with low overhead, but the lack of a stored key introduces two problems
that must be addressed. First, when performing tests against the content of a specific
cell it is now possible its bucket will contain both objects of interest as well as those
from other cells, which happened to map to the same bucket. To avoid spending time
peforming expensive narrow-phase tests on distant objects, in-depth tests must be
preceded by a bounding volume test to cull irrelevant objects. Such culling is a good
overall strategy anyway, in that nonoverlapping objects can share buckets regardless
of hash table representation.
Second, a related problem occurs when several cells are tested by the same query.
If two or more of the cells have been aliased to the same nonempty hash bucket, its
content will be checked several times for the same query. Fortunately, this seemingly
serious problem is easily solved by a time-stamping method in which hash buckets
are labeled each time they are queried. The label consists of a unique identifier that
changes for each query made. During a query, if a hash bucket is found labeled with
the current identifier the bucket has already been examined and can be ignored. Time
stamping is further described in Section 7.7.2.
A different approach to extending a grid when an object moves out of the region
covered by the grid is described in [Reinhard00]. Separating the grid into both logical
and physical parts, the logical grid is allowed to grow as the object moves outside the
grid. However, the extra cells thus introduced are mapped onto the existing physical
grid through a toroidal wrapping of logical cell coordinates modulo the size of the
physical grid. The size of the logical grid now determines whether an object near
the physical grid boundary must consider collisions against objects in its toroidal
neighbor cells on the opposite side of the grid.
7.1.4
Storing Static Data
When grid data is static, such as when it represents world polygon data instead of
dynamic objects, the need for a linked list can be removed altogether [Haines99].
Rather than storing the data in linked lists, the idea is to store all cell data in a single
contiguous array. Figure 7.3 illustrates the same grid with the data stored using linked
lists (a) and into an array (b).
The grid data can be assigned to an array in a two-pass process. In the first pass,
the static data is iterated over, but instead of assigning the data to overlapped grid
cells only a counter per cell is incremented when data would normally have been
assigned to the cell. After all data is processed, counts have thereby been obtained
for all
n
grid cells, with
a
k
indicating the number of objects in cell
C
k
. At this point an
array of
m
elements
m
=
a
i
0
≤
i
<
n
