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