Switched i_draw to i_line, added endpoint boolean condition,
[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) {
250 float alpha;
251 lx = sx; ly = sy;
252 polar_to_plane(x, y, angle, radius, &cx, &cy);
253 sx = cx; sy = cy;
254
255 if (fabs(cx-lx) > fabs(cy-ly)) {
256 int ccx, ccy;
257 if (lx>cx) {
258 ccx = lx; lx = cx; cx = ccx;
259 ccy = ly; ly = cy; cy = ccy;
260 }
261
262 for(ccx=lx; ccx<=cx; ccx++) {
263 ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
264 i_mmarray_add(dot, ccx, ccy);
265 }
266 } else {
267 int ccx, ccy;
268
269 if (ly>cy) {
270 ccy = ly; ly = cy; cy = ccy;
271 ccx = lx; lx = cx; cx = ccx;
272 }
273
274 for(ccy=ly; ccy<=cy; ccy++) {
275 if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
276 i_mmarray_add(dot, ccx, ccy);
277 }
278 }
279 }
280}
281
282/* Get the number of subpixels covered */
283
284static
285int
286i_pixel_coverage(i_mmarray *dot, int x, int y) {
287 frac minx = x*16;
288 frac maxx = minx+15;
289 frac cy;
290 int cnt = 0;
291
292 for(cy=y*16; cy<(y+1)*16; cy++) {
293 frac tmin = dot->data[cy].min;
294 frac tmax = dot->data[cy].max;
295
296 if (tmax == -1 || tmin > maxx || tmax < minx) continue;
297
298 if (tmin < minx) tmin = minx;
299 if (tmax > maxx) tmax = maxx;
300
301 cnt+=1+tmax-tmin;
302 }
303 return cnt;
304}
305
306void
307i_circle_aa(i_img *im, float x, float y, float rad, i_color *val) {
308 i_mmarray dot;
309 i_color temp;
310 int ly;
311
312 mm_log((1, "i_circle_aa(im %p, x %d, y %d, rad %.2f, val %p)\n", im, x, y, rad, val));
313
314 i_mmarray_cr(&dot,16*im->ysize);
315 make_minmax_list(&dot, x, y, rad);
316
317 for(ly = 0; ly<im->ysize; ly++) {
318 int ix, cy, cnt = 0, minx = INT_MAX, maxx = INT_MIN;
319
320 /* Find the left/rightmost set subpixels */
321 for(cy = 0; cy<16; cy++) {
322 frac tmin = dot.data[ly*16+cy].min;
323 frac tmax = dot.data[ly*16+cy].max;
324 if (tmax == -1) continue;
325
326 if (minx > tmin) minx = tmin;
327 if (maxx < tmax) maxx = tmax;
328 }
329
330 if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
331
332 minx /= 16;
333 maxx /= 16;
334 for(ix=minx; ix<=maxx; ix++) {
335 int cnt = i_pixel_coverage(&dot, ix, ly);
336 if (cnt>255) cnt = 255;
337 if (cnt) { /* should never be true */
338 int ch;
339 float ratio = (float)cnt/255.0;
340 i_gpix(im, ix, ly, &temp);
341 for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
342 i_ppix(im, ix, ly, &temp);
343 }
344 }
345 }
4b19f77a 346 i_mmarray_dst(&dot);
6af18d2b
AMH
347}
348
349
350
351
352
353
02d1d628
AMH
354void
355i_box(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
356 int x,y;
357 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));
358 for(x=x1;x<x2+1;x++) {
359 i_ppix(im,x,y1,val);
360 i_ppix(im,x,y2,val);
361 }
362 for(y=y1;y<y2+1;y++) {
363 i_ppix(im,x1,y,val);
364 i_ppix(im,x2,y,val);
365 }
366}
367
368void
369i_box_filled(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
370 int x,y;
371 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));
372 for(x=x1;x<x2+1;x++) for (y=y1;y<y2+1;y++) i_ppix(im,x,y,val);
373}
374
f1ac5027
TC
375void
376i_box_cfill(i_img *im,int x1,int y1,int x2,int y2,i_fill_t *fill) {
377 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));
378
379 ++x2;
380 if (im->bits == i_8_bits && fill->fill_with_color) {
381 i_color *line = mymalloc(sizeof(i_color) * (x2 - x1));
efdc2568
TC
382 i_color *work = NULL;
383 if (fill->combine)
384 work = mymalloc(sizeof(i_color) * (x2-x1));
f1ac5027 385 while (y1 <= y2) {
43c5dacb 386 if (fill->combine) {
f1ac5027 387 i_glin(im, x1, x2, y1, line);
43c5dacb
TC
388 (fill->fill_with_color)(fill, x1, y1, x2-x1, im->channels, work);
389 (fill->combine)(line, work, im->channels, x2-x1);
390 }
391 else {
392 (fill->fill_with_color)(fill, x1, y1, x2-x1, im->channels, line);
393 }
f1ac5027
TC
394 i_plin(im, x1, x2, y1, line);
395 ++y1;
396 }
397 myfree(line);
efdc2568
TC
398 if (work)
399 myfree(work);
f1ac5027
TC
400 }
401 else {
402 i_fcolor *line = mymalloc(sizeof(i_fcolor) * (x2 - x1));
efdc2568
TC
403 i_fcolor *work;
404 work = mymalloc(sizeof(i_fcolor) * (x2 - x1));
405
f1ac5027 406 while (y1 <= y2) {
43c5dacb 407 if (fill->combine) {
f1ac5027 408 i_glinf(im, x1, x2, y1, line);
43c5dacb
TC
409 (fill->fill_with_fcolor)(fill, x1, y1, x2-x1, im->channels, work);
410 (fill->combinef)(line, work, im->channels, x2-x1);
411 }
412 else {
413 (fill->fill_with_fcolor)(fill, x1, y1, x2-x1, im->channels, line);
414 }
f1ac5027 415 i_plinf(im, x1, x2, y1, line);
2de568dc 416 ++y1;
f1ac5027
TC
417 }
418 myfree(line);
efdc2568
TC
419 if (work)
420 myfree(work);
f1ac5027
TC
421 }
422}
02d1d628 423
aa833c97
AMH
424
425/*
426=item i_line(im, x1, y1, x2, y2, val, endp)
427
428Draw a line to image using bresenhams linedrawing algorithm
429
430 im - image to draw to
431 x1 - starting x coordinate
432 y1 - starting x coordinate
433 x2 - starting x coordinate
434 y2 - starting x coordinate
435 val - color to write to image
436 endp - endpoint flag (boolean)
437
438=cut
439*/
440
02d1d628 441void
aa833c97
AMH
442i_line(i_img *im, int x1, int y1, int x2, int y2, i_color *val, int endp) {
443 int x, y;
444 int dx, dy;
445 int p;
446 unsigned char *cp;
02d1d628 447
aa833c97
AMH
448 dx = x2 - x1;
449 dy = y2 - y1;
02d1d628 450
aa833c97
AMH
451
452 /* choose variable to iterate on */
453 if (abs(dx)>abs(dy)) {
454 int dx2, dy2, cpy;
455
456 /* sort by x */
457 if (x1 > x2) {
458 int t;
459 t = x1; x1 = x2; x2 = t;
460 t = y1; y1 = y2; y2 = t;
02d1d628 461 }
aa833c97
AMH
462
463 dx = abs(dx);
464 dx2 = dx*2;
465 dy = y2 - y1;
466
467 if (dy<0) {
468 dy = -dy;
469 cpy = -1;
470 } else {
471 cpy = 1;
472 }
473 dy2 = dy*2;
474 p = dy2 - dx;
475
476
477 y = y1;
478 for(x=x1; x<x2-1; x++) {
479 if (p<0) {
480 p += dy2;
481 } else {
482 y += cpy;
483 p += dy2-dx2;
484 }
485 i_ppix(im, x+1, y, val);
02d1d628 486 }
aa833c97
AMH
487 } else {
488 int dy2, dx2, cpx;
489
490 /* sort bx y */
491 if (y1 > y2) {
492 int t;
493 t = x1; x1 = x2; x2 = t;
494 t = y1; y1 = y2; y2 = t;
495 }
496
497 dy = abs(dy);
498 dx = x2 - x1;
499 dy2 = dy*2;
500
501 if (dx<0) {
502 dx = -dx;
503 cpx = -1;
504 } else {
505 cpx = 1;
506 }
507 dx2 = dx*2;
508 p = dx2 - dy;
509
510 x = x1;
511
512 for(y=y1; y<y2-1; y++) {
513 if (p<0) {
514 p += dx2;
515 } else {
516 x += cpx;
517 p += dx2-dy2;
518 }
519 i_ppix(im, x, y+1, val);
520 }
521 }
522 if (endp) {
523 i_ppix(im, x1, y1, val);
524 i_ppix(im, x2, y2, val);
525 } else {
526 if (x1 != x2 || y1 != y2)
527 i_ppix(im, x1, y1, val);
528 }
02d1d628
AMH
529}
530
aa833c97 531
02d1d628
AMH
532void
533i_line_aa(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
534 i_color tval;
535 float alpha;
536 float dsec,dfrac;
537 int temp,dx,dy,isec,ch;
538
539 mm_log((1,"i_draw(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
540
541 dy=y2-y1;
542 dx=x2-x1;
543
544 if (abs(dx)>abs(dy)) { /* alpha < 1 */
545 if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
546 alpha=(float)(y2-y1)/(float)(x2-x1);
547
548 dsec=y1;
549 while(x1<=x2) {
550 isec=(int)dsec;
551 dfrac=dsec-isec;
552 /* dfrac=1-(1-dfrac)*(1-dfrac); */
553 /* This is something we can play with to try to get better looking lines */
554
555 i_gpix(im,x1,isec,&tval);
556 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
557 i_ppix(im,x1,isec,&tval);
558
559 i_gpix(im,x1,isec+1,&tval);
560 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
561 i_ppix(im,x1,isec+1,&tval);
562
563 dsec+=alpha;
564 x1++;
565 }
566 } else {
567 if (y2<y1) { temp=y1; y1=y2; y2=temp; temp=x1; x1=x2; x2=temp; }
568 alpha=(float)(x2-x1)/(float)(y2-y1);
569 dsec=x1;
570 while(y1<=y2) {
571 isec=(int)dsec;
572 dfrac=dsec-isec;
573 /* dfrac=sqrt(dfrac); */
574 /* This is something we can play with */
575 i_gpix(im,isec,y1,&tval);
576 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
577 i_ppix(im,isec,y1,&tval);
578
579 i_gpix(im,isec+1,y1,&tval);
580 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
581 i_ppix(im,isec+1,y1,&tval);
582
583 dsec+=alpha;
584 y1++;
585 }
586 }
587}
588
b33c08f8 589static double
02d1d628
AMH
590perm(int n,int k) {
591 double r;
592 int i;
593 r=1;
594 for(i=k+1;i<=n;i++) r*=i;
595 for(i=1;i<=(n-k);i++) r/=i;
596 return r;
597}
598
599
600/* Note in calculating t^k*(1-t)^(n-k)
601 we can start by using t^0=1 so this simplifies to
602 t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
603 to get a new level - this may lead to errors who knows lets test it */
604
605void
606i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
607 double *bzcoef;
608 double t,cx,cy;
609 int k,i;
610 int lx = 0,ly = 0;
611 int n=l-1;
612 double itr,ccoef;
613
614
615 bzcoef=mymalloc(sizeof(double)*l);
616 for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
617 ICL_info(val);
618
619
620 /* for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
621 i=0;
622 for(t=0;t<=1;t+=0.005) {
623 cx=cy=0;
624 itr=t/(1-t);
625 ccoef=pow(1-t,n);
626 for(k=0;k<l;k++) {
627 /* cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
628 cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
629
630 cx+=bzcoef[k]*x[k]*ccoef;
631 cy+=bzcoef[k]*y[k]*ccoef;
632 ccoef*=itr;
633 }
634 /* printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
635 if (i++) {
636 i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val);
637 }
638 /* i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
639 lx=(int)(0.5+cx);
640 ly=(int)(0.5+cy);
641 }
642 ICL_info(val);
643 myfree(bzcoef);
644}
645
646
647
9982a307
AMH
648
649
650
651
652
653
654
655
02d1d628
AMH
656/* Flood fill
657
658 REF: Graphics Gems I. page 282+
659
660*/
661
02d1d628
AMH
662/* This should be moved into a seperate file? */
663
664/* This is the truncation used:
665
666 a double is multiplied by 16 and then truncated.
667 This means that 0 -> 0
668 So a triangle of (0,0) (10,10) (10,0) Will look like it's
669 not filling the (10,10) point nor the (10,0)-(10,10) line segment
670
671*/
672
673
02d1d628
AMH
674/* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
675 graphics gems I */
676
677/*
678struct stc {
679 int mylx,myrx;
680 int dadlx,dadrx;
681 int myy;
682 int mydirection;
683};
684
685Not used code???
686*/
687
688
689struct stack_element {
690 int myLx,myRx;
691 int dadLx,dadRx;
692 int myY;
693 int myDirection;
694};
695
696
697/* create the link data to put push onto the stack */
698
699static
700struct stack_element*
701crdata(int left,int right,int dadl,int dadr,int y, int dir) {
702 struct stack_element *ste;
a73aeb5f
AMH
703 ste = mymalloc(sizeof(struct stack_element));
704 ste->myLx = left;
705 ste->myRx = right;
706 ste->dadLx = dadl;
707 ste->dadRx = dadr;
708 ste->myY = y;
709 ste->myDirection = dir;
02d1d628
AMH
710 return ste;
711}
712
713/* i_ccomp compares two colors and gives true if they are the same */
714
715static int
716i_ccomp(i_color *val1,i_color *val2,int ch) {
717 int i;
718 for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
719 return 1;
720}
721
722
723static int
e25e59b1 724i_lspan(i_img *im, int seedx, int seedy, i_color *val) {
02d1d628
AMH
725 i_color cval;
726 while(1) {
727 if (seedx-1 < 0) break;
728 i_gpix(im,seedx-1,seedy,&cval);
729 if (!i_ccomp(val,&cval,im->channels)) break;
730 seedx--;
731 }
732 return seedx;
733}
734
735static int
e25e59b1 736i_rspan(i_img *im, int seedx, int seedy, i_color *val) {
02d1d628
AMH
737 i_color cval;
738 while(1) {
739 if (seedx+1 > im->xsize-1) break;
740 i_gpix(im,seedx+1,seedy,&cval);
741 if (!i_ccomp(val,&cval,im->channels)) break;
742 seedx++;
743 }
744 return seedx;
745}
746
747/* Macro to create a link and push on to the list */
748
e25e59b1
AMH
749#define ST_PUSH(left,right,dadl,dadr,y,dir) do { \
750 struct stack_element *s = crdata(left,right,dadl,dadr,y,dir); \
751 llist_push(st,&s); \
752} while (0)
02d1d628
AMH
753
754/* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
755/* No overflow check! */
756
e25e59b1
AMH
757#define ST_POP() do { \
758 struct stack_element *s; \
759 llist_pop(st,&s); \
760 lx = s->myLx; \
761 rx = s->myRx; \
762 dadLx = s->dadLx; \
763 dadRx = s->dadRx; \
764 y = s->myY; \
765 direction = s->myDirection; \
766 myfree(s); \
767} while (0)
768
769#define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do { \
770 int pushrx = rx+1; \
771 int pushlx = lx-1; \
772 ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir); \
773 if (rx > dadRx) \
774 ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir); \
775 if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir); \
776} while (0)
777
778#define SET(x,y) btm_set(btm,x,y)
02d1d628 779
86d20cb9 780/* INSIDE returns true if pixel is correct color and we haven't set it before. */
02d1d628
AMH
781#define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels) ) ))
782
02d1d628 783
02d1d628 784
aa833c97
AMH
785/* The function that does all the real work */
786
787static struct i_bitmap *
788i_flood_fill_low(i_img *im,int seedx,int seedy,
789 int *bxminp, int *bxmaxp, int *byminp, int *bymaxp) {
02d1d628 790
aa833c97
AMH
791 /*
792 int lx,rx;
793 int y;
794 int direction;
795 int dadLx,dadRx;
796 int wasIn=0;
797 */
798 int ltx, rtx;
799 int tx = 0;
02d1d628 800
e25e59b1
AMH
801 int bxmin = seedx;
802 int bxmax = seedx;
803 int bymin = seedy;
804 int bymax = seedy;
02d1d628
AMH
805
806 struct llist *st;
807 struct i_bitmap *btm;
808
809 int channels,xsize,ysize;
aa833c97 810 i_color cval,val;
02d1d628 811
a73aeb5f
AMH
812 channels = im->channels;
813 xsize = im->xsize;
814 ysize = im->ysize;
02d1d628 815
86d20cb9
AMH
816 btm = btm_new(xsize, ysize);
817 st = llist_new(100, sizeof(struct stack_element*));
02d1d628
AMH
818
819 /* Get the reference color */
86d20cb9 820 i_gpix(im, seedx, seedy, &val);
02d1d628
AMH
821
822 /* Find the starting span and fill it */
aa833c97
AMH
823 ltx = i_lspan(im, seedx, seedy, &val);
824 rtx = i_rspan(im, seedx, seedy, &val);
825 for(tx=ltx; tx<=rtx; tx++) SET(tx, seedy);
02d1d628 826
aa833c97
AMH
827 ST_PUSH(ltx, rtx, ltx, rtx, seedy+1, 1);
828 ST_PUSH(ltx, rtx, ltx, rtx, seedy-1, -1);
02d1d628
AMH
829
830 while(st->count) {
aa833c97
AMH
831 /* Stack variables */
832 int lx,rx;
833 int dadLx,dadRx;
834 int y;
835 int direction;
e25e59b1 836
aa833c97
AMH
837 int x;
838 int wasIn=0;
02d1d628 839
aa833c97
AMH
840 ST_POP(); /* sets lx, rx, dadLx, dadRx, y, direction */
841
842
843 if (y<0 || y>ysize-1) continue;
02d1d628
AMH
844 if (bymin > y) bymin=y; /* in the worst case an extra line */
845 if (bymax < y) bymax=y;
846
e25e59b1
AMH
847
848 x = lx+1;
aa833c97
AMH
849 if ( lx >= 0 && (wasIn = INSIDE(lx, y)) ) {
850 SET(lx, y);
02d1d628 851 lx--;
aa833c97 852 while(INSIDE(lx, y) && lx > 0) {
02d1d628
AMH
853 SET(lx,y);
854 lx--;
855 }
856 }
857
86d20cb9 858 if (bxmin > lx) bxmin = lx;
02d1d628
AMH
859 while(x <= xsize-1) {
860 /* printf("x=%d\n",x); */
861 if (wasIn) {
862
aa833c97 863 if (INSIDE(x, y)) {
02d1d628
AMH
864 /* case 1: was inside, am still inside */
865 SET(x,y);
866 } else {
867 /* case 2: was inside, am no longer inside: just found the
868 right edge of a span */
aa833c97 869 ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
02d1d628 870
aa833c97 871 if (bxmax < x) bxmax = x;
02d1d628
AMH
872 wasIn=0;
873 }
874 } else {
aa833c97
AMH
875 if (x > rx) goto EXT;
876 if (INSIDE(x, y)) {
877 SET(x, y);
02d1d628 878 /* case 3: Wasn't inside, am now: just found the start of a new run */
aa833c97
AMH
879 wasIn = 1;
880 lx = x;
02d1d628
AMH
881 } else {
882 /* case 4: Wasn't inside, still isn't */
883 }
884 }
885 x++;
886 }
887 EXT: /* out of loop */
888 if (wasIn) {
889 /* hit an edge of the frame buffer while inside a run */
aa833c97
AMH
890 ST_STACK(direction, dadLx, dadRx, lx, (x-1), y);
891 if (bxmax < x) bxmax = x;
02d1d628
AMH
892 }
893 }
02d1d628 894
02d1d628 895 llist_destroy(st);
cc6483e0 896
aa833c97
AMH
897 *bxminp = bxmin;
898 *bxmaxp = bxmax;
899 *byminp = bymin;
900 *bymaxp = bymax;
cc6483e0 901
aa833c97
AMH
902 return btm;
903}
cc6483e0
TC
904
905
cc6483e0 906
cc6483e0 907
aa833c97
AMH
908undef_int
909i_flood_fill(i_img *im, int seedx, int seedy, i_color *dcol) {
910 int bxmin, bxmax, bymin, bymax;
911 struct i_bitmap *btm;
912 int x, y;
cc6483e0 913
aa833c97
AMH
914 i_clear_error();
915 if (seedx < 0 || seedx >= im->xsize ||
916 seedy < 0 || seedy >= im->ysize) {
917 i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
918 return 0;
cc6483e0 919 }
cc6483e0 920
aa833c97 921 btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax);
cc6483e0 922
aa833c97
AMH
923 for(y=bymin;y<=bymax;y++)
924 for(x=bxmin;x<=bxmax;x++)
925 if (btm_test(btm,x,y))
926 i_ppix(im,x,y,dcol);
927 btm_destroy(btm);
928 return 1;
cc6483e0
TC
929}
930
aa833c97
AMH
931
932
a321d497 933undef_int
cc6483e0
TC
934i_flood_cfill(i_img *im, int seedx, int seedy, i_fill_t *fill) {
935 int bxmin, bxmax, bymin, bymax;
936 struct i_bitmap *btm;
937 int x, y;
938 int start;
939
aa833c97 940 i_clear_error();
a321d497
AMH
941
942 if (seedx < 0 || seedx >= im->xsize ||
943 seedy < 0 || seedy >= im->ysize) {
3e1e2ed3 944 i_push_error(0, "i_flood_cfill: Seed pixel outside of image");
a321d497
AMH
945 return 0;
946 }
947
cc6483e0
TC
948 btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax);
949
950 if (im->bits == i_8_bits && fill->fill_with_color) {
951 i_color *line = mymalloc(sizeof(i_color) * (bxmax - bxmin));
efdc2568
TC
952 i_color *work = NULL;
953 if (fill->combine)
954 work = mymalloc(sizeof(i_color) * (bxmax - bxmin));
cc6483e0 955
aa833c97 956 for(y=bymin; y<=bymax; y++) {
cc6483e0
TC
957 x = bxmin;
958 while (x < bxmax) {
959 while (x < bxmax && !btm_test(btm, x, y)) {
960 ++x;
961 }
962 if (btm_test(btm, x, y)) {
963 start = x;
964 while (x < bxmax && btm_test(btm, x, y)) {
965 ++x;
966 }
43c5dacb 967 if (fill->combine) {
cc6483e0 968 i_glin(im, start, x, y, line);
43c5dacb
TC
969 (fill->fill_with_color)(fill, start, y, x-start, im->channels,
970 work);
971 (fill->combine)(line, work, im->channels, x-start);
972 }
973 else {
974 (fill->fill_with_color)(fill, start, y, x-start, im->channels,
975 line);
976 }
cc6483e0
TC
977 i_plin(im, start, x, y, line);
978 }
979 }
980 }
981 myfree(line);
efdc2568
TC
982 if (work)
983 myfree(work);
cc6483e0
TC
984 }
985 else {
986 i_fcolor *line = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
efdc2568
TC
987 i_fcolor *work = NULL;
988 if (fill->combinef)
989 work = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
cc6483e0
TC
990
991 for(y=bymin;y<=bymax;y++) {
992 x = bxmin;
993 while (x < bxmax) {
994 while (x < bxmax && !btm_test(btm, x, y)) {
995 ++x;
996 }
997 if (btm_test(btm, x, y)) {
998 start = x;
999 while (x < bxmax && btm_test(btm, x, y)) {
1000 ++x;
1001 }
43c5dacb 1002 if (fill->combinef) {
cc6483e0 1003 i_glinf(im, start, x, y, line);
43c5dacb
TC
1004 (fill->fill_with_fcolor)(fill, start, y, x-start, im->channels,
1005 work);
1006 (fill->combinef)(line, work, im->channels, x-start);
1007 }
1008 else {
1009 (fill->fill_with_fcolor)(fill, start, y, x-start, im->channels,
1010 line);
1011 }
cc6483e0
TC
1012 i_plinf(im, start, x, y, line);
1013 }
1014 }
1015 }
1016 myfree(line);
efdc2568
TC
1017 if (work)
1018 myfree(work);
cc6483e0
TC
1019 }
1020
1021 btm_destroy(btm);
a321d497 1022 return 1;
cc6483e0 1023}