Graphics Reference
In-Depth Information
The smaller the ratio is, the fewer cells must be examined at a given level, on
average. However, it also means that the average number of objects per cell increases.
An appropriate ratio is application specific. When traversing from level to level, the
grid cell side increases by the following factor:
const float CELL_TO_CELL_RATIO = 2.0f; // Cells at next level are 2*side of current cell
Adding an object into the hgrid now can be done as follows.
void AddObjectToHGrid(HGrid *grid, Object *obj)
{
// Find lowest level where object fully fits inside cell, taking RATIO into account
int level;
float size = MIN_CELL_SIZE, diameter = 2.0f * obj- > radius;
for (level = 0; size * SPHERE_TO_CELL_RATIO < diameter; level++)
size *= CELL_TO_CELL_RATIO;
// Assert if object is larger than largest grid cell
assert(level < HGRID_MAX_LEVELS);
// Add object to grid square, and remember cell and level numbers,
// treating level as a third dimension coordinate
Cell cellPos((int)(obj->pos.x / size), (int)(obj->pos.y / size), level);
int bucket = ComputeHashBucketIndex(cellPos);
obj->bucket= bucket;
obj->level = level;
obj- > pNextObject = grid- > objectBucket[bucket];
grid- > objectBucket[bucket] = obj;
// Mark this level as having one more object. Also indicate level is in use
grid- > objectsAtLevel[level]++;
grid- > occupiedLevelsMask |= (1 << level);
}
Removing an object from the hgrid is done in a corresponding manner.
void RemoveObjectFromHGrid(HGrid *grid, Object *obj)
{
// One less object on this grid level. Mark level as unused if no objects left
if (--grid->objectsAtLevel[obj->level] == 0)
grid->occupiedLevelsMask &=
∼(1 << obj->level);
 
Search WWH ::




Custom Search