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