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