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