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