The Polygon Primeval

 Journal:   Dr. Dobb's Journal  Feb 1991 v16 n2 p153(7)
 -----------------------------------------------------------------------------
 Title:     The polygon primeval. (filling polygons) (column)
 Author:    Abrash, Michael.
 AttFile:    Program:  GP-FEB91.ASC  Source code listing.

 Summary:   The first in a series of columns develops routines to draw filled
            polygons.  Filled polygons, which are essentially any closed form
            filled with pixels in a consistent color or pattern, are useful
            for a variety of graphics constructs.  Polygons are divisible into
            convex, nonconvex and complex shapes.  Filling a polygon is
            fundamentally a rasterization process involving drawing all of the
            horizontal lines within the polygon's boundaries.  Problems that
            must be resolved include defining which pixels are within each
            polygon and ensuring that multiple polygons can fit together
            without overlapping.  A line-tracing algorithm is modified so that
            it contains only pixels that are truly within the polygon.  Rules
            and routines are developed to fit polygons together without
            overlapping and fill them.
 -----------------------------------------------------------------------------
 Descriptors..
 Topic:     Graphic Forms
            Computer Graphics
            Mathematics of Computing
            Methods
            Painting
            Algorithms
            Programming Instruction
            Geometry.
 Feature:   illustration
            chart
            program.
 Caption:   A standard line-drawing algorithm can select polygon-boundary
            pixels. (chart)
            Overlaying of filled polygons. (chart)
            Routine to color-fill a convex polygon. (program)

 -----------------------------------------------------------------------------
 Full Text:

 "Give me but one firm spot on which to stand, and I will move the Earth.  "

 -Archimedes

 Were Archimedes alive today, he might say, "Give me but one fast polygon-fill
 routine on which to call, and I will draw the Earth." Programmers often think
 of pixel drawing as being the basic graphics primitive, but filled polygons
 are equally fundamental and far more useful.  Filled polygons can be used for
 constructs as diverse as a single pixel or a 3-D surface, and virtually
 everything in between.

 I'll spend some time in this column developing routines to draw filled
 polygons and building more sophisticated graphics operations atop those
 routines, Sooner, rather than later, I'll get to 2-D manipulation and
 animation of polygonbased entities (with occasional diversions to Other
 graphics topics of interest), leading uP to an exploration of 3-D graphics.
 You can't get there from here without laying some groundwork, though, so this
 month I'll begin with the basics of filling a polygon.  Next month, we'll see
 how to draw a polygon considerably faster.  That will set the tone for this
 column: High-level exploration of a graphics topic first, followed by a
 speedy hardware-specific implementation for the IBM PCNGA combination, the
 most widely used graphics system around.  Abstract, machine-independent
 graphics is a thing of beauty, but only by understanding graphics at all
 levels, including the hardware, can YOu boost performance into the realm of
 the sublime.

 And slow computer graphics is scarcely worth the bother.  Filled Polygons A
 polygon is simply a shape formed by lines laid end to end to form a
 continuous, closed path.  A polygon is filled by setting afl pixels within
 the polygon's boundaries to a color or pattern.  For now, we'll work only
 with polygons filled with solid colors.

 You can divide polygons into three categories: convex, nonconvex, and
 complex, as shown in Convex polygons include what you'd normally thingk of as
 " convex" and mole; as far as we're concerned, a convex polygon is on, for
 which any horizontal line drawn through the polygon encounters the right edge
 exactly once and the left edge exactly once, excluding horizontal and
 zero-length edge segments.  Put another way, neither the right nor left edge
 of a convex polygon ever reverses direction from uP to down, or vice-versa.
 Also, the right and left edges of a convex polygon may not cross each other,
 although they may touch so long as the right edge never crosses over to the
 left side of the left edge.  (Check out the second polygon drawn in Listing
 Three, page 166, which certainly isn't convex in the normal sense.) The
 boundaries of nonconvex polygons, on the other hand, can go in whatever
 directions they please, so long as they never cross.  Complex polygons can
 have any boundaries you might imagine, which makes for interesting problems
 in deciding which interior spaces to fill and which not.  Each category is a
 superset of the previous one.

 Why bother to distinguish between convex, nonconvex, and complex polygons?
 For peformance, especially when it comes to filling convex polygons.  It's
 with filled convex polygons that we're going to start; they're widely useful
 and will serve well to introduce some of the subtler complexities of polygon
 drawing, not the least of which is the slippery concept of "inside." Which
 Side is inside? The basic principle of polygon filling is decomposing each
 polygon into a series of horizontal fines, one for each horizontal row of
 pixels, or scan line, within the polygon (a process I'll call scan
 conversion), and drawing the horizontal lines.  I'll refer to the entire
 process as rasterization.  Rasterization of convex polygons is easily done by
 starting at the top of the polygon and tracing down the left and right sides,
 one scan line (one vertical pixel) at a time, filling the extent between the
 two edges on each scan line, until the bottom of the polygon is reached.  At
 first glance, rasterization does not seem to be particularly complicated,
 although it should be apparent that this simple approach is inadequate for
 nonconvex polygons.

 There are a couple of complications, however.  The lesser complication is how
 to rasterize the polygon efficiently, given that it's difficult to write fast
 code that simultaneously traces two edges and flus the space between them.
 The solution is decoupling the process of scan-converting the polygon into a
 list of horizontal lines from that of drawing the horizontal lines.  One
 device-independent routine can trace along the two edges and build a list of
 the beginning and end coordinates of the polygon on each raster line.  Then a
 second, device-specific routine can draw from the list after the entire
 polygon has been scanned.  We'll see this in action shortly.

 The second, greater complication arises because the definition of which
 pixels are "within" a polygon is a more complicated matter than you might
 imagine.  You might think that scan-converting an edge of a polygon is
 analogous to drawing a line from one vertex to the next, but this is not so.
 A line by itself is a one-dimensional construct, and as such is approximated
 on a display by drawing the pixels nearest to the line on either side of the
 true line.  A line serving as a polygon boundary, on the other hand, is part
 of a two-dimensional object.  When filling a polygon, we want to draw the
 pixels within the polygon, but a standard vertex-to-vertex linedrawing
 algorithm will draw many pixels outside the polygon, as shown in Figure 2.

 It's no crime to use standard lines to trace out a polygon, rather than
 drawing only interior pixels.  In fact, there are certain advantages: For
 example, the edges of a filled polygon will match the edges of the same
 polygon drawn unfilled.  Such polygons will look pretty much as they're
 supposed to, and all drawing on raster displays is, after all, only an
 approximation of an ideal.

 There's one great drawback to tracing polygons with standard lines, however:
 Adjacent polygons won't fit together properly, as shown in Figure 3.  If you
 use six equilateral triangles to make a hexagon, for example, the edges of
 the triangles will overlap when traced with standard lines, and more recently
 drawn triangles will wipe out portions of their predecessors.  Worse still,
 odd color effects will show up along the polygon boundaries if exclusive-or
 drawing is used.  Consequently, filling out to the boundary lines just won't
 do for drawing images composed of fitted together polygons.  And because
 fitting polygons together is exactly what I have in mind, we need a different
 approach.  How Do You Fit Polygons Together? How, then, do you fit polygons
 together? Very carefully.  First, the line-tracing algorithm must be adjusted
 so that it selects only those pixels that are truly inside the polygon.  This
 basically requires shifting a standard line-drawing algorithm horizontally by
 one half-pixel toward the polygon's interior.  That leaves the issue of how
 to handle points that are exactly on the boundary, and points that lie at
 vertices, so that those points are drawn once and only once.  To deal with
 that, we're going to adopt the following rules:

 Points located exactly on nonhorizontal edges are drawn only if the interior
 of the polygon is directly to the right (left edges are drawn, right edges
 aren't).  9 Points located exactly on horizontal edges are drawn only if the
 interior of the polygon is directly below them (horizontal top edges are
 drawn, horizontal bottom edges aren't).

 A vertex is drawn only if afl lines ending at that point meet the above
 conditions (no right or bottom edges end at that point).

 All edges of a polygon except those that are flat tops or flat bottoms will
 be considered either right edges or left edges, regardless of slope.  The
 left edge is the one that starts with the leftmost line down from the top of
 the polygon.

 These rules ensure that no pixel is drawn more than once when adjacent
 polygons are fined, and that if polygons cover the full 360-degree range
 around a pixel, then that pixel will be drawn once and only once - just what
 we need in order to be able to fit filled polygons together seamlessly.

 This sort of non-overlapping polygon filling isn't ideal for all purposes.
 Polygons are skewed toward the top and left edges, which not only introduces
 drawing error relative to the ideal polygon but also means that a filled
 polygon won't match the same polygon drawn unfilled.  Narrow wedges and
 one-pixel-wide polygons will show up spottily.  All in all, the choice of
 polygon-filling approach depends entirely on the ways in which the filled
 polygons will be used.

 For our purposes, nonoverlapping polygons are the way to go, so let's have at
 them.

 Non-overlapping Convex Polygons Made Easy

 Without further ado, Listing One (page 164) contains a function,
 FillConvexPolygon, that accepts a list of points that describe a convex
 polygon, with the last point assumed to connect to the first, and scans it
 into a list of lines to flU, then passes that list to the function
 DrawHorizontalLineList Listing Two (page 165).  Listing Three (page 166) is a
 sample program that calls FillConvexPolygon to draw polygons of various
 sorts, and Listing Four (page 166) is a header file included by the other
 listings.

 Listing Two isn't particularly interesting; it merely draws each horizontal
 line in the passed-in list in the simplest possible way, one pixel at a time.
 NO, that doesn't make the pixel the fundamental primitive; next month I'll
 replace Listing Two with a much faster version that doesn't bother with
 individual pixels at all.)

 Listing One is where the action is this month.  Our goal is to scan out the
 left and right edges of each polygon so that all points inside and no points
 outside the polygon are drawn, and so that all points located exactly on the
 boundary are drawn only if they are not on right or bottom edges.  That's
 precisely what Listing One does; here's how.

 Listing one first finds the top and bottom of the polygon, then works out
 from the top point to find the two ends of the top edge.  If the ends are at
 different locations, the top is flat, which has two implications.  Firstly,
 it's easy to find the starting vertices and directions through the vertex
 list for the left and right edges.  (To scan-convert them properly, we must
 first determine which edge is which.) Secondly, the top scan line of the
 polygon should be drawn without the rightmost pixel, because only the
 rightmost pixel of the horizontal edge that makes up the top scan line is
 part of a right edge.

 if, on the other hand, the ends of the top edge are at the same location,
 then the top is pointed.  In that case, the top scan line of the polygon
 isn't drawn; it's part of the right-edge line that starts at the top vertex.
 it's part of a left-edge line, too, but the right edge overrides.) When the
 top isn't flat, it's more difficult to tell in which direction through the
 vertex list the right and left edges go, because both edges start at the top
 vertex.  The solution is to compare the slopes from the top vertex to ends of
 the two lines coming out of it in order to see which is leftmost.  The
 calculations in Listing One involving the various deltas do this, using a
 slightly rearranged form of the equation: DeltaYN/DeltaXN > DeltaYP/DeltaXP

 Once we know where the left edge starts in the vertex list, we can
 scan-convert it a line at a time until the bottom vertex is reached.  Each
 point is stored as the starting X coordinate for the corresponding scan line
 in the list we'll pass to DrawHorizontalLineList.  The nearest X coordinate
 on each scan line that's on or to the right of the left edge is selected.
 The last point of each line making up the left edge isn't scan-converted,
 producing two desirable effects.  First, it avoids drawing each vertex twice;
 two lines come into every vertex, but we want to scan-convert each vertex
 only once.  Second, not scan-converting the last point of each line causes
 the bottom scan line of the polygon not to be drawn, as required by our
 rules.  The first scan line of the polygon is also skipped if the top isn't
 flat.

 Now we need to scan-convert the right edge into the ending X coordinate
 fields of the line list.  This is performed in the same manner as for the
 left edge, except that every line in the right edge is moved one pixel to the
 left before being scan-converted.  Why? We want the nearest point to the left
 of but not on the right edge, so that the right edge itself isn't drawn.  As
 it happens, drawing the nearest point on or to the right of a line moved one
 pixel to the left is exactly the same as drawing the nearest point to the
 left of but not on that line in its original location.  Sketch it out and
 you'll see what I mean.

 Once the two edges are scan-converted, the whole line list is passed to
 DrawHorizontalLineList, and the polygon is drawn.

 Finis.  Oddball Cases Listing One handles zero-length segments (multiple
 vertices at the same location) by ignoring them, which will be useful down
 the road because scaled down polygons can end up with nearby vertices moved
 to the same location.  Horizontal line segments are fine anywhere in a
 polygon, too.  Basically, Listing One scan-converts between active edges (the
 edges that define the extent of the polygon on each scan line) and both
 horizontal and zero-length lines are non-active; neither advances to another
 scan line, so they don't affect the edges being scanned.

 Book of the Month

 The book of the month is the second edition of Foley and van Dam's classic
 Fundamentals of Interactive Computer Graphics, the inspiration and primary
 reference for much of the nonmachinespecific material I'll present in this
 column.  The almost entirely rewritten new version, retitled Computer
 Graphics: Principles and Practice (AddisonWesley, 1990, $64.50), nearly
 doubles the size of the first tome, to a total of 1174 pages.  You'll wish it
 were longer, too, because computer graphics has become such a broad field
 that even this massive book often merely touches on an area, providing the
 fundamental concepts, equations, and algorithms, and moves on.  Still, just
 about everything you could want to know is in there somewhere.  Truly a book
 to lose yourself in, and highly recommended.

 Coming Up Next

 This month's code merely demonstrates the principles of filling convex
 polygons, and is by no means fast.  Next month, we'll spice things up by
 eliminating the floating point calculations and pixel-at-a-time drawing and
 tossing a little assembly language into the mix.

 [BACK] Back

Discuss this article in the forums


Date this article was posted to GameDev.net: 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 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!