Move freetype 2 support into its own module
[imager.git] / polygon.c
1 #include "imager.h"
2 #include "draw.h"
3 #include "log.h"
4 #include "imrender.h"
5 #include "imageri.h"
6
7 #define IMTRUNC(x) ((int)((x)*16))
8
9 #define coarse(x) ((x)/16)
10 #define fine(x)   ((x)%16)
11
12 /*#define DEBUG_POLY*/
13 #ifdef DEBUG_POLY
14 #define POLY_DEB(x) x
15 #else
16 #define POLY_DEB(x)
17 #endif
18
19
20 typedef int pcord;
21
22 typedef struct {
23   int n;
24   pcord x,y;
25 } p_point;
26
27 typedef 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
36 typedef struct {
37   int n;
38   double x;
39 } p_slice;
40
41 typedef struct {
42   int start;
43   int stop;
44 } ss_pair;
45
46 typedef struct {
47   int *line;            /* temporary buffer for scanline */
48   int linelen;          /* length of scanline */
49 } ss_scanline;
50
51 static
52 int
53 p_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
59 static
60 int
61 p_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
69 static
70 double
71 p_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
78 static
79 double
80 p_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
87 static
88 p_line *
89 line_set_new(const double *x, const double *y, int l) {
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]);
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);
103   }
104   return lset;
105 }
106
107 static
108 p_point *
109 point_set_new(const double *x, const double *y, int l) {
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
121 static
122 void
123 ss_scanline_reset(ss_scanline *ss) {
124   memset(ss->line, 0, sizeof(int) * ss->linelen);
125 }
126
127 static
128 void
129 ss_scanline_init(ss_scanline *ss, int linelen, int linepairs) {
130   ss->line    = mymalloc( sizeof(int) * linelen );
131   ss->linelen = linelen;
132   ss_scanline_reset(ss);
133 }
134
135 static
136 void
137 ss_scanline_exorcise(ss_scanline *ss) {
138   myfree(ss->line);
139 }
140   
141                      
142
143
144 /* returns the number of matches */
145
146 static
147 int
148 lines_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
165 /* marks the up variable for all lines in a slice */
166
167 static
168 void
169 mark_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;
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
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
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
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     
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)
213               );
214   }
215 }
216
217
218
219 static
220 unsigned char
221 saturate(int in) {
222   if (in>255) { return 255; }
223   else if (in>0) return in;
224   return 0;
225 }
226
227 typedef void (*scanline_flusher)(i_img *im, ss_scanline *ss, int y, void *ctx);
228
229 /* This function must be modified later to do proper blending */
230
231 static void
232 scanline_flush(i_img *im, ss_scanline *ss, int y, void *ctx) {
233   int x, ch, tv;
234   i_color t;
235   i_color *val = (i_color *)ctx;
236   POLY_DEB( printf("Flushing line %d\n", y) );
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
248 static
249 int
250 trap_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
263 static
264 int 
265 pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord  miny, pcord maxy) {
266   double lycross, rycross;
267   int l, r;
268
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
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(
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)
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   }
309
310   return 0; /* silence compiler warning */
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
326 static
327 void
328 render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r, pcord miny, pcord maxy) {
329   
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" */
336
337   /* Find the y bounds of scanline_slice */
338
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   
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) );
354
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) );
357
358   thin = coarse(lmaxx) >= coarse(rminx);
359
360   startpix = i_max( coarse(lminx), 0 );
361   stoppix  = i_min( coarse(rmaxx-1), ss->linelen-1 );
362
363   POLY_DEB(  printf("  miny=%g maxy=%g\n", miny/16.0, maxy/16.0)  );
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     
371     POLY_DEB( printf("  (%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
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
377     POLY_DEB( printf("  A=%d B=%d C=%d\n", A, B, C) );
378
379     ss->line[cpix] += A+B-C;
380
381   }
382   POLY_DEB( printf("end render_slice_scanline()\n") );
383 }
384
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
415 static void
416 i_poly_aa_low(i_img *im, int l, const double *x, const double *y, void *ctx, scanline_flusher flusher) {
417   int i ,k;                     /* Index variables */
418   int clc;                      /* Lines inside current interval */
419   /* initialize to avoid compiler warnings */
420   pcord tempy = 0;
421   int cscl = 0;                 /* Current scanline */
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
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));
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            );
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++) {
461     int startscan = i_max( coarse(pset[i].y), 0);
462     int stopscan = i_min( coarse(pset[i+1].y+15), im->ysize);
463     pcord miny, maxy;   /* y bounds in fine coordinates */
464
465     POLY_DEB( pcord cc = (pset[i].y + pset[i+1].y)/2 );
466
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     
472     if (pset[i].y == pset[i+1].y) {
473       POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
474       continue;
475     }
476
477     clc = lines_in_interval(lset, l, tllist, pset[i].y, pset[i+1].y);
478     qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
479
480     mark_updown_slices(lset, tllist, clc);
481
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) );
507     }
508     POLY_DEB( printf("miny %g maxy %g\n", miny/16.0, maxy/16.0) );
509
510     for(cscl=startscan; cscl<stopscan; cscl++) {
511       pcord scan_miny = i_max(miny, cscl * 16);
512       pcord scan_maxy = i_min(maxy, (cscl + 1 ) * 16);
513       
514       tempy = i_min(cscl*16+16, pset[i+1].y);
515       POLY_DEB( printf("evaluating scan line %d \n", cscl) );
516       for(k=0; k<clc-1; k+=2) {
517         POLY_DEB( printf("evaluating slice %d\n", k) );
518         render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n, scan_miny, scan_maxy);
519       }
520       if (16*coarse(tempy) == tempy) {
521         POLY_DEB( printf("flushing scan line %d\n", cscl) );
522         flusher(im, &templine, cscl, ctx);
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) 
535     flusher(im, &templine, cscl-1, ctx);
536
537   ss_scanline_exorcise(&templine);
538   myfree(pset);
539   myfree(lset);
540   myfree(tllist);
541   
542 } /* Function */
543
544 int
545 i_poly_aa(i_img *im, int l, const double *x, const double *y, const i_color *val) {
546   i_color c = *val;
547   i_poly_aa_low(im, l, x, y, &c, scanline_flush);
548   return 1;
549 }
550
551 struct poly_render_state {
552   i_render render;
553   i_fill_t *fill;
554   unsigned char *cover;
555 };
556
557 static void
558 scanline_flush_render(i_img *im, ss_scanline *ss, int y, void *ctx) {
559   int x;
560   int left, right;
561   struct poly_render_state *state = (struct poly_render_state *)ctx;
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 }
581
582 int
583 i_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);
593   return 1;
594 }