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