home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / gems / g_gemsi.lha / GraphicsGems / ConcaveScan.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-10  |  4.9 KB  |  171 lines
  1. /* 
  2. Concave Polygon Scan Conversion
  3. by Paul Heckbert
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. /*
  8.  * concave: scan convert nvert-sided concave non-simple polygon
  9.  * with vertices at (point[i].x, point[i].y) for i in 
  10.  * [0..nvert-1] within the window win by
  11.  * calling spanproc for each visible span of pixels.
  12.  * Polygon can be clockwise or counterclockwise.
  13.  * Algorithm does uniform point sampling at pixel centers.
  14.  * Inside-outside test done by Jordan's rule: a point is 
  15.  * considered inside if an emanating ray intersects the polygon 
  16.  * an odd number of times.
  17.  * drawproc should fill in pixels from xl to xr inclusive on scanline y,
  18.  * e.g:
  19.  *    drawproc(y, xl, xr)
  20.  *    int y, xl, xr;
  21.  *    {
  22.  *        int x;
  23.  *        for (x=xl; x<=xr; x++)
  24.  *            pixel_write(x, y, pixelvalue);
  25.  *    }
  26.  *
  27.  *  Paul Heckbert    30 June 81, 18 Dec 89
  28.  */
  29.  
  30. #include <stdio.h>
  31. #include <math.h>
  32. #include "GraphicsGems.h"
  33.  
  34. #define ALLOC(ptr, type, n) \
  35.           ASSERT(ptr = (type *)malloc((n)*sizeof(type)))
  36.  
  37. typedef struct {        /* window: a discrete 2-D rectangle */
  38.     int x0, y0;            /* xmin and ymin */
  39.     int x1, y1;            /* xmax and ymax (inclusive) */
  40. } Window;
  41.  
  42.  
  43. typedef struct {        /* a polygon edge */
  44.     double x;    
  45.         /* x coordinate of edge's intersection with current scanline */
  46.     double dx;    /* change in x with respect to y */
  47.     int i;    /* edge number: edge i goes from pt[i] to pt[i+1] */
  48. } Edge;
  49.  
  50. static int n;            /* number of vertices */
  51. static Point2 *pt;        /* vertices */
  52.  
  53. static int nact;        /* number of active edges */
  54. static Edge *active;    /* active edge list:edges crossing scanline y */
  55.  
  56. int compare_ind(), compare_active();
  57.  
  58. concave(nvert, point, win, spanproc)
  59. int nvert;            /* number of vertices */
  60. Point2 *point;            /* vertices of polygon */
  61. Window *win;            /* screen clipping window */
  62. void (*spanproc)();        /* called for each span of pixels */
  63. {
  64.     int k, y0, y1, y, i, j, xl, xr;
  65.     int *ind;    /* list of vertex indices, sorted by pt[ind[j]].y */
  66.  
  67.     n = nvert;
  68.     pt = point;
  69.     if (n<=0) return;
  70.     ALLOC(ind, int, n);
  71.     ALLOC(active, Edge, n);
  72.  
  73.     /* create y-sorted array of indices ind[k] into vertex list */
  74.     for (k=0; k<n; k++)
  75.         ind[k] = k;
  76.     qsort(ind, n, sizeof ind[0], compare_ind);
  77.                     /* sort ind by pt[ind[k]].y */
  78.  
  79.     nact = 0;                /* start with empty active list */
  80.     k = 0;                /* ind[k] is next vertex to process */
  81.     y0 = MAX(win->y0, ceil(pt[ind[0]].y-.5));
  82.                                         /* ymin of polygon */
  83.     y1 = MIN(win->y1, floor(pt[ind[n-1]].y-.5));
  84.                                         /* ymax of polygon */
  85.  
  86.     for (y=y0; y<=y1; y++) {  /* step through scanlines */
  87.  
  88.         /* scanline y is at y+.5 in continuous coordinates */
  89.         /* Check vertices between previous scanline  */
  90.         /* and current one, if any */
  91.  
  92.         for (; k<n && pt[ind[k]].y<=y+.5; k++) {
  93.                /* to simplify, if pt.y=y+.5, pretend it's above */
  94.                /* invariant: y-.5 < pt[i].y <= y+.5 */
  95.             i = ind[k];    
  96.               /*
  97.              * insert or delete edges before and after
  98.             * vertex i  (i-1 to i, and i to i+1) from active                 * list if they cross scanline y
  99.             */
  100.             j = i>0 ? i-1 : n-1;    /* vertex previous to i */
  101.             if (pt[j].y <= y-.5)
  102.             /* old edge, remove from active list */
  103.                 delete(j);
  104.             else if (pt[j].y > y+.5)
  105.             /* new edge, add to active list */
  106.                 insert(j, y);
  107.             j = i<n-1 ? i+1 : 0;    /* vertex next after i */
  108.             if (pt[j].y <= y-.5)
  109.             /* old edge, remove from active list */
  110.                 delete(i);
  111.             else if (pt[j].y > y+.5)
  112.             /* new edge, add to active list */
  113.                 insert(i, y);
  114.         }
  115.  
  116.         /* sort active edge list by active[j].x */
  117.         qsort(active, nact, sizeof active[0], compare_active);
  118.  
  119.         /* draw horizontal segments for scanline y */
  120.         for (j=0; j<nact; j+=2) { /* draw horizontal segments */
  121.         /* span 'tween j & j+1 is inside, span tween */
  122.         /* j+1 & j+2 is outside */
  123.             xl = ceil(active[j].x-.5);    /* left end of span */
  124.             if (xl<win->x0) xl = win->x0;
  125.             xr = floor(active[j+1].x-.5);
  126.                                         /* right end of span */
  127.             if (xr>win->x1) xr = win->x1;
  128.             if (xl<=xr)
  129.             (*spanproc)(y, xl, xr);
  130.                         /* draw pixels in span */
  131.             active[j].x += active[j].dx;
  132.                         /* increment edge coords */
  133.             active[j+1].x += active[j+1].dx;
  134.           }
  135.     }
  136. }
  137.  
  138.  
  139. static delete(i)        /* remove edge i from active list */
  140. int i;
  141. {
  142.     int j;
  143.  
  144.     for (j=0; j<nact && active[j].i!=i; j++);
  145.     if (j>=nact) return;
  146.         /* edge not in active list; happens at win->y0*/
  147.     nact--;
  148.     bcopy(&active[j+1], &active[j], (nact-j)*sizeof active[0]);
  149. }
  150.  
  151. static insert(i, y)        /* append edge i to end of active list */
  152. int i, y;
  153. {
  154.     int j;
  155.     double dx;
  156.     Point2 *p, *q;
  157.  
  158.     j = i<n-1 ? i+1 : 0;
  159.     if (pt[i].y < pt[j].y) {p = &pt[i]; q = &pt[j];}
  160.     else           {p = &pt[j]; q = &pt[i];}
  161.     /* initialize x position at intersection of edge with scanline y */
  162.     active[nact].dx = dx = (q->x-p->x)/(q->y-p->y);
  163.     active[nact].x = dx*(y+.5-p->y)+p->x;
  164.     active[nact].i = i;
  165.     nact++;
  166. }
  167.  
  168. /* comparison routines for qsort */
  169. compare_ind(u, v) int *u, *v; {return pt[*u].y <= pt[*v].y ? -1 : 1;}
  170. compare_active(u, v) Edge *u, *v; {return u->x <= v->x ? -1 : 1;}
  171.