BSP Hidden Lines
Hidden-line rendering done properly: BSP + 3D ray tests.
No screen-space clipping involved.
Log in to post a comment.
// TurtleToy
Canvas.setpenopacity(0.75);
const turtle = new Turtle();
turtle.pendown();
/* ============================================================
* BSP Tree (CSG-ish) + Hidden-Line "true 3D" (no 2D clipper)
* BSP adapted from C++ BSP Tree Demo (Bretton Wade, 1994-97)
* http://www.gamers.org/dhs/helpdocs/bsp_faq.html
* ============================================================ */
const Math3D = () => {
const FLOAT_ARRAY = Float64Array;
const MAT4_IDENTITY = new FLOAT_ARRAY([
1, 0, 0, 0,
0, 1, 0, 0,
0, 0, 1, 0,
0, 0, 0, 1,
]);
class Vec3 extends FLOAT_ARRAY {
constructor(x = 0, y = 0, z = 0) {
super(3);
this[0] = x;
this[1] = y;
this[2] = z;
}
copy(v) {
this.set(v);
return this;
}
get x() { return this[0]; }
set x(v) { this[0] = v; }
get y() { return this[1]; }
set y(v) { this[1] = v; }
get z() { return this[2]; }
set z(v) { this[2] = v; }
setXYZ(x, y, z) {
this[0] = x;
this[1] = y;
this[2] = z;
return this;
}
add(v) {
this[0] += v[0];
this[1] += v[1];
this[2] += v[2];
return this;
}
addFrom(a, b) {
this[0] = a[0] + b[0];
this[1] = a[1] + b[1];
this[2] = a[2] + b[2];
return this;
}
sub(v) {
this[0] -= v[0];
this[1] -= v[1];
this[2] -= v[2];
return this;
}
subFrom(a, b) {
this[0] = a[0] - b[0];
this[1] = a[1] - b[1];
this[2] = a[2] - b[2];
return this;
}
scale(s) {
this[0] *= s;
this[1] *= s;
this[2] *= s;
return this;
}
scaleFrom(a, s) {
this[0] = a[0] * s;
this[1] = a[1] * s;
this[2] = a[2] * s;
return this;
}
addMul(v, s) {
this[0] += v[0] * s;
this[1] += v[1] * s;
this[2] += v[2] * s;
return this;
}
addMulFrom(a, b, s) {
this[0] = a[0] + b[0] * s;
this[1] = a[1] + b[1] * s;
this[2] = a[2] + b[2] * s;
return this;
}
cross(v) {
return this.crossFrom(this, v);
}
crossFrom(a, b) {
const ax = a[0], ay = a[1], az = a[2];
const bx = b[0], by = b[1], bz = b[2];
this[0] = ay * bz - az * by;
this[1] = az * bx - ax * bz;
this[2] = ax * by - ay * bx;
return this;
}
transformPointMat4(m) {
const x = this[0], y = this[1], z = this[2];
this[0] = m[0] * x + m[4] * y + m[8] * z + m[12];
this[1] = m[1] * x + m[5] * y + m[9] * z + m[13];
this[2] = m[2] * x + m[6] * y + m[10] * z + m[14];
return this;
}
transformVectorMat4(m) {
const x = this[0], y = this[1], z = this[2];
this[0] = m[0] * x + m[4] * y + m[8] * z;
this[1] = m[1] * x + m[5] * y + m[9] * z;
this[2] = m[2] * x + m[6] * y + m[10] * z;
return this;
}
projectMat4(m) {
const x = this[0], y = this[1], z = this[2];
const px = m[0] * x + m[4] * y + m[8] * z + m[12];
const py = m[1] * x + m[5] * y + m[9] * z + m[13];
const pz = m[2] * x + m[6] * y + m[10] * z + m[14];
const pw = m[3] * x + m[7] * y + m[11] * z + m[15];
if (pw === 0) {
this[0] = Infinity;
this[1] = Infinity;
this[2] = Infinity;
return this;
}
const iw = 1 / pw;
this[0] = px * iw;
this[1] = py * iw;
this[2] = pz * iw;
return this;
}
lerp(v, t) {
this[0] += t * (v[0] - this[0]);
this[1] += t * (v[1] - this[1]);
this[2] += t * (v[2] - this[2]);
return this;
}
lerpFrom(a, b, t) {
const ax = a[0], ay = a[1], az = a[2];
this[0] = ax + t * (b[0] - ax);
this[1] = ay + t * (b[1] - ay);
this[2] = az + t * (b[2] - az);
return this;
}
normalize() {
const n = this.norm();
if (n > 0) this.scale(1 / n);
return this;
}
dot(v) {
return this[0] * v[0] + this[1] * v[1] + this[2] * v[2];
}
norm() {
const x = this[0], y = this[1], z = this[2];
return Math.sqrt(x * x + y * y + z * z);
}
}
class Vec4 extends FLOAT_ARRAY {
constructor(x = 0, y = 0, z = 0, w = 0) {
super(4);
this[0] = x;
this[1] = y;
this[2] = z;
this[3] = w;
}
setXYZW(x, y, z, w) {
this[0] = x;
this[1] = y;
this[2] = z;
this[3] = w;
return this;
}
copy(v) {
this.set(v);
return this;
}
get x() { return this[0]; }
set x(v) { this[0] = v; }
get y() { return this[1]; }
set y(v) { this[1] = v; }
get z() { return this[2]; }
set z(v) { this[2] = v; }
get w() { return this[3]; }
set w(v) { this[3] = v; }
scale(s) {
this[0] *= s;
this[1] *= s;
this[2] *= s;
this[3] *= s;
return this;
}
transformMat4(m) {
const x = this[0], y = this[1], z = this[2], w = this[3];
this[0] = m[0] * x + m[4] * y + m[8] * z + m[12] * w;
this[1] = m[1] * x + m[5] * y + m[9] * z + m[13] * w;
this[2] = m[2] * x + m[6] * y + m[10] * z + m[14] * w;
this[3] = m[3] * x + m[7] * y + m[11] * z + m[15] * w;
return this;
}
}
class Mat4 extends FLOAT_ARRAY {
constructor() {
super(16);
this[0] = 1;
this[5] = 1;
this[10] = 1;
this[15] = 1;
}
identity() {
this.set(MAT4_IDENTITY);
return this;
}
copy(a) {
this.set(a);
return this;
}
multiply(b) {
const a00 = this[0],
a01 = this[1],
a02 = this[2],
a03 = this[3];
const a10 = this[4],
a11 = this[5],
a12 = this[6],
a13 = this[7];
const a20 = this[8],
a21 = this[9],
a22 = this[10],
a23 = this[11];
const a30 = this[12],
a31 = this[13],
a32 = this[14],
a33 = this[15];
let b0, b1, b2, b3;
b0 = b[0];
b1 = b[1];
b2 = b[2];
b3 = b[3];
this[0] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[1] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[2] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[3] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
b0 = b[4];
b1 = b[5];
b2 = b[6];
b3 = b[7];
this[4] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[5] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[6] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[7] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
b0 = b[8];
b1 = b[9];
b2 = b[10];
b3 = b[11];
this[8] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[9] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[10] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[11] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
b0 = b[12];
b1 = b[13];
b2 = b[14];
b3 = b[15];
this[12] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[13] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[14] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[15] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
return this;
}
multiplyFrom(a, b) {
const a00 = a[0],
a01 = a[1],
a02 = a[2],
a03 = a[3];
const a10 = a[4],
a11 = a[5],
a12 = a[6],
a13 = a[7];
const a20 = a[8],
a21 = a[9],
a22 = a[10],
a23 = a[11];
const a30 = a[12],
a31 = a[13],
a32 = a[14],
a33 = a[15];
let b0 = b[0],
b1 = b[1],
b2 = b[2],
b3 = b[3];
this[0] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[1] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[2] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[3] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
b0 = b[4];
b1 = b[5];
b2 = b[6];
b3 = b[7];
this[4] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[5] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[6] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[7] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
b0 = b[8];
b1 = b[9];
b2 = b[10];
b3 = b[11];
this[8] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[9] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[10] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[11] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
b0 = b[12];
b1 = b[13];
b2 = b[14];
b3 = b[15];
this[12] = b0 * a00 + b1 * a10 + b2 * a20 + b3 * a30;
this[13] = b0 * a01 + b1 * a11 + b2 * a21 + b3 * a31;
this[14] = b0 * a02 + b1 * a12 + b2 * a22 + b3 * a32;
this[15] = b0 * a03 + b1 * a13 + b2 * a23 + b3 * a33;
return this;
}
rotateX(rad) {
const s = Math.sin(rad);
const c = Math.cos(rad);
const a10 = this[4],
a11 = this[5],
a12 = this[6],
a13 = this[7];
const a20 = this[8],
a21 = this[9],
a22 = this[10],
a23 = this[11];
this[4] = a10 * c + a20 * s;
this[5] = a11 * c + a21 * s;
this[6] = a12 * c + a22 * s;
this[7] = a13 * c + a23 * s;
this[8] = a20 * c - a10 * s;
this[9] = a21 * c - a11 * s;
this[10] = a22 * c - a12 * s;
this[11] = a23 * c - a13 * s;
return this;
}
rotateY(rad) {
const s = Math.sin(rad);
const c = Math.cos(rad);
const a00 = this[0],
a01 = this[1],
a02 = this[2],
a03 = this[3];
const a20 = this[8],
a21 = this[9],
a22 = this[10],
a23 = this[11];
this[0] = a00 * c - a20 * s;
this[1] = a01 * c - a21 * s;
this[2] = a02 * c - a22 * s;
this[3] = a03 * c - a23 * s;
this[8] = a00 * s + a20 * c;
this[9] = a01 * s + a21 * c;
this[10] = a02 * s + a22 * c;
this[11] = a03 * s + a23 * c;
return this;
}
rotateZ(rad) {
const s = Math.sin(rad);
const c = Math.cos(rad);
const a00 = this[0],
a01 = this[1],
a02 = this[2],
a03 = this[3];
const a10 = this[4],
a11 = this[5],
a12 = this[6],
a13 = this[7];
this[0] = a00 * c + a10 * s;
this[1] = a01 * c + a11 * s;
this[2] = a02 * c + a12 * s;
this[3] = a03 * c + a13 * s;
this[4] = a10 * c - a00 * s;
this[5] = a11 * c - a01 * s;
this[6] = a12 * c - a02 * s;
this[7] = a13 * c - a03 * s;
return this;
}
rotateXFrom(a, rad) { return this.copy(a).rotateX(rad); }
rotateYFrom(a, rad) { return this.copy(a).rotateY(rad); }
rotateZFrom(a, rad) { return this.copy(a).rotateZ(rad); }
fromTranslation(x, y, z) {
this[0] = 1;
this[1] = 0;
this[2] = 0;
this[3] = 0;
this[4] = 0;
this[5] = 1;
this[6] = 0;
this[7] = 0;
this[8] = 0;
this[9] = 0;
this[10] = 1;
this[11] = 0;
this[12] = x;
this[13] = y;
this[14] = z;
this[15] = 1;
return this;
}
translate(x, y, z) {
this[12] += x * this[0] + y * this[4] + z * this[8];
this[13] += x * this[1] + y * this[5] + z * this[9];
this[14] += x * this[2] + y * this[6] + z * this[10];
this[15] += x * this[3] + y * this[7] + z * this[11];
return this;
}
scale(x, y, z) {
this[0] *= x;
this[1] *= x;
this[2] *= x;
this[3] *= x;
this[4] *= y;
this[5] *= y;
this[6] *= y;
this[7] *= y;
this[8] *= z;
this[9] *= z;
this[10] *= z;
this[11] *= z;
return this;
}
}
return {
Vec3,
Vec4,
Mat4,
};
};
/* ------------------------- Polygon ------------------------- */
const Polygon = (math) => {
const { Vec3, Vec4 } = math;
const EPSILON = 1e-5;
const HC_IN = -1;
const HC_ON = 0;
const HC_OUT = 1;
const HC_SPANNING = 2;
let nextSurface = 0;
const flip = (poly) => {
const reversed = poly.slice().reverse();
reversed.plane = new Vec4().copy(poly.plane).scale(-1);
reversed.surface = poly.surface;
const n = poly.length;
reversed.edges = poly.edges.map((_, i) => poly.edges[(2 * n - 2 - i) % n]);
return reversed;
};
const definePlane = (poly) => {
const n = new Vec3();
for (let i = 0, last = poly.length - 1; i < poly.length; last = i, i++) {
const a = poly[last];
const b = poly[i];
n[0] += (a[1] - b[1]) * (a[2] + b[2]);
n[1] += (a[2] - b[2]) * (a[0] + b[0]);
n[2] += (a[0] - b[0]) * (a[1] + b[1]);
}
const len = n.norm();
if (len === 0) throw new Error("Degenerate polygon");
n.scale(1 / len);
return new Vec4(n[0], n[1], n[2], -n.dot(poly[0]));
};
const create = (points, edges = null) => {
points.plane = definePlane(points);
points.surface = ++nextSurface;
points.edges = edges ?? points.map(() => ({ kind: "original" }));
return points;
};
const createIndexed = (vertices, indices, topology = new Map()) => {
const edges = indices.map((a, i) => {
const b = indices[(i + 1) % indices.length];
const key = Math.min(a, b) * vertices.length + Math.max(a, b);
if (!topology.has(key)) topology.set(key, { kind: "original" });
return topology.get(key);
});
return create(
indices.map((i) => vertices[i]),
edges,
);
};
const distance = (point, plane) =>
point[0] * plane[0] +
point[1] * plane[1] +
point[2] * plane[2] +
plane[3];
const split = (poly, plane) => {
const out = [], inside = [];
const outIncoming = [], inIncoming = [];
let hasOut = false, hasIn = false;
let seam;
const cutEdge = () => (seam ??= { kind: "split", plane });
const n = poly.length;
let a = poly[n - 1];
let da = distance(a, plane);
for (let i = 0; i < n; i++) {
const b = poly[i];
const db = distance(b, plane);
const edge = poly.edges[(i + n - 1) % n];
if (db > EPSILON) {
hasOut = true;
if (da < -EPSILON) {
const p = new Vec3().lerpFrom(a, b, da / (da - db));
out.push(p);
outIncoming.push(cutEdge());
inside.push(p);
inIncoming.push(edge);
}
out.push(b);
outIncoming.push(edge);
} else if (db < -EPSILON) {
hasIn = true;
if (da > EPSILON) {
const p = new Vec3().lerpFrom(a, b, da / (da - db));
out.push(p);
outIncoming.push(edge);
inside.push(p);
inIncoming.push(cutEdge());
}
inside.push(b);
inIncoming.push(edge);
} else {
out.push(b);
outIncoming.push(da < -EPSILON ? cutEdge() : edge);
inside.push(b);
inIncoming.push(da > EPSILON ? cutEdge() : edge);
}
a = b;
da = db;
}
if (!hasOut && !hasIn) return [null, null, HC_ON];
if (!hasIn) return [poly, null, HC_OUT];
if (!hasOut) return [null, poly, HC_IN];
out.plane = inside.plane = poly.plane;
out.surface = inside.surface = poly.surface;
out.edges = out.map((_, i) => outIncoming[(i + 1) % out.length]);
inside.edges = inside.map((_, i) => inIncoming[(i + 1) % inside.length]);
return [out, inside, HC_SPANNING];
};
return {
create,
createIndexed,
definePlane,
distance,
split,
flip,
HC_IN,
HC_ON,
HC_OUT,
HC_SPANNING,
EPSILON,
};
};
/* ------------------------- Primitives ------------------------- */
const Primitives = (math, polygon) => {
const { Vec3 } = math;
const { createIndexed } = polygon;
const CUBE = {
vertices: [
[1, 1, 1],
[-1, 1, 1],
[-1, -1, 1],
[1, -1, 1],
[1, 1, -1],
[-1, 1, -1],
[-1, -1, -1],
[1, -1, -1],
],
faces: [
[0, 1, 2, 3],
[7, 6, 5, 4],
[0, 3, 7, 4],
[0, 4, 5, 1],
[5, 6, 2, 1],
[3, 2, 6, 7],
],
};
const PYRAMID = {
vertices: [
[1, 0, 1],
[-1, 0, 1],
[-1, 0, -1],
[1, 0, -1],
[0, 2, 0],
],
faces: [
[0, 1, 2, 3],
[4, 1, 0],
[4, 0, 3],
[4, 2, 1],
[4, 3, 2],
],
};
const DIAMOND = {
vertices: [
[1, 0, 1], [-1, 0, 1], [-1, 0, -1], [1, 0, -1],
[0, 1, 0], [0, -1, 0]
],
faces: [
[4, 1, 0], [4, 0, 3], [4, 2, 1], [4, 3, 2],
[0, 1, 5], [3, 0, 5], [1, 2, 5], [2, 3, 5]
]
};
const buildMesh = ({ vertices, faces }, transform) => {
const p = vertices.map(([x, y, z]) => new Vec3(x, y, z).transformPointMat4(transform));
const topology = new Map();
return faces.map((indices) => createIndexed(p, indices, topology));
};
const cube = (transform) => buildMesh(CUBE, transform);
const pyramid = (transform) => buildMesh(PYRAMID, transform);
const diamond = (transform) => buildMesh(DIAMOND, transform);
return { cube, pyramid, diamond };
};
/* ------------------------- Edges ------------------------- */
const Edges = (math, polygon) => {
const { Vec3 } = math;
const { EPSILON } = polygon;
const interval = ([a, b], axis) => [
Math.min(a[axis], b[axis]),
Math.max(a[axis], b[axis]),
];
const dominantAxis = (segments) => {
let axis = -1, max = EPSILON;
for (const [a, b] of segments) {
for (let i = 0; i < 3; i++) {
const d = Math.abs(b[i] - a[i]);
if (d > max) {
max = d;
axis = i;
}
}
}
return axis;
};
const merge = (spans) => {
spans.sort((a, b) => a[0] - b[0]);
const result = [];
for (const [lo, hi] of spans) {
const last = result[result.length - 1];
if (last && lo <= last[1] + EPSILON) last[1] = Math.max(last[1], hi);
else result.push([lo, hi]);
}
return result.filter(([lo, hi]) => hi - lo > EPSILON);
};
const makeSegments = (spans, sources, axis) => {
const ref = sources.find(([a, b]) => Math.abs(b[axis] - a[axis]) > EPSILON);
if (!ref) return [];
const [a, b] = ref;
const at = (t) => new Vec3().lerpFrom(a, b, (t - a[axis]) / (b[axis] - a[axis]));
return spans.map(([lo, hi]) => [at(lo), at(hi)]);
};
const extract = (faces) => {
const originals = new Map();
const intersections = new Map();
const planeIds = new Map();
const planeCache = new Map();
const PLANE_SCALE = 1e10;
const planeId = (plane) => {
if (planeCache.has(plane)) return planeCache.get(plane);
const sign = plane.find(v => Math.abs(v) > 1e-12) < 0 ? -1 : 1;
const key = Array.from(
plane,
v => Math.round(v * sign * PLANE_SCALE)
).join(',');
if (!planeIds.has(key)) planeIds.set(key, planeIds.size);
const id = planeIds.get(key);
planeCache.set(plane, id);
return id;
};
for (const face of faces) {
for (let i = 0; i < face.length; i++) {
const segment = [face[i], face[(i + 1) % face.length]];
const edge = face.edges[i];
if (edge.kind === "original") {
if (!originals.has(edge)) originals.set(edge, []);
originals.get(edge).push(segment);
} else if (edge.kind === "split") {
const a = planeId(face.plane);
const b = planeId(edge.plane);
if (a === b) continue;
const key = `${Math.min(a, b)}:${Math.max(a, b)}`;
if (!intersections.has(key)) intersections.set(key, [[], []]);
intersections.get(key)[a < b ? 0 : 1].push(segment);
}
}
}
const result = [];
for (const group of originals.values()) {
const axis = dominantAxis(group);
if (axis < 0) continue;
result.push(
...makeSegments(
merge(group.map((s) => interval(s, axis))),
group,
axis,
)
);
}
for (const [ab, ba] of intersections.values()) {
if (!ab.length || !ba.length) continue;
const axis = dominantAxis([...ab, ...ba]);
if (axis < 0) continue;
const spans = [];
for (const sa of ab) {
for (const sb of ba) {
const [alo, ahi] = interval(sa, axis);
const [blo, bhi] = interval(sb, axis);
const lo = Math.max(alo, blo);
const hi = Math.min(ahi, bhi);
if (hi - lo > EPSILON) spans.push([lo, hi]);
}
}
result.push(...makeSegments(merge(spans), ab, axis));
}
return result;
};
return { extract };
};
/* ------------------------- BSP ------------------------- */
const BSP = (polygon) => {
const {
split,
flip,
HC_IN, HC_ON, HC_OUT, HC_SPANNING
} = polygon;
const insertNode = (node, polygons, keep) => {
const inside = [];
const outside = [];
for (const poly of polygons) {
const [out, inp, kind] = split(poly, node.plane);
if (kind === HC_ON) {
node.on.push(poly);
} else {
if (inp) inside.push(inp);
if (out) outside.push(out);
}
}
if (inside.length) node.inside = insertTree(node.inside, inside, keep, HC_IN);
if (outside.length) node.outside = insertTree(node.outside, outside, keep, HC_OUT);
};
const insertTree = (node, polygons, keep, cur) => {
if (!polygons.length) return node;
if (node) {
insertNode(node, polygons, keep);
} else if (cur === keep || keep === HC_SPANNING) {
node = {
plane: polygons[0].plane,
on: [polygons[0]],
inside: null,
outside: null,
};
if (polygons.length > 1) insertNode(node, polygons.slice(1), HC_SPANNING);
}
return node;
};
const pushTree = (node, polygons, keep, cur, result) => {
if (!polygons.length) return;
if (!node) {
if (cur === keep) result.push(...polygons);
return;
}
const inside = [];
const outside = [];
for (const poly of polygons) {
const [out, inp, kind] = split(poly, node.plane);
if (kind === HC_ON) {
result.push(poly);
} else {
if (inp) inside.push(inp);
if (out) outside.push(out);
}
}
pushTree(node.inside, inside, keep, HC_IN, result);
pushTree(node.outside, outside, keep, HC_OUT, result);
};
const reduceNode = (node) => {
if (!node) return;
const boundary = [];
for (const poly of node.on) {
const intermediate = [];
const aligned =
poly.plane[0] * node.plane[0] +
poly.plane[1] * node.plane[1] +
poly.plane[2] * node.plane[2] >
0;
if (aligned) {
pushTree(node.inside, [poly], HC_IN, HC_IN, intermediate);
pushTree(node.outside, intermediate, HC_OUT, HC_OUT, boundary);
} else {
pushTree(node.outside, [poly], HC_OUT, HC_OUT, intermediate);
pushTree(node.inside, intermediate, HC_IN, HC_IN, boundary);
}
}
node.on = boundary;
reduceNode(node.inside);
reduceNode(node.outside);
};
const collect = (node, result) => {
if (!node) return;
result.push(...node.on);
collect(node.inside, result);
collect(node.outside, result);
};
const create = () => {
let root = null;
const occluded = (eye, point) => {
if (!root) return false;
const dx = point[0] - eye[0];
const dy = point[1] - eye[1];
const dz = point[2] - eye[2];
const MAX_T = 1 - 1e-6;
const EPS = 1e-9;
const contains = (p, q) => {
let positive = false, negative = false;
const nx = p.plane[0], ny = p.plane[1], nz = p.plane[2];
for (let i = 0; i < p.length; i++) {
const a = p[i], b = p[(i + 1) % p.length];
const ex = b[0] - a[0], ey = b[1] - a[1], ez = b[2] - a[2];
const px = q[0] - a[0], py = q[1] - a[1], pz = q[2] - a[2];
const s = (ey * pz - ez * py) * nx +
(ez * px - ex * pz) * ny +
(ex * py - ey * px) * nz;
if (s > EPS) positive = true;
else if (s < -EPS) negative = true;
if (positive && negative) return false;
}
return true;
};
const trace = (node, lo, hi) => {
if (!node || hi <= lo) return false;
const plane = node.plane;
const distance = eye[0] * plane[0] + eye[1] * plane[1] + eye[2] * plane[2] + plane[3];
const velocity = dx * plane[0] + dy * plane[1] + dz * plane[2];
if (Math.abs(velocity) < EPS) {
if (distance > EPS) return trace(node.outside, lo, hi);
if (distance < -EPS) return trace(node.inside, lo, hi);
return trace(node.outside, lo, hi) || trace(node.inside, lo, hi);
}
const at = -distance / velocity;
if (at <= lo || at >= hi) {
const mid = (lo + hi) * 0.5;
return trace(distance + velocity * mid > 0 ? node.outside : node.inside, lo, hi);
}
const near = velocity > 0 ? node.inside : node.outside;
const far = velocity > 0 ? node.outside : node.inside;
if (trace(near, lo, at)) return true;
const q = [eye[0] + dx * at, eye[1] + dy * at, eye[2] + dz * at];
for (const poly of node.on) if (contains(poly, q)) return true;
return trace(far, at, hi);
};
return trace(root, 0, MAX_T);
};
const api = {
insert(polygons, sign = 1) {
if (sign !== 1 && sign !== -1)
throw new Error("CSG: sign must be +1 or -1");
const faces = sign < 0 ? polygons.map(flip) : polygons;
const keep = sign > 0 ? HC_OUT : HC_IN;
root = insertTree(root, faces, keep, HC_OUT);
return api;
},
reduce() {
reduceNode(root);
return api;
},
faces() {
const result = [];
collect(root, result);
return result;
},
occluded,
};
return api;
};
return { create };
};
/* ------------------------- Camera ------------------------- */
const Camera = (math) => {
const { Vec3 } = math;
const create = (eye, target, fov = 45, near = 0.05) => {
const focus = 100 / Math.tan(fov * Math.PI / 360);
const forward = new Vec3().subFrom(target, eye).normalize();
const right = new Vec3().crossFrom(forward, new Vec3(0, 1, 0)).normalize();
const up = new Vec3().crossFrom(right, forward).normalize();
const depth = (p) =>
(p[0] - eye[0]) * forward[0] +
(p[1] - eye[1]) * forward[1] +
(p[2] - eye[2]) * forward[2];
const project = (p) => {
const dx = p[0] - eye[0], dy = p[1] - eye[1], dz = p[2] - eye[2];
const z = dx * forward[0] + dy * forward[1] + dz * forward[2];
return [
focus * (dx * right[0] + dy * right[1] + dz * right[2]) / z,
-focus * (dx * up[0] + dy * up[1] + dz * up[2]) / z
];
};
const clipSegment = (a, b) => {
const da = depth(a), db = depth(b);
if (da < near && db < near) return null;
if (da >= near && db >= near) return [a, b];
const p = new Vec3().lerpFrom(a, b, (near - da) / (db - da));
return da < near ? [p, b] : [a, p];
};
const clipPolygon = (poly) => {
const points = [];
let a = poly[poly.length - 1], da = depth(a);
for (const b of poly) {
const db = depth(b);
if ((da >= near) !== (db >= near))
points.push(new Vec3().lerpFrom(a, b, (near - da) / (db - da)));
if (db >= near) points.push(b);
a = b;
da = db;
}
return points.length >= 3 ? points.map(project) : [];
};
return { eye, depth, project, clipSegment, clipPolygon };
};
return { create };
};
/* ------------------------- Visibility ------------------------- */
const Visibility = (math) => {
const { Vec3 } = math;
const EPS2 = 1e-8;
const cross2 = (ax, ay, bx, by) => ax * by - ay * bx;
const prepare = (segments, faces, world, camera, gridSize = 0) => {
const polygons = faces
.map(camera.clipPolygon)
.filter((p) => p.length >= 3)
.map((points) => {
let minx = Infinity, miny = Infinity;
let maxx = -Infinity, maxy = -Infinity;
for (const [x, y] of points) {
if (x < minx) minx = x;
if (x > maxx) maxx = x;
if (y < miny) miny = y;
if (y > maxy) maxy = y;
}
return { points, minx, miny, maxx, maxy };
});
let query = null;
if (gridSize > 0 && polygons.length) {
const n = gridSize;
let x0 = Infinity, y0 = Infinity, x1 = -Infinity, y1 = -Infinity;
for (const p of polygons) {
x0 = Math.min(x0, p.minx); y0 = Math.min(y0, p.miny);
x1 = Math.max(x1, p.maxx); y1 = Math.max(y1, p.maxy);
}
const sx = n / Math.max(1e-9, x1 - x0);
const sy = n / Math.max(1e-9, y1 - y0);
const cellX = x => Math.max(0, Math.min(n - 1, Math.floor((x - x0) * sx)));
const cellY = y => Math.max(0, Math.min(n - 1, Math.floor((y - y0) * sy)));
const cells = Array.from({ length: n * n }, () => []);
for (let id = 0; id < polygons.length; id++) {
const p = polygons[id];
for (let y = cellY(p.miny); y <= cellY(p.maxy); y++)
for (let x = cellX(p.minx); x <= cellX(p.maxx); x++)
cells[x + y * n].push(id);
}
const seen = new Uint32Array(polygons.length);
let stamp = 0;
const candidates = [];
query = (minx, miny, maxx, maxy) => {
candidates.length = 0;
if (maxx < x0 || maxy < y0 || minx > x1 || miny > y1) return candidates;
const tag = ++stamp;
for (let y = cellY(miny); y <= cellY(maxy); y++) {
for (let x = cellX(minx); x <= cellX(maxx); x++) {
for (const id of cells[x + y * n]) {
if (seen[id] === tag) continue;
seen[id] = tag;
candidates.push(polygons[id]);
}
}
}
return candidates;
};
}
let edgeIndex = 0;
let visibleCount = 0;
let workTime = 0;
const process = (from, to, draw) => {
const clipped = camera.clipSegment(from, to);
if (!clipped) return;
const [a, b] = clipped;
const [ax, ay] = camera.project(a);
const [bx, by] = camera.project(b);
const rx = bx - ax, ry = by - ay;
const len2 = rx * rx + ry * ry;
if (len2 < EPS2) return;
const za = camera.depth(a), zb = camera.depth(b);
const cuts = [0, 1];
const minx = Math.min(ax, bx), maxx = Math.max(ax, bx);
const miny = Math.min(ay, by), maxy = Math.max(ay, by);
for (const box of query ? query(minx, miny, maxx, maxy) : polygons) {
if (
box.maxx < minx - EPS2 || box.minx > maxx + EPS2 ||
box.maxy < miny - EPS2 || box.miny > maxy + EPS2
) continue;
const poly = box.points;
let c = poly[poly.length - 1];
for (const d of poly) {
const sx = d[0] - c[0], sy = d[1] - c[1];
const qx = c[0] - ax, qy = c[1] - ay;
const det = cross2(rx, ry, sx, sy);
if (Math.abs(det) > EPS2) {
const t = cross2(qx, qy, sx, sy) / det;
const u = cross2(qx, qy, rx, ry) / det;
if (t > EPS2 && t < 1 - EPS2 && u >= -EPS2 && u <= 1 + EPS2)
cuts.push(t);
} else if (Math.abs(cross2(qx, qy, rx, ry)) < EPS2) {
for (const p of [c, d]) {
const t = ((p[0] - ax) * rx + (p[1] - ay) * ry) / len2;
if (t > EPS2 && t < 1 - EPS2) cuts.push(t);
}
}
c = d;
}
}
cuts.sort((x, y) => x - y);
const unique = cuts.filter((t, i) => i === 0 || t - cuts[i - 1] > EPS2);
let begin = null;
const emit = (start, end) => {
if (end - start < EPS2) return;
const p = [ax + rx * start, ay + ry * start];
const q = [ax + rx * end, ay + ry * end];
draw(p, q);
visibleCount++;
};
for (let i = 0; i < unique.length - 1; i++) {
const lo = unique[i], hi = unique[i + 1];
const s = (lo + hi) * 0.5;
const t = (s * za) / ((1 - s) * zb + s * za);
const p = new Vec3().lerpFrom(a, b, t);
const seen = !world.occluded(camera.eye, p);
if (seen && begin === null) begin = lo;
if (!seen && begin !== null) {
emit(begin, lo);
begin = null;
}
}
if (begin !== null) emit(begin, 1);
};
const walk = (budgetMs, draw) => {
if (edgeIndex >= segments.length) return false;
const start = performance.now();
do {
const [a, b] = segments[edgeIndex++];
process(a, b, draw);
} while (
edgeIndex < segments.length &&
performance.now() - start < budgetMs
);
workTime += performance.now() - start;
return edgeIndex < segments.length;
};
const stats = () => ({
processed: edgeIndex,
visible: visibleCount,
workTime,
});
return { walk, stats };
};
return { prepare };
};
/* ------------------------- Groups ------------------------- */
const Groups = (math, bsp) => {
const { Mat4 } = math;
const create = () => {
const operations = [];
const build = (transform = new Mat4()) => {
const solid = bsp.create();
for (const { shape, local, sign } of operations) {
const matrix = new Mat4().multiplyFrom(transform, local);
const faces = typeof shape === "function" ? shape(matrix) : shape.build(matrix);
solid.insert(faces, sign);
}
solid.reduce();
return solid.faces();
};
const api = {
insert(shape, local, sign = +1) {
if (sign !== +1 && sign !== -1)
throw new Error("Group: sign must be +1 or -1");
operations.push({ shape, local: new Mat4().copy(local), sign });
return api;
},
build,
place(world, transform = new Mat4(), sign = +1) {
world.insert(build(transform), sign);
return world;
}
};
return api;
};
return { create };
};
/* ------------------------- Boot ------------------------- */
const math = Math3D();
const polygon = Polygon(math);
const primitives = Primitives(math, polygon);
const bsp = BSP(polygon);
const edges = Edges(math, polygon);
const camera = Camera(math);
const visibility = Visibility(math);
const groups = Groups(math, bsp);
/* ------------------------- Infernal machine ------------------------- */
const { Mat4, Vec3 } = math;
const { cube, pyramid, diamond } = primitives;
const RAD = Math.PI / 180;
const t0 = performance.now();
const world = bsp.create();
// Room
world.insert(cube(new Mat4().scale(8, 8, 8)), +1);
world.insert(cube(new Mat4().scale(7.5, 7.5, 7.5)), -1);
// Main C-shaped body
world.insert(cube(new Mat4()), +1);
world.insert(
cube(new Mat4().translate(0.625, 0, 0).scale(1.5, 0.875, 1.5)),
-1,
);
// Left window and frame
world.insert(
cube(
new Mat4()
.translate(-0.95, 0, 0)
.rotateX(45 * RAD)
.scale(0.15, 0.4, 0.4),
),
+1,
);
world.insert(
cube(
new Mat4()
.translate(-1, 0, 0)
.rotateX(45 * RAD)
.scale(0.3, 0.3, 0.3),
),
-1,
);
// Right window, frame and support
world.insert(
cube(
new Mat4()
.translate(0.8, 0, 0)
.rotateX(45 * RAD)
.scale(0.15, 0.4, 0.4),
),
+1,
);
world.insert(
cube(new Mat4().translate(0.8, 0, 0).scale(0.0625, 1.8, 0.0625)),
+1,
);
world.insert(
cube(
new Mat4()
.translate(0.8, 0, 0)
.rotateX(45 * RAD)
.scale(1.5, 0.3, 0.3),
),
-1,
);
// Long diamond and opposed pyramids
world.insert(
diamond(
new Mat4()
.rotateX(45 * RAD)
.scale(4, 0.15, 0.15)
.rotateZ(90 * RAD),
),
+1,
);
// Radiator group primitive
const radiator = groups.create();
radiator.insert(
cube,
new Mat4()
.translate(0, -0.3, 0)
.scale(0.5, 0.05, 0.5),
);
radiator.insert(
cube,
new Mat4()
.translate(0, -0.5, 0)
.scale(0.51, 0.05, 0.51),
);
radiator.insert(
pyramid,
new Mat4()
.translate(0, -0.15, 0)
.scale(0.5, 0.5, 0.5),
);
// insert radiators
radiator.place(
world,
new Mat4()
.translate(0, -1.15, 0)
);
radiator.place(
world,
new Mat4()
.translate(0, 1.15, 0)
.rotateZ(Math.PI)
);
world.reduce();
const faces = world.faces();
const segments = edges.extract(faces);
const azimuth = Math.random() * 2 * Math.PI;
const elevation = ((Math.random() - 0.5) * Math.PI) / 3;
const radius = 4.5;
const eye = new Vec3(
radius * Math.cos(elevation) * Math.cos(azimuth),
radius * Math.sin(elevation),
radius * Math.cos(elevation) * Math.sin(azimuth),
);
const cam = camera.create(eye, new Vec3(0, 0, 0), 65);
const GRID_SIZE = 64;
const renderer = visibility.prepare(segments, faces, world, cam, GRID_SIZE);
const draw = (a, b) => {
turtle.jump(a[0], a[1]);
turtle.goto(b[0], b[1]);
};
let reported = false;
function walk () {
const running = renderer.walk(8, draw);
if (!running && !reported) {
reported = true;
turtle.penup();
const { visible, workTime } = renderer.stats();
}
return running;
}