Graphics Reference
In-Depth Information
The following points need to be made about Algorithm 2.9.1.1:
(1) The polygon is assumed to lie entirely in window.
(2) Horizontal edges need not be considered because they get filled automatically.
(3) There is a problem with parity at vertices unless one takes precautions.
To understand the parity problem at vertices consider Figure 2.16 again. At vertices,
their x values would be listed twice in the active edge list. In the case of a local
maximum like vertex
B
= (x
B
,y
B
), the algorithm would fill the segments [XMIN,x
B
],
[x
B
,x
B
], and [x
B
,XMAX] on the scan line y = y
B
to the background color, the color of
the polygon, and the background color, respectively. This is as we would want it. On
the other hand, when the algorithm gets to vertex
A
= (x
A
,y
A
), assuming that there was
another edge below this vertex, it would fill [XMIN,x
A
] to the background color,
[x
A
,x
BA
] to the color of the polygon, and [x
BA
,x
BC
] to the background color, etc. This
is
not
correct. Furthermore, we cannot simply skip duplicate x-coordinates as we scan
the active edge list. If we did, then vertices like
A
would be handled correctly, but the
algorithm would now fail at local maxima and minima like
B
. The way that this parity
problem is usually resolved is to shorten one of the (two) edges that meet in a vertex
that is
not
at a local extremum. For example, change the lower vertex (x,y) of the
upper edge to (x,y + 1) (leaving the upper vertex of the lower edge in tact).
No
short-
ening takes place at vertices that are local extrema. With this change to the edges,
Algorithm 2.9.1.1 will now work correctly, but we need a test for when vertices are
local extrema. Here is one:
if
adjacent edges have the same sign for their slope
then
the common vertex is not a local extremum
else
test the opposite endpoints for whether or not they lie on the
same side of the scan line as the vertex: if they do, then the
vertex is a local extremum, otherwise, not
To see that a further test is required in the
else
case, consider Figure 2.17 and the
two pairs of segments ([(-1,-1),(0,0)],[(0,0),(1,-1)]) and ([(-1,-1),(0,0)],[(0,0),(-1,1)]).
In both pairs, the segments have opposite slopes, but (0,0) is a local extremum for the
first pair but not for the second. One can tell the two apart however because the end-
points (-1,-1) and (-1,1) for the first pair lie on opposite sides of the scan line for
(0,0), whereas the endpoints (-1,-1) and (1,-1) both lie on the same side of the scan
line.
Finally, note that the ordered edge list fill algorithm “works” for polygons with
self-intersections and/or holes. See Figure 2.18. One needs to understand what “works”
Figure 2.17.
Testing for local extrema.
