fillpoly.c - vx32 - Local 9vx git repository for patches.
(HTM) git clone git://r-36.net/vx32
(DIR) Log
(DIR) Files
(DIR) Refs
---
fillpoly.c (9959B)
---
1 #include "u.h"
2 #include "lib.h"
3 #include "draw.h"
4 #include "memdraw.h"
5 #include "memlayer.h"
6
7 typedef struct Seg Seg;
8
9 struct Seg
10 {
11 Point p0;
12 Point p1;
13 long num;
14 long den;
15 long dz;
16 long dzrem;
17 long z;
18 long zerr;
19 long d;
20 };
21
22 static void zsort(Seg **seg, Seg **ep);
23 static int ycompare(void*, void*);
24 static int xcompare(void*, void*);
25 static int zcompare(void*, void*);
26 static void xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
27 static void yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int);
28
29 #if 0
30 static void
31 fillcolor(Memimage *dst, int left, int right, int y, Memimage *src, Point p)
32 {
33 int srcval;
34
35 USED(src);
36 srcval = p.x;
37 p.x = left;
38 p.y = y;
39 memset(byteaddr(dst, p), srcval, right-left);
40 }
41 #endif
42
43 static void
44 fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
45 {
46 Rectangle r;
47
48 r.min.x = left;
49 r.min.y = y;
50 r.max.x = right;
51 r.max.y = y+1;
52 p.x += left;
53 p.y += y;
54 memdraw(dst, r, src, p, memopaque, p, op);
55 }
56
57 static void
58 fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
59 {
60 Rectangle r;
61
62 r.min.x = x;
63 r.min.y = y;
64 r.max.x = x+1;
65 r.max.y = y+1;
66 p.x += x;
67 p.y += y;
68 memdraw(dst, r, src, p, memopaque, p, op);
69 }
70
71 void
72 memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
73 {
74 _memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
75 }
76
77 void
78 _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
79 {
80 Seg **seg, *segtab;
81 Point p0;
82 int i;
83
84 if(nvert == 0)
85 return;
86
87 seg = malloc((nvert+2)*sizeof(Seg*));
88 if(seg == nil)
89 return;
90 segtab = malloc((nvert+1)*sizeof(Seg));
91 if(segtab == nil) {
92 free(seg);
93 return;
94 }
95
96 sp.x = (sp.x - vert[0].x) >> fixshift;
97 sp.y = (sp.y - vert[0].y) >> fixshift;
98 p0 = vert[nvert-1];
99 if(!fixshift) {
100 p0.x <<= 1;
101 p0.y <<= 1;
102 }
103 for(i = 0; i < nvert; i++) {
104 segtab[i].p0 = p0;
105 p0 = vert[i];
106 if(!fixshift) {
107 p0.x <<= 1;
108 p0.y <<= 1;
109 }
110 segtab[i].p1 = p0;
111 segtab[i].d = 1;
112 }
113 if(!fixshift)
114 fixshift = 1;
115
116 xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
117 if(detail)
118 yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
119
120 free(seg);
121 free(segtab);
122 }
123
124 static long
125 mod(long x, long y)
126 {
127 long z;
128
129 z = x%y;
130 if((long)(((uint32)z)^((uint32)y)) > 0 || z == 0)
131 return z;
132 return z + y;
133 }
134
135 static long
136 sdiv(long x, long y)
137 {
138 if((long)(((uint32)x)^((uint32)y)) >= 0 || x == 0)
139 return x/y;
140
141 return (x+((y>>30)|1))/y-1;
142 }
143
144 static long
145 smuldivmod(long x, long y, long z, long *mod)
146 {
147 vlong vx;
148
149 if(x == 0 || y == 0){
150 *mod = 0;
151 return 0;
152 }
153 vx = x;
154 vx *= y;
155 *mod = vx % z;
156 if(*mod < 0)
157 *mod += z; /* z is always >0 */
158 if((vx < 0) == (z < 0))
159 return vx/z;
160 return -((-vx)/z);
161 }
162
163 static void
164 xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
165 {
166 long y, maxy, x, x2, xerr, xden, onehalf;
167 Seg **ep, **next, **p, **q, *s;
168 long n, i, iy, cnt, ix, ix2, minx, maxx;
169 Point pt;
170 void (*fill)(Memimage*, int, int, int, Memimage*, Point, int);
171
172 fill = fillline;
173 /*
174 * This can only work on 8-bit destinations, since fillcolor is
175 * just using memset on sp.x.
176 *
177 * I'd rather not even enable it then, since then if the general
178 * code is too slow, someone will come up with a better improvement
179 * than this sleazy hack. -rsc
180 *
181 if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
182 fill = fillcolor;
183 sp.x = membyteval(src);
184 }
185 *
186 */
187 USED(clipped);
188
189
190 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
191 *p = s;
192 if(s->p0.y == s->p1.y)
193 continue;
194 if(s->p0.y > s->p1.y) {
195 pt = s->p0;
196 s->p0 = s->p1;
197 s->p1 = pt;
198 s->d = -s->d;
199 }
200 s->num = s->p1.x - s->p0.x;
201 s->den = s->p1.y - s->p0.y;
202 s->dz = sdiv(s->num, s->den) << fixshift;
203 s->dzrem = mod(s->num, s->den) << fixshift;
204 s->dz += sdiv(s->dzrem, s->den);
205 s->dzrem = mod(s->dzrem, s->den);
206 p++;
207 }
208 n = p-seg;
209 if(n == 0)
210 return;
211 *p = 0;
212 qsort(seg, p-seg , sizeof(Seg*), (int(*)(const void*, const void*))ycompare);
213
214 onehalf = 0;
215 if(fixshift)
216 onehalf = 1 << (fixshift-1);
217
218 minx = dst->clipr.min.x;
219 maxx = dst->clipr.max.x;
220
221 y = seg[0]->p0.y;
222 if(y < (dst->clipr.min.y << fixshift))
223 y = dst->clipr.min.y << fixshift;
224 iy = (y + onehalf) >> fixshift;
225 y = (iy << fixshift) + onehalf;
226 maxy = dst->clipr.max.y << fixshift;
227
228 ep = next = seg;
229
230 while(y<maxy) {
231 for(q = p = seg; p < ep; p++) {
232 s = *p;
233 if(s->p1.y < y)
234 continue;
235 s->z += s->dz;
236 s->zerr += s->dzrem;
237 if(s->zerr >= s->den) {
238 s->z++;
239 s->zerr -= s->den;
240 if(s->zerr < 0 || s->zerr >= s->den)
241 print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
242 }
243 *q++ = s;
244 }
245
246 for(p = next; *p; p++) {
247 s = *p;
248 if(s->p0.y >= y)
249 break;
250 if(s->p1.y < y)
251 continue;
252 s->z = s->p0.x;
253 s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
254 if(s->zerr < 0 || s->zerr >= s->den)
255 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
256 *q++ = s;
257 }
258 ep = q;
259 next = p;
260
261 if(ep == seg) {
262 if(*next == 0)
263 break;
264 iy = (next[0]->p0.y + onehalf) >> fixshift;
265 y = (iy << fixshift) + onehalf;
266 continue;
267 }
268
269 zsort(seg, ep);
270
271 for(p = seg; p < ep; p++) {
272 cnt = 0;
273 x = p[0]->z;
274 xerr = p[0]->zerr;
275 xden = p[0]->den;
276 ix = (x + onehalf) >> fixshift;
277 if(ix >= maxx)
278 break;
279 if(ix < minx)
280 ix = minx;
281 cnt += p[0]->d;
282 p++;
283 for(;;) {
284 if(p == ep) {
285 print("xscan: fill to infinity");
286 return;
287 }
288 cnt += p[0]->d;
289 if((cnt&wind) == 0)
290 break;
291 p++;
292 }
293 x2 = p[0]->z;
294 ix2 = (x2 + onehalf) >> fixshift;
295 if(ix2 <= minx)
296 continue;
297 if(ix2 > maxx)
298 ix2 = maxx;
299 if(ix == ix2 && detail) {
300 if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
301 x++;
302 ix = (x + x2) >> (fixshift+1);
303 ix2 = ix+1;
304 }
305 (*fill)(dst, ix, ix2, iy, src, sp, op);
306 }
307 y += (1<<fixshift);
308 iy++;
309 }
310 }
311
312 static void
313 yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
314 {
315 long x, maxx, y, y2, yerr, yden, onehalf;
316 Seg **ep, **next, **p, **q, *s;
317 int n, i, ix, cnt, iy, iy2, miny, maxy;
318 Point pt;
319
320 for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
321 *p = s;
322 if(s->p0.x == s->p1.x)
323 continue;
324 if(s->p0.x > s->p1.x) {
325 pt = s->p0;
326 s->p0 = s->p1;
327 s->p1 = pt;
328 s->d = -s->d;
329 }
330 s->num = s->p1.y - s->p0.y;
331 s->den = s->p1.x - s->p0.x;
332 s->dz = sdiv(s->num, s->den) << fixshift;
333 s->dzrem = mod(s->num, s->den) << fixshift;
334 s->dz += sdiv(s->dzrem, s->den);
335 s->dzrem = mod(s->dzrem, s->den);
336 p++;
337 }
338 n = p-seg;
339 if(n == 0)
340 return;
341 *p = 0;
342 qsort(seg, n , sizeof(Seg*), (int(*)(const void*, const void*))xcompare);
343
344 onehalf = 0;
345 if(fixshift)
346 onehalf = 1 << (fixshift-1);
347
348 miny = dst->clipr.min.y;
349 maxy = dst->clipr.max.y;
350
351 x = seg[0]->p0.x;
352 if(x < (dst->clipr.min.x << fixshift))
353 x = dst->clipr.min.x << fixshift;
354 ix = (x + onehalf) >> fixshift;
355 x = (ix << fixshift) + onehalf;
356 maxx = dst->clipr.max.x << fixshift;
357
358 ep = next = seg;
359
360 while(x<maxx) {
361 for(q = p = seg; p < ep; p++) {
362 s = *p;
363 if(s->p1.x < x)
364 continue;
365 s->z += s->dz;
366 s->zerr += s->dzrem;
367 if(s->zerr >= s->den) {
368 s->z++;
369 s->zerr -= s->den;
370 if(s->zerr < 0 || s->zerr >= s->den)
371 print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
372 }
373 *q++ = s;
374 }
375
376 for(p = next; *p; p++) {
377 s = *p;
378 if(s->p0.x >= x)
379 break;
380 if(s->p1.x < x)
381 continue;
382 s->z = s->p0.y;
383 s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
384 if(s->zerr < 0 || s->zerr >= s->den)
385 print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
386 *q++ = s;
387 }
388 ep = q;
389 next = p;
390
391 if(ep == seg) {
392 if(*next == 0)
393 break;
394 ix = (next[0]->p0.x + onehalf) >> fixshift;
395 x = (ix << fixshift) + onehalf;
396 continue;
397 }
398
399 zsort(seg, ep);
400
401 for(p = seg; p < ep; p++) {
402 cnt = 0;
403 y = p[0]->z;
404 yerr = p[0]->zerr;
405 yden = p[0]->den;
406 iy = (y + onehalf) >> fixshift;
407 if(iy >= maxy)
408 break;
409 if(iy < miny)
410 iy = miny;
411 cnt += p[0]->d;
412 p++;
413 for(;;) {
414 if(p == ep) {
415 print("yscan: fill to infinity");
416 return;
417 }
418 cnt += p[0]->d;
419 if((cnt&wind) == 0)
420 break;
421 p++;
422 }
423 y2 = p[0]->z;
424 iy2 = (y2 + onehalf) >> fixshift;
425 if(iy2 <= miny)
426 continue;
427 if(iy2 > maxy)
428 iy2 = maxy;
429 if(iy == iy2) {
430 if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
431 y++;
432 iy = (y + y2) >> (fixshift+1);
433 fillpoint(dst, ix, iy, src, sp, op);
434 }
435 }
436 x += (1<<fixshift);
437 ix++;
438 }
439 }
440
441 static void
442 zsort(Seg **seg, Seg **ep)
443 {
444 int done;
445 Seg **q, **p, *s;
446
447 if(ep-seg < 20) {
448 /* bubble sort by z - they should be almost sorted already */
449 q = ep;
450 do {
451 done = 1;
452 q--;
453 for(p = seg; p < q; p++) {
454 if(p[0]->z > p[1]->z) {
455 s = p[0];
456 p[0] = p[1];
457 p[1] = s;
458 done = 0;
459 }
460 }
461 } while(!done);
462 } else {
463 q = ep-1;
464 for(p = seg; p < q; p++) {
465 if(p[0]->z > p[1]->z) {
466 qsort(seg, ep-seg, sizeof(Seg*), (int(*)(const void*, const void*))zcompare);
467 break;
468 }
469 }
470 }
471 }
472
473 static int
474 ycompare(void *a, void *b)
475 {
476 Seg **s0, **s1;
477 long y0, y1;
478
479 s0 = a;
480 s1 = b;
481 y0 = (*s0)->p0.y;
482 y1 = (*s1)->p0.y;
483
484 if(y0 < y1)
485 return -1;
486 if(y0 == y1)
487 return 0;
488 return 1;
489 }
490
491 static int
492 xcompare(void *a, void *b)
493 {
494 Seg **s0, **s1;
495 long x0, x1;
496
497 s0 = a;
498 s1 = b;
499 x0 = (*s0)->p0.x;
500 x1 = (*s1)->p0.x;
501
502 if(x0 < x1)
503 return -1;
504 if(x0 == x1)
505 return 0;
506 return 1;
507 }
508
509 static int
510 zcompare(void *a, void *b)
511 {
512 Seg **s0, **s1;
513 long z0, z1;
514
515 s0 = a;
516 s1 = b;
517 z0 = (*s0)->z;
518 z1 = (*s1)->z;
519
520 if(z0 < z1)
521 return -1;
522 if(z0 == z1)
523 return 0;
524 return 1;
525 }