WebSVN – planix.SVN – Blame – /os/branches/feature_posix/sys/src/cmd/unix/drawterm/libmemdraw/fillpoly.c

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(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`
		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)(((ulong)z)^((ulong)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)(((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`
		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*), 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(xerrp[0]->den + p[0]->zerrxden > 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*), 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(yerrp[0]->den + p[0]->zerryden > 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*), zcompare);`
		467	`break;`
		468	`}`
		469	`}`
		470	`}`
		471	`}`
		472
		473	`static int`
		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`
		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`
		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	`}`

Subversion Repositories planix.SVN

(root)/os/branches/feature_posix/sys/src/cmd/unix/drawterm/libmemdraw/fillpoly.c – Rev 2