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