Graphics Reference
In-Depth Information
case BEHIND_PLANE:
backList.push_back(poly);
break;
case STRADDLING_PLANE:
// Split polygon to plane and send a part to each side of the plane
SplitPolygon(*poly, splitPlane, &frontPart, &backPart);
frontList.push_back(frontPart);
backList.push_back(backPart);
break;
}
}
// Recursively build child subtrees and return new tree root combining them
BSPNode *frontTree = BuildBSPTree(frontList, depth + 1);
BSPNode *backTree = BuildBSPTree(backList, depth + 1);
return new BSPNode(frontTree, backTree);
}
For constructing leaf-storing or solid trees, polygons that lie on the partitioning
plane are sent to either side of the plane (here, to the front side of the plane). For
node-storing trees, coplanar polygons are instead stored in the node itself.
Although simple in structure, there are a few problems hidden in the helper func-
tions called by this code. Specifically, having
PickSplittingPlane()
select a good
partitioning plane is a nontrivial problem. Sections 8.3.1 and 8.3.2 cover this problem
in more detail. There are also some subtle issues to do with robustness involved in clas-
sifying and splitting a polygon to a plane in the functions
ClassifyPolygonToPlane()
and
SplitPolygon()
, discussed further in Sections 8.3.3 through 8.3.5.
A third issue is determining when to stop the tree construction. This depends on
the type of BSP tree being built. For a node-storing tree, the recursive construction
proceeds until the set of remaining input polygons becomes empty. The same applies
for a solid-leaf tree. The construction of a leaf-storing BSP tree is typically stopped
when:
The leaf contains less than some preset number of polygons.
●
A fixed cutoff depth has been reached.
●
A good dividing plane cannot be found.
●
The examples presented in this chapter use the same tree representation for
construction of the tree and for runtime queries. However, it is important to stress
