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:
| A 1 / D
| / 2 ^
| / |
| 5 / 3
| 4 /
| B / C
A top down view of a partitioned space.
1-5 are clusters, A-D are regions made by planes P1 and P2.
front / \ back
/ \ / \
/ \ / \
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