Graphics Reference
In-Depth Information
Figure 2.18.
Various types of polygon.
means though. For example, the inside of the inner loop of Figure 2.18(a) will be
drawn in the background color.
Looking ahead to Chapter 7, which is on visible surface determination, we can
deal with multiple polygons here if we have an associated priority number with each,
where having a higher priority means being in front of or not obscuring. In the
algorithm above, as we go along we must now keep track of the polygon to which
the “current” segment “belongs.” One way to do this is to maintain the following
additional data:
(1) covers
- a Boolean array so that covers[i] is
true
for the ith polygon if
it covers the current segment
(2) numcover
- the number of polygons covering the current segment
(3) visiblePoly
- a pointer to the foremost polygon, if any
As we move from segment to segment in a scan line, numcover is incremented or
decremented appropriately. The array covers is initialized to
false
and every time that
one runs into an edge of the ith polygon, covers[i] is negated. The pointer visiblePoly
tells us the color of the current segment.
In conclusion, here are some points to consider when deciding on a fill algorithm.
The main advantages of ordered edge list algorithms are that pixels are visited only
once and they are well suited for shading algorithms since both ends of a span are
computed before the span is drawn so that one can interpolate intensities. The main
disadvantage is the large amount of processing required maintaining and sorting
various lists. The main advantage to seed fill algorithms is that they can fill arbitrary
planar contours, not just those bounded by polygonal curves. The main disadvantages
are that some pixels are visited many times and one requires an initial interior point.
The latter is not a problem in interactive situations but would be in a fully automated
one. One would then have to invoke another algorithm to find such a point. See
[AckW81] for some conclusions based on performance tests. Basically, fill time tends
to be dominated by the time required to set pixels making the ordered edge list algo-
rithms the most attractive overall. [FisB85] compares various specific seed fill algo-
rithms. An antialiased scan conversion algorithm is described in [Morr90].
