implement Polyfill; include "sys.m"; sys: Sys; include "draw.m"; draw: Draw; Point, Rect, Image, Endsquare: import draw; include "math/polyfill.m"; ∞: con 16r7fffffff; init() { sys = load Sys Sys->PATH; draw = load Draw Draw->PATH; } initzbuf(r: Rect): ref Zstate { if(sys == nil) init(); s := ref Zstate; s.r = r; s.xlen = r.dx(); s.ylen = r.dy(); s.xylen = s.xlen*s.ylen; s.zbuf0 = array[s.xylen] of int; s.zbuf1 = array[s.xylen] of int; return s; } clearzbuf(s: ref Zstate) { b0 := s.zbuf0; b1 := s.zbuf1; n := s.xylen; for(i := 0; i < n; i++) b0[i] = b1[i] = ∞; } setzbuf(s: ref Zstate, zd: int) { b0 := s.zbuf0; b1 := s.zbuf1; n := s.xylen; for(i := 0; i < n; i++) b0[i] = b1[i] = zd; } Seg: adt { p0: Point; p1: Point; num: int; den: int; dz: int; dzrem: int; z: int; zerr: int; d: int; }; fillline(dst: ref Image, left: int, right: int, y: int, src: ref Image, p: Point) { p.x += left; p.y += y; dst.line((left, y), (right, y), Endsquare, Endsquare, 0, src, p); } filllinez(dst: ref Image, left: int, right: int, y: int, z: int, e: int, dx: int, k: int, zbuf0: array of int, zbuf1: array of int, src: ref Image, p: Point) { prevx := ∞; for(x := left; x <= right; x++){ if(z+e < zbuf0[k] || (z-e <= zbuf1[k] && x != right && prevx != ∞)){ zbuf0[k] = z-e; zbuf1[k] = z+e; if(prevx == ∞) prevx = x; } else if(prevx != ∞){ fillline(dst, prevx, x-1, y, src, p); prevx = ∞; } z += dx; k++; } if(prevx != ∞) fillline(dst, prevx, right, y, src, p); } fillpoly(dst: ref Image, vert: array of Point, w: int, src: ref Image, sp: Point, zstate: ref Zstate, dc: int, dx: int, dy: int) { p0: Point; i: int; nvert := len vert; if(nvert == 0) return; fixshift := 0; seg := array[nvert+2] of ref Seg; if(seg == nil) return; segtab := array[nvert+1] of ref Seg; if(segtab == nil) 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] = ref Seg; 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, zstate, dc, dx, dy, fixshift); } mod(x: int, y: int): int { z: int; z = x%y; if((z^y) > 0 || z == 0) return z; return z + y; } sdiv(x: int, y: int): int { if((x^y) >= 0 || x == 0) return x/y; return (x+((y>>30)|1))/y-1; } smuldivmod(x: int, y: int, z: int): (int, int) { mod: int; vx: int; if(x == 0 || y == 0) return (0, 0); vx = x; vx *= y; mod = vx % z; if(mod < 0) mod += z; if((vx < 0) == (z < 0)) return (vx/z, mod); return (-((-vx)/z), mod); } xscan(dst: ref Image, seg: array of ref Seg, segtab: array of ref Seg, nseg: int, wind: int, src: ref Image, spt: Point, zstate: ref Zstate, dc: int, dx: int, dy: int, fixshift: int) { y, maxy, x, x2, onehalf: int; ep, next, p, q, s: int; n, i, iy, cnt, ix, ix2, minx, maxx, zinc, k, zv: int; pt: Point; sp: ref Seg; er := (abs(dx)+abs(dy)+1)/2; zr := zstate.r; xlen := zstate.xlen; zbuf0 := zstate.zbuf0; zbuf1 := zstate.zbuf1; s = 0; p = 0; for(i=0; i sp.p1.y) { pt = sp.p0; sp.p0 = sp.p1; sp.p1 = pt; sp.d = -sp.d; } sp.num = sp.p1.x - sp.p0.x; sp.den = sp.p1.y - sp.p0.y; sp.dz = sdiv(sp.num, sp.den) << fixshift; sp.dzrem = mod(sp.num, sp.den) << fixshift; sp.dz += sdiv(sp.dzrem, sp.den); sp.dzrem = mod(sp.dzrem, sp.den); p++; s++; } n = p; if(n == 0) return; seg[p] = nil; qsortycompare(seg, p); 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; k = (iy-zr.min.y)*xlen; zv = dc+iy*dy; ep = next = 0; while(y= sp.den) { sp.z++; sp.zerr -= sp.den; if(sp.zerr < 0 || sp.zerr >= sp.den) sys->print("bad ratzerr1: %d den %d dzrem %d\n", sp.zerr, sp.den, sp.dzrem); } seg[q] = sp; q++; } for(p = next; seg[p] != nil; p++) { sp = seg[p]; if(sp.p0.y >= y) break; if(sp.p1.y < y) continue; sp.z = sp.p0.x; (zinc, sp.zerr) = smuldivmod(y - sp.p0.y, sp.num, sp.den); sp.z += zinc; if(sp.zerr < 0 || sp.zerr >= sp.den) sys->print("bad ratzerr2: %d den %d ratdzrem %d\n", sp.zerr, sp.den, sp.dzrem); seg[q] = sp; q++; } ep = q; next = p; if(ep == 0) { if(seg[next] == nil) break; iy = (seg[next].p0.y + onehalf) >> fixshift; y = (iy << fixshift) + onehalf; k = (iy-zr.min.y)*xlen; zv = dc+iy*dy; continue; } zsort(seg, ep); for(p = 0; p < ep; p++) { sp = seg[p]; cnt = 0; x = sp.z; ix = (x + onehalf) >> fixshift; if(ix >= maxx) break; if(ix < minx) ix = minx; cnt += sp.d; p++; sp = seg[p]; for(;;) { if(p == ep) { sys->print("xscan: fill to infinity"); return; } cnt += sp.d; if((cnt&wind) == 0) break; p++; sp = seg[p]; } x2 = sp.z; ix2 = (x2 + onehalf) >> fixshift; if(ix2 <= minx) continue; if(ix2 > maxx) ix2 = maxx; filllinez(dst, ix, ix2, iy, zv+ix*dx, er, dx, k+ix-zr.min.x, zbuf0, zbuf1, src, spt); } y += (1< seg[p+1].z) { s = seg[p]; seg[p] = seg[p+1]; seg[p+1] = s; done = 0; } } } while(!done); } else { q = ep-1; for(p = 0; p < q; p++) { if(seg[p].z > seg[p+1].z) { qsortzcompare(seg, ep); break; } } } } ycompare(s0: ref Seg, s1: ref Seg): int { y0, y1: int; y0 = s0.p0.y; y1 = s1.p0.y; if(y0 < y1) return -1; if(y0 == y1) return 0; return 1; } zcompare(s0: ref Seg, s1: ref Seg): int { z0, z1: int; z0 = s0.z; z1 = s1.z; if(z0 < z1) return -1; if(z0 == z1) return 0; return 1; } qsortycompare(a : array of ref Seg, n : int) { i, j : int; t : ref Seg; while(n > 1) { i = n>>1; t = a[0]; a[0] = a[i]; a[i] = t; i = 0; j = n; for(;;) { do i++; while(i < n && ycompare(a[i], a[0]) < 0); do j--; while(j > 0 && ycompare(a[j], a[0]) > 0); if(j < i) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[0]; a[0] = a[j]; a[j] = t; n = n-j-1; if(j >= n) { qsortycompare(a, j); a = a[j+1:]; } else { qsortycompare(a[j+1:], n); n = j; } } } qsortzcompare(a : array of ref Seg, n : int) { i, j : int; t : ref Seg; while(n > 1) { i = n>>1; t = a[0]; a[0] = a[i]; a[i] = t; i = 0; j = n; for(;;) { do i++; while(i < n && zcompare(a[i], a[0]) < 0); do j--; while(j > 0 && zcompare(a[j], a[0]) > 0); if(j < i) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[0]; a[0] = a[j]; a[j] = t; n = n-j-1; if(j >= n) { qsortzcompare(a, j); a = a[j+1:]; } else { qsortzcompare(a[j+1:], n); n = j; } } } abs(n: int): int { if(n < 0) return -n; return n; }