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