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