Previous Table of Contents Next

Complex Polygon Filling: An Implementation

Listing 40.1 just shown presents a function, FillPolygon(), that fills polygons of all shapes. If CONVEX_FILL_LINKED is defined, the fast convex fill code from Chapter 39 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 40.1 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 40.2 provides the actual drawing code used to fill spans, built on a draw pixel routine that is the only hardware dependency anywhere in the C code. Listing 40.3 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 Chapter 39. (They may have the same name but are not the same file!) Listing 40.4 is a sample program that, when linked to Listings 40.1 and 40.2, demonstrates drawing polygons of various sorts.

LISTING 40.2 L40-2.C

 /* Draws all pixels in the horizontal line segment passed in, from
    (LeftX,Y) to (RightX,Y), in the specified color in mode 13h, the
    VGA’s 320x200 256-color mode. Both LeftX and RightX are drawn. No
    drawing will take place if LeftX > RightX. */

 #include <dos.h>
 #include “polygon.h”

 #define SCREEN_WIDTH    320
 #define SCREEN_SEGMENT  0xA000

 static void DrawPixel(int, int, int);

 void DrawHorizontalLineSeg(Y, LeftX, RightX, Color) {
    int X;

    /* Draw each pixel in the horizontal line segment, starting with
       the leftmost one */
    for (X = LeftX; X <= RightX; X++)
       DrawPixel(X, Y, Color);

 /* Draws the pixel at (X, Y) in color Color in VGA mode 13h */
 static void DrawPixel(int X, int Y, int Color) {
    unsigned char far *ScreenPtr;

 #ifdef __TURBOC__
 #else    /* MSC 5.0 */
    FP_OFF(ScreenPtr) = Y * SCREEN_WIDTH + X;
    *ScreenPtr = (unsigned char) Color;


 /* POLYGON.H: Header file for polygon-filling code */

 #define CONVEX    0
 #define NONCONVEX 1
 #define COMPLEX   2

 /* Describes a single point (used for a single vertex) */
 struct Point {
    int X;   /* X coordinate */
    int Y;   /* Y coordinate */
 /* Describes a series of points (used to store a list of vertices that
    describe a polygon; each vertex connects to the two adjacent
    vertices; the last vertex is assumed to connect to the first) */
 struct PointListHeader {
    int Length;                /* # of points */
    struct Point * PointPtr;   /* pointer to list of points */
 /* Describes the beginning and ending X coordinates of a single
    horizontal line (used only by fast polygon fill code) */
 struct HLine {
    int XStart; /* X coordinate of leftmost pixel in line */
    int XEnd;   /* X coordinate of rightmost pixel in line */
 /* Describes a length-long series of horizontal lines, all assumed to
    be on contiguous scan lines starting at YStart and proceeding
    downward (used to describe a scan-converted polygon to the
    low-level hardware-dependent drawing code) (used only by fast
    polygon fill code). */
 struct HLineList {
    int Length;                /* # of horizontal lines */
    int YStart;                /* Y coordinate of topmost line */
    struct HLine * HLinePtr;   /* pointer to list of horz lines */

LISTING 40.4 L40-4.C

 /* Sample program to exercise the polygon-filling routines */

 #include <conio.h>
 #include <dos.h>
 #include “polygon.h”

 #define DRAW_POLYGON(PointList,Color,Shape,X,Y)             \
    Polygon.Length = sizeof(PointList)/sizeof(struct Point); \
    Polygon.PointPtr = PointList;                            \
    FillPolygon(&Polygon, Color, Shape, X, Y);

 void main(void);
 extern int FillPolygon(struct PointListHeader *, int, int, int, int);

 void main() {
    int i, j;
    struct PointListHeader Polygon;
    static struct Point Polygon1[] =
    static struct Point Polygon2[] =
    static struct Point Polygon3[] =
    static struct Point Polygon4[] =
    static struct Point Triangle1[] = {{30,0},{15,20},{0,0}};
    static struct Point Triangle2[] = {{30,20},{15,0},{0,20}};
    static struct Point Triangle3[] = {{0,20},{20,10},{0,0}};
    static struct Point Triangle4[] = {{20,20},{20,0},{0,10}};
    union REGS regset;

    /* Set the display to VGA mode 13h, 320×200 256-color mode */ = 0×0013;
    int86(0x10, ®set, ®set);

    /* Draw three complex polygons */
    DRAW_POLYGON(Polygon1, 15, COMPLEX, 0, 0);
    getch();    /* wait for a keypress */
    DRAW_POLYGON(Polygon2, 5, COMPLEX, 0, 0);
    getch();    /* wait for a keypress */
    DRAW_POLYGON(Polygon3, 3, COMPLEX, 0, 0);
    getch();    /* wait for a keypress */

    /* Draw some adjacent nonconvex polygons */
    for (i=0; i<5; i++) {
       for (j=0; j<8; j++) {
          DRAW_POLYGON(Polygon4, 16+i*8+j, NONCONVEX, 40+(i*60),
    getch();    /* wait for a keypress */

    /* Draw adjacent triangles across the screen */
    for (j=0; j<=80; j+=20) {
       for (i=0; i<290; i += 30) {
          DRAW_POLYGON(Triangle1, 2, CONVEX, i, j);
          DRAW_POLYGON(Triangle2, 4, CONVEX, i+15, j);
    for (j=100; j<=170; j+=20) {
       /* Do a row of pointing-right triangles */
       for (i=0; i<290; i += 20) {
          DRAW_POLYGON(Triangle3, 40, CONVEX, i, j);
       /* Do a row of pointing-left triangles halfway between one row
          of pointing-right triangles and the next, to fit between */
       for (i=0; i<290; i += 20) {
          DRAW_POLYGON(Triangle4, 1, CONVEX, i, j+10);
    getch();    /* wait for a keypress */

    /* Return to text mode and exit */ = 0x0003;
    int86(0x10, &regset, &regset);

Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash