Graphics Reference
In-Depth Information
8.4
Using the BSP Tree
As an example of the ease with which BSP trees handle certain problems, con-
sider the problem of rendering the faces on the nodes of a node-storing BSP tree in
back-to-front order. By construction, the geometry on each side of a dividing plane
does not intersect. Consequently, if the camera lies on the front side of a dividing
plane no geometry on the back side of the dividing plane can obscure the geometry
on the front side (nor the geometry on the plane itself). Thus, all that is needed to
render the tree back to front is to recursively render the far subtree of the current
node, then the faces stored in the node, then recursively render the near subtree
(the one corresponding to the side on which the camera lies). The implementation
of back-to-front rendering of a BSP tree then becomes:
// Render node-storing BSP tree back-to-front w/ respect to cameraPos
void RenderBSP(BSPNode *node, Point cameraPos)
{
// Get index of which child to visit first (0 = front, 1 = back)
int index = ClassifyPointToPlane(cameraPos, node->plane) == POINT_IN_FRONT_OF_PLANE;
// First visit the side the camera is NOT on
if (node-
>
child[index]) RenderBSP(node-
>
child[index], cameraPos);
// Render all polygons stored in the node
DrawFrontfacingPolygons(node-
>
pPolyList);
// Then visit the other side (the one the camera is on)
if (node-
>
child[index
∧
1]) RenderBSP(node-
>
child[index
∧
1], cameraPos);
}
The same recursive approach is used for all queries on BSP trees. In that leaf-storing
BSP trees are really just another form of spatial partitioning, discussed in detail in
Chapter 7, the following section focuses specifically on the implementation of basic
collision queries on solid-leaf BSP trees.
8.4.1
Testing a Point Against a Solid-leaf BSP Tree
Testing if a point lies in empty or solid space of a solid-leaf BSP tree is a largely
straightforward application. At each node, the point is evaluated with respect to the
dividing plane at that node. If the point lies in front of the plane, the child node
representing the front tree is visited, and vice versa. Traversal continues until a leaf
node is reached, at which point the solidity of the leaf indicates the result.
The only complication lies in correctly determining if the query point lies on the
boundary of the solid volume represented by the BSP tree. To handle the boundary
case, both subtrees are traversed when the point lies on a dividing plane. If the
