Apex
Every tower points at something it will never reach.
Log in to post a comment.
Canvas.setpenopacity(0.75);
const turtle = new Turtle();
turtle.penup();
// CAD-like hidden line removal
// No scanline, no painter, no 2D clipper
// @ge1doot - March 13, 2026
// --------------------- Math -----------------------
const math = {
v2: (x = 0, y = 0) => {
return { x, y };
},
v3: (x = 0, y = 0, z = 0) => {
return { x, y, z };
},
set3: (o, x, y, z) => {
o.x = x;
o.y = y;
o.z = z;
return o;
},
copy3: (o, a) => {
o.x = a.x;
o.y = a.y;
o.z = a.z;
return o;
},
fromA3: (o, a) => {
o.x = a[0];
o.y = a[1];
o.z = a[2];
return o;
},
sub3: (o, a, b) => {
o.x = a.x - b.x;
o.y = a.y - b.y;
o.z = a.z - b.z;
return o;
},
lerp3: (o, a, b, t) => {
o.x = a.x + (b.x - a.x) * t;
o.y = a.y + (b.y - a.y) * t;
o.z = a.z + (b.z - a.z) * t;
return o;
},
dot3: (a, b) => a.x * b.x + a.y * b.y + a.z * b.z,
cross3: (o, a, b) => {
o.x = a.y * b.z - a.z * b.y;
o.y = a.z * b.x - a.x * b.z;
o.z = a.x * b.y - a.y * b.x;
return o;
},
norm3: (o, a) => {
const l = Math.hypot(a.x, a.y, a.z) || 1;
const s = 1 / l;
o.x = a.x * s;
o.y = a.y * s;
o.z = a.z * s;
},
sqDist3: (a, b) => {
const dx = b.x - a.x,
dy = b.y - a.y,
dz = b.z - a.z;
return dx * dx + dy * dy + dz * dz;
},
planeDist: (n, q, p) => n.x * (p.x - q.x) + n.y * (p.y - q.y) + n.z * (p.z - q.z),
planeEval: (plane, p) => plane[0] * p.x + plane[1] * p.y + plane[2] * p.z + plane[3],
transform3: (o, p, m) => {
const x = p.x, y = p.y, z = p.z;
o.x = m[0] * x + m[4] * y + m[8] * z + m[12];
o.y = m[1] * x + m[5] * y + m[9] * z + m[13];
o.z = m[2] * x + m[6] * y + m[10] * z + m[14];
return o;
},
aabb3: () => [1e9, 1e9, 1e9, -1e9, -1e9, -1e9],
aabb3Add: (a, v) => {
if (v.x < a[0]) a[0] = v.x;
if (v.x > a[3]) a[3] = v.x;
if (v.y < a[1]) a[1] = v.y;
if (v.y > a[4]) a[4] = v.y;
if (v.z < a[2]) a[2] = v.z;
if (v.z > a[5]) a[5] = v.z;
},
aabb3Union: (a, b) => {
if (b[0] < a[0]) a[0] = b[0];
if (b[3] > a[3]) a[3] = b[3];
if (b[1] < a[1]) a[1] = b[1];
if (b[4] > a[4]) a[4] = b[4];
if (b[2] < a[2]) a[2] = b[2];
if (b[5] > a[5]) a[5] = b[5];
},
aabb3Overlap: (a, b) => !(
a[3] < b[0] ||
a[0] > b[3] ||
a[4] < b[1] ||
a[1] > b[4] ||
a[5] < b[2] ||
a[2] > b[5]
),
aabb3Extends: a => [a[3] - a[0], a[4] - a[1], a[5] - a[2]],
aabb2: () => [1e9, 1e9, -1e9, -1e9],
aabb2Add: (a, p) => {
const x = p.x, y = p.y;
if (x < a[0]) a[0] = x;
if (x > a[2]) a[2] = x;
if (y < a[1]) a[1] = y;
if (y > a[3]) a[3] = y;
},
aabb2Union: (a, b) => {
if (b[0] < a[0]) a[0] = b[0];
if (b[2] > a[2]) a[2] = b[2];
if (b[1] < a[1]) a[1] = b[1];
if (b[3] > a[3]) a[3] = b[3];
},
aabb2Overlap: (a, b) => !(a[2] < b[0] || a[0] > b[2] || a[3] < b[1] || a[1] > b[3]),
segIntersectPoint: (o, a, b, c, d) => {
const ax = a.x, ay = a.y, bx = b.x, by = b.y;
const cx = c.x, cy = c.y, dx = d.x, dy = d.y;
const rpx = bx - ax, rpy = by - ay;
const spx = dx - cx, spy = dy - cy;
const dn = rpx * spy - rpy * spx;
if (dn > -1e-12 && dn < 1e-12) return false;
const qpx = cx - ax, qpy = cy - ay;
const t = (qpx * spy - qpy * spx) / dn;
const u = (qpx * rpy - qpy * rpx) / dn;
if (t < 0 || t > 1 || u < 0 || u > 1) return false;
o.x = ax + rpx * t;
o.y = ay + rpy * t;
return true;
},
quadCenter: (a, b, c, d) => {
return {
x: 0.25 * (a.x + b.x + c.x + d.x),
y: 0.25 * (a.y + b.y + c.y + d.y),
z: 0.25 * (a.z + b.z + c.z + d.z)
};
},
quadNormal: (a, b, c) => {
const abx = b.x - a.x, aby = b.y - a.y, abz = b.z - a.z;
const acx = c.x - a.x, acy = c.y - a.y, acz = c.z - a.z;
const nx = aby * acz - abz * acy,
ny = abz * acx - abx * acz,
nz = abx * acy - aby * acx;
const l = 1 / Math.sqrt(nx * nx + ny * ny + nz * nz) + 1e-12;
return { x: nx * l, y: ny * l, z: nz * l };
}
};
// --------------------- Camera -----------------------
const camera = function () {
const { v3, set3, sub3, dot3, cross3, norm3, fromA3 } = math;
const position = v3(),
cu = v3(),
cv = v3(),
cw = v3();
return class Camera {
static position = position;
static zoom = 1;
static zNear = 1e-6;
static planes = [];
static #updatePlanes(f) {
const iz = 1 / this.zoom;
this.planes = [
[+1, +0, -f[0] * iz, 0],
[-1, +0, +f[1] * iz, 0],
[+0, +1, +f[3] * iz, 0],
[+0, -1, -f[2] * iz, 0],
[+0, +0, 1, -this.zNear],
];
}
static setView(opts) {
this.zoom = opts.zoom ?? 1;
this.zNear = opts.zNear ?? 1e-6;
fromA3(this.position, opts.position);
const roll = opts.roll ?? 0;
const look = fromA3(v3(), opts.lookAt);
norm3(cw, sub3(cw, look, this.position));
norm3(
cu,
cross3(
cu,
cw,
set3(v3(), Math.sin(roll), Math.cos(roll), 0),
),
);
cross3(cv, cu, cw);
this.#updatePlanes(opts.frustrum ?? [-100, 100, -100, 100]);
return this;
}
static toCamera(o, p) {
sub3(o, p, this.position);
return set3(
o,
dot3(o, cu),
dot3(o, cv),
dot3(o, cw),
);
}
static perspective(o, c) {
if (c.z < this.zNear) return null;
const invZ = this.zoom / c.z;
o.x = c.x * invZ;
o.y = -c.y * invZ;
o.z = c.z;
return o;
}
static projectWorld(o, p) {
this.toCamera(o, p);
return this.perspective(o, o);
}
};
}();
// --------------------- BVH -----------------------
const bvh = function () {
const { v3, aabb3, aabb3Add, aabb3Union, aabb3Overlap, aabb3Extends } = math;
const ro = [0, 0, 0], rd = [0, 0, 0];
return class BVH {
static #rayAabbHit (ro, rd, aabb, tMax) {
let t0 = 0, t1 = tMax;
for (let axis = 0; axis < 3; axis++) {
const o = ro[axis], d = rd[axis];
const minv = aabb[axis], maxv = aabb[axis + 3];
if (Math.abs(d) < 1e-16) {
if (o < minv || o > maxv) return -1;
continue;
}
const inv = 1 / d;
let tNear = (minv - o) * inv;
let tFar = (maxv - o) * inv;
if (tNear > tFar) {
const tmp = tNear;
tNear = tFar;
tFar = tmp;
}
if (tNear > t0) t0 = tNear;
if (tFar < t1) t1 = tFar;
if (t1 < t0) return -1;
}
return t0;
}
static #rayTriHit (ro, rd, T) {
const a = T.a, b = T.b, c = T.c;
const e1x = b.x - a.x, e1y = b.y - a.y, e1z = b.z - a.z;
const e2x = c.x - a.x, e2y = c.y - a.y, e2z = c.z - a.z;
const px = rd[1] * e2z - rd[2] * e2y;
const py = rd[2] * e2x - rd[0] * e2z;
const pz = rd[0] * e2y - rd[1] * e2x;
const det = e1x * px + e1y * py + e1z * pz;
if (det > -1e-10 && det < 1e-10) return -1;
const invDet = 1 / det;
const tx = ro[0] - a.x, ty = ro[1] - a.y, tz = ro[2] - a.z;
const u = (tx * px + ty * py + tz * pz) * invDet;
if (u < 0 || u > 1) return -1;
const qx = ty * e1z - tz * e1y;
const qy = tz * e1x - tx * e1z;
const qz = tx * e1y - ty * e1x;
const v = (rd[0] * qx + rd[1] * qy + rd[2] * qz) * invDet;
if (v < 0 || u + v > 1) return -1;
const t = (e2x * qx + e2y * qy + e2z * qz) * invDet;
return t > 0 ? t : -1;
}
static collectSegSplits (bvh, seg, o) {
const p0 = seg.p0, p1 = seg.p1;
const tris = bvh.tris, idx = bvh.idx;
ro[0] = p0.x;
ro[1] = p0.y;
ro[2] = p0.z;
rd[0] = p1.x - p0.x;
rd[1] = p1.y - p0.y;
rd[2] = p1.z - p0.z;
const segAabb = aabb3();
aabb3Add(segAabb, p0);
aabb3Add(segAabb, p1);
const stack = [bvh.root];
while (stack.length) {
const node = stack.pop();
if (!aabb3Overlap(segAabb, node.aabb)) continue;
if (!node.left) {
for (let i = node.i0; i < node.i1; i++) {
const T = tris[idx[i]];
if (seg.type === 0) {
if (T.volumeId === seg.volumeId) continue;
} else {
if (T.faceId === seg.faceId || T.faceId === seg.clipFaceId)
continue;
}
const t = this.#rayTriHit(ro, rd, T);
if (t > 1e-6 && t < 1 - 1e-6) o.push(t);
}
continue;
}
stack.push(node.left);
stack.push(node.right);
}
}
static build (tris, leafSize = 6) {
const idx = new Int32Array(tris.length);
for (let i = 0; i < tris.length; i++) {
const T = tris[i];
T.aabb = aabb3();
aabb3Add(T.aabb, T.a);
aabb3Add(T.aabb, T.b);
aabb3Add(T.aabb, T.c);
T.centroid = v3(
(T.a.x + T.b.x + T.c.x) / 3,
(T.a.y + T.b.y + T.c.y) / 3,
(T.a.z + T.b.z + T.c.z) / 3,
);
idx[i] = i;
}
const buildNode = (i0, i1) => {
const count = i1 - i0;
const aabb = aabb3();
for (let i = i0; i < i1; i++) aabb3Union(aabb, tris[idx[i]].aabb);
if (count <= leafSize)
return { aabb, i0, i1, left: null, right: null };
const bb = aabb3();
for (let i = i0; i < i1; i++) {
const c = tris[idx[i]].centroid;
aabb3Add(bb, c);
}
const [ex, ey, ez] = aabb3Extends(bb);
let axis = 0;
if (ey > ex && ey >= ez) axis = 1;
else if (ez > ex && ez >= ey) axis = 2;
const mid = (i0 + i1) >> 1;
const key = i => {
const c = tris[idx[i]].centroid;
return axis === 0 ? c.x : axis === 1 ? c.y : c.z;
}
const sortRange = (lo, hi) => {
const stack = [lo, hi];
while (stack.length) {
const r = stack.pop(),
l = stack.pop();
if (l >= r) continue;
let i = l,
j = r;
const pivot = key((l + r) >> 1);
while (i <= j) {
while (key(i) < pivot) i++;
while (key(j) > pivot) j--;
if (i <= j) {
const t = idx[i];
idx[i] = idx[j];
idx[j] = t;
i++;
j--;
}
}
if (j - l > r - i) {
if (l < j) stack.push(l, j);
if (i < r) stack.push(i, r);
} else {
if (i < r) stack.push(i, r);
if (l < j) stack.push(l, j);
}
}
}
sortRange(i0, i1 - 1);
return {
aabb,
i0,
i1,
left: buildNode(i0, mid),
right: buildNode(mid, i1),
};
}
return { root: buildNode(0, idx.length), idx, tris };
}
static rayNearest (bvh, ro, rd, tMax, seg) {
let best = tMax;
const tris = bvh.tris, idx = bvh.idx;
const stack = [bvh.root], mode = seg.type;
const volumeId = seg.volumeId, faceId = seg.faceId, clipFaceId = seg.clipFaceId;
while (stack.length) {
const node = stack.pop();
const tBox = this.#rayAabbHit(ro, rd, node.aabb, best);
if (tBox < 0) continue;
if (!node.left) {
for (let i = node.i0; i < node.i1; i++) {
const T = tris[idx[i]];
if (mode === 0 && T.volumeId === volumeId) continue;
if (
mode === 2 &&
(T.faceId === faceId || T.faceId === clipFaceId)
)
continue;
const t = this.#rayTriHit(ro, rd, T);
if (t > 0 && t < best) best = t;
}
continue;
}
const l = node.left, r = node.right;
const tl = this.#rayAabbHit(ro, rd, l.aabb, best);
const tr = this.#rayAabbHit(ro, rd, r.aabb, best);
if (tl >= 0 && tr >= 0) {
if (tl < tr) {
stack.push(r);
stack.push(l);
} else {
stack.push(l);
stack.push(r);
}
} else if (tl >= 0) {
stack.push(l);
} else if (tr >= 0) {
stack.push(r);
}
}
return best;
}
};
}();
// --------------------- Intersections -----------------------
const intersections = function () {
const { v3, lerp3, sqDist3, planeDist } = math;
return class Intersections {
static #clipPolygon (poly, clipFace) {
const o = [];
const n = clipFace.normal;
const q = clipFace.quad[0];
for (let i = 0; i < poly.length; i++) {
const a = poly[i];
const b = poly[(i + 1) % poly.length];
const da = planeDist(n, q, a);
const db = planeDist(n, q, b);
this.addSeg(o, a, b, da, db, da <= 1e-9, db <= 1e-9);
}
return o;
}
static #clipFaceByBox (face, box, faces) {
let poly = face.quad.slice();
for (let i = 0; i < 6; i++) {
const clipFace = faces[box.faceIds[i]];
poly = this.#clipPolygon(poly, clipFace);
if (poly.length === 0) return poly;
}
return poly;
}
static #pack (a) {
const r = (s) => Math.round(s * 1e4);
const x = BigInt(r(a.x) & 0xfffff);
const y = BigInt(r(a.y) & 0xfffff);
const z = BigInt(r(a.z) & 0xfffff);
return (x << 40n) | (y << 20n) | z;
}
static #makeSegKey (a, b) {
const A = this.#pack(a);
const B = this.#pack(b);
return A < B ? (A << 60n) | B : (B << 60n) | A;
}
static #findClipFaceId (p0, p1, box, faces) {
for (let i = 0; i < 6; i++) {
const F = faces[box.faceIds[i]];
if (
Math.abs(planeDist(F.normal, F.quad[0], p0)) <= 1e-5 &&
Math.abs(planeDist(F.normal, F.quad[0], p1)) <= 1e-5
)
return F.faceId;
}
return -1;
}
static #emitFaceClips (face, box, faces, oSegs, seen) {
const poly = this.#clipFaceByBox(face, box, faces);
if (poly.length < 3) return;
for (let i = 0; i < poly.length; i++) {
const p0 = poly[i];
const p1 = poly[(i + 1) % poly.length];
if (sqDist3(p0, p1) < 1e-9) continue;
const clipFaceId = this.#findClipFaceId(p0, p1, box, faces);
if (clipFaceId < 0) continue;
const key = this.#makeSegKey(p0, p1);
if (seen.has(key)) continue;
seen.set(key, true);
oSegs.push({
p0,
p1,
volumeId: face.volumeId,
type: 2,
f0: -1,
f1: -1,
faceId: face.faceId,
clipFaceId,
});
}
}
static addSeg (o, a, b, da, db, aIn, bIn) {
if (aIn) o.push(a);
if (aIn !== bIn) {
const d = db - da;
if (Math.abs(d) > 1e-12) o.push(lerp3(v3(), a, b, -da / d));
}
}
static emitBoxesSegs (boxA, boxB, faces, oSegs) {
const seen = new Map();
for (let i = 0; i < 6; i++) {
const faceA = faces[boxA.faceIds[i]];
this.#emitFaceClips(faceA, boxB, faces, oSegs, seen);
}
for (let i = 0; i < 6; i++) {
const faceB = faces[boxB.faceIds[i]];
this.#emitFaceClips(faceB, boxA, faces, oSegs, seen);
}
}
};
}();
// --------------------- HLR -----------------------
const hlr = function () {
const {
v2,
v3,
lerp3,
sub3,
dot3,
aabb2,
aabb2Add,
aabb2Union,
aabb2Overlap,
planeEval,
segIntersectPoint,
} = math;
const tmp = v3();
const faceFront = (cam, center, normal) => {
sub3(tmp, cam.position, center);
return dot3(tmp, normal) > 0;
}
const gSize = 64, BB = aabb2();
let cam = null,
tris = null,
segs = null,
faces = null,
bvhOcc = null,
bvhSplit = null,
faceFrontMap = null,
faceEdges2D = null,
splitGrid = null,
splitSeen = null,
splitStamp = 1,
splitCandidates = null,
edgeIndex = 0,
walkTime = 0;
const c0 = v3(), c1 = v3(), ca = v3(), cb = v3(), cc = v3();
const PA = v3(), PB = v3(), WA = v3(), WB = v3(), M = v3(), mc = v3();
const rayOrig = [0, 0, 0], rayDir = [0, 0, 0];
const proj = { PA, PB }, seg = [0, 0, 0, 0];
return class HLR {
static #buildFaceFrontMap () {
const map = new Int8Array(
faces.length ? faces[faces.length - 1].faceId + 1 : 0,
);
for (let i = 0; i < faces.length; i++) {
const F = faces[i];
map[F.faceId] = faceFront(cam, F.center, F.normal) ? 1 : 0;
}
return map;
}
static #clipSegToGridRect (seg, a, b) {
let t0 = 0, t1 = 1;
const ax = a.x, ay = a.y, bx = b.x, by = b.y;
const dx = bx - ax, dy = by - ay;
if (Math.abs(dx) <= 1e-12) {
if (ax < BB[0] || ax > BB[2]) return false;
} else {
let ta = (BB[0] - ax) / dx;
let tb = (BB[2] - ax) / dx;
if (ta > tb) {
const t = ta;
ta = tb;
tb = t;
}
if (ta > t0) t0 = ta;
if (tb < t1) t1 = tb;
if (t1 < t0) return false;
}
if (Math.abs(dy) <= 1e-12) {
if (ay < BB[1] || ay > BB[3]) return false;
} else {
let ta = (BB[1] - ay) / dy;
let tb = (BB[3] - ay) / dy;
if (ta > tb) {
const t = ta;
ta = tb;
tb = t;
}
if (ta > t0) t0 = ta;
if (tb < t1) t1 = tb;
if (t1 < t0) return false;
}
seg[0] = ax + dx * t0;
seg[1] = ay + dy * t0;
seg[2] = ax + dx * t1;
seg[3] = ay + dy * t1;
return true;
}
static #traverseGrid (a, b, onCell) {
if (!this.#clipSegToGridRect(seg, a, b)) return;
let gx0 = (seg[0] - BB[0]) * BB[4];
let gy0 = (seg[1] - BB[1]) * BB[5];
let gx1 = (seg[2] - BB[0]) * BB[4];
let gy1 = (seg[3] - BB[1]) * BB[5];
const limit = gSize - 1e-9;
if (gx0 < 0) gx0 = 0;
else if (gx0 > limit) gx0 = limit;
if (gy0 < 0) gy0 = 0;
else if (gy0 > limit) gy0 = limit;
if (gx1 < 0) gx1 = 0;
else if (gx1 > limit) gx1 = limit;
if (gy1 < 0) gy1 = 0;
else if (gy1 > limit) gy1 = limit;
const dgx = gx1 - gx0, dgy = gy1 - gy0;
const stepX = dgx > 1e-12 ? 1 : dgx < -1e-12 ? -1 : 0;
const stepY = dgy > 1e-12 ? 1 : dgy < -1e-12 ? -1 : 0;
let ix = gx0 | 0, iy = gy0 | 0;
let ix1 = gx1 | 0, iy1 = gy1 | 0;
if (stepX < 0 && Math.abs(gx0 - ix) <= 1e-12 && ix > 0) ix--;
if (stepY < 0 && Math.abs(gy0 - iy) <= 1e-12 && iy > 0) iy--;
if (stepX < 0 && Math.abs(gx1 - ix1) <= 1e-12 && ix1 > 0) ix1--;
if (stepY < 0 && Math.abs(gy1 - iy1) <= 1e-12 && iy1 > 0) iy1--;
const tDeltaX = stepX ? 1 / Math.abs(dgx) : 1e30;
const tDeltaY = stepY ? 1 / Math.abs(dgy) : 1e30;
let tMaxX =
stepX > 0
? (ix + 1 - gx0) / dgx
: stepX < 0
? (gx0 - ix) / -dgx
: 1e30;
let tMaxY =
stepY > 0
? (iy + 1 - gy0) / dgy
: stepY < 0
? (gy0 - iy) / -dgy
: 1e30;
const gmax = gSize - 1;
onCell(ix, iy);
while (ix !== ix1 || iy !== iy1) {
if (tMaxX < tMaxY - 1e-12) {
ix += stepX;
if (ix < 0 || ix > gmax || iy < 0 || iy > gmax) break;
onCell(ix, iy);
tMaxX += tDeltaX;
} else if (tMaxY < tMaxX - 1e-12) {
iy += stepY;
if (ix < 0 || ix > gmax || iy < 0 || iy > gmax) break;
onCell(ix, iy);
tMaxY += tDeltaY;
} else {
const nx = ix + stepX,
ny = iy + stepY;
if (stepX && nx >= 0 && nx <= gmax) onCell(nx, iy);
if (stepY && ny >= 0 && ny <= gmax) onCell(ix, ny);
ix = nx;
iy = ny;
if (ix < 0 || ix > gmax || iy < 0 || iy > gmax) break;
onCell(ix, iy);
tMaxX += tDeltaX;
tMaxY += tDeltaY;
}
}
}
static #querySplitGrid (a, b, oIds) {
const qbb = aabb2();
aabb2Add(qbb, a);
aabb2Add(qbb, b);
const stamp = splitStamp++;
let n = 0;
this.#traverseGrid(a, b, (ix, iy) => {
const cell = splitGrid[ix + iy * gSize];
for (let k = 0; k < cell.length; k++) {
const id = cell[k];
if (splitSeen[id] === stamp) continue;
splitSeen[id] = stamp;
const E = faceEdges2D[id];
if (aabb2Overlap(qbb, E.bb)) oIds[n++] = id;
}
});
return n;
}
static #clipTriCam (a, b, c, zNear, o, volumeId, faceId) {
const poly = this.#clipPolyByPlane(
[v3(a.x, a.y, a.z), v3(b.x, b.y, b.z), v3(c.x, c.y, c.z)],
[0, 0, 1, -zNear],
);
if (poly.length < 3) return;
const p0 = poly[0];
for (let i = 1; i < poly.length - 1; i++) {
o.push({
a: p0,
b: poly[i],
c: poly[i + 1],
volumeId,
faceId,
});
}
}
static #buildSplitGrid () {
const rawEdges = [];
const c0 = v3(), c1 = v3();
const c2 = v3(), c3 = v3();
for (let i = 0; i < faces.length; i++) {
const F = faces[i];
if (!faceFrontMap[F.faceId]) continue;
const q = F.quad;
cam.toCamera(c0, q[0]);
cam.toCamera(c1, q[1]);
cam.toCamera(c2, q[2]);
cam.toCamera(c3, q[3]);
const poly = this.#clipPolyCamFrustum([c0, c1, c2, c3]);
if (poly.length < 3) continue;
const pts = [];
for (let j = 0; j < poly.length; j++) {
const p = v3();
if (!cam.perspective(p, poly[j])) continue;
pts.push(p);
}
if (pts.length < 3) continue;
for (let e = 0; e < pts.length; e++) {
const a = pts[e];
const b = pts[(e + 1) % pts.length];
const bb = aabb2();
aabb2Add(bb, a);
aabb2Add(bb, b);
rawEdges.push({
a,
b,
bb,
volumeId: F.volumeId,
});
aabb2Union(BB, bb);
}
}
faceEdges2D = rawEdges;
const gridCellCount = gSize * gSize;
splitGrid = Array.from({ length: gridCellCount }, () => []);
const dx = BB[2] - BB[0], dy = BB[3] - BB[1];
const padX = Math.max(1e-6, dx * 0.01);
const padY = Math.max(1e-6, dy * 0.01);
BB[0] -= padX;
BB[1] -= padY;
BB[2] += padX;
BB[3] += padY;
BB[4] = gSize / Math.max(1e-6, dx);
BB[5] = gSize / Math.max(1e-6, dy);
for (let i = 0; i < faceEdges2D.length; i++) {
const E = faceEdges2D[i];
this.#traverseGrid(E.a, E.b, (ix, iy) => {
splitGrid[ix + iy * gSize].push(i);
});
}
splitStamp = 1;
splitSeen = new Int32Array(faceEdges2D.length);
splitCandidates = new Int32Array(faceEdges2D.length);
}
static #solveEdges (c0, c1, zoom, p) {
const Xn = p.x / zoom, Yn = -p.y / zoom;
const x0 = c0.x, y0 = c0.y, z0 = c0.z;
const dx = c1.x - x0, dy = c1.y - y0, dz = c1.z - z0;
const dnX = dx - Xn * dz, dnY = dy - Yn * dz;
const absX = Math.abs(dnX), absY = Math.abs(dnY);
if (absX > absY) {
if (absX <= 1e-10) return null;
return (Xn * z0 - x0) / dnX;
}
if (absY <= 1e-10) return null;
return (Yn * z0 - y0) / dnY;
}
static #projectInterval (edge, sA, sB) {
lerp3(WA, edge.p0, edge.p1, sA);
if (!cam.projectWorld(PA, WA)) return null;
lerp3(WB, edge.p0, edge.p1, sB);
if (!cam.projectWorld(PB, WB)) return null;
return proj;
}
static #pointVisible (edge, s) {
lerp3(M, edge.p0, edge.p1, s);
cam.toCamera(mc, M);
const mx = mc.x, my = mc.y, mz = mc.z;
if (mz < cam.zNear) return false;
const d = Math.sqrt(mx * mx + my * my + mz * mz);
const invD = 1 / d;
rayDir[0] = mx * invD;
rayDir[1] = my * invD;
rayDir[2] = mz * invD;
const tMax = d - d * 1e-5;
const best = bvh.rayNearest(
bvhOcc,
rayOrig,
rayDir,
tMax > 0 ? tMax : 0,
edge,
);
return best >= tMax;
}
static #emitVisibleInterval (edge, sA, sB, turtle) {
if (sB <= sA + 1e-6) return;
const p = this.#projectInterval(edge, sA, sB);
if (!p) return;
const sm = 0.5 * (sA + sB);
if (!this.#pointVisible(edge, sm)) return;
turtle.jump(p.PA.x, p.PA.y);
turtle.pendown();
turtle.goto(p.PB.x, p.PB.y);
}
static #clipPolyByPlane (poly, plane) {
const o = [];
for (let i = 0; i < poly.length; i++) {
const a = poly[i];
const b = poly[(i + 1) % poly.length];
const da = planeEval(plane, a);
const db = planeEval(plane, b);
intersections.addSeg(o, a, b, da, db, da >= -1e-9, db >= -1e-9);
}
return o;
}
static #clipPolyCamFrustum (poly) {
let o = poly;
const planes = cam.planes;
for (let i = 0; i < planes.length; i++) {
o = this.#clipPolyByPlane(o, planes[i]);
if (o.length === 0) return o;
}
return o;
}
static #clipSegRangeFrustum (c0, c1) {
let s0 = 0, s1 = 1;
const delta = sub3(v3(), c1, c0);
const planes = cam.planes;
for (let i = 0; i < planes.length; i++) {
const P = planes[i];
const f0 = planeEval(P, c0);
const fd = P[0] * delta.x + P[1] * delta.y + P[2] * delta.z;
if (Math.abs(fd) <= 1e-12) {
if (f0 < 0) return null;
continue;
}
const t = -f0 / fd;
if (fd > 0) {
if (t > s0) s0 = t;
} else {
if (t < s1) s1 = t;
}
if (s1 < s0) return null;
}
return [s0, s1];
}
static #processSeg (edge, turtle) {
if (edge.type === 0) {
if (!faceFrontMap[edge.f0] && !faceFrontMap[edge.f1]) return;
} else if (edge.type === 2) {
if (!faceFrontMap[edge.faceId] && !faceFrontMap[edge.clipFaceId])
return;
}
cam.toCamera(c0, edge.p0);
cam.toCamera(c1, edge.p1);
const range = this.#clipSegRangeFrustum(c0, c1);
if (!range) return;
const sLo = range[0], sHi = range[1];
if (sHi <= sLo + 1e-6) return;
lerp3(ca, c0, c1, sLo);
if (!cam.perspective(PA, ca)) return;
lerp3(cb, c0, c1, sHi);
if (!cam.perspective(PB, cb)) return;
const splits = [sLo, sHi];
const candCount = this.#querySplitGrid(PA, PB, splitCandidates);
const zoom = cam.zoom, vhit = v2();
for (let i = 0; i < candCount; i++) {
const E = faceEdges2D[splitCandidates[i]];
if (E.volumeId === edge.volumeId) continue;
const hit = segIntersectPoint(vhit, PA, PB, E.a, E.b);
if (!hit) continue;
let s = this.#solveEdges(c0, c1, zoom, vhit);
if (s === null) continue;
if (s < sLo - 1e-6 || s > sHi + 1e-6) continue;
if (s < sLo) s = sLo;
else if (s > sHi) s = sHi;
splits.push(s);
}
bvh.collectSegSplits(bvhSplit, edge, splits);
splits.sort((a, b) => a - b);
const ts = [];
let last = -1;
for (let i = 0; i < splits.length; i++) {
const t = splits[i];
if (i === 0 || t > last + 1e-6) {
ts.push(t);
last = t;
}
}
for (let i = 0; i < ts.length - 1; i++) {
const sA = ts[i],
sB = ts[i + 1];
if (sB <= sA + 1e-6) continue;
this.#emitVisibleInterval(edge, sA, sB, turtle);
}
}
static setScene (data) {
tris = data.tris;
segs = data.segs;
faces = data.faces;
return this;
}
static setCamera (nextCam) {
cam = nextCam;
return this;
}
static build () {
const t0 = performance.now();
faceFrontMap = this.#buildFaceFrontMap();
const occTris = [], zNear = cam.zNear;
for (let i = 0; i < tris.length; i++) {
const T = tris[i];
if (!faceFrontMap[T.faceId]) continue;
cam.toCamera(ca, T.a);
cam.toCamera(cb, T.b);
cam.toCamera(cc, T.c);
this.#clipTriCam(ca, cb, cc, zNear, occTris, T.volumeId, T.faceId);
}
bvhSplit = bvh.build(tris, 6);
bvhOcc = bvh.build(occTris, 6);
this.#buildSplitGrid();
edgeIndex = 0;
console.log("Build HLR:", performance.now() - t0, "ms");
return this;
}
static walk (turtle, batch) {
const t0 = performance.now();
for (let k = 0; k < batch && edgeIndex < segs.length; k++) {
this.#processSeg(segs[edgeIndex], turtle);
edgeIndex++;
}
const t1 = performance.now();
walkTime += t1 - t0;
const running = edgeIndex < segs.length;
if (!running) console.log("Walk Time:", walkTime, "ms");
return running;
}
};
}();
// --------------------- Scene module -----------------------
const scene = function () {
const {
v3,
transform3,
aabb3,
aabb3Add,
aabb3Overlap,
quadCenter,
quadNormal,
} = math;
const EDGE_IDX = [
[0, 1],
[1, 2],
[2, 3],
[3, 0],
[4, 5],
[5, 6],
[6, 7],
[7, 4],
[0, 4],
[1, 5],
[2, 6],
[3, 7],
];
const EDGE_FACES = [
[3, 5],
[0, 5],
[2, 5],
[1, 5],
[3, 4],
[0, 4],
[2, 4],
[1, 4],
[1, 3],
[0, 3],
[0, 2],
[1, 2],
];
let nextVolumeId = 0;
const tris = [], segs = [], faces = [], boxes = [];
return class SCENE {
static #emitBox (mat, volumeId) {
const kind = mat[18];
const c = 0.5, t = 0.001;
const cornersL =
kind === 1
? [
v3(-c, -c, -c),
v3(c, -c, -c),
v3(c, c, -c),
v3(-c, c, -c),
v3(-t, -t, c),
v3(t, -t, c),
v3(t, t, c),
v3(-t, t, c),
]
: [
v3(-c, -c, -c),
v3(c, -c, -c),
v3(c, c, -c),
v3(-c, c, -c),
v3(-c, -c, c),
v3(c, -c, c),
v3(c, c, c),
v3(-c, c, c),
];
const cornersW = cornersL.map((p) => transform3(v3(), p, mat));
const bbox = aabb3();
for (let i = 0; i < 8; i++) aabb3Add(bbox, cornersW[i]);
const quads = [
[1, 2, 6, 5],
[4, 7, 3, 0],
[3, 7, 6, 2],
[4, 0, 1, 5],
[5, 6, 7, 4],
[0, 3, 2, 1],
];
const faceIds = new Array(6);
for (let fi = 0; fi < 6; fi++) {
const q = quads[fi];
const a = cornersW[q[0]],
b = cornersW[q[1]];
const c = cornersW[q[2]],
d = cornersW[q[3]];
const faceId = volumeId * 6 + fi;
faceIds[fi] = faces.length;
faces.push({
faceId,
volumeId,
center: quadCenter(a, b, c, d),
normal: quadNormal(a, b, c),
quad: [a, b, c, d],
});
tris.push({ a, b, c, volumeId, faceId });
tris.push({ a, b: c, c: d, volumeId, faceId });
}
for (let i = 0; i < 12; i++) {
const e = EDGE_IDX[i],
fp = EDGE_FACES[i];
segs.push({
p0: cornersW[e[0]],
p1: cornersW[e[1]],
volumeId,
type: 0,
f0: volumeId * 6 + fp[0],
f1: volumeId * 6 + fp[1],
faceId: -1,
});
}
boxes.push({ volumeId, faceIds, aabb: bbox });
}
static clear () {
nextVolumeId = 0;
tris.length = 0;
segs.length = 0;
faces.length = 0;
boxes.length = 0;
}
static addBox (mat) {
const volumeId = nextVolumeId++;
this.#emitBox(mat, volumeId);
return volumeId;
}
static computeIntersections () {
const t0 = performance.now();
boxes.sort((a, b) => a.aabb[0] - b.aabb[0]);
for (let i = 0; i < boxes.length; i++) {
const a = boxes[i];
const axmax = a.aabb[3];
for (let j = i + 1; j < boxes.length; j++) {
const b = boxes[j];
if (b.aabb[0] > axmax) break;
if (aabb3Overlap(a.aabb, b.aabb)) intersections.emitBoxesSegs(a, b, faces, segs);
}
}
console.log("Compute Intersections:", performance.now() - t0, "ms");
}
static getData () {
return { tris, segs, faces };
}
};
}();
// --------------------- RNG -----------------------
function RNG(s = 1 + Math.floor(Math.random() * 2147483646)) {
let seed = s;
console.log("seed:", seed);
function next() {
seed = (seed * 16807) % 2147483647;
return (seed - 1) / 2147483646;
}
return next;
}
const random = RNG();
// -------------------- CFDG ----------------------
const CFDG = () => {
const setup = {
start: "start",
transform: {
s: 150,
},
maxDepth: 9,
};
const rules = {
start(s) {
rule.city(s, { ry: random() * 360 });
},
city(s) {
PYRAMID(s, { rx: -90, z: 0.2, s: [0.5, 0.5, 0.375] });
rule.split(s, { rx: 90, x: -0.5, y: -0.5 });
rule.split(s, { rx: 90, x: 0.5, y: -0.5 });
rule.split(s, { rx: 90, x: -0.5, y: 0.5 });
rule.split(s, { rx: 90, x: 0.5, y: 0.5 });
},
split(s) {
rule.split(s, {
x: -0.25,
y: 0.25,
s: [0.5, 0.5, 0.65],
rz: 90,
});
rule.split(s, {
x: 0.25,
y: -0.25,
s: [0.5, 0.5, 1],
rz: 90,
});
rule.split(s, {
x: -0.25,
y: -0.25,
s: [0.5, 0.5, 1.5],
rz: 90,
});
rule.block(s, { x: 0.25, y: 0.25 });
},
block: [
1,
(s) => {
CUBE(s, {
z: -0.05,
s: [0.48, 0.48, 0.1],
});
},
0.5,
(s) => {
rule.rad(s, {
z: -0.05,
s: [0.5, 0.5, 0.1],
});
CUBE(s, {
z: -0.06,
s: [0.25, 0.25, 0.12],
});
},
0.25,
(s) => {
rule.grid(s, {
z: -0.1,
s: [0.5, 0.5, 0.2],
});
},
],
rad(s) {
for (let i = -0.45; i <= 0.45; i += 0.2) {
CUBE(s, {
z: i,
s: [1, 1, 0.1],
});
}
},
grid(s) {
CUBE(s, { z: 0.5, s: [1, 1, 0.1] });
for (let x = -0.4; x <= 0.4; x += 0.2) {
for (let y = -0.4; y <= 0.4; y += 0.2) {
CUBE(s, { x: x, y: y, z: 0.5, s: [0.05, 0.05, 0.10001] });
}
}
},
};
let rule = {};
const shapes = [], stack = [], matrices = [];
const transforms = {
x(m, v) {
m[12] += m[0] * v;
m[13] += m[1] * v;
m[14] += m[2] * v;
},
y(m, v) {
m[12] += m[4] * v;
m[13] += m[5] * v;
m[14] += m[6] * v;
},
z(m, v) {
m[12] += m[8] * v;
m[13] += m[9] * v;
m[14] += m[10] * v;
},
s(m, v) {
const a = Array.isArray(v);
const x = a ? v[0] : v;
const y = a ? v[1] : x;
const z = a ? v[2] : x;
m[0] *= x;
m[1] *= x;
m[2] *= x;
m[4] *= y;
m[5] *= y;
m[6] *= y;
m[8] *= z;
m[9] *= z;
m[10] *= z;
},
rx(m, v) {
const rad = Math.PI * (v / 180);
const s = Math.sin(rad);
const c = Math.cos(rad);
const a10 = m[4];
const a11 = m[5];
const a12 = m[6];
const a20 = m[8];
const a21 = m[9];
const a22 = m[10];
m[4] = a10 * c + a20 * s;
m[5] = a11 * c + a21 * s;
m[6] = a12 * c + a22 * s;
m[8] = a10 * -s + a20 * c;
m[9] = a11 * -s + a21 * c;
m[10] = a12 * -s + a22 * c;
},
ry(m, v) {
const rad = Math.PI * (v / 180);
const s = Math.sin(rad);
const c = Math.cos(rad);
const a00 = m[0];
const a01 = m[1];
const a02 = m[2];
const a20 = m[8];
const a21 = m[9];
const a22 = m[10];
m[0] = a00 * c + a20 * -s;
m[1] = a01 * c + a21 * -s;
m[2] = a02 * c + a22 * -s;
m[8] = a00 * s + a20 * c;
m[9] = a01 * s + a21 * c;
m[10] = a02 * s + a22 * c;
},
rz(m, v) {
const rad = Math.PI * (v / 180);
const s = Math.sin(rad);
const c = Math.cos(rad);
const a00 = m[0];
const a01 = m[1];
const a02 = m[2];
const a10 = m[4];
const a11 = m[5];
const a12 = m[6];
m[0] = a00 * c + a10 * s;
m[1] = a01 * c + a11 * s;
m[2] = a02 * c + a12 * s;
m[4] = a00 * -s + a10 * c;
m[5] = a01 * -s + a11 * c;
m[6] = a02 * -s + a12 * c;
},
};
const SHAPE = (m, t, p) => {
const s = m.slice(0);
for (const c in t) transforms[c](s, t[c]);
s[18] = p;
matrices.push(s);
}
const CUBE = (m, t) => SHAPE(m, t, 0);
const PYRAMID = (m, t) => SHAPE(m, t, 1);
const transform = (s, p) => {
const m = s.slice(0);
m[16]++;
for (const c in p) transforms[c](m, p[c]);
return m;
}
const run = () => {
const t0 = performance.now();
matrices.length = 0;
runshapes(setup.start, setup.transform || {});
console.log("CFDG runtime:", performance.now() - t0, "ms");
return matrices;
}
const runshapes = (start, t) => {
console.clear();
const maxDepth = setup.maxDepth || 100;
matrices.length = 0;
stack.length = 0;
rule[start]([1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0], t);
do {
const s = stack.pop();
if (s !== undefined && s[16] <= maxDepth) {
shapes[s[17]](s);
}
} while (stack.length);
}
const singlerule = (i) => {
return (s, t) => {
s = transform(s, t);
if (!s) return;
s[17] = i;
stack.push(s);
};
}
const randomrule = (totalWeight, weight, index, len) => {
return (s, t) => {
s = transform(s, t);
if (!s) return;
let w = 0;
const r = random() * totalWeight;
for (let i = 0; i < len; i++) {
w += weight[i];
if (r <= w) {
s[17] = index[i];
stack.push(s);
return;
}
}
};
}
shapes.length = 0;
for (const namerule in rules) {
const r = rules[namerule];
if (Array.isArray(r)) {
let totalWeight = 0;
const weight = [];
const index = [];
for (let i = 0; i < r.length; i += 2) {
totalWeight += r[i];
shapes.push(r[i + 1]);
weight.push(r[i]);
index.push(shapes.length - 1);
}
rule[namerule] = randomrule(totalWeight, weight, index, index.length);
} else {
shapes.push(r);
rule[namerule] = singlerule(shapes.length - 1);
}
}
return { run };
}
const cfdg = CFDG();
const matrices = cfdg.run();
console.log("Boxes:", matrices.length);
// ---------------------------- Scene --------------------------------
for (const m of matrices) scene.addBox(m);
scene.computeIntersections();
const cam = camera.setView({
position: [random() * 200 - 100, 90, 0],
lookAt: [0, 0, 0],
frustrum: [-100, 100, -100, 100],
roll: 0,
zoom: 100,
zNear: 1e-6,
});
hlr.setScene(scene.getData());
hlr.setCamera(cam);
hlr.build();
function walk() {
const running = hlr.walk(turtle, 1);
return running;
}