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