home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 505a.lha / GrapicsGems / SeedFill.c < prev    next >
Text File  |  1991-05-01  |  2KB  |  81 lines
  1. /*
  2.  * A Seed Fill Algorithm
  3.  * by Paul Heckbert
  4.  * from "Graphics Gems", Academic Press, 1990
  5.  */
  6.  
  7. /*
  8.  * fill.c : simple seed fill program
  9.  * Calls pixelread() to read pixels, pixelwrite() to write pixels.
  10.  *
  11.  * Paul Heckbert    13 Sept 1982, 28 Jan 1987
  12.  */
  13.  
  14. typedef struct {        /* window: a discrete 2-D rectangle */
  15.     int x0, y0;            /* xmin and ymin */
  16.     int x1, y1;            /* xmax and ymax (inclusive) */
  17. } Window;
  18.  
  19. typedef int Pixel;        /* 1-channel frame buffer assumed */
  20.  
  21. Pixel pixelread();
  22.  
  23. typedef struct {short y, xl, xr, dy;} Segment;
  24. /*
  25.  * Filled horizontal segment of scanline y for xl<=x<=xr.
  26.  * Parent segment was on line y-dy.  dy=1 or -1
  27.  */
  28.  
  29. #define MAX 10000        /* max depth of stack */
  30.  
  31. #define PUSH(Y, XL, XR, DY)    /* push new segment on stack */ \
  32.     if (sp<stack+MAX && Y+(DY)>=win->y0 && Y+(DY)<=win->y1) \
  33.     {sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;}
  34.  
  35. #define POP(Y, XL, XR, DY)    /* pop segment off stack */ \
  36.     {sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;}
  37.  
  38. /*
  39.  * fill: set the pixel at (x,y) and all of its 4-connected neighbors
  40.  * with the same pixel value to the new pixel value nv.
  41.  * A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
  42.  */
  43.  
  44. fill(x, y, win, nv)
  45. int x, y;    /* seed point */
  46. Window *win;    /* screen window */
  47. Pixel nv;    /* new pixel value */
  48. {
  49.     int l, x1, x2, dy;
  50.     Pixel ov;    /* old pixel value */
  51.     Segment stack[MAX], *sp = stack;    /* stack of filled segments */
  52.  
  53.     ov = pixelread(x, y);        /* read pv at seed point */
  54.     if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1) return;
  55.     PUSH(y, x, x, 1);            /* needed in some cases */
  56.     PUSH(y+1, x, x, -1);        /* seed segment (popped 1st) */
  57.  
  58.     while (sp>stack) {
  59.     /* pop segment off stack and fill a neighboring scan line */
  60.     POP(y, x1, x2, dy);
  61.     /*
  62.      * segment of scan line y-dy for x1<=x<=x2 was previously filled,
  63.      * now explore adjacent pixels in scan line y
  64.      */
  65.     for (x=x1; x>=win->x0 && pixelread(x, y)==ov; x--)
  66.         pixelwrite(x, y, nv);
  67.     if (x>=x1) goto skip;
  68.     l = x+1;
  69.     if (l<x1) PUSH(y, l, x1-1, -dy);        /* leak on left? */
  70.     x = x1+1;
  71.     do {
  72.         for (; x<=win->x1 && pixelread(x, y)==ov; x++)
  73.         pixelwrite(x, y, nv);
  74.         PUSH(y, l, x-1, dy);
  75.         if (x>x2+1) PUSH(y, x2+1, x-1, -dy);    /* leak on right? */
  76. skip:        for (x++; x<=x2 && pixelread(x, y)!=ov; x++);
  77.         l = x;
  78.     } while (x<=x2);
  79.     }
  80. }
  81.