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