Initial revision
[imager.git] / 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 }