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