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