Visible Surface Algorithms - Computer Graphics and Geometric Modeling - page 269

depth. Although there is this overlap in z, P may in fact not obscure any part of any
of the Q s, and so the algorithm performs a series of tests, ordered by complexity. These
tests involve answering the following questions:

(1) Can one separate P and the Q s in x?
(2) Can one separate P and the Q s in y?
(3) Is P on the farther side of the Q s? See Figure 7.3(b).
(4) Are the Q s on the near side of P ? See Figure 7.3(c).
(5) Do P and the Q s project to disjoint sets?

Test (5) is clearly the most complicated and the hope is that one does not have
to perform it very often. If the answer to all these tests is “no,” then one swaps P
with a Q and repeats the tests. One has to mark the Q to prevent getting into an
infinite loop. An attempt to swap an element already swapped at a previous stage
implies that one has encountered a “cyclical overlap.” An example of this is shown in
Figure 7.3(d). In that case one would cut Q at the dotted line and replace the old Q
with the two parts. Eventually one would be able to write the polygons to the frame
buffer.
The Newell algorithm handled transparency effects by overwriting the frame
buffer only partially. However, aside from the historical interest, the interesting aspect
of the algorithm comes from tests (1)-(4), which can be useful in other situations.

7.5 The BSP Algorithm

The Binary Space Partitioning (BSP) algorithm ([FuK N80] and [FuAG83]) is a visible
surface algorithm that improved on Schumacker's work by automating the division
into clusters. The basic BSP algorithm consists of two steps:

(1) A one-time preprocessing step that converts an input polygon list into a binary
tree structure called a BSP tree
(2) A traversal algorithm that traverses this tree and outputs the polygons to the
frame buffer in a back-to-front order

A key idea here (like in Schumacker's work) is that of a separating plane . The main
condition that this plane has to satisfy is that no polygon on the viewpoint side of the
plane can be obstructed by a polygon on the other side. To construct the BSP tree,
one proceeds as follows:

(1) Select any polygon P from the current list of polygons and place it at root of tree.
(2) Each remaining polygon in the list is then tested to see on which side of P it
lies. If it lies on the same side as the viewpoint one puts it in the left (or “front”)
subtree list, otherwise one puts it in the right (or “back”) subtree list. If a
polygon straddles P s plane, divide it along that plane and put each of the
pieces in the appropriate subtree list.
(3) Repeat this procedure recursively on the two subtree lists.