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