Journal: Dr. Dobb's Journal June 1991 v16 n6 p139(6)
-----------------------------------------------------------------------------
Title: Of songs, taxes, and the simplicity of complex polygons. (polygon
filling)(Graphics Programming, column) (tutorial)
Author: Abrash, Michael.
AttFile: Program: GP-JUN91.ASC C & Assembler source code.
Summary: Graphics programming techniques are presented that fill three
types of arbitrary polygons: complex, meaning there are
intersecting edges; convex, meaning a continuous curving line
could touch all vertices in the order they are defined; and
nonconvex, meaning there are no intersecting edges and the polygon
is not complex. Complex is a superset of nonconvex, which itself
is a superset of convex. Complex polygons require the slowest
fill strategy, though that strategy will fill any type of polygon.
Nonconvex polygons are filled with less sorting. Convex polygons
can be filled the fastest by merely scanning the two main sides of
the polygon. Polygon filling begins with the idea that
intersections between all polygon edges and each scan line are
identified and, and the spans between intersections are filled. A
program listing implements the fill technique for complex
polygons.
-----------------------------------------------------------------------------
Descriptors..
Topic: Program Development Techniques
Tutorial
Graphics Languages
Type-In Programs
Graphic Forms
Two-Dimensional Graphics.
Feature: illustration
chart.
Caption: Filling one scan line by finding intersecting edges. (chart)
Currently active edges are checked for intersection with any scan
line. (chart)
The global and active edge tables are linked lists. (chart)
-----------------------------------------------------------------------------
Full Text:
Every so often, my daughter asks me to sing her to sleep. (If you've ever
heard me sing, this may cause you concern about either her hearing or her
judgement, but love knows no bounds.) As any parent is well aware, singing a
young child to sleep can easily take several hours, or until sunrise, which
ever comes last. One night, running low on children's songs, I switched to a
Beatles medley, and at long last her breathing became slow and regular. At
the end, I softly sang "A Hard Day's Night," then quietly stood up to leave.
As I tiptoed out, she said, in a voice not even faintly tinged with sleep,
"Dad, what do they mean, 'working like a dog'? Chasing a stick? That
doesn't make sense; people don't chase sticks."
That led us into a discussion of idioms, which made about as much sense to
her as an explanation of quantum mechanics. Finally, I fell back on my
standard explanation of the Universe, which is that a lot of the time it
doesn't make sense.
As a general principle, that explanation holds up remarkably well. (In fact,
having just done my taxes, I think Earth is actually run by blob-creatures
from the planet Mrxx, who are helplessly doubled over with laughter at the
ridiculous things they can make us do. "Let's make them get Social Security
numbers for their pets next year!" they're saying right now, gasping for
breath.) Occasionally, however, one has the rare pleasure of finding a
corner of the Universe that makes sense, where everything fits together as if
preordained.
Filling arbitrary polygons is such a case.
Filling Arbitrary Polygons
In the February column, I described three types of polygons: convex,
nonconvex, and complex. The RenderMan Companion, which I mentioned last
month, has an intuitive definition of convex: If a rubber band stretched
around a polygon touches all vertices in the order they're defined, then the
polygon is convex. If a polygon has intersecting edges, it's complex. If a
polygon doesn't have intersecting edges but isn't convex, it's nonconvex.
Nonconvex is a special case of complex, and convex is a special case of
nonconvex. (Which, I'm well aware, makes nonconvex a lousy name--noncomplex
would have been better--but I'm following X Window System nomenclature here.)
The reason for distinguishing between these three types of polygons is that
the more specialized types can be filled with markedly faster approaches.
Complex polygons require the slowest approach; however, that approach will
serve to fill any polygon of any sort. Nonconvex polygons require less
sorting, because edges never cross. Convex polygons can be filled fastest of
all by simply scanning the two sides of the polygon, as we saw in March.
Before we dive into complex polygon filling, I'd like to point out that the
code in this article, like all polygon filling code I've ever seen, requires
that the caller describe the type of the polygon to be filled. Often,
however, the caller doesn't know what type of polygon it's passing, or
specifies complex for simplicity, because that will work for all polygons; in
such a case, the polygon filler will use the slow complex-fill code even if
the polygon is, in fact, a convex polygon.
Although I've never seen it mentioned anywhere, it is reasonably easy to
determine whether a polygon specified as complex or nonconvex is actually
convex. The best technique I've come up with is tracing around the polygon's
boundary, counting the number of times that the boundary reverses X and Y
directions. If the boundary reverses both directions no more than twice, the
polygon is convex. Whether the faster drawing of convex polygons justifies
the extra time required to count X and Y reversals depends on both the
implementation and the number of polygons in any particular application which
are specified as complex/nonconvex but are actually convex.
Active Edges
The basic premise of filling a complex polygon is that for a given scan line,
we determine all intersections between the polygon's edges and that scan line
and then fill the spans between the intersections, as shown in Figure 1.
(Section 3.6 of Computer Graphics, second edition, by Foley and van Dam
provides an overview of this and other aspects of polygon filling.) There
are several rules that might be used to determine which spans are drawn and
which aren't; we'll use the odd/even rule, which specifies that drawing turns
on after odd-numbered intersections (first, third, and so on) and off after
even-numbered intersections.
The question then becomes how we can most efficiently determine which edges
cross each scan line and where. As it happens, there is a great deal of
coherence from one scan line to the next in a polygon edge list, because each
edge starts at a given Y coordinate and continues unbroken until it ends. In
other words, edges don't leap about and stop and start randomly; the X
coordinate of an edge at one scan line is a consistent delta from that edge's
X coordinate at the last scan line, and that is consistent for the length of
the line.
This allows us to reduce the number of edges that must be checked for
intersection; on any given scan line, we only need to check for intersections
with the currently active edges--edges that start on that scan line, plus all
edges that start on earlier (above) scan lines and haven't ended yet--as
shown in Figure 2. This suggests that we can proceed from the top scan line
of the polygon to the bottom, keeping a running list of currently active
edges--called the Active Edge Table (AET)--with the edges sorted in order of
ascending X coordinate of intersection with the current scan line. Then we
can simply fill each scan line in turn according to the list of active edges
at that line.
Maintaining the AET from one scan line to the next involves three steps.
First, we must add to the AET any edges that start on the current scan line,
making sure to keep the AET X-sorted for efficient odd/even scanning.
Second, we must remove edges that end on the current scan line. Third, we
must advance the X coordinates of active edges with the same sort of error
term-based, Bresenham's-like approach we used for convex polygons, again
ensuring that the AET is X-sorted after advancing the edges.
Advancing the X coordinates is easy. For each edge, we'll store the current
X coordinate and all required error term information, and we'll use that to
advance the edge one scan line at a time; then we'll resort the AET by X
coordinate as needed. Removing edges as they end is also easy; we'll just
count down the length of each active edge on each scan line and remove an
edge when its count reaches zero. Adding edges as their tops are encountered
is a tad more complex. While there are a number of ways to do this, one
particularly efficient approach is to start out by putting all the edges of
the polygon, sorted by increasing Y coordinate, into a single list, called
the Global Edge Table (GET). Then, as each scan line is encountered, all
edges at the start of the GET that begin on the current scan line are moved
to the AET; because the GET is Y-sorted, there's no need to search the entire
GET. For still greater efficiency, edges in the GET that share common Y
coordinates can be sorted by increasing X coordinate; this ensures that no
more than one pass through the AET per scan line is ever needed when adding
new edges from the GET in such a way as to keep the AET sorted in ascending X
order.
What form should the GET and AET take? Linked lists of edge structures, as
shown in Figure 3. With linked lists, all that's required to move edges from
the GET to the AET as they become active, sort the AET, and remove edges that
have been fully drawn is the exchanging of a few pointers.
In summary, we'll initially store all the polygon edges in
Y-primary/X-secondary sort order in the GET, complete with initial X and Y
coordinates, error terms and error term adjustments, lengths, and directions
of X movement for each edge. Once the GET is built, we'll do the following:
1. Set the current Y coordinate to the Y coordinate of the first edge in the
GET.
2. Move all edges with the current Y coordinate from the GET to the AET,
removing them from the GET and maintaining the X-sorted order of the AET.
3. Draw all odd-to-even spans in the AET at the current Y coordinate.
4. Count down the lengths of all edges in the AET, removing any edges that
are done, and advancing the X coordinates of all remaining edges in the AET
by one scan line.
5. Sort the AET in order of ascending X coordinate.
6. Advance the current Y coordinate by one scan line.
7. If either the AET or GET isn't empty, go to step 2.
That's really all there is to it. Compare Listing One (page 154) to the fast
convex polygon filling code from March, and you'll see that, contrary to
expectation, complex polygon filling is indeed one of the more sane and
sensible corners of the universe.
Complex Polygon Filling:
An Implementation
Listing One shows a function, FillPolygon, that fills polygons of all shapes.
If CONVEX[underscore]FILL[underscore]LINKED is defined, then the fast convex
fill code from March is linked in and used to draw convex polygons.
Otherwise, convex polygons are handled as if they were complex. Nonconvex
polygons are also handled as complex, although this is not necessary, as
discussed shortly.
Listing One is a faithful implementation of the complex polygon filling
approach just described, with separate functions corresponding to each of the
tasks, such as building the GET and X-sorting the AET. Listing Two (page
156) provides the actual drawing code used to fill spans, built on a draw
pixel routine that is the only hardware dependency in the C code. Listing
Three (page 156) is the header file for the polygon filling code; note that
it is an expanded version of the header file used by the fast convex polygon
fill code from March. Listing Four (page 156) is a sample program that, when
linked to Listings One and Two, demonstrates drawing polygons of various
sorts.
Listing Four illustrates several interesting aspects of polygon filling. The
first and third polygons drawn illustrate the operation of the odd/even fill
rule. The second polygon drawn illustrates how holes can be created in
seemingly solid objects; an edge runs from the outside of the rectangle to
the inside, the edges comprising the hole are defined, and then the same edge
is used to move back to the outside; because the edges join seamlessly, the
rectangle appears to form a solid boundary around the hole.
The set of V-shaped polygons drawn by Listing Four demonstrate that polygons
sharing common edges meet but do not overlap. This characteristic, which I
discussed at length several months back, is not a trivial matter; it allows
polygons to fit together without fear of overlapping or missed pixels.
Listing One reflects a fairly complex rule for drawing pixels on polygon
boundaries that I have devised. It's not essential that I detail that rule
or its implementation in Listing One (which is fortunate, for I lack the
space to do so), but it's important that you know that it exists, and that,
as a result, Listing One should always fill polygons so that common
boundaries and vertices are drawn once and only once. This has the
side-effect for any individual polygon of not drawing pixels that lie exactly
on top or right boundaries or at certain vertices.
By the way, I have not seen polygon boundary filling handled this way
elsewhere. The boundary filling approach in Foley and van Dam is similar,
but seems to me to not draw all boundary and vertex pixels once and only
once.
More On Active Edges
Edges of zero height--horizontal edges and edges defined by two vertices at
the same location--never even make it into the GET in Listing One. A polygon
edge of zero height can never be an active edge, because it can never
intersect a scan line; it can only run along the scan line, and the span it
runs along is defined not by that edge but by the edges that connect to its
endpoints.
Performance Considerations
How fast is Listing One? When drawing triangles on a 20-MHz 386, it's less
than one-fifth the speed of the fast convex polygon fill code. However, most
of that time is spent drawing individual pixels; when Listing Two is replaced
with the fast assembler line segment drawing code in Listing Five (page 157),
performance improves by two and one-half times, to about half as fast as the
fast convex fill code. Even after conversion to assembly in Listing five,
DrawHorizontalLineSeg still takes more than half of the total execution time,
and the remaining time is spread out fairly evenly over the various
subroutines in Listing One. Consequently, there's no single place in which
it's possible to greatly improve performance, and the maximum additional
improvement that's possible is clearly considerably less than two times; for
that reason, and because of space limitations, I'm not going to convert the
rest of the code to assembly. However, when filling a polygon with a great
many edges, and especially one with a great many active edges at one time,
relatively more time would be spent traversing the linked lists. Then
conversion to assembly (which actually lends itself very nicely to linked
list processing) could pay off reasonably well.
The algorithm used to X-sort the AET is an interesting performance
consideration. Listing One uses a bubble sort, usually a poor choice for
performance. However, bubble sorts perform well when the data are already
almost sorted, and because of the X coherence of edges from one scan line to
another, that's generally the case with the AET. An insertion sort might be
somewhat faster, depending on the state of the AET when any particular sort
occurs, but a bubble sort will generally do just fine.
An insertion sort that scans backward through the AET from the current edge
rather than forward from the start of the AET could be quite a bit faster,
because edges rarely move more than one or two positions through the AET.
However, scanning backward requires a doubly linked list, rather than the
singly linked list used in Listing One. I've chosen to use a singly linked
list partly to minimize memory requirements (double-linking requires an extra
pointer field) and partly because supporting back links would complicate the
code a good bit. The main reason, though, is that the potential rewards for
the complications of back links and insertion sorting aren't great enough;
profiling a variety of polygons reveals that less than ten percent of total
time is spent sorting the AET. The potential 1-5 percent speedup gained by
optimizing AET sorting just isn't worth it in any but the most demanding
application -- a good example of the need to keep an overall perspective when
comparing the theoretical characteristics of various approaches.
Nonconvex Polygons
Nonconvex polygons can be filled somewhat faster than complex polygons.
Because edges never cross or switch positions with other edges once they're
in the AET, the AET for a nonconvex polygon needs to be sorted only when new
edges are added. In order for this to work, though, edges must be added to
the AET in strict left-to-right order. Complications arise when dealing with
two edges that start at the same point, because slopes must be compared to
determine which edge is leftmost. This is certainly doable, but because of
space limitations and limited performance returns, I haven't implemented this
in Listing One.
Coming Up
Next time, we may do some 256-color animation. Or we may poke into the
innards of the new 15-bpp VGAs. Or perhaps we'll take a look at RenderMan.
Who knows? If you have any preferences, by all means drop me a line.