draw.c

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