Initial revision
diff --git a/src/libdraw/md-fillpoly.c b/src/libdraw/md-fillpoly.c
new file mode 100644
index 0000000..928ae1e
--- /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;
+}
