allow box() to accept floating colors for filling areas
[imager.git] / draw.c
1 #include "imager.h"
2 #include "draw.h"
3 #include "log.h"
4 #include "imageri.h"
5 #include "imrender.h"
6 #include <limits.h>
7
8 int
9 i_ppix_norm(i_img *im, i_img_dim x, i_img_dim y, i_color const *col) {
10   i_color src;
11   i_color work;
12   int dest_alpha;
13   int remains;
14
15   if (!col->channel[3])
16     return 0;
17
18   switch (im->channels) {
19   case 1:
20     work = *col;
21     i_adapt_colors(2, 4, &work, 1);
22     i_gpix(im, x, y, &src);
23     remains = 255 - work.channel[1];
24     src.channel[0] = (src.channel[0] * remains
25                       + work.channel[0] * work.channel[1]) / 255;
26     return i_ppix(im, x, y, &src);
27
28   case 2:
29     work = *col;
30     i_adapt_colors(2, 4, &work, 1);
31     i_gpix(im, x, y, &src);
32     dest_alpha = work.channel[1] + remains * src.channel[1] / 255;
33     if (work.channel[1] == 255) {
34       return i_ppix(im, x, y, &work);
35     }
36     else {
37       src.channel[0] = (work.channel[1] * work.channel[0]
38                         + remains * src.channel[0] * src.channel[1] / 255) / dest_alpha;
39       src.channel[1] = dest_alpha;
40       return i_ppix(im, x, y, &src);
41     }
42
43   case 3:
44     work = *col;
45     i_gpix(im, x, y, &src);
46     remains = 255 - work.channel[3];
47     src.channel[0] = (src.channel[0] * remains
48                       + work.channel[0] * work.channel[3]) / 255;
49     src.channel[1] = (src.channel[1] * remains
50                       + work.channel[1] * work.channel[3]) / 255;
51     src.channel[2] = (src.channel[2] * remains
52                       + work.channel[2] * work.channel[3]) / 255;
53     return i_ppix(im, x, y, &src);
54
55   case 4:
56     work = *col;
57     i_gpix(im, x, y, &src);
58     dest_alpha = work.channel[3] + remains * src.channel[3] / 255;
59     if (work.channel[3] == 255) {
60       return i_ppix(im, x, y, &work);
61     }
62     else {
63       src.channel[0] = (work.channel[3] * work.channel[0]
64                         + remains * src.channel[0] * src.channel[3] / 255) / dest_alpha;
65       src.channel[1] = (work.channel[3] * work.channel[1]
66                         + remains * src.channel[1] * src.channel[3] / 255) / dest_alpha;
67       src.channel[2] = (work.channel[3] * work.channel[2]
68                         + remains * src.channel[2] * src.channel[3] / 255) / dest_alpha;
69       src.channel[3] = dest_alpha;
70       return i_ppix(im, x, y, &src);
71     }
72   }
73   return 0;
74 }
75
76 static void
77 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm, 
78                int bxmin, int bxmax, int bymin, int bymax);
79
80 void
81 i_mmarray_cr(i_mmarray *ar,int l) {
82   int i;
83   int alloc_size;
84
85   ar->lines=l;
86   alloc_size = sizeof(minmax) * l;
87   /* check for overflow */
88   if (alloc_size / l != sizeof(minmax)) {
89     fprintf(stderr, "overflow calculating memory allocation");
90     exit(3);
91   }
92   ar->data=mymalloc(alloc_size); /* checked 5jul05 tonyc */
93   for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
94 }
95
96 void
97 i_mmarray_dst(i_mmarray *ar) {
98   ar->lines=0;
99   if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
100 }
101
102 void
103 i_mmarray_add(i_mmarray *ar,int x,int y) {
104   if (y>-1 && y<ar->lines)
105     {
106       if (x<ar->data[y].min) ar->data[y].min=x;
107       if (x>ar->data[y].max) ar->data[y].max=x;
108     }
109 }
110
111 int
112 i_mmarray_gmin(i_mmarray *ar,int y) {
113   if (y>-1 && y<ar->lines) return ar->data[y].min;
114   else return -1;
115 }
116
117 int
118 i_mmarray_getm(i_mmarray *ar,int y) {
119   if (y>-1 && y<ar->lines) return ar->data[y].max;
120   else return MAXINT;
121 }
122
123 void
124 i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
125   int i,x;
126   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);
127 }
128
129 static
130 void
131 i_arcdraw(int x1, int y1, int x2, int y2, i_mmarray *ar) {
132   double alpha;
133   double dsec;
134   int temp;
135   alpha=(double)(y2-y1)/(double)(x2-x1);
136   if (fabs(alpha) <= 1) 
137     {
138       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
139       dsec=y1;
140       while(x1<=x2)
141         {
142           i_mmarray_add(ar,x1,(int)(dsec+0.5));
143           dsec+=alpha;
144           x1++;
145         }
146     }
147   else
148     {
149       alpha=1/alpha;
150       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
151       dsec=x1;
152       while(y1<=y2)
153         {
154           i_mmarray_add(ar,(int)(dsec+0.5),y1);
155           dsec+=alpha;
156           y1++;
157         }
158     }
159 }
160
161 void
162 i_mmarray_info(i_mmarray *ar) {
163   int i;
164   for(i=0;i<ar->lines;i++)
165   if (ar->data[i].max!=-1) printf("line %d: min=%d, max=%d.\n",i,ar->data[i].min,ar->data[i].max);
166 }
167
168 static void
169 i_arc_minmax(i_int_hlines *hlines,int x,int y,float rad,float d1,float d2) {
170   i_mmarray dot;
171   float f,fx,fy;
172   int x1,y1;
173
174   /*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));*/
175
176   i_mmarray_cr(&dot, hlines->limit_y);
177
178   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
179   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
180   fx=(float)x1; fy=(float)y1;
181
182   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
183   i_arcdraw(x, y, x1, y1, &dot);
184
185   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
186   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
187
188   for(f=d1;f<=d2;f+=0.01) i_mmarray_add(&dot,(int)(x+0.5+rad*cos(f*PI/180.0)),(int)(y+0.5+rad*sin(f*PI/180.0)));
189   
190   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
191   i_arcdraw(x, y, x1, y1, &dot);
192
193   /* render the minmax values onto the hlines */
194   for (y = 0; y < dot.lines; y++) {
195     if (dot.data[y].max!=-1) {
196       int minx, width;
197       minx = dot.data[y].min;
198       width = dot.data[y].max - dot.data[y].min + 1;
199       i_int_hlines_add(hlines, y, minx, width);
200     }
201   }
202
203   /*  dot.info(); */
204   i_mmarray_dst(&dot);
205 }
206
207 static void
208 i_arc_hlines(i_int_hlines *hlines,int x,int y,float rad,float d1,float d2) {
209   if (d1 <= d2) {
210     i_arc_minmax(hlines, x, y, rad, d1, d2);
211   }
212   else {
213     i_arc_minmax(hlines, x, y, rad, d1, 360);
214     i_arc_minmax(hlines, x, y, rad, 0, d2);
215   }
216 }
217
218 /*
219 =item i_arc(im, x, y, rad, d1, d2, color)
220
221 =category Drawing
222 =synopsis i_arc(im, 50, 50, 20, 45, 135, &color);
223
224 Fills an arc centered at (x,y) with radius I<rad> covering the range
225 of angles in degrees from d1 to d2, with the color.
226
227 =cut
228 */
229
230 void
231 i_arc(i_img *im,int x,int y,float rad,float d1,float d2,const i_color *val) {
232   i_int_hlines hlines;
233
234   i_int_init_hlines_img(&hlines, im);
235
236   i_arc_hlines(&hlines, x, y, rad, d1, d2);
237
238   i_int_hlines_fill_color(im, &hlines, val);
239
240   i_int_hlines_destroy(&hlines);
241 }
242
243 /*
244 =item i_arc_cfill(im, x, y, rad, d1, d2, fill)
245
246 =category Drawing
247 =synopsis i_arc_cfill(im, 50, 50, 35, 90, 135, fill);
248
249 Fills an arc centered at (x,y) with radius I<rad> covering the range
250 of angles in degrees from d1 to d2, with the fill object.
251
252 =cut
253 */
254
255 #define MIN_CIRCLE_STEPS 8
256 #define MAX_CIRCLE_STEPS 360
257
258 void
259 i_arc_cfill(i_img *im,int x,int y,float rad,float d1,float d2,i_fill_t *fill) {
260   i_int_hlines hlines;
261
262   i_int_init_hlines_img(&hlines, im);
263
264   i_arc_hlines(&hlines, x, y, rad, d1, d2);
265
266   i_int_hlines_fill_fill(im, &hlines, fill);
267
268   i_int_hlines_destroy(&hlines);
269 }
270
271 static void
272 arc_poly(int *count, double **xvals, double **yvals,
273          double x, double y, double rad, double d1, double d2) {
274   double d1_rad, d2_rad;
275   double circum;
276   int steps, point_count;
277   double angle_inc;
278
279   /* normalize the angles */
280   d1 = fmod(d1, 360);
281   if (d1 == 0) {
282     if (d2 >= 360) { /* default is 361 */
283       d2 = 360;
284     }
285     else {
286       d2 = fmod(d2, 360);
287       if (d2 < d1)
288         d2 += 360;
289     }
290   }
291   else {
292     d2 = fmod(d2, 360);
293     if (d2 < d1)
294       d2 += 360;
295   }
296   d1_rad = d1 * PI / 180;
297   d2_rad = d2 * PI / 180;
298
299   /* how many segments for the curved part? 
300      we do a maximum of one per degree, with a minimum of 8/circle
301      we try to aim at having about one segment per 2 pixels
302      Work it out per circle to get a step size.
303
304      I was originally making steps = circum/2 but that looked horrible.
305
306      I think there might be an issue in the polygon filler.
307   */
308   circum = 2 * PI * rad;
309   steps = circum;
310   if (steps > MAX_CIRCLE_STEPS)
311     steps = MAX_CIRCLE_STEPS;
312   else if (steps < MIN_CIRCLE_STEPS)
313     steps = MIN_CIRCLE_STEPS;
314
315   angle_inc = 2 * PI / steps;
316
317   point_count = steps + 5; /* rough */
318   /* point_count is always relatively small, so allocation won't overflow */
319   *xvals = mymalloc(point_count * sizeof(double)); /* checked 17feb2005 tonyc */
320   *yvals = mymalloc(point_count * sizeof(double)); /* checked 17feb2005 tonyc */
321
322   /* from centre to edge at d1 */
323   (*xvals)[0] = x;
324   (*yvals)[0] = y;
325   (*xvals)[1] = x + rad * cos(d1_rad);
326   (*yvals)[1] = y + rad * sin(d1_rad);
327   *count = 2;
328
329   /* step around the curve */
330   while (d1_rad < d2_rad) {
331     (*xvals)[*count] = x + rad * cos(d1_rad);
332     (*yvals)[*count] = y + rad * sin(d1_rad);
333     ++*count;
334     d1_rad += angle_inc;
335   }
336
337   /* finish off the curve */
338   (*xvals)[*count] = x + rad * cos(d2_rad);
339   (*yvals)[*count] = y + rad * sin(d2_rad);
340   ++*count;
341 }
342
343 /*
344 =item i_arc_aa(im, x, y, rad, d1, d2, color)
345
346 =category Drawing
347 =synopsis i_arc_aa(im, 50, 50, 35, 90, 135, &color);
348
349 Anti-alias fills an arc centered at (x,y) with radius I<rad> covering
350 the range of angles in degrees from d1 to d2, with the color.
351
352 =cut
353 */
354
355 void
356 i_arc_aa(i_img *im, double x, double y, double rad, double d1, double d2,
357          const i_color *val) {
358   double *xvals, *yvals;
359   int count;
360
361   arc_poly(&count, &xvals, &yvals, x, y, rad, d1, d2);
362
363   i_poly_aa(im, count, xvals, yvals, val);
364
365   myfree(xvals);
366   myfree(yvals);
367 }
368
369 /*
370 =item i_arc_aa_cfill(im, x, y, rad, d1, d2, fill)
371
372 =category Drawing
373 =synopsis i_arc_aa_cfill(im, 50, 50, 35, 90, 135, fill);
374
375 Anti-alias fills an arc centered at (x,y) with radius I<rad> covering
376 the range of angles in degrees from d1 to d2, with the fill object.
377
378 =cut
379 */
380
381 void
382 i_arc_aa_cfill(i_img *im, double x, double y, double rad, double d1, double d2,
383                i_fill_t *fill) {
384   double *xvals, *yvals;
385   int count;
386
387   arc_poly(&count, &xvals, &yvals, x, y, rad, d1, d2);
388
389   i_poly_aa_cfill(im, count, xvals, yvals, fill);
390
391   myfree(xvals);
392   myfree(yvals);
393 }
394
395 /* Temporary AA HACK */
396
397
398 typedef int frac;
399 static  frac float_to_frac(float x) { return (frac)(0.5+x*16.0); }
400
401 static 
402 void
403 polar_to_plane(float cx, float cy, float angle, float radius, frac *x, frac *y) {
404   *x = float_to_frac(cx+radius*cos(angle));
405   *y = float_to_frac(cy+radius*sin(angle));
406 }
407
408 static
409 void
410 make_minmax_list(i_mmarray *dot, float x, float y, float radius) {
411   float angle = 0.0;
412   float astep = radius>0.1 ? .5/radius : 10;
413   frac cx, cy, lx, ly, sx, sy;
414
415   mm_log((1, "make_minmax_list(dot %p, x %.2f, y %.2f, radius %.2f)\n", dot, x, y, radius));
416
417   polar_to_plane(x, y, angle, radius, &sx, &sy);
418   
419   for(angle = 0.0; angle<361; angle +=astep) {
420     lx = sx; ly = sy;
421     polar_to_plane(x, y, angle, radius, &cx, &cy);
422     sx = cx; sy = cy;
423
424     if (fabs(cx-lx) > fabs(cy-ly)) {
425       int ccx, ccy;
426       if (lx>cx) { 
427         ccx = lx; lx = cx; cx = ccx; 
428         ccy = ly; ly = cy; cy = ccy; 
429       }
430
431       for(ccx=lx; ccx<=cx; ccx++) {
432         ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
433         i_mmarray_add(dot, ccx, ccy);
434       }
435     } else {
436       int ccx, ccy;
437
438       if (ly>cy) { 
439         ccy = ly; ly = cy; cy = ccy; 
440         ccx = lx; lx = cx; cx = ccx; 
441       }
442       
443       for(ccy=ly; ccy<=cy; ccy++) {
444         if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
445         i_mmarray_add(dot, ccx, ccy);
446       }
447     }
448   }
449 }
450
451 /* Get the number of subpixels covered */
452
453 static
454 int
455 i_pixel_coverage(i_mmarray *dot, int x, int y) {
456   frac minx = x*16;
457   frac maxx = minx+15;
458   frac cy;
459   int cnt = 0;
460   
461   for(cy=y*16; cy<(y+1)*16; cy++) {
462     frac tmin = dot->data[cy].min;
463     frac tmax = dot->data[cy].max;
464
465     if (tmax == -1 || tmin > maxx || tmax < minx) continue;
466     
467     if (tmin < minx) tmin = minx;
468     if (tmax > maxx) tmax = maxx;
469     
470     cnt+=1+tmax-tmin;
471   }
472   return cnt;
473 }
474
475 /*
476 =item i_circle_aa(im, x, y, rad, color)
477
478 =category Drawing
479 =synopsis i_circle_aa(im, 50, 50, 45, &color);
480
481 Anti-alias fills a circle centered at (x,y) for radius I<rad> with
482 color.
483
484 =cut
485 */
486 void
487 i_circle_aa(i_img *im, float x, float y, float rad, const i_color *val) {
488   i_mmarray dot;
489   i_color temp;
490   int ly;
491
492   mm_log((1, "i_circle_aa(im %p, x %d, y %d, rad %.2f, val %p)\n", im, x, y, rad, val));
493
494   i_mmarray_cr(&dot,16*im->ysize);
495   make_minmax_list(&dot, x, y, rad);
496
497   for(ly = 0; ly<im->ysize; ly++) {
498     int ix, cy, minx = INT_MAX, maxx = INT_MIN;
499
500     /* Find the left/rightmost set subpixels */
501     for(cy = 0; cy<16; cy++) {
502       frac tmin = dot.data[ly*16+cy].min;
503       frac tmax = dot.data[ly*16+cy].max;
504       if (tmax == -1) continue;
505
506       if (minx > tmin) minx = tmin;
507       if (maxx < tmax) maxx = tmax;
508     }
509
510     if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
511
512     minx /= 16;
513     maxx /= 16;
514     for(ix=minx; ix<=maxx; ix++) {
515       int cnt = i_pixel_coverage(&dot, ix, ly);
516       if (cnt>255) cnt = 255;
517       if (cnt) { /* should never be true */
518         int ch;
519         float ratio = (float)cnt/255.0;
520         i_gpix(im, ix, ly, &temp);
521         for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
522         i_ppix(im, ix, ly, &temp);
523       }
524     }
525   }
526   i_mmarray_dst(&dot);
527 }
528
529 /*
530 =item i_circle_out(im, x, y, r, col)
531
532 =category Drawing
533 =synopsis i_circle_out(im, 50, 50, 45, &color);
534
535 Draw a circle outline centered at (x,y) with radius r,
536 non-anti-aliased.
537
538 Parameters:
539
540 =over
541
542 =item *
543
544 (x, y) - the center of the circle
545
546 =item *
547
548 r - the radius of the circle in pixels, must be non-negative
549
550 =back
551
552 Returns non-zero on success.
553
554 Implementation:
555
556 =cut
557 */
558
559 int
560 i_circle_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
561              const i_color *col) {
562   i_img_dim x, y;
563   i_img_dim dx, dy;
564   int error;
565
566   i_clear_error();
567
568   if (r < 0) {
569     i_push_error(0, "circle: radius must be non-negative");
570     return 0;
571   }
572
573   i_ppix(im, xc+r, yc, col);
574   i_ppix(im, xc-r, yc, col);
575   i_ppix(im, xc, yc+r, col);
576   i_ppix(im, xc, yc-r, col);
577
578   x = 0;
579   y = r;
580   dx = 1;
581   dy = -2 * r;
582   error = 1 - r;
583   while (x < y) {
584     if (error >= 0) {
585       --y;
586       dy += 2;
587       error += dy;
588     }
589     ++x;
590     dx += 2;
591     error += dx;
592
593     i_ppix(im, xc + x, yc + y, col);
594     i_ppix(im, xc + x, yc - y, col);
595     i_ppix(im, xc - x, yc + y, col);
596     i_ppix(im, xc - x, yc - y, col);
597     if (x != y) {
598       i_ppix(im, xc + y, yc + x, col);
599       i_ppix(im, xc + y, yc - x, col);
600       i_ppix(im, xc - y, yc + x, col);
601       i_ppix(im, xc - y, yc - x, col);
602     }
603   }
604
605   return 1;
606 }
607
608 /*
609 =item arc_seg(angle)
610
611 Convert an angle in degrees into an angle measure we can generate
612 simply from the numbers we have when drawing the circle.
613
614 =back
615 */
616
617 static i_img_dim
618 arc_seg(double angle, int scale) {
619   i_img_dim seg = (angle + 45) / 90;
620   double remains = angle - seg * 90; /* should be in the range [-45,45] */
621   int sign = remains < 0 ? -1 : remains ? 1 : 0;
622
623   while (seg > 4)
624     seg -= 4;
625   if (seg == 4 && remains > 0)
626     seg = 0;
627
628   return scale * (seg * 2 + sin(remains * PI/180));
629 }
630
631 /*
632 =item i_arc_out(im, x, y, r, d1, d2, col)
633
634 =category Drawing
635 =synopsis i_arc_out(im, 50, 50, 45, 45, 135, &color);
636
637 Draw an arc outline centered at (x,y) with radius r, non-anti-aliased
638 over the angle range d1 through d2 degrees.
639
640 Parameters:
641
642 =over
643
644 =item *
645
646 (x, y) - the center of the circle
647
648 =item *
649
650 r - the radius of the circle in pixels, must be non-negative
651
652 =item *
653
654 d1, d2 - the range of angles to draw the arc over, in degrees.
655
656 =back
657
658 Returns non-zero on success.
659
660 Implementation:
661
662 =cut
663 */
664
665 int
666 i_arc_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
667           float d1, float d2, const i_color *col) {
668   i_img_dim x, y;
669   i_img_dim dx, dy;
670   int error;
671   i_img_dim segs[2][2];
672   int seg_count;
673   i_img_dim sin_th;
674   i_img_dim seg_d1, seg_d2;
675   int seg_num;
676   double inv_r;
677   i_img_dim scale = r + 1;
678   i_img_dim seg1 = scale * 2;
679   i_img_dim seg2 = scale * 4;
680   i_img_dim seg3 = scale * 6;
681   i_img_dim seg4 = scale * 8;
682
683   i_clear_error();
684
685   if (r <= 0) {
686     i_push_error(0, "arc: radius must be non-negative");
687     return 0;
688   }
689   if (d1 + 360 <= d2)
690     return i_circle_out(im, xc, yc, r, col);
691
692   if (d1 < 0)
693     d1 += 360 * floor((-d1 + 359) / 360);
694   if (d2 < 0)
695     d2 += 360 * floor((-d2 + 359) / 360);
696   d1 = fmod(d1, 360);
697   d2 = fmod(d2, 360);
698   seg_d1 = arc_seg(d1, scale);
699   seg_d2 = arc_seg(d2, scale);
700   if (seg_d2 < seg_d1) {
701     /* split into two segments */
702     segs[0][0] = 0;
703     segs[0][1] = seg_d2;
704     segs[1][0] = seg_d1;
705     segs[1][1] = seg4;
706     seg_count = 2;
707   }
708   else {
709     segs[0][0] = seg_d1;
710     segs[0][1] = seg_d2;
711     seg_count = 1;
712   }
713
714   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
715     i_img_dim seg_start = segs[seg_num][0];
716     i_img_dim seg_end = segs[seg_num][1];
717     if (seg_start == 0)
718       i_ppix(im, xc+r, yc, col);
719     if (seg_start <= seg1 && seg_end >= seg1)
720       i_ppix(im, xc, yc+r, col);
721     if (seg_start <= seg2 && seg_end >= seg2)
722       i_ppix(im, xc-r, yc, col);
723     if (seg_start <= seg3 && seg_end >= seg3)
724       i_ppix(im, xc, yc-r, col);
725
726     y = 0;
727     x = r;
728     dy = 1;
729     dx = -2 * r;
730     error = 1 - r;
731     while (y < x) {
732       if (error >= 0) {
733         --x;
734         dx += 2;
735         error += dx;
736       }
737       ++y;
738       dy += 2;
739       error += dy;
740       
741       sin_th = y;
742       if (seg_start <= sin_th && seg_end >= sin_th)
743         i_ppix(im, xc + x, yc + y, col);
744       if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
745         i_ppix(im, xc + y, yc + x, col);
746
747       if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
748         i_ppix(im, xc - y, yc + x, col);
749       if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
750         i_ppix(im, xc - x, yc + y, col);
751       
752       if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
753         i_ppix(im, xc - x, yc - y, col);
754       if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
755         i_ppix(im, xc - y, yc - x, col);
756
757       if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
758         i_ppix(im, xc + y, yc - x, col);
759       if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
760         i_ppix(im, xc + x, yc - y, col);
761     }
762   }
763
764   return 1;
765 }
766
767 static double
768 cover(i_img_dim r, i_img_dim j) {
769   float rjsqrt = sqrt(r*r - j*j);
770
771   return ceil(rjsqrt) - rjsqrt;
772 }
773
774 /*
775 =item i_circle_out_aa(im, xc, yc, r, col)
776
777 =synopsis i_circle_out_aa(im, 50, 50, 45, &color);
778
779 Draw a circle outline centered at (x,y) with radius r, anti-aliased.
780
781 Parameters:
782
783 =over
784
785 =item *
786
787 (xc, yc) - the center of the circle
788
789 =item *
790
791 r - the radius of the circle in pixels, must be non-negative
792
793 =item *
794
795 col - an i_color for the color to draw in.
796
797 =back
798
799 Returns non-zero on success.
800
801 =cut
802
803 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
804 Gems.
805
806 I use floating point for I<D> since for large circles the precision of
807 a [0,255] value isn't sufficient when approaching the end of the
808 octant.
809
810 */
811
812 int
813 i_circle_out_aa(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r, const i_color *col) {
814   i_img_dim i, j;
815   double t;
816   i_color workc = *col;
817   int orig_alpha = col->channel[3];
818
819   i_clear_error();
820   if (r <= 0) {
821     i_push_error(0, "arc: radius must be non-negative");
822     return 0;
823   }
824   i = r;
825   j = 0;
826   t = 0;
827   i_ppix_norm(im, xc+i, yc+j, col);
828   i_ppix_norm(im, xc-i, yc+j, col);
829   i_ppix_norm(im, xc+j, yc+i, col);
830   i_ppix_norm(im, xc+j, yc-i, col);
831
832   while (i > j+1) {
833     double d;
834     int cv, inv_cv;
835     i_color p;
836     int ch;
837     j++;
838     d = cover(r, j);
839     cv = (int)(d * 255 + 0.5);
840     inv_cv = 255-cv;
841     if (d < t) {
842       --i;
843     }
844     if (inv_cv) {
845       workc.channel[3] = orig_alpha * inv_cv / 255;
846       i_ppix_norm(im, xc+i, yc+j, &workc);
847       i_ppix_norm(im, xc-i, yc+j, &workc);
848       i_ppix_norm(im, xc+i, yc-j, &workc);
849       i_ppix_norm(im, xc-i, yc-j, &workc);
850
851       if (i != j) {
852         i_ppix_norm(im, xc+j, yc+i, &workc);
853         i_ppix_norm(im, xc-j, yc+i, &workc);
854         i_ppix_norm(im, xc+j, yc-i, &workc);
855         i_ppix_norm(im, xc-j, yc-i, &workc);
856       }
857     }
858     if (cv && i > j) {
859       workc.channel[3] = orig_alpha * cv / 255;
860       i_ppix_norm(im, xc+i-1, yc+j, &workc);
861       i_ppix_norm(im, xc-i+1, yc+j, &workc);
862       i_ppix_norm(im, xc+i-1, yc-j, &workc);
863       i_ppix_norm(im, xc-i+1, yc-j, &workc);
864
865       if (j != i-1) {
866         i_ppix_norm(im, xc+j, yc+i-1, &workc);
867         i_ppix_norm(im, xc-j, yc+i-1, &workc);
868         i_ppix_norm(im, xc+j, yc-i+1, &workc);
869         i_ppix_norm(im, xc-j, yc-i+1, &workc);
870       }
871     }
872     t = d;
873   }
874
875   return 1;
876 }
877
878 /*
879 =item i_arc_out_aa(im, xc, yc, r, d1, d2, col)
880
881 =synopsis i_arc_out_aa(im, 50, 50, 45, 45, 125, &color);
882
883 Draw a circle arc outline centered at (x,y) with radius r, from angle
884 d1 degrees through angle d2 degrees, anti-aliased.
885
886 Parameters:
887
888 =over
889
890 =item *
891
892 (xc, yc) - the center of the circle
893
894 =item *
895
896 r - the radius of the circle in pixels, must be non-negative
897
898 =item *
899
900 d1, d2 - the range of angle in degrees to draw the arc through.  If
901 d2-d1 >= 360 a full circle is drawn.
902
903 =back
904
905 Returns non-zero on success.
906
907 =cut
908
909 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
910 Gems.
911
912 */
913
914 int
915 i_arc_out_aa(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r, float d1, float d2, const i_color *col) {
916   i_img_dim i, j;
917   double t;
918   i_color workc = *col;
919   i_img_dim segs[2][2];
920   int seg_count;
921   i_img_dim sin_th;
922   i_img_dim seg_d1, seg_d2;
923   int seg_num;
924   int orig_alpha = col->channel[3];
925   i_img_dim scale = r + 1;
926   i_img_dim seg1 = scale * 2;
927   i_img_dim seg2 = scale * 4;
928   i_img_dim seg3 = scale * 6;
929   i_img_dim seg4 = scale * 8;
930
931   i_clear_error();
932   if (r <= 0) {
933     i_push_error(0, "arc: radius must be non-negative");
934     return 0;
935   }
936   if (d1 + 360 <= d2)
937     return i_circle_out_aa(im, xc, yc, r, col);
938
939   if (d1 < 0)
940     d1 += 360 * floor((-d1 + 359) / 360);
941   if (d2 < 0)
942     d2 += 360 * floor((-d2 + 359) / 360);
943   d1 = fmod(d1, 360);
944   d2 = fmod(d2, 360);
945   seg_d1 = arc_seg(d1, scale);
946   seg_d2 = arc_seg(d2, scale);
947   if (seg_d2 < seg_d1) {
948     /* split into two segments */
949     segs[0][0] = 0;
950     segs[0][1] = seg_d2;
951     segs[1][0] = seg_d1;
952     segs[1][1] = seg4;
953     seg_count = 2;
954   }
955   else {
956     segs[0][0] = seg_d1;
957     segs[0][1] = seg_d2;
958     seg_count = 1;
959   }
960
961   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
962     i_img_dim seg_start = segs[seg_num][0];
963     i_img_dim seg_end = segs[seg_num][1];
964
965     i = r;
966     j = 0;
967     t = 0;
968
969     if (seg_start == 0)
970       i_ppix_norm(im, xc+i, yc+j, col);
971     if (seg_start <= seg1 && seg_end >= seg1)
972       i_ppix_norm(im, xc+j, yc+i, col);
973     if (seg_start <= seg2 && seg_end >= seg2)
974       i_ppix_norm(im, xc-i, yc+j, col);
975     if (seg_start <= seg3 && seg_end >= seg3)
976       i_ppix_norm(im, xc+j, yc-i, col);
977     
978     while (i > j+1) {
979       int cv, inv_cv;
980       i_color p;
981       int ch;
982       double d;
983       j++;
984       d = cover(r, j);
985       cv = (int)(d * 255 + 0.5);
986       inv_cv = 255-cv;
987       if (d < t) {
988         --i;
989       }
990       sin_th = j;
991       if (inv_cv) {
992         workc.channel[3] = orig_alpha * inv_cv / 255;
993
994         if (seg_start <= sin_th && seg_end >= sin_th)
995           i_ppix_norm(im, xc+i, yc+j, &workc);
996         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
997           i_ppix_norm(im, xc-i, yc+j, &workc);
998         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
999           i_ppix_norm(im, xc+i, yc-j, &workc);
1000         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1001           i_ppix_norm(im, xc-i, yc-j, &workc);
1002         
1003         if (i != j) {
1004           if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1005             i_ppix_norm(im, xc+j, yc+i, &workc);
1006           if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1007             i_ppix_norm(im, xc-j, yc+i, &workc);
1008           if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1009             i_ppix_norm(im, xc+j, yc-i, &workc);
1010           if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1011             i_ppix_norm(im, xc-j, yc-i, &workc);
1012         }
1013       }
1014       if (cv && i > j) {
1015         workc.channel[3] = orig_alpha * cv / 255;
1016         if (seg_start <= sin_th && seg_end >= sin_th)
1017           i_ppix_norm(im, xc+i-1, yc+j, &workc);
1018         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1019           i_ppix_norm(im, xc-i+1, yc+j, &workc);
1020         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1021           i_ppix_norm(im, xc+i-1, yc-j, &workc);
1022         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1023           i_ppix_norm(im, xc-i+1, yc-j, &workc);
1024         
1025         if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1026           i_ppix_norm(im, xc+j, yc+i-1, &workc);
1027         if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1028           i_ppix_norm(im, xc-j, yc+i-1, &workc);
1029         if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1030           i_ppix_norm(im, xc+j, yc-i+1, &workc);
1031         if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1032           i_ppix_norm(im, xc-j, yc-i+1, &workc);
1033       }
1034       t = d;
1035     }
1036   }
1037
1038   return 1;
1039 }
1040
1041 /*
1042 =item i_box(im, x1, y1, x2, y2, color)
1043
1044 =category Drawing
1045 =synopsis i_box(im, 0, 0, im->xsize-1, im->ysize-1, &color).
1046
1047 Outlines the box from (x1,y1) to (x2,y2) inclusive with I<color>.
1048
1049 =cut
1050 */
1051
1052 void
1053 i_box(i_img *im,int x1,int y1,int x2,int y2,const i_color *val) {
1054   int x,y;
1055   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));
1056   for(x=x1;x<x2+1;x++) {
1057     i_ppix(im,x,y1,val);
1058     i_ppix(im,x,y2,val);
1059   }
1060   for(y=y1;y<y2+1;y++) {
1061     i_ppix(im,x1,y,val);
1062     i_ppix(im,x2,y,val);
1063   }
1064 }
1065
1066 /*
1067 =item i_box_filled(im, x1, y1, x2, y2, color)
1068
1069 =category Drawing
1070 =synopsis i_box_filled(im, 0, 0, im->xsize-1, im->ysize-1, &color);
1071
1072 Fills the box from (x1,y1) to (x2,y2) inclusive with color.
1073
1074 =cut
1075 */
1076
1077 void
1078 i_box_filled(i_img *im,int x1,int y1,int x2,int y2, const i_color *val) {
1079   i_img_dim x, y, width;
1080   i_palidx index;
1081
1082   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));
1083
1084   if (x1 > x2 || y1 > y2
1085       || x2 < 0 || y2 < 0
1086       || x1 >= im->xsize || y1 > im->ysize)
1087     return;
1088
1089   if (x1 < 0)
1090     x1 = 0;
1091   if (x2 >= im->xsize)
1092     x2 = im->xsize - 1;
1093   if (y1 < 0)
1094     y1 = 0;
1095   if (y2 >= im->ysize)
1096     y2 = im->ysize - 1;
1097
1098   width = x2 - x1 + 1;
1099
1100   if (im->type == i_palette_type
1101       && i_findcolor(im, val, &index)) {
1102     i_palidx *line = mymalloc(sizeof(i_palidx) * width);
1103
1104     for (x = 0; x < width; ++x)
1105       line[x] = index;
1106
1107     for (y = y1; y <= y2; ++y)
1108       i_ppal(im, x1, x2+1, y, line);
1109
1110     myfree(line);
1111   }
1112   else {
1113     i_color *line = mymalloc(sizeof(i_color) * width);
1114
1115     for (x = 0; x < width; ++x)
1116       line[x] = *val;
1117
1118     for (y = y1; y <= y2; ++y)
1119       i_plin(im, x1, x2+1, y, line);
1120
1121     myfree(line);
1122   }
1123 }
1124
1125 /*
1126 =item i_box_filledf(im, x1, y1, x2, y2, color)
1127
1128 =category Drawing
1129 =synopsis i_box_filledf(im, 0, 0, im->xsize-1, im->ysize-1, &fcolor);
1130
1131 Fills the box from (x1,y1) to (x2,y2) inclusive with a floating point
1132 color.
1133
1134 =cut
1135 */
1136
1137 int
1138 i_box_filledf(i_img *im,int x1,int y1,int x2,int y2, const i_fcolor *val) {
1139   i_img_dim x, y, width;
1140   i_palidx index;
1141
1142   mm_log((1,"i_box_filledf(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
1143
1144   if (x1 > x2 || y1 > y2
1145       || x2 < 0 || y2 < 0
1146       || x1 >= im->xsize || y1 > im->ysize)
1147     return 0;
1148
1149   if (x1 < 0)
1150     x1 = 0;
1151   if (x2 >= im->xsize)
1152     x2 = im->xsize - 1;
1153   if (y1 < 0)
1154     y1 = 0;
1155   if (y2 >= im->ysize)
1156     y2 = im->ysize - 1;
1157
1158   width = x2 - x1 + 1;
1159
1160   if (im->bits <= 8) {
1161     i_color c;
1162     c.rgba.r = SampleFTo8(val->rgba.r);
1163     c.rgba.g = SampleFTo8(val->rgba.g);
1164     c.rgba.b = SampleFTo8(val->rgba.b);
1165     c.rgba.a = SampleFTo8(val->rgba.a);
1166
1167     i_box_filled(im, x1, y1, x2, y2, &c);
1168   }
1169   else {
1170     i_fcolor *line = mymalloc(sizeof(i_fcolor) * width);
1171     
1172     for (x = 0; x < width; ++x)
1173       line[x] = *val;
1174     
1175     for (y = y1; y <= y2; ++y)
1176       i_plinf(im, x1, x2+1, y, line);
1177     
1178     myfree(line);
1179   }
1180   
1181   return 1;
1182 }
1183
1184 /*
1185 =item i_box_cfill(im, x1, y1, x2, y2, fill)
1186
1187 =category Drawing
1188 =synopsis i_box_cfill(im, 0, 0, im->xsize-1, im->ysize-1, fill);
1189
1190 Fills the box from (x1,y1) to (x2,y2) inclusive with fill.
1191
1192 =cut
1193 */
1194
1195 void
1196 i_box_cfill(i_img *im,int x1,int y1,int x2,int y2,i_fill_t *fill) {
1197   i_render r;
1198   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));
1199
1200   ++x2;
1201   if (x1 < 0)
1202     x1 = 0;
1203   if (y1 < 0) 
1204     y1 = 0;
1205   if (x2 > im->xsize) 
1206     x2 = im->xsize;
1207   if (y2 >= im->ysize)
1208     y2 = im->ysize-1;
1209   if (x1 >= x2 || y1 > y2)
1210     return;
1211
1212   i_render_init(&r, im, x2-x1);
1213   while (y1 <= y2) {
1214     i_render_fill(&r, x1, y1, x2-x1, NULL, fill);
1215     ++y1;
1216   }
1217   i_render_done(&r);
1218 }
1219
1220 /* 
1221 =item i_line(C<im>, C<x1>, C<y1>, C<x2>, C<y2>, C<color>, C<endp>)
1222
1223 =category Drawing
1224
1225 =for stopwords Bresenham's
1226
1227 Draw a line to image using Bresenham's line drawing algorithm
1228
1229    im    - image to draw to
1230    x1    - starting x coordinate
1231    y1    - starting x coordinate
1232    x2    - starting x coordinate
1233    y2    - starting x coordinate
1234    color - color to write to image
1235    endp  - endpoint flag (boolean)
1236
1237 =cut
1238 */
1239
1240 void
1241 i_line(i_img *im, int x1, int y1, int x2, int y2, const i_color *val, int endp) {
1242   int x, y;
1243   int dx, dy;
1244   int p;
1245
1246   dx = x2 - x1;
1247   dy = y2 - y1;
1248
1249
1250   /* choose variable to iterate on */
1251   if (abs(dx)>abs(dy)) {
1252     int dx2, dy2, cpy;
1253
1254     /* sort by x */
1255     if (x1 > x2) {
1256       int t;
1257       t = x1; x1 = x2; x2 = t;
1258       t = y1; y1 = y2; y2 = t;
1259     }
1260     
1261     dx = abs(dx);
1262     dx2 = dx*2;
1263     dy = y2 - y1;
1264
1265     if (dy<0) {
1266       dy = -dy;
1267       cpy = -1;
1268     } else {
1269       cpy = 1;
1270     }
1271     dy2 = dy*2;
1272     p = dy2 - dx;
1273
1274     
1275     y = y1;
1276     for(x=x1; x<x2-1; x++) {
1277       if (p<0) {
1278         p += dy2;
1279       } else {
1280         y += cpy;
1281         p += dy2-dx2;
1282       }
1283       i_ppix(im, x+1, y, val);
1284     }
1285   } else {
1286     int dy2, dx2, cpx;
1287
1288     /* sort bx y */
1289     if (y1 > y2) {
1290       int t;
1291       t = x1; x1 = x2; x2 = t;
1292       t = y1; y1 = y2; y2 = t;
1293     }
1294     
1295     dy = abs(dy);
1296     dx = x2 - x1;
1297     dy2 = dy*2;
1298
1299     if (dx<0) {
1300       dx = -dx;
1301       cpx = -1;
1302     } else {
1303       cpx = 1;
1304     }
1305     dx2 = dx*2;
1306     p = dx2 - dy;
1307
1308     x = x1;
1309     
1310     for(y=y1; y<y2-1; y++) {
1311       if (p<0) {
1312         p  += dx2;
1313       } else {
1314         x += cpx;
1315         p += dx2-dy2;
1316       }
1317       i_ppix(im, x, y+1, val);
1318     }
1319   }
1320   if (endp) {
1321     i_ppix(im, x1, y1, val);
1322     i_ppix(im, x2, y2, val);
1323   } else {
1324     if (x1 != x2 || y1 != y2) 
1325       i_ppix(im, x1, y1, val);
1326   }
1327 }
1328
1329
1330 void
1331 i_line_dda(i_img *im, int x1, int y1, int x2, int y2, i_color *val) {
1332
1333   float dy;
1334   int x;
1335   
1336   for(x=x1; x<=x2; x++) {
1337     dy = y1+ (x-x1)/(float)(x2-x1)*(y2-y1);
1338     i_ppix(im, x, (int)(dy+0.5), val);
1339   }
1340 }
1341
1342 /*
1343 =item i_line_aa(C<im>, C<x1>, C<x2>, C<y1>, C<y2>, C<color>, C<endp>)
1344
1345 =category Drawing
1346
1347 Anti-alias draws a line from (x1,y1) to (x2, y2) in color.
1348
1349 The point (x2, y2) is drawn only if C<endp> is set.
1350
1351 =cut
1352 */
1353
1354 void
1355 i_line_aa(i_img *im, int x1, int y1, int x2, int y2, const i_color *val, int endp) {
1356   int x, y;
1357   int dx, dy;
1358   int p;
1359
1360   dx = x2 - x1;
1361   dy = y2 - y1;
1362
1363   /* choose variable to iterate on */
1364   if (abs(dx)>abs(dy)) {
1365     int dx2, dy2, cpy;
1366     
1367     /* sort by x */
1368     if (x1 > x2) {
1369       int t;
1370       t = x1; x1 = x2; x2 = t;
1371       t = y1; y1 = y2; y2 = t;
1372     }
1373     
1374     dx = abs(dx);
1375     dx2 = dx*2;
1376     dy = y2 - y1;
1377
1378     if (dy<0) {
1379       dy = -dy;
1380       cpy = -1;
1381     } else {
1382       cpy = 1;
1383     }
1384     dy2 = dy*2;
1385     p = dy2 - dx2; /* this has to be like this for AA */
1386     
1387     y = y1;
1388
1389     for(x=x1; x<x2-1; x++) {
1390       int ch;
1391       i_color tval;
1392       float t = (dy) ? -(float)(p)/(float)(dx2) : 1;
1393       float t1, t2;
1394
1395       if (t<0) t = 0;
1396       t1 = 1-t;
1397       t2 = t;
1398
1399       i_gpix(im,x+1,y,&tval);
1400       for(ch=0;ch<im->channels;ch++)
1401         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
1402       i_ppix(im,x+1,y,&tval);
1403
1404       i_gpix(im,x+1,y+cpy,&tval);
1405       for(ch=0;ch<im->channels;ch++)
1406         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
1407       i_ppix(im,x+1,y+cpy,&tval);
1408
1409       if (p<0) {
1410         p += dy2;
1411       } else {
1412         y += cpy;
1413         p += dy2-dx2;
1414       }
1415     }
1416   } else {
1417     int dy2, dx2, cpx;
1418
1419     /* sort bx y */
1420     if (y1 > y2) {
1421       int t;
1422       t = x1; x1 = x2; x2 = t;
1423       t = y1; y1 = y2; y2 = t;
1424     }
1425     
1426     dy = abs(dy);
1427     dx = x2 - x1;
1428     dy2 = dy*2;
1429
1430     if (dx<0) {
1431       dx = -dx;
1432       cpx = -1;
1433     } else {
1434       cpx = 1;
1435     }
1436     dx2 = dx*2;
1437     p = dx2 - dy2; /* this has to be like this for AA */
1438
1439     x = x1;
1440     
1441     for(y=y1; y<y2-1; y++) {
1442       int ch;
1443       i_color tval;
1444       float t = (dx) ? -(float)(p)/(float)(dy2) : 1;
1445       float t1, t2;
1446       
1447       if (t<0) t = 0;
1448       t1 = 1-t;
1449       t2 = t;
1450
1451       i_gpix(im,x,y+1,&tval);
1452       for(ch=0;ch<im->channels;ch++)
1453         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
1454       i_ppix(im,x,y+1,&tval);
1455
1456       i_gpix(im,x+cpx,y+1,&tval);
1457       for(ch=0;ch<im->channels;ch++)
1458         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
1459       i_ppix(im,x+cpx,y+1,&tval);
1460
1461       if (p<0) {
1462         p  += dx2;
1463       } else {
1464         x += cpx;
1465         p += dx2-dy2;
1466       }
1467     }
1468   }
1469
1470
1471   if (endp) {
1472     i_ppix(im, x1, y1, val);
1473     i_ppix(im, x2, y2, val);
1474   } else {
1475     if (x1 != x2 || y1 != y2) 
1476       i_ppix(im, x1, y1, val);
1477   }
1478 }
1479
1480
1481
1482 static double
1483 perm(int n,int k) {
1484   double r;
1485   int i;
1486   r=1;
1487   for(i=k+1;i<=n;i++) r*=i;
1488   for(i=1;i<=(n-k);i++) r/=i;
1489   return r;
1490 }
1491
1492
1493 /* Note in calculating t^k*(1-t)^(n-k) 
1494    we can start by using t^0=1 so this simplifies to
1495    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
1496    to get a new level - this may lead to errors who knows lets test it */
1497
1498 void
1499 i_bezier_multi(i_img *im,int l,const double *x,const double *y, const i_color *val) {
1500   double *bzcoef;
1501   double t,cx,cy;
1502   int k,i;
1503   int lx = 0,ly = 0;
1504   int n=l-1;
1505   double itr,ccoef;
1506
1507   /* this is the same size as the x and y arrays, so shouldn't overflow */
1508   bzcoef=mymalloc(sizeof(double)*l); /* checked 5jul05 tonyc */
1509   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
1510   ICL_info(val);
1511
1512
1513   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
1514   i=0;
1515   for(t=0;t<=1;t+=0.005) {
1516     cx=cy=0;
1517     itr=t/(1-t);
1518     ccoef=pow(1-t,n);
1519     for(k=0;k<l;k++) {
1520       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k); 
1521               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
1522
1523       cx+=bzcoef[k]*x[k]*ccoef;
1524       cy+=bzcoef[k]*y[k]*ccoef;
1525       ccoef*=itr;
1526     }
1527     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
1528     if (i++) { 
1529       i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val, 1);
1530     }
1531       /*     i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
1532     lx=(int)(0.5+cx);
1533     ly=(int)(0.5+cy);
1534   }
1535   ICL_info(val);
1536   myfree(bzcoef);
1537 }
1538
1539 /* Flood fill 
1540
1541    REF: Graphics Gems I. page 282+
1542
1543 */
1544
1545 /* This should be moved into a seperate file? */
1546
1547 /* This is the truncation used:
1548    
1549    a double is multiplied by 16 and then truncated.
1550    This means that 0 -> 0
1551    So a triangle of (0,0) (10,10) (10,0) Will look like it's
1552    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
1553
1554 */
1555
1556
1557 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in 
1558    graphics gems I */
1559
1560 /*
1561 struct stc {
1562   int mylx,myrx; 
1563   int dadlx,dadrx;
1564   int myy;
1565   int mydirection;
1566 };
1567
1568 Not used code???
1569 */
1570
1571
1572 struct stack_element {
1573   int myLx,myRx;
1574   int dadLx,dadRx;
1575   int myY;
1576   int myDirection;
1577 };
1578
1579
1580 /* create the link data to put push onto the stack */
1581
1582 static
1583 struct stack_element*
1584 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
1585   struct stack_element *ste;
1586   ste              = mymalloc(sizeof(struct stack_element)); /* checked 5jul05 tonyc */
1587   ste->myLx        = left;
1588   ste->myRx        = right;
1589   ste->dadLx       = dadl;
1590   ste->dadRx       = dadr;
1591   ste->myY         = y;
1592   ste->myDirection = dir;
1593   return ste;
1594 }
1595
1596 /* i_ccomp compares two colors and gives true if they are the same */
1597
1598 typedef int (*ff_cmpfunc)(i_color const *c1, i_color const *c2, int channels);
1599
1600 static int
1601 i_ccomp_normal(i_color const *val1, i_color const *val2, int ch) {
1602   int i;
1603   for(i = 0; i < ch; i++) 
1604     if (val1->channel[i] !=val2->channel[i])
1605       return 0;
1606   return 1;
1607 }
1608
1609 static int
1610 i_ccomp_border(i_color const *val1, i_color const *val2, int ch) {
1611   int i;
1612   for(i = 0; i < ch; i++) 
1613     if (val1->channel[i] !=val2->channel[i])
1614       return 1;
1615   return 0;
1616 }
1617
1618 static int
1619 i_lspan(i_img *im, int seedx, int seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1620   i_color cval;
1621   while(1) {
1622     if (seedx-1 < 0) break;
1623     i_gpix(im,seedx-1,seedy,&cval);
1624     if (!cmpfunc(val,&cval,im->channels)) 
1625       break;
1626     seedx--;
1627   }
1628   return seedx;
1629 }
1630
1631 static int
1632 i_rspan(i_img *im, int seedx, int seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1633   i_color cval;
1634   while(1) {
1635     if (seedx+1 > im->xsize-1) break;
1636     i_gpix(im,seedx+1,seedy,&cval);
1637     if (!cmpfunc(val,&cval,im->channels)) break;
1638     seedx++;
1639   }
1640   return seedx;
1641 }
1642
1643 /* Macro to create a link and push on to the list */
1644
1645 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
1646   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
1647   llist_push(st,&s);                                             \
1648 } while (0)
1649
1650 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
1651 /* No overflow check! */
1652  
1653 #define ST_POP() do {         \
1654   struct stack_element *s;    \
1655   llist_pop(st,&s);           \
1656   lx        = s->myLx;        \
1657   rx        = s->myRx;        \
1658   dadLx     = s->dadLx;       \
1659   dadRx     = s->dadRx;       \
1660   y         = s->myY;         \
1661   direction = s->myDirection; \
1662   myfree(s);                  \
1663 } while (0)
1664
1665 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
1666   int pushrx = rx+1;                                              \
1667   int pushlx = lx-1;                                              \
1668   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
1669   if (rx > dadRx)                                                 \
1670     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
1671   if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
1672 } while (0)
1673
1674 #define SET(x,y) btm_set(btm,x,y)
1675
1676 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
1677 #define INSIDE(x,y, seed) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
1678
1679
1680
1681 /* The function that does all the real work */
1682
1683 static struct i_bitmap *
1684 i_flood_fill_low(i_img *im,int seedx,int seedy,
1685                  int *bxminp, int *bxmaxp, int *byminp, int *bymaxp,
1686                  i_color const *seed, ff_cmpfunc cmpfunc) {
1687   int ltx, rtx;
1688   int tx = 0;
1689
1690   int bxmin = seedx;
1691   int bxmax = seedx;
1692   int bymin = seedy;
1693   int bymax = seedy;
1694
1695   struct llist *st;
1696   struct i_bitmap *btm;
1697
1698   int channels,xsize,ysize;
1699   i_color cval;
1700
1701   channels = im->channels;
1702   xsize    = im->xsize;
1703   ysize    = im->ysize;
1704
1705   btm = btm_new(xsize, ysize);
1706   st  = llist_new(100, sizeof(struct stack_element*));
1707
1708   /* Find the starting span and fill it */
1709   ltx = i_lspan(im, seedx, seedy, seed, cmpfunc);
1710   rtx = i_rspan(im, seedx, seedy, seed, cmpfunc);
1711   for(tx=ltx; tx<=rtx; tx++) SET(tx, seedy);
1712   bxmin = ltx;
1713   bxmax = rtx;
1714
1715   ST_PUSH(ltx, rtx, ltx, rtx, seedy+1,  1);
1716   ST_PUSH(ltx, rtx, ltx, rtx, seedy-1, -1);
1717
1718   while(st->count) {
1719     /* Stack variables */
1720     int lx,rx;
1721     int dadLx,dadRx;
1722     int y;
1723     int direction;
1724
1725     int x;
1726     int wasIn=0;
1727
1728     ST_POP(); /* sets lx, rx, dadLx, dadRx, y, direction */
1729
1730
1731     if (y<0 || y>ysize-1) continue;
1732     if (bymin > y) bymin=y; /* in the worst case an extra line */
1733     if (bymax < y) bymax=y; 
1734
1735
1736     x = lx+1;
1737     if ( lx >= 0 && (wasIn = INSIDE(lx, y, seed)) ) {
1738       SET(lx, y);
1739       lx--;
1740       while(lx >= 0 && INSIDE(lx, y, seed)) {
1741         SET(lx,y);
1742         lx--;
1743       }
1744     }
1745
1746     if (bxmin > lx) bxmin = lx;
1747     while(x <= xsize-1) {
1748       /*  printf("x=%d\n",x); */
1749       if (wasIn) {
1750         
1751         if (INSIDE(x, y, seed)) {
1752           /* case 1: was inside, am still inside */
1753           SET(x,y);
1754         } else {
1755           /* case 2: was inside, am no longer inside: just found the
1756              right edge of a span */
1757           ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1758
1759           if (bxmax < x) bxmax = x;
1760           wasIn=0;
1761         }
1762       } else {
1763         if (x > rx) goto EXT;
1764         if (INSIDE(x, y, seed)) {
1765           SET(x, y);
1766           /* case 3: Wasn't inside, am now: just found the start of a new run */
1767           wasIn = 1;
1768             lx = x;
1769         } else {
1770           /* case 4: Wasn't inside, still isn't */
1771         }
1772       }
1773       x++;
1774     }
1775   EXT: /* out of loop */
1776     if (wasIn) {
1777       /* hit an edge of the frame buffer while inside a run */
1778       ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1779       if (bxmax < x) bxmax = x;
1780     }
1781   }
1782
1783   llist_destroy(st);
1784
1785   *bxminp = bxmin;
1786   *bxmaxp = bxmax;
1787   *byminp = bymin;
1788   *bymaxp = bymax;
1789
1790   return btm;
1791 }
1792
1793 /*
1794 =item i_flood_fill(C<im>, C<seedx>, C<seedy>, C<color>)
1795
1796 =category Drawing
1797 =synopsis i_flood_fill(im, 50, 50, &color);
1798
1799 Flood fills the 4-connected region starting from the point (C<seedx>,
1800 C<seedy>) with I<color>.
1801
1802 Returns false if (C<seedx>, C<seedy>) are outside the image.
1803
1804 =cut
1805 */
1806
1807 undef_int
1808 i_flood_fill(i_img *im, int seedx, int seedy, const i_color *dcol) {
1809   int bxmin, bxmax, bymin, bymax;
1810   struct i_bitmap *btm;
1811   int x, y;
1812   i_color val;
1813
1814   i_clear_error();
1815   if (seedx < 0 || seedx >= im->xsize ||
1816       seedy < 0 || seedy >= im->ysize) {
1817     i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
1818     return 0;
1819   }
1820
1821   /* Get the reference color */
1822   i_gpix(im, seedx, seedy, &val);
1823
1824   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1825                          &val, i_ccomp_normal);
1826
1827   for(y=bymin;y<=bymax;y++)
1828     for(x=bxmin;x<=bxmax;x++)
1829       if (btm_test(btm,x,y)) 
1830         i_ppix(im,x,y,dcol);
1831   btm_destroy(btm);
1832   return 1;
1833 }
1834
1835 /*
1836 =item i_flood_cfill(C<im>, C<seedx>, C<seedy>, C<fill>)
1837
1838 =category Drawing
1839 =synopsis i_flood_cfill(im, 50, 50, fill);
1840
1841 Flood fills the 4-connected region starting from the point (C<seedx>,
1842 C<seedy>) with C<fill>.
1843
1844 Returns false if (C<seedx>, C<seedy>) are outside the image.
1845
1846 =cut
1847 */
1848
1849 undef_int
1850 i_flood_cfill(i_img *im, int seedx, int seedy, i_fill_t *fill) {
1851   int bxmin, bxmax, bymin, bymax;
1852   struct i_bitmap *btm;
1853   i_color val;
1854
1855   i_clear_error();
1856   
1857   if (seedx < 0 || seedx >= im->xsize ||
1858       seedy < 0 || seedy >= im->ysize) {
1859     i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
1860     return 0;
1861   }
1862
1863   /* Get the reference color */
1864   i_gpix(im, seedx, seedy, &val);
1865
1866   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1867                          &val, i_ccomp_normal);
1868
1869   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
1870
1871   btm_destroy(btm);
1872   return 1;
1873 }
1874
1875 /*
1876 =item i_flood_fill_border(C<im>, C<seedx>, C<seedy>, C<color>, C<border>)
1877
1878 =category Drawing
1879 =synopsis i_flood_fill_border(im, 50, 50, &color, &border);
1880
1881 Flood fills the 4-connected region starting from the point (C<seedx>,
1882 C<seedy>) with C<color>, fill stops when the fill reaches a pixels
1883 with color C<border>.
1884
1885 Returns false if (C<seedx>, C<seedy>) are outside the image.
1886
1887 =cut
1888 */
1889
1890 undef_int
1891 i_flood_fill_border(i_img *im, int seedx, int seedy, const i_color *dcol,
1892                     const i_color *border) {
1893   int bxmin, bxmax, bymin, bymax;
1894   struct i_bitmap *btm;
1895   int x, y;
1896
1897   i_clear_error();
1898   if (seedx < 0 || seedx >= im->xsize ||
1899       seedy < 0 || seedy >= im->ysize) {
1900     i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
1901     return 0;
1902   }
1903
1904   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1905                          border, i_ccomp_border);
1906
1907   for(y=bymin;y<=bymax;y++)
1908     for(x=bxmin;x<=bxmax;x++)
1909       if (btm_test(btm,x,y)) 
1910         i_ppix(im,x,y,dcol);
1911   btm_destroy(btm);
1912   return 1;
1913 }
1914
1915 /*
1916 =item i_flood_cfill_border(C<im>, C<seedx>, C<seedy>, C<fill>, C<border>)
1917
1918 =category Drawing
1919 =synopsis i_flood_cfill_border(im, 50, 50, fill, border);
1920
1921 Flood fills the 4-connected region starting from the point (C<seedx>,
1922 C<seedy>) with C<fill>, the fill stops when it reaches pixels of color
1923 C<border>.
1924
1925 Returns false if (C<seedx>, C<seedy>) are outside the image.
1926
1927 =cut
1928 */
1929
1930 undef_int
1931 i_flood_cfill_border(i_img *im, int seedx, int seedy, i_fill_t *fill,
1932                      const i_color *border) {
1933   int bxmin, bxmax, bymin, bymax;
1934   struct i_bitmap *btm;
1935
1936   i_clear_error();
1937   
1938   if (seedx < 0 || seedx >= im->xsize ||
1939       seedy < 0 || seedy >= im->ysize) {
1940     i_push_error(0, "i_flood_cfill_border: Seed pixel outside of image");
1941     return 0;
1942   }
1943
1944   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1945                          border, i_ccomp_border);
1946
1947   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
1948
1949   btm_destroy(btm);
1950
1951   return 1;
1952 }
1953
1954 static void
1955 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm, 
1956                int bxmin, int bxmax, int bymin, int bymax) {
1957   int x, y;
1958   int start;
1959
1960   i_render r;
1961
1962   i_render_init(&r, im, bxmax - bxmin + 1);
1963
1964   for(y=bymin; y<=bymax; y++) {
1965     x = bxmin;
1966     while (x <= bxmax) {
1967       while (x <= bxmax && !btm_test(btm, x, y)) {
1968         ++x;
1969       }
1970       if (btm_test(btm, x, y)) {
1971         start = x;
1972         while (x <= bxmax && btm_test(btm, x, y)) {
1973           ++x;
1974         }
1975         i_render_fill(&r, start, y, x-start, NULL, fill);
1976       }
1977     }
1978   }
1979   i_render_done(&r);
1980 }