polygon.c

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