Graphics Reference
In-Depth Information
7.2.1
Basic Hgrid Implementation
This section outlines a simple and straightforward implementation of an hgrid. The
hash table approach used is open hashing without the use of keys. Consequently, both
bounding volume tests as well as time stamping (Section 7.7.2) must be used to avoid
processing irrelevant and already processed data. The hgrid is assumed to have the
following minimal structure:
struct HGrid {
uint32 occupiedLevelsMask;
// Initially zero (Implies max 32 hgrid levels)
int objectsAtLevel[HGRID_MAX_LEVELS];
// Initially all zero
Object *objectBucket[NUM_BUCKETS];
// Initially all NULL
int timeStamp[NUM_BUCKETS];
// Initially all zero
int tick;
};
It is assumed that objects are inserted into the hgrid based on their bounding
spheres. For the sake of simplicity, the given code links objects within a bucket using
single-linked lists, with the list pointer embedded in the object. Use of a double-
linked list would allow removal in
O
(1) time, instead of
O
(
n
) time. Associating each
hgrid cell with an array (of object pointers) also allows removal in
O
(1) time. The latter
option requires some bookkeeping to handle the arrays overflowing, but is overall
a faster and more cache-friendly option. Let the object representation contain the
following variables.
struct Object {
Object *pNextObject;
// Embedded link to next hgrid object
Point pos;
// x, y (and z) position for sphere (or top left AABB corner)
float radius;
// Radius for bounding sphere (or width of AABB)
int bucket;
// Index of hash bucket object is in
int level;
// Grid level for the object
...
// Object data
};
Cells are here assumed to be square (cubical for a 3D hgrid). The ratio of the
diameter of the largest sphere that goes into a cell at a particular level with respect to
the cell side size is given by:
const float SPHERE_TO_CELL_RATIO = 1.0f/4.0f;
// Largest sphere in cell is 1/4*cell size
