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