plan9port

fillpoly.c (9946B)

---

 #include <u.h>
 #include <libc.h>
 #include <draw.h>
 #include <memdraw.h>
 
 typedef struct Seg	Seg;
 
 struct Seg
 {
 	Point	p0;
 	Point	p1;
 	long	num;
 	long	den;
 	long	dz;
 	long	dzrem;
 	long	z;
 	long	zerr;
 	long	d;
 };
 
 static	void	zsort(Seg **seg, Seg **ep);
 static	int	ycompare(const void*, const void*);
 static	int	xcompare(const void*, const void*);
 static	int	zcompare(const void*, const void*);
 static	void	xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
 static	void	yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int);
 
 #if 0
 static void
 fillcolor(Memimage *dst, int left, int right, int y, Memimage *src, Point p)
 {
 	int srcval;
 
 	USED(src);
 	srcval = p.x;
 	p.x = left;
 	p.y = y;
 	memset(byteaddr(dst, p), srcval, right-left);
 }
 #endif
 
 static void
 fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
 {
 	Rectangle r;
 
 	r.min.x = left;
 	r.min.y = y;
 	r.max.x = right;
 	r.max.y = y+1;
 	p.x += left;
 	p.y += y;
 	memdraw(dst, r, src, p, memopaque, p, op);
 }
 
 static void
 fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
 {
 	Rectangle r;
 
 	r.min.x = x;
 	r.min.y = y;
 	r.max.x = x+1;
 	r.max.y = y+1;
 	p.x += x;
 	p.y += y;
 	memdraw(dst, r, src, p, memopaque, p, op);
 }
 
 void
 memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
 {
 	_memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
 }
 
 void
 _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
 {
 	Seg **seg, *segtab;
 	Point p0;
 	int i;
 
 	if(nvert == 0)
 		return;
 
 	seg = malloc((nvert+2)*sizeof(Seg*));
 	if(seg == nil)
 		return;
 	segtab = malloc((nvert+1)*sizeof(Seg));
 	if(segtab == nil) {
 		free(seg);
 		return;
 	}
 
 	sp.x = (sp.x - vert[0].x) >> fixshift;
 	sp.y = (sp.y - vert[0].y) >> fixshift;
 	p0 = vert[nvert-1];
 	if(!fixshift) {
 		p0.x <<= 1;
 		p0.y <<= 1;
 	}
 	for(i = 0; i < nvert; i++) {
 		segtab[i].p0 = p0;
 		p0 = vert[i];
 		if(!fixshift) {
 			p0.x <<= 1;
 			p0.y <<= 1;
 		}
 		segtab[i].p1 = p0;
 		segtab[i].d = 1;
 	}
 	if(!fixshift)
 		fixshift = 1;
 
 	xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
 	if(detail)
 		yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
 
 	free(seg);
 	free(segtab);
 }
 
 static long
 mod(long x, long y)
 {
 	long z;
 
 	z = x%y;
 	if((long)(((ulong)z)^((ulong)y)) > 0 || z == 0)
 		return z;
 	return z + y;
 }
 
 static long
 sdiv(long x, long y)
 {
 	if((long)(((ulong)x)^((ulong)y)) >= 0 || x == 0)
 		return x/y;
 
 	return (x+((y>>30)|1))/y-1;
 }
 
 static long
 smuldivmod(long x, long y, long z, long *mod)
 {
 	vlong vx;
 
 	if(x == 0 || y == 0){
 		*mod = 0;
 		return 0;
 	}
 	vx = x;
 	vx *= y;
 	*mod = vx % z;
 	if(*mod < 0)
 		*mod += z;	/* z is always >0 */
 	if((vx < 0) == (z < 0))
 		return vx/z;
 	return -((-vx)/z);
 }
 
 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)
 {
 	long y, maxy, x, x2, xerr, xden, onehalf;
 	Seg **ep, **next, **p, **q, *s;
 	long n, i, iy, cnt, ix, ix2, minx, maxx;
 	Point pt;
 	void	(*fill)(Memimage*, int, int, int, Memimage*, Point, int);
 
 	fill = fillline;
 /*
  * This can only work on 8-bit destinations, since fillcolor is
  * just using memset on sp.x.
  *
  * I'd rather not even enable it then, since then if the general
  * code is too slow, someone will come up with a better improvement
  * than this sleazy hack.	-rsc
  *
 	if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
 		fill = fillcolor;
 		sp.x = membyteval(src);
 	}
  *
  */
 	USED(clipped);
 
 
 	for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
 		*p = s;
 		if(s->p0.y == s->p1.y)
 			continue;
 		if(s->p0.y > s->p1.y) {
 			pt = s->p0;
 			s->p0 = s->p1;
 			s->p1 = pt;
 			s->d = -s->d;
 		}
 		s->num = s->p1.x - s->p0.x;
 		s->den = s->p1.y - s->p0.y;
 		s->dz = sdiv(s->num, s->den) << fixshift;
 		s->dzrem = mod(s->num, s->den) << fixshift;
 		s->dz += sdiv(s->dzrem, s->den);
 		s->dzrem = mod(s->dzrem, s->den);
 		p++;
 	}
 	n = p-seg;
 	if(n == 0)
 		return;
 	*p = 0;
 	qsort(seg, p-seg , sizeof(Seg*), ycompare);
 
 	onehalf = 0;
 	if(fixshift)
 		onehalf = 1 << (fixshift-1);
 
 	minx = dst->clipr.min.x;
 	maxx = dst->clipr.max.x;
 
 	y = seg[0]->p0.y;
 	if(y < (dst->clipr.min.y << fixshift))
 		y = dst->clipr.min.y << fixshift;
 	iy = (y + onehalf) >> fixshift;
 	y = (iy << fixshift) + onehalf;
 	maxy = dst->clipr.max.y << fixshift;
 
 	ep = next = seg;
 
 	while(y<maxy) {
 		for(q = p = seg; p < ep; p++) {
 			s = *p;
 			if(s->p1.y < y)
 				continue;
 			s->z += s->dz;
 			s->zerr += s->dzrem;
 			if(s->zerr >= s->den) {
 				s->z++;
 				s->zerr -= s->den;
 				if(s->zerr < 0 || s->zerr >= s->den)
 					print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
 			}
 			*q++ = s;
 		}
 
 		for(p = next; *p; p++) {
 			s = *p;
 			if(s->p0.y >= y)
 				break;
 			if(s->p1.y < y)
 				continue;
 			s->z = s->p0.x;
 			s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
 			if(s->zerr < 0 || s->zerr >= s->den)
 				print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
 			*q++ = s;
 		}
 		ep = q;
 		next = p;
 
 		if(ep == seg) {
 			if(*next == 0)
 				break;
 			iy = (next[0]->p0.y + onehalf) >> fixshift;
 			y = (iy << fixshift) + onehalf;
 			continue;
 		}
 
 		zsort(seg, ep);
 
 		for(p = seg; p < ep; p++) {
 			cnt = 0;
 			x = p[0]->z;
 			xerr = p[0]->zerr;
 			xden = p[0]->den;
 			ix = (x + onehalf) >> fixshift;
 			if(ix >= maxx)
 				break;
 			if(ix < minx)
 				ix = minx;
 			cnt += p[0]->d;
 			p++;
 			for(;;) {
 				if(p == ep) {
 					print("xscan: fill to infinity");
 					return;
 				}
 				cnt += p[0]->d;
 				if((cnt&wind) == 0)
 					break;
 				p++;
 			}
 			x2 = p[0]->z;
 			ix2 = (x2 + onehalf) >> fixshift;
 			if(ix2 <= minx)
 				continue;
 			if(ix2 > maxx)
 				ix2 = maxx;
 			if(ix == ix2 && detail) {
 				if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
 					x++;
 				ix = (x + x2) >> (fixshift+1);
 				ix2 = ix+1;
 			}
 			(*fill)(dst, ix, ix2, iy, src, sp, op);
 		}
 		y += (1<<fixshift);
 		iy++;
 	}
 }
 
 static void
 yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
 {
 	long x, maxx, y, y2, yerr, yden, onehalf;
 	Seg **ep, **next, **p, **q, *s;
 	int n, i, ix, cnt, iy, iy2, miny, maxy;
 	Point pt;
 
 	for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
 		*p = s;
 		if(s->p0.x == s->p1.x)
 			continue;
 		if(s->p0.x > s->p1.x) {
 			pt = s->p0;
 			s->p0 = s->p1;
 			s->p1 = pt;
 			s->d = -s->d;
 		}
 		s->num = s->p1.y - s->p0.y;
 		s->den = s->p1.x - s->p0.x;
 		s->dz = sdiv(s->num, s->den) << fixshift;
 		s->dzrem = mod(s->num, s->den) << fixshift;
 		s->dz += sdiv(s->dzrem, s->den);
 		s->dzrem = mod(s->dzrem, s->den);
 		p++;
 	}
 	n = p-seg;
 	if(n == 0)
 		return;
 	*p = 0;
 	qsort(seg, n , sizeof(Seg*), xcompare);
 
 	onehalf = 0;
 	if(fixshift)
 		onehalf = 1 << (fixshift-1);
 
 	miny = dst->clipr.min.y;
 	maxy = dst->clipr.max.y;
 
 	x = seg[0]->p0.x;
 	if(x < (dst->clipr.min.x << fixshift))
 		x = dst->clipr.min.x << fixshift;
 	ix = (x + onehalf) >> fixshift;
 	x = (ix << fixshift) + onehalf;
 	maxx = dst->clipr.max.x << fixshift;
 
 	ep = next = seg;
 
 	while(x<maxx) {
 		for(q = p = seg; p < ep; p++) {
 			s = *p;
 			if(s->p1.x < x)
 				continue;
 			s->z += s->dz;
 			s->zerr += s->dzrem;
 			if(s->zerr >= s->den) {
 				s->z++;
 				s->zerr -= s->den;
 				if(s->zerr < 0 || s->zerr >= s->den)
 					print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
 			}
 			*q++ = s;
 		}
 
 		for(p = next; *p; p++) {
 			s = *p;
 			if(s->p0.x >= x)
 				break;
 			if(s->p1.x < x)
 				continue;
 			s->z = s->p0.y;
 			s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
 			if(s->zerr < 0 || s->zerr >= s->den)
 				print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
 			*q++ = s;
 		}
 		ep = q;
 		next = p;
 
 		if(ep == seg) {
 			if(*next == 0)
 				break;
 			ix = (next[0]->p0.x + onehalf) >> fixshift;
 			x = (ix << fixshift) + onehalf;
 			continue;
 		}
 
 		zsort(seg, ep);
 
 		for(p = seg; p < ep; p++) {
 			cnt = 0;
 			y = p[0]->z;
 			yerr = p[0]->zerr;
 			yden = p[0]->den;
 			iy = (y + onehalf) >> fixshift;
 			if(iy >= maxy)
 				break;
 			if(iy < miny)
 				iy = miny;
 			cnt += p[0]->d;
 			p++;
 			for(;;) {
 				if(p == ep) {
 					print("yscan: fill to infinity");
 					return;
 				}
 				cnt += p[0]->d;
 				if((cnt&wind) == 0)
 					break;
 				p++;
 			}
 			y2 = p[0]->z;
 			iy2 = (y2 + onehalf) >> fixshift;
 			if(iy2 <= miny)
 				continue;
 			if(iy2 > maxy)
 				iy2 = maxy;
 			if(iy == iy2) {
 				if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
 					y++;
 				iy = (y + y2) >> (fixshift+1);
 				fillpoint(dst, ix, iy, src, sp, op);
 			}
 		}
 		x += (1<<fixshift);
 		ix++;
 	}
 }
 
 static void
 zsort(Seg **seg, Seg **ep)
 {
 	int done;
 	Seg **q, **p, *s;
 
 	if(ep-seg < 20) {
 		/* bubble sort by z - they should be almost sorted already */
 		q = ep;
 		do {
 			done = 1;
 			q--;
 			for(p = seg; p < q; p++) {
 				if(p[0]->z > p[1]->z) {
 					s = p[0];
 					p[0] = p[1];
 					p[1] = s;
 					done = 0;
 				}
 			}
 		} while(!done);
 	} else {
 		q = ep-1;
 		for(p = seg; p < q; p++) {
 			if(p[0]->z > p[1]->z) {
 				qsort(seg, ep-seg, sizeof(Seg*), zcompare);
 				break;
 			}
 		}
 	}
 }
 
 static int
 ycompare(const void *a, const void *b)
 {
 	Seg **s0, **s1;
 	long y0, y1;
 
 	s0 = (Seg**)a;
 	s1 = (Seg**)b;
 	y0 = (*s0)->p0.y;
 	y1 = (*s1)->p0.y;
 
 	if(y0 < y1)
 		return -1;
 	if(y0 == y1)
 		return 0;
 	return 1;
 }
 
 static int
 xcompare(const void *a, const void *b)
 {
 	Seg **s0, **s1;
 	long x0, x1;
 
 	s0 = (Seg**)a;
 	s1 = (Seg**)b;
 	x0 = (*s0)->p0.x;
 	x1 = (*s1)->p0.x;
 
 	if(x0 < x1)
 		return -1;
 	if(x0 == x1)
 		return 0;
 	return 1;
 }
 
 static int
 zcompare(const void *a, const void *b)
 {
 	Seg **s0, **s1;
 	long z0, z1;
 
 	s0 = (Seg**)a;
 	s1 = (Seg**)b;
 	z0 = (*s0)->z;
 	z1 = (*s1)->z;
 
 	if(z0 < z1)
 		return -1;
 	if(z0 == z1)
 		return 0;
 	return 1;
 }