Also known as BSP tree. An algorithm developed by H. Fuchs, Z.M. Kedem and B.F. Naylor for calculating visible surfaces in 3D Graphics. It's often used in real-time simulations, since it trades off intensive preprocessing for a quick way of determining what surfaces are visible when the viewpoint changes.

Based on the work of R. Schumacker, who noted that environments can be seen as being made up of clusters (sets of faces). If you find a plane that seperates one set of clusters from another, then clusters on the same side of the plane as the viewpoint is can cover, but cannot be covered by, clusters on the other side. Each of these groups of clusters can then be subdivided further by other planes. From these divisions, you can make a binary tree. Here's a simple example:
^             P1    
| A    1     /       D
|           /  2   ^
|          /       |
|    5   /   3
|       /
|      /->   
|  4  /     
| B  /              C   
---------------------> X
A top down view of a partitioned space. 1-5 are clusters, A-D are regions made by planes P1 and P2.
      front /  \ back
           /    \
          /      \
         /        \
       P2          P2
      /  \        /  \
     /    \      /    \
    D      C    A      B
BSP tree from the above partitioned space.
The leaf nodes of this binary tree are areas of space defined by the partitioning planes. To determine which area the viewpoint is in, simply traverse the tree. Once the area the viewpoint is in has been determined, the number of calculations it takes to determine which polygons need to be drawn and which are obscured is reduced. For example, if the viewpoint is in A, the display algorithm can safely assume that nothing is covering cluster 1. This affects which clusters are scan-converted first.

Most implementations of BSP trees use a polygon in the scene as the root partitioning plane. The scene is then recursively partitioned with the rest of the polygons in the scene. This produces a far more useful tree than using partitioning planes that simply seperate clusters. Often, an arbitrary polygon is chosen for the root node, then the tree is balanced after it's generated.

Paraphrased from Computer Graphics: Principles and Practice

Log in or register to write something here or to contact authors.