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

# Linux Cross ReferenceTina4/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 ] ~