Graphics Reference
In-Depth Information
the plane is split to the plane before partitioning. (Polygons on the plane are treated
differently depending on what type of tree is constructed.)
3. The forming of a tree by connecting with a new tree node the two subtrees created
by recursively calling the construction algorithm with the two partitioned sets
obtained in the previous step.
These steps translate directly into code as follows (here illustrated for the construction
of a leaf-storing tree).
// Constructs BSP tree from an input vector of polygons. Pass 'depth' as 0 on entry
BSPNode *BuildBSPTree(std::vector<Polygon *> &polygons, int depth)
{
// Return NULL tree if there are no polygons
if (polygons.empty()) return NULL;
// Get number of polygons in the input vector
int numPolygons = polygons.size();
// If criterion for a leaf is matched, create a leaf node from remaining polygons
if (depth >= MAX_DEPTH || numPolygons <= MIN_LEAF_SIZE) || ...etc...)
return new BSPNode(polygons);
// Select best possible partitioning plane based on the input geometry
Plane splitPlane = PickSplittingPlane(polygons);
std::vector<Polygon *> frontList, backList;
// Test each polygon against the dividing plane, adding them
// to the front list, back list, or both, as appropriate
for(inti=0;i<numPolygons; i++) {
Polygon *poly = polygons[i], *frontPart, *backPart;
switch (ClassifyPolygonToPlane(poly, splitPlane)) {
case COPLANAR_WITH_PLANE:
// What's done in this case depends on what type of tree is being
// built. For a node-storing tree, the polygon is stored inside
// the node at this level (along with all other polygons coplanar
// with the plane). Here, for a leaf-storing tree, coplanar polygons
// are sent to either side of the plane. In this case, to the front
// side, by falling through to the next case
case IN_FRONT_OF_PLANE:
frontList.push_back(poly);
break;
