~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/math/draw/polygon.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /* @(#)Concave polygon scan conversion. apply_inside_poly(): scan
  2  * convert nvert-sided concave non-simple polygon with vertices at p[i]
  3  * for i = [0..nvert-1] by calling func() for each visible span of
  4  * pixels; the polygon can be clockwise or counterclockwise. Algorithm
  5  * does uniform point sampling at pixel centres. Inside-outside test is
  6  * done by Jordan's rule: a point is considered to be inside if an
  7  * emanating ray intersects the polygon an odd number of times. func()
  8  * processes the data on line y from lx to ux inclusive.
  9  * 
 10  * Concave Polygon Scan Conversion, by Paul Heckbert; modified by Jim
 11  * Ivins. See Glassner (editor) 1990 "Graphics Gems" p 681 (Academic
 12  * Press) */
 13 #include <tina/math.h>
 14 #include <tina/sysfuncs.h>
 15 
 16 typedef struct
 17 {
 18     double  x;                  /* x coordinate of intersection with
 19                                  * current scanline. */
 20     double  dx;                 /* change in x WRT y. */
 21     int     i;                  /* Edge number: edge i goes from pt[i]
 22                                  * to pt[i+1] */
 23 }
 24 
 25         Poly_edge;
 26 
 27 static Vec2 *pt = NULL;         /* Array of vertices. */
 28 static Poly_edge *active = NULL;/* Active edge list: edges crossing
 29                                  * scanline y. */
 30 
 31 static int compare_ind(const void *u, const void *v)
 32 {
 33     /* Changed by Julian Briggs 2/11/93 to match qsort */
 34     /**
 35       int     ind_u = vec2_y (pt[*(int*)u]);
 36       int     ind_v = vec2_y (pt[*(int*)v]);
 37       **/
 38     int     ind_u = (int) vec2_y(pt[*(int *) u]);
 39     int     ind_v = (int) vec2_y(pt[*(int *) v]);
 40 
 41     return (ind_u == ind_v) ? 0 : (ind_u < ind_v ? -1 : +1);
 42 }
 43 
 44 static int compare_active(const void *u, const void *v)
 45 {
 46     /* Changed by Julian Briggs 2/11/93 to match qsort */
 47     /* return (u->x <= v->x) ? -1 : +1; */
 48     return (((Poly_edge *) u)->x <= ((Poly_edge *) v)->x) ? -1 : +1;
 49 }
 50 
 51 static void delete(int i, int *nact)
 52 {
 53     int     j;
 54 
 55     for (j = 0; active[j].i != i; j++)
 56         if (j >= *nact)
 57             return;
 58     (*nact)--;
 59     memcpy(&active[j], &active[j + 1], (*nact - j) * sizeof(active[0]));
 60 }
 61 
 62 static void insert(int i, int y, int n, int *nact)
 63 {
 64     int     j;
 65     double  dx;
 66     Vec2   *p;
 67     Vec2   *q;
 68 
 69     j = i < n - 1 ? i + 1 : 0;
 70     if (vec2_x(pt[i]) < vec2_x(pt[j]))
 71     {
 72         p = &pt[i];
 73         q = &pt[j];
 74     } else
 75     {
 76         p = &pt[j];
 77         q = &pt[i];
 78     }
 79 
 80     active[*nact].dx = dx = (vec2_x(*q) - vec2_x(*p))
 81         / (vec2_y(*q) - vec2_y(*p));
 82     active[*nact].x = dx * (y + 0.5 - vec2_y(*p)) + vec2_x(*p);
 83     active[*nact].i = i;
 84     (*nact)++;
 85 }
 86 
 87 void    apply_inside_poly(int nvert, Vec2 * p, int max_x, int max_y,
 88                                   void (*func) (), void *data)
 89 {
 90     int     nact;               /* Number of active edges. */
 91     int     k, ly, uy, y, i, j, lx, ux;
 92     int    *ind;                /* Sorted list of vertex indices */
 93 
 94     pt = p;
 95 
 96     if ((nvert <= 0) || !p)
 97         return;
 98 
 99     ind = tvector_alloc(0, nvert, int);
100     active = tvector_alloc(0, nvert, Poly_edge);
101 
102     /* Create a y-sorted array of indices ind[k] into ertex list */
103     for (k = 0; k < nvert; k++)
104         ind[k] = k;
105 
106     qsort(ind, nvert, sizeof(ind[0]), compare_ind);
107 
108     nact = 0;
109     k = 0;
110     /* BUGFIX Julian Briggs 1/11/93: ceil & floor take & return double */
111     ly = MAX(0, (int) ceil((double) vec2_y(pt[ind[0]]) - 0.5)); /* Polygon y min */
112     uy = MIN(max_y - 1,
113              (int) floor((double) vec2_y(pt[ind[nvert - 1]]) - 0.5));   /* Polygon y max */
114 
115     for (y = ly; y <= uy; y++)
116     {
117         for (; k < nvert && vec2_y(pt[ind[k]]) <= y + 0.5; k++)
118         {
119             i = ind[k];
120 
121             j = i > 0 ? i - 1 : nvert - 1;      /* Vertex before i */
122             if (vec2_y(pt[j]) <= y - 0.5)
123                 delete(j, &nact);
124             else if (vec2_y(pt[j]) > y + 0.5)
125                 insert(j, y, nvert, &nact);
126 
127             j = i < nvert - 1 ? i + 1 : 0;      /* Vertex after i */
128             if (vec2_y(pt[j]) <= y - 0.5)
129                 delete(i, &nact);
130             else if (vec2_y(pt[j]) > y + 0.5)
131                 insert(i, y, nvert, &nact);
132         }
133 
134         qsort(active, nact, sizeof(active[0]), compare_active);
135 
136         /* Draw horizontal segments for scanline y. Span between j and
137          * j+1 is inside polygon. Span between j+1 and j+2 is outside
138          * polygon. */
139         for (j = 0; j < nact; j += 2)
140         {
141             lx = (int) ceil(active[j].x - 0.5); /* Left end of span */
142             if (lx < 0)
143                 lx = 0;
144 
145             ux = (int) floor(active[j + 1].x - 0.5);    /* Right end of span */
146             if (ux >= max_x)
147                 ux = max_x - 1;
148 
149             (*func) (y, lx, ux, data);
150 
151             active[j].x += active[j].dx;
152             active[j + 1].x += active[j + 1].dx;
153         }
154     }
155     tvector_free(ind, 0, int);
156     tvector_free(active, 0, Poly_edge);
157 }
158 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.