Binary Space Partitioning is a preprocessing technique for polygonal scenes first introduced by Fuchs, Kedem, and Naylor [1]. Geometrically, the process of creating a Binary Space Partition (BSP) tree involves splitting a d-space into two half-spaces with a hyperplane of dimension d-1. The process is repeated until the entire space is divided into a heirarchy of potentially infinite ``cells''.
BSP trees have been discovered to have a number of useful properties of interest the computer graphics community. In the case of a three dimensional tree generated by this process, a modified in-order traversal will yield a depth-sorted ordering of all polygons in the space. Later work develops the use of BSP trees to perform set operations on polyhedra [2], [3]. It is also possible to implement an efficient ray-shooting algorithm operating on BSP trees; such algorithms have been used to speed up ray-tracing systems [4].
In the case of a three-dimensional polygonal environment, one wants to generate an autopartition of the world environment. An autopartitioning involves choosing a polygon from the space and using that polygon's plane as the dividing hyperplane. All of the polygons remaining are classified into one or the other of the half-spaces. Any polygons that cross the dividing plane are split, the two new polygons placed into the appropriate half-space. The process is recursively repeated in each half-space until every polygon has been incorporated into the tree.
As one might expect, the generation of BSP trees is not something to be left to blind chance. Two efficiency issues arise in the generation of BSP trees. For a naive partitioning algorithm operating in three-space, a partitioning of n polygons will yield O(n^3) polygons due to planar splits. Paterson and Yao [5] showed that an autopartition of size O(n^2) is possible, and they present the algorithm for producing such an autopartition.
The second concern is to keep the BSP tree well-balanced. The efficiency of ray-shooting and BSP set operations depends on maintaining a reasonably well-balanced tree. Bruce Naylor is involved in ongoing research on algorithms and techniques to maintain well-balanced BSP trees.
Once a BSP tree has been generated that represents the scene to be displayed a modified in-order traversal will yield either a back-to-front or front-to-back ordering of the polygons with respect to an arbitrary view point. Figure~1 gives the front-to-back traversal algorithm as presented by Gordon and Chen [6].
Procedure front_to_back(BSP_tree, view_point)
begin
if (BSP_tree != null)
if (positive_side_of(root(BSP_tree),view_point))
front_to_back(positive_branch(BSP_tree),view_point);
display_polygon(root(BSP_tree));
front_to_back(negative_branch(BSP_tree),view_point);
else
front_to_back(negative_branch(BSP_tree),view_point);
display_polygon(root(BSP_tree));
front_to_back(positive_branch(BSP_tree),view_point);
end
Figure 1: Front-to-back BSP tree traversalFront to back traversal is not an arbitrary choice for this example. As will be shown later, it provides a significant speedup in rendering time when polygons are rendered using a non-trivial scan-conversion process such as texture-mapping, shading, and so forth.
Naylor [7] describes an BSP traversal algorithm for polygon display that integrates three dimensional clipping into the tree traversal for increased efficiency. In order to understand Naylor's technique, think of the view volume as an object in world space. The region to be rendered is the intersection of the interior view volume and the world space. The resultant algorithm closely resembles the BSP merging algorithm of [8]. It has the property that subtrees of the BSP that do not intersect the view volume can be ignored during the tree traversal. Thus global clipping can be performed in O(log n) time, as opposed to the traditional O(n) time required for global clipping.
This form of global clipping is excellently suited to systems where the view-volume represents only a small portion of the total world database. In particular, architectural models typically fall into this category. Since global clipping via the BSP tree is logarithmic in the size of the world database, this algorithm effectively de-sensitizes the renderer to slowdowns due to a large world database.