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