xref: /plan9/sys/src/cmd/unix/drawterm/libmemdraw/fillpoly.c (revision 8ccd4a6360d974db7bd7bbd4f37e7018419ea908)
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(const void*, const void*);
24 static	int	xcompare(const void*, const void*);
25 static	int	zcompare(const void*, const 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 #ifdef NOT
30 static void
fillcolor(Memimage * dst,int left,int right,int y,Memimage * src,Point p)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
fillline(Memimage * dst,int left,int right,int y,Memimage * src,Point p,int op)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
fillpoint(Memimage * dst,int x,int y,Memimage * src,Point p,int op)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
memfillpoly(Memimage * dst,Point * vert,int nvert,int w,Memimage * src,Point sp,int op)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
_memfillpolysc(Memimage * dst,Point * vert,int nvert,int w,Memimage * src,Point sp,int detail,int fixshift,int clipped,int op)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
mod(long x,long y)125 mod(long x, long y)
126 {
127 	long z;
128 
129 	z = x%y;
130 	if((long)(((ulong)z)^((ulong)y)) > 0 || z == 0)
131 		return z;
132 	return z + y;
133 }
134 
135 static long
sdiv(long x,long y)136 sdiv(long x, long y)
137 {
138 	if((long)(((ulong)x)^((ulong)y)) >= 0 || x == 0)
139 		return x/y;
140 
141 	return (x+((y>>30)|1))/y-1;
142 }
143 
144 static long
smuldivmod(long x,long y,long z,long * mod)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
xscan(Memimage * dst,Seg ** seg,Seg * segtab,int nseg,int wind,Memimage * src,Point sp,int detail,int fixshift,int clipped,int op)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*), 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
yscan(Memimage * dst,Seg ** seg,Seg * segtab,int nseg,int wind,Memimage * src,Point sp,int fixshift,int op)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*), 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
zsort(Seg ** seg,Seg ** ep)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*), zcompare);
467 				break;
468 			}
469 		}
470 	}
471 }
472 
473 static int
ycompare(const void * a,const void * b)474 ycompare(const void *a, const void *b)
475 {
476 	Seg **s0, **s1;
477 	long y0, y1;
478 
479 	s0 = (Seg**)a;
480 	s1 = (Seg**)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
xcompare(const void * a,const void * b)492 xcompare(const void *a, const void *b)
493 {
494 	Seg **s0, **s1;
495 	long x0, x1;
496 
497 	s0 = (Seg**)a;
498 	s1 = (Seg**)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
zcompare(const void * a,const void * b)510 zcompare(const void *a, const void *b)
511 {
512 	Seg **s0, **s1;
513 	long z0, z1;
514 
515 	s0 = (Seg**)a;
516 	s1 = (Seg**)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 }
526