Scan-Line Polygon Fill Algorithm

Figure 4.3 illustrates the scan-line procedure for solid filling of polygon areas [6]. For each scan line crossing a polygon, the area-fill algorithm locates the intersection points of the scan line with the polygon edges. These intersection points are then sorted from left to right, and the corresponding frame-buffer positions between each intersection pair are set to the specified fill color. In the example of Fig. 4.3, the four pixel intersection positions with the polygon boundaries define two stretches of interior pixels from x=10 to x=14 and from x=18 to x=24.

Fig.4.3. Scan-Line Procedure

The following procedure [6] performs a solid-fill scan conversion for an input set of polygon vertices. For each scan line within the vertical extents of the polygon, an active edge list is set up and edge intersections are calculated. Across each scan line, the interior fill is then applied between successive pairs of edge intersections, processed from left to right.

#include "device.h"

typedef struct tEdge {

int yUpper;

float xIntersect. dxPerScan;

struct tEdge * next;

} Edge:

/* Inserts edge into list in order of increasing xIntersect field. * I

void insertEdge (Edge ' list, Edge edge)

{

Edge *p, *q = list;

p = q->next;

while (p!= NULL) {

if (edge->xIntersect < p->xIntersect)

p = NULL;

else {

q = P:

p = p->next;

}

}

edge->next = q->next;

q->next = edge;

}

/* For an index, return y-coordinate of next non-horizontal line */

int yNext (int k, int cnt, dcPt * pts)

{

int j;

if ((k+1) > (cnt-1))

j = 0;

else

j = k+1;

while (pts[k].y == pts[j].y)

if ((j+1) > (cnt-1))

j = 0;

else

j++;

return (pts[j].y);

}

/* Store lower-y coordinate and inverse slope for each edge. Adjust and store upper-y coordinate for edges that are the lower member of a monotonically increasing or decreasing pair of edges */

void makeEdgeRec

(dcPt lower, dcPt upper, int yComp, Edge * edge, Edge * edges[])

{

edge->dxPerScan=

(float) upper.x - 1ower.x) / (upper.y - 1ower.y);

edge->xIntersect = 1ower.x;

if (upper.y < yComp)

edge->yUpper = upper.y - 1:

else

edge->yUpper = upper.y;

insertEdge (edges[lower.y], edge);

}

void buildEdgeList (int cnt, dcPt * pts, Edge * edges[])

{

Edge * edge;

dcPt vl, v2;

int i, yPrev = pts[cnt – 2].Y;

v1.x = pts[cnt-1l.x; v1.y = pts[cnt-1l.y;

for (i=O; i<cnt: i++) {

v2 = pts[i];

if (v1.y! = v2.y) (/* non-horizontal line */

edge = (Edge *) malloc (sizeof (Edge));

if (v1.y < v2.y) /* up-going edge */

makeEdgeRec (vl, v2, yNext(i, cnt, pts), edge, edges);

else /* down-going edge */

makeEdgeRec (v2, vl, yPrev, edge,

edges);

}

yPrev = v1.y;

v1 = v2;

}

}

void buildActiveList (int scan, Edge * active,

Edge * edges[])

{

Edge * p, * q;

p = edges[scanl->next;

while (p) {

q = p->next;

insertEdge (active, p);

p = q;

}

}

void fillscan (int scan, Edge * active)

{

Edge * p1, p2;

int i;

pl = active->next;

while (pl) {

p2 = pl->next;

for (i=pl->xIntersect; 1<p2->xIntersect; i++)

setpixel ((int) i, scan);

pl = p2->next

}

}

void deleteAfter (Edge * q)

{

Edge * p = q->next;

q->next = p->next;

free (p);

}

/* Delete completed edges. Update 'xIntersect' field for others */

void updateActiveList (int scan. Edge * active)

{

Edge * q = active, * p = active->next;

while (p)

if (scan >= p->yUpper) {

p = p->next;

deleLeAfter (q);

}

else {

p->xIntersect = p->xIntersect + p->dxPerScan;

q = p;

p = p->next;

}

}

void resortActiveList (Edge * active)

{

Edge * q, * p = active->next;

active->next = NULL;

while (p) {

q = p->next;

insertEdge (active, p);

P = q;

}

)

void scanFill (int cnt, dCPt * pts)

{

Edge * edges [WINDOW_HEIGHT], * active;

int i.scan;

for (i=0; i<WINDOW_HEIGHT; i++){

edges[i] = (Edge *) malloc (sizeof (Edge));

edges[i]->next = NULL;

}

buildEdgeList (cnt, pts, edges);

active = (Edge *) malloc (sizeof (Edge));

active->next = NULL;

for (scan=0; scan<WINDOW_HEIGHT; scan++) {

buildActiveList (scan, active, edges);

if (active->next) {

fillScan (scan, active);

updateActiveList (scan, active);

resortActiveList (active);

}

}

/* Free edge records that have been malloc'ed... */

}

Поиск по сайту: