Spatial Partitioning - Real-Time Collision Detection - page 335

// Similarly to above, try to move max element to the right
for (t = pMax- > pRight[i]; pMax- > value[i] > t- > value[i];t=t- > pRight[i])
if (t- > minmax == MIN_ELEM)
if (AABBOverlap(pAABB, GetAABB(t)))
if (!HasCollisionPair(pAABB, GetAABB(t)))
AddCollisionPair(pAABB, GetAABB(t));
if (t != pMax->pRight[i])
MoveElement(i, pMax, t->pLeft[i]);
// Similarly to above, try to move min element to the right
for (t = pMin- > pRight[i]; pMin- > value[i] > t- > value[i];t=t- > pRight[i])
if (t- > minmax == MAX_ELEM)
if (HasCollisionPair(pAABB, GetAABB(t)))
DeleteCollisionPair(pAABB, GetAABB(t));
if (t != pMin- > pRight[i])
MoveElement(i, pMin, t- > pLeft[i]);
// Similarly to above, try to move max element to the left
for (t = pMax- > pLeft[i]; pMax- > value[i] < t- > value[i];t=t- > pLeft[i])
if (t- > minmax == MIN_ELEM)
if (HasCollisionPair(pAABB, GetAABB(t)))
DeleteCollisionPair(pAABB, GetAABB(t));
if (t != pMax- > pLeft[i])
MoveElement(i, pMax, t);
}
}
The support function to move the AABB elements within the list is given by:
void MoveElement(int i, Elem *pElem, Elem *pDest)
{
// Unlink element...
pElem- > pLeft[i]- > pRight[i] = pElem- > pRight[i];
pElem- > pRight[i]- > pLeft[i] = pElem- > pLeft[i];
// ...and relink it _after_ the destination element
pElem- > pLeft[i] = pDest;
pElem- > pRight[i] = pDest- > pRight[i];
pDest- > pRight[i]- > pLeft[i] = pElem;
pDest- > pRight[i] = pElem;
}