Fixed a bug which caused compile and runtime errors with IM_NOLOG=1
[imager.git] / draw.c
CommitLineData
02d1d628
AMH
1#include "image.h"
2#include "draw.h"
3#include "log.h"
4
5void
6i_mmarray_cr(i_mmarray *ar,int l) {
7 int i;
8
9 ar->lines=l;
10 ar->data=mymalloc(sizeof(minmax)*l);
11 for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
12}
13
14void
15i_mmarray_dst(i_mmarray *ar) {
16 ar->lines=0;
17 if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
18}
19
20void
21i_mmarray_add(i_mmarray *ar,int x,int y) {
22 if (y>-1 && y<ar->lines)
23 {
24 if (x<ar->data[y].min) ar->data[y].min=x;
25 if (x>ar->data[y].max) ar->data[y].max=x;
26 }
27}
28
29int
30i_mmarray_gmin(i_mmarray *ar,int y) {
31 if (y>-1 && y<ar->lines) return ar->data[y].min;
32 else return -1;
33}
34
35int
36i_mmarray_getm(i_mmarray *ar,int y) {
37 if (y>-1 && y<ar->lines) return ar->data[y].max;
38 else return MAXINT;
39}
40
41void
42i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
43 int i,x;
44 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);
45}
46
47
48static
49void
50i_arcdraw(int x1, int y1, int x2, int y2, i_mmarray *ar) {
51 double alpha;
52 double dsec;
53 int temp;
54 alpha=(double)(y2-y1)/(double)(x2-x1);
55 if (fabs(alpha)<1)
56 {
57 if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
58 dsec=y1;
59 while(x1<x2)
60 {
61 dsec+=alpha;
62 i_mmarray_add(ar,x1,(int)(dsec+0.5));
63 x1++;
64 }
65 }
66 else
67 {
68 alpha=1/alpha;
69 if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
70 dsec=x1;
71 while(y1<y2)
72 {
73 dsec+=alpha;
74 i_mmarray_add(ar,(int)(dsec+0.5),y1);
75 y1++;
76 }
77 }
78}
79
80void
81i_mmarray_info(i_mmarray *ar) {
82 int i;
83 for(i=0;i<ar->lines;i++)
84 if (ar->data[i].max!=-1) printf("line %d: min=%d, max=%d.\n",i,ar->data[i].min,ar->data[i].max);
85}
86
87
88void
89i_arc(i_img *im,int x,int y,float rad,float d1,float d2,i_color *val) {
90 i_mmarray dot;
91 float f,fx,fy;
92 int x1,y1;
93
94 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));
95
96 i_mmarray_cr(&dot,im->ysize);
97
98 x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
99 y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
100 fx=(float)x1; fy=(float)y1;
101
102 /* printf("x1: %d.\ny1: %d.\n",x1,y1); */
103 i_arcdraw(x, y, x1, y1, &dot);
104
105 x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
106 y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
107
108 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)));
109
110 /* printf("x1: %d.\ny1: %d.\n",x1,y1); */
111 i_arcdraw(x, y, x1, y1, &dot);
112
113 /* dot.info(); */
114 i_mmarray_render(im,&dot,val);
115}
116
117void
118i_box(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
119 int x,y;
120 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));
121 for(x=x1;x<x2+1;x++) {
122 i_ppix(im,x,y1,val);
123 i_ppix(im,x,y2,val);
124 }
125 for(y=y1;y<y2+1;y++) {
126 i_ppix(im,x1,y,val);
127 i_ppix(im,x2,y,val);
128 }
129}
130
131void
132i_box_filled(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
133 int x,y;
134 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));
135 for(x=x1;x<x2+1;x++) for (y=y1;y<y2+1;y++) i_ppix(im,x,y,val);
136}
137
138
139void
140i_draw(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
141 double alpha;
142 double dsec;
143 int temp;
144
145 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));
146
147 alpha=(double)(y2-y1)/(double)(x2-x1);
148 if (fabs(alpha)<1)
149 {
150 if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
151 dsec=y1;
152 while(x1<x2)
153 {
154 dsec+=alpha;
155 i_ppix(im,x1,(int)(dsec+0.5),val);
156 x1++;
157 }
158 }
159 else
160 {
161 alpha=1/alpha;
162 if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
163 dsec=x1;
164 while(y1<y2)
165 {
166 dsec+=alpha;
167 i_ppix(im,(int)(dsec+0.5),y1,val);
168 y1++;
169 }
170 }
171 mm_log((1,"i_draw: alpha=%f.\n",alpha));
172}
173
174void
175i_line_aa(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
176 i_color tval;
177 float alpha;
178 float dsec,dfrac;
179 int temp,dx,dy,isec,ch;
180
181 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));
182
183 dy=y2-y1;
184 dx=x2-x1;
185
186 if (abs(dx)>abs(dy)) { /* alpha < 1 */
187 if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
188 alpha=(float)(y2-y1)/(float)(x2-x1);
189
190 dsec=y1;
191 while(x1<=x2) {
192 isec=(int)dsec;
193 dfrac=dsec-isec;
194 /* dfrac=1-(1-dfrac)*(1-dfrac); */
195 /* This is something we can play with to try to get better looking lines */
196
197 i_gpix(im,x1,isec,&tval);
198 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
199 i_ppix(im,x1,isec,&tval);
200
201 i_gpix(im,x1,isec+1,&tval);
202 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
203 i_ppix(im,x1,isec+1,&tval);
204
205 dsec+=alpha;
206 x1++;
207 }
208 } else {
209 if (y2<y1) { temp=y1; y1=y2; y2=temp; temp=x1; x1=x2; x2=temp; }
210 alpha=(float)(x2-x1)/(float)(y2-y1);
211 dsec=x1;
212 while(y1<=y2) {
213 isec=(int)dsec;
214 dfrac=dsec-isec;
215 /* dfrac=sqrt(dfrac); */
216 /* This is something we can play with */
217 i_gpix(im,isec,y1,&tval);
218 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
219 i_ppix(im,isec,y1,&tval);
220
221 i_gpix(im,isec+1,y1,&tval);
222 for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
223 i_ppix(im,isec+1,y1,&tval);
224
225 dsec+=alpha;
226 y1++;
227 }
228 }
229}
230
231double
232perm(int n,int k) {
233 double r;
234 int i;
235 r=1;
236 for(i=k+1;i<=n;i++) r*=i;
237 for(i=1;i<=(n-k);i++) r/=i;
238 return r;
239}
240
241
242/* Note in calculating t^k*(1-t)^(n-k)
243 we can start by using t^0=1 so this simplifies to
244 t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
245 to get a new level - this may lead to errors who knows lets test it */
246
247void
248i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
249 double *bzcoef;
250 double t,cx,cy;
251 int k,i;
252 int lx = 0,ly = 0;
253 int n=l-1;
254 double itr,ccoef;
255
256
257 bzcoef=mymalloc(sizeof(double)*l);
258 for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
259 ICL_info(val);
260
261
262 /* for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
263 i=0;
264 for(t=0;t<=1;t+=0.005) {
265 cx=cy=0;
266 itr=t/(1-t);
267 ccoef=pow(1-t,n);
268 for(k=0;k<l;k++) {
269 /* cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
270 cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
271
272 cx+=bzcoef[k]*x[k]*ccoef;
273 cy+=bzcoef[k]*y[k]*ccoef;
274 ccoef*=itr;
275 }
276 /* printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
277 if (i++) {
278 i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val);
279 }
280 /* i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
281 lx=(int)(0.5+cx);
282 ly=(int)(0.5+cy);
283 }
284 ICL_info(val);
285 myfree(bzcoef);
286}
287
288
289
290/* Flood fill
291
292 REF: Graphics Gems I. page 282+
293
294*/
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311/* This should be moved into a seperate file? */
312
313/* This is the truncation used:
314
315 a double is multiplied by 16 and then truncated.
316 This means that 0 -> 0
317 So a triangle of (0,0) (10,10) (10,0) Will look like it's
318 not filling the (10,10) point nor the (10,0)-(10,10) line segment
319
320*/
321
322
323
324
325#define IMTRUNC(x) ((int)(x*16))
326
327
328/*
329typedef struct {
330 short ms,ls;
331} pcord;
332*/
333
334typedef int pcord;
335
336struct p_point {
337 int n;
338 pcord x,y;
339};
340
341struct p_line {
342 int n;
343 pcord x1,y1;
344 pcord x2,y2;
345 pcord miny,maxy;
346};
347
348struct p_slice {
349 int n;
350 double x;
351};
352
353int
354p_compy(const struct p_point *p1, const struct p_point *p2) {
355 if (p1->y > p2->y) return 1;
356 if (p1->y < p2->y) return -1;
357 return 0;
358}
359
360int
361p_compx(const struct p_slice *p1, const struct p_slice *p2) {
362 if (p1->x > p2->x) return 1;
363 if (p1->x < p2->x) return -1;
364 return 0;
365}
366
367/* Change this to int? and round right goddamn it! */
368
369double
370p_eval_aty(struct p_line *l,pcord y) {
371 int t;
372 t=l->y2-l->y1;
373 if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
374 return (l->x1+l->x2)/2.0;
375}
376
377double
378p_eval_atx(struct p_line *l,pcord x) {
379 int t;
380 t=l->x2-l->x1;
381 if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
382 return (l->y1+l->y2)/2.0;
383}
384
385
386/* Algorithm to count the pixels covered by line going through pixel (x,y)
387 in coarse coords.
388*/
389
390/*
391static int
392p_eval_coverage(struct p_line *l, int lc, int x, pcord y1, pcord y2) {
393
394 return 0;
395}
396*/
397
398
399/* Antialiasing polygon algorithm
400 specs:
401 1. only nice polygons - no crossovers
402 2. 1/16 pixel resolution # previously - floating point co-ordinates
403 3. full antialiasing ( complete spectrum of blends )
404 4. uses hardly any memory
405 5. no subsampling phase
406
407 For each interval we must:
408 1. find which lines are in it
409 2. order the lines from in increasing x order.
410 since we are assuming no crossovers it is sufficent
411 to check a single point on each line.
412*/
413
414/*
415 Terms:
416
417 1. Interval: A vertical segment in which no lines cross nor end.
418 2. Scanline: A physical line, contains 16 subpixels in the horizontal direction
419 3. Slice: A start stop line pair.
420
421 */
422
423/* Templine logic:
424
425 The variable tempflush describes if there is anything in the templine array or not.
426
427 if tempflush is 0 then the array is clean.
428 if tempflush is 1 then the array contains a partial filled scanline
429
430 */
431
432/* Rendering of a single start stop pair:
433
434?? REWRITE
435
436 The rendering is split in three parts
437 1. From the first start pixel to the first stop pixel
438 2. Area from the first end pixel to the last start pixel
439 3. Area from the first end pixel to the last start pixel
440
441 */
442
443
444void
445i_poly_aa(i_img *im,int l,double *x,double *y,i_color *val) {
446 int i,k; /* Index variables */
447 int clc; /* Index of next item on interval linelist */
448 int tx; /* Coarse x coord within a scanline */
449 pcord miny,maxy; /* Min and max values of the current slice in the subcord system */
450 pcord minacy,maxacy; /* Min and max values of the current scanline bounded by the slice
451 in the subcord system */
452 int cscl; /* Current scanline */
453 pcord cc; /* Current vertical centerpoint of interval */
454 int mt1,mt2;
455 int minsx,minex,maxsx,maxex; /* The horizontal stretches of the lines beloning to the current slice within a scanline */
456 int *templine; /* Line accumulator */
457
458 struct p_point *pset; /* List of points in polygon */
459 struct p_line *lset; /* List of lines in polygon */
460 struct p_slice *tllist; /* List of slices */
461
462 i_color red,blue,yellow;
463 red.rgb.r=255;
464 red.rgb.g=0;
465 red.rgb.b=0;
466
467 blue.rgb.r=0;
468 blue.rgb.g=0;
469 blue.rgb.b=255;
470
471 yellow.rgb.r=255;
472 yellow.rgb.g=255;
473 yellow.rgb.b=255;
474
475 if ( (pset=mymalloc(sizeof(struct p_point)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
476 if ( (lset=mymalloc(sizeof(struct p_line)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
477 if ( (tllist=mymalloc(sizeof(struct p_slice)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
478 if ( (templine=mymalloc(sizeof(int)*im->xsize)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
479
480 /* insert the lines into the line list */
481
482 for(i=0;i<l;i++) {
483 pset[i].n=i;
484 pset[i].x=IMTRUNC(x[i]);
485 pset[i].y=IMTRUNC(y[i]);
486 lset[i].n=i;
487 lset[i].x1=IMTRUNC(x[i]);
488 lset[i].y1=IMTRUNC(y[i]);
489 lset[i].x2=IMTRUNC(x[(i+1)%l]);
490 lset[i].y2=IMTRUNC(y[(i+1)%l]);
491 lset[i].miny=min(lset[i].y1,lset[i].y2);
492 lset[i].maxy=max(lset[i].y1,lset[i].y2);
493 }
494
495 qsort(pset,l,sizeof(struct p_point),(int(*)(const void *,const void *))p_compy);
496
497 printf("post point list (sorted in ascending y order)\n");
498 for(i=0;i<l;i++) {
499 printf("%d [ %d ] %d %d\n",i,pset[i].n,pset[i].x,pset[i].y);
500 }
501
502 printf("line list\n");
503 for(i=0;i<l;i++) {
504 printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",i,lset[i].n,lset[i].x1,lset[i].y1,lset[i].x2,lset[i].y2,lset[i].miny,lset[i].maxy);
505 }
506
507 printf("MAIN LOOP\n\n");
508
509 /* Zero templine buffer */
510 /* Templine buffer flushed everytime a scan line ends */
511 for(i=0;i<im->xsize;i++) templine[i]=0;
512
513
514 /* loop on intervals */
515 for(i=0;i<l-1;i++) {
516 cc=(pset[i].y+pset[i+1].y)/2;
517 printf("current slice is: %d to %d ( cpoint %d )\n",pset[i].y,pset[i+1].y,cc);
518 clc=0;
519
520 /* stuff this in a function ?? */
521
522 /* Check what lines belong to interval */
523 for(k=0;k<l;k++) {
524 printf("checking line: %d [ %d ] (%d , %d) -> (%d, %d) yspan ( %d , %d )",
525 k,lset[k].n,lset[k].x1,lset[k].y1,lset[k].x2,lset[k].y2,lset[k].miny,lset[k].maxy);
526 if (cc >= lset[k].miny && cc <= lset[k].maxy) {
527 if (lset[k].miny == lset[k].maxy) printf(" HORIZONTAL - skipped\n");
528 else {
529 printf(" INSIDE\n");
530 tllist[clc].x=p_eval_aty(&lset[k],cc);
531 tllist[clc++].n=k;
532 }
533 } else printf(" OUTSIDE\n");
534 }
535
536 /*
537 at this point a table of pixels that need special care should
538 be generated from the line list - it should be ordered so that only
539 one needs to be checked - options: rendering to a list then order - or
540 rendering in the right order might be possible to do nicely with the
541 following heuristic:
542
543 1. Draw leftmost pixel for this line
544 2. If preceeding pixel was occupied check next one else go to 1 again.
545 */
546
547 printf("lines in current interval:");
548 for(k=0;k<clc;k++) printf(" %d (%.2f)",tllist[k].n,tllist[k].x);
549 printf("\n");
550
551 /* evaluate the lines in the middle of the slice */
552
553 printf("Sort lines left to right within interval\n");
554 qsort(tllist,clc,sizeof(struct p_slice),(int(*)(const void *,const void *))p_compx);
555
556 printf("sorted lines in interval - output:");
557 for(k=0;k<clc;k++) printf(" %d",tllist[k].n);
558 printf("\n");
559
560 miny=pset[i].y;
561 maxy=pset[i+1].y;
562
563 /* iterate over scanlines */
564 for(cscl=(miny)/16;cscl<=maxy/16;cscl++) {
565 minacy=max(miny,cscl*16);
566 maxacy=min(maxy,cscl*16+15);
567
568 printf("Scanline bound %d - %d\n",minacy, maxacy);
569
570 /* iterate over line pairs (slices) within interval */
571 for(k=0;k<clc-1;k+=2) {
572
573 mt1=p_eval_aty(&lset[tllist[k].n],minacy); /* upper corner */
574 mt2=p_eval_aty(&lset[tllist[k].n],maxacy); /* lower corner */
575 minsx=min(mt1,mt2);
576 minex=max(mt1,mt2);
577 mt1=p_eval_aty(&lset[tllist[k+1].n],minacy); /* upper corner */
578 mt2=p_eval_aty(&lset[tllist[k+1].n],maxacy); /* lower corner */
579 maxsx=min(mt1,mt2);
580 maxex=max(mt1,mt2);
581
582 printf("minsx: %d minex: %d\n",minsx,minex);
583 printf("maxsx: %d maxex: %d\n",maxsx,maxex);
584
585 if (minex/16<maxsx/16) printf("Scan slice is simple!\n");
586 else printf("Scan slice is complicated!\n");
587
588 if (minsx/16 == minex/16) { /* The line starts and ends in the same pixel */
589 printf("Low slant start pixel\n");
590 templine[minsx/16]=(maxacy-minacy+1)*(minex-minsx+1)/2+((minex | 0xF)-minex)*(maxacy-minacy+1);
591 } else {
592 for(tx=minsx/16;tx<minex/16+1;tx++) {
593 int minx,maxx,minxy,maxxy;
594 minx=max(minsx, tx*16 );
595 maxx=min(minex, tx*16+15);
596
597 if (minx == maxx) {
598 templine[tx]=(maxacy-minacy+1);
599 } else {
600
601 minxy=p_eval_atx(&lset[tllist[k].n], minx);
602 maxxy=p_eval_atx(&lset[tllist[k].n], maxx);
603
604 templine[tx]+=(abs(minxy-maxxy)+1)*(minex-minsx+1)/2; /* The triangle between the points */
605 if (mt1 < mt2) { /* \ slant */
606 /* ((minex | 0xF)-minex)*(maxacy-minacy+1); FIXME: unfinished */
607
608
609
610 } else {
611 templine[tx]+=((minex | 0xF)-minex)*(maxacy-minacy+1);
612 }
613
614 }
615 }
616 }
617
618 for(tx=maxsx/16;tx<maxex/16+1;tx++) templine[tx]+=16*(maxacy-minacy+1);
619
620 /* for(tx=minex/16+1;tx<maxsx/16;tx++) 0; */
621
622
623 printf("line %d: painting %d - %d\n",cscl,minex/16+1,maxsx/16);
624 if ( (minacy != cscl*16) || (maxacy != cscl*16+15) ) {
625 for(tx=minsx/16;tx<maxex/16+1;tx++) {
626 i_ppix(im,tx,cscl,&yellow);
627 }
628 }
629 else {
630 for(tx=minsx/16;tx<minex/16+1;tx++) i_ppix(im,tx,cscl,&red);
631 for(tx=maxsx/16;tx<maxex/16+1;tx++) i_ppix(im,tx,cscl,&blue);
632 for(tx=minex/16+1;tx<maxsx/16;tx++) i_ppix(im,tx,cscl,val);
633 }
634
635 } /* Slices */
636 } /* Scanlines */
637 } /* Intervals */
638} /* Function */
639
640
641
642
643
644
645
646/* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
647 graphics gems I */
648
649/*
650struct stc {
651 int mylx,myrx;
652 int dadlx,dadrx;
653 int myy;
654 int mydirection;
655};
656
657Not used code???
658*/
659
660
661struct stack_element {
662 int myLx,myRx;
663 int dadLx,dadRx;
664 int myY;
665 int myDirection;
666};
667
668
669/* create the link data to put push onto the stack */
670
671static
672struct stack_element*
673crdata(int left,int right,int dadl,int dadr,int y, int dir) {
674 struct stack_element *ste;
675 ste=(struct stack_element*)mymalloc(sizeof(struct stack_element));
676 ste->myLx=left;
677 ste->myRx=right;
678 ste->dadLx=dadl;
679 ste->dadRx=dadr;
680 ste->myY=y;
681 ste->myDirection=dir;
682 return ste;
683}
684
685/* i_ccomp compares two colors and gives true if they are the same */
686
687static int
688i_ccomp(i_color *val1,i_color *val2,int ch) {
689 int i;
690 for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
691 return 1;
692}
693
694
695static int
696i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
697 i_color cval;
698 while(1) {
699 if (seedx-1 < 0) break;
700 i_gpix(im,seedx-1,seedy,&cval);
701 if (!i_ccomp(val,&cval,im->channels)) break;
702 seedx--;
703 }
704 return seedx;
705}
706
707static int
708i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
709 i_color cval;
710 while(1) {
711 if (seedx+1 > im->xsize-1) break;
712 i_gpix(im,seedx+1,seedy,&cval);
713 if (!i_ccomp(val,&cval,im->channels)) break;
714 seedx++;
715 }
716 return seedx;
717}
718
719/* Macro to create a link and push on to the list */
720
721#define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s=crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s);}
722
723/* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
724/* No overflow check! */
725
726#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); }
727
728#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); }
729
730#define SET(x,y) btm_set(btm,x,y);
731
732#define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels) ) ))
733
734void
735i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
736
737 int lx,rx;
738 int y;
739 int direction;
740 int dadLx,dadRx;
741
742 int wasIn=0;
743 int x=0;
744
745 /* int tx,ty; */
746
747 int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
748
749 struct llist *st;
750 struct i_bitmap *btm;
751
752 int channels,xsize,ysize;
753 i_color cval,val;
754
755 channels=im->channels;
756 xsize=im->xsize;
757 ysize=im->ysize;
758
759 btm=btm_new(xsize,ysize);
760 st=llist_new(100,sizeof(struct stack_element*));
761
762 /* Get the reference color */
763 i_gpix(im,seedx,seedy,&val);
764
765 /* Find the starting span and fill it */
766 lx=i_lspan(im,seedx,seedy,&val);
767 rx=i_rspan(im,seedx,seedy,&val);
768
769 /* printf("span: %d %d \n",lx,rx); */
770
771 for(x=lx;x<=rx;x++) SET(x,seedy);
772
773 ST_PUSH(lx,rx,lx,rx,seedy+1,1);
774 ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
775
776 while(st->count) {
777 ST_POP();
778
779 if (y<0 || y>ysize-1) continue;
780
781 if (bymin > y) bymin=y; /* in the worst case an extra line */
782 if (bymax < y) bymax=y;
783
784 /* printf("start of scan - on stack : %d \n",st->count); */
785
786
787 /* printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
788
789 /*
790 printf(" ");
791 for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
792 printf("\n");
793 for(ty=0;ty<ysize;ty++) {
794 printf("%d",ty%10);
795 for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
796 printf("\n");
797 }
798
799 printf("y=%d\n",y);
800 */
801
802
803 x=lx+1;
804 if ( (wasIn = INSIDE(lx,y)) ) {
805 SET(lx,y);
806 lx--;
807 while(INSIDE(lx,y) && lx > 0) {
808 SET(lx,y);
809 lx--;
810 }
811 }
812
813 if (bxmin > lx) bxmin=lx;
814
815 while(x <= xsize-1) {
816 /* printf("x=%d\n",x); */
817 if (wasIn) {
818
819 if (INSIDE(x,y)) {
820 /* case 1: was inside, am still inside */
821 SET(x,y);
822 } else {
823 /* case 2: was inside, am no longer inside: just found the
824 right edge of a span */
825 ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
826
827 if (bxmax < x) bxmax=x;
828
829 wasIn=0;
830 }
831 } else {
832 if (x>rx) goto EXT;
833 if (INSIDE(x,y)) {
834 SET(x,y);
835 /* case 3: Wasn't inside, am now: just found the start of a new run */
836 wasIn=1;
837 lx=x;
838 } else {
839 /* case 4: Wasn't inside, still isn't */
840 }
841 }
842 x++;
843 }
844 EXT: /* out of loop */
845 if (wasIn) {
846 /* hit an edge of the frame buffer while inside a run */
847 ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
848 if (bxmax < x) bxmax=x;
849 }
850 }
851
852 /* printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
853 printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
854
855 for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
856
857 btm_destroy(btm);
858 llist_destroy(st);
859}