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