Spatial Partitioning - Real-Time Collision Detection - page 313

for collisions can be done as a recursive top-down procedure in which the objects of
each nonempty node are checked against all objects in the subtree below the node.
// Tests all objects that could possibly overlap due to cell ancestry and coexistence
// in the same cell. Assumes objects exist in a single cell only, and fully inside it
void TestAllCollisions(Node *pTree)
{
// Keep track of all ancestor object lists in a stack
const int MAX_DEPTH = 40;
static Node *ancestorStack[MAX_DEPTH];
static int depth = 0; // 'Depth == 0' is invariant over calls
// Check collision between all objects on this level and all
// ancestor objects. The current level is included as its own
// ancestor so all necessary pairwise tests are done
ancestorStack[depth++] = pTree;
for(intn=0;n<depth; n++) {
Object *pA, *pB;
for (pA = ancestorStack[n]- > pObjList; pA; pA = pA- > pNextObject) {
for (pB = pTree- > pObjList; pB; pB = pB- > pNextObject) {
// Avoid testing both A- > B and B- > A
if (pA == pB) break;
// Now perform the collision test between pA and pB in some manner
TestCollision(pA, pB);
}
}
}
// Recursively visit all existing children
for(inti=0;i<8;i++)
if (pTree- > pChild[i])
TestAllCollisions(pTree->pChild[i]);
// Remove current node from ancestor stack before returning
depth--;
}
7.3.3 Locational Codes and Finding the Octant for a Point
Consider a query point somewhere inside the space occupied by an octree. The leaf
node octant in which the point lies can be found without having to perform direct