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