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