Graphics Reference
In-Depth Information
7.1.3
Hashed Storage and Infinite Grids
Perhaps the most effective alternative to using a dense array to store the grid is to
map each cell into a hash table of a fixed set of
n
buckets (Figure 7.2). In this scheme,
the buckets contain the linked lists of objects. The grid itself is conceptual and does
not use any memory. An example of a simple multiplicative hash function, mapping
a tuple consisting of the cell position coordinates into a bucket index, follows.
// Cell position
struct Cell {
Cell(int32 px, int32 py, int32 pz){x=px;y=py;z=pz;}
int32 x, y, z;
};
#define NUM_BUCKETS 1024
// Computes hash bucket index in range [0, NUM_BUCKETS-1]
int32 ComputeHashBucketIndex(Cell cellPos)
{
const int32 h1 = 0x8da6b343; //
Large multiplicative constants;
const int32 h2 = 0xd8163841; //
here arbitrarily chosen primes
const int32 h3 = 0xcb1ab31f;
int32n=h1*cellPos.x + h2 * cellPos.y + h3 * cellPos.z;
n=n%NUM_BUCKETS;
if (n < 0) n += NUM_BUCKETS;
return n;
}
Note that it is surprisingly easy to construct hash functions that although perhaps
not bad, are just not very good (and there are no guarantees the previous hash
function is particularly strong). For information on constructing more sophisticated
hash functions see [Binstock96], [Jenkins97], or [Knuth98].
Performing a hash mapping of this type has the added benefit of allowing the grid
to be unbounded in size. The mapping function wraps world coordinates into a finite
number of cells (thereby making boundary checks for accessing neighboring cells
unnecessary). Although the world may consist of an infinite amount of cells, only a
finite number of them are overlapped by objects at a given time. Thus, the storage
required for a hashed grid is related to the number of objects and is independent of
the grid size.
To avoid having to perform a hash table lookup to find out that a cell is in fact
empty and is not in the table, a dense bit array with 1 bit per cell in the grid can be
used as a quick pretest indicator of whether a cell is empty or not. (Of course, this
optimization is only possible by keeping the grid fixed in size.)
