From cm26+@andrew.cmu.edu Mon Nov 14 00:18:45 1988
Path: leah!itsgw!sun.soe.clarkson.edu!batcomputer!cornell!rochester!pt.cs.cmu.edu!andrew.cmu.edu!cm26+
From: cm26+@andrew.cmu.edu (Curt McDowell)
Newsgroups: comp.graphics
Subject: Re: Fast vector based fill algoritm
Message-ID: 
Date: 14 Nov 88 05:18:45 GMT
References: <344@infocon.se>
Organization: Carnegie Mellon
Lines: 204
In-Reply-To: <344@infocon.se>

> *Excerpts from ext.nn.comp.graphics: 10-Nov-88 Fast vector based fill algo..*
> *Magnus Karlson@infocon.s (792)*
> I forgot to add that the output should go to a plotter and we don't
> have room in memory to first make a normal pixel fill and then convert
> to vectors. So pleace if someone have a better(faster) algoritm then
> the only one we have found in the book Computer Graphics by Hearn & Baker
I've never seen H&B's book.  But it seems to me that a scan conversion algorithm
would be perfect for this.  That is, if the requirement of a "vector-based fill
algorithm" is satisfied by drawing many closely-spaced horizontal and/or
vertical lines on the plotter.

I recently was forced to implement a polygon fill for my Computer Graphics
course :-).  The algorithm we used seems to work very well, even for extremely
convoluted self-intersecting polygons with many vertices.  I'm including the
fully implemented C routines below; the only graphics-system dependent part is
about 2 lines in DrawRuns, and of course a plotter is very good at drawing runs.

I've modified the algorithm to avoid floating point using the ever wonderful
Bresenham method, and implemented it in an impeccable object oriented style.  It
would not be hard to generate a crosshatch-filled polygon by making a second
pass, reversing the interpretation of the X's and Y's.

/*
 * Generalized Polygon Fill
 *
 * Implementation by Curt McDowell,
 * Carnegie Mellon University,
 * for Computer Graphics (15-462),
 * November 13, 1988
 *
 * Takes a raster and a polygon.
 * The polygon is filled within the raster
 * The polygonal area is clipped to the raster bounds.
 * A fill pattern must be specified (by another raster).
 * Current drawing mode is honored (three possibilities).
 */

struct edge {
    struct edge *next;
    long yTop, yBot;
    long xNowWhole, xNowNum, xNowDen, xNowDir;
    long xNowNumStep;
};

#define MAXVERTICAL     1024

private void FillEdges(p, edgeTable)
POLYGON *p;
struct edge *edgeTable[];
{
    int i, j, n = polygon_GetN(p);

    for (i = 0; i < MAXVERTICAL; i++)
        edgeTable[i] = NULL;

    for (i = 0; i < n; i++) {
        POINT *p1, *p2, *p3;
        struct edge *e;
        p1 = polygon_RefNth(p, i);
        p2 = polygon_RefNth(p, (i + 1) % n);
        if (point_GetY(p1) == point_GetY(p2))
            continue;   /* Skip horiz. edges */
        /* Find next vertex not level with p2 */
        for (j = (i + 2) % n; ; j = (j + 1) % n) {
            p3 = polygon_RefNth(p, j);
            if (point_GetY(p2) != point_GetY(p3))
                break;
        }
        e = New(struct edge);
        e->xNowNumStep = ABS(point_GetX(p1) - point_GetX(p2));
        if (point_GetY(p2) > point_GetY(p1)) {
            e->yTop = point_GetY(p1);
            e->yBot = point_GetY(p2);
            e->xNowWhole = point_GetX(p1);
            e->xNowDir = SGN(point_GetX(p2) - point_GetX(p1));
            e->xNowDen = e->yBot - e->yTop;
            e->xNowNum = (e->xNowDen >> 1);
            if (point_GetY(p3) > point_GetY(p2))
                e->yBot--;
        } else {
            e->yTop = point_GetY(p2);
            e->yBot = point_GetY(p1);
            e->xNowWhole = point_GetX(p2);
            e->xNowDir = SGN(point_GetX(p1) - point_GetX(p2));
            e->xNowDen = e->yBot - e->yTop;
            e->xNowNum = (e->xNowDen >> 1);
            if (point_GetY(p3) < point_GetY(p2)) {
                e->yTop++;
                e->xNowNum += e->xNowNumStep;
                while (e->xNowNum >= e->xNowDen) {
                    e->xNowWhole += e->xNowDir;
                    e->xNowNum -= e->xNowDen;
                }
            }
        }
        e->next = edgeTable[e->yTop];
        edgeTable[e->yTop] = e;
    }
}

/*
 * UpdateActive first removes any edges which curY has entirely
 * passed by.  The removed edges are freed.
 * It then removes any edges from the edge table at curY and
 * places them on the active list.
 */

private struct edge *UpdateActive(active, edgeTable, curY)
struct edge *active, *edgeTable[];
long curY;
{
    struct edge *e, **ep;
    for (ep = &active, e = *ep; e != NULL; e = *ep)
        if (e->yBot < curY) {
            *ep = e->next;
            free(e);
        } else
            ep = &e->next;
    *ep = edgeTable[curY];
    return active;
}

/*
 * DrawRuns first uses an insertion sort to order the X
 * coordinates of each active edge.  It updates the X coordinates
 * for each edge as it does this.
 * Then it draws a run between each pair of coordinates,
 * using the specified fill pattern.
 *
 * This routine is very slow and it would not be that
 * difficult to speed it way up.
 */

private void DrawRuns(r, active, curY, pat)
RAS *r;
struct edge *active;
long curY;
RAS *pat;
{
    struct edge *e;
    static long xCoords[100];
    long numCoords = 0;
    int i, x;
    for (e = active; e != NULL; e = e->next) {
        for (i = numCoords; i > 0 &&
          xCoords[i - 1] > e->xNowWhole; i--)
            xCoords[i] = xCoords[i - 1];
        xCoords[i] = e->xNowWhole;
        numCoords++;
        e->xNowNum += e->xNowNumStep;
        while (e->xNowNum >= e->xNowDen) {
            e->xNowWhole += e->xNowDir;
            e->xNowNum -= e->xNowDen;
        }
    }
    if (numCoords % 2)  /* Protect from degenerate polygons */
        xCoords[numCoords] = xCoords[numCoords - 1],
        numCoords++;
    for (i = 0; i < numCoords; i += 2) {
        /* Here's the graphics-dependent part. */
        /* All we need is to draw a horizontal line */
        /* from (xCoords[i], curY) to (xCoords[i + 1], curY). */
        /* Example: I want to fill the polygon with a pattern. */
        /* (This example is very slow because it's done point by */
        /* point, thus not taking advantage of the potential for */
        /* speed afforded by the scan conversion...) */

        for (x = xCoords[i]; x <= xCoords[i + 1]; x++)
            if (ras_TestPointModulo(pat, x, curY))
                ras_Point(r, x, curY);
    }
}

/*
 * This version of the fill takes a fill pattern argument.  It may
 * be removed throughout for straight single-color fills.
 */

void ras_FillPolygon(r, p, pat)
RAS *r;
POLYGON *p;
RAS *pat;
{
    static struct edge *edgeTable[MAXVERTICAL];
    struct edge *active;
    long curY;

    FillEdges(p, edgeTable);

    for (curY = 0; edgeTable[curY] == NULL; curY++)
        if (curY == MAXVERTICAL - 1)
            return;     /* No edges in polygon */

    for (active = NULL; (active = UpdateActive(active,
      edgeTable, curY)) != NULL; curY++)
        DrawRuns(r, active, curY, pat);
}

Curt McDowell
Box 499
5115 Margaret Morriston St.
Pittsburgh, PA 15213
cm26@andrew.cmu.edu
Carnegie Mellon University


�