Spatial Partitioning - Real-Time Collision Detection - page 333

pSentinel->max.pLeft[i] = &pSentinel->min;
pSentinel- > max.pRight[i] = NULL;

// not strictly needed

pSentinel- > min.value[i] = -FLT_MAX;
pSentinel- > max.value[i] = FLT_MAX;
gListHead[i] = &pSentinel- > min;

}
// Note backwardness of initializing these two
pSentinel- > min.minmax = MAX_ELEM;
pSentinel- > max.minmax = MIN_ELEM;

Inserting a new AABB into the sorted lists is done by scanning the lists for the
appropriate insertion point. To simplify the presentation here, the overlap pair sta-
tus is calculated in a separate pass after the new AABB has been inserted. To make
the code more efficient, the overlap pair status could be updated at the same time
objects are inserted by interleaving the routines. (Note that it is not possible to deter-
mine all overlapping pairs just by examining the Elem structs between the min and
max element. The latter test would miss overlap with a larger AABB, completely
encompassing the new AABB.)
To keep track of which collisions are active, the following code assumes the
existence of two functions AddCollisionPair() and DeleteCollisionPair() that
register and unregister, respectively, a pair of objects as being colliding.

void InsertAABBIntoList(AABB *pAABB)
{

// For all three axes
for(inti=0;i<3;i++) {
// Search from start of list
Elem *pElem = gListHead[i];

// Insert min cell at position where pElem points to first larger element.
// Assumes large sentinel value guards from falling off end of list
while (pElem- > value[i] < pAABB- > min.value[i])
pElem = pElem- > pRight[i];
pAABB- > min.pLeft[i] = pElem- > pLeft[i];
pAABB- > min.pRight[i] = pElem;
pElem- > pLeft[i]- > pRight[i] = &pAABB- > min;
pElem- > pLeft[i] = &pAABB- > min;

// Insert max cell in the same way. Can continue searching from last
// position as list is sorted. Also assumes sentinel value present
while (pElem->value[i] < pAABB->max.value[i])
pElem = pElem->pRight[i];