avoid dead code in i_t1_glyph_names().
[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   i_img_dim first_row = floor(y) - ceil(rad);
504   i_img_dim last_row = ceil(y) + ceil(rad);
505   double r_sqr = rad * rad;
506   i_img_dim max_width = 2 * ceil(rad) + 1;
507   unsigned char *coverage = NULL;
508   size_t coverage_size;
509   int sub;
510
511   im_log((aIMCTX, 1, "i_circle_aa_low(im %p, centre(" i_DFp "), rad %.2f, r %p, ctx %p)\n",
512           im, i_DFcp(x, y), rad, r, ctx));
513
514   if (first_row < 0)
515     first_row = 0;
516   if (last_row > im->ysize-1)
517     last_row = im->ysize - 1;
518
519   if (rad <= 0 || last_row < first_row) {
520     /* outside the image */
521     return;
522   }
523
524   coverage_size = max_width;
525   coverage = mymalloc(coverage_size);
526
527   for(ly = first_row; ly < last_row; ly++) {
528     frac min_frac_x[16];
529     frac max_frac_x[16];
530     i_img_dim min_frac_left_x = im->xsize * 16;
531     i_img_dim max_frac_left_x = -1;
532     i_img_dim min_frac_right_x = im->xsize * 16;
533     i_img_dim max_frac_right_x = -1;
534     /* reset work_y each row so the error doesn't build up */
535     double work_y = ly;
536     double dy, dy_sqr;
537       
538     for (sub = 0; sub < 16; ++sub) {
539       work_y += 1.0 / 16.0;
540       dy = work_y - y;
541       dy_sqr = dy * dy;
542
543       if (dy_sqr < r_sqr) {
544         double dx = sqrt(r_sqr - dy_sqr);
545         double left_x = x - dx;
546         double right_x = x + dx;
547         frac frac_left_x = float_to_frac(left_x);
548         frac frac_right_x = float_to_frac(right_x);
549
550         if (frac_left_x < min_frac_left_x)
551           min_frac_left_x = frac_left_x;
552         if (frac_left_x > max_frac_left_x)
553           max_frac_left_x = frac_left_x;
554         if (frac_right_x < min_frac_right_x)
555           min_frac_right_x = frac_right_x;
556         if (frac_right_x > max_frac_right_x)
557           max_frac_right_x = frac_right_x;
558         min_frac_x[sub] = frac_left_x;
559         max_frac_x[sub] = frac_right_x;
560       }
561       else {
562         min_frac_x[sub] = max_frac_x[sub] = 0;
563         max_frac_left_x = im->xsize * 16;
564         min_frac_right_x = -1;
565       }
566     }
567
568     if (min_frac_left_x != -1) {
569       /* something to draw on this line */
570       i_img_dim min_x = (min_frac_left_x / 16);
571       i_img_dim max_x = (max_frac_right_x + 15) / 16;
572       i_img_dim left_solid = (max_frac_left_x + 15) / 16;
573       i_img_dim right_solid = min_frac_right_x / 16;
574       i_img_dim work_x;
575       i_img_dim frac_work_x;
576       i_sample_t *cout = coverage;
577
578       for (work_x = min_x, frac_work_x = min_x * 16;
579            work_x <= max_x;
580            ++work_x, frac_work_x += 16) {
581         if (work_x <= left_solid || work_x >= right_solid) {
582           int pix_coverage = 0;
583           int ch;
584           double ratio;
585           i_img_dim frac_work_right = frac_work_x + 16;
586           for (sub = 0; sub < 16; ++sub) {
587             frac pix_left = min_frac_x[sub];
588             frac pix_right = max_frac_x[sub];
589             if (pix_left < pix_right
590                 && pix_left < frac_work_right
591                 && pix_right >= frac_work_x) {
592               if (pix_left < frac_work_x)
593                 pix_left = frac_work_x;
594               if (pix_right > frac_work_right)
595                 pix_right = frac_work_right;
596               pix_coverage += pix_right - pix_left;
597             }
598           }
599
600           assert(pix_coverage <= 256);
601           *cout++ = pix_coverage * 255 / 256;
602         }
603         else {
604           /* full coverage */
605           *cout++ = 255;
606         }
607       }
608       r(im, min_x, ly, max_x - min_x + 1, coverage, ctx);
609     }
610   }
611
612   myfree(coverage);
613 }
614
615 static void
616 scanline_flush_color(i_img *im, i_img_dim x, i_img_dim y, i_img_dim width, const unsigned char *cover, void *ctx) {
617   flush_color_t *fc = ctx;
618
619   i_render_color(&fc->r, x, y, width, cover, &fc->c);
620 }
621
622 static void
623 scanline_flush_fill(i_img *im, i_img_dim x, i_img_dim y, i_img_dim width, const unsigned char *cover, void *ctx) {
624   flush_fill_t *ff = ctx;
625
626   i_render_fill(&ff->r, x, y, width, cover, ff->fill);
627 }
628
629
630 /*
631 =item i_circle_out(im, x, y, r, col)
632
633 =category Drawing
634 =synopsis i_circle_out(im, 50, 50, 45, &color);
635
636 Draw a circle outline centered at (x,y) with radius r,
637 non-anti-aliased.
638
639 Parameters:
640
641 =over
642
643 =item *
644
645 (x, y) - the center of the circle
646
647 =item *
648
649 r - the radius of the circle in pixels, must be non-negative
650
651 =back
652
653 Returns non-zero on success.
654
655 Implementation:
656
657 =cut
658 */
659
660 int
661 i_circle_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
662              const i_color *col) {
663   i_img_dim x, y;
664   i_img_dim dx, dy;
665   int error;
666   dIMCTXim(im);
667
668   im_log((aIMCTX, 1, "i_circle_out(im %p, centre(" i_DFp "), rad %" i_DF ", col %p)\n",
669           im, i_DFcp(xc, yc), i_DFc(r), col));
670
671   im_clear_error(aIMCTX);
672
673   if (r < 0) {
674     im_push_error(aIMCTX, 0, "circle: radius must be non-negative");
675     return 0;
676   }
677
678   i_ppix(im, xc+r, yc, col);
679   i_ppix(im, xc-r, yc, col);
680   i_ppix(im, xc, yc+r, col);
681   i_ppix(im, xc, yc-r, col);
682
683   x = 0;
684   y = r;
685   dx = 1;
686   dy = -2 * r;
687   error = 1 - r;
688   while (x < y) {
689     if (error >= 0) {
690       --y;
691       dy += 2;
692       error += dy;
693     }
694     ++x;
695     dx += 2;
696     error += dx;
697
698     i_ppix(im, xc + x, yc + y, col);
699     i_ppix(im, xc + x, yc - y, col);
700     i_ppix(im, xc - x, yc + y, col);
701     i_ppix(im, xc - x, yc - y, col);
702     if (x != y) {
703       i_ppix(im, xc + y, yc + x, col);
704       i_ppix(im, xc + y, yc - x, col);
705       i_ppix(im, xc - y, yc + x, col);
706       i_ppix(im, xc - y, yc - x, col);
707     }
708   }
709
710   return 1;
711 }
712
713 /*
714 =item arc_seg(angle)
715
716 Convert an angle in degrees into an angle measure we can generate
717 simply from the numbers we have when drawing the circle.
718
719 =cut
720 */
721
722 static i_img_dim
723 arc_seg(double angle, int scale) {
724   i_img_dim seg = (angle + 45) / 90;
725   double remains = angle - seg * 90; /* should be in the range [-45,45] */
726
727   while (seg > 4)
728     seg -= 4;
729   if (seg == 4 && remains > 0)
730     seg = 0;
731
732   return scale * (seg * 2 + sin(remains * PI/180));
733 }
734
735 /*
736 =item i_arc_out(im, x, y, r, d1, d2, col)
737
738 =category Drawing
739 =synopsis i_arc_out(im, 50, 50, 45, 45, 135, &color);
740
741 Draw an arc outline centered at (x,y) with radius r, non-anti-aliased
742 over the angle range d1 through d2 degrees.
743
744 Parameters:
745
746 =over
747
748 =item *
749
750 (x, y) - the center of the circle
751
752 =item *
753
754 r - the radius of the circle in pixels, must be non-negative
755
756 =item *
757
758 d1, d2 - the range of angles to draw the arc over, in degrees.
759
760 =back
761
762 Returns non-zero on success.
763
764 Implementation:
765
766 =cut
767 */
768
769 int
770 i_arc_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
771           double d1, double d2, const i_color *col) {
772   i_img_dim x, y;
773   i_img_dim dx, dy;
774   int error;
775   i_img_dim segs[2][2];
776   int seg_count;
777   i_img_dim sin_th;
778   i_img_dim seg_d1, seg_d2;
779   int seg_num;
780   i_img_dim scale = r + 1;
781   i_img_dim seg1 = scale * 2;
782   i_img_dim seg2 = scale * 4;
783   i_img_dim seg3 = scale * 6;
784   i_img_dim seg4 = scale * 8;
785   dIMCTXim(im);
786
787   im_log((aIMCTX,1,"i_arc_out(im %p,centre(" i_DFp "), rad %" i_DF ", d1 %f, d2 %f, col %p)",
788           im, i_DFcp(xc, yc), i_DFc(r), d1, d2, col));
789
790   im_clear_error(aIMCTX);
791
792   if (r <= 0) {
793     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
794     return 0;
795   }
796   if (d1 + 360 <= d2)
797     return i_circle_out(im, xc, yc, r, col);
798
799   if (d1 < 0)
800     d1 += 360 * floor((-d1 + 359) / 360);
801   if (d2 < 0)
802     d2 += 360 * floor((-d2 + 359) / 360);
803   d1 = fmod(d1, 360);
804   d2 = fmod(d2, 360);
805   seg_d1 = arc_seg(d1, scale);
806   seg_d2 = arc_seg(d2, scale);
807   if (seg_d2 < seg_d1) {
808     /* split into two segments */
809     segs[0][0] = 0;
810     segs[0][1] = seg_d2;
811     segs[1][0] = seg_d1;
812     segs[1][1] = seg4;
813     seg_count = 2;
814   }
815   else {
816     segs[0][0] = seg_d1;
817     segs[0][1] = seg_d2;
818     seg_count = 1;
819   }
820
821   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
822     i_img_dim seg_start = segs[seg_num][0];
823     i_img_dim seg_end = segs[seg_num][1];
824     if (seg_start == 0)
825       i_ppix(im, xc+r, yc, col);
826     if (seg_start <= seg1 && seg_end >= seg1)
827       i_ppix(im, xc, yc+r, col);
828     if (seg_start <= seg2 && seg_end >= seg2)
829       i_ppix(im, xc-r, yc, col);
830     if (seg_start <= seg3 && seg_end >= seg3)
831       i_ppix(im, xc, yc-r, col);
832
833     y = 0;
834     x = r;
835     dy = 1;
836     dx = -2 * r;
837     error = 1 - r;
838     while (y < x) {
839       if (error >= 0) {
840         --x;
841         dx += 2;
842         error += dx;
843       }
844       ++y;
845       dy += 2;
846       error += dy;
847       
848       sin_th = y;
849       if (seg_start <= sin_th && seg_end >= sin_th)
850         i_ppix(im, xc + x, yc + y, col);
851       if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
852         i_ppix(im, xc + y, yc + x, col);
853
854       if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
855         i_ppix(im, xc - y, yc + x, col);
856       if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
857         i_ppix(im, xc - x, yc + y, col);
858       
859       if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
860         i_ppix(im, xc - x, yc - y, col);
861       if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
862         i_ppix(im, xc - y, yc - x, col);
863
864       if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
865         i_ppix(im, xc + y, yc - x, col);
866       if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
867         i_ppix(im, xc + x, yc - y, col);
868     }
869   }
870
871   return 1;
872 }
873
874 static double
875 cover(i_img_dim r, i_img_dim j) {
876   double rjsqrt = sqrt(r*r - j*j);
877
878   return ceil(rjsqrt) - rjsqrt;
879 }
880
881 /*
882 =item i_circle_out_aa(im, xc, yc, r, col)
883
884 =synopsis i_circle_out_aa(im, 50, 50, 45, &color);
885
886 Draw a circle outline centered at (x,y) with radius r, anti-aliased.
887
888 Parameters:
889
890 =over
891
892 =item *
893
894 (xc, yc) - the center of the circle
895
896 =item *
897
898 r - the radius of the circle in pixels, must be non-negative
899
900 =item *
901
902 col - an i_color for the color to draw in.
903
904 =back
905
906 Returns non-zero on success.
907
908 =cut
909
910 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
911 Gems.
912
913 I use floating point for I<D> since for large circles the precision of
914 a [0,255] value isn't sufficient when approaching the end of the
915 octant.
916
917 */
918
919 int
920 i_circle_out_aa(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r, const i_color *col) {
921   i_img_dim i, j;
922   double t;
923   i_color workc = *col;
924   int orig_alpha = col->channel[3];
925   dIMCTXim(im);
926
927   im_log((aIMCTX,1,"i_circle_out_aa(im %p,centre(" i_DFp "), rad %" i_DF ", col %p)",
928           im, i_DFcp(xc, yc), i_DFc(r), col));
929
930   im_clear_error(aIMCTX);
931   if (r <= 0) {
932     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
933     return 0;
934   }
935   i = r;
936   j = 0;
937   t = 0;
938   i_ppix_norm(im, xc+i, yc+j, col);
939   i_ppix_norm(im, xc-i, yc+j, col);
940   i_ppix_norm(im, xc+j, yc+i, col);
941   i_ppix_norm(im, xc+j, yc-i, col);
942
943   while (i > j+1) {
944     double d;
945     int cv, inv_cv;
946     j++;
947     d = cover(r, j);
948     cv = (int)(d * 255 + 0.5);
949     inv_cv = 255-cv;
950     if (d < t) {
951       --i;
952     }
953     if (inv_cv) {
954       workc.channel[3] = orig_alpha * inv_cv / 255;
955       i_ppix_norm(im, xc+i, yc+j, &workc);
956       i_ppix_norm(im, xc-i, yc+j, &workc);
957       i_ppix_norm(im, xc+i, yc-j, &workc);
958       i_ppix_norm(im, xc-i, yc-j, &workc);
959
960       if (i != j) {
961         i_ppix_norm(im, xc+j, yc+i, &workc);
962         i_ppix_norm(im, xc-j, yc+i, &workc);
963         i_ppix_norm(im, xc+j, yc-i, &workc);
964         i_ppix_norm(im, xc-j, yc-i, &workc);
965       }
966     }
967     if (cv && i > j) {
968       workc.channel[3] = orig_alpha * cv / 255;
969       i_ppix_norm(im, xc+i-1, yc+j, &workc);
970       i_ppix_norm(im, xc-i+1, yc+j, &workc);
971       i_ppix_norm(im, xc+i-1, yc-j, &workc);
972       i_ppix_norm(im, xc-i+1, yc-j, &workc);
973
974       if (j != i-1) {
975         i_ppix_norm(im, xc+j, yc+i-1, &workc);
976         i_ppix_norm(im, xc-j, yc+i-1, &workc);
977         i_ppix_norm(im, xc+j, yc-i+1, &workc);
978         i_ppix_norm(im, xc-j, yc-i+1, &workc);
979       }
980     }
981     t = d;
982   }
983
984   return 1;
985 }
986
987 /*
988 =item i_arc_out_aa(im, xc, yc, r, d1, d2, col)
989
990 =synopsis i_arc_out_aa(im, 50, 50, 45, 45, 125, &color);
991
992 Draw a circle arc outline centered at (x,y) with radius r, from angle
993 d1 degrees through angle d2 degrees, anti-aliased.
994
995 Parameters:
996
997 =over
998
999 =item *
1000
1001 (xc, yc) - the center of the circle
1002
1003 =item *
1004
1005 r - the radius of the circle in pixels, must be non-negative
1006
1007 =item *
1008
1009 d1, d2 - the range of angle in degrees to draw the arc through.  If
1010 d2-d1 >= 360 a full circle is drawn.
1011
1012 =back
1013
1014 Returns non-zero on success.
1015
1016 =cut
1017
1018 Based on "Fast Anti-Aliased Circle Generation", Xiaolin Wu, Graphics
1019 Gems.
1020
1021 */
1022
1023 int
1024 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) {
1025   i_img_dim i, j;
1026   double t;
1027   i_color workc = *col;
1028   i_img_dim segs[2][2];
1029   int seg_count;
1030   i_img_dim sin_th;
1031   i_img_dim seg_d1, seg_d2;
1032   int seg_num;
1033   int orig_alpha = col->channel[3];
1034   i_img_dim scale = r + 1;
1035   i_img_dim seg1 = scale * 2;
1036   i_img_dim seg2 = scale * 4;
1037   i_img_dim seg3 = scale * 6;
1038   i_img_dim seg4 = scale * 8;
1039   dIMCTXim(im);
1040
1041   im_log((aIMCTX,1,"i_arc_out_aa(im %p,centre(" i_DFp "), rad %" i_DF ", d1 %f, d2 %f, col %p)",
1042           im, i_DFcp(xc, yc), i_DFc(r), d1, d2, col));
1043
1044   im_clear_error(aIMCTX);
1045   if (r <= 0) {
1046     im_push_error(aIMCTX, 0, "arc: radius must be non-negative");
1047     return 0;
1048   }
1049   if (d1 + 360 <= d2)
1050     return i_circle_out_aa(im, xc, yc, r, col);
1051
1052   if (d1 < 0)
1053     d1 += 360 * floor((-d1 + 359) / 360);
1054   if (d2 < 0)
1055     d2 += 360 * floor((-d2 + 359) / 360);
1056   d1 = fmod(d1, 360);
1057   d2 = fmod(d2, 360);
1058   seg_d1 = arc_seg(d1, scale);
1059   seg_d2 = arc_seg(d2, scale);
1060   if (seg_d2 < seg_d1) {
1061     /* split into two segments */
1062     segs[0][0] = 0;
1063     segs[0][1] = seg_d2;
1064     segs[1][0] = seg_d1;
1065     segs[1][1] = seg4;
1066     seg_count = 2;
1067   }
1068   else {
1069     segs[0][0] = seg_d1;
1070     segs[0][1] = seg_d2;
1071     seg_count = 1;
1072   }
1073
1074   for (seg_num = 0; seg_num < seg_count; ++seg_num) {
1075     i_img_dim seg_start = segs[seg_num][0];
1076     i_img_dim seg_end = segs[seg_num][1];
1077
1078     i = r;
1079     j = 0;
1080     t = 0;
1081
1082     if (seg_start == 0)
1083       i_ppix_norm(im, xc+i, yc+j, col);
1084     if (seg_start <= seg1 && seg_end >= seg1)
1085       i_ppix_norm(im, xc+j, yc+i, col);
1086     if (seg_start <= seg2 && seg_end >= seg2)
1087       i_ppix_norm(im, xc-i, yc+j, col);
1088     if (seg_start <= seg3 && seg_end >= seg3)
1089       i_ppix_norm(im, xc+j, yc-i, col);
1090     
1091     while (i > j+1) {
1092       int cv, inv_cv;
1093       double d;
1094       j++;
1095       d = cover(r, j);
1096       cv = (int)(d * 255 + 0.5);
1097       inv_cv = 255-cv;
1098       if (d < t) {
1099         --i;
1100       }
1101       sin_th = j;
1102       if (inv_cv) {
1103         workc.channel[3] = orig_alpha * inv_cv / 255;
1104
1105         if (seg_start <= sin_th && seg_end >= sin_th)
1106           i_ppix_norm(im, xc+i, yc+j, &workc);
1107         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1108           i_ppix_norm(im, xc-i, yc+j, &workc);
1109         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1110           i_ppix_norm(im, xc+i, yc-j, &workc);
1111         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1112           i_ppix_norm(im, xc-i, yc-j, &workc);
1113         
1114         if (i != j) {
1115           if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1116             i_ppix_norm(im, xc+j, yc+i, &workc);
1117           if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1118             i_ppix_norm(im, xc-j, yc+i, &workc);
1119           if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1120             i_ppix_norm(im, xc+j, yc-i, &workc);
1121           if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1122             i_ppix_norm(im, xc-j, yc-i, &workc);
1123         }
1124       }
1125       if (cv && i > j) {
1126         workc.channel[3] = orig_alpha * cv / 255;
1127         if (seg_start <= sin_th && seg_end >= sin_th)
1128           i_ppix_norm(im, xc+i-1, yc+j, &workc);
1129         if (seg_start <= seg2 - sin_th && seg_end >= seg2 - sin_th)
1130           i_ppix_norm(im, xc-i+1, yc+j, &workc);
1131         if (seg_start <= seg4 - sin_th && seg_end >= seg4 - sin_th)
1132           i_ppix_norm(im, xc+i-1, yc-j, &workc);
1133         if (seg_start <= seg2 + sin_th && seg_end >= seg2 + sin_th)
1134           i_ppix_norm(im, xc-i+1, yc-j, &workc);
1135         
1136         if (seg_start <= seg1 - sin_th && seg_end >= seg1 - sin_th)
1137           i_ppix_norm(im, xc+j, yc+i-1, &workc);
1138         if (seg_start <= seg1 + sin_th && seg_end >= seg1 + sin_th)
1139           i_ppix_norm(im, xc-j, yc+i-1, &workc);
1140         if (seg_start <= seg3 + sin_th && seg_end >= seg3 + sin_th)
1141           i_ppix_norm(im, xc+j, yc-i+1, &workc);
1142         if (seg_start <= seg3 - sin_th && seg_end >= seg3 - sin_th)
1143           i_ppix_norm(im, xc-j, yc-i+1, &workc);
1144       }
1145       t = d;
1146     }
1147   }
1148
1149   return 1;
1150 }
1151
1152 /*
1153 =item i_box(im, x1, y1, x2, y2, color)
1154
1155 =category Drawing
1156 =synopsis i_box(im, 0, 0, im->xsize-1, im->ysize-1, &color).
1157
1158 Outlines the box from (x1,y1) to (x2,y2) inclusive with I<color>.
1159
1160 =cut
1161 */
1162
1163 void
1164 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) {
1165   i_img_dim x,y;
1166   dIMCTXim(im);
1167
1168   im_log((aIMCTX, 1,"i_box(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1169           im, i_DFcp(x1,y1), i_DFcp(x2,y2), val));
1170   for(x=x1;x<x2+1;x++) {
1171     i_ppix(im,x,y1,val);
1172     i_ppix(im,x,y2,val);
1173   }
1174   for(y=y1;y<y2+1;y++) {
1175     i_ppix(im,x1,y,val);
1176     i_ppix(im,x2,y,val);
1177   }
1178 }
1179
1180 /*
1181 =item i_box_filled(im, x1, y1, x2, y2, color)
1182
1183 =category Drawing
1184 =synopsis i_box_filled(im, 0, 0, im->xsize-1, im->ysize-1, &color);
1185
1186 Fills the box from (x1,y1) to (x2,y2) inclusive with color.
1187
1188 =cut
1189 */
1190
1191 void
1192 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) {
1193   i_img_dim x, y, width;
1194   i_palidx index;
1195   dIMCTXim(im);
1196
1197   im_log((aIMCTX,1,"i_box_filled(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1198           im, i_DFcp(x1, y1), i_DFcp(x2,y2) ,val));
1199
1200   if (x1 > x2 || y1 > y2
1201       || x2 < 0 || y2 < 0
1202       || x1 >= im->xsize || y1 > im->ysize)
1203     return;
1204
1205   if (x1 < 0)
1206     x1 = 0;
1207   if (x2 >= im->xsize)
1208     x2 = im->xsize - 1;
1209   if (y1 < 0)
1210     y1 = 0;
1211   if (y2 >= im->ysize)
1212     y2 = im->ysize - 1;
1213
1214   width = x2 - x1 + 1;
1215
1216   if (im->type == i_palette_type
1217       && i_findcolor(im, val, &index)) {
1218     i_palidx *line = mymalloc(sizeof(i_palidx) * width);
1219
1220     for (x = 0; x < width; ++x)
1221       line[x] = index;
1222
1223     for (y = y1; y <= y2; ++y)
1224       i_ppal(im, x1, x2+1, y, line);
1225
1226     myfree(line);
1227   }
1228   else {
1229     i_color *line = mymalloc(sizeof(i_color) * width);
1230
1231     for (x = 0; x < width; ++x)
1232       line[x] = *val;
1233
1234     for (y = y1; y <= y2; ++y)
1235       i_plin(im, x1, x2+1, y, line);
1236
1237     myfree(line);
1238   }
1239 }
1240
1241 /*
1242 =item i_box_filledf(im, x1, y1, x2, y2, color)
1243
1244 =category Drawing
1245 =synopsis i_box_filledf(im, 0, 0, im->xsize-1, im->ysize-1, &fcolor);
1246
1247 Fills the box from (x1,y1) to (x2,y2) inclusive with a floating point
1248 color.
1249
1250 =cut
1251 */
1252
1253 int
1254 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) {
1255   i_img_dim x, y, width;
1256   dIMCTXim(im);
1257
1258   im_log((aIMCTX, 1,"i_box_filledf(im* %p, p1(" i_DFp "), p2(" i_DFp "),val %p)\n",
1259           im, i_DFcp(x1, y1), i_DFcp(x2, y2), val));
1260
1261   if (x1 > x2 || y1 > y2
1262       || x2 < 0 || y2 < 0
1263       || x1 >= im->xsize || y1 > im->ysize)
1264     return 0;
1265
1266   if (x1 < 0)
1267     x1 = 0;
1268   if (x2 >= im->xsize)
1269     x2 = im->xsize - 1;
1270   if (y1 < 0)
1271     y1 = 0;
1272   if (y2 >= im->ysize)
1273     y2 = im->ysize - 1;
1274
1275   width = x2 - x1 + 1;
1276
1277   if (im->bits <= 8) {
1278     i_color c;
1279     c.rgba.r = SampleFTo8(val->rgba.r);
1280     c.rgba.g = SampleFTo8(val->rgba.g);
1281     c.rgba.b = SampleFTo8(val->rgba.b);
1282     c.rgba.a = SampleFTo8(val->rgba.a);
1283
1284     i_box_filled(im, x1, y1, x2, y2, &c);
1285   }
1286   else {
1287     i_fcolor *line = mymalloc(sizeof(i_fcolor) * width);
1288     
1289     for (x = 0; x < width; ++x)
1290       line[x] = *val;
1291     
1292     for (y = y1; y <= y2; ++y)
1293       i_plinf(im, x1, x2+1, y, line);
1294     
1295     myfree(line);
1296   }
1297   
1298   return 1;
1299 }
1300
1301 /*
1302 =item i_box_cfill(im, x1, y1, x2, y2, fill)
1303
1304 =category Drawing
1305 =synopsis i_box_cfill(im, 0, 0, im->xsize-1, im->ysize-1, fill);
1306
1307 Fills the box from (x1,y1) to (x2,y2) inclusive with fill.
1308
1309 =cut
1310 */
1311
1312 void
1313 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) {
1314   i_render r;
1315   dIMCTXim(im);
1316
1317   im_log((aIMCTX,1,"i_box_cfill(im* %p, p1(" i_DFp "), p2(" i_DFp "), fill %p)\n",
1318           im, i_DFcp(x1, y1), i_DFcp(x2,y2), fill));
1319
1320   ++x2;
1321   if (x1 < 0)
1322     x1 = 0;
1323   if (y1 < 0) 
1324     y1 = 0;
1325   if (x2 > im->xsize) 
1326     x2 = im->xsize;
1327   if (y2 >= im->ysize)
1328     y2 = im->ysize-1;
1329   if (x1 >= x2 || y1 > y2)
1330     return;
1331
1332   i_render_init(&r, im, x2-x1);
1333   while (y1 <= y2) {
1334     i_render_fill(&r, x1, y1, x2-x1, NULL, fill);
1335     ++y1;
1336   }
1337   i_render_done(&r);
1338 }
1339
1340 /* 
1341 =item i_line(C<im>, C<x1>, C<y1>, C<x2>, C<y2>, C<color>, C<endp>)
1342
1343 =category Drawing
1344
1345 =for stopwords Bresenham's
1346
1347 Draw a line to image using Bresenham's line drawing algorithm
1348
1349    im    - image to draw to
1350    x1    - starting x coordinate
1351    y1    - starting x coordinate
1352    x2    - starting x coordinate
1353    y2    - starting x coordinate
1354    color - color to write to image
1355    endp  - endpoint flag (boolean)
1356
1357 =cut
1358 */
1359
1360 void
1361 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) {
1362   i_img_dim x, y;
1363   i_img_dim dx, dy;
1364   i_img_dim p;
1365
1366   dx = x2 - x1;
1367   dy = y2 - y1;
1368
1369
1370   /* choose variable to iterate on */
1371   if (i_abs(dx) > i_abs(dy)) {
1372     i_img_dim dx2, dy2, cpy;
1373
1374     /* sort by x */
1375     if (x1 > x2) {
1376       i_img_dim t;
1377       t = x1; x1 = x2; x2 = t;
1378       t = y1; y1 = y2; y2 = t;
1379     }
1380     
1381     dx = i_abs(dx);
1382     dx2 = dx*2;
1383     dy = y2 - y1;
1384
1385     if (dy<0) {
1386       dy = -dy;
1387       cpy = -1;
1388     } else {
1389       cpy = 1;
1390     }
1391     dy2 = dy*2;
1392     p = dy2 - dx;
1393
1394     
1395     y = y1;
1396     for(x=x1; x<x2-1; x++) {
1397       if (p<0) {
1398         p += dy2;
1399       } else {
1400         y += cpy;
1401         p += dy2-dx2;
1402       }
1403       i_ppix(im, x+1, y, val);
1404     }
1405   } else {
1406     i_img_dim dy2, dx2, cpx;
1407
1408     /* sort bx y */
1409     if (y1 > y2) {
1410       i_img_dim t;
1411       t = x1; x1 = x2; x2 = t;
1412       t = y1; y1 = y2; y2 = t;
1413     }
1414     
1415     dy = i_abs(dy);
1416     dx = x2 - x1;
1417     dy2 = dy*2;
1418
1419     if (dx<0) {
1420       dx = -dx;
1421       cpx = -1;
1422     } else {
1423       cpx = 1;
1424     }
1425     dx2 = dx*2;
1426     p = dx2 - dy;
1427
1428     x = x1;
1429     
1430     for(y=y1; y<y2-1; y++) {
1431       if (p<0) {
1432         p  += dx2;
1433       } else {
1434         x += cpx;
1435         p += dx2-dy2;
1436       }
1437       i_ppix(im, x, y+1, val);
1438     }
1439   }
1440   if (endp) {
1441     i_ppix(im, x1, y1, val);
1442     i_ppix(im, x2, y2, val);
1443   } else {
1444     if (x1 != x2 || y1 != y2) 
1445       i_ppix(im, x1, y1, val);
1446   }
1447 }
1448
1449
1450 void
1451 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) {
1452
1453   double dy;
1454   i_img_dim x;
1455   
1456   for(x=x1; x<=x2; x++) {
1457     dy = y1+ (x-x1)/(double)(x2-x1)*(y2-y1);
1458     i_ppix(im, x, (i_img_dim)(dy+0.5), val);
1459   }
1460 }
1461
1462 /*
1463 =item i_line_aa(C<im>, C<x1>, C<x2>, C<y1>, C<y2>, C<color>, C<endp>)
1464
1465 =category Drawing
1466
1467 Anti-alias draws a line from (x1,y1) to (x2, y2) in color.
1468
1469 The point (x2, y2) is drawn only if C<endp> is set.
1470
1471 =cut
1472 */
1473
1474 void
1475 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) {
1476   i_img_dim x, y;
1477   i_img_dim dx, dy;
1478   i_img_dim p;
1479
1480   dx = x2 - x1;
1481   dy = y2 - y1;
1482
1483   /* choose variable to iterate on */
1484   if (i_abs(dx) > i_abs(dy)) {
1485     i_img_dim dx2, dy2, cpy;
1486     
1487     /* sort by x */
1488     if (x1 > x2) {
1489       i_img_dim t;
1490       t = x1; x1 = x2; x2 = t;
1491       t = y1; y1 = y2; y2 = t;
1492     }
1493     
1494     dx = i_abs(dx);
1495     dx2 = dx*2;
1496     dy = y2 - y1;
1497
1498     if (dy<0) {
1499       dy = -dy;
1500       cpy = -1;
1501     } else {
1502       cpy = 1;
1503     }
1504     dy2 = dy*2;
1505     p = dy2 - dx2; /* this has to be like this for AA */
1506     
1507     y = y1;
1508
1509     for(x=x1; x<x2-1; x++) {
1510       int ch;
1511       i_color tval;
1512       double t = (dy) ? -(float)(p)/(float)(dx2) : 1;
1513       double t1, t2;
1514
1515       if (t<0) t = 0;
1516       t1 = 1-t;
1517       t2 = t;
1518
1519       i_gpix(im,x+1,y,&tval);
1520       for(ch=0;ch<im->channels;ch++)
1521         tval.channel[ch]=(unsigned char)(t1*(float)tval.channel[ch]+t2*(float)val->channel[ch]);
1522       i_ppix(im,x+1,y,&tval);
1523
1524       i_gpix(im,x+1,y+cpy,&tval);
1525       for(ch=0;ch<im->channels;ch++)
1526         tval.channel[ch]=(unsigned char)(t2*(float)tval.channel[ch]+t1*(float)val->channel[ch]);
1527       i_ppix(im,x+1,y+cpy,&tval);
1528
1529       if (p<0) {
1530         p += dy2;
1531       } else {
1532         y += cpy;
1533         p += dy2-dx2;
1534       }
1535     }
1536   } else {
1537     i_img_dim dy2, dx2, cpx;
1538
1539     /* sort bx y */
1540     if (y1 > y2) {
1541       i_img_dim t;
1542       t = x1; x1 = x2; x2 = t;
1543       t = y1; y1 = y2; y2 = t;
1544     }
1545     
1546     dy = i_abs(dy);
1547     dx = x2 - x1;
1548     dy2 = dy*2;
1549
1550     if (dx<0) {
1551       dx = -dx;
1552       cpx = -1;
1553     } else {
1554       cpx = 1;
1555     }
1556     dx2 = dx*2;
1557     p = dx2 - dy2; /* this has to be like this for AA */
1558
1559     x = x1;
1560     
1561     for(y=y1; y<y2-1; y++) {
1562       int ch;
1563       i_color tval;
1564       double t = (dx) ? -(double)(p)/(double)(dy2) : 1;
1565       double t1, t2;
1566       
1567       if (t<0) t = 0;
1568       t1 = 1-t;
1569       t2 = t;
1570
1571       i_gpix(im,x,y+1,&tval);
1572       for(ch=0;ch<im->channels;ch++)
1573         tval.channel[ch]=(unsigned char)(t1*(double)tval.channel[ch]+t2*(double)val->channel[ch]);
1574       i_ppix(im,x,y+1,&tval);
1575
1576       i_gpix(im,x+cpx,y+1,&tval);
1577       for(ch=0;ch<im->channels;ch++)
1578         tval.channel[ch]=(unsigned char)(t2*(double)tval.channel[ch]+t1*(double)val->channel[ch]);
1579       i_ppix(im,x+cpx,y+1,&tval);
1580
1581       if (p<0) {
1582         p  += dx2;
1583       } else {
1584         x += cpx;
1585         p += dx2-dy2;
1586       }
1587     }
1588   }
1589
1590
1591   if (endp) {
1592     i_ppix(im, x1, y1, val);
1593     i_ppix(im, x2, y2, val);
1594   } else {
1595     if (x1 != x2 || y1 != y2) 
1596       i_ppix(im, x1, y1, val);
1597   }
1598 }
1599
1600
1601
1602 static double
1603 perm(i_img_dim n,i_img_dim k) {
1604   double r;
1605   i_img_dim i;
1606   r=1;
1607   for(i=k+1;i<=n;i++) r*=i;
1608   for(i=1;i<=(n-k);i++) r/=i;
1609   return r;
1610 }
1611
1612
1613 /* Note in calculating t^k*(1-t)^(n-k) 
1614    we can start by using t^0=1 so this simplifies to
1615    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
1616    to get a new level - this may lead to errors who knows lets test it */
1617
1618 void
1619 i_bezier_multi(i_img *im,int l,const double *x,const double *y, const i_color *val) {
1620   double *bzcoef;
1621   double t,cx,cy;
1622   int k,i;
1623   i_img_dim lx = 0,ly = 0;
1624   int n=l-1;
1625   double itr,ccoef;
1626
1627   /* this is the same size as the x and y arrays, so shouldn't overflow */
1628   bzcoef=mymalloc(sizeof(double)*l); /* checked 5jul05 tonyc */
1629   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
1630   ICL_info(val);
1631
1632
1633   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
1634   i=0;
1635   for(t=0;t<=1;t+=0.005) {
1636     cx=cy=0;
1637     itr=t/(1-t);
1638     ccoef=pow(1-t,n);
1639     for(k=0;k<l;k++) {
1640       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k); 
1641               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
1642
1643       cx+=bzcoef[k]*x[k]*ccoef;
1644       cy+=bzcoef[k]*y[k]*ccoef;
1645       ccoef*=itr;
1646     }
1647     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
1648     if (i++) { 
1649       i_line_aa(im,lx,ly,(i_img_dim)(0.5+cx),(i_img_dim)(0.5+cy),val, 1);
1650     }
1651       /*     i_ppix(im,(i_img_dim)(0.5+cx),(i_img_dim)(0.5+cy),val); */
1652     lx=(i_img_dim)(0.5+cx);
1653     ly=(i_img_dim)(0.5+cy);
1654   }
1655   ICL_info(val);
1656   myfree(bzcoef);
1657 }
1658
1659 /* Flood fill 
1660
1661    REF: Graphics Gems I. page 282+
1662
1663 */
1664
1665 /* This should be moved into a seperate file? */
1666
1667 /* This is the truncation used:
1668    
1669    a double is multiplied by 16 and then truncated.
1670    This means that 0 -> 0
1671    So a triangle of (0,0) (10,10) (10,0) Will look like it's
1672    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
1673
1674 */
1675
1676
1677 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in 
1678    graphics gems I */
1679
1680 /*
1681 struct stc {
1682   i_img_dim mylx,myrx; 
1683   i_img_dim dadlx,dadrx;
1684   i_img_dim myy;
1685   int mydirection;
1686 };
1687
1688 Not used code???
1689 */
1690
1691
1692 struct stack_element {
1693   i_img_dim myLx,myRx;
1694   i_img_dim dadLx,dadRx;
1695   i_img_dim myY;
1696   int myDirection;
1697 };
1698
1699
1700 /* create the link data to put push onto the stack */
1701
1702 static
1703 struct stack_element*
1704 crdata(i_img_dim left,i_img_dim right,i_img_dim dadl,i_img_dim dadr,i_img_dim y, int dir) {
1705   struct stack_element *ste;
1706   ste              = mymalloc(sizeof(struct stack_element)); /* checked 5jul05 tonyc */
1707   ste->myLx        = left;
1708   ste->myRx        = right;
1709   ste->dadLx       = dadl;
1710   ste->dadRx       = dadr;
1711   ste->myY         = y;
1712   ste->myDirection = dir;
1713   return ste;
1714 }
1715
1716 /* i_ccomp compares two colors and gives true if they are the same */
1717
1718 typedef int (*ff_cmpfunc)(i_color const *c1, i_color const *c2, int channels);
1719
1720 static int
1721 i_ccomp_normal(i_color const *val1, i_color const *val2, int ch) {
1722   int i;
1723   for(i = 0; i < ch; i++) 
1724     if (val1->channel[i] !=val2->channel[i])
1725       return 0;
1726   return 1;
1727 }
1728
1729 static int
1730 i_ccomp_border(i_color const *val1, i_color const *val2, int ch) {
1731   int i;
1732   for(i = 0; i < ch; i++) 
1733     if (val1->channel[i] !=val2->channel[i])
1734       return 1;
1735   return 0;
1736 }
1737
1738 static int
1739 i_lspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1740   i_color cval;
1741   while(1) {
1742     if (seedx-1 < 0) break;
1743     i_gpix(im,seedx-1,seedy,&cval);
1744     if (!cmpfunc(val,&cval,im->channels)) 
1745       break;
1746     seedx--;
1747   }
1748   return seedx;
1749 }
1750
1751 static int
1752 i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpfunc cmpfunc) {
1753   i_color cval;
1754   while(1) {
1755     if (seedx+1 > im->xsize-1) break;
1756     i_gpix(im,seedx+1,seedy,&cval);
1757     if (!cmpfunc(val,&cval,im->channels)) break;
1758     seedx++;
1759   }
1760   return seedx;
1761 }
1762
1763 #ifdef DEBUG_FLOOD_FILL
1764
1765 #define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir) \
1766   fprintf(stderr, "push(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
1767           i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
1768
1769 #define ST_POP_NOTE(left, right, dadl, dadr, y, dir) \
1770   fprintf(stderr, "popped(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
1771           i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
1772
1773 #define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)                  \
1774   fprintf(stderr, "stack(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
1775           i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
1776
1777 #else
1778
1779 #define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir)
1780
1781 #define ST_POP_NOTE(left, right, dadl, dadr, y, dir)
1782
1783 #define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)
1784
1785 #endif
1786
1787
1788 /* Macro to create a link and push on to the list */
1789
1790 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
1791   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
1792   ST_PUSH_NOTE(left, right, dadl, dadr, y, dir);                 \
1793   llist_push(st,&s);                                             \
1794 } while (0)
1795
1796 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
1797 /* No overflow check! */
1798  
1799 #define ST_POP() do {         \
1800   struct stack_element *s;    \
1801   llist_pop(st,&s);           \
1802   lx        = s->myLx;        \
1803   rx        = s->myRx;        \
1804   dadLx     = s->dadLx;       \
1805   dadRx     = s->dadRx;       \
1806   y         = s->myY;         \
1807   direction = s->myDirection; \
1808   ST_POP_NOTE(lx, rx, dadLx, dadRx, y, direction);      \
1809   myfree(s);                  \
1810 } while (0)
1811
1812 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
1813   i_img_dim pushrx = rx+1;                                              \
1814   i_img_dim pushlx = lx-1;                                              \
1815   ST_STACK_NOTE(lx, rx, dadLx, dadRx, y, dir);           \
1816   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
1817   if (rx > dadRx)                                                 \
1818     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
1819   if (lx < dadLx)                                               \
1820     ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
1821 } while (0)
1822
1823 #define SET(x,y) btm_set(btm,x,y)
1824
1825 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
1826 #define INSIDE(x,y, seed) \
1827   (assert((x) >= 0 && (x) < (im)->xsize && (y) >= 0 && (y) < (im)->ysize), \
1828    (!btm_test(btm,x,y) && \
1829      ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
1830
1831 /* The function that does all the real work */
1832
1833 static struct i_bitmap *
1834 i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
1835                  i_img_dim *bxminp, i_img_dim *bxmaxp, i_img_dim *byminp, i_img_dim *bymaxp,
1836                  i_color const *seed, ff_cmpfunc cmpfunc) {
1837   i_img_dim ltx, rtx;
1838   i_img_dim tx = 0;
1839
1840   i_img_dim bxmin = seedx;
1841   i_img_dim bxmax = seedx;
1842   i_img_dim bymin = seedy;
1843   i_img_dim bymax = seedy;
1844
1845   struct llist *st;
1846   struct i_bitmap *btm;
1847
1848   int channels;
1849   i_img_dim xsize,ysize;
1850   i_color cval; /* used by the INSIDE() macro */
1851
1852   channels = im->channels;
1853   xsize    = im->xsize;
1854   ysize    = im->ysize;
1855
1856   btm = btm_new(xsize, ysize);
1857   st  = llist_new(100, sizeof(struct stack_element*));
1858
1859   /* Find the starting span and fill it */
1860   ltx = i_lspan(im, seedx, seedy, seed, cmpfunc);
1861   rtx = i_rspan(im, seedx, seedy, seed, cmpfunc);
1862   for(tx=ltx; tx<=rtx; tx++) SET(tx, seedy);
1863   bxmin = ltx;
1864   bxmax = rtx;
1865
1866   ST_PUSH(ltx, rtx, ltx, rtx, seedy+1,  1);
1867   ST_PUSH(ltx, rtx, ltx, rtx, seedy-1, -1);
1868
1869   while(st->count) {
1870     /* Stack variables */
1871     i_img_dim lx,rx;
1872     i_img_dim dadLx,dadRx;
1873     i_img_dim y;
1874     int direction;
1875
1876     i_img_dim x;
1877     int wasIn=0;
1878
1879     ST_POP(); /* sets lx, rx, dadLx, dadRx, y, direction */
1880
1881
1882     if (y<0 || y>ysize-1) continue;
1883     if (bymin > y) bymin=y; /* in the worst case an extra line */
1884     if (bymax < y) bymax=y; 
1885
1886
1887     x = lx+1;
1888     if ( lx >= 0 && (wasIn = INSIDE(lx, y, seed)) ) {
1889       SET(lx, y);
1890       lx--;
1891       while(lx >= 0 && INSIDE(lx, y, seed)) {
1892         SET(lx,y);
1893         lx--;
1894       }
1895       /* lx should point at the left-most INSIDE() pixel */
1896       ++lx;
1897     }
1898
1899     if (bxmin > lx) bxmin = lx;
1900     while(x <= xsize-1) {
1901       /*  printf("x=%d\n",x); */
1902       if (wasIn) {
1903         
1904         if (INSIDE(x, y, seed)) {
1905           /* case 1: was inside, am still inside */
1906           SET(x,y);
1907         } else {
1908           /* case 2: was inside, am no longer inside: just found the
1909              right edge of a span */
1910           ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1911
1912           if (bxmax < x) bxmax = x;
1913           wasIn=0;
1914         }
1915       } else {
1916         if (x > rx) goto EXT;
1917         if (INSIDE(x, y, seed)) {
1918           SET(x, y);
1919           /* case 3: Wasn't inside, am now: just found the start of a new run */
1920           wasIn = 1;
1921             lx = x;
1922         } else {
1923           /* case 4: Wasn't inside, still isn't */
1924         }
1925       }
1926       x++;
1927     }
1928   EXT: /* out of loop */
1929     if (wasIn) {
1930       /* hit an edge of the frame buffer while inside a run */
1931       ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
1932       if (bxmax < x) bxmax = x;
1933     }
1934   }
1935
1936   llist_destroy(st);
1937
1938   *bxminp = bxmin;
1939   *bxmaxp = bxmax;
1940   *byminp = bymin;
1941   *bymaxp = bymax;
1942
1943   return btm;
1944 }
1945
1946 /*
1947 =item i_flood_fill(C<im>, C<seedx>, C<seedy>, C<color>)
1948
1949 =category Drawing
1950 =synopsis i_flood_fill(im, 50, 50, &color);
1951
1952 Flood fills the 4-connected region starting from the point (C<seedx>,
1953 C<seedy>) with I<color>.
1954
1955 Returns false if (C<seedx>, C<seedy>) are outside the image.
1956
1957 =cut
1958 */
1959
1960 undef_int
1961 i_flood_fill(i_img *im, i_img_dim seedx, i_img_dim seedy, const i_color *dcol) {
1962   i_img_dim bxmin, bxmax, bymin, bymax;
1963   struct i_bitmap *btm;
1964   i_img_dim x, y;
1965   i_color val;
1966   dIMCTXim(im);
1967
1968   im_log((aIMCTX, 1, "i_flood_fill(im %p, seed(" i_DFp "), col %p)",
1969           im, i_DFcp(seedx, seedy), dcol));
1970
1971   im_clear_error(aIMCTX);
1972   if (seedx < 0 || seedx >= im->xsize ||
1973       seedy < 0 || seedy >= im->ysize) {
1974     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
1975     return 0;
1976   }
1977
1978   /* Get the reference color */
1979   i_gpix(im, seedx, seedy, &val);
1980
1981   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
1982                          &val, i_ccomp_normal);
1983
1984   for(y=bymin;y<=bymax;y++)
1985     for(x=bxmin;x<=bxmax;x++)
1986       if (btm_test(btm,x,y)) 
1987         i_ppix(im,x,y,dcol);
1988   btm_destroy(btm);
1989   return 1;
1990 }
1991
1992 /*
1993 =item i_flood_cfill(C<im>, C<seedx>, C<seedy>, C<fill>)
1994
1995 =category Drawing
1996 =synopsis i_flood_cfill(im, 50, 50, fill);
1997
1998 Flood fills the 4-connected region starting from the point (C<seedx>,
1999 C<seedy>) with C<fill>.
2000
2001 Returns false if (C<seedx>, C<seedy>) are outside the image.
2002
2003 =cut
2004 */
2005
2006 undef_int
2007 i_flood_cfill(i_img *im, i_img_dim seedx, i_img_dim seedy, i_fill_t *fill) {
2008   i_img_dim bxmin, bxmax, bymin, bymax;
2009   struct i_bitmap *btm;
2010   i_color val;
2011   dIMCTXim(im);
2012
2013   im_log((aIMCTX, 1, "i_flood_cfill(im %p, seed(" i_DFp "), fill %p)",
2014           im, i_DFcp(seedx, seedy), fill));
2015
2016   im_clear_error(aIMCTX);
2017   
2018   if (seedx < 0 || seedx >= im->xsize ||
2019       seedy < 0 || seedy >= im->ysize) {
2020     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
2021     return 0;
2022   }
2023
2024   /* Get the reference color */
2025   i_gpix(im, seedx, seedy, &val);
2026
2027   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2028                          &val, i_ccomp_normal);
2029
2030   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
2031
2032   btm_destroy(btm);
2033   return 1;
2034 }
2035
2036 /*
2037 =item i_flood_fill_border(C<im>, C<seedx>, C<seedy>, C<color>, C<border>)
2038
2039 =category Drawing
2040 =synopsis i_flood_fill_border(im, 50, 50, &color, &border);
2041
2042 Flood fills the 4-connected region starting from the point (C<seedx>,
2043 C<seedy>) with C<color>, fill stops when the fill reaches a pixels
2044 with color C<border>.
2045
2046 Returns false if (C<seedx>, C<seedy>) are outside the image.
2047
2048 =cut
2049 */
2050
2051 undef_int
2052 i_flood_fill_border(i_img *im, i_img_dim seedx, i_img_dim seedy, const i_color *dcol,
2053                     const i_color *border) {
2054   i_img_dim bxmin, bxmax, bymin, bymax;
2055   struct i_bitmap *btm;
2056   i_img_dim x, y;
2057   dIMCTXim(im);
2058
2059   im_log((aIMCTX, 1, "i_flood_cfill(im %p, seed(" i_DFp "), dcol %p, border %p)",
2060           im, i_DFcp(seedx, seedy), dcol, border));
2061
2062   im_clear_error(aIMCTX);
2063   if (seedx < 0 || seedx >= im->xsize ||
2064       seedy < 0 || seedy >= im->ysize) {
2065     im_push_error(aIMCTX, 0, "i_flood_cfill: Seed pixel outside of image");
2066     return 0;
2067   }
2068
2069   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2070                          border, i_ccomp_border);
2071
2072   for(y=bymin;y<=bymax;y++)
2073     for(x=bxmin;x<=bxmax;x++)
2074       if (btm_test(btm,x,y)) 
2075         i_ppix(im,x,y,dcol);
2076   btm_destroy(btm);
2077   return 1;
2078 }
2079
2080 /*
2081 =item i_flood_cfill_border(C<im>, C<seedx>, C<seedy>, C<fill>, C<border>)
2082
2083 =category Drawing
2084 =synopsis i_flood_cfill_border(im, 50, 50, fill, border);
2085
2086 Flood fills the 4-connected region starting from the point (C<seedx>,
2087 C<seedy>) with C<fill>, the fill stops when it reaches pixels of color
2088 C<border>.
2089
2090 Returns false if (C<seedx>, C<seedy>) are outside the image.
2091
2092 =cut
2093 */
2094
2095 undef_int
2096 i_flood_cfill_border(i_img *im, i_img_dim seedx, i_img_dim seedy, i_fill_t *fill,
2097                      const i_color *border) {
2098   i_img_dim bxmin, bxmax, bymin, bymax;
2099   struct i_bitmap *btm;
2100   dIMCTXim(im);
2101
2102   im_log((aIMCTX, 1, "i_flood_cfill_border(im %p, seed(" i_DFp "), fill %p, border %p)",
2103           im, i_DFcp(seedx, seedy), fill, border));
2104
2105   im_clear_error(aIMCTX);
2106   
2107   if (seedx < 0 || seedx >= im->xsize ||
2108       seedy < 0 || seedy >= im->ysize) {
2109     im_push_error(aIMCTX, 0, "i_flood_cfill_border: Seed pixel outside of image");
2110     return 0;
2111   }
2112
2113   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax,
2114                          border, i_ccomp_border);
2115
2116   cfill_from_btm(im, fill, btm, bxmin, bxmax, bymin, bymax);
2117
2118   btm_destroy(btm);
2119
2120   return 1;
2121 }
2122
2123 static void
2124 cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm, 
2125                i_img_dim bxmin, i_img_dim bxmax, i_img_dim bymin, i_img_dim bymax) {
2126   i_img_dim x, y;
2127   i_img_dim start;
2128
2129   i_render r;
2130
2131   i_render_init(&r, im, bxmax - bxmin + 1);
2132
2133   for(y=bymin; y<=bymax; y++) {
2134     x = bxmin;
2135     while (x <= bxmax) {
2136       while (x <= bxmax && !btm_test(btm, x, y)) {
2137         ++x;
2138       }
2139       if (btm_test(btm, x, y)) {
2140         start = x;
2141         while (x <= bxmax && btm_test(btm, x, y)) {
2142           ++x;
2143         }
2144         i_render_fill(&r, start, y, x-start, NULL, fill);
2145       }
2146     }
2147   }
2148   i_render_done(&r);
2149 }
2150
2151 /*
2152 =back
2153
2154 =cut
2155 */