draw.c

   1 #include "image.h"
   2 #include "draw.h"
   3 #include "log.h"
   4
   5 #include <limits.h>
   6
   7 void
   8 i_mmarray_cr(i_mmarray *ar,int l) {
   9   int i;
  10
  11   ar->lines=l;
  12   ar->data=mymalloc(sizeof(minmax)*l);
  13   for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
  14 }
  15
  16 void
  17 i_mmarray_dst(i_mmarray *ar) {
  18   ar->lines=0;
  19   if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
  20 }
  21
  22 void
  23 i_mmarray_add(i_mmarray *ar,int x,int y) {
  24   if (y>-1 && y<ar->lines)
  25     {
  26       if (x<ar->data[y].min) ar->data[y].min=x;
  27       if (x>ar->data[y].max) ar->data[y].max=x;
  28     }
  29 }
  30
  31 int
  32 i_mmarray_gmin(i_mmarray *ar,int y) {
  33   if (y>-1 && y<ar->lines) return ar->data[y].min;
  34   else return -1;
  35 }
  36
  37 int
  38 i_mmarray_getm(i_mmarray *ar,int y) {
  39   if (y>-1 && y<ar->lines) return ar->data[y].max;
  40   else return MAXINT;
  41 }
  42
  43 void
  44 i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
  45   int i,x;
  46   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);
  47 }
  48
  49 void
  50 i_mmarray_render_fill(i_img *im,i_mmarray *ar,i_fill_t *fill) {
  51   int x, w, y;
  52   if (im->bits == i_8_bits && fill->fill_with_color) {
  53     i_color *line = mymalloc(sizeof(i_color) * im->xsize);
  54     i_color *work = NULL;
  55     if (fill->combine)
  56       work = mymalloc(sizeof(i_color) * im->xsize);
  57     for(y=0;y<ar->lines;y++) {
  58       if (ar->data[y].max!=-1) {
  59         x = ar->data[y].min;
  60         w = ar->data[y].max-ar->data[y].min;
  61
  62         if (fill->combine)
  63           i_glin(im, x, x+w, y, line);
  64
  65         (fill->fill_with_color)(fill, x, y, w, im->channels, line, work);
  66         i_plin(im, x, x+w, y, line);
  67       }
  68     }
  69
  70     myfree(line);
  71     if (work)
  72       myfree(work);
  73   }
  74   else {
  75     i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
  76     i_fcolor *work = NULL;
  77     if (fill->combinef)
  78       work = mymalloc(sizeof(i_fcolor) * im->xsize);
  79     for(y=0;y<ar->lines;y++) {
  80       if (ar->data[y].max!=-1) {
  81         x = ar->data[y].min;
  82         w = ar->data[y].max-ar->data[y].min;
  83
  84         if (fill->combinef)
  85           i_glinf(im, x, x+w, y, line);
  86
  87         (fill->fill_with_fcolor)(fill, x, y, w, im->channels, line, work);
  88         i_plinf(im, x, x+w, y, line);
  89       }
  90     }
  91
  92     myfree(line);
  93     if (work)
  94       myfree(work);
  95   }
  96 }
  97
  98
  99 static
 100 void
 101 i_arcdraw(int x1, int y1, int x2, int y2, i_mmarray *ar) {
 102   double alpha;
 103   double dsec;
 104   int temp;
 105   alpha=(double)(y2-y1)/(double)(x2-x1);
 106   if (fabs(alpha)<1)
 107     {
 108       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 109       dsec=y1;
 110       while(x1<x2)
 111         {
 112           dsec+=alpha;
 113           i_mmarray_add(ar,x1,(int)(dsec+0.5));
 114           x1++;
 115         }
 116     }
 117   else
 118     {
 119       alpha=1/alpha;
 120       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 121       dsec=x1;
 122       while(y1<y2)
 123         {
 124           dsec+=alpha;
 125           i_mmarray_add(ar,(int)(dsec+0.5),y1);
 126           y1++;
 127         }
 128     }
 129 }
 130
 131 void
 132 i_mmarray_info(i_mmarray *ar) {
 133   int i;
 134   for(i=0;i<ar->lines;i++)
 135   if (ar->data[i].max!=-1) printf("line %d: min=%d, max=%d.\n",i,ar->data[i].min,ar->data[i].max);
 136 }
 137
 138
 139 void
 140 i_arc(i_img *im,int x,int y,float rad,float d1,float d2,i_color *val) {
 141   i_mmarray dot;
 142   float f,fx,fy;
 143   int x1,y1;
 144
 145   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));
 146
 147   i_mmarray_cr(&dot,im->ysize);
 148
 149   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
 150   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
 151   fx=(float)x1; fy=(float)y1;
 152
 153   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 154   i_arcdraw(x, y, x1, y1, &dot);
 155
 156   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
 157   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
 158
 159   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)));
 160
 161   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 162   i_arcdraw(x, y, x1, y1, &dot);
 163
 164   /*  dot.info(); */
 165   i_mmarray_render(im,&dot,val);
 166   i_mmarray_dst(&dot);
 167 }
 168
 169 void
 170 i_arc_cfill(i_img *im,int x,int y,float rad,float d1,float d2,i_fill_t *fill) {
 171   i_mmarray dot;
 172   float f,fx,fy;
 173   int x1,y1;
 174
 175   mm_log((1,"i_arc_cfill(im* 0x%x,x %d,y %d,rad %.2f,d1 %.2f,d2 %.2f,fill 0x%x)\n",im,x,y,rad,d1,d2,fill));
 176
 177   i_mmarray_cr(&dot,im->ysize);
 178
 179   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
 180   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
 181   fx=(float)x1; fy=(float)y1;
 182
 183   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 184   i_arcdraw(x, y, x1, y1, &dot);
 185
 186   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
 187   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
 188
 189   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)));
 190
 191   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 192   i_arcdraw(x, y, x1, y1, &dot);
 193
 194   /*  dot.info(); */
 195   i_mmarray_render_fill(im,&dot,fill);
 196   i_mmarray_dst(&dot);
 197 }
 198
 199
 200
 201 /* Temporary AA HACK */
 202
 203
 204 typedef int frac;
 205 static  frac float_to_frac(float x) { return (frac)(0.5+x*16.0); }
 206 static   int frac_sub     (frac x)  { return (x%16); }
 207 static   int frac_int     (frac x)  { return (x/16); }
 208 static float frac_to_float(float x) { return (float)x/16.0; }
 209
 210 static
 211 void
 212 polar_to_plane(float cx, float cy, float angle, float radius, frac *x, frac *y) {
 213   *x = float_to_frac(cx+radius*cos(angle));
 214   *y = float_to_frac(cy+radius*sin(angle));
 215 }
 216
 217 static
 218 void
 219 order_pair(frac *x, frac *y) {
 220   frac t = *x;
 221   if (t>*y) {
 222     *x = *y;
 223     *y = t;
 224   }
 225 }
 226
 227
 228
 229
 230 static
 231 void
 232 make_minmax_list(i_mmarray *dot, float x, float y, float radius) {
 233   float angle = 0.0;
 234   float astep = radius>0.1 ? .5/radius : 10;
 235   frac cx, cy, lx, ly, sx, sy;
 236
 237   mm_log((1, "make_minmax_list(dot %p, x %.2f, y %.2f, radius %.2f)\n", dot, x, y, radius));
 238
 239   polar_to_plane(x, y, angle, radius, &sx, &sy);
 240
 241   for(angle = 0.0; angle<361; angle +=astep) {
 242     float alpha;
 243     lx = sx; ly = sy;
 244     polar_to_plane(x, y, angle, radius, &cx, &cy);
 245     sx = cx; sy = cy;
 246
 247     if (fabs(cx-lx) > fabs(cy-ly)) {
 248       int ccx, ccy;
 249       if (lx>cx) {
 250         ccx = lx; lx = cx; cx = ccx;
 251         ccy = ly; ly = cy; cy = ccy;
 252       }
 253
 254       for(ccx=lx; ccx<=cx; ccx++) {
 255         ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
 256         i_mmarray_add(dot, ccx, ccy);
 257       }
 258     } else {
 259       int ccx, ccy;
 260
 261       if (ly>cy) {
 262         ccy = ly; ly = cy; cy = ccy;
 263         ccx = lx; lx = cx; cx = ccx;
 264       }
 265
 266       for(ccy=ly; ccy<=cy; ccy++) {
 267         if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
 268         i_mmarray_add(dot, ccx, ccy);
 269       }
 270     }
 271   }
 272 }
 273
 274 /* Get the number of subpixels covered */
 275
 276 static
 277 int
 278 i_pixel_coverage(i_mmarray *dot, int x, int y) {
 279   frac minx = x*16;
 280   frac maxx = minx+15;
 281   frac cy;
 282   int cnt = 0;
 283
 284   for(cy=y*16; cy<(y+1)*16; cy++) {
 285     frac tmin = dot->data[cy].min;
 286     frac tmax = dot->data[cy].max;
 287
 288     if (tmax == -1 || tmin > maxx || tmax < minx) continue;
 289
 290     if (tmin < minx) tmin = minx;
 291     if (tmax > maxx) tmax = maxx;
 292
 293     cnt+=1+tmax-tmin;
 294   }
 295   return cnt;
 296 }
 297
 298 void
 299 i_circle_aa(i_img *im, float x, float y, float rad, i_color *val) {
 300   i_mmarray dot;
 301   i_color temp;
 302   int ly;
 303
 304   mm_log((1, "i_circle_aa(im %p, x %d, y %d, rad %.2f, val %p)\n", im, x, y, rad, val));
 305
 306   i_mmarray_cr(&dot,16*im->ysize);
 307   make_minmax_list(&dot, x, y, rad);
 308
 309   for(ly = 0; ly<im->ysize; ly++) {
 310     int ix, cy, cnt = 0, minx = INT_MAX, maxx = INT_MIN;
 311
 312     /* Find the left/rightmost set subpixels */
 313     for(cy = 0; cy<16; cy++) {
 314       frac tmin = dot.data[ly*16+cy].min;
 315       frac tmax = dot.data[ly*16+cy].max;
 316       if (tmax == -1) continue;
 317
 318       if (minx > tmin) minx = tmin;
 319       if (maxx < tmax) maxx = tmax;
 320     }
 321
 322     if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
 323
 324     minx /= 16;
 325     maxx /= 16;
 326     for(ix=minx; ix<=maxx; ix++) {
 327       int cnt = i_pixel_coverage(&dot, ix, ly);
 328       if (cnt>255) cnt = 255;
 329       if (cnt) { /* should never be true */
 330         int ch;
 331         float ratio = (float)cnt/255.0;
 332         i_gpix(im, ix, ly, &temp);
 333         for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
 334         i_ppix(im, ix, ly, &temp);
 335       }
 336     }
 337   }
 338   i_mmarray_dst(&dot);
 339 }
 340
 341
 342
 343
 344
 345
 346 void
 347 i_box(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 348   int x,y;
 349   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));
 350   for(x=x1;x<x2+1;x++) {
 351     i_ppix(im,x,y1,val);
 352     i_ppix(im,x,y2,val);
 353   }
 354   for(y=y1;y<y2+1;y++) {
 355     i_ppix(im,x1,y,val);
 356     i_ppix(im,x2,y,val);
 357   }
 358 }
 359
 360 void
 361 i_box_filled(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 362   int x,y;
 363   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));
 364   for(x=x1;x<x2+1;x++) for (y=y1;y<y2+1;y++) i_ppix(im,x,y,val);
 365 }
 366
 367 void
 368 i_box_cfill(i_img *im,int x1,int y1,int x2,int y2,i_fill_t *fill) {
 369   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));
 370
 371   ++x2;
 372   if (im->bits == i_8_bits && fill->fill_with_color) {
 373     i_color *line = mymalloc(sizeof(i_color) * (x2 - x1));
 374     i_color *work = NULL;
 375     if (fill->combine)
 376       work = mymalloc(sizeof(i_color) * (x2-x1));
 377     while (y1 <= y2) {
 378       if (fill->combine)
 379         i_glin(im, x1, x2, y1, line);
 380
 381       (fill->fill_with_color)(fill, x1, y1, x2-x1, im->channels, line, work);
 382       i_plin(im, x1, x2, y1, line);
 383       ++y1;
 384     }
 385     myfree(line);
 386     if (work)
 387       myfree(work);
 388   }
 389   else {
 390     i_fcolor *line = mymalloc(sizeof(i_fcolor) * (x2 - x1));
 391     i_fcolor *work;
 392     work = mymalloc(sizeof(i_fcolor) * (x2 - x1));
 393
 394     while (y1 <= y2) {
 395       if (fill->combinef)
 396         i_glinf(im, x1, x2, y1, line);
 397
 398       (fill->fill_with_fcolor)(fill, x1, y1, x2-x1, im->channels, line, work);
 399       i_plinf(im, x1, x2, y1, line);
 400       ++y1;
 401     }
 402     myfree(line);
 403     if (work)
 404       myfree(work);
 405   }
 406 }
 407
 408 void
 409 i_draw(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 410   double alpha;
 411   double dsec;
 412   int temp;
 413
 414   mm_log((1,"i_draw(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
 415
 416   alpha=(double)(y2-y1)/(double)(x2-x1);
 417   if (fabs(alpha)<1)
 418     {
 419       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 420       dsec=y1;
 421       while(x1<x2)
 422         {
 423           dsec+=alpha;
 424           i_ppix(im,x1,(int)(dsec+0.5),val);
 425           x1++;
 426         }
 427     }
 428   else
 429     {
 430       alpha=1/alpha;
 431       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 432       dsec=x1;
 433       while(y1<y2)
 434         {
 435           dsec+=alpha;
 436           i_ppix(im,(int)(dsec+0.5),y1,val);
 437           y1++;
 438         }
 439     }
 440   mm_log((1,"i_draw: alpha=%f.\n",alpha));
 441 }
 442
 443 void
 444 i_line_aa(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 445   i_color tval;
 446   float alpha;
 447   float dsec,dfrac;
 448   int temp,dx,dy,isec,ch;
 449
 450   mm_log((1,"i_draw(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
 451
 452   dy=y2-y1;
 453   dx=x2-x1;
 454
 455   if (abs(dx)>abs(dy)) { /* alpha < 1 */
 456     if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 457     alpha=(float)(y2-y1)/(float)(x2-x1);
 458
 459     dsec=y1;
 460     while(x1<=x2) {
 461       isec=(int)dsec;
 462       dfrac=dsec-isec;
 463       /*      dfrac=1-(1-dfrac)*(1-dfrac); */
 464       /* This is something we can play with to try to get better looking lines */
 465
 466       i_gpix(im,x1,isec,&tval);
 467       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
 468       i_ppix(im,x1,isec,&tval);
 469
 470       i_gpix(im,x1,isec+1,&tval);
 471       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
 472       i_ppix(im,x1,isec+1,&tval);
 473
 474       dsec+=alpha;
 475       x1++;
 476     }
 477   } else {
 478     if (y2<y1) { temp=y1; y1=y2; y2=temp; temp=x1; x1=x2; x2=temp; }
 479     alpha=(float)(x2-x1)/(float)(y2-y1);
 480     dsec=x1;
 481     while(y1<=y2) {
 482       isec=(int)dsec;
 483       dfrac=dsec-isec;
 484       /*      dfrac=sqrt(dfrac); */
 485       /* This is something we can play with */
 486       i_gpix(im,isec,y1,&tval);
 487       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
 488       i_ppix(im,isec,y1,&tval);
 489
 490       i_gpix(im,isec+1,y1,&tval);
 491       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
 492       i_ppix(im,isec+1,y1,&tval);
 493
 494       dsec+=alpha;
 495       y1++;
 496     }
 497   }
 498 }
 499
 500 double
 501 perm(int n,int k) {
 502   double r;
 503   int i;
 504   r=1;
 505   for(i=k+1;i<=n;i++) r*=i;
 506   for(i=1;i<=(n-k);i++) r/=i;
 507   return r;
 508 }
 509
 510
 511 /* Note in calculating t^k*(1-t)^(n-k)
 512    we can start by using t^0=1 so this simplifies to
 513    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
 514    to get a new level - this may lead to errors who knows lets test it */
 515
 516 void
 517 i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
 518   double *bzcoef;
 519   double t,cx,cy;
 520   int k,i;
 521   int lx = 0,ly = 0;
 522   int n=l-1;
 523   double itr,ccoef;
 524
 525
 526   bzcoef=mymalloc(sizeof(double)*l);
 527   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
 528   ICL_info(val);
 529
 530
 531   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
 532   i=0;
 533   for(t=0;t<=1;t+=0.005) {
 534     cx=cy=0;
 535     itr=t/(1-t);
 536     ccoef=pow(1-t,n);
 537     for(k=0;k<l;k++) {
 538       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
 539               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
 540
 541       cx+=bzcoef[k]*x[k]*ccoef;
 542       cy+=bzcoef[k]*y[k]*ccoef;
 543       ccoef*=itr;
 544     }
 545     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
 546     if (i++) {
 547       i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val);
 548     }
 549       /*     i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
 550     lx=(int)(0.5+cx);
 551     ly=(int)(0.5+cy);
 552   }
 553   ICL_info(val);
 554   myfree(bzcoef);
 555 }
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567 /* Flood fill
 568
 569    REF: Graphics Gems I. page 282+
 570
 571 */
 572
 573 /* This should be moved into a seperate file? */
 574
 575 /* This is the truncation used:
 576
 577    a double is multiplied by 16 and then truncated.
 578    This means that 0 -> 0
 579    So a triangle of (0,0) (10,10) (10,0) Will look like it's
 580    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
 581
 582 */
 583
 584
 585 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
 586    graphics gems I */
 587
 588 /*
 589 struct stc {
 590   int mylx,myrx;
 591   int dadlx,dadrx;
 592   int myy;
 593   int mydirection;
 594 };
 595
 596 Not used code???
 597 */
 598
 599
 600 struct stack_element {
 601   int myLx,myRx;
 602   int dadLx,dadRx;
 603   int myY;
 604   int myDirection;
 605 };
 606
 607
 608 /* create the link data to put push onto the stack */
 609
 610 static
 611 struct stack_element*
 612 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
 613   struct stack_element *ste;
 614   ste              = mymalloc(sizeof(struct stack_element));
 615   ste->myLx        = left;
 616   ste->myRx        = right;
 617   ste->dadLx       = dadl;
 618   ste->dadRx       = dadr;
 619   ste->myY         = y;
 620   ste->myDirection = dir;
 621   return ste;
 622 }
 623
 624 /* i_ccomp compares two colors and gives true if they are the same */
 625
 626 static int
 627 i_ccomp(i_color *val1,i_color *val2,int ch) {
 628   int i;
 629   for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
 630   return 1;
 631 }
 632
 633
 634 static int
 635 i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
 636   i_color cval;
 637   while(1) {
 638     if (seedx-1 < 0) break;
 639     i_gpix(im,seedx-1,seedy,&cval);
 640     if (!i_ccomp(val,&cval,im->channels)) break;
 641     seedx--;
 642   }
 643   return seedx;
 644 }
 645
 646 static int
 647 i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
 648   i_color cval;
 649   while(1) {
 650     if (seedx+1 > im->xsize-1) break;
 651     i_gpix(im,seedx+1,seedy,&cval);
 652     if (!i_ccomp(val,&cval,im->channels)) break;
 653     seedx++;
 654   }
 655   return seedx;
 656 }
 657
 658 /* Macro to create a link and push on to the list */
 659
 660 #define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s = crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s); }
 661
 662 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
 663 /* No overflow check! */
 664
 665 #define ST_POP() { struct stack_element *s; llist_pop(st,&s); lx = s->myLx; rx = s->myRx; dadLx = s->dadLx; dadRx = s->dadRx; y = s->myY; direction= s->myDirection; myfree(s); }
 666
 667 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) { int pushrx = rx+1; int pushlx = lx-1; ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir); if (rx > dadRx)                                      ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir); if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir); }
 668
 669 #define SET(x,y) btm_set(btm,x,y);
 670
 671 #define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels)  ) ))
 672
 673 void
 674 i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
 675
 676   int lx,rx;
 677   int y;
 678   int direction;
 679   int dadLx,dadRx;
 680
 681   int wasIn=0;
 682   int x=0;
 683
 684   /*  int tx,ty; */
 685
 686   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
 687
 688   struct llist *st;
 689   struct i_bitmap *btm;
 690
 691   int channels,xsize,ysize;
 692   i_color cval,val;
 693
 694   channels = im->channels;
 695   xsize    = im->xsize;
 696   ysize    = im->ysize;
 697
 698   btm = btm_new(xsize,ysize);
 699   st = llist_new(100,sizeof(struct stack_element*));
 700
 701   /* Get the reference color */
 702   i_gpix(im,seedx,seedy,&val);
 703
 704   /* Find the starting span and fill it */
 705   lx = i_lspan(im,seedx,seedy,&val);
 706   rx = i_rspan(im,seedx,seedy,&val);
 707
 708   /* printf("span: %d %d \n",lx,rx); */
 709
 710   for(x=lx; x<=rx; x++) SET(x,seedy);
 711
 712   ST_PUSH(lx, rx, lx, rx, seedy+1, 1);
 713   ST_PUSH(lx, rx, lx, rx, seedy-1,-1);
 714
 715   while(st->count) {
 716     ST_POP();
 717
 718     if (y<0 || y>ysize-1) continue;
 719
 720     if (bymin > y) bymin=y; /* in the worst case an extra line */
 721     if (bymax < y) bymax=y;
 722
 723     /*     printf("start of scan - on stack : %d \n",st->count); */
 724
 725
 726     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
 727
 728     /*
 729     printf(" ");
 730     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
 731     printf("\n");
 732     for(ty=0;ty<ysize;ty++) {
 733       printf("%d",ty%10);
 734       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
 735       printf("\n");
 736     }
 737
 738     printf("y=%d\n",y);
 739     */
 740
 741
 742     x=lx+1;
 743     if ( (wasIn = INSIDE(lx,y)) ) {
 744       SET(lx,y);
 745       lx--;
 746       while(INSIDE(lx,y) && lx > 0) {
 747         SET(lx,y);
 748         lx--;
 749       }
 750     }
 751
 752     if (bxmin > lx) bxmin=lx;
 753
 754     while(x <= xsize-1) {
 755       /*  printf("x=%d\n",x); */
 756       if (wasIn) {
 757
 758         if (INSIDE(x,y)) {
 759           /* case 1: was inside, am still inside */
 760           SET(x,y);
 761         } else {
 762           /* case 2: was inside, am no longer inside: just found the
 763              right edge of a span */
 764           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
 765
 766           if (bxmax < x) bxmax=x;
 767
 768           wasIn=0;
 769         }
 770       } else {
 771         if (x>rx) goto EXT;
 772         if (INSIDE(x,y)) {
 773           SET(x,y);
 774           /* case 3: Wasn't inside, am now: just found the start of a new run */
 775           wasIn=1;
 776             lx=x;
 777         } else {
 778           /* case 4: Wasn't inside, still isn't */
 779         }
 780       }
 781       x++;
 782     }
 783   EXT: /* out of loop */
 784     if (wasIn) {
 785       /* hit an edge of the frame buffer while inside a run */
 786       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
 787       if (bxmax < x) bxmax=x;
 788     }
 789   }
 790
 791   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
 792        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
 793
 794   for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
 795
 796   btm_destroy(btm);
 797   mm_log((1, "DESTROY\n"));
 798   llist_destroy(st);
 799 }
 800
 801 static struct i_bitmap *
 802 i_flood_fill_low(i_img *im,int seedx,int seedy,
 803                  int *bxminp, int *bxmaxp, int *byminp, int *bymaxp) {
 804   int lx,rx;
 805   int y;
 806   int direction;
 807   int dadLx,dadRx;
 808
 809   int wasIn=0;
 810   int x=0;
 811
 812   /*  int tx,ty; */
 813
 814   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
 815
 816   struct llist *st;
 817   struct i_bitmap *btm;
 818
 819   int channels,xsize,ysize;
 820   i_color cval,val;
 821
 822   channels=im->channels;
 823   xsize=im->xsize;
 824   ysize=im->ysize;
 825
 826   btm=btm_new(xsize,ysize);
 827   st=llist_new(100,sizeof(struct stack_element*));
 828
 829   /* Get the reference color */
 830   i_gpix(im,seedx,seedy,&val);
 831
 832   /* Find the starting span and fill it */
 833   lx=i_lspan(im,seedx,seedy,&val);
 834   rx=i_rspan(im,seedx,seedy,&val);
 835
 836   /* printf("span: %d %d \n",lx,rx); */
 837
 838   for(x=lx;x<=rx;x++) SET(x,seedy);
 839
 840   ST_PUSH(lx,rx,lx,rx,seedy+1,1);
 841   ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
 842
 843   while(st->count) {
 844     ST_POP();
 845
 846     if (y<0 || y>ysize-1) continue;
 847
 848     if (bymin > y) bymin=y; /* in the worst case an extra line */
 849     if (bymax < y) bymax=y;
 850
 851     /*     printf("start of scan - on stack : %d \n",st->count); */
 852
 853
 854     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
 855
 856     /*
 857     printf(" ");
 858     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
 859     printf("\n");
 860     for(ty=0;ty<ysize;ty++) {
 861       printf("%d",ty%10);
 862       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
 863       printf("\n");
 864     }
 865
 866     printf("y=%d\n",y);
 867     */
 868
 869
 870     x=lx+1;
 871     if ( (wasIn = INSIDE(lx,y)) ) {
 872       SET(lx,y);
 873       lx--;
 874       while(INSIDE(lx,y) && lx > 0) {
 875         SET(lx,y);
 876         lx--;
 877       }
 878     }
 879
 880     if (bxmin > lx) bxmin=lx;
 881
 882     while(x <= xsize-1) {
 883       /*  printf("x=%d\n",x); */
 884       if (wasIn) {
 885
 886         if (INSIDE(x,y)) {
 887           /* case 1: was inside, am still inside */
 888           SET(x,y);
 889         } else {
 890           /* case 2: was inside, am no longer inside: just found the
 891              right edge of a span */
 892           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
 893
 894           if (bxmax < x) bxmax=x;
 895
 896           wasIn=0;
 897         }
 898       } else {
 899         if (x>rx) goto EXT;
 900         if (INSIDE(x,y)) {
 901           SET(x,y);
 902           /* case 3: Wasn't inside, am now: just found the start of a new run */
 903           wasIn=1;
 904             lx=x;
 905         } else {
 906           /* case 4: Wasn't inside, still isn't */
 907         }
 908       }
 909       x++;
 910     }
 911   EXT: /* out of loop */
 912     if (wasIn) {
 913       /* hit an edge of the frame buffer while inside a run */
 914       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
 915       if (bxmax < x) bxmax=x;
 916     }
 917   }
 918
 919   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
 920        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
 921
 922   llist_destroy(st);
 923
 924   *bxminp = bxmin;
 925   *bxmaxp = bxmax;
 926   *byminp = bymin;
 927   *bymaxp = bymax;
 928
 929   return btm;
 930 }
 931
 932 void
 933 i_flood_cfill(i_img *im, int seedx, int seedy, i_fill_t *fill) {
 934   int bxmin, bxmax, bymin, bymax;
 935   struct i_bitmap *btm;
 936   int x, y;
 937   int start;
 938
 939   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax);
 940
 941   if (im->bits == i_8_bits && fill->fill_with_color) {
 942     i_color *line = mymalloc(sizeof(i_color) * (bxmax - bxmin));
 943     i_color *work = NULL;
 944     if (fill->combine)
 945       work = mymalloc(sizeof(i_color) * (bxmax - bxmin));
 946
 947     for(y=bymin;y<=bymax;y++) {
 948       x = bxmin;
 949       while (x < bxmax) {
 950         while (x < bxmax && !btm_test(btm, x, y)) {
 951           ++x;
 952         }
 953         if (btm_test(btm, x, y)) {
 954           start = x;
 955           while (x < bxmax && btm_test(btm, x, y)) {
 956             ++x;
 957           }
 958           if (fill->combine)
 959             i_glin(im, start, x, y, line);
 960           (fill->fill_with_color)(fill, start, y, x-start, im->channels,
 961                                   line, work);
 962           i_plin(im, start, x, y, line);
 963         }
 964       }
 965     }
 966     myfree(line);
 967     if (work)
 968       myfree(work);
 969   }
 970   else {
 971     i_fcolor *line = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
 972     i_fcolor *work = NULL;
 973     if (fill->combinef)
 974       work = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
 975
 976     for(y=bymin;y<=bymax;y++) {
 977       x = bxmin;
 978       while (x < bxmax) {
 979         while (x < bxmax && !btm_test(btm, x, y)) {
 980           ++x;
 981         }
 982         if (btm_test(btm, x, y)) {
 983           start = x;
 984           while (x < bxmax && btm_test(btm, x, y)) {
 985             ++x;
 986           }
 987           if (fill->combinef)
 988             i_glinf(im, start, x, y, line);
 989           (fill->fill_with_fcolor)(fill, start, y, x-start, im->channels,
 990                                    line, work);
 991           i_plinf(im, start, x, y, line);
 992         }
 993       }
 994     }
 995     myfree(line);
 996     if (work)
 997       myfree(work);
 998   }
 999
1000   btm_destroy(btm);
1001 }