www.pudn.com > CG2Programs.rar > scanFill.c

/* scanFill, Chapter 3, pp. 122-125 */

/* EXAMPLE STARTS HERE */
#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. */
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 nonhorizontal 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 monotically increasing or decreasing pair of edges */
void makeEdgeRec
  (dcPt lower, dcPt upper, int yComp, Edge * edge, Edge * edges[])
{
  edge->dxPerScan =
    (float) (upper.x - lower.x) / (upper.y - lower.y);
  edge->xIntersect = lower.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 v1, v2;
  int i, yPrev = pts[cnt - 2].y;
  
  v1.x = pts[cnt-1].x; v1.y = pts[cnt-1].y;
  for (i=0; inext;
  while (p) {
    q = p->next;
    insertEdge (active, p);
    p = q;
  }
}

void fillScan (int scan, Edge * active)
{
  Edge * p1, * p2;
  int i;
  
  p1 = active->next;
  while (p1) {
    p2 = p1->next;
    for (i=p1->xIntersect; ixIntersect; i++)
      setPixel ((int) i, scan);
    p1 = 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;
      deleteAfter (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; inext = NULL;
  }
  buildEdgeList (cnt, pts, edges);
  active = (Edge *) malloc (sizeof (Edge));
  active->next = NULL;

  for (scan=0; scannext) {
      fillScan (scan, active);
      updateActiveList (scan, active);
      resortActiveList (active);
    }
  }
  /* Free edge records that have been malloc'ed ... */
}
/* EXAMPLE ENDS HERE */


void main (int argc, char ** argv)
{
  /* A bow-tie polygon */
  dcPt pts[] = {
    WINDOW_WIDTH/4, WINDOW_HEIGHT/4,
    3*WINDOW_WIDTH/4, 3*WINDOW_HEIGHT/4,
    3*WINDOW_WIDTH/4, WINDOW_HEIGHT/4,
    WINDOW_WIDTH/4, 3*WINDOW_HEIGHT/4
    };
  
  long windowID = openGraphics (*argv, WINDOW_WIDTH, WINDOW_HEIGHT);
  
  setBackground (WHITE);
  setColor (BLACK);
  scanFill (4, pts);
  sleep (20);
  closeGraphics (windowID);
}