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