Graphics Reference
In-Depth Information
it was sufficient to choose the best from a few chosen
at random
(five seemed to work
well).
We have just described the original BSP algorithms. Variants have been developed
since then. For example, Kaplan ([Kapl85]) chose his separating planes to be parallel
to the coordinate planes of the reference coordinate system. Such an algorithm is
sometimes called an
orthogonal BSP algorithm
. This property of separating planes can
simplify computations, especially when objects have bounding boxes. We shall
mention other BSP algorithms later on when discussing ray tracing in Section 10.2.
To summarize, the BSP algorithm is a good algorithm where the world model does
not change much and only the viewpoint changes. Examples of such situations are
flight simulators, architects walking through a house, and biochemists viewing com-
plicated molecules. Chin ([Chin95]) describes an efficient way to implement and use
BSP trees.
7.6
Warnock and Weiler-Atherton Area Subdivision
The Warnock visible surface determination algorithm [Warn69] is an image space
algorithm that attempts to find rectangular regions (here called
windows
) of the same
intensity on the screen (
area coherence
). Algorithm 7.6.1 is an outline of the algorithm.
The polygons referred to in the algorithm are the
projected
polygons. See Figure 7.5.
Essential to this algorithm is the ability to perform the following tests on any
polygon
P
:
Initialize a list L of windows to consist of a single window that is the entire screen;
For each window W in the current list L of windows look for one of the following “trivial”
cases:
(1) All polygons are disjoint from W. In this case one draws W in the background color.
(2) Only one polygon
P
intersects W. In this case draw the intersection of
P
and W in the
color of
P
and the rest of W in the background color. In practice, this case is divided
into three subcases:
P
is contained in W,
P
surrounds W,
P
and W have a nontrivial
intersection.
(3) At least one surrounding polygon was found and it is in front of all other polygons that
intersect the window. In that case draw the window in the color of that polygon.
Otherwise, divide the window W into four equal smaller windows, add them to the list L of
windows, and repeat the process until one gets down to a window the size of a pixel. At that
point one checks directly which polygon is in front of all the others at that pixel.
Algorithm 7.6.1.
Outline of the Warnock algorithm.
