CadCraft™ v0.8.1
Use it now
Menu

Resources Numerical accuracy Calculation policy

Box tree for picking and collisions

Finds which items have a box that a point range or a ray touches, for picking, snapping and collision checks.

How the precision is kept

Boxes, centers and node boxes are Float64Array, and every test is a 64-bit comparison. The tree only narrows down candidates; the exact test for an item is done by the caller.

Calculations under this policy

2 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.

m3d/bvh.js CadCraft 0.8.2 64-bit 2 calculations Reviewed

Tests None found by the review

Ray against boxes

64-bit

Calls back for every item whose box a ray passes through.

t₀ = max(nearₐ), t₁ = min(farₐ); hit if t₀ ≤ t₁

Slab test in 64-bit with the inverse direction 1 / d. If a slab distance is NaN (origin on a slab plane with zero direction) the ray is kept only if the origin lies inside that slab. The test is on boxes, not on the item itself.

  • m3d/bvh.js
  • lines 84 to 99
  • CadCraft 0.8.2
ray(o, d, cb, tmax = Infinity) {
  const ix = 1 / d[0], iy = 1 / d[1], iz = 1 / d[2];
  return this.walk((lo, hi) => {
    let t0 = 0, t1 = typeof tmax === 'number' ? tmax : tmax.t;
    for (let a = 0; a < 3; a++) {
      const inv = a === 0 ? ix : a === 1 ? iy : iz;
      let n = (lo[a] - o[a]) * inv, f = (hi[a] - o[a]) * inv;
      if (Number.isNaN(n) || Number.isNaN(f)) { if (o[a] < lo[a] || o[a] > hi[a]) return false; continue; }   // along a side
      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;
  }, cb);
}

Boxes of point lists

64-bit

The box of each item from its points, grown by a pad.

Min and max over the points in 64-bit, with the pad subtracted and added; stored in a Float64Array. An item with no points gets infinite limits.

  • m3d/bvh.js
  • lines 117 to 130
  • CadCraft 0.8.2
/** Boxes (6 per item) for lists of points: pts(i) → array of [x, y, z]; n items. */
export function boxesOf(n, pts, pad = 0) {
  const b = new Float64Array(n * 6);
  for (let i = 0; i < n; i++) {
    let x0 = Infinity, y0 = Infinity, z0 = Infinity, x1 = -Infinity, y1 = -Infinity, z1 = -Infinity;
    for (const p of pts(i)) {
      if (p[0] < x0) x0 = p[0]; if (p[1] < y0) y0 = p[1]; if (p[2] < z0) z0 = p[2];
      if (p[0] > x1) x1 = p[0]; if (p[1] > y1) y1 = p[1]; if (p[2] > z1) z1 = p[2];
    }
    const o = i * 6;
    b[o] = x0 - pad; b[o + 1] = y0 - pad; b[o + 2] = z0 - pad; b[o + 3] = x1 + pad; b[o + 4] = y1 + pad; b[o + 5] = z1 + pad;
  }
  return b;
}

In detail

Method
Median split of box centers along the longest side, leaf size 6; ray against box by the slab method with inverse direction.
Number types
Float64Array boxes and node boxes, Uint32Array and Int32Array indexes.
Tolerances
None: box and ray tests use exact comparisons, so a touching box counts as a hit. A zero direction component gives an infinite inverse; a 0 times infinity NaN is handled by testing whether the origin is within that slab.

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.

Every policy that takes this approach