Move freetype 2 support into its own module
[imager.git] / polygon.c
CommitLineData
92bda632 1#include "imager.h"
9982a307
AMH
2#include "draw.h"
3#include "log.h"
9b1ec2b8 4#include "imrender.h"
50c75381 5#include "imageri.h"
9982a307
AMH
6
7#define IMTRUNC(x) ((int)((x)*16))
8
9#define coarse(x) ((x)/16)
10#define fine(x) ((x)%16)
11
1c5252ed
TC
12/*#define DEBUG_POLY*/
13#ifdef DEBUG_POLY
14#define POLY_DEB(x) x
15#else
9982a307 16#define POLY_DEB(x)
1c5252ed 17#endif
9982a307
AMH
18
19
20typedef int pcord;
21
22typedef struct {
23 int n;
24 pcord x,y;
25} p_point;
26
27typedef struct {
28 int n;
29 pcord x1,y1;
30 pcord x2,y2;
31 pcord miny,maxy;
32 pcord minx,maxx;
33 int updown; /* -1 means down, 0 vertical, 1 up */
34} p_line;
35
36typedef struct {
37 int n;
38 double x;
39} p_slice;
40
41typedef struct {
42 int start;
43 int stop;
44} ss_pair;
45
46typedef struct {
47 int *line; /* temporary buffer for scanline */
48 int linelen; /* length of scanline */
9982a307
AMH
49} ss_scanline;
50
9982a307
AMH
51static
52int
53p_compy(const p_point *p1, const p_point *p2) {
54 if (p1->y > p2->y) return 1;
55 if (p1->y < p2->y) return -1;
56 return 0;
57}
58
59static
60int
61p_compx(const p_slice *p1, const p_slice *p2) {
62 if (p1->x > p2->x) return 1;
63 if (p1->x < p2->x) return -1;
64 return 0;
65}
66
67/* Change this to int? and round right goddamn it! */
68
69static
70double
71p_eval_aty(p_line *l, pcord y) {
72 int t;
73 t=l->y2-l->y1;
74 if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
75 return (l->x1+l->x2)/2.0;
76}
77
78static
79double
80p_eval_atx(p_line *l, pcord x) {
81 int t;
82 t = l->x2-l->x1;
83 if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
84 return (l->y1+l->y2)/2.0;
85}
86
87static
88p_line *
97ac0a96 89line_set_new(const double *x, const double *y, int l) {
9982a307
AMH
90 int i;
91 p_line *lset = mymalloc(sizeof(p_line) * l);
92
93 for(i=0; i<l; i++) {
94 lset[i].n=i;
95 lset[i].x1 = IMTRUNC(x[i]);
96 lset[i].y1 = IMTRUNC(y[i]);
97 lset[i].x2 = IMTRUNC(x[(i+1)%l]);
98 lset[i].y2 = IMTRUNC(y[(i+1)%l]);
b33c08f8
TC
99 lset[i].miny=i_min(lset[i].y1,lset[i].y2);
100 lset[i].maxy=i_max(lset[i].y1,lset[i].y2);
101 lset[i].minx=i_min(lset[i].x1,lset[i].x2);
102 lset[i].maxx=i_max(lset[i].x1,lset[i].x2);
9982a307
AMH
103 }
104 return lset;
105}
106
107static
108p_point *
97ac0a96 109point_set_new(const double *x, const double *y, int l) {
9982a307
AMH
110 int i;
111 p_point *pset = mymalloc(sizeof(p_point) * l);
112
113 for(i=0; i<l; i++) {
114 pset[i].n=i;
115 pset[i].x=IMTRUNC(x[i]);
116 pset[i].y=IMTRUNC(y[i]);
117 }
118 return pset;
119}
120
9982a307
AMH
121static
122void
123ss_scanline_reset(ss_scanline *ss) {
9982a307
AMH
124 memset(ss->line, 0, sizeof(int) * ss->linelen);
125}
126
127static
128void
129ss_scanline_init(ss_scanline *ss, int linelen, int linepairs) {
130 ss->line = mymalloc( sizeof(int) * linelen );
131 ss->linelen = linelen;
9982a307
AMH
132 ss_scanline_reset(ss);
133}
134
d0e7bfee
AMH
135static
136void
137ss_scanline_exorcise(ss_scanline *ss) {
138 myfree(ss->line);
d0e7bfee
AMH
139}
140
141
142
9982a307
AMH
143
144/* returns the number of matches */
145
146static
147int
fe24d684
AMH
148lines_in_interval(p_line *lset, int l, p_slice *tllist, pcord minc, pcord maxc) {
149 int k;
150 int count = 0;
151 for(k=0; k<l; k++) {
152 if (lset[k].maxy > minc && lset[k].miny < maxc) {
153 if (lset[k].miny == lset[k].maxy) {
154 POLY_DEB( printf(" HORIZONTAL - skipped\n") );
155 } else {
156 tllist[count].x=p_eval_aty(&lset[k],(minc+maxc)/2.0 );
157 tllist[count].n=k;
158 count++;
159 }
160 }
161 }
162 return count;
163}
164
9982a307
AMH
165/* marks the up variable for all lines in a slice */
166
167static
168void
169mark_updown_slices(p_line *lset, p_slice *tllist, int count) {
170 p_line *l, *r;
171 int k;
172 for(k=0; k<count; k+=2) {
173 l = lset + tllist[k].n;
9982a307
AMH
174
175 if (l->y1 == l->y2) {
176 mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
177 exit(3);
178 }
179
9982a307
AMH
180 l->updown = (l->x1 == l->x2) ?
181 0 :
182 (l->x1 > l->x2)
183 ?
184 (l->y1 > l->y2) ? -1 : 1
185 :
186 (l->y1 > l->y2) ? 1 : -1;
187
d0e7bfee
AMH
188 POLY_DEB( printf("marking left line %d as %s(%d)\n", l->n,
189 l->updown ? l->updown == 1 ? "up" : "down" : "vert", l->updown, l->updown)
190 );
191
192 if (k+1 >= count) {
193 mm_log((1, "Invalid polygon spec, odd number of line crossings.\n"));
194 return;
195 }
196
197 r = lset + tllist[k+1].n;
198 if (r->y1 == r->y2) {
199 mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
200 exit(3);
201 }
202
9982a307
AMH
203 r->updown = (r->x1 == r->x2) ?
204 0 :
205 (r->x1 > r->x2)
206 ?
207 (r->y1 > r->y2) ? -1 : 1
208 :
209 (r->y1 > r->y2) ? 1 : -1;
210
d0e7bfee
AMH
211 POLY_DEB( printf("marking right line %d as %s(%d)\n", r->n,
212 r->updown ? r->updown == 1 ? "up" : "down" : "vert", r->updown, r->updown)
9982a307
AMH
213 );
214 }
215}
216
217
218
219static
220unsigned char
221saturate(int in) {
222 if (in>255) { return 255; }
223 else if (in>0) return in;
224 return 0;
225}
226
7bd0a037 227typedef void (*scanline_flusher)(i_img *im, ss_scanline *ss, int y, void *ctx);
9982a307
AMH
228
229/* This function must be modified later to do proper blending */
230
b33c08f8 231static void
7bd0a037 232scanline_flush(i_img *im, ss_scanline *ss, int y, void *ctx) {
9982a307
AMH
233 int x, ch, tv;
234 i_color t;
43c5dacb 235 i_color *val = (i_color *)ctx;
1c5252ed 236 POLY_DEB( printf("Flushing line %d\n", y) );
9982a307
AMH
237 for(x=0; x<im->xsize; x++) {
238 tv = saturate(ss->line[x]);
239 i_gpix(im, x, y, &t);
240 for(ch=0; ch<im->channels; ch++)
241 t.channel[ch] = tv/255.0 * val->channel[ch] + (1.0-tv/255.0) * t.channel[ch];
242 i_ppix(im, x, y, &t);
243 }
244}
245
246
247
248static
249int
250trap_square(pcord xlen, pcord ylen, double xl, double yl) {
251 POLY_DEB( printf("trap_square: %d %d %.2f %.2f\n", xlen, ylen, xl, yl) );
252 return xlen*ylen-(xl*yl)/2.0;
253}
254
255
256/*
257 pixel_coverage calculates the 'left side' pixel coverage of a pixel that is
258 within the min/max ranges. The shape always corresponds to a square with some
259 sort of a triangle cut from it (which can also yield a triangle).
260*/
261
262
263static
264int
265pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord miny, pcord maxy) {
266 double lycross, rycross;
267 int l, r;
268
1c5252ed
TC
269 POLY_DEB
270 (
271 printf(" pixel_coverage(..., minx %g, maxx%g, miny %g, maxy %g)\n",
272 minx/16.0, maxx/16.0, miny/16.0, maxy/16.0)
273 );
274
9982a307
AMH
275 if (!line->updown) {
276 l = r = 0;
277 } else {
278 lycross = p_eval_atx(line, minx);
279 rycross = p_eval_atx(line, maxx);
280 l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */
281 r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */
282 }
283 POLY_DEB(
1c5252ed
TC
284 printf(" %4s(%+d): ", line->updown ? line->updown == 1 ? "up" : "down" : "vert", line->updown);
285 printf(" (%2d,%2d) [%3d-%3d, %3d-%3d] lycross=%.2f rycross=%.2f", coarse(minx), coarse(miny), minx, maxx, miny, maxy, lycross, rycross);
286 printf(" l=%d r=%d\n", l, r)
9982a307
AMH
287 );
288
289 if (l && r)
290 return line->updown == 1 ?
291 (double)(maxx-minx) * (2.0*maxy-lycross-rycross)/2.0 /* up case */
292 :
293 (double)(maxx-minx) * (lycross+rycross-2*miny)/2.0; /* down case */
294
295 if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0;
296
297 if (l && !r)
298 return line->updown == 1 ?
299 trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) :
300 trap_square(maxx-minx, maxy-miny, p_eval_aty(line, maxy)-minx, maxy-p_eval_atx(line, minx));
301
302
303 if (!l && r) {
304 int r = line->updown == 1 ?
305 (maxx-p_eval_aty(line, maxy))*(maxy-p_eval_atx(line, maxx))/2.0 :
306 (maxx-p_eval_aty(line, miny))*(p_eval_atx(line, maxx)-miny)/2.0;
307 return r;
308 }
b07bc64b
TC
309
310 return 0; /* silence compiler warning */
9982a307
AMH
311}
312
313
314
315
316
317/*
318 handle the scanline slice in three steps
319
320 1. Where only the left edge is inside a pixel
321 2a. Where both left and right edge are inside a pixel
322 2b. Where neither left or right edge are inside a pixel
323 3. Where only the right edge is inside a pixel
324*/
325
326static
327void
1c5252ed 328render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r, pcord miny, pcord maxy) {
9982a307 329
9982a307
AMH
330 pcord lminx, lmaxx; /* left line min/max within y bounds in fine coords */
331 pcord rminx, rmaxx; /* right line min/max within y bounds in fine coords */
332 int cpix; /* x-coordinate of current pixel */
333 int thin; /* boolean for thin/thick segment */
334 int startpix; /* temporary variable for "start of this interval" */
335 int stoppix; /* temporary variable for "end of this interval" */
9982a307
AMH
336
337 /* Find the y bounds of scanline_slice */
338
1c5252ed
TC
339 POLY_DEB
340 (
341 printf("render_slice_scanline(..., y=%d)\n");
342 printf(" left n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
343 l->n, l->x1/16.0, l->y1/16.0, l->x2/16.0, l->y2/16.0,
344 l->minx/16.0, l->miny/16.0, l->maxx/16.0, l->maxy/16.0,
345 l->updown);
346 printf(" right n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
347 r->n, r->x1/16.0, r->y1/16.0, r->x2/16.0, r->y2/16.0,
348 r->minx/16.0, r->miny/16.0, r->maxx/16.0, r->maxy/16.0,
349 r->updown);
350 );
351
b33c08f8
TC
352 lminx = i_min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
353 lmaxx = i_max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
9982a307 354
b33c08f8
TC
355 rminx = i_min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
356 rmaxx = i_max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
9982a307
AMH
357
358 thin = coarse(lmaxx) >= coarse(rminx);
359
b33c08f8
TC
360 startpix = i_max( coarse(lminx), 0 );
361 stoppix = i_min( coarse(rmaxx-1), ss->linelen-1 );
1c5252ed
TC
362
363 POLY_DEB( printf(" miny=%g maxy=%g\n", miny/16.0, maxy/16.0) );
9982a307
AMH
364
365 for(cpix=startpix; cpix<=stoppix; cpix++) {
366 int lt = coarse(lmaxx-1) >= cpix;
367 int rt = coarse(rminx) <= cpix;
368
369 int A, B, C;
370
1c5252ed 371 POLY_DEB( printf(" (%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
9982a307
AMH
372
373 A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0;
374 B = lt ? 0 : 16*(maxy-miny);
375 C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0;
376
1c5252ed 377 POLY_DEB( printf(" A=%d B=%d C=%d\n", A, B, C) );
9982a307
AMH
378
379 ss->line[cpix] += A+B-C;
380
381 }
1c5252ed 382 POLY_DEB( printf("end render_slice_scanline()\n") );
9982a307
AMH
383}
384
9982a307
AMH
385/* Antialiasing polygon algorithm
386 specs:
387 1. only nice polygons - no crossovers
388 2. 1/16 pixel resolution
389 3. full antialiasing ( complete spectrum of blends )
390 4. uses hardly any memory
391 5. no subsampling phase
392
393
394 Algorithm outline:
395 1. Split into vertical intervals.
396 2. handle each interval
397
398 For each interval we must:
399 1. find which lines are in it
400 2. order the lines from in increasing x order.
401 since we are assuming no crossovers it is sufficent
402 to check a single point on each line.
403*/
404
405/*
406 Definitions:
407
408 1. Interval: A vertical segment in which no lines cross nor end.
409 2. Scanline: A physical line, contains 16 subpixels in the horizontal direction
410 3. Slice: A start stop line pair.
411
412 */
413
414
b33c08f8 415static void
7bd0a037 416i_poly_aa_low(i_img *im, int l, const double *x, const double *y, void *ctx, scanline_flusher flusher) {
9982a307
AMH
417 int i ,k; /* Index variables */
418 int clc; /* Lines inside current interval */
b07bc64b
TC
419 /* initialize to avoid compiler warnings */
420 pcord tempy = 0;
421 int cscl = 0; /* Current scanline */
9982a307
AMH
422
423 ss_scanline templine; /* scanline accumulator */
424 p_point *pset; /* List of points in polygon */
425 p_line *lset; /* List of lines in polygon */
426 p_slice *tllist; /* List of slices */
427
43c5dacb 428 mm_log((1, "i_poly_aa(im %p, l %d, x %p, y %p, ctx %p, flusher %p)\n", im, l, x, y, ctx, flusher));
d0e7bfee
AMH
429
430 for(i=0; i<l; i++) {
431 mm_log((2, "(%.2f, %.2f)\n", x[i], y[i]));
432 }
433
434
435 POLY_DEB(
436 fflush(stdout);
437 setbuf(stdout, NULL);
438 );
9982a307
AMH
439
440 tllist = mymalloc(sizeof(p_slice)*l);
441
442 ss_scanline_init(&templine, im->xsize, l);
443
444 pset = point_set_new(x, y, l);
445 lset = line_set_new(x, y, l);
446
447
448 qsort(pset, l, sizeof(p_point), (int(*)(const void *,const void *))p_compy);
449
450 POLY_DEB(
451 for(i=0;i<l;i++) {
452 printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",
453 i, lset[i].n, lset[i].x1, lset[i].y1, lset[i].x2, lset[i].y2, lset[i].miny, lset[i].maxy);
454 }
455 printf("MAIN LOOP\n\n");
456 );
457
458
459 /* loop on intervals */
460 for(i=0; i<l-1; i++) {
b33c08f8
TC
461 int startscan = i_max( coarse(pset[i].y), 0);
462 int stopscan = i_min( coarse(pset[i+1].y+15), im->ysize);
1c5252ed 463 pcord miny, maxy; /* y bounds in fine coordinates */
9982a307 464
1c5252ed 465 POLY_DEB( pcord cc = (pset[i].y + pset[i+1].y)/2 );
fe24d684 466
9982a307
AMH
467 POLY_DEB(
468 printf("current slice is %d: %d to %d ( cpoint %d ) scanlines %d to %d\n",
469 i, pset[i].y, pset[i+1].y, cc, startscan, stopscan)
470 );
471
1c5252ed
TC
472 if (pset[i].y == pset[i+1].y) {
473 POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
474 continue;
475 }
476
fe24d684 477 clc = lines_in_interval(lset, l, tllist, pset[i].y, pset[i+1].y);
9982a307
AMH
478 qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
479
480 mark_updown_slices(lset, tllist, clc);
481
1c5252ed
TC
482 POLY_DEB
483 (
484 printf("Interval contains %d lines\n", clc);
485 for(k=0; k<clc; k++) {
486 int lno = tllist[k].n;
487 p_line *ln = lset+lno;
488 printf("%d: line #%2d: (%2d, %2d)->(%2d, %2d) (%2d/%2d, %2d/%2d) -> (%2d/%2d, %2d/%2d) alignment=%s\n",
489 k, lno, ln->x1, ln->y1, ln->x2, ln->y2,
490 coarse(ln->x1), fine(ln->x1),
491 coarse(ln->y1), fine(ln->y1),
492 coarse(ln->x2), fine(ln->x2),
493 coarse(ln->y2), fine(ln->y2),
494 ln->updown == 0 ? "vert" : ln->updown == 1 ? "up" : "down");
495
496 }
497 );
498 maxy = im->ysize * 16;
499 miny = 0;
500 for (k = 0; k < clc; ++k) {
501 p_line const * line = lset + tllist[k].n;
502 if (line->miny > miny)
503 miny = line->miny;
504 if (line->maxy < maxy)
505 maxy = line->maxy;
506 POLY_DEB( printf(" line miny %g maxy %g\n", line->miny/16.0, line->maxy/16.0) );
9982a307 507 }
1c5252ed
TC
508 POLY_DEB( printf("miny %g maxy %g\n", miny/16.0, maxy/16.0) );
509
9982a307 510 for(cscl=startscan; cscl<stopscan; cscl++) {
1c5252ed
TC
511 pcord scan_miny = i_max(miny, cscl * 16);
512 pcord scan_maxy = i_min(maxy, (cscl + 1 ) * 16);
513
b33c08f8 514 tempy = i_min(cscl*16+16, pset[i+1].y);
9982a307
AMH
515 POLY_DEB( printf("evaluating scan line %d \n", cscl) );
516 for(k=0; k<clc-1; k+=2) {
fe24d684 517 POLY_DEB( printf("evaluating slice %d\n", k) );
1c5252ed 518 render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n, scan_miny, scan_maxy);
9982a307
AMH
519 }
520 if (16*coarse(tempy) == tempy) {
521 POLY_DEB( printf("flushing scan line %d\n", cscl) );
43c5dacb 522 flusher(im, &templine, cscl, ctx);
9982a307
AMH
523 ss_scanline_reset(&templine);
524 }
525 /*
526 else {
527 scanline_flush(im, &templine, cscl, val);
528 ss_scanline_reset(&templine);
529 return 0;
530 }
531 */
532 }
533 } /* Intervals */
534 if (16*coarse(tempy) != tempy)
43c5dacb 535 flusher(im, &templine, cscl-1, ctx);
9982a307 536
d0e7bfee
AMH
537 ss_scanline_exorcise(&templine);
538 myfree(pset);
539 myfree(lset);
540 myfree(tllist);
541
542} /* Function */
43c5dacb 543
1c5252ed 544int
97ac0a96 545i_poly_aa(i_img *im, int l, const double *x, const double *y, const i_color *val) {
7bd0a037
TC
546 i_color c = *val;
547 i_poly_aa_low(im, l, x, y, &c, scanline_flush);
1c5252ed 548 return 1;
43c5dacb 549}
9b1ec2b8
TC
550
551struct poly_render_state {
552 i_render render;
553 i_fill_t *fill;
554 unsigned char *cover;
555};
556
557static void
7bd0a037
TC
558scanline_flush_render(i_img *im, ss_scanline *ss, int y, void *ctx) {
559 int x;
9b1ec2b8 560 int left, right;
7bd0a037 561 struct poly_render_state *state = (struct poly_render_state *)ctx;
9b1ec2b8
TC
562
563 left = 0;
564 while (left < im->xsize && ss->line[left] <= 0)
565 ++left;
566 if (left < im->xsize) {
567 right = im->xsize;
568 /* since going from the left found something, moving from the
569 right should */
570 while (/* right > left && */ ss->line[right-1] <= 0)
571 --right;
572
573 /* convert to the format the render interface wants */
574 for (x = left; x < right; ++x) {
575 state->cover[x-left] = saturate(ss->line[x]);
576 }
577 i_render_fill(&state->render, left, y, right-left, state->cover,
578 state->fill);
579 }
580}
43c5dacb 581
1c5252ed 582int
9b1ec2b8
TC
583i_poly_aa_cfill(i_img *im, int l, const double *x, const double *y,
584 i_fill_t *fill) {
585 struct poly_render_state ctx;
586
587 i_render_init(&ctx.render, im, im->xsize);
588 ctx.fill = fill;
589 ctx.cover = mymalloc(im->xsize);
590 i_poly_aa_low(im, l, x, y, &ctx, scanline_flush_render);
591 myfree(ctx.cover);
592 i_render_done(&ctx.render);
1c5252ed 593 return 1;
43c5dacb 594}