vx32

Local 9vx git repository for patches.
git clone git://r-36.net/vx32
Log | Files | Refs

fillpoly.c (9959B)


      1 #include "u.h"
      2 #include "lib.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 #if 0
     30 static void
     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
     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
     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
     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
     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
    125 mod(long x, long y)
    126 {
    127 	long z;
    128 
    129 	z = x%y;
    130 	if((long)(((uint32)z)^((uint32)y)) > 0 || z == 0)
    131 		return z;
    132 	return z + y;
    133 }
    134 
    135 static long
    136 sdiv(long x, long y)
    137 {
    138 	if((long)(((uint32)x)^((uint32)y)) >= 0 || x == 0)
    139 		return x/y;
    140 
    141 	return (x+((y>>30)|1))/y-1;
    142 }
    143 
    144 static long
    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
    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*), (int(*)(const void*, const void*))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
    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*), (int(*)(const void*, const void*))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
    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*), (int(*)(const void*, const void*))zcompare);
    467 				break;
    468 			}
    469 		}
    470 	}
    471 }
    472 
    473 static int
    474 ycompare(void *a, void *b)
    475 {
    476 	Seg **s0, **s1;
    477 	long y0, y1;
    478 
    479 	s0 = a;
    480 	s1 = 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
    492 xcompare(void *a, void *b)
    493 {
    494 	Seg **s0, **s1;
    495 	long x0, x1;
    496 
    497 	s0 = a;
    498 	s1 = 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
    510 zcompare(void *a, void *b)
    511 {
    512 	Seg **s0, **s1;
    513 	long z0, z1;
    514 
    515 	s0 = a;
    516 	s1 = 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 }