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