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