271513238f0500da370195caaf4ceecd2d4fae86
[imager.git] / polygon.c
1 #include "image.h"
2 #include "draw.h"
3 #include "log.h"
4
5
6 #define IMTRUNC(x) ((int)((x)*16))
7
8 #define coarse(x) ((x)/16)
9 #define fine(x)   ((x)%16)
10
11 #define POLY_DEB(x)
12
13
14
15 typedef int pcord;
16
17 typedef struct {
18   int n;
19   pcord x,y;
20 } p_point;
21
22 typedef struct {
23   int n;
24   pcord x1,y1;
25   pcord x2,y2;
26   pcord miny,maxy;
27   pcord minx,maxx;
28   int updown; /* -1 means down, 0 vertical, 1 up */
29 } p_line;
30
31 typedef struct {
32   int n;
33   double x;
34 } p_slice;
35
36 typedef struct {
37   int start;
38   int stop;
39 } ss_pair;
40
41 typedef struct {
42   int *line;            /* temporary buffer for scanline */
43   int linelen;          /* length of scanline */
44   ss_pair *ss_list;     /* list of start stop linepairs */
45   int ssnext;           /* index of the next pair to use */
46   int sslen;            /* maximum number of start stop pairs */
47 } ss_scanline;
48
49
50
51
52
53
54
55
56 static
57 int
58 p_compy(const p_point *p1, const p_point *p2) {
59   if (p1->y > p2->y) return 1;
60   if (p1->y < p2->y) return -1;
61   return 0;
62 }
63
64 static
65 int
66 p_compx(const p_slice *p1, const p_slice *p2) {
67   if (p1->x > p2->x) return 1;
68   if (p1->x < p2->x) return -1;
69   return 0;
70 }
71
72 /* Change this to int? and round right goddamn it! */
73
74 static
75 double
76 p_eval_aty(p_line *l, pcord y) {
77   int t;
78   t=l->y2-l->y1;
79   if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
80   return (l->x1+l->x2)/2.0;
81 }
82
83 static
84 double
85 p_eval_atx(p_line *l, pcord x) {
86   int t;
87   t = l->x2-l->x1;
88   if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
89   return (l->y1+l->y2)/2.0;
90 }
91
92 static
93 p_line *
94 line_set_new(double *x, double *y, int l) {
95   int i;
96   p_line *lset = mymalloc(sizeof(p_line) * l);
97
98   for(i=0; i<l; i++) {
99     lset[i].n=i;
100     lset[i].x1 = IMTRUNC(x[i]);
101     lset[i].y1 = IMTRUNC(y[i]);
102     lset[i].x2 = IMTRUNC(x[(i+1)%l]);
103     lset[i].y2 = IMTRUNC(y[(i+1)%l]);
104     lset[i].miny=min(lset[i].y1,lset[i].y2);
105     lset[i].maxy=max(lset[i].y1,lset[i].y2);
106     lset[i].minx=min(lset[i].x1,lset[i].x2);
107     lset[i].maxx=max(lset[i].x1,lset[i].x2);
108   }
109   return lset;
110 }
111
112 static
113 p_point *
114 point_set_new(double *x, double *y, int l) {
115   int i;
116   p_point *pset = mymalloc(sizeof(p_point) * l);
117   
118   for(i=0; i<l; i++) {
119     pset[i].n=i;
120     pset[i].x=IMTRUNC(x[i]);
121     pset[i].y=IMTRUNC(y[i]);
122   }
123   return pset;
124 }
125
126 static
127 void
128 p_line_dump(p_line *l) {
129   printf("%d (%d,%d)->(%d,%d) [%d-%d,%d-%d]\n", l->n, l->x1, l->y1, l->x2, l->y2, 
130          l->minx, l->maxx, l->miny, l->maxy);
131 }
132
133
134 static
135 void
136 ss_scanline_reset(ss_scanline *ss) {
137   ss->ssnext = 0;
138   memset(ss->line, 0, sizeof(int) * ss->linelen);
139 }
140
141 static
142 void
143 ss_scanline_init(ss_scanline *ss, int linelen, int linepairs) {
144   ss->line    = mymalloc( sizeof(int) * linelen );
145   ss->linelen = linelen;
146   ss->ss_list = mymalloc( sizeof(ss_pair) * linepairs );
147   ss->sslen   = linepairs;
148   ss_scanline_reset(ss);
149 }
150
151 static
152 void
153 ss_scanline_exorcise(ss_scanline *ss) {
154   myfree(ss->line);
155   myfree(ss->ss_list);
156 }
157   
158                      
159
160
161 /* returns the number of matches */
162
163 static
164 int
165 lines_in_interval(p_line *lset, int l, p_slice *tllist, pcord minc, pcord maxc) {
166   int k;
167   int count = 0;
168   for(k=0; k<l; k++) {
169     if (lset[k].maxy > minc && lset[k].miny < maxc) {
170       if (lset[k].miny == lset[k].maxy) {
171         POLY_DEB( printf(" HORIZONTAL - skipped\n") );
172       } else {
173         tllist[count].x=p_eval_aty(&lset[k],(minc+maxc)/2.0 );
174         tllist[count].n=k;
175         count++;
176       }
177     }
178   }
179   return count;
180 }
181
182 static
183 int
184 lines_in_interval_old(p_line *lset, int l, p_slice *tllist, pcord cc) {
185   int k;
186   int count = 0;
187   for(k=0; k<l; k++) {
188     if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
189       if (lset[k].miny == lset[k].maxy) {
190         POLY_DEB( printf(" HORIZONTAL - skipped\n") );
191       }
192       else {
193         tllist[count].x=p_eval_aty(&lset[k],cc);
194         tllist[count].n=k;
195         count++;
196       }
197     }
198   }
199   return count;
200 }
201
202 /* marks the up variable for all lines in a slice */
203
204 static
205 void
206 mark_updown_slices(p_line *lset, p_slice *tllist, int count) {
207   p_line *l, *r;
208   int k;
209   for(k=0; k<count; k+=2) {
210     l = lset + tllist[k].n;
211
212     if (l->y1 == l->y2) {
213       mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
214       exit(3);
215     }
216
217     l->updown = (l->x1 == l->x2) ?
218       0 :
219       (l->x1 > l->x2)
220       ? 
221       (l->y1 > l->y2) ? -1 : 1
222       : 
223       (l->y1 > l->y2) ? 1 : -1;
224
225     POLY_DEB( printf("marking left line %d as %s(%d)\n", l->n,
226                      l->updown ?  l->updown == 1 ? "up" : "down" : "vert", l->updown, l->updown)
227               );
228
229     if (k+1 >= count) {
230       mm_log((1, "Invalid polygon spec, odd number of line crossings.\n"));
231       return;
232     }
233
234     r = lset + tllist[k+1].n;
235     if (r->y1 == r->y2) {
236       mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
237       exit(3);
238     }
239
240     r->updown = (r->x1 == r->x2) ?
241       0 :
242       (r->x1 > r->x2)
243       ? 
244       (r->y1 > r->y2) ? -1 : 1
245       : 
246       (r->y1 > r->y2) ? 1 : -1;
247     
248     POLY_DEB( printf("marking right line %d as %s(%d)\n", r->n,
249                      r->updown ?  r->updown == 1 ? "up" : "down" : "vert", r->updown, r->updown)
250               );
251   }
252 }
253
254
255
256 static
257 unsigned char
258 saturate(int in) {
259   if (in>255) { return 255; }
260   else if (in>0) return in;
261   return 0;
262 }
263
264 typedef void (*scanline_flusher)(i_img *im, ss_scanline *ss, int y, void *ctx);
265
266 /* This function must be modified later to do proper blending */
267
268 void
269 scanline_flush(i_img *im, ss_scanline *ss, int y, void *ctx) {
270   int x, ch, tv;
271   i_color t;
272   i_color *val = (i_color *)ctx;
273   for(x=0; x<im->xsize; x++) {
274     tv = saturate(ss->line[x]);
275     i_gpix(im, x, y, &t);
276     for(ch=0; ch<im->channels; ch++) 
277       t.channel[ch] = tv/255.0 * val->channel[ch] + (1.0-tv/255.0) * t.channel[ch];
278     i_ppix(im, x, y, &t);
279   }
280 }
281
282
283
284 static
285 int
286 trap_square(pcord xlen, pcord ylen, double xl, double yl) {
287   POLY_DEB( printf("trap_square: %d %d %.2f %.2f\n", xlen, ylen, xl, yl) );
288   return xlen*ylen-(xl*yl)/2.0;
289 }
290
291
292 /* 
293    pixel_coverage calculates the 'left side' pixel coverage of a pixel that is
294    within the min/max ranges.  The shape always corresponds to a square with some
295    sort of a triangle cut from it (which can also yield a triangle).
296 */
297
298
299 static
300 int 
301 pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord  miny, pcord maxy) {
302   double lycross, rycross;
303   int l, r;
304
305   double xs, ys;
306   
307   if (!line->updown) {
308     l = r = 0;
309   } else {
310     lycross = p_eval_atx(line, minx);
311     rycross = p_eval_atx(line, maxx);
312     l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */
313     r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */
314   }
315   POLY_DEB(
316            printf("%4s(%+d): ", line->updown ?  line->updown == 1 ? "up" : "down" : "vert", line->updown);
317            printf("(%2d,%2d) [%3d-%3d, %3d-%3d] lycross=%.2f rycross=%.2f", coarse(minx), coarse(miny), minx, maxx, miny, maxy, lycross, rycross);
318            printf("    l=%d r=%d\n", l, r)
319            );
320   
321   if (l && r) 
322     return line->updown == 1 ? 
323       (double)(maxx-minx) * (2.0*maxy-lycross-rycross)/2.0  /* up case */
324       :
325       (double)(maxx-minx) * (lycross+rycross-2*miny)/2.0;  /* down case */
326   
327   if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0;
328
329   if (l && !r)
330     return line->updown == 1 ?
331       trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) : 
332       trap_square(maxx-minx, maxy-miny, p_eval_aty(line, maxy)-minx, maxy-p_eval_atx(line, minx));
333   
334
335   if (!l && r) {
336     int r = line->updown == 1 ?
337       (maxx-p_eval_aty(line, maxy))*(maxy-p_eval_atx(line, maxx))/2.0 : 
338       (maxx-p_eval_aty(line, miny))*(p_eval_atx(line, maxx)-miny)/2.0;
339     return r;
340   }
341 }
342
343
344
345
346
347 /* 
348    handle the scanline slice in three steps 
349    
350    1.  Where only the left edge is inside a pixel
351    2a. Where both left and right edge are inside a pixel
352    2b. Where neither left or right edge are inside a pixel
353    3.  Where only the right edge is inside a pixel
354 */
355
356 static
357 void
358 render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r) {
359   
360   pcord miny, maxy;     /* y bounds in fine coordinates */
361   pcord lminx, lmaxx;   /* left line min/max within y bounds in fine coords */
362   pcord rminx, rmaxx;   /* right line min/max within y bounds in fine coords */
363   int cpix;             /* x-coordinate of current pixel */
364   int thin;             /* boolean for thin/thick segment */
365   int startpix;         /* temporary variable for "start of this interval" */
366   int stoppix;          /* temporary variable for "end of this interval" */
367   int step2end;         /* temporary variable to mark where step2 ends */
368
369   /* Find the y bounds of scanline_slice */
370
371   maxy = min( l->maxy, r->maxy );
372   miny = max( l->miny, r->miny );
373
374   maxy = min( maxy, (y+1)*16 );
375   miny = max( miny,  y*16 );
376
377   lminx = min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
378   lmaxx = max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
379
380   rminx = min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
381   rmaxx = max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
382
383   thin = coarse(lmaxx) >= coarse(rminx);
384
385   startpix = max( coarse(lminx), 0 );
386   stoppix  = min( coarse(rmaxx-1), ss->linelen-1 );
387   
388   for(cpix=startpix; cpix<=stoppix; cpix++) {
389     int lt = coarse(lmaxx-1) >= cpix;
390     int rt = coarse(rminx) <= cpix;
391     
392     int A, B, C;
393     
394     POLY_DEB( printf("(%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
395
396     A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0;
397     B = lt ? 0 : 16*(maxy-miny);
398     C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0;
399
400     POLY_DEB( printf("A=%d B=%d C=%d\n", A, B, C) );
401
402     ss->line[cpix] += A+B-C;
403
404   }
405   
406 }
407
408
409
410 static
411 void
412 render_slice_scanline_old(ss_scanline *ss, int y, p_line *l, p_line *r) {
413   
414   pcord miny, maxy;     /* y bounds in fine coordinates */
415   pcord lminx, lmaxx;   /* left line min/max within y bounds in fine coords */
416   pcord rminx, rmaxx;   /* right line min/max within y bounds in fine coords */
417   int cpix;             /* x-coordinate of current pixel */
418   int thin;             /* boolean for thin/thick segment */
419   int startpix;         /* temporary variable for "start of this interval" */
420   int stoppix;          /* temporary variable for "end of this interval" */
421   int step2end;         /* temporary variable to mark where step2 ends */
422
423   /* Find the y bounds of scanline_slice */
424
425   maxy = min( l->maxy, r->maxy );
426   miny = max( l->miny, r->miny );
427
428   maxy = min( maxy, (y+1)*16 );
429   miny = max( miny,  y*16 );
430
431   lminx = min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
432   lmaxx = max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
433
434   rminx = min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
435   rmaxx = max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
436
437   thin = coarse(lmaxx) >= coarse(rminx);
438
439
440   /* First step */
441   startpix = coarse(lminx);                             /* includes tricky starting pixel */
442   stoppix  = min(coarse(lmaxx), coarse(rminx) );        /* last pixel is tricky */
443   
444   /* handle start pixel */
445
446   cpix = startpix;
447   if (cpix < stoppix) {
448     ss->line[cpix] += pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy);
449     printf("%2d: step1 - start pixel\n", cpix);
450   }
451   
452   for(cpix=startpix+1; cpix<stoppix; cpix++) {
453     printf("%2d: step1 pixel\n", cpix);
454     ss->line[cpix] += l->updown == 1 ? 
455       8.0 * (2*maxy-p_eval_atx(l, 16*cpix)-p_eval_atx(l, 16*cpix+16))   /* up case */
456       :
457       8.0 * (p_eval_atx(l, 16*cpix)+p_eval_atx(l, 16*cpix+16)-2*miny);  /* down case */
458   }
459   
460   
461   /* handle stop pixel */
462
463   if (thin) { /* step 2a */
464     startpix = coarse(rminx);
465     stoppix = coarse(lmaxx+15); /* one more than needed */
466     
467     for(cpix=startpix; cpix<stoppix; cpix++) {
468       printf("%2d: step2a pixel\n", cpix);
469       ss->line[cpix] += 
470         pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy)
471         +(cpix*16+16-min(cpix*16+16, l->maxx))*(maxy-miny)
472         -pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy);
473     }
474   } else { /* step 2b */
475     stoppix = coarse(rminx);
476     for(/* cpix already correct */; cpix<stoppix; cpix++) {
477       printf("%2d: step2b pixel\n", cpix);
478       ss->line[cpix] += 16.0*(maxy-miny);
479     }
480   }
481   
482   /* step 3 */
483
484   cpix = max(coarse(rminx), coarse(lmaxx+15));
485   stoppix = coarse(rmaxx-15);
486   
487   printf("step3 from %d to %d\n", cpix, stoppix);
488
489   for(; cpix<stoppix; cpix++) {
490     printf("%2d: step3 pixel\n", cpix);
491     ss->line[cpix] += 0+ 
492       (l->updown == 1 ?
493        8.0 * (2*maxy-p_eval_atx(r, 16*cpix)-p_eval_atx(r, 16*cpix+16))  /* up case */
494        :
495        8.0 * (p_eval_atx(r, 16*cpix)+p_eval_atx(r, 16*cpix+16)-2*miny));  /* down case */
496   }
497   
498   ss->line[cpix] += (16.0)*(maxy-miny) - pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy);
499 }
500
501
502
503
504
505
506 /* Antialiasing polygon algorithm 
507    specs:
508    1. only nice polygons - no crossovers
509    2. 1/16 pixel resolution
510    3. full antialiasing ( complete spectrum of blends )
511    4. uses hardly any memory
512    5. no subsampling phase
513    
514
515    Algorithm outline:
516    1. Split into vertical intervals.
517    2. handle each interval 
518
519    For each interval we must: 
520    1. find which lines are in it
521    2. order the lines from in increasing x order.
522       since we are assuming no crossovers it is sufficent
523       to check a single point on each line.
524 */
525
526 /*
527   Definitions:
528   
529   1. Interval:  A vertical segment in which no lines cross nor end.
530   2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
531   3. Slice:     A start stop line pair.
532   
533  */
534
535
536 void
537 i_poly_aa_low(i_img *im, int l, double *x, double *y, void *ctx, scanline_flusher flusher) {
538   int i ,k;                     /* Index variables */
539   int clc;                      /* Lines inside current interval */
540   pcord miny ,maxy;             /* Min and max values of the current slice in the subcord system */
541   pcord tempy;
542   int cscl;                     /* Current scanline */
543
544   ss_scanline templine;         /* scanline accumulator */
545   p_point *pset;                /* List of points in polygon */
546   p_line  *lset;                /* List of lines in polygon */
547   p_slice *tllist;              /* List of slices */
548
549   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));
550
551   for(i=0; i<l; i++) {
552     mm_log((2, "(%.2f, %.2f)\n", x[i], y[i]));
553   }
554
555
556   POLY_DEB(
557            fflush(stdout);
558            setbuf(stdout, NULL);
559            );
560
561   tllist   = mymalloc(sizeof(p_slice)*l);
562   
563   ss_scanline_init(&templine, im->xsize, l);
564
565   pset     = point_set_new(x, y, l);
566   lset     = line_set_new(x, y, l);
567
568
569   qsort(pset, l, sizeof(p_point), (int(*)(const void *,const void *))p_compy);
570   
571   POLY_DEB(
572            for(i=0;i<l;i++) {
573              printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",
574                     i, lset[i].n, lset[i].x1, lset[i].y1, lset[i].x2, lset[i].y2, lset[i].miny, lset[i].maxy);
575            }
576            printf("MAIN LOOP\n\n");
577            );
578   
579
580   /* loop on intervals */
581   for(i=0; i<l-1; i++) {
582     int startscan = max( coarse(pset[i].y), 0);
583     int stopscan = min( coarse(pset[i+1].y+15), im->ysize);
584     pcord cc = (pset[i].y + pset[i+1].y)/2;
585
586     if (pset[i].y == pset[i+1].y) {
587       POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
588       continue;
589     }
590
591     POLY_DEB(
592              printf("current slice is %d: %d to %d ( cpoint %d ) scanlines %d to %d\n", 
593                     i, pset[i].y, pset[i+1].y, cc, startscan, stopscan)
594              );
595     
596     
597     clc = lines_in_interval(lset, l, tllist, pset[i].y, pset[i+1].y);
598     qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
599
600     mark_updown_slices(lset, tllist, clc);
601
602     POLY_DEB( printf("Interval contains %d lines\n", clc) );
603
604     for(k=0; k<clc; k++) {
605       int lno = tllist[k].n;
606       p_line *ln = lset+lno;
607       POLY_DEB(
608                printf("%d:  line #%2d: (%2d, %2d)->(%2d, %2d) (%2d/%2d, %2d/%2d) -> (%2d/%2d, %2d/%2d) alignment=%s\n",
609                       k, lno, ln->x1, ln->y1, ln->x2, ln->y2, 
610                       coarse(ln->x1), fine(ln->x1), 
611                       coarse(ln->y1), fine(ln->y1), 
612                       coarse(ln->x2), fine(ln->x2), 
613                       coarse(ln->y2), fine(ln->y2),
614                       ln->updown == 0 ? "vert" : ln->updown == 1 ? "up" : "down")
615                );
616     }
617     for(cscl=startscan; cscl<stopscan; cscl++) {
618       tempy = min(cscl*16+16, pset[i+1].y);
619       POLY_DEB( printf("evaluating scan line %d \n", cscl) );
620       for(k=0; k<clc-1; k+=2) {
621         POLY_DEB( printf("evaluating slice %d\n", k) );
622         render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n);
623       }
624       if (16*coarse(tempy) == tempy) {
625         POLY_DEB( printf("flushing scan line %d\n", cscl) );
626         flusher(im, &templine, cscl, ctx);
627         ss_scanline_reset(&templine);
628       }
629       /*
630         else {
631         scanline_flush(im, &templine, cscl, val);
632         ss_scanline_reset(&templine);
633         return 0;
634         }
635       */
636     }
637   } /* Intervals */
638   if (16*coarse(tempy) != tempy) 
639     flusher(im, &templine, cscl-1, ctx);
640
641   ss_scanline_exorcise(&templine);
642   myfree(pset);
643   myfree(lset);
644   myfree(tllist);
645   
646 } /* Function */
647
648 void
649 i_poly_aa(i_img *im, int l, double *x, double *y, i_color *val) {
650   i_poly_aa_low(im, l, x, y, val, scanline_flush);
651 }
652
653 struct poly_cfill_state {
654   i_color *fillbuf;
655   i_color *linebuf;
656   int *cover;
657   i_fill_t *fill;
658 };
659
660 void
661 scanline_flush_cfill(i_img *im, ss_scanline *ss, int y, void *ctx) {
662   int x, ch, tv;
663   i_color t;
664   int pos;
665   int left, right;
666   struct poly_cfill_state *state = (struct poly_cfill_state *)ctx;
667   i_color *fillbuf = state->fillbuf;
668   i_color *line = state->linebuf;
669
670   left = 0;
671   while (left < im->xsize && ss->line[left] <= 0)
672     ++left;
673   if (left < im->xsize) {
674     right = im->xsize;
675     /* since going from the left found something, moving from the 
676        right should */
677     while (/* right > left && */ ss->line[right-1] <= 0) 
678       --right;
679     
680     (state->fill->fill_with_color)(state->fill, left, y, right-left, 
681                                    im->channels, fillbuf);
682     i_glin(im, left, right, y, line);
683     pos = 0;
684     if (state->fill->combine) {
685       for (x = left; x < right; ++x) {
686         tv = saturate(ss->line[x]);
687         fillbuf[pos].channel[3] = 
688           fillbuf[pos].channel[3] * tv / 255;
689       }
690       (state->fill->combine)(line, fillbuf, im->channels, right-left);
691       pos++;
692     }
693     else {
694       for (x = left; x < right; ++x) {
695         tv = saturate(ss->line[x]);
696         if (tv) { 
697           if (tv == 255) {
698             line[pos] = fillbuf[pos];
699           }
700           else {
701             i_color *to = line + pos;
702             i_color *from = fillbuf + pos;
703             for (ch = 0; ch < im->channels; ++ch) {
704               to->channel[ch] = (tv * from->channel[ch] + 
705                                  (255 - tv) * to->channel[ch]) / 255;
706             }
707           }
708         }
709         pos++;
710       }
711     }
712     i_plin(im, left, right, y, line);
713   }
714 }
715
716 struct poly_cfill_state_f {
717   i_fcolor *fillbuf;
718   i_fcolor *linebuf;
719   int *cover;
720   i_fill_t *fill;
721 };
722
723 void
724 scanline_flush_cfill_f(i_img *im, ss_scanline *ss, int y, void *ctx) {
725   int x, ch, tv;
726   int pos;
727   int left, right;
728   struct poly_cfill_state_f *state = (struct poly_cfill_state_f *)ctx;
729   i_fcolor *fillbuf = state->fillbuf;
730   i_fcolor *line = state->linebuf;
731
732   left = 0;
733   while (left < im->xsize && ss->line[left] <= 0)
734     ++left;
735   if (left < im->xsize) {
736     right = im->xsize;
737     /* since going from the left found something, moving from the 
738        right should */
739     while (/* right > left && */ ss->line[right-1] <= 0) 
740       --right;
741     
742     (state->fill->fill_with_fcolor)(state->fill, left, y, right-left, 
743                                     im->channels, fillbuf);
744     i_glinf(im, left, right, y, line);
745     pos = 0;
746     if (state->fill->combinef) {
747       for (x = left; x < right; ++x) {
748         tv = saturate(ss->line[x]);
749         fillbuf[pos].channel[3] = 
750           fillbuf[pos].channel[3] * tv / 255;
751       }
752       (state->fill->combinef)(line, fillbuf, im->channels, right-left);
753       pos++;
754     }
755     else {
756       for (x = left; x < right; ++x) {
757         tv = saturate(ss->line[x]);
758         if (tv) { 
759           if (tv == 255) {
760             line[pos] = fillbuf[pos];
761           }
762           else {
763             i_fcolor *to = line + pos;
764             i_fcolor *from = fillbuf + pos;
765             for (ch = 0; ch < im->channels; ++ch) {
766               to->channel[ch] = (tv * from->channel[ch] + 
767                                  (255 - tv) * to->channel[ch]) / 255;
768             }
769           }
770         }
771         pos++;
772       }
773     }
774     i_plinf(im, left, right, y, line);
775   }
776 }
777
778 void
779 i_poly_aa_cfill(i_img *im, int l, double *x, double *y, i_fill_t *fill) {
780   if (im->bits == i_8_bits && fill->fill_with_color) {
781     struct poly_cfill_state ctx;
782     ctx.fillbuf = mymalloc(sizeof(i_color) * im->xsize * 2);
783     ctx.linebuf = ctx.fillbuf + im->xsize;
784     ctx.cover = mymalloc(sizeof(int) * im->xsize);
785     ctx.fill = fill;
786     i_poly_aa_low(im, l, x, y, &ctx, scanline_flush_cfill);
787     myfree(ctx.fillbuf);
788     myfree(ctx.cover);
789   }
790   else {
791     struct poly_cfill_state_f ctx;
792     ctx.fillbuf = mymalloc(sizeof(i_fcolor) * im->xsize * 2);
793     ctx.linebuf = ctx.fillbuf + im->xsize;
794     ctx.cover = mymalloc(sizeof(int) * im->xsize);
795     ctx.fill = fill;
796     i_poly_aa_low(im, l, x, y, &ctx, scanline_flush_cfill_f);
797     myfree(ctx.fillbuf);
798     myfree(ctx.cover);
799   }
800 }