Graphics Reference
In-Depth Information
subtree results indicate the same result (solid or empty space), that is the result.
Otherwise, the point lies in the boundary. The following code illustrates how this test
may be implemented (using a thick plane for robustness).
int PointInSolidSpace(BSPNode *node, Point p)
{
while (!node- > IsLeaf()) {
// Compute distance of point to dividing plane
float dist = Dot(node- > plane.n, p) - node- > plane.d;
if (dist > EPSILON) {
// Point in front of plane, so traverse front of tree
node = node- > child[0];
} else if (dist < -EPSILON) {
// Point behind of plane, so traverse back of tree
node = node->child[1];
} else {
// Point on dividing plane; must traverse both sides
int front = PointInSolidSpace(node- > child[0], p);
int back = PointInSolidSpace(node- > child[1], p);
// If results agree, return that, else point is on boundary
return (front == back) ? front : POINT_ON_BOUNDARY;
}
}
// Now at a leaf, inside/outside status determined by solid flag
return node- > IsSolid() ? POINT_INSIDE : POINT_OUTSIDE;
}
If it is not necessary to categorize points as lying on the boundary and they can
instead be considered inside the solid, this test can be simplified to visit the back side
when the point is categorized as on the dividing plane. The code then becomes:
int PointInSolidSpace(BSPNode *node, Point p)
{
while (!node- > IsLeaf()) {
// Compute distance of point to dividing plane
float dist = Dot(node- > plane.n, p) - node- > plane.d;
// Traverse front of tree when point in front of plane, else back of tree
node = node- > child[dist <= EPSILON];
}
// Now at a leaf, inside/outside status determined by solid flag
return node- > IsSolid() ? POINT_INSIDE : POINT_OUTSIDE;
}
 
Search WWH ::




Custom Search