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