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