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