hide or rename any symbols that are likely to conflict with other
[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
AMH
423
424void
425i_draw(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
426 double alpha;
427 double dsec;
428 int temp;
429
430 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));
431
432 alpha=(double)(y2-y1)/(double)(x2-x1);
433 if (fabs(alpha)<1)
434 {
435 if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
436 dsec=y1;
437 while(x1<x2)
438 {
439 dsec+=alpha;
440 i_ppix(im,x1,(int)(dsec+0.5),val);
441 x1++;
442 }
443 }
444 else
445 {
446 alpha=1/alpha;
447 if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
448 dsec=x1;
449 while(y1<y2)
450 {
451 dsec+=alpha;
452 i_ppix(im,(int)(dsec+0.5),y1,val);
453 y1++;
454 }
455 }
456 mm_log((1,"i_draw: alpha=%f.\n",alpha));
457}
458
459void
460i_line_aa(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
461 i_color tval;
462 float alpha;
463 float dsec,dfrac;
464 int temp,dx,dy,isec,ch;
465
466 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));
467
468 dy=y2-y1;
469 dx=x2-x1;
470
471 if (abs(dx)>abs(dy)) { /* alpha < 1 */
472 if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
473 alpha=(float)(y2-y1)/(float)(x2-x1);
474
475 dsec=y1;
476 while(x1<=x2) {
477 isec=(int)dsec;
478 dfrac=dsec-isec;
479 /* dfrac=1-(1-dfrac)*(1-dfrac); */
480 /* This is something we can play with to try to get better looking lines */
481
482 i_gpix(im,x1,isec,&tval);
483 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
484 i_ppix(im,x1,isec,&tval);
485
486 i_gpix(im,x1,isec+1,&tval);
487 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
488 i_ppix(im,x1,isec+1,&tval);
489
490 dsec+=alpha;
491 x1++;
492 }
493 } else {
494 if (y2<y1) { temp=y1; y1=y2; y2=temp; temp=x1; x1=x2; x2=temp; }
495 alpha=(float)(x2-x1)/(float)(y2-y1);
496 dsec=x1;
497 while(y1<=y2) {
498 isec=(int)dsec;
499 dfrac=dsec-isec;
500 /* dfrac=sqrt(dfrac); */
501 /* This is something we can play with */
502 i_gpix(im,isec,y1,&tval);
503 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
504 i_ppix(im,isec,y1,&tval);
505
506 i_gpix(im,isec+1,y1,&tval);
507 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
508 i_ppix(im,isec+1,y1,&tval);
509
510 dsec+=alpha;
511 y1++;
512 }
513 }
514}
515
b33c08f8 516static double
02d1d628
AMH
517perm(int n,int k) {
518 double r;
519 int i;
520 r=1;
521 for(i=k+1;i<=n;i++) r*=i;
522 for(i=1;i<=(n-k);i++) r/=i;
523 return r;
524}
525
526
527/* Note in calculating t^k*(1-t)^(n-k)
528 we can start by using t^0=1 so this simplifies to
529 t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
530 to get a new level - this may lead to errors who knows lets test it */
531
532void
533i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
534 double *bzcoef;
535 double t,cx,cy;
536 int k,i;
537 int lx = 0,ly = 0;
538 int n=l-1;
539 double itr,ccoef;
540
541
542 bzcoef=mymalloc(sizeof(double)*l);
543 for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
544 ICL_info(val);
545
546
547 /* for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
548 i=0;
549 for(t=0;t<=1;t+=0.005) {
550 cx=cy=0;
551 itr=t/(1-t);
552 ccoef=pow(1-t,n);
553 for(k=0;k<l;k++) {
554 /* cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
555 cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
556
557 cx+=bzcoef[k]*x[k]*ccoef;
558 cy+=bzcoef[k]*y[k]*ccoef;
559 ccoef*=itr;
560 }
561 /* printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
562 if (i++) {
563 i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val);
564 }
565 /* i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
566 lx=(int)(0.5+cx);
567 ly=(int)(0.5+cy);
568 }
569 ICL_info(val);
570 myfree(bzcoef);
571}
572
573
574
9982a307
AMH
575
576
577
578
579
580
581
582
02d1d628
AMH
583/* Flood fill
584
585 REF: Graphics Gems I. page 282+
586
587*/
588
02d1d628
AMH
589/* This should be moved into a seperate file? */
590
591/* This is the truncation used:
592
593 a double is multiplied by 16 and then truncated.
594 This means that 0 -> 0
595 So a triangle of (0,0) (10,10) (10,0) Will look like it's
596 not filling the (10,10) point nor the (10,0)-(10,10) line segment
597
598*/
599
600
02d1d628
AMH
601/* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
602 graphics gems I */
603
604/*
605struct stc {
606 int mylx,myrx;
607 int dadlx,dadrx;
608 int myy;
609 int mydirection;
610};
611
612Not used code???
613*/
614
615
616struct stack_element {
617 int myLx,myRx;
618 int dadLx,dadRx;
619 int myY;
620 int myDirection;
621};
622
623
624/* create the link data to put push onto the stack */
625
626static
627struct stack_element*
628crdata(int left,int right,int dadl,int dadr,int y, int dir) {
629 struct stack_element *ste;
a73aeb5f
AMH
630 ste = mymalloc(sizeof(struct stack_element));
631 ste->myLx = left;
632 ste->myRx = right;
633 ste->dadLx = dadl;
634 ste->dadRx = dadr;
635 ste->myY = y;
636 ste->myDirection = dir;
02d1d628
AMH
637 return ste;
638}
639
640/* i_ccomp compares two colors and gives true if they are the same */
641
642static int
643i_ccomp(i_color *val1,i_color *val2,int ch) {
644 int i;
645 for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
646 return 1;
647}
648
649
650static int
651i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
652 i_color cval;
653 while(1) {
654 if (seedx-1 < 0) break;
655 i_gpix(im,seedx-1,seedy,&cval);
656 if (!i_ccomp(val,&cval,im->channels)) break;
657 seedx--;
658 }
659 return seedx;
660}
661
662static int
663i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
664 i_color cval;
665 while(1) {
666 if (seedx+1 > im->xsize-1) break;
667 i_gpix(im,seedx+1,seedy,&cval);
668 if (!i_ccomp(val,&cval,im->channels)) break;
669 seedx++;
670 }
671 return seedx;
672}
673
674/* Macro to create a link and push on to the list */
675
a73aeb5f 676#define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s = crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s); }
02d1d628
AMH
677
678/* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
679/* No overflow check! */
680
a73aeb5f 681#define ST_POP() { struct stack_element *s; llist_pop(st,&s); lx = s->myLx; rx = s->myRx; dadLx = s->dadLx; dadRx = s->dadRx; y = s->myY; direction= s->myDirection; myfree(s); }
02d1d628 682
a73aeb5f 683#define ST_STACK(dir,dadLx,dadRx,lx,rx,y) { int pushrx = rx+1; int pushlx = lx-1; ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir); if (rx > dadRx) ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir); if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir); }
02d1d628
AMH
684
685#define SET(x,y) btm_set(btm,x,y);
686
687#define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels) ) ))
688
689void
690i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
691
692 int lx,rx;
693 int y;
694 int direction;
695 int dadLx,dadRx;
696
697 int wasIn=0;
698 int x=0;
699
700 /* int tx,ty; */
701
702 int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
703
704 struct llist *st;
705 struct i_bitmap *btm;
706
707 int channels,xsize,ysize;
708 i_color cval,val;
709
a73aeb5f
AMH
710 channels = im->channels;
711 xsize = im->xsize;
712 ysize = im->ysize;
02d1d628 713
a73aeb5f
AMH
714 btm = btm_new(xsize,ysize);
715 st = llist_new(100,sizeof(struct stack_element*));
02d1d628
AMH
716
717 /* Get the reference color */
718 i_gpix(im,seedx,seedy,&val);
719
720 /* Find the starting span and fill it */
a73aeb5f
AMH
721 lx = i_lspan(im,seedx,seedy,&val);
722 rx = i_rspan(im,seedx,seedy,&val);
02d1d628
AMH
723
724 /* printf("span: %d %d \n",lx,rx); */
725
a73aeb5f 726 for(x=lx; x<=rx; x++) SET(x,seedy);
02d1d628 727
a73aeb5f
AMH
728 ST_PUSH(lx, rx, lx, rx, seedy+1, 1);
729 ST_PUSH(lx, rx, lx, rx, seedy-1,-1);
02d1d628
AMH
730
731 while(st->count) {
732 ST_POP();
733
734 if (y<0 || y>ysize-1) continue;
735
736 if (bymin > y) bymin=y; /* in the worst case an extra line */
737 if (bymax < y) bymax=y;
738
739 /* printf("start of scan - on stack : %d \n",st->count); */
740
741
742 /* printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
743
744 /*
745 printf(" ");
746 for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
747 printf("\n");
748 for(ty=0;ty<ysize;ty++) {
749 printf("%d",ty%10);
750 for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
751 printf("\n");
752 }
753
754 printf("y=%d\n",y);
755 */
756
757
758 x=lx+1;
759 if ( (wasIn = INSIDE(lx,y)) ) {
760 SET(lx,y);
761 lx--;
762 while(INSIDE(lx,y) && lx > 0) {
763 SET(lx,y);
764 lx--;
765 }
766 }
767
768 if (bxmin > lx) bxmin=lx;
769
770 while(x <= xsize-1) {
771 /* printf("x=%d\n",x); */
772 if (wasIn) {
773
774 if (INSIDE(x,y)) {
775 /* case 1: was inside, am still inside */
776 SET(x,y);
777 } else {
778 /* case 2: was inside, am no longer inside: just found the
779 right edge of a span */
780 ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
781
782 if (bxmax < x) bxmax=x;
783
784 wasIn=0;
785 }
786 } else {
787 if (x>rx) goto EXT;
788 if (INSIDE(x,y)) {
789 SET(x,y);
790 /* case 3: Wasn't inside, am now: just found the start of a new run */
791 wasIn=1;
792 lx=x;
793 } else {
794 /* case 4: Wasn't inside, still isn't */
795 }
796 }
797 x++;
798 }
799 EXT: /* out of loop */
800 if (wasIn) {
801 /* hit an edge of the frame buffer while inside a run */
802 ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
803 if (bxmax < x) bxmax=x;
804 }
805 }
806
807 /* printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
808 printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
809
810 for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
811
812 btm_destroy(btm);
a73aeb5f 813 mm_log((1, "DESTROY\n"));
02d1d628
AMH
814 llist_destroy(st);
815}
cc6483e0
TC
816
817static struct i_bitmap *
818i_flood_fill_low(i_img *im,int seedx,int seedy,
819 int *bxminp, int *bxmaxp, int *byminp, int *bymaxp) {
820 int lx,rx;
821 int y;
822 int direction;
823 int dadLx,dadRx;
824
825 int wasIn=0;
826 int x=0;
827
828 /* int tx,ty; */
829
830 int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
831
832 struct llist *st;
833 struct i_bitmap *btm;
834
835 int channels,xsize,ysize;
836 i_color cval,val;
837
838 channels=im->channels;
839 xsize=im->xsize;
840 ysize=im->ysize;
841
842 btm=btm_new(xsize,ysize);
843 st=llist_new(100,sizeof(struct stack_element*));
844
845 /* Get the reference color */
846 i_gpix(im,seedx,seedy,&val);
847
848 /* Find the starting span and fill it */
849 lx=i_lspan(im,seedx,seedy,&val);
850 rx=i_rspan(im,seedx,seedy,&val);
851
852 /* printf("span: %d %d \n",lx,rx); */
853
854 for(x=lx;x<=rx;x++) SET(x,seedy);
855
856 ST_PUSH(lx,rx,lx,rx,seedy+1,1);
857 ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
858
859 while(st->count) {
860 ST_POP();
861
862 if (y<0 || y>ysize-1) continue;
863
864 if (bymin > y) bymin=y; /* in the worst case an extra line */
865 if (bymax < y) bymax=y;
866
867 /* printf("start of scan - on stack : %d \n",st->count); */
868
869
870 /* printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
871
872 /*
873 printf(" ");
874 for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
875 printf("\n");
876 for(ty=0;ty<ysize;ty++) {
877 printf("%d",ty%10);
878 for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
879 printf("\n");
880 }
881
882 printf("y=%d\n",y);
883 */
884
885
886 x=lx+1;
887 if ( (wasIn = INSIDE(lx,y)) ) {
888 SET(lx,y);
889 lx--;
890 while(INSIDE(lx,y) && lx > 0) {
891 SET(lx,y);
892 lx--;
893 }
894 }
895
896 if (bxmin > lx) bxmin=lx;
897
898 while(x <= xsize-1) {
899 /* printf("x=%d\n",x); */
900 if (wasIn) {
901
902 if (INSIDE(x,y)) {
903 /* case 1: was inside, am still inside */
904 SET(x,y);
905 } else {
906 /* case 2: was inside, am no longer inside: just found the
907 right edge of a span */
908 ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
909
910 if (bxmax < x) bxmax=x;
911
912 wasIn=0;
913 }
914 } else {
915 if (x>rx) goto EXT;
916 if (INSIDE(x,y)) {
917 SET(x,y);
918 /* case 3: Wasn't inside, am now: just found the start of a new run */
919 wasIn=1;
920 lx=x;
921 } else {
922 /* case 4: Wasn't inside, still isn't */
923 }
924 }
925 x++;
926 }
927 EXT: /* out of loop */
928 if (wasIn) {
929 /* hit an edge of the frame buffer while inside a run */
930 ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
931 if (bxmax < x) bxmax=x;
932 }
933 }
934
935 /* printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
936 printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
937
938 llist_destroy(st);
939
940 *bxminp = bxmin;
941 *bxmaxp = bxmax;
942 *byminp = bymin;
943 *bymaxp = bymax;
944
945 return btm;
946}
947
948void
949i_flood_cfill(i_img *im, int seedx, int seedy, i_fill_t *fill) {
950 int bxmin, bxmax, bymin, bymax;
951 struct i_bitmap *btm;
952 int x, y;
953 int start;
954
955 btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax);
956
957 if (im->bits == i_8_bits && fill->fill_with_color) {
958 i_color *line = mymalloc(sizeof(i_color) * (bxmax - bxmin));
efdc2568
TC
959 i_color *work = NULL;
960 if (fill->combine)
961 work = mymalloc(sizeof(i_color) * (bxmax - bxmin));
cc6483e0
TC
962
963 for(y=bymin;y<=bymax;y++) {
964 x = bxmin;
965 while (x < bxmax) {
966 while (x < bxmax && !btm_test(btm, x, y)) {
967 ++x;
968 }
969 if (btm_test(btm, x, y)) {
970 start = x;
971 while (x < bxmax && btm_test(btm, x, y)) {
972 ++x;
973 }
43c5dacb 974 if (fill->combine) {
cc6483e0 975 i_glin(im, start, x, y, line);
43c5dacb
TC
976 (fill->fill_with_color)(fill, start, y, x-start, im->channels,
977 work);
978 (fill->combine)(line, work, im->channels, x-start);
979 }
980 else {
981 (fill->fill_with_color)(fill, start, y, x-start, im->channels,
982 line);
983 }
cc6483e0
TC
984 i_plin(im, start, x, y, line);
985 }
986 }
987 }
988 myfree(line);
efdc2568
TC
989 if (work)
990 myfree(work);
cc6483e0
TC
991 }
992 else {
993 i_fcolor *line = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
efdc2568
TC
994 i_fcolor *work = NULL;
995 if (fill->combinef)
996 work = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
cc6483e0
TC
997
998 for(y=bymin;y<=bymax;y++) {
999 x = bxmin;
1000 while (x < bxmax) {
1001 while (x < bxmax && !btm_test(btm, x, y)) {
1002 ++x;
1003 }
1004 if (btm_test(btm, x, y)) {
1005 start = x;
1006 while (x < bxmax && btm_test(btm, x, y)) {
1007 ++x;
1008 }
43c5dacb 1009 if (fill->combinef) {
cc6483e0 1010 i_glinf(im, start, x, y, line);
43c5dacb
TC
1011 (fill->fill_with_fcolor)(fill, start, y, x-start, im->channels,
1012 work);
1013 (fill->combinef)(line, work, im->channels, x-start);
1014 }
1015 else {
1016 (fill->fill_with_fcolor)(fill, start, y, x-start, im->channels,
1017 line);
1018 }
cc6483e0
TC
1019 i_plinf(im, start, x, y, line);
1020 }
1021 }
1022 }
1023 myfree(line);
efdc2568
TC
1024 if (work)
1025 myfree(work);
cc6483e0
TC
1026 }
1027
1028 btm_destroy(btm);
1029}