Commit | Line | Data |
---|---|---|
02d1d628 AMH |
1 | #include "image.h" |
2 | #include "draw.h" | |
3 | #include "log.h" | |
4 | ||
6af18d2b AMH |
5 | #include <limits.h> |
6 | ||
02d1d628 AMH |
7 | void |
8 | i_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 | ||
16 | void | |
17 | i_mmarray_dst(i_mmarray *ar) { | |
18 | ar->lines=0; | |
19 | if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; } | |
20 | } | |
21 | ||
22 | void | |
23 | i_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 | ||
31 | int | |
32 | i_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 | ||
37 | int | |
38 | i_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 | ||
43 | void | |
44 | i_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 | ||
50 | static | |
51 | void | |
52 | i_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 | ||
82 | void | |
83 | i_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 | ||
90 | void | |
91 | i_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 | ||
124 | typedef int frac; | |
125 | static frac float_to_frac(float x) { return (frac)(0.5+x*16.0); } | |
126 | static int frac_sub (frac x) { return (x%16); } | |
127 | static int frac_int (frac x) { return (x/16); } | |
128 | static float frac_to_float(float x) { return (float)x/16.0; } | |
129 | ||
130 | static | |
131 | void | |
132 | polar_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 | ||
137 | static | |
138 | void | |
139 | order_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 | ||
150 | static | |
151 | void | |
152 | make_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 | ||
196 | static | |
197 | int | |
198 | i_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 | ||
218 | void | |
219 | i_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 |
265 | void |
266 | i_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 | ||
279 | void | |
280 | i_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 | ||
287 | void | |
288 | i_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 | ||
322 | void | |
323 | i_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 | ||
379 | double | |
380 | perm(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 | ||
395 | void | |
396 | i_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 | /* | |
477 | typedef struct { | |
478 | short ms,ls; | |
479 | } pcord; | |
480 | */ | |
481 | ||
482 | typedef int pcord; | |
483 | ||
484 | struct p_point { | |
485 | int n; | |
486 | pcord x,y; | |
487 | }; | |
488 | ||
489 | struct p_line { | |
490 | int n; | |
491 | pcord x1,y1; | |
492 | pcord x2,y2; | |
493 | pcord miny,maxy; | |
494 | }; | |
495 | ||
496 | struct p_slice { | |
497 | int n; | |
498 | double x; | |
499 | }; | |
500 | ||
501 | int | |
502 | p_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 | ||
508 | int | |
509 | p_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 | ||
517 | double | |
518 | p_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 | ||
525 | double | |
526 | p_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 | /* | |
539 | static int | |
540 | p_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 | ||
592 | void | |
593 | i_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 | /* | |
798 | struct stc { | |
799 | int mylx,myrx; | |
800 | int dadlx,dadrx; | |
801 | int myy; | |
802 | int mydirection; | |
803 | }; | |
804 | ||
805 | Not used code??? | |
806 | */ | |
807 | ||
808 | ||
809 | struct 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 | ||
819 | static | |
820 | struct stack_element* | |
821 | crdata(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 | ||
835 | static int | |
836 | i_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 | ||
843 | static int | |
844 | i_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 | ||
855 | static int | |
856 | i_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 | ||
882 | void | |
883 | i_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 | } |