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 static void
   9 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm,
  10                int bxmin, int bxmax, int bymin, int bymax);
  11
  12 void
  13 i_mmarray_cr(i_mmarray *ar,int l) {
  14   int i;
  15   int alloc_size;
  16
  17   ar->lines=l;
  18   alloc_size = sizeof(minmax) * l;
  19   /* check for overflow */
  20   if (alloc_size / l != sizeof(minmax)) {
  21     fprintf(stderr, "overflow calculating memory allocation");
  22     exit(3);
  23   }
  24   ar->data=mymalloc(alloc_size); /* checked 5jul05 tonyc */
  25   for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
  26 }
  27
  28 void
  29 i_mmarray_dst(i_mmarray *ar) {
  30   ar->lines=0;
  31   if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
  32 }
  33
  34 void
  35 i_mmarray_add(i_mmarray *ar,int x,int y) {
  36   if (y>-1 && y<ar->lines)
  37     {
  38       if (x<ar->data[y].min) ar->data[y].min=x;
  39       if (x>ar->data[y].max) ar->data[y].max=x;
  40     }
  41 }
  42
  43 int
  44 i_mmarray_gmin(i_mmarray *ar,int y) {
  45   if (y>-1 && y<ar->lines) return ar->data[y].min;
  46   else return -1;
  47 }
  48
  49 int
  50 i_mmarray_getm(i_mmarray *ar,int y) {
  51   if (y>-1 && y<ar->lines) return ar->data[y].max;
  52   else return MAXINT;
  53 }
  54
  55 void
  56 i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
  57   int i,x;
  58   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);
  59 }
  60
  61 static
  62 void
  63 i_arcdraw(int x1, int y1, int x2, int y2, i_mmarray *ar) {
  64   double alpha;
  65   double dsec;
  66   int temp;
  67   alpha=(double)(y2-y1)/(double)(x2-x1);
  68   if (fabs(alpha) <= 1)
  69     {
  70       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
  71       dsec=y1;
  72       while(x1<=x2)
  73         {
  74           i_mmarray_add(ar,x1,(int)(dsec+0.5));
  75           dsec+=alpha;
  76           x1++;
  77         }
  78     }
  79   else
  80     {
  81       alpha=1/alpha;
  82       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
  83       dsec=x1;
  84       while(y1<=y2)
  85         {
  86           i_mmarray_add(ar,(int)(dsec+0.5),y1);
  87           dsec+=alpha;
  88           y1++;
  89         }
  90     }
  91 }
  92
  93 void
  94 i_mmarray_info(i_mmarray *ar) {
  95   int i;
  96   for(i=0;i<ar->lines;i++)
  97   if (ar->data[i].max!=-1) printf("line %d: min=%d, max=%d.\n",i,ar->data[i].min,ar->data[i].max);
  98 }
  99
 100 static void
 101 i_arc_minmax(i_int_hlines *hlines,int x,int y,float rad,float d1,float d2) {
 102   i_mmarray dot;
 103   float f,fx,fy;
 104   int x1,y1;
 105
 106   /*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));*/
 107
 108   i_mmarray_cr(&dot, hlines->limit_y);
 109
 110   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
 111   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
 112   fx=(float)x1; fy=(float)y1;
 113
 114   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 115   i_arcdraw(x, y, x1, y1, &dot);
 116
 117   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
 118   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
 119
 120   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)));
 121
 122   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 123   i_arcdraw(x, y, x1, y1, &dot);
 124
 125   /* render the minmax values onto the hlines */
 126   for (y = 0; y < dot.lines; y++) {
 127     if (dot.data[y].max!=-1) {
 128       int minx, width;
 129       minx = dot.data[y].min;
 130       width = dot.data[y].max - dot.data[y].min + 1;
 131       i_int_hlines_add(hlines, y, minx, width);
 132     }
 133   }
 134
 135   /*  dot.info(); */
 136   i_mmarray_dst(&dot);
 137 }
 138
 139 static void
 140 i_arc_hlines(i_int_hlines *hlines,int x,int y,float rad,float d1,float d2) {
 141   if (d1 <= d2) {
 142     i_arc_minmax(hlines, x, y, rad, d1, d2);
 143   }
 144   else {
 145     i_arc_minmax(hlines, x, y, rad, d1, 360);
 146     i_arc_minmax(hlines, x, y, rad, 0, d2);
 147   }
 148 }
 149
 150 /*
 151 =item i_arc(im, x, y, rad, d1, d2, color)
 152
 153 =category Drawing
 154 =synopsis i_arc(im, 50, 50, 20, 45, 135, &color);
 155
 156 Fills an arc centered at (x,y) with radius I<rad> covering the range
 157 of angles in degrees from d1 to d2, with the color.
 158
 159 =cut
 160 */
 161
 162 void
 163 i_arc(i_img *im,int x,int y,float rad,float d1,float d2,const i_color *val) {
 164   i_int_hlines hlines;
 165
 166   i_int_init_hlines_img(&hlines, im);
 167
 168   i_arc_hlines(&hlines, x, y, rad, d1, d2);
 169
 170   i_int_hlines_fill_color(im, &hlines, val);
 171
 172   i_int_hlines_destroy(&hlines);
 173 }
 174
 175 /*
 176 =item i_arc_cfill(im, x, y, rad, d1, d2, fill)
 177
 178 =category Drawing
 179 =synopsis i_arc_cfill(im, 50, 50, 35, 90, 135, fill);
 180
 181 Fills an arc centered at (x,y) with radius I<rad> covering the range
 182 of angles in degrees from d1 to d2, with the fill object.
 183
 184 =cut
 185 */
 186
 187 #define MIN_CIRCLE_STEPS 8
 188 #define MAX_CIRCLE_STEPS 360
 189
 190 void
 191 i_arc_cfill(i_img *im,int x,int y,float rad,float d1,float d2,i_fill_t *fill) {
 192   i_int_hlines hlines;
 193
 194   i_int_init_hlines_img(&hlines, im);
 195
 196   i_arc_hlines(&hlines, x, y, rad, d1, d2);
 197
 198   i_int_hlines_fill_fill(im, &hlines, fill);
 199
 200   i_int_hlines_destroy(&hlines);
 201 }
 202
 203 static void
 204 arc_poly(int *count, double **xvals, double **yvals,
 205          double x, double y, double rad, double d1, double d2) {
 206   double d1_rad, d2_rad;
 207   double circum;
 208   int steps, point_count;
 209   double angle_inc;
 210
 211   /* normalize the angles */
 212   d1 = fmod(d1, 360);
 213   if (d1 == 0) {
 214     if (d2 >= 360) { /* default is 361 */
 215       d2 = 360;
 216     }
 217     else {
 218       d2 = fmod(d2, 360);
 219       if (d2 < d1)
 220         d2 += 360;
 221     }
 222   }
 223   else {
 224     d2 = fmod(d2, 360);
 225     if (d2 < d1)
 226       d2 += 360;
 227   }
 228   d1_rad = d1 * PI / 180;
 229   d2_rad = d2 * PI / 180;
 230
 231   /* how many segments for the curved part?
 232      we do a maximum of one per degree, with a minimum of 8/circle
 233      we try to aim at having about one segment per 2 pixels
 234      Work it out per circle to get a step size.
 235
 236      I was originally making steps = circum/2 but that looked horrible.
 237
 238      I think there might be an issue in the polygon filler.
 239   */
 240   circum = 2 * PI * rad;
 241   steps = circum;
 242   if (steps > MAX_CIRCLE_STEPS)
 243     steps = MAX_CIRCLE_STEPS;
 244   else if (steps < MIN_CIRCLE_STEPS)
 245     steps = MIN_CIRCLE_STEPS;
 246
 247   angle_inc = 2 * PI / steps;
 248
 249   point_count = steps + 5; /* rough */
 250   /* point_count is always relatively small, so allocation won't overflow */
 251   *xvals = mymalloc(point_count * sizeof(double)); /* checked 17feb2005 tonyc */
 252   *yvals = mymalloc(point_count * sizeof(double)); /* checked 17feb2005 tonyc */
 253
 254   /* from centre to edge at d1 */
 255   (*xvals)[0] = x;
 256   (*yvals)[0] = y;
 257   (*xvals)[1] = x + rad * cos(d1_rad);
 258   (*yvals)[1] = y + rad * sin(d1_rad);
 259   *count = 2;
 260
 261   /* step around the curve */
 262   while (d1_rad < d2_rad) {
 263     (*xvals)[*count] = x + rad * cos(d1_rad);
 264     (*yvals)[*count] = y + rad * sin(d1_rad);
 265     ++*count;
 266     d1_rad += angle_inc;
 267   }
 268
 269   /* finish off the curve */
 270   (*xvals)[*count] = x + rad * cos(d2_rad);
 271   (*yvals)[*count] = y + rad * sin(d2_rad);
 272   ++*count;
 273 }
 274
 275 /*
 276 =item i_arc_aa(im, x, y, rad, d1, d2, color)
 277
 278 =category Drawing
 279 =synopsis i_arc_aa(im, 50, 50, 35, 90, 135, &color);
 280
 281 Antialias fills an arc centered at (x,y) with radius I<rad> covering
 282 the range of angles in degrees from d1 to d2, with the color.
 283
 284 =cut
 285 */
 286
 287 void
 288 i_arc_aa(i_img *im, double x, double y, double rad, double d1, double d2,
 289          const i_color *val) {
 290   double *xvals, *yvals;
 291   int count;
 292
 293   arc_poly(&count, &xvals, &yvals, x, y, rad, d1, d2);
 294
 295   i_poly_aa(im, count, xvals, yvals, val);
 296
 297   myfree(xvals);
 298   myfree(yvals);
 299 }
 300
 301 /*
 302 =item i_arc_aa_cfill(im, x, y, rad, d1, d2, fill)
 303
 304 =category Drawing
 305 =synopsis i_arc_aa_cfill(im, 50, 50, 35, 90, 135, fill);
 306
 307 Antialias fills an arc centered at (x,y) with radius I<rad> covering
 308 the range of angles in degrees from d1 to d2, with the fill object.
 309
 310 =cut
 311 */
 312
 313 void
 314 i_arc_aa_cfill(i_img *im, double x, double y, double rad, double d1, double d2,
 315                i_fill_t *fill) {
 316   double *xvals, *yvals;
 317   int count;
 318
 319   arc_poly(&count, &xvals, &yvals, x, y, rad, d1, d2);
 320
 321   i_poly_aa_cfill(im, count, xvals, yvals, fill);
 322
 323   myfree(xvals);
 324   myfree(yvals);
 325 }
 326
 327 /* Temporary AA HACK */
 328
 329
 330 typedef int frac;
 331 static  frac float_to_frac(float x) { return (frac)(0.5+x*16.0); }
 332
 333 static
 334 void
 335 polar_to_plane(float cx, float cy, float angle, float radius, frac *x, frac *y) {
 336   *x = float_to_frac(cx+radius*cos(angle));
 337   *y = float_to_frac(cy+radius*sin(angle));
 338 }
 339
 340 static
 341 void
 342 make_minmax_list(i_mmarray *dot, float x, float y, float radius) {
 343   float angle = 0.0;
 344   float astep = radius>0.1 ? .5/radius : 10;
 345   frac cx, cy, lx, ly, sx, sy;
 346
 347   mm_log((1, "make_minmax_list(dot %p, x %.2f, y %.2f, radius %.2f)\n", dot, x, y, radius));
 348
 349   polar_to_plane(x, y, angle, radius, &sx, &sy);
 350
 351   for(angle = 0.0; angle<361; angle +=astep) {
 352     lx = sx; ly = sy;
 353     polar_to_plane(x, y, angle, radius, &cx, &cy);
 354     sx = cx; sy = cy;
 355
 356     if (fabs(cx-lx) > fabs(cy-ly)) {
 357       int ccx, ccy;
 358       if (lx>cx) {
 359         ccx = lx; lx = cx; cx = ccx;
 360         ccy = ly; ly = cy; cy = ccy;
 361       }
 362
 363       for(ccx=lx; ccx<=cx; ccx++) {
 364         ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
 365         i_mmarray_add(dot, ccx, ccy);
 366       }
 367     } else {
 368       int ccx, ccy;
 369
 370       if (ly>cy) {
 371         ccy = ly; ly = cy; cy = ccy;
 372         ccx = lx; lx = cx; cx = ccx;
 373       }
 374
 375       for(ccy=ly; ccy<=cy; ccy++) {
 376         if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
 377         i_mmarray_add(dot, ccx, ccy);
 378       }
 379     }
 380   }
 381 }
 382
 383 /* Get the number of subpixels covered */
 384
 385 static
 386 int
 387 i_pixel_coverage(i_mmarray *dot, int x, int y) {
 388   frac minx = x*16;
 389   frac maxx = minx+15;
 390   frac cy;
 391   int cnt = 0;
 392
 393   for(cy=y*16; cy<(y+1)*16; cy++) {
 394     frac tmin = dot->data[cy].min;
 395     frac tmax = dot->data[cy].max;
 396
 397     if (tmax == -1 || tmin > maxx || tmax < minx) continue;
 398
 399     if (tmin < minx) tmin = minx;
 400     if (tmax > maxx) tmax = maxx;
 401
 402     cnt+=1+tmax-tmin;
 403   }
 404   return cnt;
 405 }
 406
 407 /*
 408 =item i_circle_aa(im, x, y, rad, color)
 409
 410 =category Drawing
 411 =synopsis i_circle_aa(im, 50, 50, 45, &color);
 412
 413 Antialias fills a circle centered at (x,y) for radius I<rad> with
 414 color.
 415
 416 =cut
 417 */
 418 void
 419 i_circle_aa(i_img *im, float x, float y, float rad, const i_color *val) {
 420   i_mmarray dot;
 421   i_color temp;
 422   int ly;
 423
 424   mm_log((1, "i_circle_aa(im %p, x %d, y %d, rad %.2f, val %p)\n", im, x, y, rad, val));
 425
 426   i_mmarray_cr(&dot,16*im->ysize);
 427   make_minmax_list(&dot, x, y, rad);
 428
 429   for(ly = 0; ly<im->ysize; ly++) {
 430     int ix, cy, minx = INT_MAX, maxx = INT_MIN;
 431
 432     /* Find the left/rightmost set subpixels */
 433     for(cy = 0; cy<16; cy++) {
 434       frac tmin = dot.data[ly*16+cy].min;
 435       frac tmax = dot.data[ly*16+cy].max;
 436       if (tmax == -1) continue;
 437
 438       if (minx > tmin) minx = tmin;
 439       if (maxx < tmax) maxx = tmax;
 440     }
 441
 442     if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
 443
 444     minx /= 16;
 445     maxx /= 16;
 446     for(ix=minx; ix<=maxx; ix++) {
 447       int cnt = i_pixel_coverage(&dot, ix, ly);
 448       if (cnt>255) cnt = 255;
 449       if (cnt) { /* should never be true */
 450         int ch;
 451         float ratio = (float)cnt/255.0;
 452         i_gpix(im, ix, ly, &temp);
 453         for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
 454         i_ppix(im, ix, ly, &temp);
 455       }
 456     }
 457   }
 458   i_mmarray_dst(&dot);
 459 }
 460
 461 /*
 462 =item i_box(im, x1, y1, x2, y2, color)
 463
 464 =category Drawing
 465 =synopsis i_box(im, 0, 0, im->xsize-1, im->ysize-1, &color).
 466
 467 Outlines the box from (x1,y1) to (x2,y2) inclusive with I<color>.
 468
 469 =cut
 470 */
 471
 472 void
 473 i_box(i_img *im,int x1,int y1,int x2,int y2,const i_color *val) {
 474   int x,y;
 475   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));
 476   for(x=x1;x<x2+1;x++) {
 477     i_ppix(im,x,y1,val);
 478     i_ppix(im,x,y2,val);
 479   }
 480   for(y=y1;y<y2+1;y++) {
 481     i_ppix(im,x1,y,val);
 482     i_ppix(im,x2,y,val);
 483   }
 484 }
 485
 486 /*
 487 =item i_box_filled(im, x1, y1, x2, y2, color)
 488
 489 =category Drawing
 490 =synopsis i_box_filled(im, 0, 0, im->xsize-1, im->ysize-1, &color);
 491
 492 Fills the box from (x1,y1) to (x2,y2) inclusive with color.
 493
 494 =cut
 495 */
 496
 497 void
 498 i_box_filled(i_img *im,int x1,int y1,int x2,int y2, const i_color *val) {
 499   int x,y;
 500   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));
 501   for(x=x1;x<x2+1;x++) for (y=y1;y<y2+1;y++) i_ppix(im,x,y,val);
 502 }
 503
 504 /*
 505 =item i_box_cfill(im, x1, y1, x2, y2, fill)
 506
 507 =category Drawing
 508 =synopsis i_box_cfill(im, 0, 0, im->xsize-1, im->ysize-1, fill);
 509
 510 Fills the box from (x1,y1) to (x2,y2) inclusive with fill.
 511
 512 =cut
 513 */
 514
 515 void
 516 i_box_cfill(i_img *im,int x1,int y1,int x2,int y2,i_fill_t *fill) {
 517   i_render r;
 518   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));
 519
 520   ++x2;
 521   if (x1 < 0)
 522     x1 = 0;
 523   if (y1 < 0)
 524     y1 = 0;
 525   if (x2 > im->xsize)
 526     x2 = im->xsize;
 527   if (y2 >= im->ysize)
 528     y2 = im->ysize-1;
 529   if (x1 >= x2 || y1 > y2)
 530     return;
 531
 532   i_render_init(&r, im, x2-x1);
 533   while (y1 <= y2) {
 534     i_render_fill(&r, x1, y1, x2-x1, NULL, fill);
 535     ++y1;
 536   }
 537   i_render_done(&r);
 538 }
 539
 540 /*
 541 =item i_line(im, x1, y1, x2, y2, val, endp)
 542
 543 =category Drawing
 544
 545 Draw a line to image using bresenhams linedrawing algorithm
 546
 547    im   - image to draw to
 548    x1   - starting x coordinate
 549    y1   - starting x coordinate
 550    x2   - starting x coordinate
 551    y2   - starting x coordinate
 552    val  - color to write to image
 553    endp - endpoint flag (boolean)
 554
 555 =cut
 556 */
 557
 558 void
 559 i_line(i_img *im, int x1, int y1, int x2, int y2, const i_color *val, int endp) {
 560   int x, y;
 561   int dx, dy;
 562   int p;
 563
 564   dx = x2 - x1;
 565   dy = y2 - y1;
 566
 567
 568   /* choose variable to iterate on */
 569   if (abs(dx)>abs(dy)) {
 570     int dx2, dy2, cpy;
 571
 572     /* sort by x */
 573     if (x1 > x2) {
 574       int t;
 575       t = x1; x1 = x2; x2 = t;
 576       t = y1; y1 = y2; y2 = t;
 577     }
 578
 579     dx = abs(dx);
 580     dx2 = dx*2;
 581     dy = y2 - y1;
 582
 583     if (dy<0) {
 584       dy = -dy;
 585       cpy = -1;
 586     } else {
 587       cpy = 1;
 588     }
 589     dy2 = dy*2;
 590     p = dy2 - dx;
 591
 592
 593     y = y1;
 594     for(x=x1; x<x2-1; x++) {
 595       if (p<0) {
 596         p += dy2;
 597       } else {
 598         y += cpy;
 599         p += dy2-dx2;
 600       }
 601       i_ppix(im, x+1, y, val);
 602     }
 603   } else {
 604     int dy2, dx2, cpx;
 605
 606     /* sort bx y */
 607     if (y1 > y2) {
 608       int t;
 609       t = x1; x1 = x2; x2 = t;
 610       t = y1; y1 = y2; y2 = t;
 611     }
 612
 613     dy = abs(dy);
 614     dx = x2 - x1;
 615     dy2 = dy*2;
 616
 617     if (dx<0) {
 618       dx = -dx;
 619       cpx = -1;
 620     } else {
 621       cpx = 1;
 622     }
 623     dx2 = dx*2;
 624     p = dx2 - dy;
 625
 626     x = x1;
 627
 628     for(y=y1; y<y2-1; y++) {
 629       if (p<0) {
 630         p  += dx2;
 631       } else {
 632         x += cpx;
 633         p += dx2-dy2;
 634       }
 635       i_ppix(im, x, y+1, val);
 636     }
 637   }
 638   if (endp) {
 639     i_ppix(im, x1, y1, val);
 640     i_ppix(im, x2, y2, val);
 641   } else {
 642     if (x1 != x2 || y1 != y2)
 643       i_ppix(im, x1, y1, val);
 644   }
 645 }
 646
 647
 648 void
 649 i_line_dda(i_img *im, int x1, int y1, int x2, int y2, i_color *val) {
 650
 651   float dy;
 652   int x;
 653
 654   for(x=x1; x<=x2; x++) {
 655     dy = y1+ (x-x1)/(float)(x2-x1)*(y2-y1);
 656     i_ppix(im, x, (int)(dy+0.5), val);
 657   }
 658 }
 659
 660 /*
 661 =item i_line_aa(im, x1, x2, y1, y2, color, endp)
 662
 663 =category Drawing
 664
 665 Antialias draws a line from (x1,y1) to (x2, y2) in color.
 666
 667 The point (x2, y2) is drawn only if endp is set.
 668
 669 =cut
 670 */
 671
 672 void
 673 i_line_aa(i_img *im, int x1, int y1, int x2, int y2, const i_color *val, int endp) {
 674   int x, y;
 675   int dx, dy;
 676   int p;
 677
 678   dx = x2 - x1;
 679   dy = y2 - y1;
 680
 681   /* choose variable to iterate on */
 682   if (abs(dx)>abs(dy)) {
 683     int dx2, dy2, cpy;
 684
 685     /* sort by x */
 686     if (x1 > x2) {
 687       int t;
 688       t = x1; x1 = x2; x2 = t;
 689       t = y1; y1 = y2; y2 = t;
 690     }
 691
 692     dx = abs(dx);
 693     dx2 = dx*2;
 694     dy = y2 - y1;
 695
 696     if (dy<0) {
 697       dy = -dy;
 698       cpy = -1;
 699     } else {
 700       cpy = 1;
 701     }
 702     dy2 = dy*2;
 703     p = dy2 - dx2; /* this has to be like this for AA */
 704
 705     y = y1;
 706
 707     for(x=x1; x<x2-1; x++) {
 708       int ch;
 709       i_color tval;
 710       float t = (dy) ? -(float)(p)/(float)(dx2) : 1;
 711       float t1, t2;
 712
 713       if (t<0) t = 0;
 714       t1 = 1-t;
 715       t2 = t;
 716
 717       i_gpix(im,x+1,y,&tval);
 718       for(ch=0;ch<im->channels;ch++)
 719         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
 720       i_ppix(im,x+1,y,&tval);
 721
 722       i_gpix(im,x+1,y+cpy,&tval);
 723       for(ch=0;ch<im->channels;ch++)
 724         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
 725       i_ppix(im,x+1,y+cpy,&tval);
 726
 727       if (p<0) {
 728         p += dy2;
 729       } else {
 730         y += cpy;
 731         p += dy2-dx2;
 732       }
 733     }
 734   } else {
 735     int dy2, dx2, cpx;
 736
 737     /* sort bx y */
 738     if (y1 > y2) {
 739       int t;
 740       t = x1; x1 = x2; x2 = t;
 741       t = y1; y1 = y2; y2 = t;
 742     }
 743
 744     dy = abs(dy);
 745     dx = x2 - x1;
 746     dy2 = dy*2;
 747
 748     if (dx<0) {
 749       dx = -dx;
 750       cpx = -1;
 751     } else {
 752       cpx = 1;
 753     }
 754     dx2 = dx*2;
 755     p = dx2 - dy2; /* this has to be like this for AA */
 756
 757     x = x1;
 758
 759     for(y=y1; y<y2-1; y++) {
 760       int ch;
 761       i_color tval;
 762       float t = (dx) ? -(float)(p)/(float)(dy2) : 1;
 763       float t1, t2;
 764
 765       if (t<0) t = 0;
 766       t1 = 1-t;
 767       t2 = t;
 768
 769       i_gpix(im,x,y+1,&tval);
 770       for(ch=0;ch<im->channels;ch++)
 771         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
 772       i_ppix(im,x,y+1,&tval);
 773
 774       i_gpix(im,x+cpx,y+1,&tval);
 775       for(ch=0;ch<im->channels;ch++)
 776         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
 777       i_ppix(im,x+cpx,y+1,&tval);
 778
 779       if (p<0) {
 780         p  += dx2;
 781       } else {
 782         x += cpx;
 783         p += dx2-dy2;
 784       }
 785     }
 786   }
 787
 788
 789   if (endp) {
 790     i_ppix(im, x1, y1, val);
 791     i_ppix(im, x2, y2, val);
 792   } else {
 793     if (x1 != x2 || y1 != y2)
 794       i_ppix(im, x1, y1, val);
 795   }
 796 }
 797
 798
 799
 800 static double
 801 perm(int n,int k) {
 802   double r;
 803   int i;
 804   r=1;
 805   for(i=k+1;i<=n;i++) r*=i;
 806   for(i=1;i<=(n-k);i++) r/=i;
 807   return r;
 808 }
 809
 810
 811 /* Note in calculating t^k*(1-t)^(n-k)
 812    we can start by using t^0=1 so this simplifies to
 813    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
 814    to get a new level - this may lead to errors who knows lets test it */
 815
 816 void
 817 i_bezier_multi(i_img *im,int l,const double *x,const double *y, const i_color *val) {
 818   double *bzcoef;
 819   double t,cx,cy;
 820   int k,i;
 821   int lx = 0,ly = 0;
 822   int n=l-1;
 823   double itr,ccoef;
 824
 825   /* this is the same size as the x and y arrays, so shouldn't overflow */
 826   bzcoef=mymalloc(sizeof(double)*l); /* checked 5jul05 tonyc */
 827   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
 828   ICL_info(val);
 829
 830
 831   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
 832   i=0;
 833   for(t=0;t<=1;t+=0.005) {
 834     cx=cy=0;
 835     itr=t/(1-t);
 836     ccoef=pow(1-t,n);
 837     for(k=0;k<l;k++) {
 838       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
 839               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
 840
 841       cx+=bzcoef[k]*x[k]*ccoef;
 842       cy+=bzcoef[k]*y[k]*ccoef;
 843       ccoef*=itr;
 844     }
 845     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
 846     if (i++) {
 847       i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val, 1);
 848     }
 849       /*     i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
 850     lx=(int)(0.5+cx);
 851     ly=(int)(0.5+cy);
 852   }
 853   ICL_info(val);
 854   myfree(bzcoef);
 855 }
 856
 857 /* Flood fill
 858
 859    REF: Graphics Gems I. page 282+
 860
 861 */
 862
 863 /* This should be moved into a seperate file? */
 864
 865 /* This is the truncation used:
 866
 867    a double is multiplied by 16 and then truncated.
 868    This means that 0 -> 0
 869    So a triangle of (0,0) (10,10) (10,0) Will look like it's
 870    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
 871
 872 */
 873
 874
 875 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
 876    graphics gems I */
 877
 878 /*
 879 struct stc {
 880   int mylx,myrx;
 881   int dadlx,dadrx;
 882   int myy;
 883   int mydirection;
 884 };
 885
 886 Not used code???
 887 */
 888
 889
 890 struct stack_element {
 891   int myLx,myRx;
 892   int dadLx,dadRx;
 893   int myY;
 894   int myDirection;
 895 };
 896
 897
 898 /* create the link data to put push onto the stack */
 899
 900 static
 901 struct stack_element*
 902 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
 903   struct stack_element *ste;
 904   ste              = mymalloc(sizeof(struct stack_element)); /* checked 5jul05 tonyc */
 905   ste->myLx        = left;
 906   ste->myRx        = right;
 907   ste->dadLx       = dadl;
 908   ste->dadRx       = dadr;
 909   ste->myY         = y;
 910   ste->myDirection = dir;
 911   return ste;
 912 }
 913
 914 /* i_ccomp compares two colors and gives true if they are the same */
 915
 916 typedef int (*ff_cmpfunc)(i_color const *c1, i_color const *c2, int channels);
 917
 918 static int
 919 i_ccomp_normal(i_color const *val1, i_color const *val2, int ch) {
 920   int i;
 921   for(i = 0; i < ch; i++)
 922     if (val1->channel[i] !=val2->channel[i])
 923       return 0;
 924   return 1;
 925 }
 926
 927 static int
 928 i_ccomp_border(i_color const *val1, i_color const *val2, int ch) {
 929   int i;
 930   for(i = 0; i < ch; i++)
 931     if (val1->channel[i] !=val2->channel[i])
 932       return 1;
 933   return 0;
 934 }
 935
 936 static int
 937 i_lspan(i_img *im, int seedx, int seedy, i_color const *val, ff_cmpfunc cmpfunc) {
 938   i_color cval;
 939   while(1) {
 940     if (seedx-1 < 0) break;
 941     i_gpix(im,seedx-1,seedy,&cval);
 942     if (!cmpfunc(val,&cval,im->channels))
 943       break;
 944     seedx--;
 945   }
 946   return seedx;
 947 }
 948
 949 static int
 950 i_rspan(i_img *im, int seedx, int seedy, i_color const *val, ff_cmpfunc cmpfunc) {
 951   i_color cval;
 952   while(1) {
 953     if (seedx+1 > im->xsize-1) break;
 954     i_gpix(im,seedx+1,seedy,&cval);
 955     if (!cmpfunc(val,&cval,im->channels)) break;
 956     seedx++;
 957   }
 958   return seedx;
 959 }
 960
 961 /* Macro to create a link and push on to the list */
 962
 963 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
 964   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
 965   llist_push(st,&s);                                             \
 966 } while (0)
 967
 968 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
 969 /* No overflow check! */
 970
 971 #define ST_POP() do {         \
 972   struct stack_element *s;    \
 973   llist_pop(st,&s);           \
 974   lx        = s->myLx;        \
 975   rx        = s->myRx;        \
 976   dadLx     = s->dadLx;       \
 977   dadRx     = s->dadRx;       \
 978   y         = s->myY;         \
 979   direction = s->myDirection; \
 980   myfree(s);                  \
 981 } while (0)
 982
 983 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
 984   int pushrx = rx+1;                                              \
 985   int pushlx = lx-1;                                              \
 986   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
 987   if (rx > dadRx)                                                 \
 988     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
 989   if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
 990 } while (0)
 991
 992 #define SET(x,y) btm_set(btm,x,y)
 993
 994 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
 995 #define INSIDE(x,y, seed) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
 996
 997
 998
 999 /* The function that does all the real work */
1000
1001 static struct i_bitmap *
1002 i_flood_fill_low(i_img *im,int seedx,int seedy,
1003                  int *bxminp, int *bxmaxp, int *byminp, int *bymaxp,
1004                  i_color const *seed, ff_cmpfunc cmpfunc) {
1005   int ltx, rtx;
1006   int tx = 0;
1007
1008   int bxmin = seedx;
1009   int bxmax = seedx;
1010   int bymin = seedy;
1011   int bymax = seedy;
1012
1013   struct llist *st;
1014   struct i_bitmap *btm;
1015
1016   int channels,xsize,ysize;
1017   i_color cval;
1018
1019   channels = im->channels;
1020   xsize    = im->xsize;
1021   ysize    = im->ysize;
1022
1023   btm = btm_new(xsize, ysize);
1024   st  = llist_new(100, sizeof(struct stack_element*));
1025
1026   /* Find the starting span and fill it */
1027   ltx = i_lspan(im, seedx, seedy, seed, cmpfunc);
1028   rtx = i_rspan(im, seedx, seedy, seed, cmpfunc);
1029   for(tx=ltx; tx<=rtx; tx++) SET(tx, seedy);
1030
1031   ST_PUSH(ltx, rtx, ltx, rtx, seedy+1,  1);
1032   ST_PUSH(ltx, rtx, ltx, rtx, seedy-1, -1);
1033
1034   while(st->count) {
1035     /* Stack variables */
1036     int lx,rx;
1037     int dadLx,dadRx;
1038     int y;
1039     int direction;
1040
1041     int x;
1042     int wasIn=0;
1043
1044     ST_POP(); /* sets lx, rx, dadLx, dadRx, y, direction */
1045
1046
1047     if (y<0 || y>ysize-1) continue;
1048     if (bymin > y) bymin=y; /* in the worst case an extra line */
1049     if (bymax < y) bymax=y;
1050
1051
1052     x = lx+1;
1053     if ( lx >= 0 && (wasIn = INSIDE(lx, y, seed)) ) {
1054       SET(lx, y);
1055       lx--;
1056       while(INSIDE(lx, y, seed) && lx > 0) {
1057         SET(lx,y);
1058         lx--;
1059       }
1060     }
1061
1062     if (bxmin > lx) bxmin = lx;
1063     while(x <= xsize-1) {
1064       /*  printf("x=%d\n",x); */
1065       if (wasIn) {
1066
1067         if (INSIDE(x, y, seed)) {
1068           /* case 1: was inside, am still inside */
1069           SET(x,y);
1070         } else {
1071           /* case 2: was inside, am no longer inside: just found the
1072              right edge of a span */
1073           ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1074
1075           if (bxmax < x) bxmax = x;
1076           wasIn=0;
1077         }
1078       } else {
1079         if (x > rx) goto EXT;
1080         if (INSIDE(x, y, seed)) {
1081           SET(x, y);
1082           /* case 3: Wasn't inside, am now: just found the start of a new run */
1083           wasIn = 1;
1084             lx = x;
1085         } else {
1086           /* case 4: Wasn't inside, still isn't */
1087         }
1088       }
1089       x++;
1090     }
1091   EXT: /* out of loop */
1092     if (wasIn) {
1093       /* hit an edge of the frame buffer while inside a run */
1094       ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1095       if (bxmax < x) bxmax = x;
1096     }
1097   }
1098
1099   llist_destroy(st);
1100
1101   *bxminp = bxmin;
1102   *bxmaxp = bxmax;
1103   *byminp = bymin;
1104   *bymaxp = bymax;
1105
1106   return btm;
1107 }
1108
1109 /*
1110 =item i_flood_fill(im, seedx, seedy, color)
1111
1112 =category Drawing
1113 =synopsis i_flood_fill(im, 50, 50, &color);
1114
1115 Flood fills the 4-connected region starting from the point (seedx,
1116 seedy) with I<color>.
1117
1118 Returns false if (seedx, seedy) are outside the image.
1119
1120 =cut
1121 */
1122
1123 undef_int
1124 i_flood_fill(i_img *im, int seedx, int seedy, const i_color *dcol) {
1125   int bxmin, bxmax, bymin, bymax;
1126   struct i_bitmap *btm;
1127   int x, y;
1128   i_color val;
1129
1130   i_clear_error();
1131   if (seedx < 0 || seedx >= im->xsize ||
1132       seedy < 0 || seedy >= im->ysize) {
1133     i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
1134     return 0;
1135   }
1136
1137   /* Get the reference color */
1138   i_gpix(im, seedx, seedy, &val);
1139
1140   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1141                          &val, i_ccomp_normal);
1142
1143   for(y=bymin;y<=bymax;y++)
1144     for(x=bxmin;x<=bxmax;x++)
1145       if (btm_test(btm,x,y))
1146         i_ppix(im,x,y,dcol);
1147   btm_destroy(btm);
1148   return 1;
1149 }
1150
1151 /*
1152 =item i_flood_cfill(im, seedx, seedy, fill)
1153
1154 =category Drawing
1155 =synopsis i_flood_cfill(im, 50, 50, fill);
1156
1157 Flood fills the 4-connected region starting from the point (seedx,
1158 seedy) with I<fill>.
1159
1160 Returns false if (seedx, seedy) are outside the image.
1161
1162 =cut
1163 */
1164
1165 undef_int
1166 i_flood_cfill(i_img *im, int seedx, int seedy, i_fill_t *fill) {
1167   int bxmin, bxmax, bymin, bymax;
1168   struct i_bitmap *btm;
1169   i_color val;
1170
1171   i_clear_error();
1172
1173   if (seedx < 0 || seedx >= im->xsize ||
1174       seedy < 0 || seedy >= im->ysize) {
1175     i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
1176     return 0;
1177   }
1178
1179   /* Get the reference color */
1180   i_gpix(im, seedx, seedy, &val);
1181
1182   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1183                          &val, i_ccomp_normal);
1184
1185   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
1186
1187   btm_destroy(btm);
1188   return 1;
1189 }
1190
1191 /*
1192 =item i_flood_fill_border(im, seedx, seedy, color, border)
1193
1194 =category Drawing
1195 =synopsis i_flood_fill_border(im, 50, 50, &color, &border);
1196
1197 Flood fills the 4-connected region starting from the point (seedx,
1198 seedy) with I<color>, fill stops when the fill reaches a pixels with
1199 color I<border>.
1200
1201 Returns false if (seedx, seedy) are outside the image.
1202
1203 =cut
1204 */
1205
1206 undef_int
1207 i_flood_fill_border(i_img *im, int seedx, int seedy, const i_color *dcol,
1208                     const i_color *border) {
1209   int bxmin, bxmax, bymin, bymax;
1210   struct i_bitmap *btm;
1211   int x, y;
1212
1213   i_clear_error();
1214   if (seedx < 0 || seedx >= im->xsize ||
1215       seedy < 0 || seedy >= im->ysize) {
1216     i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
1217     return 0;
1218   }
1219
1220   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1221                          border, i_ccomp_border);
1222
1223   for(y=bymin;y<=bymax;y++)
1224     for(x=bxmin;x<=bxmax;x++)
1225       if (btm_test(btm,x,y))
1226         i_ppix(im,x,y,dcol);
1227   btm_destroy(btm);
1228   return 1;
1229 }
1230
1231 /*
1232 =item i_flood_cfill_border(im, seedx, seedy, fill, border)
1233
1234 =category Drawing
1235 =synopsis i_flood_cfill_border(im, 50, 50, fill, border);
1236
1237 Flood fills the 4-connected region starting from the point (seedx,
1238 seedy) with I<fill>, the fill stops when it reaches pixels of color
1239 I<border>.
1240
1241 Returns false if (seedx, seedy) are outside the image.
1242
1243 =cut
1244 */
1245
1246 undef_int
1247 i_flood_cfill_border(i_img *im, int seedx, int seedy, i_fill_t *fill,
1248                      const i_color *border) {
1249   int bxmin, bxmax, bymin, bymax;
1250   struct i_bitmap *btm;
1251
1252   i_clear_error();
1253
1254   if (seedx < 0 || seedx >= im->xsize ||
1255       seedy < 0 || seedy >= im->ysize) {
1256     i_push_error(0, "i_flood_cfill_border: Seed pixel outside of image");
1257     return 0;
1258   }
1259
1260   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1261                          border, i_ccomp_border);
1262
1263   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
1264
1265   btm_destroy(btm);
1266
1267   return 1;
1268 }
1269
1270 static void
1271 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm,
1272                int bxmin, int bxmax, int bymin, int bymax) {
1273   int x, y;
1274   int start;
1275
1276   i_render r;
1277
1278   i_render_init(&r, im, bxmax - bxmin + 1);
1279
1280   for(y=bymin; y<=bymax; y++) {
1281     x = bxmin;
1282     while (x <= bxmax) {
1283       while (x <= bxmax && !btm_test(btm, x, y)) {
1284         ++x;
1285       }
1286       if (btm_test(btm, x, y)) {
1287         start = x;
1288         while (x <= bxmax && btm_test(btm, x, y)) {
1289           ++x;
1290         }
1291         i_render_fill(&r, start, y, x-start, NULL, fill);
1292       }
1293     }
1294   }
1295   i_render_done(&r);
1296 }