BSP Tree Hierarchies - Real-Time Collision Detection - page 376

8.4.2 Intersecting a Ray Against a Solid-leaf BSP Tree

A typical query on a BSP tree is the intersection of a ray or segment against the tree.
One solution is to adapt the function VisitNodes() , discussed in Section 7.4.1, for
traversing all nodes of a node-storing k -d tree intersected by a segment. Here, an
alternative, nonrecursive, traversal routine is given.
One important difference between VisitNodes() and the discussed query is that
the former computes the intersection point of the segment and a dividing plane. It
then breaks the segment into two subsegments at this point. These subsegments
are then subject to splitting in a similar manner as they are passed down the tree
recursively. Due to accumulation of errors, this means that the computed intersection
points are likely to drift off the original segment. The further down the tree a query
traversal reaches the farther from the original segment the intersection points are
expected to move. From a robustness standpoint, this is not very good.
The accumulation of error can be avoided by working exclusively with the inter-
section times of the ray with the dividing planes, without ever computing the
intersection points. Use of thick planes hides the errors remaining in intersection
time computations.
The routine to intersect the ray R ( t ) t max , against a solid-leaf

BSP tree follows. The time t hit of the first intersection with a solid leaf is returned
when such an intersection exists.

= P + t d , t min ≤ t ≤

// Intersect ray/segment R(t)=p+t*d, tmin <= t <= tmax, against bsp tree
// 'node', returning time thit of first intersection with a solid leaf, if any
int RayIntersect(BSPNode *node, Point p, Vector d, float tmin, float tmax, float *thit)
{

std::stack<BSPNode *> nodeStack;
std::stack<float> timeStack;

assert(node != NULL);
while (1) {
if (!node- > IsLeaf()) {
float denom = Dot(node- > plane.n, d);
float dist = node- > plane.d - Dot(node- > plane.n, p);
int nearIndex = dist > 0.0f;
// If denom is zero, ray runs parallel to plane. In this case,
// just fall through to visit the near side (the one p lies on)
if (denom != 0.0f) {
float t = dist / denom;
if (0.0f <= t && t <= tmax) {
if (t >= tmin) {
// Straddling, push far side onto stack, then visit near side
nodeStack.push(node->child[1 ∧ nearIndex]);