Finds the nearest face a ray meets and the distance from a point to the nearest face, for the supports preview, the wall-thickness check, hollowing and splitting.
How the precision is kept
Positions, normals, areas and boxes are Float64Array and every query is 64-bit. The ray test is Möller–Trumbore with fixed absolute tolerances; the point distance is the closed-form closest point on a triangle. A box tree only limits which triangles are tested, each of which is then measured in full.
Calculations under this policy
5 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
The unit normal, area and bounding box of every triangle, and the size of the whole mesh.
n = (b − a) × (c − a); area = |n| ÷ 2; unit normal = n ÷ |n|
Edges are formed by subtracting the first corner, so the cross product does not depend on where the mesh sits. A triangle with zero cross product keeps a zero normal and zero area and is not divided.
print-geom.js
lines 21 to 42
ModelCraft 0.8.1
export function triMesh(mesh) {
const P = mesh.positions, I = mesh.indices, nt = I.length / 3;
const N = new Float64Array(nt * 3), A = new Float64Array(nt), boxes = new Float64Array(nt * 6);
const lo = [Infinity, Infinity, Infinity], hi = [-Infinity, -Infinity, -Infinity];
for (let t = 0; t < nt; t++) {
const a = I[t * 3] * 3, b = I[t * 3 + 1] * 3, c = I[t * 3 + 2] * 3;
const ux = P[b] - P[a], uy = P[b + 1] - P[a + 1], uz = P[b + 2] - P[a + 2];
const vx = P[c] - P[a], vy = P[c + 1] - P[a + 1], vz = P[c + 2] - P[a + 2];
const nx = uy * vz - uz * vy, ny = uz * vx - ux * vz, nz = ux * vy - uy * vx, l = Math.hypot(nx, ny, nz);
A[t] = l / 2;
if (l) { N[t * 3] = nx / l; N[t * 3 + 1] = ny / l; N[t * 3 + 2] = nz / l; }
for (let k = 0; k < 3; k++) {
const x = P[a + k], y = P[b + k], z = P[c + k];
const mn = Math.min(x, y, z), mx = Math.max(x, y, z);
boxes[t * 6 + k] = mn; boxes[t * 6 + 3 + k] = mx;
if (mn < lo[k]) lo[k] = mn;
if (mx > hi[k]) hi[k] = mx;
}
}
const tree = new BoxTree(boxes);
return { P, I, nt, N, A, tree, boxes, lo, hi, size: [hi[0] - lo[0], hi[1] - lo[1], hi[2] - lo[2]], stack: new Int32Array(256) };
}
Nearest face along a ray
64-bit
The distance to the first triangle a ray meets between two limits, and whether it meets it from behind.
det = e₁·(d × e₂); u = (s·(d × e₂)) ÷ det; v = (d·(s × e₁)) ÷ det; t = (e₂·(s × e₁)) ÷ det
A triangle is skipped when |det| < 1e-14, an absolute cutoff in mm² times the direction's length, so with a unit direction a triangle with sides of about 1e-7 mm or smaller is never hit. u and v are accepted up to 1e-9 outside the triangle (absolute, in barycentric units). The reciprocals 1 ÷ dx are taken without a zero check and the box test handles the infinite case.
print-geom.js
lines 47 to 82
ModelCraft 0.8.1
export function rayNearest(T, ox, oy, oz, dx, dy, dz, tmin, tmax, skip, hit) {
const { tree, P, I } = T;
if (!tree.n) return -1;
const nb = tree.nb, kid = tree.kid, idx = tree.idx, B = tree.boxes;
const ix = 1 / dx, iy = 1 / dy, iz = 1 / dz;
let best = tmax, bestTri = -1, bestBack = 0, sp = 0, st = T.stack;
st[sp++] = 0;
while (sp) {
const id = st[--sp], o = id * 6;
if (!slab(nb, o, ox, oy, oz, ix, iy, iz, tmin, best)) continue;
const a = kid[id * 2], c = kid[id * 2 + 1];
if (a >= 0) { if (sp + 2 > st.length) st = grow(T); st[sp++] = c; st[sp++] = a; continue; }
for (let k = -1 - a, e = -1 - a + c; k < e; k++) {
const t = idx[k];
if (t === skip || !slab(B, t * 6, ox, oy, oz, ix, iy, iz, tmin, best)) continue;
// Möller–Trumbore
const p0 = I[t * 3] * 3, p1 = I[t * 3 + 1] * 3, p2 = I[t * 3 + 2] * 3;
const e1x = P[p1] - P[p0], e1y = P[p1 + 1] - P[p0 + 1], e1z = P[p1 + 2] - P[p0 + 2];
const e2x = P[p2] - P[p0], e2y = P[p2 + 1] - P[p0 + 1], e2z = P[p2 + 2] - P[p0 + 2];
const hx = dy * e2z - dz * e2y, hy = dz * e2x - dx * e2z, hz = dx * e2y - dy * e2x;
const det = e1x * hx + e1y * hy + e1z * hz;
if (Math.abs(det) < 1e-14) continue;
const f = 1 / det, sx = ox - P[p0], sy = oy - P[p0 + 1], sz = oz - P[p0 + 2];
const u = f * (sx * hx + sy * hy + sz * hz);
if (u < -1e-9 || u > 1 + 1e-9) continue;
const qx = sy * e1z - sz * e1y, qy = sz * e1x - sx * e1z, qz = sx * e1y - sy * e1x;
const v = f * (dx * qx + dy * qy + dz * qz);
if (v < -1e-9 || u + v > 1 + 1e-9) continue;
const d = f * (e2x * qx + e2y * qy + e2z * qz);
if (d > tmin && d <= best) { best = d; bestTri = t; bestBack = det < 0 ? 1 : 0; }
}
}
if (bestTri < 0) return -1;
if (hit) { hit.tri = bestTri; hit.back = bestBack; }
return best;
}
Ray and box
64-bit
Whether a ray passes through a box within the current distance limits.
When the direction is zero on an axis the products are 0 × ∞ = NaN; the code detects NaN and then tests whether the origin lies between the two sides instead. The comparison is exact, with no tolerance, so the box test is only as wide as the box itself.
print-geom.js
lines 84 to 95
ModelCraft 0.8.1
function slab(b, o, ox, oy, oz, ix, iy, iz, t0, t1) {
for (let a = 0; a < 3; a++) {
const og = a === 0 ? ox : a === 1 ? oy : oz, inv = a === 0 ? ix : a === 1 ? iy : iz;
let n = (b[o + a] - og) * inv, f = (b[o + 3 + a] - og) * inv;
if (n !== n || f !== f) { if (og < b[o + a] || og > b[o + 3 + a]) return false; continue; } // along a side (0 · ∞)
if (n > f) { const s = n; n = f; f = s; }
if (n > t0) t0 = n;
if (f < t1) t1 = f;
if (t0 > t1) return false;
}
return true;
}
Point to triangle distance
64-bit
The squared distance from a point to the closest point of one triangle.
closest point q by the corner, edge and face regions; d² = |p − q|²
All dot products are taken relative to the triangle's own corners. The last case, a closest point inside the face, divides by va + vb + vc without a zero check.
The distance from a point to the nearest triangle within a search radius.
d = √(min over triangles of d²), limited to r
Squared distances are compared and one square root is taken at the end. Boxes farther than the best squared distance so far are skipped with an exact comparison.
print-geom.js
lines 127 to 146
ModelCraft 0.8.1
export function nearestDist(T, x, y, z, r) {
const { tree } = T;
if (!tree.n) return Infinity;
const nb = tree.nb, kid = tree.kid, idx = tree.idx, B = tree.boxes;
let best2 = r * r, found = false, sp = 0, st = T.stack;
st[sp++] = 0;
while (sp) {
const id = st[--sp];
if (boxD2(nb, id * 6, x, y, z) > best2) continue;
const a = kid[id * 2], c = kid[id * 2 + 1];
if (a >= 0) { if (sp + 2 > st.length) st = grow(T); st[sp++] = c; st[sp++] = a; continue; }
for (let k = -1 - a, e = -1 - a + c; k < e; k++) {
const t = idx[k];
if (boxD2(B, t * 6, x, y, z) > best2) continue;
const d2 = triPointDist2(T, t, x, y, z);
if (d2 <= best2) { best2 = d2; found = true; }
}
}
return found ? Math.sqrt(best2) : Infinity;
}
In detail
Method
Möller–Trumbore ray and triangle test; closest point on a triangle after Ericson, Real-Time Collision Detection § 5.1.5 (cited in the code); slab test for boxes.
Number types
Float64Array for positions, normals, areas and boxes; Int32Array for the traversal stack; millimeters.
Tolerances
Ray test: a triangle is skipped when |det| < 1e-14 (absolute); barycentric limits are widened by 1e-9 (absolute, dimensionless).
Limits
The 1e-14 determinant cutoff is not scaled to the triangle's size or the direction's length, so very small triangles are skipped as parallel.
Approach: 64-bit, direct
Every value is a 64-bit number from input to result. Formulas are closed form or a direct solve, and every comparison uses a stated tolerance.