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:

Y
^ P1
| A 1 / D
| / 2 ^
| / |
|---------/----------P2
| 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.

P1
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*