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