1 #include <stdio.h>
2 /* A fillpoly in C - for fun
3 * Sed - start : Tue Sep 7 23:31:26 MET DST 1999
4 * Wed Sep 8 00:30:42 MET DST 1999 : all done, except the low stuff in
5 * fill_left and fill_right and the dealing with colors in fill_lines
6 * Wed Sep 8 00:58:03 MET DST 1999 : all cases dealed in fill_left except
7 * the 12 harder (where x1!x2 and y1!=y2, which makes 4 combinations, each
8 * of them giving 3 subcase (dx>dy or dx=dy or dx<dy)). Well, let's go to
9 * bed. Tomorrow, will have to write my dea's report (continue it). In
10 * exactly 7 days and some hours, I'll be over with this shit. Cool.
11 * But no holidays, because the next day, go to see for army shit, and
12 * I have a job now too, shit of the shits !
13 * Fri Sep 10 00:23:53 MET DST 1999 - let's continue
14 * Fri Sep 10 01:37:00 MET DST 1999 - fill_left done, now let's debug it !
15 * Fri Sep 10 02:10:54 MET DST 1999 - ok, it work fine. No bug ! (except an <
16 * instead of a <= in the caller of fill_left and a bug with my rotation
17 * which turned the poly in the indirect way.
18 * Something cool would be to have float instead of int for coords of a point
19 * and do some subpixel. And I have to make fill_right too. And the colors !
20 * (i did not test that)
21 * Fri Sep 17 10:57:52 MET DST 1999 - Ok, let's subpixel it all.
22 * Holidays are cool, nope ? Yeah, they are !
23 * Sun Sep 19 00:59:26 MET DST 1999 : subpixel seems to work.
24 * I'm not sure of it at all, strange behavior with one example,
25 * but better with another even if strangeness still in there.
26 * I am almost sure something's wrong with floor, so I gonna try
27 * to put it all in 16:16 math fixed point.
28 */
29 #include <assert.h>
30 #include <math.h>
31
32 #include "device.h"
33 #include "poly.h"
34
35 #define abs(x) ((x)>0 ? (x) : (-(x)))
36
37 static int miny, maxy;
38
39 /* returns a*b/c in int 16:16 */
muldiv(int a,int b,int c)40 static inline int muldiv(int a, int b, int c)
41 {
42 #ifdef PC_ARCHI
43 register int r;
44 __asm__ volatile ("imul %2 \n"
45 "idiv %3 \n"
46 : "=a" (r)
47 : "a" (a), "b" (b), "c" (c)
48 : "eax", "ebx", "ecx", "edx"
49 );
50 return r;
51 #else
52 double r, aa=a, bb=b, cc=c;
53 r=aa*bb/cc;
54 return r;
55 #endif
56 }
57
58 /*******************************************************
59 * fill_left *
60 *******************************************************/
fill_left(device * d,point * p1,point * p2)61 void fill_left(device *d, point *p1, point *p2)
62 {
63 /* lots of goto for lisibility (if if else if if else else is impossible to debug) */
64 register int x1=p1->x*65536., x2=p2->x*65536., y1=p1->y*65536., y2=p2->y*65536., dx, dy;
65 register int xcur;
66 register int xinc;
67 register int i;
68 register int y1i=(y1+65535)>>16, y2i=(y2+65535)>>16;
69
70 /* in asm, those two subs are good for us, because we can test if x1<x2 and if y1<y2 at the same time, but it's C */
71 dx=x2-x1;
72 dy=y2-y1;
73
74 if (dx<0)
75 goto x1_sup_x2;
76 if (dx)
77 goto x1_inf_x2;
78
79 /* here x1==x2 */
80 if (dy<-65535)
81 goto x1_eq_x2_and_y1_sup_y2;
82 if (dy>65535)
83 goto x1_eq_x2_and_y1_inf_y2;
84 /* here x1==x2 && y1==y2 */
85 if (y1i<y2i) {
86 the_lines[y1i].x_left=x1;
87 } else {
88 the_lines[y2i].x_left=x1;
89 }
90 return;
91 x1_eq_x2_and_y1_sup_y2:
92 for (i=y2i; i<y1i; i++) {
93 the_lines[i].x_left=x1;
94 }
95 return;
96 x1_eq_x2_and_y1_inf_y2:
97 for (i=y1i; i<y2i; i++) {
98 the_lines[i].x_left=x1;
99 }
100 return;
101
102 x1_inf_x2:
103 if (dy<-65535)
104 goto x1_inf_x2_and_y1_sup_y2;
105 if (dy>65535)
106 goto x1_inf_x2_and_y1_inf_y2;
107 /* x1<x2 && y1==y2 */
108 if (y1i<y2i) {
109 the_lines[y1i].x_left=x1;
110 } else {
111 the_lines[y2i].x_left=x1;
112 }
113 return;
114 x1_inf_x2_and_y1_sup_y2:
115 /*
116 (x2, y2)
117
118
119 (x1, y1)
120 */
121 if (dx!=dy)
122 goto x1_inf_x2_and_y1_sup_y2_dx_sup_dy;
123 /* here dx == dy */
124 for (i=y2i; i<y1i; i++, x2-=65536) {
125 the_lines[i].x_left=x2;
126 }
127 return;
128 x1_inf_x2_and_y1_sup_y2_dx_sup_dy:
129 /*
130 xxxx
131 xxxx
132 xxxx
133 xxxx
134 */
135 xinc=muldiv(dx, 65536, dy);
136 xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
137 for (i=y2i; i<y1i; i++, xcur+=xinc) {
138 the_lines[i].x_left=xcur;
139 }
140 return;
141
142 x1_inf_x2_and_y1_inf_y2:
143 /*
144 (x1, y1)
145
146
147 (x2, y2)
148 */
149 if (dx!=dy)
150 goto x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy;
151 /* here dx == dy */
152 for (i=y1i; i<y2i; i++, x1+=65536) {
153 the_lines[i].x_left=x1;
154 }
155 return;
156
157 x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy:
158 /*
159 xxxx
160 xxxx
161 xxxx
162 */
163 xinc=muldiv(dx,65536,dy);
164 xcur=x1+muldiv(xinc, ((y1i<<16)-y1), 65536);
165 for (i=y1i; i<y2i; i++, xcur+=xinc) {
166 the_lines[i].x_left=xcur;
167 }
168 return;
169
170 x1_sup_x2:
171 if (dy<-65535)
172 goto x1_sup_x2_and_y1_sup_y2;
173 if (dy>65535)
174 goto x1_sup_x2_and_y1_inf_y2;
175 /* x1>x2 && y1==y2 */
176 if (y1i<y2i) {
177 the_lines[y1i].x_left=x2;
178 } else {
179 the_lines[y2i].x_left=x2;
180 }
181 return;
182 x1_sup_x2_and_y1_sup_y2:
183 /*
184 (x2, y2)
185
186
187 (x1, y1)
188 */
189 if (dx!=dy)
190 goto x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy;
191 /* here dx == dy */
192 for (i=y2i; i<y1i; i++, x2+=65536) {
193 the_lines[i].x_left=x2;
194 }
195 return;
196 x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy:
197 xinc=muldiv(dx, 65536, dy);
198 xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
199 for (i=y2i; i<y1i; i++, xcur+=xinc) {
200 the_lines[i].x_left=xcur;
201 }
202 return;
203
204 x1_sup_x2_and_y1_inf_y2:
205 /*
206 (x1, y1)
207
208
209 (x2, y2)
210 */
211 if (dx!=dy)
212 goto x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy;
213 /* here dx == dy */
214 for (i=y1i; i<y2i; i++, x1-=65536) {
215 the_lines[i].x_left=x1;
216 }
217 return;
218 x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy:
219 xinc=muldiv(dx, 65536, dy);
220 xcur=x1+muldiv(xinc, (y1i<<16)-y1, 65536);
221 for (i=y1i; i<y2i; i++, xcur+=xinc) {
222 the_lines[i].x_left=xcur;
223 }
224 return;
225 }
226
227 /************************************************
228 * fill_right *
229 ************************************************/
fill_right(device * d,point * p1,point * p2)230 static void fill_right(device *d, point *p1, point *p2)
231 {
232 /* lots of goto for lisibility (if if else if if else else is impossible to debug) */
233 register int x1=p1->x*65536., x2=p2->x*65536., y1=p1->y*65536., y2=p2->y*65536., dx, dy;
234 register int xcur;
235 register int xinc;
236 register int i;
237 register int y1i=(y1+65535)>>16, y2i=(y2+65535)>>16;
238
239 /* in asm, those two subs are good for us, because we can test if x1<x2 and if y1<y2 at the same time, but it's C */
240 dx=x2-x1;
241 dy=y2-y1;
242
243 if (dx<0)
244 goto x1_sup_x2;
245 if (dx)
246 goto x1_inf_x2;
247
248 /* here x1==x2 */
249 if (dy<-65535)
250 goto x1_eq_x2_and_y1_sup_y2;
251 if (dy>65535)
252 goto x1_eq_x2_and_y1_inf_y2;
253 /* here x1==x2 && y1==y2 */
254 if (y1i<y2i) {
255 the_lines[y1i].x_right=x1;
256 } else {
257 the_lines[y2i].x_right=x1;
258 }
259 return;
260 x1_eq_x2_and_y1_sup_y2:
261 for (i=y2i; i<y1i; i++) {
262 the_lines[i].x_right=x1;
263 }
264 return;
265 x1_eq_x2_and_y1_inf_y2:
266 for (i=y1i; i<y2i; i++) {
267 the_lines[i].x_right=x1;
268 }
269 return;
270
271 x1_inf_x2:
272 if (dy<-65535)
273 goto x1_inf_x2_and_y1_sup_y2;
274 if (dy>65535)
275 goto x1_inf_x2_and_y1_inf_y2;
276 /* x1<x2 && y1==y2 */
277 if (y1i<y2i) {
278 the_lines[y1i].x_right=x2;
279 } else {
280 the_lines[y2i].x_right=x2;
281 }
282 return;
283 x1_inf_x2_and_y1_sup_y2:
284 /*
285 (x2, y2)
286
287
288 (x1, y1)
289 */
290 if (dx!=dy)
291 goto x1_inf_x2_and_y1_sup_y2_dx_sup_dy;
292 /* here dx == dy */
293 for (i=y2i; i<y1i; i++, x2-=65536) {
294 the_lines[i].x_right=x2;
295 }
296 return;
297 x1_inf_x2_and_y1_sup_y2_dx_sup_dy:
298 /*
299 xxxx
300 xxxx
301 xxxx
302 xxxx
303 */
304 xinc=muldiv(dx, 65536, dy);
305 xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
306 for (i=y2i; i<y1i; i++, xcur+=xinc) {
307 the_lines[i].x_right=xcur;
308 }
309 return;
310
311 x1_inf_x2_and_y1_inf_y2:
312 /*
313 (x1, y1)
314
315
316 (x2, y2)
317 */
318 if (dx!=dy)
319 goto x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy;
320 /* here dx == dy */
321 for (i=y1i; i<y2i; i++, x1+=65536) {
322 the_lines[i].x_right=x1;
323 }
324 return;
325
326 x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy:
327 /*
328 xxxx
329 xxxx
330 xxxx
331 */
332 xinc=muldiv(dx,65536,dy);
333 xcur=x1+muldiv(xinc, ((y1i<<16)-y1), 65536);
334 for (i=y1i; i<y2i; i++, xcur+=xinc) {
335 the_lines[i].x_right=xcur;
336 }
337 return;
338
339 x1_sup_x2:
340 if (dy<-65535)
341 goto x1_sup_x2_and_y1_sup_y2;
342 if (dy>65535)
343 goto x1_sup_x2_and_y1_inf_y2;
344 /* x1>x2 && y1==y2 */
345 if (y2i<y1i) {
346 the_lines[y2i].x_right=x1;
347 } else {
348 the_lines[y1i].x_right=x1;
349 }
350 return;
351 x1_sup_x2_and_y1_sup_y2:
352 /*
353 (x2, y2)
354
355
356 (x1, y1)
357 */
358 if (dx!=dy)
359 goto x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy;
360 /* here dx == dy */
361 for (i=y2i; i<y1i; i++, x2+=65536) {
362 the_lines[i].x_right=x2;
363 }
364 return;
365 x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy:
366 xinc=muldiv(dx, 65536, dy);
367 xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
368 for (i=y2i; i<y1i; i++, xcur+=xinc) {
369 the_lines[i].x_right=xcur;
370 }
371 return;
372
373 x1_sup_x2_and_y1_inf_y2:
374 /*
375 (x1, y1)
376
377
378 (x2, y2)
379 */
380 if (dx!=dy)
381 goto x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy;
382 /* here dx == dy */
383 for (i=y1i; i<y2i; i++, x1-=65536) {
384 the_lines[i].x_right=x1;
385 }
386 return;
387 x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy:
388 xinc=muldiv(dx, 65536, dy);
389 xcur=x1+muldiv(xinc, (y1i<<16)-y1, 65536);
390 for (i=y1i; i<y2i; i++, xcur+=xinc) {
391 the_lines[i].x_right=xcur;
392 }
393 return;
394 }
395
396 /* device dependant stuff (the only one function in there) (depends of x and y res of device,
397 * of depth too) (we suppose 320x200x256, 256 grey levels)
398 */
fill_lines(device * d,int thecol)399 void fill_lines(device *d, int thecol)
400 {
401 if (d->depth==8) {
402 register int i;
403 #ifndef PC_ARCHI
404 register int j;
405 register unsigned char *q;
406 #endif
407 register unsigned char *p=d->buffer;
408 device_line *cur_line=&the_lines[(int)miny];
409 register int col=thecol;
410
411 p+=miny*SCREEN_X;
412 for (i=miny; i<maxy; i++, p+=SCREEN_X, cur_line++) {
413 #ifndef PC_ARCHI
414 register const int xleft=(cur_line->x_left/65536)+1;
415 register const int xright=cur_line->x_right/65536;
416 q=p;
417 q+=xleft;
418 for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++)
419 *q=col;
420 #else
421 __asm__ volatile ("movl %0, %%ebx \n"
422 "movl %1, %%ecx \n"
423 "shrl $16, %%ebx \n"
424 "shrl $16, %%ecx \n"
425 "incl %%ebx \n"
426 "addl %%ebx, %%edi \n"
427 "inc %%ecx \n"
428 "subl %%ebx, %%ecx \n"
429 "jbe 1f \n"
430 "2: rep; stosb \n"
431 "1: \n"
432 :
433 : "g" (cur_line->x_left), "g" (cur_line->x_right), "a" (col), "D" (p)
434 : "ebx", "ecx", "eax", "edi"
435 );
436 #endif
437 }
438 } else if (d->depth==16) { /* here 16bpp */
439 register int i;
440 #ifndef PC_ARCHI
441 register int j;
442 register unsigned short *q;
443 #endif
444 register unsigned short *p=(unsigned short *)d->buffer;
445 device_line *cur_line=&the_lines[(int)miny];
446 register int col=thecol;
447
448 p+=miny*SCREEN_X;
449 for (i=miny; i<maxy; i++, p+=SCREEN_X, cur_line++) {
450 #ifndef PC_ARCHI
451 register const int xleft=(cur_line->x_left/65536)+1;
452 register const int xright=cur_line->x_right/65536;
453 q=p;
454 q+=xleft;
455 for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++)
456 *q=col;
457 #else
458 __asm__ volatile ("movl %0, %%ebx \n"
459 "movl %1, %%ecx \n"
460 "shrl $16, %%ebx \n"
461 "shrl $16, %%ecx \n"
462 "incl %%ebx \n"
463 "addl %%ebx, %%edi \n"
464 "addl %%ebx, %%edi \n"
465 "inc %%ecx \n"
466 "subl %%ebx, %%ecx \n"
467 "jbe 1f \n"
468 "2: rep; stosw \n"
469 "1: \n"
470 :
471 : "g" (cur_line->x_left), "g" (cur_line->x_right), "a" (col), "D" (p)
472 : "ebx", "ecx", "eax", "edi"
473 );
474 #endif
475 }
476 } else if (d->depth==24) {
477 register int i;
478 register int j;
479 register unsigned char *q;
480 register unsigned char *p=(unsigned char *)d->buffer;
481 device_line *cur_line=&the_lines[(int)miny];
482 register int col1=thecol&255;
483 register int col2=(thecol>>8)&255;
484 register int col3=thecol>>16;
485
486 p+=miny*SCREEN_X*3;
487 for (i=miny; i<maxy; i++, p+=SCREEN_X*3, cur_line++) {
488 register const int xleft=(cur_line->x_left/65536)+1;
489 register const int xright=cur_line->x_right/65536;
490 q=p;
491 q+=xleft*3;
492 for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++) {
493 *q++=col1;
494 *q++=col2;
495 *q=col3;
496 }
497 }
498 } else { /* here 32bpp */
499 register int i;
500 #ifndef PC_ARCHI
501 register int j;
502 register unsigned int *q;
503 #endif
504 register unsigned int *p=(unsigned int *)d->buffer;
505 device_line *cur_line=&the_lines[(int)miny];
506 register int col=thecol;
507
508 p+=miny*SCREEN_X;
509 for (i=miny; i<maxy; i++, p+=SCREEN_X, cur_line++) {
510 #ifndef PC_ARCHI
511 register const int xleft=(cur_line->x_left/65536)+1;
512 register const int xright=cur_line->x_right/65536;
513 q=p;
514 q+=xleft;
515 for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++)
516 *q=col;
517 #else
518 __asm__ volatile ("movl %0, %%ebx \n"
519 "movl %1, %%ecx \n"
520 "shrl $16, %%ebx \n"
521 "shrl $16, %%ecx \n"
522 "incl %%ebx \n"
523 "addl %%ebx, %%edi \n"
524 "addl %%ebx, %%edi \n"
525 "addl %%ebx, %%edi \n"
526 "addl %%ebx, %%edi \n"
527 "incl %%ecx \n"
528 "subl %%ebx, %%ecx \n"
529 "jbe 1f \n"
530 "2: rep; stosl \n"
531 "1: \n"
532 :
533 : "g" (cur_line->x_left), "g" (cur_line->x_right), "a" (col), "D" (p)
534 : "ebx", "ecx", "eax", "edi"
535 );
536 #endif
537 }
538 }
539 }
540
541 /* the poly is direct and clipped and convex */
542 #include <stdio.h>
fillpoly(device * d,poly * p)543 void fillpoly(device *d, poly *p)
544 {
545 register int i;
546 register point *q=&p->points[0], *r=&p->points[0];
547 register int nb=p->nb_points;
548 register int tl=0, br=0;
549
550 assert(p);
551 assert(d);
552 assert(p->nb_points>2);
553 /* get top left and bottom right points */
554 miny=((int)(r[0].y*65536.)+65535)>>16;
555 maxy=((int)(r[0].y*65536.)+32767)>>16;
556
557 for (i=0; i<nb; i++, q++) {
558 /* fprintf(stderr, "p[%d]=(%d, %d)\n", i, q->x, q->y); */
559 if ((q->y < r[tl].y) || (q->y==r[tl].y && q->x < r[tl].x)) {
560 tl=i;
561 miny=((int)(r[i].y*65536.)+65535)>>16;
562 }
563 if ((q->y > r[br].y) || (q->y==r[br].y && q->x > r[br].x)) {
564 br=i;
565 maxy=((int)(r[i].y*65536.)+32767)>>16;
566 }
567 }
568 /* fprintf(stderr, "top-left=%d bottom-right=%d\nminy=%d maxy=%d\n", tl, br, miny, maxy); */
569 /* draw left stuff */
570 if (br==tl)
571 return;
572 assert(br!=tl);
573 if (br<tl) {
574 for (i=tl; i<nb-1; i++)
575 fill_left(d, &r[i], &r[i+1]);
576 fill_left(d, &r[nb-1], &r[0]);
577 for (i=0; i<=br-1; i++)
578 fill_left(d, &r[i], &r[i+1]);
579 } else { /* br > tl */
580 for (i=tl; i<=br-1; i++) {
581 /* fprintf(stderr, "line p[%d] -> p[%d]\n", i, i+1); */
582 fill_left(d, &r[i], &r[i+1]);
583 }
584 }
585 /* getchar(); */
586 /* draw right stuff */
587 if (br>tl) {
588 for (i=br; i<nb-1; i++)
589 fill_right(d, &r[i], &r[i+1]);
590 fill_right(d, &r[nb-1], &r[0]);
591 for (i=0; i<=tl-1; i++)
592 fill_right(d, &r[i], &r[i+1]);
593 } else { /* br < tl */
594 for (i=br; i<=tl-1; i++)
595 fill_right(d, &r[i], &r[i+1]);
596 }
597
598 /* fill the lines */
599 fill_lines(d, p->color);
600 }
601