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 typedef void
 428 (*flush_render_t)(i_img *im, i_img_dim l, i_img_dim r, i_img_dim y, const i_sample_t *cover, void *ctx);
 429
 430 static void
 431 i_circle_aa_low(i_img *im, double x, double y, double rad, flush_render_t r, void *ctx);
 432
 433 static void
 434 scanline_flush_color(i_img *im, i_img_dim l, i_img_dim y, i_img_dim width, const i_sample_t *cover, void *ctx);
 435
 436 static void
 437 scanline_flush_fill(i_img *im, i_img_dim l, i_img_dim y, i_img_dim width, const i_sample_t *cover, void *ctx);
 438
 439 typedef struct {
 440   i_render r;
 441   i_color c;
 442 } flush_color_t;
 443
 444 typedef struct {
 445   i_render r;
 446   i_fill_t *fill;
 447 } flush_fill_t;
 448
 449 /*
 450 =item i_circle_aa(im, x, y, rad, color)
 451
 452 =category Drawing
 453 =synopsis i_circle_aa(im, 50, 50, 45, &color);
 454
 455 Anti-alias fills a circle centered at (x,y) for radius I<rad> with
 456 color.
 457
 458 =cut
 459 */
 460
 461 void
 462 i_circle_aa(i_img *im, double x, double y, double rad, const i_color *val) {
 463   flush_color_t fc;
 464
 465   fc.c = *val;
 466   i_render_init(&fc.r, im, rad * 2 + 1);
 467
 468   i_circle_aa_low(im, x, y, rad, scanline_flush_color, &fc);
 469
 470   i_render_done(&fc.r);
 471 }
 472
 473 /*
 474 =item i_circle_aa_fill(im, x, y, rad, fill)
 475
 476 =category Drawing
 477 =synopsis i_circle_aa_fill(im, 50, 50, 45, fill);
 478
 479 Anti-alias fills a circle centered at (x,y) for radius I<rad> with
 480 fill.
 481
 482 =cut
 483 */
 484
 485 void
 486 i_circle_aa_fill(i_img *im, double x, double y, double rad, i_fill_t *fill) {
 487   flush_fill_t ff;
 488
 489   ff.fill = fill;
 490   i_render_init(&ff.r, im, rad * 2 + 1);
 491
 492   i_circle_aa_low(im, x, y, rad, scanline_flush_fill, &ff);
 493
 494   i_render_done(&ff.r);
 495 }
 496
 497 static void
 498 i_circle_aa_low(i_img *im, double x, double y, double rad, flush_render_t r,
 499                 void *ctx) {
 500   i_color temp;
 501   i_img_dim ly;
 502   dIMCTXim(im);
 503   double ceil_rad = ceil(rad);
 504   i_img_dim first_row = floor(y) - ceil_rad;
 505   i_img_dim last_row = ceil(y) + ceil_rad;
 506   i_img_dim first_col = floor(x) - ceil_rad;
 507   i_img_dim last_col = ceil(x) + ceil_rad;
 508   double r_sqr = rad * rad;
 509   i_img_dim max_width = 2 * ceil(rad) + 1;
 510   unsigned char *coverage = NULL;
 511   size_t coverage_size;
 512   int sub;
 513
 514   im_log((aIMCTX, 1, "i_circle_aa_low(im %p, centre(" i_DFp "), rad %.2f, r %p, ctx %p)\n",
 515           im, i_DFcp(x, y), rad, r, ctx));
 516
 517   if (first_row < 0)
 518     first_row = 0;
 519   if (last_row > im->ysize-1)
 520     last_row = im->ysize - 1;
 521   if (first_col < 0)
 522     first_col = 0;
 523   if (last_col > im->xsize-1)
 524     last_col = im->xsize - 1;
 525
 526   if (rad <= 0 || last_row < first_row || last_col < first_col) {
 527     /* outside the image */
 528     return;
 529   }
 530
 531   coverage_size = max_width;
 532   coverage = mymalloc(coverage_size);
 533
 534   for(ly = first_row; ly < last_row; ly++) {
 535     frac min_frac_x[16];
 536     frac max_frac_x[16];
 537     i_img_dim min_frac_left_x = 16 *(ceil(x) + ceil(rad));
 538     i_img_dim max_frac_left_x = -1;
 539     i_img_dim min_frac_right_x = 16 * (floor(x) - ceil(rad));
 540     i_img_dim max_frac_right_x = -1;
 541     /* reset work_y each row so the error doesn't build up */
 542     double work_y = ly;
 543     double dy, dy_sqr;
 544
 545     for (sub = 0; sub < 16; ++sub) {
 546       work_y += 1.0 / 16.0;
 547       dy = work_y - y;
 548       dy_sqr = dy * dy;
 549
 550       if (dy_sqr < r_sqr) {
 551         double dx = sqrt(r_sqr - dy_sqr);
 552         double left_x = x - dx;
 553         double right_x = x + dx;
 554         frac frac_left_x = float_to_frac(left_x);
 555         frac frac_right_x = float_to_frac(right_x);
 556
 557         if (frac_left_x < min_frac_left_x)
 558           min_frac_left_x = frac_left_x;
 559         if (frac_left_x > max_frac_left_x)
 560           max_frac_left_x = frac_left_x;
 561         if (frac_right_x < min_frac_right_x)
 562           min_frac_right_x = frac_right_x;
 563         if (frac_right_x > max_frac_right_x)
 564           max_frac_right_x = frac_right_x;
 565         min_frac_x[sub] = frac_left_x;
 566         max_frac_x[sub] = frac_right_x;
 567       }
 568       else {
 569         min_frac_x[sub] = max_frac_x[sub] = 0;
 570         max_frac_left_x = im->xsize * 16;
 571         min_frac_right_x = -1;
 572       }
 573     }
 574
 575     if (min_frac_left_x != -1) {
 576       /* something to draw on this line */
 577       i_img_dim min_x = (min_frac_left_x / 16);
 578       i_img_dim max_x = (max_frac_right_x + 15) / 16;
 579       i_img_dim left_solid = (max_frac_left_x + 15) / 16;
 580       i_img_dim right_solid = min_frac_right_x / 16;
 581       i_img_dim work_x;
 582       i_img_dim frac_work_x;
 583       i_sample_t *cout = coverage;
 584
 585       for (work_x = min_x, frac_work_x = min_x * 16;
 586            work_x <= max_x;
 587            ++work_x, frac_work_x += 16) {
 588         if (work_x <= left_solid || work_x >= right_solid) {
 589           int pix_coverage = 0;
 590           int ch;
 591           double ratio;
 592           i_img_dim frac_work_right = frac_work_x + 16;
 593           for (sub = 0; sub < 16; ++sub) {
 594             frac pix_left = min_frac_x[sub];
 595             frac pix_right = max_frac_x[sub];
 596             if (pix_left < pix_right
 597                 && pix_left < frac_work_right
 598                 && pix_right >= frac_work_x) {
 599               if (pix_left < frac_work_x)
 600                 pix_left = frac_work_x;
 601               if (pix_right > frac_work_right)
 602                 pix_right = frac_work_right;
 603               pix_coverage += pix_right - pix_left;
 604             }
 605           }
 606
 607           assert(pix_coverage <= 256);
 608           *cout++ = pix_coverage * 255 / 256;
 609         }
 610         else {
 611           /* full coverage */
 612           *cout++ = 255;
 613         }
 614       }
 615       r(im, min_x, ly, max_x - min_x + 1, coverage, ctx);
 616     }
 617   }
 618
 619   myfree(coverage);
 620 }
 621
 622 static void
 623 scanline_flush_color(i_img *im, i_img_dim x, i_img_dim y, i_img_dim width, const unsigned char *cover, void *ctx) {
 624   flush_color_t *fc = ctx;
 625
 626   i_render_color(&fc->r, x, y, width, cover, &fc->c);
 627 }
 628
 629 static void
 630 scanline_flush_fill(i_img *im, i_img_dim x, i_img_dim y, i_img_dim width, const unsigned char *cover, void *ctx) {
 631   flush_fill_t *ff = ctx;
 632
 633   i_render_fill(&ff->r, x, y, width, cover, ff->fill);
 634 }
 635
 636
 637 /*
 638 =item i_circle_out(im, x, y, r, col)
 639
 640 =category Drawing
 641 =synopsis i_circle_out(im, 50, 50, 45, &color);
 642
 643 Draw a circle outline centered at (x,y) with radius r,
 644 non-anti-aliased.
 645
 646 Parameters:
 647
 648 =over
 649
 650 =item *
 651
 652 (x, y) - the center of the circle
 653
 654 =item *
 655
 656 r - the radius of the circle in pixels, must be non-negative
 657
 658 =back
 659
 660 Returns non-zero on success.
 661
 662 Implementation:
 663
 664 =cut
 665 */
 666
 667 int
 668 i_circle_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
 669              const i_color *col) {
 670   i_img_dim x, y;
 671   i_img_dim dx, dy;
 672   int error;
 673   dIMCTXim(im);
 674
 675   im_log((aIMCTX, 1, "i_circle_out(im %p, centre(" i_DFp "), rad %" i_DF ", col %p)\n",
 676           im, i_DFcp(xc, yc), i_DFc(r), col));
 677
 678   im_clear_error(aIMCTX);
 679
 680   if (r < 0) {
 681     im_push_error(aIMCTX, 0, "circle: radius must be non-negative");
 682     return 0;
 683   }
 684
 685   i_ppix(im, xc+r, yc, col);
 686   i_ppix(im, xc-r, yc, col);
 687   i_ppix(im, xc, yc+r, col);
 688   i_ppix(im, xc, yc-r, col);
 689
 690   x = 0;
 691   y = r;
 692   dx = 1;
 693   dy = -2 * r;
 694   error = 1 - r;
 695   while (x < y) {
 696     if (error >= 0) {
 697       --y;
 698       dy += 2;
 699       error += dy;
 700     }
 701     ++x;
 702     dx += 2;
 703     error += dx;
 704
 705     i_ppix(im, xc + x, yc + y, col);
 706     i_ppix(im, xc + x, yc - y, col);
 707     i_ppix(im, xc - x, yc + y, col);
 708     i_ppix(im, xc - x, yc - y, col);
 709     if (x != y) {
 710       i_ppix(im, xc + y, yc + x, col);
 711       i_ppix(im, xc + y, yc - x, col);
 712       i_ppix(im, xc - y, yc + x, col);
 713       i_ppix(im, xc - y, yc - x, col);
 714     }
 715   }
 716
 717   return 1;
 718 }
 719
 720 /*
 721 =item arc_seg(angle)
 722
 723 Convert an angle in degrees into an angle measure we can generate
 724 simply from the numbers we have when drawing the circle.
 725
 726 =cut
 727 */
 728
 729 static i_img_dim
 730 arc_seg(double angle, int scale) {
 731   i_img_dim seg = (angle + 45) / 90;
 732   double remains = angle - seg * 90; /* should be in the range [-45,45] */
 733
 734   while (seg > 4)
 735     seg -= 4;
 736   if (seg == 4 && remains > 0)
 737     seg = 0;
 738
 739   return scale * (seg * 2 + sin(remains * PI/180));
 740 }
 741
 742 /*
 743 =item i_arc_out(im, x, y, r, d1, d2, col)
 744
 745 =category Drawing
 746 =synopsis i_arc_out(im, 50, 50, 45, 45, 135, &color);
 747
 748 Draw an arc outline centered at (x,y) with radius r, non-anti-aliased
 749 over the angle range d1 through d2 degrees.
 750
 751 Parameters:
 752
 753 =over
 754
 755 =item *
 756
 757 (x, y) - the center of the circle
 758
 759 =item *
 760
 761 r - the radius of the circle in pixels, must be non-negative
 762
 763 =item *
 764
 765 d1, d2 - the range of angles to draw the arc over, in degrees.
 766
 767 =back
 768
 769 Returns non-zero on success.
 770
 771 Implementation:
 772
 773 =cut
 774 */
 775
 776 int
 777 i_arc_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
 778           double d1, double d2, const i_color *col) {
 779   i_img_dim x, y;
 780   i_img_dim dx, dy;
 781   int error;
 782   i_img_dim segs[2][2];
 783   int seg_count;
 784   i_img_dim sin_th;
 785   i_img_dim seg_d1, seg_d2;
 786   int seg_num;
 787   i_img_dim scale = r + 1;
 788   i_img_dim seg1 = scale * 2;
 789   i_img_dim seg2 = scale * 4;
 790   i_img_dim seg3 = scale * 6;
 791   i_img_dim seg4 = scale * 8;
 792   dIMCTXim(im);
 793
 794   im_log((aIMCTX,1,"i_arc_out(im %p,centre(" i_DFp "), rad %" i_DF ", d1 %f, d2 %f, col %p)",
 795           im, i_DFcp(xc, yc), i_DFc(r), d1, d2, col));
 796
 797   im_clear_error(aIMCTX);
 798
 799   if (r <= 0) {
 800     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
 801     return 0;
 802   }
 803   if (d1 + 360 <= d2)
 804     return i_circle_out(im, xc, yc, r, col);
 805
 806   if (d1 < 0)
 807     d1 += 360 * floor((-d1 + 359) / 360);
 808   if (d2 < 0)
 809     d2 += 360 * floor((-d2 + 359) / 360);
 810   d1 = fmod(d1, 360);
 811   d2 = fmod(d2, 360);
 812   seg_d1 = arc_seg(d1, scale);
 813   seg_d2 = arc_seg(d2, scale);
 814   if (seg_d2 < seg_d1) {
 815     /* split into two segments */
 816     segs[0][0] = 0;
 817     segs[0][1] = seg_d2;
 818     segs[1][0] = seg_d1;
 819     segs[1][1] = seg4;
 820     seg_count = 2;
 821   }
 822   else {
 823     segs[0][0] = seg_d1;
 824     segs[0][1] = seg_d2;
 825     seg_count = 1;
 826   }
 827
 828   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
 829     i_img_dim seg_start = segs[seg_num][0];
 830     i_img_dim seg_end = segs[seg_num][1];
 831     if (seg_start == 0)
 832       i_ppix(im, xc+r, yc, col);
 833     if (seg_start <= seg1 && seg_end >= seg1)
 834       i_ppix(im, xc, yc+r, col);
 835     if (seg_start <= seg2 && seg_end >= seg2)
 836       i_ppix(im, xc-r, yc, col);
 837     if (seg_start <= seg3 && seg_end >= seg3)
 838       i_ppix(im, xc, yc-r, col);
 839
 840     y = 0;
 841     x = r;
 842     dy = 1;
 843     dx = -2 * r;
 844     error = 1 - r;
 845     while (y < x) {
 846       if (error >= 0) {
 847         --x;
 848         dx += 2;
 849         error += dx;
 850       }
 851       ++y;
 852       dy += 2;
 853       error += dy;
 854
 855       sin_th = y;
 856       if (seg_start <= sin_th && seg_end >= sin_th)
 857         i_ppix(im, xc + x, yc + y, col);
 858       if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
 859         i_ppix(im, xc + y, yc + x, col);
 860
 861       if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
 862         i_ppix(im, xc - y, yc + x, col);
 863       if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
 864         i_ppix(im, xc - x, yc + y, col);
 865
 866       if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
 867         i_ppix(im, xc - x, yc - y, col);
 868       if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
 869         i_ppix(im, xc - y, yc - x, col);
 870
 871       if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
 872         i_ppix(im, xc + y, yc - x, col);
 873       if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
 874         i_ppix(im, xc + x, yc - y, col);
 875     }
 876   }
 877
 878   return 1;
 879 }
 880
 881 static double
 882 cover(i_img_dim r, i_img_dim j) {
 883   double rjsqrt = sqrt(r*r - j*j);
 884
 885   return ceil(rjsqrt) - rjsqrt;
 886 }
 887
 888 /*
 889 =item i_circle_out_aa(im, xc, yc, r, col)
 890
 891 =synopsis i_circle_out_aa(im, 50, 50, 45, &color);
 892
 893 Draw a circle outline centered at (x,y) with radius r, anti-aliased.
 894
 895 Parameters:
 896
 897 =over
 898
 899 =item *
 900
 901 (xc, yc) - the center of the circle
 902
 903 =item *
 904
 905 r - the radius of the circle in pixels, must be non-negative
 906
 907 =item *
 908
 909 col - an i_color for the color to draw in.
 910
 911 =back
 912
 913 Returns non-zero on success.
 914
 915 =cut
 916
 917 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
 918 Gems.
 919
 920 I use floating point for I<D> since for large circles the precision of
 921 a [0,255] value isn't sufficient when approaching the end of the
 922 octant.
 923
 924 */
 925
 926 int
 927 i_circle_out_aa(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r, const i_color *col) {
 928   i_img_dim i, j;
 929   double t;
 930   i_color workc = *col;
 931   int orig_alpha = col->channel[3];
 932   dIMCTXim(im);
 933
 934   im_log((aIMCTX,1,"i_circle_out_aa(im %p,centre(" i_DFp "), rad %" i_DF ", col %p)",
 935           im, i_DFcp(xc, yc), i_DFc(r), col));
 936
 937   im_clear_error(aIMCTX);
 938   if (r <= 0) {
 939     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
 940     return 0;
 941   }
 942   i = r;
 943   j = 0;
 944   t = 0;
 945   i_ppix_norm(im, xc+i, yc+j, col);
 946   i_ppix_norm(im, xc-i, yc+j, col);
 947   i_ppix_norm(im, xc+j, yc+i, col);
 948   i_ppix_norm(im, xc+j, yc-i, col);
 949
 950   while (i > j+1) {
 951     double d;
 952     int cv, inv_cv;
 953     j++;
 954     d = cover(r, j);
 955     cv = (int)(d * 255 + 0.5);
 956     inv_cv = 255-cv;
 957     if (d < t) {
 958       --i;
 959     }
 960     if (inv_cv) {
 961       workc.channel[3] = orig_alpha * inv_cv / 255;
 962       i_ppix_norm(im, xc+i, yc+j, &workc);
 963       i_ppix_norm(im, xc-i, yc+j, &workc);
 964       i_ppix_norm(im, xc+i, yc-j, &workc);
 965       i_ppix_norm(im, xc-i, yc-j, &workc);
 966
 967       if (i != j) {
 968         i_ppix_norm(im, xc+j, yc+i, &workc);
 969         i_ppix_norm(im, xc-j, yc+i, &workc);
 970         i_ppix_norm(im, xc+j, yc-i, &workc);
 971         i_ppix_norm(im, xc-j, yc-i, &workc);
 972       }
 973     }
 974     if (cv && i > j) {
 975       workc.channel[3] = orig_alpha * cv / 255;
 976       i_ppix_norm(im, xc+i-1, yc+j, &workc);
 977       i_ppix_norm(im, xc-i+1, yc+j, &workc);
 978       i_ppix_norm(im, xc+i-1, yc-j, &workc);
 979       i_ppix_norm(im, xc-i+1, yc-j, &workc);
 980
 981       if (j != i-1) {
 982         i_ppix_norm(im, xc+j, yc+i-1, &workc);
 983         i_ppix_norm(im, xc-j, yc+i-1, &workc);
 984         i_ppix_norm(im, xc+j, yc-i+1, &workc);
 985         i_ppix_norm(im, xc-j, yc-i+1, &workc);
 986       }
 987     }
 988     t = d;
 989   }
 990
 991   return 1;
 992 }
 993
 994 /*
 995 =item i_arc_out_aa(im, xc, yc, r, d1, d2, col)
 996
 997 =synopsis i_arc_out_aa(im, 50, 50, 45, 45, 125, &color);
 998
 999 Draw a circle arc outline centered at (x,y) with radius r, from angle
1000 d1 degrees through angle d2 degrees, anti-aliased.
1001
1002 Parameters:
1003
1004 =over
1005
1006 =item *
1007
1008 (xc, yc) - the center of the circle
1009
1010 =item *
1011
1012 r - the radius of the circle in pixels, must be non-negative
1013
1014 =item *
1015
1016 d1, d2 - the range of angle in degrees to draw the arc through.  If
1017 d2-d1 >= 360 a full circle is drawn.
1018
1019 =back
1020
1021 Returns non-zero on success.
1022
1023 =cut
1024
1025 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
1026 Gems.
1027
1028 */
1029
1030 int
1031 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) {
1032   i_img_dim i, j;
1033   double t;
1034   i_color workc = *col;
1035   i_img_dim segs[2][2];
1036   int seg_count;
1037   i_img_dim sin_th;
1038   i_img_dim seg_d1, seg_d2;
1039   int seg_num;
1040   int orig_alpha = col->channel[3];
1041   i_img_dim scale = r + 1;
1042   i_img_dim seg1 = scale * 2;
1043   i_img_dim seg2 = scale * 4;
1044   i_img_dim seg3 = scale * 6;
1045   i_img_dim seg4 = scale * 8;
1046   dIMCTXim(im);
1047
1048   im_log((aIMCTX,1,"i_arc_out_aa(im %p,centre(" i_DFp "), rad %" i_DF ", d1 %f, d2 %f, col %p)",
1049           im, i_DFcp(xc, yc), i_DFc(r), d1, d2, col));
1050
1051   im_clear_error(aIMCTX);
1052   if (r <= 0) {
1053     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
1054     return 0;
1055   }
1056   if (d1 + 360 <= d2)
1057     return i_circle_out_aa(im, xc, yc, r, col);
1058
1059   if (d1 < 0)
1060     d1 += 360 * floor((-d1 + 359) / 360);
1061   if (d2 < 0)
1062     d2 += 360 * floor((-d2 + 359) / 360);
1063   d1 = fmod(d1, 360);
1064   d2 = fmod(d2, 360);
1065   seg_d1 = arc_seg(d1, scale);
1066   seg_d2 = arc_seg(d2, scale);
1067   if (seg_d2 < seg_d1) {
1068     /* split into two segments */
1069     segs[0][0] = 0;
1070     segs[0][1] = seg_d2;
1071     segs[1][0] = seg_d1;
1072     segs[1][1] = seg4;
1073     seg_count = 2;
1074   }
1075   else {
1076     segs[0][0] = seg_d1;
1077     segs[0][1] = seg_d2;
1078     seg_count = 1;
1079   }
1080
1081   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
1082     i_img_dim seg_start = segs[seg_num][0];
1083     i_img_dim seg_end = segs[seg_num][1];
1084
1085     i = r;
1086     j = 0;
1087     t = 0;
1088
1089     if (seg_start == 0)
1090       i_ppix_norm(im, xc+i, yc+j, col);
1091     if (seg_start <= seg1 && seg_end >= seg1)
1092       i_ppix_norm(im, xc+j, yc+i, col);
1093     if (seg_start <= seg2 && seg_end >= seg2)
1094       i_ppix_norm(im, xc-i, yc+j, col);
1095     if (seg_start <= seg3 && seg_end >= seg3)
1096       i_ppix_norm(im, xc+j, yc-i, col);
1097
1098     while (i > j+1) {
1099       int cv, inv_cv;
1100       double d;
1101       j++;
1102       d = cover(r, j);
1103       cv = (int)(d * 255 + 0.5);
1104       inv_cv = 255-cv;
1105       if (d < t) {
1106         --i;
1107       }
1108       sin_th = j;
1109       if (inv_cv) {
1110         workc.channel[3] = orig_alpha * inv_cv / 255;
1111
1112         if (seg_start <= sin_th && seg_end >= sin_th)
1113           i_ppix_norm(im, xc+i, yc+j, &workc);
1114         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1115           i_ppix_norm(im, xc-i, yc+j, &workc);
1116         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1117           i_ppix_norm(im, xc+i, yc-j, &workc);
1118         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1119           i_ppix_norm(im, xc-i, yc-j, &workc);
1120
1121         if (i != j) {
1122           if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1123             i_ppix_norm(im, xc+j, yc+i, &workc);
1124           if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1125             i_ppix_norm(im, xc-j, yc+i, &workc);
1126           if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1127             i_ppix_norm(im, xc+j, yc-i, &workc);
1128           if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1129             i_ppix_norm(im, xc-j, yc-i, &workc);
1130         }
1131       }
1132       if (cv && i > j) {
1133         workc.channel[3] = orig_alpha * cv / 255;
1134         if (seg_start <= sin_th && seg_end >= sin_th)
1135           i_ppix_norm(im, xc+i-1, yc+j, &workc);
1136         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1137           i_ppix_norm(im, xc-i+1, yc+j, &workc);
1138         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1139           i_ppix_norm(im, xc+i-1, yc-j, &workc);
1140         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1141           i_ppix_norm(im, xc-i+1, yc-j, &workc);
1142
1143         if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1144           i_ppix_norm(im, xc+j, yc+i-1, &workc);
1145         if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1146           i_ppix_norm(im, xc-j, yc+i-1, &workc);
1147         if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1148           i_ppix_norm(im, xc+j, yc-i+1, &workc);
1149         if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1150           i_ppix_norm(im, xc-j, yc-i+1, &workc);
1151       }
1152       t = d;
1153     }
1154   }
1155
1156   return 1;
1157 }
1158
1159 /*
1160 =item i_box(im, x1, y1, x2, y2, color)
1161
1162 =category Drawing
1163 =synopsis i_box(im, 0, 0, im->xsize-1, im->ysize-1, &color).
1164
1165 Outlines the box from (x1,y1) to (x2,y2) inclusive with I<color>.
1166
1167 =cut
1168 */
1169
1170 void
1171 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) {
1172   i_img_dim x,y;
1173   dIMCTXim(im);
1174
1175   im_log((aIMCTX, 1,"i_box(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1176           im, i_DFcp(x1,y1), i_DFcp(x2,y2), val));
1177   for(x=x1;x<x2+1;x++) {
1178     i_ppix(im,x,y1,val);
1179     i_ppix(im,x,y2,val);
1180   }
1181   for(y=y1;y<y2+1;y++) {
1182     i_ppix(im,x1,y,val);
1183     i_ppix(im,x2,y,val);
1184   }
1185 }
1186
1187 /*
1188 =item i_box_filled(im, x1, y1, x2, y2, color)
1189
1190 =category Drawing
1191 =synopsis i_box_filled(im, 0, 0, im->xsize-1, im->ysize-1, &color);
1192
1193 Fills the box from (x1,y1) to (x2,y2) inclusive with color.
1194
1195 =cut
1196 */
1197
1198 void
1199 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) {
1200   i_img_dim x, y, width;
1201   i_palidx index;
1202   dIMCTXim(im);
1203
1204   im_log((aIMCTX,1,"i_box_filled(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1205           im, i_DFcp(x1, y1), i_DFcp(x2,y2) ,val));
1206
1207   if (x1 > x2 || y1 > y2
1208       || x2 < 0 || y2 < 0
1209       || x1 >= im->xsize || y1 > im->ysize)
1210     return;
1211
1212   if (x1 < 0)
1213     x1 = 0;
1214   if (x2 >= im->xsize)
1215     x2 = im->xsize - 1;
1216   if (y1 < 0)
1217     y1 = 0;
1218   if (y2 >= im->ysize)
1219     y2 = im->ysize - 1;
1220
1221   width = x2 - x1 + 1;
1222
1223   if (im->type == i_palette_type
1224       && i_findcolor(im, val, &index)) {
1225     i_palidx *line = mymalloc(sizeof(i_palidx) * width);
1226
1227     for (x = 0; x < width; ++x)
1228       line[x] = index;
1229
1230     for (y = y1; y <= y2; ++y)
1231       i_ppal(im, x1, x2+1, y, line);
1232
1233     myfree(line);
1234   }
1235   else {
1236     i_color *line = mymalloc(sizeof(i_color) * width);
1237
1238     for (x = 0; x < width; ++x)
1239       line[x] = *val;
1240
1241     for (y = y1; y <= y2; ++y)
1242       i_plin(im, x1, x2+1, y, line);
1243
1244     myfree(line);
1245   }
1246 }
1247
1248 /*
1249 =item i_box_filledf(im, x1, y1, x2, y2, color)
1250
1251 =category Drawing
1252 =synopsis i_box_filledf(im, 0, 0, im->xsize-1, im->ysize-1, &fcolor);
1253
1254 Fills the box from (x1,y1) to (x2,y2) inclusive with a floating point
1255 color.
1256
1257 =cut
1258 */
1259
1260 int
1261 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) {
1262   i_img_dim x, y, width;
1263   dIMCTXim(im);
1264
1265   im_log((aIMCTX, 1,"i_box_filledf(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1266           im, i_DFcp(x1, y1), i_DFcp(x2, y2), val));
1267
1268   if (x1 > x2 || y1 > y2
1269       || x2 < 0 || y2 < 0
1270       || x1 >= im->xsize || y1 > im->ysize)
1271     return 0;
1272
1273   if (x1 < 0)
1274     x1 = 0;
1275   if (x2 >= im->xsize)
1276     x2 = im->xsize - 1;
1277   if (y1 < 0)
1278     y1 = 0;
1279   if (y2 >= im->ysize)
1280     y2 = im->ysize - 1;
1281
1282   width = x2 - x1 + 1;
1283
1284   if (im->bits <= 8) {
1285     i_color c;
1286     c.rgba.r = SampleFTo8(val->rgba.r);
1287     c.rgba.g = SampleFTo8(val->rgba.g);
1288     c.rgba.b = SampleFTo8(val->rgba.b);
1289     c.rgba.a = SampleFTo8(val->rgba.a);
1290
1291     i_box_filled(im, x1, y1, x2, y2, &c);
1292   }
1293   else {
1294     i_fcolor *line = mymalloc(sizeof(i_fcolor) * width);
1295
1296     for (x = 0; x < width; ++x)
1297       line[x] = *val;
1298
1299     for (y = y1; y <= y2; ++y)
1300       i_plinf(im, x1, x2+1, y, line);
1301
1302     myfree(line);
1303   }
1304
1305   return 1;
1306 }
1307
1308 /*
1309 =item i_box_cfill(im, x1, y1, x2, y2, fill)
1310
1311 =category Drawing
1312 =synopsis i_box_cfill(im, 0, 0, im->xsize-1, im->ysize-1, fill);
1313
1314 Fills the box from (x1,y1) to (x2,y2) inclusive with fill.
1315
1316 =cut
1317 */
1318
1319 void
1320 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) {
1321   i_render r;
1322   dIMCTXim(im);
1323
1324   im_log((aIMCTX,1,"i_box_cfill(im* %p, p1(" i_DFp "), p2(" i_DFp "), fill %p)\n",
1325           im, i_DFcp(x1, y1), i_DFcp(x2,y2), fill));
1326
1327   ++x2;
1328   if (x1 < 0)
1329     x1 = 0;
1330   if (y1 < 0)
1331     y1 = 0;
1332   if (x2 > im->xsize)
1333     x2 = im->xsize;
1334   if (y2 >= im->ysize)
1335     y2 = im->ysize-1;
1336   if (x1 >= x2 || y1 > y2)
1337     return;
1338
1339   i_render_init(&r, im, x2-x1);
1340   while (y1 <= y2) {
1341     i_render_fill(&r, x1, y1, x2-x1, NULL, fill);
1342     ++y1;
1343   }
1344   i_render_done(&r);
1345 }
1346
1347 /*
1348 =item i_line(C<im>, C<x1>, C<y1>, C<x2>, C<y2>, C<color>, C<endp>)
1349
1350 =category Drawing
1351
1352 =for stopwords Bresenham's
1353
1354 Draw a line to image using Bresenham's line drawing algorithm
1355
1356    im    - image to draw to
1357    x1    - starting x coordinate
1358    y1    - starting x coordinate
1359    x2    - starting x coordinate
1360    y2    - starting x coordinate
1361    color - color to write to image
1362    endp  - endpoint flag (boolean)
1363
1364 =cut
1365 */
1366
1367 void
1368 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) {
1369   i_img_dim x, y;
1370   i_img_dim dx, dy;
1371   i_img_dim p;
1372
1373   dx = x2 - x1;
1374   dy = y2 - y1;
1375
1376
1377   /* choose variable to iterate on */
1378   if (i_abs(dx) > i_abs(dy)) {
1379     i_img_dim dx2, dy2, cpy;
1380
1381     /* sort by x */
1382     if (x1 > x2) {
1383       i_img_dim t;
1384       t = x1; x1 = x2; x2 = t;
1385       t = y1; y1 = y2; y2 = t;
1386     }
1387
1388     dx = i_abs(dx);
1389     dx2 = dx*2;
1390     dy = y2 - y1;
1391
1392     if (dy<0) {
1393       dy = -dy;
1394       cpy = -1;
1395     } else {
1396       cpy = 1;
1397     }
1398     dy2 = dy*2;
1399     p = dy2 - dx;
1400
1401
1402     y = y1;
1403     for(x=x1; x<x2-1; x++) {
1404       if (p<0) {
1405         p += dy2;
1406       } else {
1407         y += cpy;
1408         p += dy2-dx2;
1409       }
1410       i_ppix(im, x+1, y, val);
1411     }
1412   } else {
1413     i_img_dim dy2, dx2, cpx;
1414
1415     /* sort bx y */
1416     if (y1 > y2) {
1417       i_img_dim t;
1418       t = x1; x1 = x2; x2 = t;
1419       t = y1; y1 = y2; y2 = t;
1420     }
1421
1422     dy = i_abs(dy);
1423     dx = x2 - x1;
1424     dy2 = dy*2;
1425
1426     if (dx<0) {
1427       dx = -dx;
1428       cpx = -1;
1429     } else {
1430       cpx = 1;
1431     }
1432     dx2 = dx*2;
1433     p = dx2 - dy;
1434
1435     x = x1;
1436
1437     for(y=y1; y<y2-1; y++) {
1438       if (p<0) {
1439         p  += dx2;
1440       } else {
1441         x += cpx;
1442         p += dx2-dy2;
1443       }
1444       i_ppix(im, x, y+1, val);
1445     }
1446   }
1447   if (endp) {
1448     i_ppix(im, x1, y1, val);
1449     i_ppix(im, x2, y2, val);
1450   } else {
1451     if (x1 != x2 || y1 != y2)
1452       i_ppix(im, x1, y1, val);
1453   }
1454 }
1455
1456
1457 void
1458 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) {
1459
1460   double dy;
1461   i_img_dim x;
1462
1463   for(x=x1; x<=x2; x++) {
1464     dy = y1+ (x-x1)/(double)(x2-x1)*(y2-y1);
1465     i_ppix(im, x, (i_img_dim)(dy+0.5), val);
1466   }
1467 }
1468
1469 /*
1470 =item i_line_aa(C<im>, C<x1>, C<x2>, C<y1>, C<y2>, C<color>, C<endp>)
1471
1472 =category Drawing
1473
1474 Anti-alias draws a line from (x1,y1) to (x2, y2) in color.
1475
1476 The point (x2, y2) is drawn only if C<endp> is set.
1477
1478 =cut
1479 */
1480
1481 void
1482 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) {
1483   i_img_dim x, y;
1484   i_img_dim dx, dy;
1485   i_img_dim p;
1486
1487   dx = x2 - x1;
1488   dy = y2 - y1;
1489
1490   /* choose variable to iterate on */
1491   if (i_abs(dx) > i_abs(dy)) {
1492     i_img_dim dx2, dy2, cpy;
1493
1494     /* sort by x */
1495     if (x1 > x2) {
1496       i_img_dim t;
1497       t = x1; x1 = x2; x2 = t;
1498       t = y1; y1 = y2; y2 = t;
1499     }
1500
1501     dx = i_abs(dx);
1502     dx2 = dx*2;
1503     dy = y2 - y1;
1504
1505     if (dy<0) {
1506       dy = -dy;
1507       cpy = -1;
1508     } else {
1509       cpy = 1;
1510     }
1511     dy2 = dy*2;
1512     p = dy2 - dx2; /* this has to be like this for AA */
1513
1514     y = y1;
1515
1516     for(x=x1; x<x2-1; x++) {
1517       int ch;
1518       i_color tval;
1519       double t = (dy) ? -(float)(p)/(float)(dx2) : 1;
1520       double t1, t2;
1521
1522       if (t<0) t = 0;
1523       t1 = 1-t;
1524       t2 = t;
1525
1526       i_gpix(im,x+1,y,&tval);
1527       for(ch=0;ch<im->channels;ch++)
1528         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
1529       i_ppix(im,x+1,y,&tval);
1530
1531       i_gpix(im,x+1,y+cpy,&tval);
1532       for(ch=0;ch<im->channels;ch++)
1533         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
1534       i_ppix(im,x+1,y+cpy,&tval);
1535
1536       if (p<0) {
1537         p += dy2;
1538       } else {
1539         y += cpy;
1540         p += dy2-dx2;
1541       }
1542     }
1543   } else {
1544     i_img_dim dy2, dx2, cpx;
1545
1546     /* sort bx y */
1547     if (y1 > y2) {
1548       i_img_dim t;
1549       t = x1; x1 = x2; x2 = t;
1550       t = y1; y1 = y2; y2 = t;
1551     }
1552
1553     dy = i_abs(dy);
1554     dx = x2 - x1;
1555     dy2 = dy*2;
1556
1557     if (dx<0) {
1558       dx = -dx;
1559       cpx = -1;
1560     } else {
1561       cpx = 1;
1562     }
1563     dx2 = dx*2;
1564     p = dx2 - dy2; /* this has to be like this for AA */
1565
1566     x = x1;
1567
1568     for(y=y1; y<y2-1; y++) {
1569       int ch;
1570       i_color tval;
1571       double t = (dx) ? -(double)(p)/(double)(dy2) : 1;
1572       double t1, t2;
1573
1574       if (t<0) t = 0;
1575       t1 = 1-t;
1576       t2 = t;
1577
1578       i_gpix(im,x,y+1,&tval);
1579       for(ch=0;ch<im->channels;ch++)
1580         tval.channel[ch]=(unsigned char)(t1*(double)tval.channel[ch]+t2*(double)val->channel[ch]);
1581       i_ppix(im,x,y+1,&tval);
1582
1583       i_gpix(im,x+cpx,y+1,&tval);
1584       for(ch=0;ch<im->channels;ch++)
1585         tval.channel[ch]=(unsigned char)(t2*(double)tval.channel[ch]+t1*(double)val->channel[ch]);
1586       i_ppix(im,x+cpx,y+1,&tval);
1587
1588       if (p<0) {
1589         p  += dx2;
1590       } else {
1591         x += cpx;
1592         p += dx2-dy2;
1593       }
1594     }
1595   }
1596
1597
1598   if (endp) {
1599     i_ppix(im, x1, y1, val);
1600     i_ppix(im, x2, y2, val);
1601   } else {
1602     if (x1 != x2 || y1 != y2)
1603       i_ppix(im, x1, y1, val);
1604   }
1605 }
1606
1607
1608
1609 static double
1610 perm(i_img_dim n,i_img_dim k) {
1611   double r;
1612   i_img_dim i;
1613   r=1;
1614   for(i=k+1;i<=n;i++) r*=i;
1615   for(i=1;i<=(n-k);i++) r/=i;
1616   return r;
1617 }
1618
1619
1620 /* Note in calculating t^k*(1-t)^(n-k)
1621    we can start by using t^0=1 so this simplifies to
1622    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
1623    to get a new level - this may lead to errors who knows lets test it */
1624
1625 void
1626 i_bezier_multi(i_img *im,int l,const double *x,const double *y, const i_color *val) {
1627   double *bzcoef;
1628   double t,cx,cy;
1629   int k,i;
1630   i_img_dim lx = 0,ly = 0;
1631   int n=l-1;
1632   double itr,ccoef;
1633
1634   /* this is the same size as the x and y arrays, so shouldn't overflow */
1635   bzcoef=mymalloc(sizeof(double)*l); /* checked 5jul05 tonyc */
1636   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
1637   ICL_info(val);
1638
1639
1640   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
1641   i=0;
1642   for(t=0;t<=1;t+=0.005) {
1643     cx=cy=0;
1644     itr=t/(1-t);
1645     ccoef=pow(1-t,n);
1646     for(k=0;k<l;k++) {
1647       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
1648               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
1649
1650       cx+=bzcoef[k]*x[k]*ccoef;
1651       cy+=bzcoef[k]*y[k]*ccoef;
1652       ccoef*=itr;
1653     }
1654     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
1655     if (i++) {
1656       i_line_aa(im,lx,ly,(i_img_dim)(0.5+cx),(i_img_dim)(0.5+cy),val, 1);
1657     }
1658       /*     i_ppix(im,(i_img_dim)(0.5+cx),(i_img_dim)(0.5+cy),val); */
1659     lx=(i_img_dim)(0.5+cx);
1660     ly=(i_img_dim)(0.5+cy);
1661   }
1662   ICL_info(val);
1663   myfree(bzcoef);
1664 }
1665
1666 /* Flood fill
1667
1668    REF: Graphics Gems I. page 282+
1669
1670 */
1671
1672 /* This should be moved into a seperate file? */
1673
1674 /* This is the truncation used:
1675
1676    a double is multiplied by 16 and then truncated.
1677    This means that 0 -> 0
1678    So a triangle of (0,0) (10,10) (10,0) Will look like it's
1679    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
1680
1681 */
1682
1683
1684 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
1685    graphics gems I */
1686
1687 /*
1688 struct stc {
1689   i_img_dim mylx,myrx;
1690   i_img_dim dadlx,dadrx;
1691   i_img_dim myy;
1692   int mydirection;
1693 };
1694
1695 Not used code???
1696 */
1697
1698
1699 struct stack_element {
1700   i_img_dim myLx,myRx;
1701   i_img_dim dadLx,dadRx;
1702   i_img_dim myY;
1703   int myDirection;
1704 };
1705
1706
1707 /* create the link data to put push onto the stack */
1708
1709 static
1710 struct stack_element*
1711 crdata(i_img_dim left,i_img_dim right,i_img_dim dadl,i_img_dim dadr,i_img_dim y, int dir) {
1712   struct stack_element *ste;
1713   ste              = mymalloc(sizeof(struct stack_element)); /* checked 5jul05 tonyc */
1714   ste->myLx        = left;
1715   ste->myRx        = right;
1716   ste->dadLx       = dadl;
1717   ste->dadRx       = dadr;
1718   ste->myY         = y;
1719   ste->myDirection = dir;
1720   return ste;
1721 }
1722
1723 /* i_ccomp compares two colors and gives true if they are the same */
1724
1725 typedef int (*ff_cmpfunc)(i_color const *c1, i_color const *c2, int channels);
1726
1727 static int
1728 i_ccomp_normal(i_color const *val1, i_color const *val2, int ch) {
1729   int i;
1730   for(i = 0; i < ch; i++)
1731     if (val1->channel[i] !=val2->channel[i])
1732       return 0;
1733   return 1;
1734 }
1735
1736 static int
1737 i_ccomp_border(i_color const *val1, i_color const *val2, int ch) {
1738   int i;
1739   for(i = 0; i < ch; i++)
1740     if (val1->channel[i] !=val2->channel[i])
1741       return 1;
1742   return 0;
1743 }
1744
1745 static int
1746 i_lspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1747   i_color cval;
1748   while(1) {
1749     if (seedx-1 < 0) break;
1750     i_gpix(im,seedx-1,seedy,&cval);
1751     if (!cmpfunc(val,&cval,im->channels))
1752       break;
1753     seedx--;
1754   }
1755   return seedx;
1756 }
1757
1758 static int
1759 i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1760   i_color cval;
1761   while(1) {
1762     if (seedx+1 > im->xsize-1) break;
1763     i_gpix(im,seedx+1,seedy,&cval);
1764     if (!cmpfunc(val,&cval,im->channels)) break;
1765     seedx++;
1766   }
1767   return seedx;
1768 }
1769
1770 #ifdef DEBUG_FLOOD_FILL
1771
1772 #define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir) \
1773   fprintf(stderr, "push(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
1774           i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
1775
1776 #define ST_POP_NOTE(left, right, dadl, dadr, y, dir) \
1777   fprintf(stderr, "popped(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
1778           i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
1779
1780 #define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)                  \
1781   fprintf(stderr, "stack(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
1782           i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
1783
1784 #else
1785
1786 #define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir)
1787
1788 #define ST_POP_NOTE(left, right, dadl, dadr, y, dir)
1789
1790 #define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)
1791
1792 #endif
1793
1794
1795 /* Macro to create a link and push on to the list */
1796
1797 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
1798   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
1799   ST_PUSH_NOTE(left, right, dadl, dadr, y, dir);                 \
1800   llist_push(st,&s);                                             \
1801 } while (0)
1802
1803 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
1804 /* No overflow check! */
1805
1806 #define ST_POP() do {         \
1807   struct stack_element *s;    \
1808   llist_pop(st,&s);           \
1809   lx        = s->myLx;        \
1810   rx        = s->myRx;        \
1811   dadLx     = s->dadLx;       \
1812   dadRx     = s->dadRx;       \
1813   y         = s->myY;         \
1814   direction = s->myDirection; \
1815   ST_POP_NOTE(lx, rx, dadLx, dadRx, y, direction);      \
1816   myfree(s);                  \
1817 } while (0)
1818
1819 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
1820   i_img_dim pushrx = rx+1;                                              \
1821   i_img_dim pushlx = lx-1;                                              \
1822   ST_STACK_NOTE(lx, rx, dadLx, dadRx, y, dir);           \
1823   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
1824   if (rx > dadRx)                                                 \
1825     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
1826   if (lx < dadLx)                                               \
1827     ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
1828 } while (0)
1829
1830 #define SET(x,y) btm_set(btm,x,y)
1831
1832 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
1833 #define INSIDE(x,y, seed) \
1834   (assert((x) >= 0 && (x) < (im)->xsize && (y) >= 0 && (y) < (im)->ysize), \
1835    (!btm_test(btm,x,y) && \
1836      ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
1837
1838 /* The function that does all the real work */
1839
1840 static struct i_bitmap *
1841 i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
1842                  i_img_dim *bxminp, i_img_dim *bxmaxp, i_img_dim *byminp, i_img_dim *bymaxp,
1843                  i_color const *seed, ff_cmpfunc cmpfunc) {
1844   i_img_dim ltx, rtx;
1845   i_img_dim tx = 0;
1846
1847   i_img_dim bxmin = seedx;
1848   i_img_dim bxmax = seedx;
1849   i_img_dim bymin = seedy;
1850   i_img_dim bymax = seedy;
1851
1852   struct llist *st;
1853   struct i_bitmap *btm;
1854
1855   int channels;
1856   i_img_dim xsize,ysize;
1857   i_color cval; /* used by the INSIDE() macro */
1858
1859   channels = im->channels;
1860   xsize    = im->xsize;
1861   ysize    = im->ysize;
1862
1863   btm = btm_new(xsize, ysize);
1864   st  = llist_new(100, sizeof(struct stack_element*));
1865
1866   /* Find the starting span and fill it */
1867   ltx = i_lspan(im, seedx, seedy, seed, cmpfunc);
1868   rtx = i_rspan(im, seedx, seedy, seed, cmpfunc);
1869   for(tx=ltx; tx<=rtx; tx++) SET(tx, seedy);
1870   bxmin = ltx;
1871   bxmax = rtx;
1872
1873   ST_PUSH(ltx, rtx, ltx, rtx, seedy+1,  1);
1874   ST_PUSH(ltx, rtx, ltx, rtx, seedy-1, -1);
1875
1876   while(st->count) {
1877     /* Stack variables */
1878     i_img_dim lx,rx;
1879     i_img_dim dadLx,dadRx;
1880     i_img_dim y;
1881     int direction;
1882
1883     i_img_dim x;
1884     int wasIn=0;
1885
1886     ST_POP(); /* sets lx, rx, dadLx, dadRx, y, direction */
1887
1888
1889     if (y<0 || y>ysize-1) continue;
1890     if (bymin > y) bymin=y; /* in the worst case an extra line */
1891     if (bymax < y) bymax=y;
1892
1893
1894     x = lx+1;
1895     if ( lx >= 0 && (wasIn = INSIDE(lx, y, seed)) ) {
1896       SET(lx, y);
1897       lx--;
1898       while(lx >= 0 && INSIDE(lx, y, seed)) {
1899         SET(lx,y);
1900         lx--;
1901       }
1902       /* lx should point at the left-most INSIDE() pixel */
1903       ++lx;
1904     }
1905
1906     if (bxmin > lx) bxmin = lx;
1907     while(x <= xsize-1) {
1908       /*  printf("x=%d\n",x); */
1909       if (wasIn) {
1910
1911         if (INSIDE(x, y, seed)) {
1912           /* case 1: was inside, am still inside */
1913           SET(x,y);
1914         } else {
1915           /* case 2: was inside, am no longer inside: just found the
1916              right edge of a span */
1917           ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1918
1919           if (bxmax < x) bxmax = x;
1920           wasIn=0;
1921         }
1922       } else {
1923         if (x > rx) goto EXT;
1924         if (INSIDE(x, y, seed)) {
1925           SET(x, y);
1926           /* case 3: Wasn't inside, am now: just found the start of a new run */
1927           wasIn = 1;
1928             lx = x;
1929         } else {
1930           /* case 4: Wasn't inside, still isn't */
1931         }
1932       }
1933       x++;
1934     }
1935   EXT: /* out of loop */
1936     if (wasIn) {
1937       /* hit an edge of the frame buffer while inside a run */
1938       ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1939       if (bxmax < x) bxmax = x;
1940     }
1941   }
1942
1943   llist_destroy(st);
1944
1945   *bxminp = bxmin;
1946   *bxmaxp = bxmax;
1947   *byminp = bymin;
1948   *bymaxp = bymax;
1949
1950   return btm;
1951 }
1952
1953 /*
1954 =item i_flood_fill(C<im>, C<seedx>, C<seedy>, C<color>)
1955
1956 =category Drawing
1957 =synopsis i_flood_fill(im, 50, 50, &color);
1958
1959 Flood fills the 4-connected region starting from the point (C<seedx>,
1960 C<seedy>) with I<color>.
1961
1962 Returns false if (C<seedx>, C<seedy>) are outside the image.
1963
1964 =cut
1965 */
1966
1967 undef_int
1968 i_flood_fill(i_img *im, i_img_dim seedx, i_img_dim seedy, const i_color *dcol) {
1969   i_img_dim bxmin, bxmax, bymin, bymax;
1970   struct i_bitmap *btm;
1971   i_img_dim x, y;
1972   i_color val;
1973   dIMCTXim(im);
1974
1975   im_log((aIMCTX, 1, "i_flood_fill(im %p, seed(" i_DFp "), col %p)",
1976           im, i_DFcp(seedx, seedy), dcol));
1977
1978   im_clear_error(aIMCTX);
1979   if (seedx < 0 || seedx >= im->xsize ||
1980       seedy < 0 || seedy >= im->ysize) {
1981     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
1982     return 0;
1983   }
1984
1985   /* Get the reference color */
1986   i_gpix(im, seedx, seedy, &val);
1987
1988   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1989                          &val, i_ccomp_normal);
1990
1991   for(y=bymin;y<=bymax;y++)
1992     for(x=bxmin;x<=bxmax;x++)
1993       if (btm_test(btm,x,y))
1994         i_ppix(im,x,y,dcol);
1995   btm_destroy(btm);
1996   return 1;
1997 }
1998
1999 /*
2000 =item i_flood_cfill(C<im>, C<seedx>, C<seedy>, C<fill>)
2001
2002 =category Drawing
2003 =synopsis i_flood_cfill(im, 50, 50, fill);
2004
2005 Flood fills the 4-connected region starting from the point (C<seedx>,
2006 C<seedy>) with C<fill>.
2007
2008 Returns false if (C<seedx>, C<seedy>) are outside the image.
2009
2010 =cut
2011 */
2012
2013 undef_int
2014 i_flood_cfill(i_img *im, i_img_dim seedx, i_img_dim seedy, i_fill_t *fill) {
2015   i_img_dim bxmin, bxmax, bymin, bymax;
2016   struct i_bitmap *btm;
2017   i_color val;
2018   dIMCTXim(im);
2019
2020   im_log((aIMCTX, 1, "i_flood_cfill(im %p, seed(" i_DFp "), fill %p)",
2021           im, i_DFcp(seedx, seedy), fill));
2022
2023   im_clear_error(aIMCTX);
2024
2025   if (seedx < 0 || seedx >= im->xsize ||
2026       seedy < 0 || seedy >= im->ysize) {
2027     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
2028     return 0;
2029   }
2030
2031   /* Get the reference color */
2032   i_gpix(im, seedx, seedy, &val);
2033
2034   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2035                          &val, i_ccomp_normal);
2036
2037   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
2038
2039   btm_destroy(btm);
2040   return 1;
2041 }
2042
2043 /*
2044 =item i_flood_fill_border(C<im>, C<seedx>, C<seedy>, C<color>, C<border>)
2045
2046 =category Drawing
2047 =synopsis i_flood_fill_border(im, 50, 50, &color, &border);
2048
2049 Flood fills the 4-connected region starting from the point (C<seedx>,
2050 C<seedy>) with C<color>, fill stops when the fill reaches a pixels
2051 with color C<border>.
2052
2053 Returns false if (C<seedx>, C<seedy>) are outside the image.
2054
2055 =cut
2056 */
2057
2058 undef_int
2059 i_flood_fill_border(i_img *im, i_img_dim seedx, i_img_dim seedy, const i_color *dcol,
2060                     const i_color *border) {
2061   i_img_dim bxmin, bxmax, bymin, bymax;
2062   struct i_bitmap *btm;
2063   i_img_dim x, y;
2064   dIMCTXim(im);
2065
2066   im_log((aIMCTX, 1, "i_flood_cfill(im %p, seed(" i_DFp "), dcol %p, border %p)",
2067           im, i_DFcp(seedx, seedy), dcol, border));
2068
2069   im_clear_error(aIMCTX);
2070   if (seedx < 0 || seedx >= im->xsize ||
2071       seedy < 0 || seedy >= im->ysize) {
2072     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
2073     return 0;
2074   }
2075
2076   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2077                          border, i_ccomp_border);
2078
2079   for(y=bymin;y<=bymax;y++)
2080     for(x=bxmin;x<=bxmax;x++)
2081       if (btm_test(btm,x,y))
2082         i_ppix(im,x,y,dcol);
2083   btm_destroy(btm);
2084   return 1;
2085 }
2086
2087 /*
2088 =item i_flood_cfill_border(C<im>, C<seedx>, C<seedy>, C<fill>, C<border>)
2089
2090 =category Drawing
2091 =synopsis i_flood_cfill_border(im, 50, 50, fill, border);
2092
2093 Flood fills the 4-connected region starting from the point (C<seedx>,
2094 C<seedy>) with C<fill>, the fill stops when it reaches pixels of color
2095 C<border>.
2096
2097 Returns false if (C<seedx>, C<seedy>) are outside the image.
2098
2099 =cut
2100 */
2101
2102 undef_int
2103 i_flood_cfill_border(i_img *im, i_img_dim seedx, i_img_dim seedy, i_fill_t *fill,
2104                      const i_color *border) {
2105   i_img_dim bxmin, bxmax, bymin, bymax;
2106   struct i_bitmap *btm;
2107   dIMCTXim(im);
2108
2109   im_log((aIMCTX, 1, "i_flood_cfill_border(im %p, seed(" i_DFp "), fill %p, border %p)",
2110           im, i_DFcp(seedx, seedy), fill, border));
2111
2112   im_clear_error(aIMCTX);
2113
2114   if (seedx < 0 || seedx >= im->xsize ||
2115       seedy < 0 || seedy >= im->ysize) {
2116     im_push_error(aIMCTX, 0, "i_flood_cfill_border: Seed pixel outside of image");
2117     return 0;
2118   }
2119
2120   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2121                          border, i_ccomp_border);
2122
2123   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
2124
2125   btm_destroy(btm);
2126
2127   return 1;
2128 }
2129
2130 static void
2131 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm,
2132                i_img_dim bxmin, i_img_dim bxmax, i_img_dim bymin, i_img_dim bymax) {
2133   i_img_dim x, y;
2134   i_img_dim start;
2135
2136   i_render r;
2137
2138   i_render_init(&r, im, bxmax - bxmin + 1);
2139
2140   for(y=bymin; y<=bymax; y++) {
2141     x = bxmin;
2142     while (x <= bxmax) {
2143       while (x <= bxmax && !btm_test(btm, x, y)) {
2144         ++x;
2145       }
2146       if (btm_test(btm, x, y)) {
2147         start = x;
2148         while (x <= bxmax && btm_test(btm, x, y)) {
2149           ++x;
2150         }
2151         i_render_fill(&r, start, y, x-start, NULL, fill);
2152       }
2153     }
2154   }
2155   i_render_done(&r);
2156 }
2157
2158 /*
2159 =back
2160
2161 =cut
2162 */