diff options
Diffstat (limited to 'src/libdraw/md-fillpoly.c')
| -rw-r--r-- | src/libdraw/md-fillpoly.c | 524 |
1 files changed, 524 insertions, 0 deletions
diff --git a/src/libdraw/md-fillpoly.c b/src/libdraw/md-fillpoly.c new file mode 100644 index 00000000..928ae1e1 --- /dev/null +++ b/src/libdraw/md-fillpoly.c @@ -0,0 +1,524 @@ +#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)(((u32int)z)^((u32int)y)) > 0 || z == 0) + return z; + return z + y; +} + +static long +sdiv(long x, long y) +{ + if((long)(((u32int)x)^((u32int)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; +} |