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