The Simplicity of complex polygons (poly.filling)

 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
 Topic:     Program Development Techniques
            Graphics Languages
            Type-In Programs
            Graphic Forms
            Two-Dimensional Graphics.
 Feature:   illustration
 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

 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

 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

 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

 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

 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

 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.

 [BACK] Back

Discuss this article in the forums

Date this article was posted to 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Michael Abrash's Articles

© 1999-2011 All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!