Shortens a move so that solids do not pass into each other, and returns the distance actually moved.
How the precision is kept
The move is tested at sample positions along its straight path and the first contact is then narrowed by 24 bisections, all in 64-bit numbers. Contact means an edge crossing the inside of a face or a point of one solid inside the other; touching within 1e-5 model units is allowed. The stop position is therefore found to within the bisection step, and a contact can be missed when the samples are farther apart than the thinnest part.
Open item. Lift the cap of 160 samples for long moves, so that the sample spacing never exceeds half the thinnest dimension.
Calculations under this policy
7 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 part of a straight move that stays clear of other solids.
steps = min(160, max(4, ⌈|δ| ÷ (thin ÷ 2)⌉)); then 24 halvings between the last clear and the first blocked sample
The result is the last clear position of the bisection, within |δ| ÷ steps ÷ 2²⁴ of the first contact found. The sample count is capped at 160, so for a move longer than 80 times the thinnest dimension the samples are farther apart than half that dimension and a thin wall can lie between two samples. A move no longer than 1e-5 is returned unchanged.
m3d/collide.js
lines 90 to 105
CadCraft 0.8.2
clamp(delta) {
if (empty || !statics.length || len(delta) <= TOL) return { delta, hit: false };
const steps = Math.min(MAX_STEPS, Math.max(4, Math.ceil(len(delta) / (thin / 2))));
let lo = 0, hi = null;
for (let i = 1; i <= steps; i++) {
const t = i / steps;
if (blocked(mul(delta, t))) { hi = t; break; }
lo = t;
}
if (hi === null) return { delta, hit: false };
for (let k = 0; k < 24; k++) {
const m = (lo + hi) / 2;
if (blocked(mul(delta, m))) hi = m; else lo = m;
}
return { delta: mul(delta, lo), hit: true };
},
Thinnest dimension
64-bit
The smallest box side of the moving pieces and of everything in the way, which sets the sample spacing.
thin = max(0.005, min over boxes of the smallest side above 1e-4)
Box sides of 1e-4 or less are left out, and the result is never below 0.005 model units. Both limits are absolute.
Whether a segment passes through a face's interior.
sₚ = n·p − d, s_q = n·q − d; t = sₚ ÷ (sₚ − s_q)
Both ends must be more than 1e-5 from the plane on opposite sides, so the divisor adds two magnitudes and cannot cancel. A crossing point within 1e-5 of the face's outline does not count.
m3d/collide.js
lines 197 to 209
CadCraft 0.8.2
/** Segment p–q crosses face f's interior (f shifted by s): ends strictly on both sides, crossing point
* inside the face and clear of its outline. */
function crosses(p, q, f, s) {
const dd = s ? f.d + dot(f.n, s) : f.d;
const sp = dot(f.n, p) - dd, sq = dot(f.n, q) - dd;
if (!((sp > TOL && sq < -TOL) || (sp < -TOL && sq > TOL))) return false;
const t = sp / (sp - sq);
let x = add(p, mul(sub(q, p), t));
if (s) x = sub(x, s); // test against the unshifted face
if (!inFace(x, f)) return false;
for (const [a, b] of f.bnd) if (segDist(x, a, b) <= TOL) return false;
return true;
}
Point in a face
64-bit
Whether a point on a face's plane lies in one of its triangles.
u, v from cross products ÷ |n|²; inside when u, v, 1 − u − v ≥ −1e-9
Barycentric coordinates with a slack of 1e-9, which is relative to the triangle because the coordinates are ratios. Triangles whose squared normal is below 1e-24 are skipped, an absolute limit.
m3d/collide.js
lines 211 to 220
CadCraft 0.8.2
function inFace(x, f) {
for (const [a, b, c] of f.tris) {
const n = cross(sub(b, a), sub(c, a));
const nn = dot(n, n);
if (nn < 1e-24) continue;
const u = dot(cross(sub(c, b), sub(x, b)), n) / nn, v = dot(cross(sub(a, c), sub(x, c)), n) / nn;
if (u >= -1e-9 && v >= -1e-9 && 1 - u - v >= -1e-9) return true;
}
return false;
}
Point inside a solid
64-bit
Whether a point lies inside the closed surface made of an object's faces.
Three fixed ray directions are tried and all three must cross the surface an odd number of times. A crossing at 1e-5 or closer means the point is on the surface, which counts as not inside. A ray that passes exactly through an edge shared by two faces can be counted for both.
m3d/collide.js
lines 229 to 247
CadCraft 0.8.2
/** Is p inside the closed surface made of object o's faces? Three rays must all cross it an odd number of times;
* a point on the surface is not inside. Only the faces whose boxes a ray passes through are tried. */
function inside(p, o) {
for (const r of RAYS) {
let n = 0, on = false;
o.ftree.ray(p, r, (j) => {
for (const [a, b, c] of o.F[j].tris) {
const t = rayTriT(p, r, a, b, c);
if (t === null) continue;
if (t <= TOL) { on = true; return true; }
n++;
return false;
}
return false;
});
if (on || n % 2 === 0) return false;
}
return true;
}
Ray against a triangle
64-bit
The distance along a ray to a triangle, or nothing when it misses.
det = e₁·(d × e₂); u = (s·(d × e₂)) ÷ det; v = (d·(s × e₁)) ÷ det; t = (e₂·(s × e₁)) ÷ det
The ray is treated as parallel when |det| is below 1e-14, an absolute limit on a value that scales with the square of the triangle's size, so very small triangles are skipped. u and v have a slack of 1e-9; a hit up to 1e-5 behind the start is returned as 0.
m3d/collide.js
lines 249 to 258
CadCraft 0.8.2
function rayTriT(o, d, a, b, c) {
const e1 = sub(b, a), e2 = sub(c, a), pv = cross(d, e2), det = dot(e1, pv);
if (Math.abs(det) < 1e-14) return null;
const inv = 1 / det, s = sub(o, a), u = dot(s, pv) * inv;
if (u < -1e-9 || u > 1 + 1e-9) return null;
const q = cross(s, e1), v = dot(d, q) * inv;
if (v < -1e-9 || u + v > 1 + 1e-9) return null;
const t = dot(e2, q) * inv;
return t >= -TOL ? Math.max(t, 0) : null;
}
Box of a placed component
64-bit
The bounding box in the model of a component's faces and edges, from its own coordinates and its placement matrix.
X = (m₀x + m₄y + m₈z + m₁₂) ÷ w
Each point goes through the 4 by 4 matrix in 64-bit numbers; a zero w is replaced by 1. The box is the minimum and maximum of the transformed points.
m3d/collide.js
lines 129 to 144
CadCraft 0.8.2
/** The world box of a placement's faces and edges in the way (all of them: `whole`), from its own-space arrays. */
function placedBox(o, whole) {
const { m, L } = o.P;
let x0 = Infinity, y0 = Infinity, z0 = Infinity, x1 = -Infinity, y1 = -Infinity, z1 = -Infinity;
const put = (x, y, z) => {
const w = m[3] * x + m[7] * y + m[11] * z + m[15] || 1;
const X = (m[0] * x + m[4] * y + m[8] * z + m[12]) / w, Y = (m[1] * x + m[5] * y + m[9] * z + m[13]) / w, Z = (m[2] * x + m[6] * y + m[10] * z + m[14]) / w;
if (X < x0) x0 = X; if (X > x1) x1 = X; if (Y < y0) y0 = Y; if (Y > y1) y1 = Y; if (Z < z0) z0 = Z; if (Z > z1) z1 = Z;
};
if (whole) { const T = L.pts; for (let i = 0; i < T.length; i += 3) put(T[i], T[i + 1], T[i + 2]); }
else {
for (const i of o.fi) for (const t of L.faces[i].tris) for (const p of t) put(p[0], p[1], p[2]);
for (const i of o.ei) { const e = L.edges[i]; put(e.a[0], e.a[1], e.a[2]); put(e.b[0], e.b[1], e.b[2]); }
}
return x0 <= x1 ? { min: [x0, y0, z0], max: [x1, y1, z1] } : null;
}
In detail
Method
Sampling along the path, then bisection. Edge against face by plane distances and a point-in-triangle test; point inside a solid by three rays that must all cross the surface an odd number of times; ray against triangle by two edge vectors and a determinant.
Number types
64-bit numbers in arrays of three.
Tolerances
Touching distance 1e-5 model units, absolute (the code comment calls it 10 µm). Barycentric slack 1e-9. A ray is parallel to a triangle below |det| 1e-14. Triangles with squared normal below 1e-24 are skipped. At most 160 samples; 24 bisections.
Limits
Translations only; rotate and scale are not checked. Solids already overlapping at the start are ignored. The tolerances do not scale with the size of the model.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.