polygon.c

filter: Statementstmt 95.8% 253 / 264 Branchbran 91.7% 145 / 158 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 94.3% 398 / 422 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« ICO/t/t10icon.t ↑ Summary DynTest/t/t00dyntest.t »
1 #define IMAGER_NO_CONTEXT
2 #include "imager.h"
3 #include "draw.h"
4 #include "log.h"
5 #include "imrender.h"
6 #include "imageri.h"
7  
8 #define IMTRUNC(x) ((int)((x)*16))
9  
10 #define coarse(x) ((x)/16)
11 #define fine(x) ((x)%16)
12  
13 /*#define DEBUG_POLY*/
14 #ifdef DEBUG_POLY
15 #define POLY_DEB(x) x
16 #else
17 #define POLY_DEB(x)
18 #endif
19  
20  
21 typedef i_img_dim pcord;
22  
23 typedef struct {
24 size_t n;
25 pcord x,y;
26 } p_point;
27  
28 typedef struct {
29 size_t n;
30 pcord x1,y1;
31 pcord x2,y2;
32 pcord miny,maxy;
33 pcord minx,maxx;
34 int updown; /* -1 means down, 0 vertical, 1 up */
35 int dir; /* 1 for down, -1 for up */
36 } p_line;
37  
38 typedef struct {
39 size_t n;
40 double x;
41 } p_slice;
42  
43 typedef struct {
44 int *line; /* temporary buffer for scanline */
45 i_img_dim linelen; /* length of scanline */
46 } ss_scanline;
47  
48 static
49 int
50 7353 p_compy(const p_point *p1, const p_point *p2) {
51 7353 ▶ if (p1->y > p2->y) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (p1->y > p2->y) return 1; 3957 3396 7353
52 3396 ▶ if (p1->y < p2->y) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (p1->y < p2->y) return -1; 2845 551 3396
53 551 return 0;
54 }
55  
56 static
57 int
58 4052 p_compx(const p_slice *p1, const p_slice *p2) {
59 4052 ▶ if (p1->x > p2->x) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (p1->x > p2->x) return 1; 2228 1824 4052
60 1824 ▶ if (p1->x < p2->x) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (p1->x < p2->x) return -1; 1810 14 1824
61 14 return 0;
62 }
63  
64 /* Change this to int? and round right goddamn it! */
65  
66 static
67 double
68 93277 p_eval_aty(p_line *l, pcord y) {
69 int t;
70 93277 t=l->y2-l->y1;
71 93277 ▶ if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
Branch: 1 branch
BranchTrueFalseTotal
if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t; 93277 0 93277
72 0 return (l->x1+l->x2)/2.0;
73 }
74  
75 static
76 double
77 57255 p_eval_atx(p_line *l, pcord x) {
78 int t;
79 57255 t = l->x2-l->x1;
80 57255 ▶ if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
Branch: 1 branch
BranchTrueFalseTotal
if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t; 57255 0 57255
81 0 return (l->y1+l->y2)/2.0;
82 }
83  
84 static
85 p_line *
86 97 line_set_new(const i_polygon_t *polys, size_t count, size_t *line_count) {
87 size_t i, j, n;
88 p_line *lset, *line;
89 97 size_t lines = 0;
90
91 202 ▶ for (i = 0; i < count; ++i)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < count; ++i) 105 97 202
92 105 lines += polys[i].count;
93  
94 97 line = lset = mymalloc(sizeof(p_line) * lines);
95  
96 97 n = 0;
97 202 ▶ for (i = 0; i < count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < count; ++i) { 105 97 202
98 105 const i_polygon_t *p = polys + i;
99  
100 2077 ▶ for(j = 0; j < p->count; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for(j = 0; j < p->count; j++) { 1972 105 2077
101 1972 line->x1 = IMTRUNC(p->x[j]);
102 1972 line->y1 = IMTRUNC(p->y[j]);
103 1972 line->x2 = IMTRUNC(p->x[(j + 1) % p->count]);
104 1972 line->y2 = IMTRUNC(p->y[(j + 1) % p->count]);
105  
106 /* don't include purely horizontal lines, we don't usefully
107 intersect with them. */
108 1972 ▶ if (line->y1 == line->y2)
Branch: 1 branch
BranchTrueFalseTotal
if (line->y1 == line->y2) 94 1878 1972
109 94 continue;
110  
111 1878 line->miny = i_min(line->y1, line->y2);
112 1878 line->maxy = i_max(line->y1, line->y2);
113 1878 line->minx = i_min(line->x1, line->x2);
114 1878 line->maxx = i_max(line->x1, line->x2);
115 1878 line->n = n++;
116 1878 ++line;
117 }
118 }
119 97 *line_count = n;
120  
121 97 return lset;
122 }
123  
124 static
125 p_point *
126 97 point_set_new(const i_polygon_t *polys, size_t count, size_t *point_count) {
127 size_t i, j, n;
128 p_point *pset, *pt;
129 97 size_t points = 0;
130
131 202 ▶ for (i = 0; i < count; ++i)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < count; ++i) 105 97 202
132 105 points += polys[i].count;
133  
134 97 *point_count = points;
135  
136 97 pt = pset = mymalloc(sizeof(p_point) * points);
137  
138 97 n = 0;
139 202 ▶ for (i = 0; i < count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < count; ++i) { 105 97 202
140 105 const i_polygon_t *p = polys + i;
141  
142 2077 ▶ for(j = 0; j < p->count; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for(j = 0; j < p->count; j++) { 1972 105 2077
143 1972 pt->n = n++;
144 1972 pt->x = IMTRUNC(p->x[j]);
145 1972 pt->y = IMTRUNC(p->y[j]);
146 1972 ++pt;
147 }
148 }
149 97 return pset;
150 }
151  
152 static
153 void
154 5419 ss_scanline_reset(ss_scanline *ss) {
155 5419 memset(ss->line, 0, sizeof(int) * ss->linelen);
156 5419 }
157  
158 static
159 void
160 97 ss_scanline_init(ss_scanline *ss, i_img_dim linelen) {
161 97 ss->line = mymalloc( sizeof(int) * linelen );
162 97 ss->linelen = linelen;
163 97 ss_scanline_reset(ss);
164 97 }
165  
166 static
167 void
168 97 ss_scanline_exorcise(ss_scanline *ss) {
169 97 myfree(ss->line);
170 97 }
171
172
173  
174  
175 /* returns the number of matches */
176  
177 static
178 int
179 1357 lines_in_interval(p_line *lset, int l, p_slice *tllist, pcord minc, pcord maxc) {
180 int k;
181 1357 int count = 0;
182 179922 ▶ for(k=0; k<l; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for(k=0; k<l; k++) { 178565 1357 179922
183 178565 ▶ if (lset[k].maxy > minc && lset[k].miny < maxc) {
Branch: 2 branches
BranchTrueFalseTotal
if (lset[k].maxy > minc && lset[k].miny < maxc) { 91266 87299 178565
if (lset[k].maxy > minc && lset[k].miny < maxc) { 4298 86968 91266
184 4298 ▶ if (lset[k].miny == lset[k].maxy) {
Branch: 1 branch
BranchTrueFalseTotal
if (lset[k].miny == lset[k].maxy) { 4298 0 4298
185 POLY_DEB( printf(" HORIZONTAL - skipped\n") );
186 } else {
187 4298 tllist[count].x=p_eval_aty(&lset[k],(minc+maxc)/2.0 );
188 4298 tllist[count].n=k;
189 4298 count++;
190 }
191 }
192 }
193 1357 return count;
194 }
195  
196 /* marks the up variable for all lines in a slice */
197  
198 static
199 void
200 1357 mark_updown_slices(pIMCTX, p_line *lset, p_slice *tllist, int count) {
201 p_line *l, *r;
202 int k;
203 3506 ▶ for(k=0; k<count; k+=2) {
Branch: 1 branch
BranchTrueFalseTotal
for(k=0; k<count; k+=2) { 2149 1357 3506
204 2149 l = lset + tllist[k].n;
205  
206 2149 ▶ if (l->y1 == l->y2) {
Branch: 1 branch
BranchTrueFalseTotal
if (l->y1 == l->y2) { 0 2149 2149
207 0 im_log((aIMCTX,1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
208 0 exit(3);
209 }
210  
211 4298 l->updown = (l->x1 == l->x2) ?
212 4220 ▶ 0 :
Branch: 1 branch
BranchTrueFalseTotal
0 : 2071 78 2149
213 2071 (l->x1 > l->x2)
214 ?
215 1053 ▶ (l->y1 > l->y2) ? -1 : 1
Branch: 1 branch
BranchTrueFalseTotal
(l->y1 > l->y2) ? -1 : 1 1050 3 1053
216 4142 ▶ :
Branch: 1 branch
BranchTrueFalseTotal
: 1053 1018 2071
217 1018 ▶ (l->y1 > l->y2) ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
(l->y1 > l->y2) ? 1 : -1; 1015 3 1018
218 2149 ▶ l->dir = l->y1 < l->y2 ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
l->dir = l->y1 < l->y2 ? 1 : -1; 15 2134 2149
219  
220 POLY_DEB( printf("marking left line %d as %s(%d)\n", l->n,
221 l->updown ? l->updown == 1 ? "up" : "down" : "vert", l->updown, l->updown)
222 );
223  
224 2149 ▶ if (k+1 >= count) {
Branch: 1 branch
BranchTrueFalseTotal
if (k+1 >= count) { 0 2149 2149
225 0 im_log((aIMCTX, 1, "Invalid polygon spec, odd number of line crossings.\n"));
226 0 return;
227 }
228  
229 2149 r = lset + tllist[k+1].n;
230 2149 ▶ if (r->y1 == r->y2) {
Branch: 1 branch
BranchTrueFalseTotal
if (r->y1 == r->y2) { 0 2149 2149
231 0 im_log((aIMCTX, 1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
232 0 exit(3);
233 }
234  
235 4298 r->updown = (r->x1 == r->x2) ?
236 4239 ▶ 0 :
Branch: 1 branch
BranchTrueFalseTotal
0 : 2090 59 2149
237 2090 (r->x1 > r->x2)
238 ?
239 1041 ▶ (r->y1 > r->y2) ? -1 : 1
Branch: 1 branch
BranchTrueFalseTotal
(r->y1 > r->y2) ? -1 : 1 3 1038 1041
240 4180 ▶ :
Branch: 1 branch
BranchTrueFalseTotal
: 1041 1049 2090
241 1049 ▶ (r->y1 > r->y2) ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
(r->y1 > r->y2) ? 1 : -1; 3 1046 1049
242 2149 ▶ r->dir = r->y1 < r->y2 ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
r->dir = r->y1 < r->y2 ? 1 : -1; 2134 15 2149
243
244 POLY_DEB( printf("marking right line %d as %s(%d)\n", r->n,
245 r->updown ? r->updown == 1 ? "up" : "down" : "vert", r->updown, r->updown)
246 );
247 }
248 }
249  
250 static
251 unsigned char
252 1672998 saturate(int in) {
253 1672998 ▶ if (in>255) { return 255; }
Branch: 1 branch
BranchTrueFalseTotal
if (in>255) { return 255; } 188704 1484294 1672998
254 1484294 ▶ else if (in>0) return in;
Branch: 1 branch
BranchTrueFalseTotal
else if (in>0) return in; 19200 1465094 1484294
255 1465094 return 0;
256 }
257  
258 typedef void (*scanline_flusher)(i_img *im, ss_scanline *ss, int y, void *ctx);
259  
260 /* This function must be modified later to do proper blending */
261  
262 static void
263 4782 scanline_flush(i_img *im, ss_scanline *ss, int y, void *ctx) {
264 int x, ch, tv;
265 i_color t;
266 4782 i_color *val = (i_color *)ctx;
267 POLY_DEB( printf("Flushing line %d\n", y) );
268 1620262 ▶ for(x=0; x<im->xsize; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for(x=0; x<im->xsize; x++) { 1615480 4782 1620262
269 1615480 tv = saturate(ss->line[x]);
270 1615480 i_gpix(im, x, y, &t);
271 6461920 ▶ for(ch=0; ch<im->channels; ch++)
Branch: 1 branch
BranchTrueFalseTotal
for(ch=0; ch<im->channels; ch++) 4846440 1615480 6461920
272 4846440 t.channel[ch] = tv/255.0 * val->channel[ch] + (1.0-tv/255.0) * t.channel[ch];
273 1615480 i_ppix(im, x, y, &t);
274 }
275 4782 }
276  
277  
278  
279 static
280 int
281 5731 trap_square(pcord xlen, pcord ylen, double xl, double yl) {
282 POLY_DEB( printf("trap_square: %d %d %.2f %.2f\n", xlen, ylen, xl, yl) );
283 5731 return xlen*ylen-(xl*yl)/2.0;
284 }
285  
286  
287 /*
288 pixel_coverage calculates the 'left side' pixel coverage of a pixel that is
289 within the min/max ranges. The shape always corresponds to a square with some
290 sort of a triangle cut from it (which can also yield a triangle).
291 */
292  
293  
294 static
295 int
296 23091 pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord miny, pcord maxy) {
297 double lycross, rycross;
298 int l, r;
299  
300 POLY_DEB
301 (
302 printf(" pixel_coverage(..., minx %g, maxx%g, miny %g, maxy %g)\n",
303 minx/16.0, maxx/16.0, miny/16.0, maxy/16.0)
304 );
305  
306 23091 ▶ if (!line->updown) {
Branch: 1 branch
BranchTrueFalseTotal
if (!line->updown) { 520 22571 23091
307 520 l = r = 0;
308 } else {
309 22571 lycross = p_eval_atx(line, minx);
310 22571 rycross = p_eval_atx(line, maxx);
311 22571 ▶ l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */
Branch: 2 branches
BranchTrueFalseTotal
l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */ 16466 6105 22571
l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */ 9968 6498 16466
312 22571 ▶ r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */
Branch: 2 branches
BranchTrueFalseTotal
r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */ 16827 5744 22571
r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */ 10619 6208 16827
313 }
314 POLY_DEB(
315 printf(" %4s(%+d): ", line->updown ? line->updown == 1 ? "up" : "down" : "vert", line->updown);
316 printf(" (%2d,%2d) [%3d-%3d, %3d-%3d] lycross=%.2f rycross=%.2f", coarse(minx), coarse(miny), minx, maxx, miny, maxy, lycross, rycross);
317 printf(" l=%d r=%d\n", l, r)
318 );
319
320 23091 ▶ if (l && r)
Branch: 2 branches
BranchTrueFalseTotal
if (l && r) 9968 13123 23091
if (l && r) 4237 5731 9968
321 4237 return line->updown == 1 ?
322 2016 (double)(maxx-minx) * (2.0*maxy-lycross-rycross)/2.0 /* up case */
323 6458 ▶ :
Branch: 1 branch
BranchTrueFalseTotal
: 2016 2221 4237
324 2221 (double)(maxx-minx) * (lycross+rycross-2*miny)/2.0; /* down case */
325
326 18854 ▶ if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0;
Branch: 2 branches
BranchTrueFalseTotal
if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0; 13123 5731 18854
if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0; 6741 6382 13123
327  
328 12113 ▶ if (l && !r)
Branch: 2 branches
BranchTrueFalseTotal
if (l && !r) 5731 6382 12113
if (l && !r) 5731 0 5731
329 5731 return line->updown == 1 ?
330 8165 ▶ trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) :
Branch: 1 branch
BranchTrueFalseTotal
trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) : 3297 2434 5731
331 2434 trap_square(maxx-minx, maxy-miny, p_eval_aty(line, maxy)-minx, maxy-p_eval_atx(line, minx));
332
333  
334 6382 ▶ if (!l && r) {
Branch: 2 branches
BranchTrueFalseTotal
if (!l && r) { 6382 0 6382
if (!l && r) { 6382 0 6382
335 6382 ▶ int r = line->updown == 1 ?
Branch: 1 branch
BranchTrueFalseTotal
int r = line->updown == 1 ? 3194 3188 6382
336 3194 (maxx-p_eval_aty(line, maxy))*(maxy-p_eval_atx(line, maxx))/2.0 :
337 3188 (maxx-p_eval_aty(line, miny))*(p_eval_atx(line, maxx)-miny)/2.0;
338 6382 return r;
339 }
340  
341 /* NOTREACHED */
342 0 return 0; /* silence compiler warning */
343 }
344  
345  
346  
347  
348  
349 /*
350 handle the scanline slice in three steps
351
352 1. Where only the left edge is inside a pixel
353 2a. Where both left and right edge are inside a pixel
354 2b. Where neither left or right edge are inside a pixel
355 3. Where only the right edge is inside a pixel
356 */
357  
358 static
359 void
360 7923 render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r, pcord miny, pcord maxy) {
361
362 pcord lminx, lmaxx; /* left line min/max within y bounds in fine coords */
363 pcord rminx, rmaxx; /* right line min/max within y bounds in fine coords */
364 i_img_dim cpix; /* x-coordinate of current pixel */
365 i_img_dim startpix; /* temporary variable for "start of this interval" */
366 i_img_dim stoppix; /* temporary variable for "end of this interval" */
367  
368 /* Find the y bounds of scanline_slice */
369 (void)y;
370  
371 POLY_DEB
372 (
373 printf("render_slice_scanline(..., y=%d)\n", y);
374 printf(" left n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
375 l->n, l->x1/16.0, l->y1/16.0, l->x2/16.0, l->y2/16.0,
376 l->minx/16.0, l->miny/16.0, l->maxx/16.0, l->maxy/16.0,
377 l->updown);
378 printf(" right n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
379 r->n, r->x1/16.0, r->y1/16.0, r->x2/16.0, r->y2/16.0,
380 r->minx/16.0, r->miny/16.0, r->maxx/16.0, r->maxy/16.0,
381 r->updown);
382 );
383
384 7923 lminx = i_min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
385 7923 lmaxx = i_max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
386  
387 7923 rminx = i_min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
388 7923 rmaxx = i_max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
389  
390 7923 startpix = i_max( coarse(lminx), 0 );
391 7923 stoppix = i_min( coarse(rmaxx-1), ss->linelen-1 );
392  
393 POLY_DEB( printf(" miny=%g maxy=%g\n", miny/16.0, maxy/16.0) );
394
395 290282 ▶ for(cpix=startpix; cpix<=stoppix; cpix++) {
Branch: 1 branch
BranchTrueFalseTotal
for(cpix=startpix; cpix<=stoppix; cpix++) { 282359 7923 290282
396 282359 int lt = coarse(lmaxx-1) >= cpix;
397 282359 int rt = coarse(rminx) <= cpix;
398
399 int A, B, C;
400
401 POLY_DEB( printf(" (%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
402  
403 282359 ▶ A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0;
Branch: 1 branch
BranchTrueFalseTotal
A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0; 11470 270889 282359
404 282359 ▶ B = lt ? 0 : 16*(maxy-miny);
Branch: 1 branch
BranchTrueFalseTotal
B = lt ? 0 : 16*(maxy-miny); 270889 11470 282359
405 282359 ▶ C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0;
Branch: 1 branch
BranchTrueFalseTotal
C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0; 11621 270738 282359
406  
407 POLY_DEB( printf(" A=%d B=%d C=%d\n", A, B, C) );
408  
409 282359 ss->line[cpix] += A+B-C;
410  
411 }
412 POLY_DEB( printf("end render_slice_scanline()\n") );
413 7923 }
414  
415 /* Antialiasing polygon algorithm
416 specs:
417 1. only nice polygons - no crossovers
418 2. 1/16 pixel resolution
419 3. full antialiasing ( complete spectrum of blends )
420 4. uses hardly any memory
421 5. no subsampling phase
422
423  
424 Algorithm outline:
425 1. Split into vertical intervals.
426 2. handle each interval
427  
428 For each interval we must:
429 1. find which lines are in it
430 2. order the lines from in increasing x order.
431 since we are assuming no crossovers it is sufficent
432 to check a single point on each line.
433 */
434  
435 /*
436 Definitions:
437
438 1. Interval: A vertical segment in which no lines cross nor end.
439 2. Scanline: A physical line, contains 16 subpixels in the horizontal direction
440 3. Slice: A start stop line pair.
441
442 */
443  
444  
445 static int
446 99 i_poly_poly_aa_low(i_img *im, int count, const i_polygon_t *polys,
447 i_poly_fill_mode_t mode, void *ctx,
448 scanline_flusher flusher) {
449 size_t pt_index;
450 int k; /* Index variables */
451 i_img_dim clc; /* Lines inside current interval */
452 /* initialize to avoid compiler warnings */
453 99 pcord tempy = 0;
454 99 i_img_dim cscl = 0; /* Current scanline */
455  
456 ss_scanline templine; /* scanline accumulator */
457 p_point *pset; /* List of points in polygon */
458 p_line *lset; /* List of lines in polygon */
459 p_slice *tllist; /* List of slices */
460 size_t pcount, lcount;
461 99 dIMCTX;
462  
463 99 im_log((aIMCTX, 1, "i_poly_poly_aa_low(im %p, count %d, polys %p, ctx %p, flusher %p)\n", im, count, polys, ctx, flusher));
464  
465 99 i_clear_error();
466  
467 99 ▶ if (count < 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (count < 1) { 0 99 99
468 0 i_push_error(0, "no polygons to draw");
469 0 return 0;
470 }
471  
472 204 ▶ for (k = 0; k < count; ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < count; ++k) { 107 97 204
473 107 ▶ if (polys[k].count < 3) {
Branch: 1 branch
BranchTrueFalseTotal
if (polys[k].count < 3) { 2 105 107
474 2 i_push_error(0, "polygons must have at least 3 points");
475 2 return 0;
476 }
477 }
478  
479 202 ▶ for (k = 0; k < count; ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < count; ++k) { 105 97 202
480 105 const i_polygon_t *p = polys + k;
481 105 im_log((aIMCTX, 2, "poly %d\n", k));
482 2077 ▶ for(pt_index = 0; pt_index < p->count; pt_index++) {
Branch: 1 branch
BranchTrueFalseTotal
for(pt_index = 0; pt_index < p->count; pt_index++) { 1972 105 2077
483 1972 im_log((aIMCTX, 2, " (%.2f, %.2f)\n", p->x[pt_index], p->y[pt_index]));
484 }
485 }
486  
487  
488 POLY_DEB(
489 fflush(stdout);
490 setbuf(stdout, NULL);
491 );
492  
493 97 pset = point_set_new(polys, count, &pcount);
494 97 lset = line_set_new(polys, count, &lcount);
495  
496 97 ss_scanline_init(&templine, im->xsize);
497  
498 97 tllist = mymalloc(sizeof(p_slice) * lcount);
499
500 97 qsort(pset, pcount, sizeof(p_point), (int(*)(const void *,const void *))p_compy);
501
502 POLY_DEB(
503 for(i=0;i<lcount;i++) {
504 printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",
505 i, lset[i].n, lset[i].x1, lset[i].y1, lset[i].x2, lset[i].y2, lset[i].miny, lset[i].maxy);
506 }
507 printf("MAIN LOOP\n\n");
508 );
509
510  
511 /* loop on intervals */
512 1972 ▶ for (pt_index = 0; pt_index < pcount-1; pt_index++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pt_index = 0; pt_index < pcount-1; pt_index++) { 1875 97 1972
513 1875 i_img_dim startscan = i_max( coarse(pset[pt_index].y), 0);
514 1875 i_img_dim stopscan = i_min( coarse(pset[pt_index+1].y+15), im->ysize);
515 pcord miny, maxy; /* y bounds in fine coordinates */
516  
517 POLY_DEB( pcord cc = (pset[pt_index].y + pset[pt_index+1].y)/2 );
518  
519 POLY_DEB(
520 printf("current slice is %d: %d to %d ( cpoint %d ) scanlines %d to %d\n",
521 pt_index, pset[pt_index].y, pset[pt_index+1].y, cc,
522 startscan, stopscan)
523 );
524
525 1875 ▶ if (pset[pt_index].y == pset[pt_index+1].y) {
Branch: 1 branch
BranchTrueFalseTotal
if (pset[pt_index].y == pset[pt_index+1].y) { 518 1357 1875
526 POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
527 518 continue;
528 }
529  
530 1357 clc = lines_in_interval(lset, lcount, tllist, pset[pt_index].y, pset[pt_index+1].y);
531 1357 qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
532  
533 1357 mark_updown_slices(aIMCTX, lset, tllist, clc);
534  
535 POLY_DEB
536 (
537 printf("Interval contains %d lines\n", clc);
538 for(k=0; k<clc; k++) {
539 int lno = tllist[k].n;
540 p_line *ln = lset+lno;
541 printf("%d: line #%2d: (%2d, %2d)->(%2d, %2d) (%2d/%2d, %2d/%2d) -> (%2d/%2d, %2d/%2d) alignment=%s\n",
542 k, lno, ln->x1, ln->y1, ln->x2, ln->y2,
543 coarse(ln->x1), fine(ln->x1),
544 coarse(ln->y1), fine(ln->y1),
545 coarse(ln->x2), fine(ln->x2),
546 coarse(ln->y2), fine(ln->y2),
547 ln->updown == 0 ? "vert" : ln->updown == 1 ? "up" : "down");
548
549 }
550 );
551 1357 maxy = im->ysize * 16;
552 1357 miny = 0;
553 5655 ▶ for (k = 0; k < clc; ++k) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < clc; ++k) { 4298 1357 5655
554 4298 p_line const * line = lset + tllist[k].n;
555 4298 ▶ if (line->miny > miny)
Branch: 1 branch
BranchTrueFalseTotal
if (line->miny > miny) 2006 2292 4298
556 2006 miny = line->miny;
557 4298 ▶ if (line->maxy < maxy)
Branch: 1 branch
BranchTrueFalseTotal
if (line->maxy < maxy) 1989 2309 4298
558 1989 maxy = line->maxy;
559 POLY_DEB( printf(" line miny %g maxy %g\n", line->miny/16.0, line->maxy/16.0) );
560 }
561 POLY_DEB( printf("miny %g maxy %g\n", miny/16.0, maxy/16.0) );
562  
563 7820 ▶ for(cscl=startscan; cscl<stopscan; cscl++) {
Branch: 1 branch
BranchTrueFalseTotal
for(cscl=startscan; cscl<stopscan; cscl++) { 6463 1357 7820
564 6463 pcord scan_miny = i_max(miny, cscl * 16);
565 6463 pcord scan_maxy = i_min(maxy, (cscl + 1 ) * 16);
566
567 6463 tempy = i_min(cscl*16+16, pset[pt_index+1].y);
568 POLY_DEB( printf("evaluating scan line %d \n", cscl) );
569 6463 ▶ if (mode == i_pfm_evenodd) {
Branch: 1 branch
BranchTrueFalseTotal
if (mode == i_pfm_evenodd) { 6223 240 6463
570 13826 ▶ for(k=0; k<clc-1; k+=2) {
Branch: 1 branch
BranchTrueFalseTotal
for(k=0; k<clc-1; k+=2) { 7603 6223 13826
571 POLY_DEB( printf("evaluating slice %d\n", k) );
572 7603 render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n, scan_miny, scan_maxy);
573 }
574 }
575 else {
576 240 k = 0;
577 560 ▶ while (k < clc) {
Branch: 1 branch
BranchTrueFalseTotal
while (k < clc) { 320 240 560
578 320 p_line *left = lset + tllist[k++].n;
579 320 p_line *current = NULL;
580 320 int acc = left->dir;
581  
582 800 ▶ while (k < clc && acc) {
Branch: 2 branches
BranchTrueFalseTotal
while (k < clc && acc) { 560 240 800
while (k < clc && acc) { 480 80 560
583 480 current = lset + tllist[k++].n;
584 480 acc += current->dir;
585 }
586 320 ▶ if (acc == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (acc == 0) { 320 0 320
587 320 render_slice_scanline(&templine, cscl, left, current,
588 scan_miny, scan_maxy);
589 }
590 }
591 }
592 6463 ▶ if (16*coarse(tempy) == tempy) {
Branch: 1 branch
BranchTrueFalseTotal
if (16*coarse(tempy) == tempy) { 5322 1141 6463
593 POLY_DEB( printf("flushing scan line %d\n", cscl) );
594 5322 flusher(im, &templine, cscl, ctx);
595 5322 ss_scanline_reset(&templine);
596 }
597 /*
598 else {
599 scanline_flush(im, &templine, cscl, val);
600 ss_scanline_reset(&templine);
601 return 0;
602 }
603 */
604 }
605 } /* Intervals */
606 97 ▶ if (16*coarse(tempy) != tempy)
Branch: 1 branch
BranchTrueFalseTotal
if (16*coarse(tempy) != tempy) 83 14 97
607 83 flusher(im, &templine, cscl-1, ctx);
608  
609 97 ss_scanline_exorcise(&templine);
610 97 myfree(pset);
611 97 myfree(lset);
612 97 myfree(tllist);
613  
614 97 return 1;
615 }
616  
617 /*
618 =item i_poly_poly_aa(im, count, polys, mode, color)
619 =synopsis i_poly_poly_aa(im, 1, &poly, mode, color);
620 =category Drawing
621  
622 Fill the C<count> polygons defined by C<polys> the color specified by
623 C<color>.
624  
625 At least one polygon must be supplied.
626  
627 All polygons must have at least 3 points.
628  
629 =cut
630 */
631  
632 int
633 94 i_poly_poly_aa(i_img *im, int count, const i_polygon_t *polys,
634 i_poly_fill_mode_t mode, const i_color *val) {
635 94 i_color c = *val;
636 94 return i_poly_poly_aa_low(im, count, polys, mode, &c, scanline_flush);
637 }
638  
639 /*
640 =item i_poly_aa_m(im, count, x, y, mode, color)
641 =synopsis i_poly_aa_m(im, count, x, y, mode, color);
642 =category Drawing
643  
644 Fill a polygon defined by the points specified by the x and y arrays with
645 the color specified by C<color>.
646  
647 =cut
648 */
649  
650 int
651 63 i_poly_aa_m(i_img *im, int l, const double *x, const double *y,
652 i_poly_fill_mode_t mode, const i_color *val) {
653 i_polygon_t poly;
654  
655 63 poly.count = l;
656 63 poly.x = x;
657 63 poly.y = y;
658 63 return i_poly_poly_aa(im, 1, &poly, mode, val);
659 }
660  
661 int
662 25 i_poly_aa(i_img *im, int l, const double *x, const double *y, const i_color *val) {
663 i_polygon_t poly;
664  
665 25 poly.count = l;
666 25 poly.x = x;
667 25 poly.y = y;
668 25 return i_poly_poly_aa(im, 1, &poly, i_pfm_evenodd, val);
669 }
670  
671 struct poly_render_state {
672 i_render render;
673 i_fill_t *fill;
674 unsigned char *cover;
675 };
676  
677 static void
678 623 scanline_flush_render(i_img *im, ss_scanline *ss, int y, void *ctx) {
679 i_img_dim x;
680 i_img_dim left, right;
681 623 struct poly_render_state *state = (struct poly_render_state *)ctx;
682  
683 623 left = 0;
684 58408 ▶ while (left < im->xsize && ss->line[left] <= 0)
Branch: 2 branches
BranchTrueFalseTotal
while (left < im->xsize && ss->line[left] <= 0) 58408 0 58408
while (left < im->xsize && ss->line[left] <= 0) 57785 623 58408
685 57785 ++left;
686 623 ▶ if (left < im->xsize) {
Branch: 1 branch
BranchTrueFalseTotal
if (left < im->xsize) { 623 0 623
687 623 right = im->xsize;
688 /* since going from the left found something, moving from the
689 right should */
690 54820 ▶ while (/* right > left && */ ss->line[right-1] <= 0)
Branch: 1 branch
BranchTrueFalseTotal
while (/* right > left && */ ss->line[right-1] <= 0) 54197 623 54820
691 54197 --right;
692
693 /* convert to the format the render interface wants */
694 58141 ▶ for (x = left; x < right; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = left; x < right; ++x) { 57518 623 58141
695 57518 state->cover[x-left] = saturate(ss->line[x]);
696 }
697 623 i_render_fill(&state->render, left, y, right-left, state->cover,
698 state->fill);
699 }
700 623 }
701  
702 /*
703 =item i_poly_poly_aa_cfill(im, count, polys, mode, fill)
704 =synopsis i_poly_poly_aa_cfill(im, 1, &poly, mode, fill);
705 =category Drawing
706  
707 Fill the C<count> polygons defined by C<polys> the fill specified by
708 C<fill>.
709  
710 At least one polygon must be supplied.
711  
712 All polygons must have at least 3 points.
713  
714 =cut
715 */
716  
717 int
718 5 i_poly_poly_aa_cfill(i_img *im, int count, const i_polygon_t *polys,
719 i_poly_fill_mode_t mode, i_fill_t *fill) {
720 struct poly_render_state ctx;
721 int result;
722  
723 5 i_render_init(&ctx.render, im, im->xsize);
724 5 ctx.fill = fill;
725 5 ctx.cover = mymalloc(im->xsize);
726  
727 5 result = i_poly_poly_aa_low(im, count, polys, mode, &ctx,
728 scanline_flush_render);
729  
730 5 myfree(ctx.cover);
731 5 i_render_done(&ctx.render);
732  
733 5 return result;
734 }
735  
736 /*
737 =item i_poly_aa_cfill_m(im, count, x, y, mode, fill)
738 =synopsis i_poly_aa_cfill(im, count, x, y, mode, fill);
739 =category Drawing
740  
741 Fill a polygon defined by the points specified by the x and y arrays with
742 the fill specified by C<fill>.
743  
744 =cut
745 */
746  
747 int
748 4 i_poly_aa_cfill_m(i_img *im, int l, const double *x, const double *y,
749 i_poly_fill_mode_t mode, i_fill_t *fill) {
750 i_polygon_t poly;
751  
752 4 poly.count = l;
753 4 poly.x = x;
754 4 poly.y = y;
755  
756 4 return i_poly_poly_aa_cfill(im, 1, &poly, mode, fill);
757 }
758  
759 int
760 1 i_poly_aa_cfill(i_img *im, int l, const double *x, const double *y,
761 i_fill_t *fill) {
762 i_polygon_t poly;
763  
764 1 poly.count = l;
765 1 poly.x = x;
766 1 poly.y = y;
767  
768 1 return i_poly_poly_aa_cfill(im, 1, &poly, i_pfm_evenodd, fill);
769 }
« ICO/t/t10icon.t ↑ Summary DynTest/t/t00dyntest.t »