Subversion Repositories planix.SVN

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 
}