Algorithm

The BSP tree algorithm [1] is based on the observation that a polygon will be scan-converted correctly (i.e., will not overlap incorrectly or be overlapped incorrectly by other polygons) if all polygons on the other side of it from the viewer are scan-converted first, followed by it, and then all polygons on the same side of it as the viewer. We need to ensure that this is so for each polygon.

The algorithm makes it easy to determine a correct order for scan conversion by building a binary tree of polygons, the BSP tree. The BSP tree's root is a polygon selected from those to be displayed; the algorithm works correctly no matter which is picked. The root polygon is used to partition the environment into two half-spaces. One half-space contains all remaining polygons in front of the root polygon, relative to its surface normal; the other contains all polygons behind the root polygon. Any polygon lying on both sides of the root polygon's plane is split by the plane, and its front and back pieces are assigned to the appropriate half-space. One polygon each from the root polygon's front and back half-spaces becomes its front and back children, and each child is recursively used to divide the remaining polygons in its half-space in the same fashion. The algorithm terminates when each node contains only a single polygon. A C++ pseudo-code for tree-building phase is given below [5].

struct  BSP_tree
{
   plane     partition;
   list      polygons;
   BSP_tree  *front,
             *back;
};

void Build_BSP_Tree (BSP_tree *tree, list polygons)
{
   polygon   *root = polygons.Get_From_List ();
   tree->partition = root->Get_Plane ();
   tree->polygons.Add_To_List (root);
   list      front_list,
             back_list;
   polygon   *poly;
   while ((poly = polygons.Get_From_List ()) != 0)
   {
      int   result = tree->partition.Classify_Polygon (poly);
      switch (result)
      {
         case COINCIDENT:
            tree->polygons.Add_To_List (poly);
            break;
         case IN_BACK_OF:
            backlist.Add_To_List (poly);
            break;
         case IN_FRONT_OF:
            frontlist.Add_To_List (poly);
            break;
         case SPANNING:
            polygon   *front_piece, *back_piece;
            Split_Polygon (poly, tree->partition, front_piece, back_piece);
            backlist.Add_To_List (back_piece);
            frontlist.Add_To_List (front_piece);
            break;
      }
   }
   if ( ! front_list.Is_Empty_List ())
   {
      tree->front = new BSP_tree;
      Build_BSP_Tree (tree->front, front_list);
   }
   if ( ! back_list.Is_Empty_List ())
   {
      tree->back = new BSP_tree;
      Build_BSP_Tree (tree->back, back_list);
   }
}

Remarkably, the BSP tree can be traversed in a modified in-order tree walk to yield a correct priority-ordered polygon list for an arbitrary viewpoint. Consider the root polygon. It divides the remaining polygons into two sets, each of which lies entirely on one side of the root's plane. Thus, the algorithm needs only to guarantee that the sets are displayed in the correct relative order to ensure both that one set's polygons do not interfere with the other's and that the root polygon is displayed properly and in the correct order relative to the others. If the viewer is in the root polygon's front half-space, then the algorithm must first display all polygons in the root's rear half-space (those that could be obscured by the root), then the root, and finally all polygons in its front half-space (those that could obscure the root). Alternatively, if the viewer is in the root polygon's rear half-space, then the algorithm must display all polygons in the root's front half-space, then the root, and finally all polygons in its rear half-space. If the polygon is seen on edge, either display order suffices. Back-face culling may be accomplished by not displaying a polygon if the eye is in its rear half-space. Each of the root's children is recursively processed by this algorithm.

void	Draw_BSP_Tree (BSP_tree *tree, point eye)
{
   real   result = tree->partition.Classify_Point (eye);
   if (result > 0)
   {
      Draw_BSP_Tree (tree->back, eye);
      tree->polygons.Draw_Polygon_List ();
      Draw_BSP_Tree (tree->front, eye);
   }
   else if (result < 0)
   {
      Draw_BSP_Tree (tree->front, eye);
      tree->polygons.Draw_Polygon_List ();
      Draw_BSP_Tree (tree->back, eye);
   }
   else // result is 0
   {
      // the eye point is on the partition plane...
      Draw_BSP_Tree (tree->front, eye);
      Draw_BSP_Tree (tree->back, eye);
   }
}

Like the depth-sort algorithm, the BSP tree algorithm performs intersection and sorting entirely at object precision, and relies on the image-precision overwrite capabilities of a raster device. Unlike depth sort, it performs all polygon splitting during a preprocessing step that must be repeated only when the environment changes. Note that more polygon splitting may occur than in the depth-sort algorithm.