1 /**********
2 *
3 * Copyright (c) 2003, Division of Imaging Science and Biomedical Engineering,
4 * University of Manchester, UK. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without modification,
7 * are permitted provided that the following conditions are met:
8 *
9 * . Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * . Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * . Neither the name of the University of Manchester nor the names of its
17 * contributors may be used to endorse or promote products derived from this
18 * software without specific prior written permission.
19 *
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 *
33 **********
34 *
35 * Program : TINA
36 * File : $Source: /home/tina/cvs/tina-libs/tina/math/mathDraw_polygon.c,v $
37 * Date : $Date: 2005/01/09 17:49:25 $
38 * Version : $Revision: 1.4 $
39 * CVS Id : $Id: mathDraw_polygon.c,v 1.4 2005/01/09 17:49:25 paul Exp $
40 *
41 * Author : Legacy TINA
42 *
43 * Notes :
44 * @(#)Concave polygon scan conversion. apply_inside_poly(): scan
45 * convert nvert-sided concave non-simple polygon with vertices at p[i]
46 * for i = [0..nvert-1] by calling func() for each visible span of
47 * pixels; the polygon can be clockwise or counterclockwise. Algorithm
48 * does uniform point sampling at pixel centres. Inside-outside test is
49 * done by Jordan's rule: a point is considered to be inside if an
50 * emanating ray intersects the polygon an odd number of times. func()
51 * processes the data on line y from lx to ux inclusive.
52 *
53 * Concave Polygon Scan Conversion, by Paul Heckbert; modified by Jim
54 * Ivins. See Glassner (editor) 1990 "Graphics Gems" p 681 (Academic
55 * Press)
56 *
57 *********
58 */
59
60 #include "mathDraw_polygon.h"
61
62 #if HAVE_CONFIG_H
63 # include <config.h>
64 #endif
65
66 #include <math.h>
67 #include <stdlib.h>
68 #include <string.h>
69 #include <tina/sys/sysPro.h>
70 #include <tina/math/math_DrawDef.h>
71 #include <tina/math/math_GeomDef.h>
72 #include <tina/math/math_GeomPro.h>
73
74 static Vec2 *pt = NULL; /* Array of vertices. */
75 static Poly_edge *active = NULL;/* Active edge list: edges crossing
76 * scanline y. */
77
78
79
80 static int compare_ind(const void *u, const void *v)
81 {
82 /* Changed by Julian Briggs 2/11/93 to match qsort */
83 /**
84 int ind_u = vec2_y (pt[*(int*)u]);
85 int ind_v = vec2_y (pt[*(int*)v]);
86 **/
87 int ind_u = (int) vec2_y(pt[*(int *) u]);
88 int ind_v = (int) vec2_y(pt[*(int *) v]);
89
90 return (ind_u == ind_v) ? 0 : (ind_u < ind_v ? -1 : +1);
91 }
92
93 static int compare_active(const void *u, const void *v)
94 {
95 /* Changed by Julian Briggs 2/11/93 to match qsort */
96 /* return (u->x <= v->x) ? -1 : +1; */
97 return (((Poly_edge *) u)->x <= ((Poly_edge *) v)->x) ? -1 : +1;
98 }
99
100 static void delete(int i, int *nact)
101 {
102 int j;
103
104 for (j = 0; active[j].i != i; j++)
105 if (j >= *nact)
106 return;
107 (*nact)--;
108 memcpy(&active[j], &active[j + 1], (*nact - j) * sizeof(active[0]));
109 }
110
111 static void insert(int i, int y, int n, int *nact)
112 {
113 int j;
114 double dx;
115 Vec2 *p;
116 Vec2 *q;
117
118 j = i < n - 1 ? i + 1 : 0;
119 if (vec2_x(pt[i]) < vec2_x(pt[j]))
120 {
121 p = &pt[i];
122 q = &pt[j];
123 } else
124 {
125 p = &pt[j];
126 q = &pt[i];
127 }
128
129 active[*nact].dx = dx = (vec2_x(*q) - vec2_x(*p))
130 / (vec2_y(*q) - vec2_y(*p));
131 active[*nact].x = dx * (y + 0.5 - vec2_y(*p)) + vec2_x(*p);
132 active[*nact].i = i;
133 (*nact)++;
134 }
135
136 void apply_inside_poly(int nvert, Vec2 * p, int max_x, int max_y,
137 void (*func) (), void *data)
138 {
139 int nact; /* Number of active edges. */
140 int k, ly, uy, y, i, j, lx, ux;
141 int *ind; /* Sorted list of vertex indices */
142
143 pt = p;
144
145 if ((nvert <= 0) || !p)
146 return;
147
148 ind = tvector_alloc(0, nvert, int);
149 active = tvector_alloc(0, nvert, Poly_edge);
150
151 /* Create a y-sorted array of indices ind[k] into ertex list */
152 for (k = 0; k < nvert; k++)
153 ind[k] = k;
154
155 qsort(ind, nvert, sizeof(ind[0]), compare_ind);
156
157 nact = 0;
158 k = 0;
159 /* BUGFIX Julian Briggs 1/11/93: ceil & floor take & return double */
160 ly = MAX(0, (int) ceil((double) vec2_y(pt[ind[0]]) - 0.5)); /* Polygon y min */
161 uy = MIN(max_y - 1,
162 (int) floor((double) vec2_y(pt[ind[nvert - 1]]) - 0.5)); /* Polygon y max */
163
164 for (y = ly; y <= uy; y++)
165 {
166 for (; k < nvert && vec2_y(pt[ind[k]]) <= y + 0.5; k++)
167 {
168 i = ind[k];
169
170 j = i > 0 ? i - 1 : nvert - 1; /* Vertex before i */
171 if (vec2_y(pt[j]) <= y - 0.5)
172 delete(j, &nact);
173 else if (vec2_y(pt[j]) > y + 0.5)
174 insert(j, y, nvert, &nact);
175
176 j = i < nvert - 1 ? i + 1 : 0; /* Vertex after i */
177 if (vec2_y(pt[j]) <= y - 0.5)
178 delete(i, &nact);
179 else if (vec2_y(pt[j]) > y + 0.5)
180 insert(i, y, nvert, &nact);
181 }
182
183 qsort(active, nact, sizeof(active[0]), compare_active);
184
185 /* Draw horizontal segments for scanline y. Span between j and
186 * j+1 is inside polygon. Span between j+1 and j+2 is outside
187 * polygon. */
188 for (j = 0; j < nact; j += 2)
189 {
190 lx = (int) ceil(active[j].x - 0.5); /* Left end of span */
191 if (lx < 0)
192 lx = 0;
193
194 ux = (int) floor(active[j + 1].x - 0.5); /* Right end of span */
195 if (ux >= max_x)
196 ux = max_x - 1;
197
198 (*func) (y, lx, ux, data);
199
200 active[j].x += active[j].dx;
201 active[j + 1].x += active[j + 1].dx;
202 }
203 }
204 tvector_free(ind, 0, int);
205 tvector_free(active, 0, Poly_edge);
206 }
207
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.