draw.c

   1 #include "image.h"
   2 #include "draw.h"
   3 #include "log.h"
   4
   5 void
   6 i_mmarray_cr(i_mmarray *ar,int l) {
   7   int i;
   8
   9   ar->lines=l;
  10   ar->data=mymalloc(sizeof(minmax)*l);
  11   for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
  12 }
  13
  14 void
  15 i_mmarray_dst(i_mmarray *ar) {
  16   ar->lines=0;
  17   if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
  18 }
  19
  20 void
  21 i_mmarray_add(i_mmarray *ar,int x,int y) {
  22   if (y>-1 && y<ar->lines)
  23     {
  24       if (x<ar->data[y].min) ar->data[y].min=x;
  25       if (x>ar->data[y].max) ar->data[y].max=x;
  26     }
  27 }
  28
  29 int
  30 i_mmarray_gmin(i_mmarray *ar,int y) {
  31   if (y>-1 && y<ar->lines) return ar->data[y].min;
  32   else return -1;
  33 }
  34
  35 int
  36 i_mmarray_getm(i_mmarray *ar,int y) {
  37   if (y>-1 && y<ar->lines) return ar->data[y].max;
  38   else return MAXINT;
  39 }
  40
  41 void
  42 i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
  43   int i,x;
  44   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);
  45 }
  46
  47
  48 static
  49 void
  50 i_arcdraw(int x1, int y1, int x2, int y2, i_mmarray *ar) {
  51   double alpha;
  52   double dsec;
  53   int temp;
  54   alpha=(double)(y2-y1)/(double)(x2-x1);
  55   if (fabs(alpha)<1)
  56     {
  57       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
  58       dsec=y1;
  59       while(x1<x2)
  60         {
  61           dsec+=alpha;
  62           i_mmarray_add(ar,x1,(int)(dsec+0.5));
  63           x1++;
  64         }
  65     }
  66   else
  67     {
  68       alpha=1/alpha;
  69       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
  70       dsec=x1;
  71       while(y1<y2)
  72         {
  73           dsec+=alpha;
  74           i_mmarray_add(ar,(int)(dsec+0.5),y1);
  75           y1++;
  76         }
  77     }
  78 }
  79
  80 void
  81 i_mmarray_info(i_mmarray *ar) {
  82   int i;
  83   for(i=0;i<ar->lines;i++)
  84   if (ar->data[i].max!=-1) printf("line %d: min=%d, max=%d.\n",i,ar->data[i].min,ar->data[i].max);
  85 }
  86
  87
  88 void
  89 i_arc(i_img *im,int x,int y,float rad,float d1,float d2,i_color *val) {
  90   i_mmarray dot;
  91   float f,fx,fy;
  92   int x1,y1;
  93
  94   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));
  95
  96   i_mmarray_cr(&dot,im->ysize);
  97
  98   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
  99   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
 100   fx=(float)x1; fy=(float)y1;
 101
 102   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 103   i_arcdraw(x, y, x1, y1, &dot);
 104
 105   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
 106   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
 107
 108   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)));
 109
 110   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 111   i_arcdraw(x, y, x1, y1, &dot);
 112
 113   /*  dot.info(); */
 114   i_mmarray_render(im,&dot,val);
 115 }
 116
 117 void
 118 i_box(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 119   int x,y;
 120   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));
 121   for(x=x1;x<x2+1;x++) {
 122     i_ppix(im,x,y1,val);
 123     i_ppix(im,x,y2,val);
 124   }
 125   for(y=y1;y<y2+1;y++) {
 126     i_ppix(im,x1,y,val);
 127     i_ppix(im,x2,y,val);
 128   }
 129 }
 130
 131 void
 132 i_box_filled(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 133   int x,y;
 134   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));
 135   for(x=x1;x<x2+1;x++) for (y=y1;y<y2+1;y++) i_ppix(im,x,y,val);
 136 }
 137
 138
 139 void
 140 i_draw(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 141   double alpha;
 142   double dsec;
 143   int temp;
 144
 145   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));
 146
 147   alpha=(double)(y2-y1)/(double)(x2-x1);
 148   if (fabs(alpha)<1)
 149     {
 150       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 151       dsec=y1;
 152       while(x1<x2)
 153         {
 154           dsec+=alpha;
 155           i_ppix(im,x1,(int)(dsec+0.5),val);
 156           x1++;
 157         }
 158     }
 159   else
 160     {
 161       alpha=1/alpha;
 162       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 163       dsec=x1;
 164       while(y1<y2)
 165         {
 166           dsec+=alpha;
 167           i_ppix(im,(int)(dsec+0.5),y1,val);
 168           y1++;
 169         }
 170     }
 171   mm_log((1,"i_draw: alpha=%f.\n",alpha));
 172 }
 173
 174 void
 175 i_line_aa(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 176   i_color tval;
 177   float alpha;
 178   float dsec,dfrac;
 179   int temp,dx,dy,isec,ch;
 180
 181   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));
 182
 183   dy=y2-y1;
 184   dx=x2-x1;
 185
 186   if (abs(dx)>abs(dy)) { /* alpha < 1 */
 187     if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 188     alpha=(float)(y2-y1)/(float)(x2-x1);
 189
 190     dsec=y1;
 191     while(x1<=x2) {
 192       isec=(int)dsec;
 193       dfrac=dsec-isec;
 194       /*      dfrac=1-(1-dfrac)*(1-dfrac); */
 195       /* This is something we can play with to try to get better looking lines */
 196
 197       i_gpix(im,x1,isec,&tval);
 198       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
 199       i_ppix(im,x1,isec,&tval);
 200
 201       i_gpix(im,x1,isec+1,&tval);
 202       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
 203       i_ppix(im,x1,isec+1,&tval);
 204
 205       dsec+=alpha;
 206       x1++;
 207     }
 208   } else {
 209     if (y2<y1) { temp=y1; y1=y2; y2=temp; temp=x1; x1=x2; x2=temp; }
 210     alpha=(float)(x2-x1)/(float)(y2-y1);
 211     dsec=x1;
 212     while(y1<=y2) {
 213       isec=(int)dsec;
 214       dfrac=dsec-isec;
 215       /*      dfrac=sqrt(dfrac); */
 216       /* This is something we can play with */
 217       i_gpix(im,isec,y1,&tval);
 218       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
 219       i_ppix(im,isec,y1,&tval);
 220
 221       i_gpix(im,isec+1,y1,&tval);
 222       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
 223       i_ppix(im,isec+1,y1,&tval);
 224
 225       dsec+=alpha;
 226       y1++;
 227     }
 228   }
 229 }
 230
 231 double
 232 perm(int n,int k) {
 233   double r;
 234   int i;
 235   r=1;
 236   for(i=k+1;i<=n;i++) r*=i;
 237   for(i=1;i<=(n-k);i++) r/=i;
 238   return r;
 239 }
 240
 241
 242 /* Note in calculating t^k*(1-t)^(n-k)
 243    we can start by using t^0=1 so this simplifies to
 244    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
 245    to get a new level - this may lead to errors who knows lets test it */
 246
 247 void
 248 i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
 249   double *bzcoef;
 250   double t,cx,cy;
 251   int k,i;
 252   int lx = 0,ly = 0;
 253   int n=l-1;
 254   double itr,ccoef;
 255
 256
 257   bzcoef=mymalloc(sizeof(double)*l);
 258   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
 259   ICL_info(val);
 260
 261
 262   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
 263   i=0;
 264   for(t=0;t<=1;t+=0.005) {
 265     cx=cy=0;
 266     itr=t/(1-t);
 267     ccoef=pow(1-t,n);
 268     for(k=0;k<l;k++) {
 269       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
 270               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
 271
 272       cx+=bzcoef[k]*x[k]*ccoef;
 273       cy+=bzcoef[k]*y[k]*ccoef;
 274       ccoef*=itr;
 275     }
 276     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
 277     if (i++) {
 278       i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val);
 279     }
 280       /*     i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
 281     lx=(int)(0.5+cx);
 282     ly=(int)(0.5+cy);
 283   }
 284   ICL_info(val);
 285   myfree(bzcoef);
 286 }
 287
 288
 289
 290 /* Flood fill
 291
 292    REF: Graphics Gems I. page 282+
 293
 294 */
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311 /* This should be moved into a seperate file? */
 312
 313 /* This is the truncation used:
 314
 315    a double is multiplied by 16 and then truncated.
 316    This means that 0 -> 0
 317    So a triangle of (0,0) (10,10) (10,0) Will look like it's
 318    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
 319
 320 */
 321
 322
 323
 324
 325 #define IMTRUNC(x) ((int)(x*16))
 326
 327
 328 /*
 329 typedef struct {
 330   short ms,ls;
 331 } pcord;
 332 */
 333
 334 typedef int pcord;
 335
 336 struct p_point {
 337   int n;
 338   pcord x,y;
 339 };
 340
 341 struct p_line  {
 342   int n;
 343   pcord x1,y1;
 344   pcord x2,y2;
 345   pcord miny,maxy;
 346 };
 347
 348 struct p_slice {
 349   int n;
 350   double x;
 351 };
 352
 353 int
 354 p_compy(const struct p_point *p1, const struct p_point *p2) {
 355   if (p1->y > p2->y) return 1;
 356   if (p1->y < p2->y) return -1;
 357   return 0;
 358 }
 359
 360 int
 361 p_compx(const struct p_slice *p1, const struct p_slice *p2) {
 362   if (p1->x > p2->x) return 1;
 363   if (p1->x < p2->x) return -1;
 364   return 0;
 365 }
 366
 367 /* Change this to int? and round right goddamn it! */
 368
 369 double
 370 p_eval_aty(struct p_line *l,pcord y) {
 371   int t;
 372   t=l->y2-l->y1;
 373   if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
 374   return (l->x1+l->x2)/2.0;
 375 }
 376
 377 double
 378 p_eval_atx(struct p_line *l,pcord x) {
 379   int t;
 380   t=l->x2-l->x1;
 381   if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
 382   return (l->y1+l->y2)/2.0;
 383 }
 384
 385
 386 /* Algorithm to count the pixels covered by line going through pixel (x,y)
 387    in coarse coords.
 388 */
 389
 390 /*
 391 static int
 392 p_eval_coverage(struct p_line *l, int lc, int x, pcord y1, pcord y2) {
 393
 394   return 0;
 395 }
 396 */
 397
 398
 399 /* Antialiasing polygon algorithm
 400    specs:
 401      1. only nice polygons - no crossovers
 402      2. 1/16 pixel resolution # previously - floating point co-ordinates
 403      3. full antialiasing ( complete spectrum of blends )
 404      4. uses hardly any memory
 405      5. no subsampling phase
 406
 407    For each interval we must:
 408      1. find which lines are in it
 409      2. order the lines from in increasing x order.
 410         since we are assuming no crossovers it is sufficent
 411         to check a single point on each line.
 412 */
 413
 414 /*
 415   Terms:
 416
 417     1. Interval:  A vertical segment in which no lines cross nor end.
 418     2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
 419     3. Slice:     A start stop line pair.
 420
 421  */
 422
 423 /* Templine logic:
 424
 425    The variable tempflush describes if there is anything in the templine array or not.
 426
 427    if tempflush is 0 then the array is clean.
 428    if tempflush is 1 then the array contains a partial filled scanline
 429
 430  */
 431
 432 /* Rendering of a single start stop pair:
 433
 434 ?? REWRITE
 435
 436    The rendering is split in three parts
 437    1. From the first start pixel to the first stop pixel
 438    2. Area from the first end pixel to the last start pixel
 439    3. Area from the first end pixel to the last start pixel
 440
 441  */
 442
 443
 444 void
 445 i_poly_aa(i_img *im,int l,double *x,double *y,i_color *val) {
 446   int i,k;                      /* Index variables */
 447   int clc;                      /* Index of next item on interval linelist */
 448   int tx;                       /* Coarse x coord within a scanline */
 449   pcord miny,maxy;              /* Min and max values of the current slice in the subcord system */
 450   pcord minacy,maxacy;          /* Min and max values of the current scanline bounded by the slice
 451                                    in the subcord system */
 452   int cscl;                     /* Current scanline */
 453   pcord cc;                     /* Current vertical centerpoint of interval */
 454   int mt1,mt2;
 455   int minsx,minex,maxsx,maxex;  /* The horizontal stretches of the lines beloning to the current slice within a scanline */
 456   int *templine;                /* Line accumulator */
 457
 458   struct p_point *pset;         /* List of points in polygon */
 459   struct p_line *lset;          /* List of lines in polygon */
 460   struct p_slice *tllist;       /* List of slices */
 461
 462   i_color red,blue,yellow;
 463   red.rgb.r=255;
 464   red.rgb.g=0;
 465   red.rgb.b=0;
 466
 467   blue.rgb.r=0;
 468   blue.rgb.g=0;
 469   blue.rgb.b=255;
 470
 471   yellow.rgb.r=255;
 472   yellow.rgb.g=255;
 473   yellow.rgb.b=255;
 474
 475   if ( (pset=mymalloc(sizeof(struct p_point)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 476   if ( (lset=mymalloc(sizeof(struct p_line)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 477   if ( (tllist=mymalloc(sizeof(struct p_slice)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 478   if ( (templine=mymalloc(sizeof(int)*im->xsize)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 479
 480   /* insert the lines into the line list */
 481
 482   for(i=0;i<l;i++) {
 483     pset[i].n=i;
 484     pset[i].x=IMTRUNC(x[i]);
 485     pset[i].y=IMTRUNC(y[i]);
 486     lset[i].n=i;
 487     lset[i].x1=IMTRUNC(x[i]);
 488     lset[i].y1=IMTRUNC(y[i]);
 489     lset[i].x2=IMTRUNC(x[(i+1)%l]);
 490     lset[i].y2=IMTRUNC(y[(i+1)%l]);
 491     lset[i].miny=min(lset[i].y1,lset[i].y2);
 492     lset[i].maxy=max(lset[i].y1,lset[i].y2);
 493   }
 494
 495   qsort(pset,l,sizeof(struct p_point),(int(*)(const void *,const void *))p_compy);
 496
 497   printf("post point list (sorted in ascending y order)\n");
 498   for(i=0;i<l;i++) {
 499     printf("%d [ %d ] %d %d\n",i,pset[i].n,pset[i].x,pset[i].y);
 500   }
 501
 502   printf("line list\n");
 503   for(i=0;i<l;i++) {
 504     printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",i,lset[i].n,lset[i].x1,lset[i].y1,lset[i].x2,lset[i].y2,lset[i].miny,lset[i].maxy);
 505   }
 506
 507   printf("MAIN LOOP\n\n");
 508
 509   /* Zero templine buffer */
 510   /* Templine buffer flushed everytime a scan line ends */
 511   for(i=0;i<im->xsize;i++) templine[i]=0;
 512
 513
 514   /* loop on intervals */
 515   for(i=0;i<l-1;i++) {
 516     cc=(pset[i].y+pset[i+1].y)/2;
 517     printf("current slice is: %d to %d ( cpoint %d )\n",pset[i].y,pset[i+1].y,cc);
 518     clc=0;
 519
 520     /* stuff this in a function ?? */
 521
 522     /* Check what lines belong to interval */
 523     for(k=0;k<l;k++) {
 524       printf("checking line: %d [ %d ] (%d , %d) -> (%d, %d) yspan ( %d , %d )",
 525              k,lset[k].n,lset[k].x1,lset[k].y1,lset[k].x2,lset[k].y2,lset[k].miny,lset[k].maxy);
 526       if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
 527         if (lset[k].miny == lset[k].maxy) printf(" HORIZONTAL - skipped\n");
 528         else {
 529           printf(" INSIDE\n");
 530           tllist[clc].x=p_eval_aty(&lset[k],cc);
 531           tllist[clc++].n=k;
 532         }
 533       } else printf(" OUTSIDE\n");
 534     }
 535
 536     /*
 537        at this point a table of pixels that need special care should
 538        be generated from the line list - it should be ordered so that only
 539        one needs to be checked - options: rendering to a list then order - or
 540        rendering in the right order might be possible to do nicely with the
 541        following heuristic:
 542
 543        1. Draw leftmost pixel for this line
 544        2. If preceeding pixel was occupied check next one else go to 1 again.
 545     */
 546
 547     printf("lines in current interval:");
 548     for(k=0;k<clc;k++) printf("  %d (%.2f)",tllist[k].n,tllist[k].x);
 549     printf("\n");
 550
 551     /* evaluate the lines in the middle of the slice */
 552
 553     printf("Sort lines left to right within interval\n");
 554     qsort(tllist,clc,sizeof(struct p_slice),(int(*)(const void *,const void *))p_compx);
 555
 556     printf("sorted lines in interval - output:");
 557     for(k=0;k<clc;k++) printf(" %d",tllist[k].n);
 558     printf("\n");
 559
 560     miny=pset[i].y;
 561     maxy=pset[i+1].y;
 562
 563     /* iterate over scanlines */
 564     for(cscl=(miny)/16;cscl<=maxy/16;cscl++) {
 565       minacy=max(miny,cscl*16);
 566       maxacy=min(maxy,cscl*16+15);
 567
 568       printf("Scanline bound %d - %d\n",minacy, maxacy);
 569
 570       /* iterate over line pairs (slices) within interval */
 571       for(k=0;k<clc-1;k+=2) {
 572
 573         mt1=p_eval_aty(&lset[tllist[k].n],minacy);      /* upper corner */
 574         mt2=p_eval_aty(&lset[tllist[k].n],maxacy);      /* lower corner */
 575         minsx=min(mt1,mt2);
 576         minex=max(mt1,mt2);
 577         mt1=p_eval_aty(&lset[tllist[k+1].n],minacy);    /* upper corner */
 578         mt2=p_eval_aty(&lset[tllist[k+1].n],maxacy);    /* lower corner */
 579         maxsx=min(mt1,mt2);
 580         maxex=max(mt1,mt2);
 581
 582         printf("minsx: %d minex: %d\n",minsx,minex);
 583         printf("maxsx: %d maxex: %d\n",maxsx,maxex);
 584
 585         if (minex/16<maxsx/16) printf("Scan slice is simple!\n");
 586         else printf("Scan slice is complicated!\n");
 587
 588         if (minsx/16 == minex/16) { /* The line starts and ends in the same pixel */
 589           printf("Low slant start pixel\n");
 590           templine[minsx/16]=(maxacy-minacy+1)*(minex-minsx+1)/2+((minex | 0xF)-minex)*(maxacy-minacy+1);
 591         } else {
 592           for(tx=minsx/16;tx<minex/16+1;tx++) {
 593             int minx,maxx,minxy,maxxy;
 594             minx=max(minsx,  tx*16   );
 595             maxx=min(minex,  tx*16+15);
 596
 597             if (minx == maxx) {
 598               templine[tx]=(maxacy-minacy+1);
 599             } else {
 600
 601               minxy=p_eval_atx(&lset[tllist[k].n], minx);
 602               maxxy=p_eval_atx(&lset[tllist[k].n], maxx);
 603
 604               templine[tx]+=(abs(minxy-maxxy)+1)*(minex-minsx+1)/2; /* The triangle between the points */
 605               if (mt1 < mt2) { /* \ slant */
 606                 /* ((minex | 0xF)-minex)*(maxacy-minacy+1); FIXME: unfinished */
 607
 608
 609
 610               } else {
 611                 templine[tx]+=((minex | 0xF)-minex)*(maxacy-minacy+1);
 612               }
 613
 614             }
 615           }
 616         }
 617
 618         for(tx=maxsx/16;tx<maxex/16+1;tx++) templine[tx]+=16*(maxacy-minacy+1);
 619
 620         /*      for(tx=minex/16+1;tx<maxsx/16;tx++) 0; */
 621
 622
 623         printf("line %d: painting  %d - %d\n",cscl,minex/16+1,maxsx/16);
 624         if ( (minacy != cscl*16) || (maxacy != cscl*16+15) ) {
 625           for(tx=minsx/16;tx<maxex/16+1;tx++) {
 626             i_ppix(im,tx,cscl,&yellow);
 627           }
 628         }
 629         else {
 630           for(tx=minsx/16;tx<minex/16+1;tx++) i_ppix(im,tx,cscl,&red);
 631           for(tx=maxsx/16;tx<maxex/16+1;tx++) i_ppix(im,tx,cscl,&blue);
 632           for(tx=minex/16+1;tx<maxsx/16;tx++) i_ppix(im,tx,cscl,val);
 633         }
 634
 635       } /* Slices */
 636     } /* Scanlines */
 637   } /* Intervals */
 638 } /* Function */
 639
 640
 641
 642
 643
 644
 645
 646 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
 647    graphics gems I */
 648
 649 /*
 650 struct stc {
 651   int mylx,myrx;
 652   int dadlx,dadrx;
 653   int myy;
 654   int mydirection;
 655 };
 656
 657 Not used code???
 658 */
 659
 660
 661 struct stack_element {
 662   int myLx,myRx;
 663   int dadLx,dadRx;
 664   int myY;
 665   int myDirection;
 666 };
 667
 668
 669 /* create the link data to put push onto the stack */
 670
 671 static
 672 struct stack_element*
 673 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
 674   struct stack_element *ste;
 675   ste=(struct stack_element*)mymalloc(sizeof(struct stack_element));
 676   ste->myLx=left;
 677   ste->myRx=right;
 678   ste->dadLx=dadl;
 679   ste->dadRx=dadr;
 680   ste->myY=y;
 681   ste->myDirection=dir;
 682   return ste;
 683 }
 684
 685 /* i_ccomp compares two colors and gives true if they are the same */
 686
 687 static int
 688 i_ccomp(i_color *val1,i_color *val2,int ch) {
 689   int i;
 690   for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
 691   return 1;
 692 }
 693
 694
 695 static int
 696 i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
 697   i_color cval;
 698   while(1) {
 699     if (seedx-1 < 0) break;
 700     i_gpix(im,seedx-1,seedy,&cval);
 701     if (!i_ccomp(val,&cval,im->channels)) break;
 702     seedx--;
 703   }
 704   return seedx;
 705 }
 706
 707 static int
 708 i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
 709   i_color cval;
 710   while(1) {
 711     if (seedx+1 > im->xsize-1) break;
 712     i_gpix(im,seedx+1,seedy,&cval);
 713     if (!i_ccomp(val,&cval,im->channels)) break;
 714     seedx++;
 715   }
 716   return seedx;
 717 }
 718
 719 /* Macro to create a link and push on to the list */
 720
 721 #define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s=crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s);}
 722
 723 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
 724 /* No overflow check! */
 725
 726 #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); }
 727
 728 #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); }
 729
 730 #define SET(x,y) btm_set(btm,x,y);
 731
 732 #define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels)  ) ))
 733
 734 void
 735 i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
 736
 737   int lx,rx;
 738   int y;
 739   int direction;
 740   int dadLx,dadRx;
 741
 742   int wasIn=0;
 743   int x=0;
 744
 745   /*  int tx,ty; */
 746
 747   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
 748
 749   struct llist *st;
 750   struct i_bitmap *btm;
 751
 752   int channels,xsize,ysize;
 753   i_color cval,val;
 754
 755   channels=im->channels;
 756   xsize=im->xsize;
 757   ysize=im->ysize;
 758
 759   btm=btm_new(xsize,ysize);
 760   st=llist_new(100,sizeof(struct stack_element*));
 761
 762   /* Get the reference color */
 763   i_gpix(im,seedx,seedy,&val);
 764
 765   /* Find the starting span and fill it */
 766   lx=i_lspan(im,seedx,seedy,&val);
 767   rx=i_rspan(im,seedx,seedy,&val);
 768
 769   /* printf("span: %d %d \n",lx,rx); */
 770
 771   for(x=lx;x<=rx;x++) SET(x,seedy);
 772
 773   ST_PUSH(lx,rx,lx,rx,seedy+1,1);
 774   ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
 775
 776   while(st->count) {
 777     ST_POP();
 778
 779     if (y<0 || y>ysize-1) continue;
 780
 781     if (bymin > y) bymin=y; /* in the worst case an extra line */
 782     if (bymax < y) bymax=y;
 783
 784     /*     printf("start of scan - on stack : %d \n",st->count); */
 785
 786
 787     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
 788
 789     /*
 790     printf(" ");
 791     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
 792     printf("\n");
 793     for(ty=0;ty<ysize;ty++) {
 794       printf("%d",ty%10);
 795       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
 796       printf("\n");
 797     }
 798
 799     printf("y=%d\n",y);
 800     */
 801
 802
 803     x=lx+1;
 804     if ( (wasIn = INSIDE(lx,y)) ) {
 805       SET(lx,y);
 806       lx--;
 807       while(INSIDE(lx,y) && lx > 0) {
 808         SET(lx,y);
 809         lx--;
 810       }
 811     }
 812
 813     if (bxmin > lx) bxmin=lx;
 814
 815     while(x <= xsize-1) {
 816       /*  printf("x=%d\n",x); */
 817       if (wasIn) {
 818
 819         if (INSIDE(x,y)) {
 820           /* case 1: was inside, am still inside */
 821           SET(x,y);
 822         } else {
 823           /* case 2: was inside, am no longer inside: just found the
 824              right edge of a span */
 825           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
 826
 827           if (bxmax < x) bxmax=x;
 828
 829           wasIn=0;
 830         }
 831       } else {
 832         if (x>rx) goto EXT;
 833         if (INSIDE(x,y)) {
 834           SET(x,y);
 835           /* case 3: Wasn't inside, am now: just found the start of a new run */
 836           wasIn=1;
 837             lx=x;
 838         } else {
 839           /* case 4: Wasn't inside, still isn't */
 840         }
 841       }
 842       x++;
 843     }
 844   EXT: /* out of loop */
 845     if (wasIn) {
 846       /* hit an edge of the frame buffer while inside a run */
 847       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
 848       if (bxmax < x) bxmax=x;
 849     }
 850   }
 851
 852   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
 853        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
 854
 855   for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
 856
 857   btm_destroy(btm);
 858   llist_destroy(st);
 859 }