draw.c

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