draw.c

   1 #define IMAGER_NO_CONTEXT
   2 #include "imager.h"
   3 #include "draw.h"
   4 #include "log.h"
   5 #include "imageri.h"
   6 #include "imrender.h"
   7 #include <limits.h>
   8
   9 int
  10 i_ppix_norm(i_img *im, i_img_dim x, i_img_dim y, i_color const *col) {
  11   i_color src;
  12   i_color work;
  13   int dest_alpha;
  14   int remains;
  15
  16   if (!col->channel[3])
  17     return 0;
  18
  19   switch (im->channels) {
  20   case 1:
  21     work = *col;
  22     i_adapt_colors(2, 4, &work, 1);
  23     i_gpix(im, x, y, &src);
  24     remains = 255 - work.channel[1];
  25     src.channel[0] = (src.channel[0] * remains
  26                       + work.channel[0] * work.channel[1]) / 255;
  27     return i_ppix(im, x, y, &src);
  28
  29   case 2:
  30     work = *col;
  31     i_adapt_colors(2, 4, &work, 1);
  32     i_gpix(im, x, y, &src);
  33     remains = 255 - work.channel[1];
  34     dest_alpha = work.channel[1] + remains * src.channel[1] / 255;
  35     if (work.channel[1] == 255) {
  36       return i_ppix(im, x, y, &work);
  37     }
  38     else {
  39       src.channel[0] = (work.channel[1] * work.channel[0]
  40                         + remains * src.channel[0] * src.channel[1] / 255) / dest_alpha;
  41       src.channel[1] = dest_alpha;
  42       return i_ppix(im, x, y, &src);
  43     }
  44
  45   case 3:
  46     work = *col;
  47     i_gpix(im, x, y, &src);
  48     remains = 255 - work.channel[3];
  49     src.channel[0] = (src.channel[0] * remains
  50                       + work.channel[0] * work.channel[3]) / 255;
  51     src.channel[1] = (src.channel[1] * remains
  52                       + work.channel[1] * work.channel[3]) / 255;
  53     src.channel[2] = (src.channel[2] * remains
  54                       + work.channel[2] * work.channel[3]) / 255;
  55     return i_ppix(im, x, y, &src);
  56
  57   case 4:
  58     work = *col;
  59     i_gpix(im, x, y, &src);
  60     remains = 255 - work.channel[3];
  61     dest_alpha = work.channel[3] + remains * src.channel[3] / 255;
  62     if (work.channel[3] == 255) {
  63       return i_ppix(im, x, y, &work);
  64     }
  65     else {
  66       src.channel[0] = (work.channel[3] * work.channel[0]
  67                         + remains * src.channel[0] * src.channel[3] / 255) / dest_alpha;
  68       src.channel[1] = (work.channel[3] * work.channel[1]
  69                         + remains * src.channel[1] * src.channel[3] / 255) / dest_alpha;
  70       src.channel[2] = (work.channel[3] * work.channel[2]
  71                         + remains * src.channel[2] * src.channel[3] / 255) / dest_alpha;
  72       src.channel[3] = dest_alpha;
  73       return i_ppix(im, x, y, &src);
  74     }
  75   }
  76   return 0;
  77 }
  78
  79 static void
  80 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm,
  81                i_img_dim bxmin, i_img_dim bxmax, i_img_dim bymin, i_img_dim bymax);
  82
  83 void
  84 i_mmarray_cr(i_mmarray *ar,i_img_dim l) {
  85   i_img_dim i;
  86   size_t alloc_size;
  87
  88   ar->lines=l;
  89   alloc_size = sizeof(minmax) * l;
  90   /* check for overflow */
  91   if (alloc_size / l != sizeof(minmax)) {
  92     fprintf(stderr, "overflow calculating memory allocation");
  93     exit(3);
  94   }
  95   ar->data=mymalloc(alloc_size); /* checked 5jul05 tonyc */
  96   for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
  97 }
  98
  99 void
 100 i_mmarray_dst(i_mmarray *ar) {
 101   ar->lines=0;
 102   if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
 103 }
 104
 105 void
 106 i_mmarray_add(i_mmarray *ar,i_img_dim x,i_img_dim y) {
 107   if (y>-1 && y<ar->lines)
 108     {
 109       if (x<ar->data[y].min) ar->data[y].min=x;
 110       if (x>ar->data[y].max) ar->data[y].max=x;
 111     }
 112 }
 113
 114 int
 115 i_mmarray_gmin(i_mmarray *ar,i_img_dim y) {
 116   if (y>-1 && y<ar->lines) return ar->data[y].min;
 117   else return -1;
 118 }
 119
 120 int
 121 i_mmarray_getm(i_mmarray *ar,i_img_dim y) {
 122   if (y>-1 && y<ar->lines) return ar->data[y].max;
 123   else return MAXINT;
 124 }
 125
 126 #if 0
 127 /* unused? */
 128 void
 129 i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
 130   i_img_dim i,x;
 131   for(i=0;i<ar->lines;i++) if (ar->data[i].max!=-1) for(x=ar->data[i].min;x<ar->data[i].max;x++) i_ppix(im,x,i,val);
 132 }
 133 #endif
 134
 135 static
 136 void
 137 i_arcdraw(i_img_dim x1, i_img_dim y1, i_img_dim x2, i_img_dim y2, i_mmarray *ar) {
 138   double alpha;
 139   double dsec;
 140   i_img_dim temp;
 141   alpha=(double)(y2-y1)/(double)(x2-x1);
 142   if (fabs(alpha) <= 1)
 143     {
 144       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 145       dsec=y1;
 146       while(x1<=x2)
 147         {
 148           i_mmarray_add(ar,x1,(i_img_dim)(dsec+0.5));
 149           dsec+=alpha;
 150           x1++;
 151         }
 152     }
 153   else
 154     {
 155       alpha=1/alpha;
 156       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 157       dsec=x1;
 158       while(y1<=y2)
 159         {
 160           i_mmarray_add(ar,(i_img_dim)(dsec+0.5),y1);
 161           dsec+=alpha;
 162           y1++;
 163         }
 164     }
 165 }
 166
 167 void
 168 i_mmarray_info(i_mmarray *ar) {
 169   i_img_dim i;
 170   for(i=0;i<ar->lines;i++)
 171   if (ar->data[i].max!=-1)
 172     printf("line %"i_DF ": min=%" i_DF ", max=%" i_DF ".\n",
 173            i_DFc(i), i_DFc(ar->data[i].min), i_DFc(ar->data[i].max));
 174 }
 175
 176 static void
 177 i_arc_minmax(i_int_hlines *hlines,i_img_dim x,i_img_dim y, double rad,float d1,float d2) {
 178   i_mmarray dot;
 179   double f;
 180   i_img_dim x1,y1;
 181
 182   i_mmarray_cr(&dot, hlines->limit_y);
 183
 184   x1=(i_img_dim)(x+0.5+rad*cos(d1*PI/180.0));
 185   y1=(i_img_dim)(y+0.5+rad*sin(d1*PI/180.0));
 186
 187   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 188   i_arcdraw(x, y, x1, y1, &dot);
 189
 190   x1=(i_img_dim)(x+0.5+rad*cos(d2*PI/180.0));
 191   y1=(i_img_dim)(y+0.5+rad*sin(d2*PI/180.0));
 192
 193   for(f=d1;f<=d2;f+=0.01)
 194     i_mmarray_add(&dot,(i_img_dim)(x+0.5+rad*cos(f*PI/180.0)),(i_img_dim)(y+0.5+rad*sin(f*PI/180.0)));
 195
 196   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 197   i_arcdraw(x, y, x1, y1, &dot);
 198
 199   /* render the minmax values onto the hlines */
 200   for (y = 0; y < dot.lines; y++) {
 201     if (dot.data[y].max!=-1) {
 202       i_img_dim minx, width;
 203       minx = dot.data[y].min;
 204       width = dot.data[y].max - dot.data[y].min + 1;
 205       i_int_hlines_add(hlines, y, minx, width);
 206     }
 207   }
 208
 209   /*  dot.info(); */
 210   i_mmarray_dst(&dot);
 211 }
 212
 213 static void
 214 i_arc_hlines(i_int_hlines *hlines,i_img_dim x,i_img_dim y,double rad,float d1,float d2) {
 215   if (d1 <= d2) {
 216     i_arc_minmax(hlines, x, y, rad, d1, d2);
 217   }
 218   else {
 219     i_arc_minmax(hlines, x, y, rad, d1, 360);
 220     i_arc_minmax(hlines, x, y, rad, 0, d2);
 221   }
 222 }
 223
 224 /*
 225 =item i_arc(im, x, y, rad, d1, d2, color)
 226
 227 =category Drawing
 228 =synopsis i_arc(im, 50, 50, 20, 45, 135, &color);
 229
 230 Fills an arc centered at (x,y) with radius I<rad> covering the range
 231 of angles in degrees from d1 to d2, with the color.
 232
 233 =cut
 234 */
 235
 236 void
 237 i_arc(i_img *im, i_img_dim x, i_img_dim y,double rad,double d1,double d2,const i_color *val) {
 238   i_int_hlines hlines;
 239   dIMCTXim(im);
 240
 241   im_log((aIMCTX,1,"i_arc(im %p,(x,y)=(" i_DFp "), rad %f, d1 %f, d2 %f, col %p)",
 242           im, i_DFcp(x, y), rad, d1, d2, val));
 243
 244   i_int_init_hlines_img(&hlines, im);
 245
 246   i_arc_hlines(&hlines, x, y, rad, d1, d2);
 247
 248   i_int_hlines_fill_color(im, &hlines, val);
 249
 250   i_int_hlines_destroy(&hlines);
 251 }
 252
 253 /*
 254 =item i_arc_cfill(im, x, y, rad, d1, d2, fill)
 255
 256 =category Drawing
 257 =synopsis i_arc_cfill(im, 50, 50, 35, 90, 135, fill);
 258
 259 Fills an arc centered at (x,y) with radius I<rad> covering the range
 260 of angles in degrees from d1 to d2, with the fill object.
 261
 262 =cut
 263 */
 264
 265 #define MIN_CIRCLE_STEPS 8
 266 #define MAX_CIRCLE_STEPS 360
 267
 268 void
 269 i_arc_cfill(i_img *im, i_img_dim x, i_img_dim y,double rad,double d1,double d2,i_fill_t *fill) {
 270   i_int_hlines hlines;
 271   dIMCTXim(im);
 272
 273   im_log((aIMCTX,1,"i_arc_cfill(im %p,(x,y)=(" i_DFp "), rad %f, d1 %f, d2 %f, fill %p)",
 274           im, i_DFcp(x, y), rad, d1, d2, fill));
 275
 276   i_int_init_hlines_img(&hlines, im);
 277
 278   i_arc_hlines(&hlines, x, y, rad, d1, d2);
 279
 280   i_int_hlines_fill_fill(im, &hlines, fill);
 281
 282   i_int_hlines_destroy(&hlines);
 283 }
 284
 285 static void
 286 arc_poly(int *count, double **xvals, double **yvals,
 287          double x, double y, double rad, double d1, double d2) {
 288   double d1_rad, d2_rad;
 289   double circum;
 290   i_img_dim steps, point_count;
 291   double angle_inc;
 292
 293   /* normalize the angles */
 294   d1 = fmod(d1, 360);
 295   if (d1 == 0) {
 296     if (d2 >= 360) { /* default is 361 */
 297       d2 = 360;
 298     }
 299     else {
 300       d2 = fmod(d2, 360);
 301       if (d2 < d1)
 302         d2 += 360;
 303     }
 304   }
 305   else {
 306     d2 = fmod(d2, 360);
 307     if (d2 < d1)
 308       d2 += 360;
 309   }
 310   d1_rad = d1 * PI / 180;
 311   d2_rad = d2 * PI / 180;
 312
 313   /* how many segments for the curved part?
 314      we do a maximum of one per degree, with a minimum of 8/circle
 315      we try to aim at having about one segment per 2 pixels
 316      Work it out per circle to get a step size.
 317
 318      I was originally making steps = circum/2 but that looked horrible.
 319
 320      I think there might be an issue in the polygon filler.
 321   */
 322   circum = 2 * PI * rad;
 323   steps = circum;
 324   if (steps > MAX_CIRCLE_STEPS)
 325     steps = MAX_CIRCLE_STEPS;
 326   else if (steps < MIN_CIRCLE_STEPS)
 327     steps = MIN_CIRCLE_STEPS;
 328
 329   angle_inc = 2 * PI / steps;
 330
 331   point_count = steps + 5; /* rough */
 332   /* point_count is always relatively small, so allocation won't overflow */
 333   *xvals = mymalloc(point_count * sizeof(double)); /* checked 17feb2005 tonyc */
 334   *yvals = mymalloc(point_count * sizeof(double)); /* checked 17feb2005 tonyc */
 335
 336   /* from centre to edge at d1 */
 337   (*xvals)[0] = x;
 338   (*yvals)[0] = y;
 339   (*xvals)[1] = x + rad * cos(d1_rad);
 340   (*yvals)[1] = y + rad * sin(d1_rad);
 341   *count = 2;
 342
 343   /* step around the curve */
 344   while (d1_rad < d2_rad) {
 345     (*xvals)[*count] = x + rad * cos(d1_rad);
 346     (*yvals)[*count] = y + rad * sin(d1_rad);
 347     ++*count;
 348     d1_rad += angle_inc;
 349   }
 350
 351   /* finish off the curve */
 352   (*xvals)[*count] = x + rad * cos(d2_rad);
 353   (*yvals)[*count] = y + rad * sin(d2_rad);
 354   ++*count;
 355 }
 356
 357 /*
 358 =item i_arc_aa(im, x, y, rad, d1, d2, color)
 359
 360 =category Drawing
 361 =synopsis i_arc_aa(im, 50, 50, 35, 90, 135, &color);
 362
 363 Anti-alias fills an arc centered at (x,y) with radius I<rad> covering
 364 the range of angles in degrees from d1 to d2, with the color.
 365
 366 =cut
 367 */
 368
 369 void
 370 i_arc_aa(i_img *im, double x, double y, double rad, double d1, double d2,
 371          const i_color *val) {
 372   double *xvals, *yvals;
 373   int count;
 374   dIMCTXim(im);
 375
 376   im_log((aIMCTX,1,"i_arc_aa(im %p,(x,y)=(%f,%f), rad %f, d1 %f, d2 %f, col %p)",
 377           im, x, y, rad, d1, d2, val));
 378
 379   arc_poly(&count, &xvals, &yvals, x, y, rad, d1, d2);
 380
 381   i_poly_aa(im, count, xvals, yvals, val);
 382
 383   myfree(xvals);
 384   myfree(yvals);
 385 }
 386
 387 /*
 388 =item i_arc_aa_cfill(im, x, y, rad, d1, d2, fill)
 389
 390 =category Drawing
 391 =synopsis i_arc_aa_cfill(im, 50, 50, 35, 90, 135, fill);
 392
 393 Anti-alias fills an arc centered at (x,y) with radius I<rad> covering
 394 the range of angles in degrees from d1 to d2, with the fill object.
 395
 396 =cut
 397 */
 398
 399 void
 400 i_arc_aa_cfill(i_img *im, double x, double y, double rad, double d1, double d2,
 401                i_fill_t *fill) {
 402   double *xvals, *yvals;
 403   int count;
 404   dIMCTXim(im);
 405
 406   im_log((aIMCTX,1,"i_arc_aa_cfill(im %p,(x,y)=(%f,%f), rad %f, d1 %f, d2 %f, fill %p)",
 407           im, x, y, rad, d1, d2, fill));
 408
 409   arc_poly(&count, &xvals, &yvals, x, y, rad, d1, d2);
 410
 411   i_poly_aa_cfill(im, count, xvals, yvals, fill);
 412
 413   myfree(xvals);
 414   myfree(yvals);
 415 }
 416
 417 /* Temporary AA HACK */
 418
 419
 420 typedef i_img_dim frac;
 421 static  frac float_to_frac(double x) { return (frac)(0.5+x*16.0); }
 422
 423 static
 424 void
 425 polar_to_plane(double cx, double cy, float angle, double radius, frac *x, frac *y) {
 426   *x = float_to_frac(cx+radius*cos(angle));
 427   *y = float_to_frac(cy+radius*sin(angle));
 428 }
 429
 430 static
 431 void
 432 make_minmax_list(pIMCTX, i_mmarray *dot, double x, double y, double radius) {
 433   float angle = 0.0;
 434   float astep = radius>0.1 ? .5/radius : 10;
 435   frac cx, cy, lx, ly, sx, sy;
 436
 437   im_log((aIMCTX, 1, "make_minmax_list(dot %p, x %.2f, y %.2f, radius %.2f)\n", dot, x, y, radius));
 438
 439   polar_to_plane(x, y, angle, radius, &sx, &sy);
 440
 441   for(angle = 0.0; angle<361; angle +=astep) {
 442     lx = sx; ly = sy;
 443     polar_to_plane(x, y, angle, radius, &cx, &cy);
 444     sx = cx; sy = cy;
 445
 446     if (fabs(cx-lx) > fabs(cy-ly)) {
 447       int ccx, ccy;
 448       if (lx>cx) {
 449         ccx = lx; lx = cx; cx = ccx;
 450         ccy = ly; ly = cy; cy = ccy;
 451       }
 452
 453       for(ccx=lx; ccx<=cx; ccx++) {
 454         ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
 455         i_mmarray_add(dot, ccx, ccy);
 456       }
 457     } else {
 458       int ccx, ccy;
 459
 460       if (ly>cy) {
 461         ccy = ly; ly = cy; cy = ccy;
 462         ccx = lx; lx = cx; cx = ccx;
 463       }
 464
 465       for(ccy=ly; ccy<=cy; ccy++) {
 466         if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
 467         i_mmarray_add(dot, ccx, ccy);
 468       }
 469     }
 470   }
 471 }
 472
 473 /* Get the number of subpixels covered */
 474
 475 static
 476 int
 477 i_pixel_coverage(i_mmarray *dot, i_img_dim x, i_img_dim y) {
 478   frac minx = x*16;
 479   frac maxx = minx+15;
 480   frac cy;
 481   int cnt = 0;
 482
 483   for(cy=y*16; cy<(y+1)*16; cy++) {
 484     frac tmin = dot->data[cy].min;
 485     frac tmax = dot->data[cy].max;
 486
 487     if (tmax == -1 || tmin > maxx || tmax < minx) continue;
 488
 489     if (tmin < minx) tmin = minx;
 490     if (tmax > maxx) tmax = maxx;
 491
 492     cnt+=1+tmax-tmin;
 493   }
 494   return cnt;
 495 }
 496
 497 /*
 498 =item i_circle_aa(im, x, y, rad, color)
 499
 500 =category Drawing
 501 =synopsis i_circle_aa(im, 50, 50, 45, &color);
 502
 503 Anti-alias fills a circle centered at (x,y) for radius I<rad> with
 504 color.
 505
 506 =cut
 507 */
 508 void
 509 i_circle_aa(i_img *im, double x, double y, double rad, const i_color *val) {
 510   i_mmarray dot;
 511   i_color temp;
 512   i_img_dim ly;
 513   dIMCTXim(im);
 514
 515   im_log((aIMCTX, 1, "i_circle_aa(im %p, centre(" i_DFp "), rad %.2f, val %p)\n",
 516           im, i_DFcp(x, y), rad, val));
 517
 518   i_mmarray_cr(&dot,16*im->ysize);
 519   make_minmax_list(aIMCTX, &dot, x, y, rad);
 520
 521   for(ly = 0; ly<im->ysize; ly++) {
 522     int ix, cy, minx = INT_MAX, maxx = INT_MIN;
 523
 524     /* Find the left/rightmost set subpixels */
 525     for(cy = 0; cy<16; cy++) {
 526       frac tmin = dot.data[ly*16+cy].min;
 527       frac tmax = dot.data[ly*16+cy].max;
 528       if (tmax == -1) continue;
 529
 530       if (minx > tmin) minx = tmin;
 531       if (maxx < tmax) maxx = tmax;
 532     }
 533
 534     if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
 535
 536     minx /= 16;
 537     maxx /= 16;
 538     for(ix=minx; ix<=maxx; ix++) {
 539       int cnt = i_pixel_coverage(&dot, ix, ly);
 540       if (cnt>255) cnt = 255;
 541       if (cnt) { /* should never be true */
 542         int ch;
 543         float ratio = (float)cnt/255.0;
 544         i_gpix(im, ix, ly, &temp);
 545         for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
 546         i_ppix(im, ix, ly, &temp);
 547       }
 548     }
 549   }
 550   i_mmarray_dst(&dot);
 551 }
 552
 553 /*
 554 =item i_circle_out(im, x, y, r, col)
 555
 556 =category Drawing
 557 =synopsis i_circle_out(im, 50, 50, 45, &color);
 558
 559 Draw a circle outline centered at (x,y) with radius r,
 560 non-anti-aliased.
 561
 562 Parameters:
 563
 564 =over
 565
 566 =item *
 567
 568 (x, y) - the center of the circle
 569
 570 =item *
 571
 572 r - the radius of the circle in pixels, must be non-negative
 573
 574 =back
 575
 576 Returns non-zero on success.
 577
 578 Implementation:
 579
 580 =cut
 581 */
 582
 583 int
 584 i_circle_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
 585              const i_color *col) {
 586   i_img_dim x, y;
 587   i_img_dim dx, dy;
 588   int error;
 589   dIMCTXim(im);
 590
 591   im_log((aIMCTX, 1, "i_circle_out(im %p, centre(" i_DFp "), rad %" i_DF ", col %p)\n",
 592           im, i_DFcp(xc, yc), i_DFc(r), col));
 593
 594   im_clear_error(aIMCTX);
 595
 596   if (r < 0) {
 597     im_push_error(aIMCTX, 0, "circle: radius must be non-negative");
 598     return 0;
 599   }
 600
 601   i_ppix(im, xc+r, yc, col);
 602   i_ppix(im, xc-r, yc, col);
 603   i_ppix(im, xc, yc+r, col);
 604   i_ppix(im, xc, yc-r, col);
 605
 606   x = 0;
 607   y = r;
 608   dx = 1;
 609   dy = -2 * r;
 610   error = 1 - r;
 611   while (x < y) {
 612     if (error >= 0) {
 613       --y;
 614       dy += 2;
 615       error += dy;
 616     }
 617     ++x;
 618     dx += 2;
 619     error += dx;
 620
 621     i_ppix(im, xc + x, yc + y, col);
 622     i_ppix(im, xc + x, yc - y, col);
 623     i_ppix(im, xc - x, yc + y, col);
 624     i_ppix(im, xc - x, yc - y, col);
 625     if (x != y) {
 626       i_ppix(im, xc + y, yc + x, col);
 627       i_ppix(im, xc + y, yc - x, col);
 628       i_ppix(im, xc - y, yc + x, col);
 629       i_ppix(im, xc - y, yc - x, col);
 630     }
 631   }
 632
 633   return 1;
 634 }
 635
 636 /*
 637 =item arc_seg(angle)
 638
 639 Convert an angle in degrees into an angle measure we can generate
 640 simply from the numbers we have when drawing the circle.
 641
 642 =cut
 643 */
 644
 645 static i_img_dim
 646 arc_seg(double angle, int scale) {
 647   i_img_dim seg = (angle + 45) / 90;
 648   double remains = angle - seg * 90; /* should be in the range [-45,45] */
 649
 650   while (seg > 4)
 651     seg -= 4;
 652   if (seg == 4 && remains > 0)
 653     seg = 0;
 654
 655   return scale * (seg * 2 + sin(remains * PI/180));
 656 }
 657
 658 /*
 659 =item i_arc_out(im, x, y, r, d1, d2, col)
 660
 661 =category Drawing
 662 =synopsis i_arc_out(im, 50, 50, 45, 45, 135, &color);
 663
 664 Draw an arc outline centered at (x,y) with radius r, non-anti-aliased
 665 over the angle range d1 through d2 degrees.
 666
 667 Parameters:
 668
 669 =over
 670
 671 =item *
 672
 673 (x, y) - the center of the circle
 674
 675 =item *
 676
 677 r - the radius of the circle in pixels, must be non-negative
 678
 679 =item *
 680
 681 d1, d2 - the range of angles to draw the arc over, in degrees.
 682
 683 =back
 684
 685 Returns non-zero on success.
 686
 687 Implementation:
 688
 689 =cut
 690 */
 691
 692 int
 693 i_arc_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
 694           double d1, double d2, const i_color *col) {
 695   i_img_dim x, y;
 696   i_img_dim dx, dy;
 697   int error;
 698   i_img_dim segs[2][2];
 699   int seg_count;
 700   i_img_dim sin_th;
 701   i_img_dim seg_d1, seg_d2;
 702   int seg_num;
 703   i_img_dim scale = r + 1;
 704   i_img_dim seg1 = scale * 2;
 705   i_img_dim seg2 = scale * 4;
 706   i_img_dim seg3 = scale * 6;
 707   i_img_dim seg4 = scale * 8;
 708   dIMCTXim(im);
 709
 710   im_log((aIMCTX,1,"i_arc_out(im %p,centre(" i_DFp "), rad %" i_DF ", d1 %f, d2 %f, col %p)",
 711           im, i_DFcp(xc, yc), i_DFc(r), d1, d2, col));
 712
 713   im_clear_error(aIMCTX);
 714
 715   if (r <= 0) {
 716     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
 717     return 0;
 718   }
 719   if (d1 + 360 <= d2)
 720     return i_circle_out(im, xc, yc, r, col);
 721
 722   if (d1 < 0)
 723     d1 += 360 * floor((-d1 + 359) / 360);
 724   if (d2 < 0)
 725     d2 += 360 * floor((-d2 + 359) / 360);
 726   d1 = fmod(d1, 360);
 727   d2 = fmod(d2, 360);
 728   seg_d1 = arc_seg(d1, scale);
 729   seg_d2 = arc_seg(d2, scale);
 730   if (seg_d2 < seg_d1) {
 731     /* split into two segments */
 732     segs[0][0] = 0;
 733     segs[0][1] = seg_d2;
 734     segs[1][0] = seg_d1;
 735     segs[1][1] = seg4;
 736     seg_count = 2;
 737   }
 738   else {
 739     segs[0][0] = seg_d1;
 740     segs[0][1] = seg_d2;
 741     seg_count = 1;
 742   }
 743
 744   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
 745     i_img_dim seg_start = segs[seg_num][0];
 746     i_img_dim seg_end = segs[seg_num][1];
 747     if (seg_start == 0)
 748       i_ppix(im, xc+r, yc, col);
 749     if (seg_start <= seg1 && seg_end >= seg1)
 750       i_ppix(im, xc, yc+r, col);
 751     if (seg_start <= seg2 && seg_end >= seg2)
 752       i_ppix(im, xc-r, yc, col);
 753     if (seg_start <= seg3 && seg_end >= seg3)
 754       i_ppix(im, xc, yc-r, col);
 755
 756     y = 0;
 757     x = r;
 758     dy = 1;
 759     dx = -2 * r;
 760     error = 1 - r;
 761     while (y < x) {
 762       if (error >= 0) {
 763         --x;
 764         dx += 2;
 765         error += dx;
 766       }
 767       ++y;
 768       dy += 2;
 769       error += dy;
 770
 771       sin_th = y;
 772       if (seg_start <= sin_th && seg_end >= sin_th)
 773         i_ppix(im, xc + x, yc + y, col);
 774       if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
 775         i_ppix(im, xc + y, yc + x, col);
 776
 777       if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
 778         i_ppix(im, xc - y, yc + x, col);
 779       if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
 780         i_ppix(im, xc - x, yc + y, col);
 781
 782       if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
 783         i_ppix(im, xc - x, yc - y, col);
 784       if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
 785         i_ppix(im, xc - y, yc - x, col);
 786
 787       if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
 788         i_ppix(im, xc + y, yc - x, col);
 789       if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
 790         i_ppix(im, xc + x, yc - y, col);
 791     }
 792   }
 793
 794   return 1;
 795 }
 796
 797 static double
 798 cover(i_img_dim r, i_img_dim j) {
 799   double rjsqrt = sqrt(r*r - j*j);
 800
 801   return ceil(rjsqrt) - rjsqrt;
 802 }
 803
 804 /*
 805 =item i_circle_out_aa(im, xc, yc, r, col)
 806
 807 =synopsis i_circle_out_aa(im, 50, 50, 45, &color);
 808
 809 Draw a circle outline centered at (x,y) with radius r, anti-aliased.
 810
 811 Parameters:
 812
 813 =over
 814
 815 =item *
 816
 817 (xc, yc) - the center of the circle
 818
 819 =item *
 820
 821 r - the radius of the circle in pixels, must be non-negative
 822
 823 =item *
 824
 825 col - an i_color for the color to draw in.
 826
 827 =back
 828
 829 Returns non-zero on success.
 830
 831 =cut
 832
 833 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
 834 Gems.
 835
 836 I use floating point for I<D> since for large circles the precision of
 837 a [0,255] value isn't sufficient when approaching the end of the
 838 octant.
 839
 840 */
 841
 842 int
 843 i_circle_out_aa(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r, const i_color *col) {
 844   i_img_dim i, j;
 845   double t;
 846   i_color workc = *col;
 847   int orig_alpha = col->channel[3];
 848   dIMCTXim(im);
 849
 850   im_log((aIMCTX,1,"i_circle_out_aa(im %p,centre(" i_DFp "), rad %" i_DF ", col %p)",
 851           im, i_DFcp(xc, yc), i_DFc(r), col));
 852
 853   im_clear_error(aIMCTX);
 854   if (r <= 0) {
 855     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
 856     return 0;
 857   }
 858   i = r;
 859   j = 0;
 860   t = 0;
 861   i_ppix_norm(im, xc+i, yc+j, col);
 862   i_ppix_norm(im, xc-i, yc+j, col);
 863   i_ppix_norm(im, xc+j, yc+i, col);
 864   i_ppix_norm(im, xc+j, yc-i, col);
 865
 866   while (i > j+1) {
 867     double d;
 868     int cv, inv_cv;
 869     j++;
 870     d = cover(r, j);
 871     cv = (int)(d * 255 + 0.5);
 872     inv_cv = 255-cv;
 873     if (d < t) {
 874       --i;
 875     }
 876     if (inv_cv) {
 877       workc.channel[3] = orig_alpha * inv_cv / 255;
 878       i_ppix_norm(im, xc+i, yc+j, &workc);
 879       i_ppix_norm(im, xc-i, yc+j, &workc);
 880       i_ppix_norm(im, xc+i, yc-j, &workc);
 881       i_ppix_norm(im, xc-i, yc-j, &workc);
 882
 883       if (i != j) {
 884         i_ppix_norm(im, xc+j, yc+i, &workc);
 885         i_ppix_norm(im, xc-j, yc+i, &workc);
 886         i_ppix_norm(im, xc+j, yc-i, &workc);
 887         i_ppix_norm(im, xc-j, yc-i, &workc);
 888       }
 889     }
 890     if (cv && i > j) {
 891       workc.channel[3] = orig_alpha * cv / 255;
 892       i_ppix_norm(im, xc+i-1, yc+j, &workc);
 893       i_ppix_norm(im, xc-i+1, yc+j, &workc);
 894       i_ppix_norm(im, xc+i-1, yc-j, &workc);
 895       i_ppix_norm(im, xc-i+1, yc-j, &workc);
 896
 897       if (j != i-1) {
 898         i_ppix_norm(im, xc+j, yc+i-1, &workc);
 899         i_ppix_norm(im, xc-j, yc+i-1, &workc);
 900         i_ppix_norm(im, xc+j, yc-i+1, &workc);
 901         i_ppix_norm(im, xc-j, yc-i+1, &workc);
 902       }
 903     }
 904     t = d;
 905   }
 906
 907   return 1;
 908 }
 909
 910 /*
 911 =item i_arc_out_aa(im, xc, yc, r, d1, d2, col)
 912
 913 =synopsis i_arc_out_aa(im, 50, 50, 45, 45, 125, &color);
 914
 915 Draw a circle arc outline centered at (x,y) with radius r, from angle
 916 d1 degrees through angle d2 degrees, anti-aliased.
 917
 918 Parameters:
 919
 920 =over
 921
 922 =item *
 923
 924 (xc, yc) - the center of the circle
 925
 926 =item *
 927
 928 r - the radius of the circle in pixels, must be non-negative
 929
 930 =item *
 931
 932 d1, d2 - the range of angle in degrees to draw the arc through.  If
 933 d2-d1 >= 360 a full circle is drawn.
 934
 935 =back
 936
 937 Returns non-zero on success.
 938
 939 =cut
 940
 941 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
 942 Gems.
 943
 944 */
 945
 946 int
 947 i_arc_out_aa(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r, double d1, double d2, const i_color *col) {
 948   i_img_dim i, j;
 949   double t;
 950   i_color workc = *col;
 951   i_img_dim segs[2][2];
 952   int seg_count;
 953   i_img_dim sin_th;
 954   i_img_dim seg_d1, seg_d2;
 955   int seg_num;
 956   int orig_alpha = col->channel[3];
 957   i_img_dim scale = r + 1;
 958   i_img_dim seg1 = scale * 2;
 959   i_img_dim seg2 = scale * 4;
 960   i_img_dim seg3 = scale * 6;
 961   i_img_dim seg4 = scale * 8;
 962   dIMCTXim(im);
 963
 964   im_log((aIMCTX,1,"i_arc_out_aa(im %p,centre(" i_DFp "), rad %" i_DF ", d1 %f, d2 %f, col %p)",
 965           im, i_DFcp(xc, yc), i_DFc(r), d1, d2, col));
 966
 967   im_clear_error(aIMCTX);
 968   if (r <= 0) {
 969     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
 970     return 0;
 971   }
 972   if (d1 + 360 <= d2)
 973     return i_circle_out_aa(im, xc, yc, r, col);
 974
 975   if (d1 < 0)
 976     d1 += 360 * floor((-d1 + 359) / 360);
 977   if (d2 < 0)
 978     d2 += 360 * floor((-d2 + 359) / 360);
 979   d1 = fmod(d1, 360);
 980   d2 = fmod(d2, 360);
 981   seg_d1 = arc_seg(d1, scale);
 982   seg_d2 = arc_seg(d2, scale);
 983   if (seg_d2 < seg_d1) {
 984     /* split into two segments */
 985     segs[0][0] = 0;
 986     segs[0][1] = seg_d2;
 987     segs[1][0] = seg_d1;
 988     segs[1][1] = seg4;
 989     seg_count = 2;
 990   }
 991   else {
 992     segs[0][0] = seg_d1;
 993     segs[0][1] = seg_d2;
 994     seg_count = 1;
 995   }
 996
 997   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
 998     i_img_dim seg_start = segs[seg_num][0];
 999     i_img_dim seg_end = segs[seg_num][1];
1000
1001     i = r;
1002     j = 0;
1003     t = 0;
1004
1005     if (seg_start == 0)
1006       i_ppix_norm(im, xc+i, yc+j, col);
1007     if (seg_start <= seg1 && seg_end >= seg1)
1008       i_ppix_norm(im, xc+j, yc+i, col);
1009     if (seg_start <= seg2 && seg_end >= seg2)
1010       i_ppix_norm(im, xc-i, yc+j, col);
1011     if (seg_start <= seg3 && seg_end >= seg3)
1012       i_ppix_norm(im, xc+j, yc-i, col);
1013
1014     while (i > j+1) {
1015       int cv, inv_cv;
1016       double d;
1017       j++;
1018       d = cover(r, j);
1019       cv = (int)(d * 255 + 0.5);
1020       inv_cv = 255-cv;
1021       if (d < t) {
1022         --i;
1023       }
1024       sin_th = j;
1025       if (inv_cv) {
1026         workc.channel[3] = orig_alpha * inv_cv / 255;
1027
1028         if (seg_start <= sin_th && seg_end >= sin_th)
1029           i_ppix_norm(im, xc+i, yc+j, &workc);
1030         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1031           i_ppix_norm(im, xc-i, yc+j, &workc);
1032         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1033           i_ppix_norm(im, xc+i, yc-j, &workc);
1034         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1035           i_ppix_norm(im, xc-i, yc-j, &workc);
1036
1037         if (i != j) {
1038           if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1039             i_ppix_norm(im, xc+j, yc+i, &workc);
1040           if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1041             i_ppix_norm(im, xc-j, yc+i, &workc);
1042           if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1043             i_ppix_norm(im, xc+j, yc-i, &workc);
1044           if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1045             i_ppix_norm(im, xc-j, yc-i, &workc);
1046         }
1047       }
1048       if (cv && i > j) {
1049         workc.channel[3] = orig_alpha * cv / 255;
1050         if (seg_start <= sin_th && seg_end >= sin_th)
1051           i_ppix_norm(im, xc+i-1, yc+j, &workc);
1052         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1053           i_ppix_norm(im, xc-i+1, yc+j, &workc);
1054         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1055           i_ppix_norm(im, xc+i-1, yc-j, &workc);
1056         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1057           i_ppix_norm(im, xc-i+1, yc-j, &workc);
1058
1059         if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1060           i_ppix_norm(im, xc+j, yc+i-1, &workc);
1061         if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1062           i_ppix_norm(im, xc-j, yc+i-1, &workc);
1063         if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1064           i_ppix_norm(im, xc+j, yc-i+1, &workc);
1065         if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1066           i_ppix_norm(im, xc-j, yc-i+1, &workc);
1067       }
1068       t = d;
1069     }
1070   }
1071
1072   return 1;
1073 }
1074
1075 /*
1076 =item i_box(im, x1, y1, x2, y2, color)
1077
1078 =category Drawing
1079 =synopsis i_box(im, 0, 0, im->xsize-1, im->ysize-1, &color).
1080
1081 Outlines the box from (x1,y1) to (x2,y2) inclusive with I<color>.
1082
1083 =cut
1084 */
1085
1086 void
1087 i_box(i_img *im,i_img_dim x1,i_img_dim y1,i_img_dim x2,i_img_dim y2,const i_color *val) {
1088   i_img_dim x,y;
1089   dIMCTXim(im);
1090
1091   im_log((aIMCTX, 1,"i_box(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1092           im, i_DFcp(x1,y1), i_DFcp(x2,y2), val));
1093   for(x=x1;x<x2+1;x++) {
1094     i_ppix(im,x,y1,val);
1095     i_ppix(im,x,y2,val);
1096   }
1097   for(y=y1;y<y2+1;y++) {
1098     i_ppix(im,x1,y,val);
1099     i_ppix(im,x2,y,val);
1100   }
1101 }
1102
1103 /*
1104 =item i_box_filled(im, x1, y1, x2, y2, color)
1105
1106 =category Drawing
1107 =synopsis i_box_filled(im, 0, 0, im->xsize-1, im->ysize-1, &color);
1108
1109 Fills the box from (x1,y1) to (x2,y2) inclusive with color.
1110
1111 =cut
1112 */
1113
1114 void
1115 i_box_filled(i_img *im,i_img_dim x1,i_img_dim y1,i_img_dim x2,i_img_dim y2, const i_color *val) {
1116   i_img_dim x, y, width;
1117   i_palidx index;
1118   dIMCTXim(im);
1119
1120   im_log((aIMCTX,1,"i_box_filled(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1121           im, i_DFcp(x1, y1), i_DFcp(x2,y2) ,val));
1122
1123   if (x1 > x2 || y1 > y2
1124       || x2 < 0 || y2 < 0
1125       || x1 >= im->xsize || y1 > im->ysize)
1126     return;
1127
1128   if (x1 < 0)
1129     x1 = 0;
1130   if (x2 >= im->xsize)
1131     x2 = im->xsize - 1;
1132   if (y1 < 0)
1133     y1 = 0;
1134   if (y2 >= im->ysize)
1135     y2 = im->ysize - 1;
1136
1137   width = x2 - x1 + 1;
1138
1139   if (im->type == i_palette_type
1140       && i_findcolor(im, val, &index)) {
1141     i_palidx *line = mymalloc(sizeof(i_palidx) * width);
1142
1143     for (x = 0; x < width; ++x)
1144       line[x] = index;
1145
1146     for (y = y1; y <= y2; ++y)
1147       i_ppal(im, x1, x2+1, y, line);
1148
1149     myfree(line);
1150   }
1151   else {
1152     i_color *line = mymalloc(sizeof(i_color) * width);
1153
1154     for (x = 0; x < width; ++x)
1155       line[x] = *val;
1156
1157     for (y = y1; y <= y2; ++y)
1158       i_plin(im, x1, x2+1, y, line);
1159
1160     myfree(line);
1161   }
1162 }
1163
1164 /*
1165 =item i_box_filledf(im, x1, y1, x2, y2, color)
1166
1167 =category Drawing
1168 =synopsis i_box_filledf(im, 0, 0, im->xsize-1, im->ysize-1, &fcolor);
1169
1170 Fills the box from (x1,y1) to (x2,y2) inclusive with a floating point
1171 color.
1172
1173 =cut
1174 */
1175
1176 int
1177 i_box_filledf(i_img *im,i_img_dim x1,i_img_dim y1,i_img_dim x2,i_img_dim y2, const i_fcolor *val) {
1178   i_img_dim x, y, width;
1179   dIMCTXim(im);
1180
1181   im_log((aIMCTX, 1,"i_box_filledf(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1182           im, i_DFcp(x1, y1), i_DFcp(x2, y2), val));
1183
1184   if (x1 > x2 || y1 > y2
1185       || x2 < 0 || y2 < 0
1186       || x1 >= im->xsize || y1 > im->ysize)
1187     return 0;
1188
1189   if (x1 < 0)
1190     x1 = 0;
1191   if (x2 >= im->xsize)
1192     x2 = im->xsize - 1;
1193   if (y1 < 0)
1194     y1 = 0;
1195   if (y2 >= im->ysize)
1196     y2 = im->ysize - 1;
1197
1198   width = x2 - x1 + 1;
1199
1200   if (im->bits <= 8) {
1201     i_color c;
1202     c.rgba.r = SampleFTo8(val->rgba.r);
1203     c.rgba.g = SampleFTo8(val->rgba.g);
1204     c.rgba.b = SampleFTo8(val->rgba.b);
1205     c.rgba.a = SampleFTo8(val->rgba.a);
1206
1207     i_box_filled(im, x1, y1, x2, y2, &c);
1208   }
1209   else {
1210     i_fcolor *line = mymalloc(sizeof(i_fcolor) * width);
1211
1212     for (x = 0; x < width; ++x)
1213       line[x] = *val;
1214
1215     for (y = y1; y <= y2; ++y)
1216       i_plinf(im, x1, x2+1, y, line);
1217
1218     myfree(line);
1219   }
1220
1221   return 1;
1222 }
1223
1224 /*
1225 =item i_box_cfill(im, x1, y1, x2, y2, fill)
1226
1227 =category Drawing
1228 =synopsis i_box_cfill(im, 0, 0, im->xsize-1, im->ysize-1, fill);
1229
1230 Fills the box from (x1,y1) to (x2,y2) inclusive with fill.
1231
1232 =cut
1233 */
1234
1235 void
1236 i_box_cfill(i_img *im,i_img_dim x1,i_img_dim y1,i_img_dim x2,i_img_dim y2,i_fill_t *fill) {
1237   i_render r;
1238   dIMCTXim(im);
1239
1240   im_log((aIMCTX,1,"i_box_cfill(im* %p, p1(" i_DFp "), p2(" i_DFp "), fill %p)\n",
1241           im, i_DFcp(x1, y1), i_DFcp(x2,y2), fill));
1242
1243   ++x2;
1244   if (x1 < 0)
1245     x1 = 0;
1246   if (y1 < 0)
1247     y1 = 0;
1248   if (x2 > im->xsize)
1249     x2 = im->xsize;
1250   if (y2 >= im->ysize)
1251     y2 = im->ysize-1;
1252   if (x1 >= x2 || y1 > y2)
1253     return;
1254
1255   i_render_init(&r, im, x2-x1);
1256   while (y1 <= y2) {
1257     i_render_fill(&r, x1, y1, x2-x1, NULL, fill);
1258     ++y1;
1259   }
1260   i_render_done(&r);
1261 }
1262
1263 /*
1264 =item i_line(C<im>, C<x1>, C<y1>, C<x2>, C<y2>, C<color>, C<endp>)
1265
1266 =category Drawing
1267
1268 =for stopwords Bresenham's
1269
1270 Draw a line to image using Bresenham's line drawing algorithm
1271
1272    im    - image to draw to
1273    x1    - starting x coordinate
1274    y1    - starting x coordinate
1275    x2    - starting x coordinate
1276    y2    - starting x coordinate
1277    color - color to write to image
1278    endp  - endpoint flag (boolean)
1279
1280 =cut
1281 */
1282
1283 void
1284 i_line(i_img *im, i_img_dim x1, i_img_dim y1, i_img_dim x2, i_img_dim y2, const i_color *val, int endp) {
1285   i_img_dim x, y;
1286   i_img_dim dx, dy;
1287   i_img_dim p;
1288
1289   dx = x2 - x1;
1290   dy = y2 - y1;
1291
1292
1293   /* choose variable to iterate on */
1294   if (i_abs(dx) > i_abs(dy)) {
1295     i_img_dim dx2, dy2, cpy;
1296
1297     /* sort by x */
1298     if (x1 > x2) {
1299       i_img_dim t;
1300       t = x1; x1 = x2; x2 = t;
1301       t = y1; y1 = y2; y2 = t;
1302     }
1303
1304     dx = i_abs(dx);
1305     dx2 = dx*2;
1306     dy = y2 - y1;
1307
1308     if (dy<0) {
1309       dy = -dy;
1310       cpy = -1;
1311     } else {
1312       cpy = 1;
1313     }
1314     dy2 = dy*2;
1315     p = dy2 - dx;
1316
1317
1318     y = y1;
1319     for(x=x1; x<x2-1; x++) {
1320       if (p<0) {
1321         p += dy2;
1322       } else {
1323         y += cpy;
1324         p += dy2-dx2;
1325       }
1326       i_ppix(im, x+1, y, val);
1327     }
1328   } else {
1329     i_img_dim dy2, dx2, cpx;
1330
1331     /* sort bx y */
1332     if (y1 > y2) {
1333       i_img_dim t;
1334       t = x1; x1 = x2; x2 = t;
1335       t = y1; y1 = y2; y2 = t;
1336     }
1337
1338     dy = i_abs(dy);
1339     dx = x2 - x1;
1340     dy2 = dy*2;
1341
1342     if (dx<0) {
1343       dx = -dx;
1344       cpx = -1;
1345     } else {
1346       cpx = 1;
1347     }
1348     dx2 = dx*2;
1349     p = dx2 - dy;
1350
1351     x = x1;
1352
1353     for(y=y1; y<y2-1; y++) {
1354       if (p<0) {
1355         p  += dx2;
1356       } else {
1357         x += cpx;
1358         p += dx2-dy2;
1359       }
1360       i_ppix(im, x, y+1, val);
1361     }
1362   }
1363   if (endp) {
1364     i_ppix(im, x1, y1, val);
1365     i_ppix(im, x2, y2, val);
1366   } else {
1367     if (x1 != x2 || y1 != y2)
1368       i_ppix(im, x1, y1, val);
1369   }
1370 }
1371
1372
1373 void
1374 i_line_dda(i_img *im, i_img_dim x1, i_img_dim y1, i_img_dim x2, i_img_dim y2, i_color *val) {
1375
1376   double dy;
1377   i_img_dim x;
1378
1379   for(x=x1; x<=x2; x++) {
1380     dy = y1+ (x-x1)/(double)(x2-x1)*(y2-y1);
1381     i_ppix(im, x, (i_img_dim)(dy+0.5), val);
1382   }
1383 }
1384
1385 /*
1386 =item i_line_aa(C<im>, C<x1>, C<x2>, C<y1>, C<y2>, C<color>, C<endp>)
1387
1388 =category Drawing
1389
1390 Anti-alias draws a line from (x1,y1) to (x2, y2) in color.
1391
1392 The point (x2, y2) is drawn only if C<endp> is set.
1393
1394 =cut
1395 */
1396
1397 void
1398 i_line_aa(i_img *im, i_img_dim x1, i_img_dim y1, i_img_dim x2, i_img_dim y2, const i_color *val, int endp) {
1399   i_img_dim x, y;
1400   i_img_dim dx, dy;
1401   i_img_dim p;
1402
1403   dx = x2 - x1;
1404   dy = y2 - y1;
1405
1406   /* choose variable to iterate on */
1407   if (i_abs(dx) > i_abs(dy)) {
1408     i_img_dim dx2, dy2, cpy;
1409
1410     /* sort by x */
1411     if (x1 > x2) {
1412       i_img_dim t;
1413       t = x1; x1 = x2; x2 = t;
1414       t = y1; y1 = y2; y2 = t;
1415     }
1416
1417     dx = i_abs(dx);
1418     dx2 = dx*2;
1419     dy = y2 - y1;
1420
1421     if (dy<0) {
1422       dy = -dy;
1423       cpy = -1;
1424     } else {
1425       cpy = 1;
1426     }
1427     dy2 = dy*2;
1428     p = dy2 - dx2; /* this has to be like this for AA */
1429
1430     y = y1;
1431
1432     for(x=x1; x<x2-1; x++) {
1433       int ch;
1434       i_color tval;
1435       double t = (dy) ? -(float)(p)/(float)(dx2) : 1;
1436       double t1, t2;
1437
1438       if (t<0) t = 0;
1439       t1 = 1-t;
1440       t2 = t;
1441
1442       i_gpix(im,x+1,y,&tval);
1443       for(ch=0;ch<im->channels;ch++)
1444         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
1445       i_ppix(im,x+1,y,&tval);
1446
1447       i_gpix(im,x+1,y+cpy,&tval);
1448       for(ch=0;ch<im->channels;ch++)
1449         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
1450       i_ppix(im,x+1,y+cpy,&tval);
1451
1452       if (p<0) {
1453         p += dy2;
1454       } else {
1455         y += cpy;
1456         p += dy2-dx2;
1457       }
1458     }
1459   } else {
1460     i_img_dim dy2, dx2, cpx;
1461
1462     /* sort bx y */
1463     if (y1 > y2) {
1464       i_img_dim t;
1465       t = x1; x1 = x2; x2 = t;
1466       t = y1; y1 = y2; y2 = t;
1467     }
1468
1469     dy = i_abs(dy);
1470     dx = x2 - x1;
1471     dy2 = dy*2;
1472
1473     if (dx<0) {
1474       dx = -dx;
1475       cpx = -1;
1476     } else {
1477       cpx = 1;
1478     }
1479     dx2 = dx*2;
1480     p = dx2 - dy2; /* this has to be like this for AA */
1481
1482     x = x1;
1483
1484     for(y=y1; y<y2-1; y++) {
1485       int ch;
1486       i_color tval;
1487       double t = (dx) ? -(double)(p)/(double)(dy2) : 1;
1488       double t1, t2;
1489
1490       if (t<0) t = 0;
1491       t1 = 1-t;
1492       t2 = t;
1493
1494       i_gpix(im,x,y+1,&tval);
1495       for(ch=0;ch<im->channels;ch++)
1496         tval.channel[ch]=(unsigned char)(t1*(double)tval.channel[ch]+t2*(double)val->channel[ch]);
1497       i_ppix(im,x,y+1,&tval);
1498
1499       i_gpix(im,x+cpx,y+1,&tval);
1500       for(ch=0;ch<im->channels;ch++)
1501         tval.channel[ch]=(unsigned char)(t2*(double)tval.channel[ch]+t1*(double)val->channel[ch]);
1502       i_ppix(im,x+cpx,y+1,&tval);
1503
1504       if (p<0) {
1505         p  += dx2;
1506       } else {
1507         x += cpx;
1508         p += dx2-dy2;
1509       }
1510     }
1511   }
1512
1513
1514   if (endp) {
1515     i_ppix(im, x1, y1, val);
1516     i_ppix(im, x2, y2, val);
1517   } else {
1518     if (x1 != x2 || y1 != y2)
1519       i_ppix(im, x1, y1, val);
1520   }
1521 }
1522
1523
1524
1525 static double
1526 perm(i_img_dim n,i_img_dim k) {
1527   double r;
1528   i_img_dim i;
1529   r=1;
1530   for(i=k+1;i<=n;i++) r*=i;
1531   for(i=1;i<=(n-k);i++) r/=i;
1532   return r;
1533 }
1534
1535
1536 /* Note in calculating t^k*(1-t)^(n-k)
1537    we can start by using t^0=1 so this simplifies to
1538    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
1539    to get a new level - this may lead to errors who knows lets test it */
1540
1541 void
1542 i_bezier_multi(i_img *im,int l,const double *x,const double *y, const i_color *val) {
1543   double *bzcoef;
1544   double t,cx,cy;
1545   int k,i;
1546   i_img_dim lx = 0,ly = 0;
1547   int n=l-1;
1548   double itr,ccoef;
1549
1550   /* this is the same size as the x and y arrays, so shouldn't overflow */
1551   bzcoef=mymalloc(sizeof(double)*l); /* checked 5jul05 tonyc */
1552   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
1553   ICL_info(val);
1554
1555
1556   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
1557   i=0;
1558   for(t=0;t<=1;t+=0.005) {
1559     cx=cy=0;
1560     itr=t/(1-t);
1561     ccoef=pow(1-t,n);
1562     for(k=0;k<l;k++) {
1563       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
1564               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
1565
1566       cx+=bzcoef[k]*x[k]*ccoef;
1567       cy+=bzcoef[k]*y[k]*ccoef;
1568       ccoef*=itr;
1569     }
1570     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
1571     if (i++) {
1572       i_line_aa(im,lx,ly,(i_img_dim)(0.5+cx),(i_img_dim)(0.5+cy),val, 1);
1573     }
1574       /*     i_ppix(im,(i_img_dim)(0.5+cx),(i_img_dim)(0.5+cy),val); */
1575     lx=(i_img_dim)(0.5+cx);
1576     ly=(i_img_dim)(0.5+cy);
1577   }
1578   ICL_info(val);
1579   myfree(bzcoef);
1580 }
1581
1582 /* Flood fill
1583
1584    REF: Graphics Gems I. page 282+
1585
1586 */
1587
1588 /* This should be moved into a seperate file? */
1589
1590 /* This is the truncation used:
1591
1592    a double is multiplied by 16 and then truncated.
1593    This means that 0 -> 0
1594    So a triangle of (0,0) (10,10) (10,0) Will look like it's
1595    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
1596
1597 */
1598
1599
1600 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
1601    graphics gems I */
1602
1603 /*
1604 struct stc {
1605   i_img_dim mylx,myrx;
1606   i_img_dim dadlx,dadrx;
1607   i_img_dim myy;
1608   int mydirection;
1609 };
1610
1611 Not used code???
1612 */
1613
1614
1615 struct stack_element {
1616   i_img_dim myLx,myRx;
1617   i_img_dim dadLx,dadRx;
1618   i_img_dim myY;
1619   int myDirection;
1620 };
1621
1622
1623 /* create the link data to put push onto the stack */
1624
1625 static
1626 struct stack_element*
1627 crdata(i_img_dim left,i_img_dim right,i_img_dim dadl,i_img_dim dadr,i_img_dim y, int dir) {
1628   struct stack_element *ste;
1629   ste              = mymalloc(sizeof(struct stack_element)); /* checked 5jul05 tonyc */
1630   ste->myLx        = left;
1631   ste->myRx        = right;
1632   ste->dadLx       = dadl;
1633   ste->dadRx       = dadr;
1634   ste->myY         = y;
1635   ste->myDirection = dir;
1636   return ste;
1637 }
1638
1639 /* i_ccomp compares two colors and gives true if they are the same */
1640
1641 typedef int (*ff_cmpfunc)(i_color const *c1, i_color const *c2, int channels);
1642
1643 static int
1644 i_ccomp_normal(i_color const *val1, i_color const *val2, int ch) {
1645   int i;
1646   for(i = 0; i < ch; i++)
1647     if (val1->channel[i] !=val2->channel[i])
1648       return 0;
1649   return 1;
1650 }
1651
1652 static int
1653 i_ccomp_border(i_color const *val1, i_color const *val2, int ch) {
1654   int i;
1655   for(i = 0; i < ch; i++)
1656     if (val1->channel[i] !=val2->channel[i])
1657       return 1;
1658   return 0;
1659 }
1660
1661 static int
1662 i_lspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1663   i_color cval;
1664   while(1) {
1665     if (seedx-1 < 0) break;
1666     i_gpix(im,seedx-1,seedy,&cval);
1667     if (!cmpfunc(val,&cval,im->channels))
1668       break;
1669     seedx--;
1670   }
1671   return seedx;
1672 }
1673
1674 static int
1675 i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1676   i_color cval;
1677   while(1) {
1678     if (seedx+1 > im->xsize-1) break;
1679     i_gpix(im,seedx+1,seedy,&cval);
1680     if (!cmpfunc(val,&cval,im->channels)) break;
1681     seedx++;
1682   }
1683   return seedx;
1684 }
1685
1686 /* Macro to create a link and push on to the list */
1687
1688 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
1689   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
1690   llist_push(st,&s);                                             \
1691 } while (0)
1692
1693 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
1694 /* No overflow check! */
1695
1696 #define ST_POP() do {         \
1697   struct stack_element *s;    \
1698   llist_pop(st,&s);           \
1699   lx        = s->myLx;        \
1700   rx        = s->myRx;        \
1701   dadLx     = s->dadLx;       \
1702   dadRx     = s->dadRx;       \
1703   y         = s->myY;         \
1704   direction = s->myDirection; \
1705   myfree(s);                  \
1706 } while (0)
1707
1708 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
1709   i_img_dim pushrx = rx+1;                                              \
1710   i_img_dim pushlx = lx-1;                                              \
1711   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
1712   if (rx > dadRx)                                                 \
1713     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
1714   if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
1715 } while (0)
1716
1717 #define SET(x,y) btm_set(btm,x,y)
1718
1719 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
1720 #define INSIDE(x,y, seed) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
1721
1722
1723
1724 /* The function that does all the real work */
1725
1726 static struct i_bitmap *
1727 i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
1728                  i_img_dim *bxminp, i_img_dim *bxmaxp, i_img_dim *byminp, i_img_dim *bymaxp,
1729                  i_color const *seed, ff_cmpfunc cmpfunc) {
1730   i_img_dim ltx, rtx;
1731   i_img_dim tx = 0;
1732
1733   i_img_dim bxmin = seedx;
1734   i_img_dim bxmax = seedx;
1735   i_img_dim bymin = seedy;
1736   i_img_dim bymax = seedy;
1737
1738   struct llist *st;
1739   struct i_bitmap *btm;
1740
1741   int channels;
1742   i_img_dim xsize,ysize;
1743   i_color cval;
1744
1745   channels = im->channels;
1746   xsize    = im->xsize;
1747   ysize    = im->ysize;
1748
1749   btm = btm_new(xsize, ysize);
1750   st  = llist_new(100, sizeof(struct stack_element*));
1751
1752   /* Find the starting span and fill it */
1753   ltx = i_lspan(im, seedx, seedy, seed, cmpfunc);
1754   rtx = i_rspan(im, seedx, seedy, seed, cmpfunc);
1755   for(tx=ltx; tx<=rtx; tx++) SET(tx, seedy);
1756   bxmin = ltx;
1757   bxmax = rtx;
1758
1759   ST_PUSH(ltx, rtx, ltx, rtx, seedy+1,  1);
1760   ST_PUSH(ltx, rtx, ltx, rtx, seedy-1, -1);
1761
1762   while(st->count) {
1763     /* Stack variables */
1764     i_img_dim lx,rx;
1765     i_img_dim dadLx,dadRx;
1766     i_img_dim y;
1767     int direction;
1768
1769     i_img_dim x;
1770     int wasIn=0;
1771
1772     ST_POP(); /* sets lx, rx, dadLx, dadRx, y, direction */
1773
1774
1775     if (y<0 || y>ysize-1) continue;
1776     if (bymin > y) bymin=y; /* in the worst case an extra line */
1777     if (bymax < y) bymax=y;
1778
1779
1780     x = lx+1;
1781     if ( lx >= 0 && (wasIn = INSIDE(lx, y, seed)) ) {
1782       SET(lx, y);
1783       lx--;
1784       while(lx >= 0 && INSIDE(lx, y, seed)) {
1785         SET(lx,y);
1786         lx--;
1787       }
1788     }
1789
1790     if (bxmin > lx) bxmin = lx;
1791     while(x <= xsize-1) {
1792       /*  printf("x=%d\n",x); */
1793       if (wasIn) {
1794
1795         if (INSIDE(x, y, seed)) {
1796           /* case 1: was inside, am still inside */
1797           SET(x,y);
1798         } else {
1799           /* case 2: was inside, am no longer inside: just found the
1800              right edge of a span */
1801           ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1802
1803           if (bxmax < x) bxmax = x;
1804           wasIn=0;
1805         }
1806       } else {
1807         if (x > rx) goto EXT;
1808         if (INSIDE(x, y, seed)) {
1809           SET(x, y);
1810           /* case 3: Wasn't inside, am now: just found the start of a new run */
1811           wasIn = 1;
1812             lx = x;
1813         } else {
1814           /* case 4: Wasn't inside, still isn't */
1815         }
1816       }
1817       x++;
1818     }
1819   EXT: /* out of loop */
1820     if (wasIn) {
1821       /* hit an edge of the frame buffer while inside a run */
1822       ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1823       if (bxmax < x) bxmax = x;
1824     }
1825   }
1826
1827   llist_destroy(st);
1828
1829   *bxminp = bxmin;
1830   *bxmaxp = bxmax;
1831   *byminp = bymin;
1832   *bymaxp = bymax;
1833
1834   return btm;
1835 }
1836
1837 /*
1838 =item i_flood_fill(C<im>, C<seedx>, C<seedy>, C<color>)
1839
1840 =category Drawing
1841 =synopsis i_flood_fill(im, 50, 50, &color);
1842
1843 Flood fills the 4-connected region starting from the point (C<seedx>,
1844 C<seedy>) with I<color>.
1845
1846 Returns false if (C<seedx>, C<seedy>) are outside the image.
1847
1848 =cut
1849 */
1850
1851 undef_int
1852 i_flood_fill(i_img *im, i_img_dim seedx, i_img_dim seedy, const i_color *dcol) {
1853   i_img_dim bxmin, bxmax, bymin, bymax;
1854   struct i_bitmap *btm;
1855   i_img_dim x, y;
1856   i_color val;
1857   dIMCTXim(im);
1858
1859   im_log((aIMCTX, 1, "i_flood_fill(im %p, seed(" i_DFp "), col %p)",
1860           im, i_DFcp(seedx, seedy), dcol));
1861
1862   im_clear_error(aIMCTX);
1863   if (seedx < 0 || seedx >= im->xsize ||
1864       seedy < 0 || seedy >= im->ysize) {
1865     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
1866     return 0;
1867   }
1868
1869   /* Get the reference color */
1870   i_gpix(im, seedx, seedy, &val);
1871
1872   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1873                          &val, i_ccomp_normal);
1874
1875   for(y=bymin;y<=bymax;y++)
1876     for(x=bxmin;x<=bxmax;x++)
1877       if (btm_test(btm,x,y))
1878         i_ppix(im,x,y,dcol);
1879   btm_destroy(btm);
1880   return 1;
1881 }
1882
1883 /*
1884 =item i_flood_cfill(C<im>, C<seedx>, C<seedy>, C<fill>)
1885
1886 =category Drawing
1887 =synopsis i_flood_cfill(im, 50, 50, fill);
1888
1889 Flood fills the 4-connected region starting from the point (C<seedx>,
1890 C<seedy>) with C<fill>.
1891
1892 Returns false if (C<seedx>, C<seedy>) are outside the image.
1893
1894 =cut
1895 */
1896
1897 undef_int
1898 i_flood_cfill(i_img *im, i_img_dim seedx, i_img_dim seedy, i_fill_t *fill) {
1899   i_img_dim bxmin, bxmax, bymin, bymax;
1900   struct i_bitmap *btm;
1901   i_color val;
1902   dIMCTXim(im);
1903
1904   im_log((aIMCTX, 1, "i_flood_cfill(im %p, seed(" i_DFp "), fill %p)",
1905           im, i_DFcp(seedx, seedy), fill));
1906
1907   im_clear_error(aIMCTX);
1908
1909   if (seedx < 0 || seedx >= im->xsize ||
1910       seedy < 0 || seedy >= im->ysize) {
1911     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
1912     return 0;
1913   }
1914
1915   /* Get the reference color */
1916   i_gpix(im, seedx, seedy, &val);
1917
1918   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1919                          &val, i_ccomp_normal);
1920
1921   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
1922
1923   btm_destroy(btm);
1924   return 1;
1925 }
1926
1927 /*
1928 =item i_flood_fill_border(C<im>, C<seedx>, C<seedy>, C<color>, C<border>)
1929
1930 =category Drawing
1931 =synopsis i_flood_fill_border(im, 50, 50, &color, &border);
1932
1933 Flood fills the 4-connected region starting from the point (C<seedx>,
1934 C<seedy>) with C<color>, fill stops when the fill reaches a pixels
1935 with color C<border>.
1936
1937 Returns false if (C<seedx>, C<seedy>) are outside the image.
1938
1939 =cut
1940 */
1941
1942 undef_int
1943 i_flood_fill_border(i_img *im, i_img_dim seedx, i_img_dim seedy, const i_color *dcol,
1944                     const i_color *border) {
1945   i_img_dim bxmin, bxmax, bymin, bymax;
1946   struct i_bitmap *btm;
1947   i_img_dim x, y;
1948   dIMCTXim(im);
1949
1950   im_log((aIMCTX, 1, "i_flood_cfill(im %p, seed(" i_DFp "), dcol %p, border %p)",
1951           im, i_DFcp(seedx, seedy), dcol, border));
1952
1953   im_clear_error(aIMCTX);
1954   if (seedx < 0 || seedx >= im->xsize ||
1955       seedy < 0 || seedy >= im->ysize) {
1956     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
1957     return 0;
1958   }
1959
1960   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1961                          border, i_ccomp_border);
1962
1963   for(y=bymin;y<=bymax;y++)
1964     for(x=bxmin;x<=bxmax;x++)
1965       if (btm_test(btm,x,y))
1966         i_ppix(im,x,y,dcol);
1967   btm_destroy(btm);
1968   return 1;
1969 }
1970
1971 /*
1972 =item i_flood_cfill_border(C<im>, C<seedx>, C<seedy>, C<fill>, C<border>)
1973
1974 =category Drawing
1975 =synopsis i_flood_cfill_border(im, 50, 50, fill, border);
1976
1977 Flood fills the 4-connected region starting from the point (C<seedx>,
1978 C<seedy>) with C<fill>, the fill stops when it reaches pixels of color
1979 C<border>.
1980
1981 Returns false if (C<seedx>, C<seedy>) are outside the image.
1982
1983 =cut
1984 */
1985
1986 undef_int
1987 i_flood_cfill_border(i_img *im, i_img_dim seedx, i_img_dim seedy, i_fill_t *fill,
1988                      const i_color *border) {
1989   i_img_dim bxmin, bxmax, bymin, bymax;
1990   struct i_bitmap *btm;
1991   dIMCTXim(im);
1992
1993   im_log((aIMCTX, 1, "i_flood_cfill_border(im %p, seed(" i_DFp "), fill %p, border %p)",
1994           im, i_DFcp(seedx, seedy), fill, border));
1995
1996   im_clear_error(aIMCTX);
1997
1998   if (seedx < 0 || seedx >= im->xsize ||
1999       seedy < 0 || seedy >= im->ysize) {
2000     im_push_error(aIMCTX, 0, "i_flood_cfill_border: Seed pixel outside of image");
2001     return 0;
2002   }
2003
2004   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2005                          border, i_ccomp_border);
2006
2007   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
2008
2009   btm_destroy(btm);
2010
2011   return 1;
2012 }
2013
2014 static void
2015 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm,
2016                i_img_dim bxmin, i_img_dim bxmax, i_img_dim bymin, i_img_dim bymax) {
2017   i_img_dim x, y;
2018   i_img_dim start;
2019
2020   i_render r;
2021
2022   i_render_init(&r, im, bxmax - bxmin + 1);
2023
2024   for(y=bymin; y<=bymax; y++) {
2025     x = bxmin;
2026     while (x <= bxmax) {
2027       while (x <= bxmax && !btm_test(btm, x, y)) {
2028         ++x;
2029       }
2030       if (btm_test(btm, x, y)) {
2031         start = x;
2032         while (x <= bxmax && btm_test(btm, x, y)) {
2033           ++x;
2034         }
2035         i_render_fill(&r, start, y, x-start, NULL, fill);
2036       }
2037     }
2038   }
2039   i_render_done(&r);
2040 }
2041
2042 /*
2043 =back
2044
2045 =cut
2046 */