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.