support for generic fills for box and arc, with solid, hatched
[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
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557 /* This should be moved into a seperate file? */
558
559 /* This is the truncation used:
560    
561    a double is multiplied by 16 and then truncated.
562    This means that 0 -> 0
563    So a triangle of (0,0) (10,10) (10,0) Will look like it's
564    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
565
566 */
567
568
569
570
571 #define IMTRUNC(x) ((int)(x*16))
572
573
574 /*
575 typedef struct {
576   short ms,ls;
577 } pcord;
578 */
579
580 typedef int pcord;
581
582 struct p_point {
583   int n;
584   pcord x,y;
585 };
586
587 struct p_line  {
588   int n;
589   pcord x1,y1;
590   pcord x2,y2;
591   pcord miny,maxy;
592 };
593
594 struct p_slice {
595   int n;
596   double x;
597 };
598
599 int
600 p_compy(const struct p_point *p1, const struct p_point *p2) {
601   if (p1->y > p2->y) return 1;
602   if (p1->y < p2->y) return -1;
603   return 0;
604 }
605
606 int
607 p_compx(const struct p_slice *p1, const struct p_slice *p2) {
608   if (p1->x > p2->x) return 1;
609   if (p1->x < p2->x) return -1;
610   return 0;
611 }
612
613 /* Change this to int? and round right goddamn it! */
614
615 double
616 p_eval_aty(struct p_line *l,pcord y) {
617   int t;
618   t=l->y2-l->y1;
619   if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
620   return (l->x1+l->x2)/2.0;
621 }
622
623 double
624 p_eval_atx(struct p_line *l,pcord x) {
625   int t;
626   t=l->x2-l->x1;
627   if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
628   return (l->y1+l->y2)/2.0;
629 }
630
631
632 /* Algorithm to count the pixels covered by line going through pixel (x,y)
633    in coarse coords.
634 */
635
636 /*
637 static int
638 p_eval_coverage(struct p_line *l, int lc, int x, pcord y1, pcord y2) {
639
640   return 0;
641 }
642 */
643
644
645 /* Antialiasing polygon algorithm 
646    specs:
647      1. only nice polygons - no crossovers
648      2. 1/16 pixel resolution # previously - floating point co-ordinates
649      3. full antialiasing ( complete spectrum of blends )
650      4. uses hardly any memory
651      5. no subsampling phase
652
653    For each interval we must: 
654      1. find which lines are in it
655      2. order the lines from in increasing x order.
656         since we are assuming no crossovers it is sufficent
657         to check a single point on each line.
658 */
659
660 /*
661   Terms:
662   
663     1. Interval:  A vertical segment in which no lines cross nor end.
664     2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
665     3. Slice:     A start stop line pair.
666   
667  */
668
669 /* Templine logic: 
670    
671    The variable tempflush describes if there is anything in the templine array or not.
672    
673    if tempflush is 0 then the array is clean.
674    if tempflush is 1 then the array contains a partial filled scanline
675    
676  */
677
678 /* Rendering of a single start stop pair:
679
680 ?? REWRITE
681    
682    The rendering is split in three parts
683    1. From the first start pixel to the first stop pixel
684    2. Area from the first end pixel to the last start pixel
685    3. Area from the first end pixel to the last start pixel
686
687  */
688
689
690 void
691 i_poly_aa(i_img *im,int l,double *x,double *y,i_color *val) {
692   int i,k;                      /* Index variables */
693   int clc;                      /* Index of next item on interval linelist */
694   int tx;                       /* Coarse x coord within a scanline */
695   pcord miny,maxy;              /* Min and max values of the current slice in the subcord system */
696   pcord minacy,maxacy;          /* Min and max values of the current scanline bounded by the slice
697                                    in the subcord system */
698   int cscl;                     /* Current scanline */
699   pcord cc;                     /* Current vertical centerpoint of interval */
700   int mt1,mt2;
701   int minsx,minex,maxsx,maxex;  /* The horizontal stretches of the lines beloning to the current slice within a scanline */
702   int *templine;                /* Line accumulator */
703
704   struct p_point *pset;         /* List of points in polygon */
705   struct p_line *lset;          /* List of lines in polygon */
706   struct p_slice *tllist;       /* List of slices */
707
708   i_color red,blue,yellow;
709   red.rgb.r=255;
710   red.rgb.g=0;
711   red.rgb.b=0;
712
713   blue.rgb.r=0;
714   blue.rgb.g=0;
715   blue.rgb.b=255;
716
717   yellow.rgb.r=255;
718   yellow.rgb.g=255;
719   yellow.rgb.b=255;
720   
721   if ( (pset=mymalloc(sizeof(struct p_point)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
722   if ( (lset=mymalloc(sizeof(struct p_line)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
723   if ( (tllist=mymalloc(sizeof(struct p_slice)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
724   if ( (templine=mymalloc(sizeof(int)*im->xsize)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
725
726   /* insert the lines into the line list */
727   
728   for(i=0;i<l;i++) {
729     pset[i].n=i;
730     pset[i].x=IMTRUNC(x[i]);
731     pset[i].y=IMTRUNC(y[i]);
732     lset[i].n=i;
733     lset[i].x1=IMTRUNC(x[i]);
734     lset[i].y1=IMTRUNC(y[i]);
735     lset[i].x2=IMTRUNC(x[(i+1)%l]);
736     lset[i].y2=IMTRUNC(y[(i+1)%l]);
737     lset[i].miny=min(lset[i].y1,lset[i].y2);
738     lset[i].maxy=max(lset[i].y1,lset[i].y2);
739   }
740   
741   qsort(pset,l,sizeof(struct p_point),(int(*)(const void *,const void *))p_compy);
742   
743   printf("post point list (sorted in ascending y order)\n");
744   for(i=0;i<l;i++) {
745     printf("%d [ %d ] %d %d\n",i,pset[i].n,pset[i].x,pset[i].y);
746   }
747   
748   printf("line list\n");
749   for(i=0;i<l;i++) {
750     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);
751   }
752
753   printf("MAIN LOOP\n\n");
754
755   /* Zero templine buffer */
756   /* Templine buffer flushed everytime a scan line ends */
757   for(i=0;i<im->xsize;i++) templine[i]=0;
758   
759
760   /* loop on intervals */
761   for(i=0;i<l-1;i++) {
762     cc=(pset[i].y+pset[i+1].y)/2;
763     printf("current slice is: %d to %d ( cpoint %d )\n",pset[i].y,pset[i+1].y,cc);
764     clc=0;
765
766     /* stuff this in a function ?? */
767
768     /* Check what lines belong to interval */
769     for(k=0;k<l;k++) {
770       printf("checking line: %d [ %d ] (%d , %d) -> (%d, %d) yspan ( %d , %d )",
771              k,lset[k].n,lset[k].x1,lset[k].y1,lset[k].x2,lset[k].y2,lset[k].miny,lset[k].maxy);
772       if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
773         if (lset[k].miny == lset[k].maxy) printf(" HORIZONTAL - skipped\n");
774         else {
775           printf(" INSIDE\n"); 
776           tllist[clc].x=p_eval_aty(&lset[k],cc);
777           tllist[clc++].n=k;
778         }
779       } else printf(" OUTSIDE\n");
780     }
781     
782     /* 
783        at this point a table of pixels that need special care should
784        be generated from the line list - it should be ordered so that only
785        one needs to be checked - options: rendering to a list then order - or
786        rendering in the right order might be possible to do nicely with the
787        following heuristic:
788        
789        1. Draw leftmost pixel for this line
790        2. If preceeding pixel was occupied check next one else go to 1 again.
791     */
792     
793     printf("lines in current interval:");
794     for(k=0;k<clc;k++) printf("  %d (%.2f)",tllist[k].n,tllist[k].x);
795     printf("\n");
796     
797     /* evaluate the lines in the middle of the slice */
798     
799     printf("Sort lines left to right within interval\n");
800     qsort(tllist,clc,sizeof(struct p_slice),(int(*)(const void *,const void *))p_compx);
801     
802     printf("sorted lines in interval - output:");
803     for(k=0;k<clc;k++) printf(" %d",tllist[k].n);
804     printf("\n");
805     
806     miny=pset[i].y;
807     maxy=pset[i+1].y;
808
809     /* iterate over scanlines */
810     for(cscl=(miny)/16;cscl<=maxy/16;cscl++) {
811       minacy=max(miny,cscl*16);
812       maxacy=min(maxy,cscl*16+15);
813       
814       printf("Scanline bound %d - %d\n",minacy, maxacy);
815
816       /* iterate over line pairs (slices) within interval */
817       for(k=0;k<clc-1;k+=2) {
818
819         mt1=p_eval_aty(&lset[tllist[k].n],minacy);      /* upper corner */
820         mt2=p_eval_aty(&lset[tllist[k].n],maxacy);      /* lower corner */
821         minsx=min(mt1,mt2);
822         minex=max(mt1,mt2);
823         mt1=p_eval_aty(&lset[tllist[k+1].n],minacy);    /* upper corner */
824         mt2=p_eval_aty(&lset[tllist[k+1].n],maxacy);    /* lower corner */
825         maxsx=min(mt1,mt2);
826         maxex=max(mt1,mt2);
827
828         printf("minsx: %d minex: %d\n",minsx,minex);
829         printf("maxsx: %d maxex: %d\n",maxsx,maxex);
830         
831         if (minex/16<maxsx/16) printf("Scan slice is simple!\n");
832         else printf("Scan slice is complicated!\n");
833         
834         if (minsx/16 == minex/16) { /* The line starts and ends in the same pixel */
835           printf("Low slant start pixel\n");
836           templine[minsx/16]=(maxacy-minacy+1)*(minex-minsx+1)/2+((minex | 0xF)-minex)*(maxacy-minacy+1);
837         } else {
838           for(tx=minsx/16;tx<minex/16+1;tx++) {
839             int minx,maxx,minxy,maxxy;
840             minx=max(minsx,  tx*16   );
841             maxx=min(minex,  tx*16+15);
842
843             if (minx == maxx) {
844               templine[tx]=(maxacy-minacy+1);
845             } else {
846             
847               minxy=p_eval_atx(&lset[tllist[k].n], minx);
848               maxxy=p_eval_atx(&lset[tllist[k].n], maxx);
849               
850               templine[tx]+=(abs(minxy-maxxy)+1)*(minex-minsx+1)/2; /* The triangle between the points */
851               if (mt1 < mt2) { /* \ slant */
852                 /* ((minex | 0xF)-minex)*(maxacy-minacy+1); FIXME: unfinished */
853                 
854
855
856               } else {
857                 templine[tx]+=((minex | 0xF)-minex)*(maxacy-minacy+1);
858               }
859               
860             }
861           }
862         }
863
864         for(tx=maxsx/16;tx<maxex/16+1;tx++) templine[tx]+=16*(maxacy-minacy+1);
865         
866         /*      for(tx=minex/16+1;tx<maxsx/16;tx++) 0; */
867         
868         
869         printf("line %d: painting  %d - %d\n",cscl,minex/16+1,maxsx/16);
870         if ( (minacy != cscl*16) || (maxacy != cscl*16+15) ) {
871           for(tx=minsx/16;tx<maxex/16+1;tx++) {
872             i_ppix(im,tx,cscl,&yellow);
873           }
874         }
875         else {
876           for(tx=minsx/16;tx<minex/16+1;tx++) i_ppix(im,tx,cscl,&red);
877           for(tx=maxsx/16;tx<maxex/16+1;tx++) i_ppix(im,tx,cscl,&blue);
878           for(tx=minex/16+1;tx<maxsx/16;tx++) i_ppix(im,tx,cscl,val);
879         }
880
881       } /* Slices */
882     } /* Scanlines */
883   } /* Intervals */
884 } /* Function */
885
886
887
888
889
890
891
892 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in 
893    graphics gems I */
894
895 /*
896 struct stc {
897   int mylx,myrx; 
898   int dadlx,dadrx;
899   int myy;
900   int mydirection;
901 };
902
903 Not used code???
904 */
905
906
907 struct stack_element {
908   int myLx,myRx;
909   int dadLx,dadRx;
910   int myY;
911   int myDirection;
912 };
913
914
915 /* create the link data to put push onto the stack */
916
917 static
918 struct stack_element*
919 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
920   struct stack_element *ste;
921   ste=(struct stack_element*)mymalloc(sizeof(struct stack_element));
922   ste->myLx=left;
923   ste->myRx=right;
924   ste->dadLx=dadl;
925   ste->dadRx=dadr;
926   ste->myY=y;
927   ste->myDirection=dir;
928   return ste;
929 }
930
931 /* i_ccomp compares two colors and gives true if they are the same */
932
933 static int
934 i_ccomp(i_color *val1,i_color *val2,int ch) {
935   int i;
936   for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
937   return 1;
938 }
939
940
941 static int
942 i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
943   i_color cval;
944   while(1) {
945     if (seedx-1 < 0) break;
946     i_gpix(im,seedx-1,seedy,&cval);
947     if (!i_ccomp(val,&cval,im->channels)) break;
948     seedx--;
949   }
950   return seedx;
951 }
952
953 static int
954 i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
955   i_color cval;
956   while(1) {
957     if (seedx+1 > im->xsize-1) break;
958     i_gpix(im,seedx+1,seedy,&cval);
959     if (!i_ccomp(val,&cval,im->channels)) break;
960     seedx++;
961   }
962   return seedx;
963 }
964
965 /* Macro to create a link and push on to the list */
966
967 #define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s=crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s);}
968
969 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
970 /* No overflow check! */
971  
972 #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); }
973
974 #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); }
975
976 #define SET(x,y) btm_set(btm,x,y);
977
978 #define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels)  ) ))
979
980 void
981 i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
982
983   int lx,rx;
984   int y;
985   int direction;
986   int dadLx,dadRx;
987
988   int wasIn=0;
989   int x=0;
990
991   /*  int tx,ty; */
992
993   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
994
995   struct llist *st;
996   struct i_bitmap *btm;
997
998   int channels,xsize,ysize;
999   i_color cval,val;
1000
1001   channels=im->channels;
1002   xsize=im->xsize;
1003   ysize=im->ysize;
1004
1005   btm=btm_new(xsize,ysize);
1006   st=llist_new(100,sizeof(struct stack_element*));
1007
1008   /* Get the reference color */
1009   i_gpix(im,seedx,seedy,&val);
1010
1011   /* Find the starting span and fill it */
1012   lx=i_lspan(im,seedx,seedy,&val);
1013   rx=i_rspan(im,seedx,seedy,&val);
1014   
1015   /* printf("span: %d %d \n",lx,rx); */
1016
1017   for(x=lx;x<=rx;x++) SET(x,seedy);
1018
1019   ST_PUSH(lx,rx,lx,rx,seedy+1,1);
1020   ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
1021
1022   while(st->count) {
1023     ST_POP();
1024     
1025     if (y<0 || y>ysize-1) continue;
1026
1027     if (bymin > y) bymin=y; /* in the worst case an extra line */
1028     if (bymax < y) bymax=y; 
1029
1030     /*     printf("start of scan - on stack : %d \n",st->count); */
1031
1032     
1033     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
1034     
1035     /*
1036     printf(" ");
1037     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
1038     printf("\n");
1039     for(ty=0;ty<ysize;ty++) {
1040       printf("%d",ty%10);
1041       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
1042       printf("\n");
1043     }
1044
1045     printf("y=%d\n",y);
1046     */
1047
1048
1049     x=lx+1;
1050     if ( (wasIn = INSIDE(lx,y)) ) {
1051       SET(lx,y);
1052       lx--;
1053       while(INSIDE(lx,y) && lx > 0) {
1054         SET(lx,y);
1055         lx--;
1056       }
1057     }
1058
1059     if (bxmin > lx) bxmin=lx;
1060     
1061     while(x <= xsize-1) {
1062       /*  printf("x=%d\n",x); */
1063       if (wasIn) {
1064         
1065         if (INSIDE(x,y)) {
1066           /* case 1: was inside, am still inside */
1067           SET(x,y);
1068         } else {
1069           /* case 2: was inside, am no longer inside: just found the
1070              right edge of a span */
1071           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1072
1073           if (bxmax < x) bxmax=x;
1074
1075           wasIn=0;
1076         }
1077       } else {
1078         if (x>rx) goto EXT;
1079         if (INSIDE(x,y)) {
1080           SET(x,y);
1081           /* case 3: Wasn't inside, am now: just found the start of a new run */
1082           wasIn=1;
1083             lx=x;
1084         } else {
1085           /* case 4: Wasn't inside, still isn't */
1086         }
1087       }
1088       x++;
1089     }
1090   EXT: /* out of loop */
1091     if (wasIn) {
1092       /* hit an edge of the frame buffer while inside a run */
1093       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1094       if (bxmax < x) bxmax=x;
1095     }
1096   }
1097   
1098   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); 
1099        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
1100
1101   for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
1102
1103   btm_destroy(btm);
1104   llist_destroy(st);
1105 }