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 }