Spatial Partitioning - Real-Time Collision Detection - page 323

segment, 0 tmax , the segment straddles the plane and both children of the

tree are recursively descended. If not, only the side containing the segment origin is
recursively visited.
By first descending the side of the segment origin, overlapped k -d tree nodes are
guaranteed to be traversed in order near to far. Thus, assuming the closest intersection
point is sought, when a hit is detected among the node contents the test procedure
can exit early, not having to test any other nodes.

≤ t <

// Visit all k-d tree nodes intersected by segmentS=a+t*d,0<=t<tmax
void VisitNodes(KDNode *pNode, Point a, Vector d, float tmax)
{

if (pNode == NULL) return;

// Visiting current node, perform actual work here
...

// Figure out which child to recurse into first (0 = near, 1 = far)
int dim = pNode- > splitType;
int first = a[dim] > pNode- > splitValue;

if (d[dim] == 0.0f) {
// Segment parallel to splitting plane, visit near side only
VisitNodes(pNode->child[first], a, d, tmax);
} else {
// Find t value for intersection between segment and split plane
float t = (pNode- > splitValue - a[dim]) / d[dim];

// Test if line segment straddles splitting plane
if (0.0f <= t && t < tmax) {
// Yes, traverse near side first, then far side
VisitNodes(pNode- > child[first], a, d, t);
VisitNodes(pNode- > child[first ∧ 1],a+t*d,d,tmax - t);
} else {
// No, so just traverse near side
VisitNodes(pNode- > child[first], a, d, tmax);

}

}

}

This procedure can be rewritten to avoid explicit recursion, in the manner described
in Chapter 6. Only small changes are required to accommodate traversals for octrees
and BSP trees. It is also possible to directly link the faces of a leaf to the leaf
nodes they border, allowing direct traversal from one leaf to the next. As a face