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(1);
const turtle = new Turtle();
turtle.penup();
/* ============================================================
* 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
* ============================================================ */
/* ------------------------- Constants ------------------------- */
const HC_IN = -1, HC_ON = 0, HC_OUT = 1, HC_SPANNING = 2;
const EPSILON = 1 / 100000;
/* ------------------------- vec4 / mat4 ------------------------- */
const v4 = {
multiplyScalar (v, s) { return [ v[0]*s, v[1]*s, v[2]*s, v[3]*s ]; },
subtract (v, p) { return [ v[0]-p[0], v[1]-p[1], v[2]-p[2], v[3]-p[3] ]; },
add (v, p) { return [ v[0]+p[0], v[1]+p[1], v[2]+p[2], v[3]+p[3] ]; },
multiplyMatrix (v, m) {
const px = v[0], py = v[1], pz = v[2], pw = v[3];
return [
px*m[0] + py*m[4] + pz*m[8] + pw*m[12],
px*m[1] + py*m[5] + pz*m[9] + pw*m[13],
px*m[2] + py*m[6] + pz*m[10] + pw*m[14],
px*m[3] + py*m[7] + pz*m[11] + pw*m[15]
];
},
crossProduct (v, p) {
return [
v[1]*p[2] - v[2]*p[1],
v[2]*p[0] - v[0]*p[2],
v[0]*p[1] - v[1]*p[0],
0
];
},
dotProduct (v, p) {
return v[0]*p[0] + v[1]*p[1] + v[2]*p[2] + v[3]*p[3];
},
normalize (v) {
const n = Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2] + v[3]*v[3]);
return [ v[0]/n, v[1]/n, v[2]/n, v[3]/n ];
}
};
const m4 = {
identity() {
return [
1,0,0,0,
0,1,0,0,
0,0,1,0,
0,0,0,1
];
},
multiply (m, n) {
const
m1XX = m[0], m1XY = m[1], m1XZ = m[2], m1XW = m[3],
m1YX = m[4], m1YY = m[5], m1YZ = m[6], m1YW = m[7],
m1ZX = m[8], m1ZY = m[9], m1ZZ = m[10], m1ZW = m[11],
m1WX = m[12], m1WY = m[13], m1WZ = m[14], m1WW = m[15],
m2XX = n[0], m2XY = n[1], m2XZ = n[2], m2XW = n[3],
m2YX = n[4], m2YY = n[5], m2YZ = n[6], m2YW = n[7],
m2ZX = n[8], m2ZY = n[9], m2ZZ = n[10], m2ZW = n[11],
m2WX = n[12], m2WY = n[13], m2WZ = n[14], m2WW = n[15];
return [
m1XX*m2XX + m1XY*m2YX + m1XZ*m2ZX + m1XW*m2WX,
m1XX*m2XY + m1XY*m2YY + m1XZ*m2ZY + m1XW*m2WY,
m1XX*m2XZ + m1XY*m2YZ + m1XZ*m2ZZ + m1XW*m2WZ,
m1XX*m2XW + m1XY*m2YW + m1XZ*m2ZW + m1XW*m2WW,
m1YX*m2XX + m1YY*m2YX + m1YZ*m2ZX + m1YW*m2WX,
m1YX*m2XY + m1YY*m2YY + m1YZ*m2ZY + m1YW*m2WY,
m1YX*m2XZ + m1YY*m2YZ + m1YZ*m2ZZ + m1YW*m2WZ,
m1YX*m2XW + m1YY*m2YW + m1YZ*m2ZW + m1YW*m2WW,
m1ZX*m2XX + m1ZY*m2YX + m1ZZ*m2ZX + m1ZW*m2WX,
m1ZX*m2XY + m1ZY*m2YY + m1ZZ*m2ZY + m1ZW*m2WY,
m1ZX*m2XZ + m1ZY*m2YZ + m1ZZ*m2ZZ + m1ZW*m2WZ,
m1ZX*m2XW + m1ZY*m2YW + m1ZZ*m2ZW + m1ZW*m2WW,
m1WX*m2XX + m1WY*m2YX + m1WZ*m2ZX + m1WW*m2WX,
m1WX*m2XY + m1WY*m2YY + m1WZ*m2ZY + m1WW*m2WY,
m1WX*m2XZ + m1WY*m2YZ + m1WZ*m2ZZ + m1WW*m2WZ,
m1WX*m2XW + m1WY*m2YW + m1WZ*m2ZW + m1WW*m2WW
];
},
inverse (m) {
const
a00 = m[0], a01 = m[1], a02 = m[2], a03 = m[3],
a10 = m[4], a11 = m[5], a12 = m[6], a13 = m[7],
a20 = m[8], a21 = m[9], a22 = m[10], a23 = m[11],
a30 = m[12], a31 = m[13], a32 = m[14], a33 = m[15],
b00 = a00 * a11 - a01 * a10,
b01 = a00 * a12 - a02 * a10,
b02 = a00 * a13 - a03 * a10,
b03 = a01 * a12 - a02 * a11,
b04 = a01 * a13 - a03 * a11,
b05 = a02 * a13 - a03 * a12,
b06 = a20 * a31 - a21 * a30,
b07 = a20 * a32 - a22 * a30,
b08 = a20 * a33 - a23 * a30,
b09 = a21 * a32 - a22 * a31,
b10 = a21 * a33 - a23 * a31,
b11 = a22 * a33 - a23 * a32;
let det = b00*b11 - b01*b10 + b02*b09 + b03*b08 - b04*b07 + b05*b06;
if (!det) return this;
det = 1.0 / det;
return [
(a11*b11 - a12*b10 + a13*b09)*det,
(a02*b10 - a01*b11 - a03*b09)*det,
(a31*b05 - a32*b04 + a33*b03)*det,
(a22*b04 - a21*b05 - a23*b03)*det,
(a12*b08 - a10*b11 - a13*b07)*det,
(a00*b11 - a02*b08 + a03*b07)*det,
(a32*b02 - a30*b05 - a33*b01)*det,
(a20*b05 - a22*b02 + a23*b01)*det,
(a10*b10 - a11*b08 + a13*b06)*det,
(a01*b08 - a00*b10 - a03*b06)*det,
(a30*b04 - a31*b02 + a33*b00)*det,
(a21*b02 - a20*b04 - a23*b00)*det,
(a11*b07 - a10*b09 - a12*b06)*det,
(a00*b09 - a01*b07 + a02*b06)*det,
(a31*b01 - a30*b03 - a32*b00)*det,
(a20*b03 - a21*b01 + a22*b00)*det
];
},
rotateXYZ (angleX, angleY, angleZ) {
const cw = Math.cos(angleX), sw = Math.sin(angleX);
const cy = Math.cos(angleY), sy = Math.sin(angleY);
const ck = angleZ ? Math.cos(angleZ) : 1;
const sk = angleZ ? Math.sin(angleZ) : 0;
return [
cy*ck, cw*sk + sw*sy*ck, sw*sk - cw*sy*ck, 0,
-cy*sk, cw*ck - sw*sy*sk, sw*ck + cw*sy*sk, 0,
sy, -sw*cy, cw*cy, 0,
0, 0, 0, 1
];
},
scale (m, x, y, z) {
return this.multiply(m, [
x,0,0,0,
0,y,0,0,
0,0,z,0,
0,0,0,1
]);
},
translate (m, x, y, z) {
return this.multiply(m, [
1,0,0,0,
0,1,0,0,
0,0,1,0,
x,y,z,1
]);
},
rotateX (m, angle) {
angle = angle * (Math.PI / 180);
const c = Math.cos(angle), s = Math.sin(angle);
return this.multiply(m, [
1,0,0,0,
0,c,s,0,
0,-s,c,0,
0,0,0,1
]);
},
rotateY (m, angle) {
angle = angle * (Math.PI / 180);
const c = Math.cos(angle), s = Math.sin(angle);
return this.multiply(m, [
c,0,-s,0,
0,1,0,0,
s,0,c,0,
0,0,0,1
]);
},
rotateZ (m, angle) {
angle = angle * (Math.PI / 180);
const c = Math.cos(angle), s = Math.sin(angle);
return this.multiply(m, [
c,-s,0,0,
s,c,0,0,
0,0,1,0,
0,0,0,1
]);
}
};
/* ------------------------- mat4 chaining (builder) ------------------------- */
const mat4 = () => new Mat4();
class Mat4 {
constructor () { this.m = m4.identity(); }
scale (x, y, z) { this.m = m4.scale(this.m, x, y, z); return this; }
translate (x, y, z) { this.m = m4.translate(this.m, x, y, z); return this; }
rotateX (a) { this.m = m4.rotateX(this.m, a); return this; }
rotateY (a) { this.m = m4.rotateY(this.m, a); return this; }
rotateZ (a) { this.m = m4.rotateZ(this.m, a); return this; }
}
/* ------------------------- Polygon primitive ------------------------- */
const polygon = {
createIndexed (p, list) {
const points = [];
for (const index of list) points.push(p[index]);
points.plane = this.definePlane(points);
return points;
},
create (p) {
p.plane = this.definePlane(p);
return p;
},
definePlane (poly) {
// Newell normal (robust for convex polys too)
let sum = [0,0,0,0];
for (let i = 0, last = poly.length - 1; i < poly.length; last = i, i++) {
const A = poly[last]; // expects CCW order
const B = poly[i];
sum[0] += (A[1] - B[1]) * (A[2] + B[2]);
sum[1] += (A[2] - B[2]) * (A[0] + B[0]);
sum[2] += (A[0] - B[0]) * (A[1] + B[1]);
}
sum = v4.normalize(sum);
const p = poly[0];
return [
sum[0],
sum[1],
sum[2],
-(sum[0]*p[0] + sum[1]*p[1] + sum[2]*p[2] + sum[3]*p[3])
];
},
split (poly, plane) {
const outpts = [], inpts = [];
let outp, inp, out_c = 0, in_c = 0, poly_class = HC_ON;
let ptA = poly[poly.length - 1];
let sideA = v4.dotProduct(ptA, plane);
for (const ptB of poly) {
const sideB = v4.dotProduct(ptB, plane);
if (sideB > EPSILON) {
if (poly_class === HC_ON) poly_class = HC_OUT;
else if (poly_class !== HC_OUT) poly_class = HC_SPANNING;
if (sideA < -EPSILON) {
const v = v4.subtract(ptB, ptA);
outpts[out_c++] = inpts[in_c++] =
v4.add(ptA, v4.multiplyScalar(v, -v4.dotProduct(ptA, plane) / v4.dotProduct(v, plane)));
poly_class = HC_SPANNING;
}
outpts[out_c++] = ptB;
} else if (sideB < -EPSILON) {
if (poly_class === HC_ON) poly_class = HC_IN;
else if (poly_class !== HC_IN) poly_class = HC_SPANNING;
if (sideA > EPSILON) {
const v = v4.subtract(ptB, ptA);
outpts[out_c++] = inpts[in_c++] =
v4.add(ptA, v4.multiplyScalar(v, -v4.dotProduct(ptA, plane) / v4.dotProduct(v, plane)));
poly_class = HC_SPANNING;
}
inpts[in_c++] = ptB;
} else {
outpts[out_c++] = inpts[in_c++] = ptB;
}
ptA = ptB;
sideA = sideB;
}
switch (poly_class) {
case HC_OUT: outp = poly; break;
case HC_IN: inp = poly; break;
case HC_SPANNING:
outp = this.create(outpts);
inp = this.create(inpts);
break;
}
return [outp, inp, poly_class];
}
};
/* ------------------------- Geometry brushes ------------------------- */
const cube = (transform) => {
const p = [
v4.multiplyMatrix([ 1, 1, 1, 1], transform),
v4.multiplyMatrix([-1, 1, 1, 1], transform),
v4.multiplyMatrix([-1, -1, 1, 1], transform),
v4.multiplyMatrix([ 1, -1, 1, 1], transform),
v4.multiplyMatrix([ 1, 1, -1, 1], transform),
v4.multiplyMatrix([-1, 1, -1, 1], transform),
v4.multiplyMatrix([-1, -1, -1, 1], transform),
v4.multiplyMatrix([ 1, -1, -1, 1], transform)
];
return [
polygon.createIndexed(p, [0, 1, 2, 3]),
polygon.createIndexed(p, [7, 6, 5, 4]),
polygon.createIndexed(p, [0, 3, 7, 4]),
polygon.createIndexed(p, [0, 4, 5, 1]),
polygon.createIndexed(p, [5, 6, 2, 1]),
polygon.createIndexed(p, [3, 2, 6, 7])
];
};
const pyramid = (transform) => {
const p = [
v4.multiplyMatrix([ 1, 0, 1, 1], transform),
v4.multiplyMatrix([-1, 0, 1, 1], transform),
v4.multiplyMatrix([-1, 0, -1, 1], transform),
v4.multiplyMatrix([ 1, 0, -1, 1], transform),
v4.multiplyMatrix([ 0, 2, 0, 1], transform)
];
return [
polygon.createIndexed(p, [0, 1, 2, 3]),
polygon.createIndexed(p, [4, 1, 0]),
polygon.createIndexed(p, [4, 0, 3]),
polygon.createIndexed(p, [4, 2, 1]),
polygon.createIndexed(p, [4, 3, 2])
];
};
const diamond = (transform) => {
const p = [
v4.multiplyMatrix([ 1, 0, 1, 1], transform),
v4.multiplyMatrix([-1, 0, 1, 1], transform),
v4.multiplyMatrix([-1, 0, -1, 1], transform),
v4.multiplyMatrix([ 1, 0, -1, 1], transform),
v4.multiplyMatrix([ 0, 1, 0, 1], transform),
v4.multiplyMatrix([ 0, -1, 0, 1], transform)
];
return [
polygon.createIndexed(p, [4, 1, 0]),
polygon.createIndexed(p, [4, 0, 3]),
polygon.createIndexed(p, [4, 2, 1]),
polygon.createIndexed(p, [4, 3, 2]),
polygon.createIndexed(p, [0, 1, 5]),
polygon.createIndexed(p, [3, 0, 5]),
polygon.createIndexed(p, [1, 2, 5]),
polygon.createIndexed(p, [2, 3, 5])
];
};
/* ------------------------- BSP Tree ------------------------- */
class BspTree {
constructor () { this.node = null; }
insert (list, keep, cur = keep) {
if (list.length === 0) return;
if (this.node) {
this.node.insert(list, keep);
} else {
if ((cur === keep) || (keep === HC_SPANNING)) {
this.node = new BspNode(list.pop());
if (list.length) this.node.insert(list, HC_SPANNING);
}
}
}
pushPoly (poly, result, keep, cur) {
if (this.node !== null) this.node.pushPoly(poly, result, keep);
else if (cur === keep) result.push(poly);
}
pushList (list, result, keep, cur) {
if (list.length === 0) return;
if (this.node !== null) this.node.pushList(list, result, keep);
else if (cur === keep) result.push.apply(result, list);
}
reduce () {
if (this.node !== null) this.node.reduce();
}
}
class BspNode {
constructor (poly) {
this.plane = poly.plane;
this.on = [poly];
this.in = new BspTree();
this.out = new BspTree();
}
insert (list, keep) {
const inside = [], outside = [];
for (const poly of list) {
const [outp, inp, sgn] = polygon.split(poly, this.plane);
if (sgn === HC_ON) this.on.push(poly);
else {
if ((sgn === HC_IN) || (sgn === HC_SPANNING)) inside.push(inp);
if ((sgn === HC_OUT) || (sgn === HC_SPANNING)) outside.push(outp);
}
}
if (inside.length !== 0) this.in.insert(inside, keep, HC_IN);
if (outside.length !== 0) this.out.insert(outside, keep, HC_OUT);
}
pushPoly (poly, result, keep) {
const [outp, inp, sgn] = polygon.split(poly, this.plane);
if (sgn === HC_ON) result.push(poly);
else {
if ((sgn === HC_IN) || (sgn === HC_SPANNING)) this.in.pushPoly(inp, result, keep, HC_IN);
if ((sgn === HC_OUT) || (sgn === HC_SPANNING)) this.out.pushPoly(outp, result, keep, HC_OUT);
}
}
pushList (list, result, keep) {
const inside = [], outside = [];
for (const poly of list) {
const [outp, inp, sgn] = polygon.split(poly, this.plane);
if (sgn === HC_ON) result.push(poly);
else {
if ((sgn === HC_IN) || (sgn === HC_SPANNING)) inside.push(inp);
if ((sgn === HC_OUT) || (sgn === HC_SPANNING)) outside.push(outp);
}
}
if (inside.length !== 0) this.in.pushList(inside, result, keep, HC_IN);
if (outside.length !== 0) this.out.pushList(outside, result, keep, HC_OUT);
}
reduce () {
// "Extrude" negative parts: compute boundary polys
const results = [], boundary = [];
for (const poly of this.on) {
// if plane differs, choose which side to treat as inside/outside
if (Math.abs(poly.plane[3] + this.plane[3]) > EPSILON) {
this.in.pushPoly (poly, results, HC_IN, HC_IN);
this.out.pushList(results, boundary, HC_OUT, HC_OUT);
} else {
this.out.pushPoly(poly, results, HC_OUT, HC_OUT);
this.in.pushList (results, boundary, HC_IN, HC_IN);
}
}
this.on = boundary;
this.in.reduce();
this.out.reduce();
}
}
/* ------------------------- Camera ------------------------- */
const camera = {
frame: 1,
aspect: 100,
look (e, to, zoom) {
this.posEye = [e[0], e[1], e[2], 1];
this.zoom = zoom;
const vpn = v4.normalize(v4.subtract(this.posEye, [to[0], to[1], to[2], 1]));
// build orthonormal basis (store it!)
let u = v4.crossProduct([0, 1, 0, 0], vpn);
u = v4.normalize(u);
let v = v4.crossProduct(vpn, u);
v = v4.normalize(v);
const vrp = v4.add(this.posEye, v4.multiplyScalar(vpn, -zoom));
this.u = u; // vec4
this.v = v; // vec4
this.n = vpn; // vec4
this.vrp = vrp; // vec4
this.view = m4.multiply(this.viewMatrix(u, v, vpn, vrp), this.perspective(zoom));
},
perspective (distance) {
// w = 1 - z / distance (so projection is x/w, y/w)
return [
1,0,0,0,
0,1,0,0,
0,0,1,-1/distance,
0,0,0,1
];
},
viewMatrix (u, v, n, r) {
return [
u[0], v[0], n[0], 0,
u[1], v[1], n[1], 0,
u[2], v[2], n[2], 0,
-(r[0]*u[0] + r[1]*u[1] + r[2]*u[2] + r[3]*u[3]),
-(r[0]*v[0] + r[1]*v[1] + r[2]*v[2] + r[3]*v[3]),
-(r[0]*n[0] + r[1]*n[1] + r[2]*n[2] + r[3]*n[3]), 1
];
}
};
/* ===========================================================
* BSP + Hidden-Line (true 3D, no 2D clipper)
*
* Pipeline
* 1) BSP world.reduce() => boundary polygons (the "solid" skin)
* 2) Cad.collectPolys() => grab all boundary polys from the BSP tree
* 3) Cad.buildEdges() => build unique edges by vertex-key hashing
* 4) Cad.filterSplitEdges() => drop coplanar adjacency edges (BSP split artifacts)
* 5) Cad.purgeTJunctionEdges() => drop internal T-junction edges on coplanar faces
* 6) Cad.drawHiddenEdges() => recursive edge splitting + per-point visibility via ray casting
*
* ================================================================ */
class Cad {
constructor (world, camera, turtle) {
this.world = world;
this.camera = camera;
this.turtle = turtle;
this.polys = [];
this.edges = []; // { a, b, faces:[p0,p1?] }
// topology tolerances
this.epsKey = 1 / 10000; // vertex quantization
this.epsN = 1 / 10000; // plane normal epsilon
this.epsD = 1 / 10000; // plane d epsilon
// hidden-line params
this.epsHit = 1 / 100000; // ray-plane epsilon
this.pixelTol = 0.6; // screen-space tolerance
this.maxSplit = 15; // recursion cap
this.wMin = 0.05; // near-plane safety
}
/* ===================== Private helpers ===================== */
#collectNode (node) {
for (const p of node.on) this.polys.push(p);
if (node.in && node.in.node) this.#collectNode(node.in.node);
if (node.out && node.out.node) this.#collectNode(node.out.node);
}
#key3 (v, eps) {
const x = Math.round(v[0] / eps);
const y = Math.round(v[1] / eps);
const z = Math.round(v[2] / eps);
return x + "," + y + "," + z;
}
#coplanarPlanes (p0, p1) {
const dot = p0[0]*p1[0] + p0[1]*p1[1] + p0[2]*p1[2];
const epsN = 3 * this.epsN;
const epsD = 10 * this.epsD;
if (Math.abs(dot - 1) < epsN) return (Math.abs(p0[3] - p1[3]) < epsD);
if (Math.abs(dot + 1) < epsN) return (Math.abs(p0[3] + p1[3]) < epsD);
return false;
}
#clipWorldSegToWMin (A, B) {
const wMin = this.wMin;
// camera space endpoints
const Ac = v4.multiplyMatrix(A, this.camera.viewing);
const Bc = v4.multiplyMatrix(B, this.camera.viewing);
const wa = Ac[3];
const wb = Bc[3];
const ina = wa >= wMin;
const inb = wb >= wMin;
if (ina && inb) return [A, B];
if (!ina && !inb) return null;
// t where w(t) = wMin in camera space
const t = (wMin - wa) / (wb - wa);
// interpolate in WORLD space (camera transform is linear)
const C = [
A[0] + (B[0] - A[0]) * t,
A[1] + (B[1] - A[1]) * t,
A[2] + (B[2] - A[2]) * t,
1
];
return ina ? [A, C] : [C, B];
}
#edgeOnPolyBoundary (A, B, poly, plane) {
// project everything to a stable 2D basis on the plane,
// then test if AB matches some polygon boundary edge (colinear + overlap).
const n = [plane[0], plane[1], plane[2], 0];
let ux = 0, uy = 0, uz = 0;
if (Math.abs(n[0]) < 0.9) { ux = 1; uy = 0; uz = 0; }
else { ux = 0; uy = 1; uz = 0; }
const u = v4.normalize(v4.crossProduct([ux,uy,uz,0], n));
const v = v4.normalize(v4.crossProduct(n, u));
const ax = A[0]*u[0] + A[1]*u[1] + A[2]*u[2];
const ay = A[0]*v[0] + A[1]*v[1] + A[2]*v[2];
const bx = B[0]*u[0] + B[1]*u[1] + B[2]*u[2];
const by = B[0]*v[0] + B[1]*v[1] + B[2]*v[2];
const eps = 1 / 5000;
const m = poly.length;
for (let i = 0; i < m; i++) {
const P = poly[i];
const Q = poly[(i + 1) % m];
const px = P[0]*u[0] + P[1]*u[1] + P[2]*u[2];
const py = P[0]*v[0] + P[1]*v[1] + P[2]*v[2];
const qx = Q[0]*u[0] + Q[1]*u[1] + Q[2]*u[2];
const qy = Q[0]*v[0] + Q[1]*v[1] + Q[2]*v[2];
const abx = bx - ax, aby = by - ay;
const apx = px - ax, apy = py - ay;
const aqx = qx - ax, aqy = qy - ay;
const c1 = abx * apy - aby * apx;
const c2 = abx * aqy - aby * aqx;
if (Math.abs(c1) > eps || Math.abs(c2) > eps) continue;
const denom = (abx*abx + aby*aby);
if (denom < eps) continue;
const tp = (apx*abx + apy*aby) / denom;
const tq = (aqx*abx + aqy*aby) / denom;
const mn = Math.min(tp, tq);
const mx = Math.max(tp, tq);
if (mn <= 0 + 5*eps && mx >= 1 - 5*eps) return true;
}
return false;
}
#pointInConvexPoly3D (Q, poly, plane) {
// winding-agnostic half-space test:
// inside if all edge tests have same sign (within eps)
const nx = plane[0], ny = plane[1], nz = plane[2];
const n = poly.length;
let pos = false, neg = false;
for (let i = 0; i < n; i++) {
const A = poly[i];
const B = poly[(i + 1) % n];
const abx = B[0] - A[0], aby = B[1] - A[1], abz = B[2] - A[2];
const aqx = Q[0] - A[0], aqy = Q[1] - A[1], aqz = Q[2] - A[2];
const cx = aby * aqz - abz * aqy;
const cy = abz * aqx - abx * aqz;
const cz = abx * aqy - aby * aqx;
const s = cx*nx + cy*ny + cz*nz;
if (s > this.epsHit) pos = true;
else if (s < -this.epsHit) neg = true;
if (pos && neg) return false;
}
return true;
}
#isOccludedPoint (P, f0, f1, p2cached) {
const p2 = p2cached || this.project(P);
const x = p2[0], y = p2[1];
// ray through pixel
const [O, D] = this.rayFromScreen(x, y); // D normalized
// distance of P along ray
const OP = v4.subtract(P, O);
const tP = OP[0]*D[0] + OP[1]*D[1] + OP[2]*D[2];
if (tP <= this.epsHit) return false;
for (const poly of this.polys) {
// skip owning faces (avoid self-occlusion)
if (poly === f0 || poly === f1) continue;
// screen AABB cull
if (x < poly._bb0 || x > poly._bb2 || y < poly._bb1 || y > poly._bb3) continue;
const pl = poly.plane;
const nx = pl[0], ny = pl[1], nz = pl[2], d = pl[3];
// back-face cull (front-facing occluders only)
const nd = nx*D[0] + ny*D[1] + nz*D[2];
if (nd >= -this.epsHit) continue;
// ray-plane intersection
const no = nx*O[0] + ny*O[1] + nz*O[2] + d;
const tHit = -no / nd;
if (tHit <= this.epsHit) continue;
if (tHit >= tP - this.epsHit) continue;
const Q = [
O[0] + D[0] * tHit,
O[1] + D[1] * tHit,
O[2] + D[2] * tHit,
1
];
if (this.#pointInConvexPoly3D(Q, poly, pl)) return true;
}
return false;
}
#isVisiblePoint (P, f0, f1, p2cached) {
return !this.#isOccludedPoint(P, f0, f1, p2cached);
}
#splitDrawEdge (A, B, f0, f1, depth) {
// near-plane safety: clip segment before any projection
const clipped = this.#clipWorldSegToWMin(A, B);
if (!clipped) return;
A = clipped[0];
B = clipped[1];
const a2 = this.project(A);
const b2 = this.project(B);
const dx = b2[0] - a2[0];
const dy = b2[1] - a2[1];
const d2 = dx*dx + dy*dy;
const visA = this.#isVisiblePoint(A, f0, f1, a2);
const visB = this.#isVisiblePoint(B, f0, f1, b2);
// fast accept
if (visA && visB && (d2 <= this.pixelTol*this.pixelTol || depth >= this.maxSplit)) {
const t = this.turtle;
t.penup(); t.goto(a2[0], a2[1]);
t.pendown(); t.goto(b2[0], b2[1]);
return;
}
// fast reject
if (!visA && !visB && (d2 <= this.pixelTol*this.pixelTol || depth >= this.maxSplit)) {
return;
}
// split
const M = [
(A[0] + B[0]) * 0.5,
(A[1] + B[1]) * 0.5,
(A[2] + B[2]) * 0.5,
1
];
const m2 = this.project(M);
const visM = this.#isVisiblePoint(M, f0, f1, m2);
// if all same state but still large, keep splitting
if (visA === visM && visM === visB && depth < this.maxSplit) {
this.#splitDrawEdge(A, M, f0, f1, depth + 1);
this.#splitDrawEdge(M, B, f0, f1, depth + 1);
return;
}
// mixed states => split adaptively
if (depth < this.maxSplit) {
this.#splitDrawEdge(A, M, f0, f1, depth + 1);
this.#splitDrawEdge(M, B, f0, f1, depth + 1);
} else {
// fallback: draw if midpoint visible
if (visM) {
const t = this.turtle;
t.penup(); t.goto(a2[0], a2[1]);
t.pendown(); t.goto(b2[0], b2[1]);
}
}
}
/* ====================== Public API ======================= */
setRotation (rx, ry, rz) {
// recompute camera transforms + rotated basis for ray casting
this.camera.frame++;
const r = m4.rotateXYZ(rx, ry, rz);
const invr = m4.inverse(r);
this.camera.viewing = m4.multiply(r, this.camera.view);
this.camera.eye = v4.multiplyMatrix(this.camera.posEye, invr);
// rotate camera basis + vrp the same way (world space)
this.uR = v4.normalize(v4.multiplyMatrix(this.camera.u, invr));
this.vR = v4.normalize(v4.multiplyMatrix(this.camera.v, invr));
this.vrpR = v4.multiplyMatrix(this.camera.vrp, invr);
}
project (p4) {
const p = v4.multiplyMatrix(p4, this.camera.viewing);
const invw = 1 / p[3];
return [
(p[0] * invw) * this.camera.aspect,
(p[1] * invw) * -this.camera.aspect
];
}
rayFromScreen (x, y) {
// build a world-space ray from screen coords (turtle units)
const nx = x / this.camera.aspect;
const ny = -y / this.camera.aspect;
const Pw = v4.add(
this.vrpR,
v4.add(
v4.multiplyScalar(this.uR, nx),
v4.multiplyScalar(this.vR, ny)
)
);
const O = this.camera.eye;
const D = v4.normalize(v4.subtract(Pw, O));
return [O, D];
}
collectPolys () {
this.polys.length = 0;
if (!this.world || !this.world.node) return this.polys;
this.#collectNode(this.world.node);
return this.polys;
}
buildEdges () {
const map = new Map();
const eps = this.epsKey;
for (const poly of this.polys) {
const n = poly.length;
for (let i = 0; i < n; i++) {
const a = poly[i];
const b = poly[(i + 1) % n];
const ka = this.#key3(a, eps);
const kb = this.#key3(b, eps);
const ek = (ka < kb) ? (ka + "|" + kb) : (kb + "|" + ka);
let e = map.get(ek);
if (!e) {
e = { a: a, b: b, faces: [poly] };
map.set(ek, e);
} else {
if (e.faces.length < 2) e.faces.push(poly);
}
}
}
this.edges.length = 0;
for (const e of map.values()) this.edges.push(e);
return this.edges;
}
filterSplitEdges () {
// remove edges between coplanar adjacent polygons (BSP split artifacts)
const out = [];
for (const e of this.edges) {
if (e.faces.length === 1) out.push(e);
else {
const p0 = e.faces[0], p1 = e.faces[1];
if (!this.#coplanarPlanes(p0.plane, p1.plane)) out.push(e);
}
}
this.edges = out;
return this.edges;
}
purgeTJunctionEdges () {
// remove "internal" edges caused by T-junctions on coplanar faces
// (keeps the silhouette / boundary lines only)
const buckets = new Map();
const pe = 1 / 2000; // plane quantization
const pkey = (pl) => {
const nx = Math.round(pl[0] / pe);
const ny = Math.round(pl[1] / pe);
const nz = Math.round(pl[2] / pe);
const d = Math.round(pl[3] / (pe * 10));
if (nx < 0 || (nx === 0 && (ny < 0 || (ny === 0 && nz < 0)))) {
return (-nx)+","+(-ny)+","+(-nz)+","+(-d);
}
return nx+","+ny+","+nz+","+d;
};
for (const poly of this.polys) {
const k = pkey(poly.plane);
let b = buckets.get(k);
if (!b) buckets.set(k, (b = []));
b.push(poly);
}
const out = [];
for (const e of this.edges) {
// only ambiguous ones: single-face edges
if (e.faces.length !== 1) { out.push(e); continue; }
const owner = e.faces[0];
const k = pkey(owner.plane);
const candidates = buckets.get(k);
let kill = false;
if (candidates && candidates.length > 1) {
for (const q of candidates) {
if (q === owner) continue;
if (this.#edgeOnPolyBoundary(e.a, e.b, q, owner.plane)) {
kill = true;
break;
}
}
}
if (!kill) out.push(e);
}
this.edges = out;
return this.edges;
}
preparePolys2D () {
// compute per-poly screen AABB (cheap cull for occlusion tests)
for (const poly of this.polys) {
let minx = 1e30, miny = 1e30;
let maxx = -1e30, maxy = -1e30;
for (const p0 of poly) {
if (p0.frame !== this.camera.frame) {
const p = v4.multiplyMatrix(p0, this.camera.viewing);
const invw = 1 / p[3];
p0.frame = this.camera.frame;
p0.x = (p[0] * invw) * this.camera.aspect;
p0.y = (p[1] * invw) * -this.camera.aspect;
}
const x = p0.x, y = p0.y;
if (x < minx) minx = x;
if (y < miny) miny = y;
if (x > maxx) maxx = x;
if (y > maxy) maxy = y;
}
poly._bb0 = minx;
poly._bb1 = miny;
poly._bb2 = maxx;
poly._bb3 = maxy;
}
}
drawHiddenEdges () {
this.preparePolys2D();
for (const e of this.edges) {
const f0 = e.faces[0] || null;
const f1 = e.faces[1] || null;
this.#splitDrawEdge(e.a, e.b, f0, f1, 0);
}
}
addOccluderPolys (list) {
for (const p of list) this.polys.push(p);
}
addDrawableEdges (pairs) {
// pairs = [[A,B],[A,B]...] with A,B vec4
for (const e of pairs) {
this.edges.push({ a: e[0], b: e[1], faces: [] });
}
}
}
/* ------------------------- Room (occluder + drawable edges) ------------------------- */
class RoomHL {
constructor (sx = 10, sy = 5, sz = 10) {
this.sx = sx; this.sy = sy; this.sz = sz;
this.m = m4.identity();
this.polys = [];
this.edges = [];
this.#build();
}
translate (x, y, z) {
this.m = m4.translate(this.m, x, y, z);
this.#build();
return this;
}
#pt (x, y, z) {
return v4.multiplyMatrix([x, y, z, 1], this.m);
}
#build () {
const sx = this.sx, sy = this.sy, sz = this.sz;
const P = [
this.#pt(-sx, -sy, -sz),
this.#pt( sx, -sy, -sz),
this.#pt( sx, sy, -sz),
this.#pt(-sx, sy, -sz),
this.#pt(-sx, -sy, sz),
this.#pt( sx, -sy, sz),
this.#pt( sx, sy, sz),
this.#pt(-sx, sy, sz)
];
// 6 quads, CCW as seen from INSIDE the room (important for back-face cull)
this.polys = [
polygon.createIndexed(P, [0,1,2,3]), // back (-z)
polygon.createIndexed(P, [4,7,6,5]), // front (+z)
polygon.createIndexed(P, [0,4,5,1]), // bottom(-y)
polygon.createIndexed(P, [3,2,6,7]), // top (+y)
polygon.createIndexed(P, [0,3,7,4]), // left (-x)
polygon.createIndexed(P, [1,5,6,2]) // right (+x)
];
// 12 edges as indices
this.edges = [
[P[0],P[1]],[P[1],P[2]],[P[2],P[3]],[P[3],P[0]],
[P[4],P[5]],[P[5],P[6]],[P[6],P[7]],[P[7],P[4]],
[P[0],P[4]],[P[1],P[5]],[P[2],P[6]],[P[3],P[7]]
];
}
}
/* ------------------------- Scene build (BSP) ------------------------- */
const world = new BspTree();
// Main "machine"
world.insert(cube(mat4().m), 1); // base cube
world.insert(cube(mat4().scale(-1.5,-0.875,-1.5).translate(0.625,0,0).m), -1); // C cutout
world.insert(cube(mat4().scale(0.15,0.4,0.4).translate(-0.95,0,0).rotateX(45).m), 1); // window frame
world.insert(cube(mat4().scale(-0.3,-0.3,-0.3).translate(-1,0,0).rotateX(45).m), -1); // window hole
world.insert(cube(mat4().scale(0.15,0.4,0.4).translate(0.8,0,0).rotateX(45).m), 1); // window frame
world.insert(cube(mat4().scale(0.0625,1.8,0.0625).translate(0.8,0,0).m), 1); // support
world.insert(cube(mat4().scale(-1.5,-0.3,-0.3).translate(0.8,0,0).rotateX(45).m), -1); // window hole
world.insert(diamond(mat4().rotateZ(90).scale(4,0.15,0.15).rotateX(45).m), 1); // long diamond
world.insert(pyramid(mat4().scale(0.5,0.5,0.5).translate(0,-1.25,0).rotateZ(180).m), 1); // pyramid
world.insert(pyramid(mat4().scale(0.5,0.5,0.5).translate(0,-1.25,0).m), 1); // pyramid
world.insert(cube(mat4().scale(0.5,0.05,0.5).translate(0,-1.4,0).m), 1);// slab
world.insert(cube(mat4().scale(0.51,0.05,0.51).translate(0,-1.6,0).m), 1); // slab
world.insert(cube(mat4().scale(0.5,0.05,0.5).translate(0,1.4,0).m), 1); // slab
world.insert(cube(mat4().scale(0.51,0.05,0.51).translate(0,1.6,0).m), 1); // slab
world.reduce(); // compute boundary polys (CSG-ish)
/* ------------------------- Run (hidden-line) ------------------------- */
camera.look([0,0,8], [0,0,0], 3);
const cad = new Cad(world, camera, turtle);
// Extract BSP boundary polys
cad.collectPolys();
// Add a room as occluder + drawable edges
const room = new RoomHL(10, 5, 10);
cad.addOccluderPolys(room.polys);
// Build drawable edge list from boundary polys + room edges
cad.buildEdges();
cad.filterSplitEdges();
cad.purgeTJunctionEdges();
cad.addDrawableEdges(room.edges);
// Random rotation (rx, ry, rz in radians)
cad.setRotation(-0.25 * Math.PI + Math.random() * 0.5 * Math.PI, Math.random() * 2 * Math.PI, 0);
// Hidden-line render (true 3D: rays vs polygons)
cad.drawHiddenEdges();