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