home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / gems / g_gemsi.lha / GraphicsGems / SeedFill.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-10  |  2.4 KB  |  85 lines
  1. /*
  2. A Seed Fill Algorithm
  3. by Paul Heckbert
  4. from "Grahics 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. /*
  40.  * fill: set the pixel at (x,y) and all of its 4-connected neighbors
  41.  * with the same pixel value to the new pixel value nv.
  42.  * A 4-connected neighbor is a pixel above, below, left, or right of
  43.  * a pixel.
  44.  */
  45.  
  46. fill(x, y, win, nv)
  47. int x, y;    /* seed point */
  48. Window *win;    /* screen window */
  49. Pixel nv;    /* new pixel value */
  50. {
  51.     int l, x1, x2, dy;
  52.     Pixel ov;    /* old pixel value */
  53.     Segment stack[MAX], *sp = stack;    /* stack of filled segments */
  54.  
  55.     ov = pixelread(x, y);        /* read pv at seed point */
  56.     if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1)
  57.     return;
  58.     PUSH(y, x, x, 1);            /* needed in some cases */
  59.     PUSH(y+1, x, x, -1);        /* seed segment (popped 1st) */
  60.  
  61.     while (sp>stack) {
  62.         /* pop segment off stack and fill a neighboring scan line */
  63.         POP(y, x1, x2, dy);
  64.         /*
  65.           * segment of scan line y-dy for x1<=x<=x2 was
  66.          * previously filled,
  67.          * now explore adjacent pixels in scan line y
  68.          */
  69.         for (x=x1; x>=win->x0 && pixelread(x, y)==ov; x--)
  70.             pixelwrite(x, y, nv);
  71.         if (x>=x1) goto skip;
  72.         l = x+1;
  73.         if (l<x1) PUSH(y, l, x1-1, -dy);    /* leak on left? */
  74.         x = x1+1;
  75.         do {
  76.             for (; x<=win->x1 && pixelread(x, y)==ov; x++)
  77.                 pixelwrite(x, y, nv);
  78.             PUSH(y, l, x-1, dy);
  79.             if (x>x2+1) PUSH(y, x2+1, x-1, -dy); /* leak on right? */
  80. skip:        for (x++; x<=x2 && pixelread(x, y)!=ov; x++);
  81.             l = x;
  82.         }     while (x<=x2);
  83.    }
  84. }
  85.