Graphics Reference
In-Depth Information
Figure 7.5.
Area subdivision examples.
Test 1:
Is
P
disjoint from a window?
Test 2:
Does
P
surround a window?
Test 3:
Does
P
partially meet a window?
Test 4:
Does
P
fall inside a window?
Test 5:
Is
P
in front of other polygons?
For a quick test for disjointness, one usually uses bounding boxes. One way to test
if the window falls inside a polygon is to substitute the vertices of the window into
the equations for the edges of the projected polygons. If these tests fail, then one needs
to check if the boundary of the polygon intersects the window by checking each edge
of the polygon against each edge of the window. If the boundaries are disjoint, then
one still has to distinguish between the case where the regions are disjoint or where
one contains the other. We discussed some tests for doing this in Section 6.3. One
approach is to use a parity test and count the number of times that, say, any hori-
zontal ray starting at a window vertex intersects the polygon. If the number is even,
then the two are disjoint, otherwise the polygon surrounds the window. Another
approach is to use an angle counting argument.
Tests 1-4 above dealt with view plane issues. Test 5 involves depth calculations.
As mentioned earlier, we are assuming an orthogonal projection (with the camera at
-•) and so testing if one point is in front of another amounts to checking that its z-
value is less than that of the other point. Assume that two polygons
P
and
Q
meet the
window. We give a test for whether
P
is in front of
Q
. In Warnock's algorithm this test
is only needed for the case
P
is a surrounding polygon, but the fact that it is sur-
rounding is not important. Here is the test: if the depth of the plane of
P
is less than
the depth of the plane of
Q
at the four corners of the window, then
P
is in front of
Q
(Figure 7.6(a)). This is a sufficient but not necessary condition for that to happen
(Figures 7.6(b) and (c)). Warnock subdivides the window if the test fails.
There are many variations of Warnock's algorithms. The windows need not be rec-
tangular. The problem with rectangular windows is that, being bad matches to most
polygons, the algorithm has to recurse down to the pixel level a lot. The Weiler-
Atherton algorithm ([WeiA77]) uses subwindows that match the shape of the poly-
gons. See Figure 7.7, which shows a list of polygons being clipped against a polygon
