Rebuilds a mesh as an even closed mesh at a chosen voxel size, and moves vertices onto the nearest point of another surface.
How the precision is kept
Distances from grid points to the mesh's triangles are computed in 64-bit but kept in a Float32Array, and the level set that makes the new mesh is fed by interpolating those 32-bit samples. The new surface is in any case an approximation at the voxel size. Snapping vertices onto a surface is 64-bit throughout.
Open item. Keep the distance samples in a Float64Array so the level set is not fed 32-bit values.
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.
mesh/remesh.jsModelCraft 0.8.1 32-bit in part5 calculationsReviewed
Tests tools/modelcraft-test/mesh.mjs
Squared distance to a triangle
64-bit
The squared distance from a point to the nearest point of a triangle.
q = nearest point by region (vertex, edge or interior); d² = |p − q|²
The region is chosen by comparing dot products and their 2 × 2 determinants with zero, with no tolerance. The interior case divides by v_a + v_b + v_c without a guard; that sum is zero only for a triangle of zero area.
For every grid point within two voxels of a triangle, the distance to the nearest triangle.
g = voxel ÷ 2; d(i, j, k) = √(min over triangles of d²), capped at 2·voxel
Each squared distance is computed in 64-bit, then compared with and stored in a Float32Array, and the square root is taken in place in that array, so a sample is rounded to 32-bit twice. Grid points that no triangle reaches keep the fill value (2 × voxel)².
mesh/remesh.js
lines 67 to 87
ModelCraft 0.8.1
const g = voxel / 2, pad = 2 * voxel;
const min = [b.min[0] - pad, b.min[1] - pad, b.min[2] - pad];
const nx = Math.ceil((b.max[0] - b.min[0] + 2 * pad) / g) + 1, ny = Math.ceil((b.max[1] - b.min[1] + 2 * pad) / g) + 1, nz = Math.ceil((b.max[2] - b.min[2] + 2 * pad) / g) + 1;
if (nx * ny * nz > 24e6) throw new Error('grid');
const band = 2 * voxel, far = band * band;
const d = new Float32Array(nx * ny * nz).fill(far);
const at = (i, j, k) => (k * ny + j) * nx + i;
// the band: each triangle against the grid points in its box grown by the band
for (let t = 0; t < n; t++) {
const a = tri[t * 3], bb = tri[t * 3 + 1], c = tri[t * 3 + 2];
let lo = [Infinity, Infinity, Infinity], hi = [-Infinity, -Infinity, -Infinity];
for (const v of [a, bb, c]) for (let q = 0; q < 3; q++) { lo[q] = Math.min(lo[q], P[v * 3 + q]); hi[q] = Math.max(hi[q], P[v * 3 + q]); }
const i0 = Math.max(0, Math.floor((lo[0] - band - min[0]) / g)), i1 = Math.min(nx - 1, Math.ceil((hi[0] + band - min[0]) / g));
const j0 = Math.max(0, Math.floor((lo[1] - band - min[1]) / g)), j1 = Math.min(ny - 1, Math.ceil((hi[1] + band - min[1]) / g));
const k0 = Math.max(0, Math.floor((lo[2] - band - min[2]) / g)), k1 = Math.min(nz - 1, Math.ceil((hi[2] + band - min[2]) / g));
for (let k = k0; k <= k1; k++) for (let j = j0; j <= j1; j++) for (let i = i0; i <= i1; i++) {
const idx = at(i, j, k), q = dist2Tri(min[0] + i * g, min[1] + j * g, min[2] + k * g, P, a, bb, c);
if (q < d[idx]) d[idx] = q;
}
}
for (let i = 0; i < d.length; i++) d[i] = Math.sqrt(d[i]);
Inside or outside
64-bit
Marks each grid point as inside or outside the mesh by counting the faces a ray along +x crosses.
crossing when w₀, w₁, w₂ share a sign; x = (w₀·x_A + w₁·x_B + w₂·x_C) ÷ (w₀ + w₁ + w₂); inside when the winding count before x is above 0
The three edge functions are plain 64-bit cross products of coordinates taken relative to the row, compared with zero without exact arithmetic. To keep rows off mesh edges each row is shifted by 3.1e-7 × the box diagonal in y and 1.7 times that in z, so the sign is tested slightly off the sample's own position.
mesh/remesh.js
lines 95 to 113
ModelCraft 0.8.1
const jit = size * 3.1e-7; // off the grid rows a little, so a row never runs exactly along an edge
for (let k = 0; k < nz; k++) for (let j = 0; j < ny; j++) {
const y = min[1] + j * g + jit, z = min[2] + k * g + jit * 1.7, xs = [];
tree.ray([min[0] - g, y, z], [1, 0, 0], (t) => {
// the ray x = s, (y, z) fixed: does it pass through triangle t, and where?
const A = tri[t * 3], B = tri[t * 3 + 1], C = tri[t * 3 + 2];
const ay = P[A * 3 + 1] - y, az = P[A * 3 + 2] - z, by = P[B * 3 + 1] - y, bz = P[B * 3 + 2] - z, cy = P[C * 3 + 1] - y, cz = P[C * 3 + 2] - z;
const w0 = by * cz - bz * cy, w1 = cy * az - cz * ay, w2 = ay * bz - az * by;
if (!((w0 >= 0 && w1 >= 0 && w2 >= 0) || (w0 <= 0 && w1 <= 0 && w2 <= 0))) return;
const s = w0 + w1 + w2; // twice the triangle's area seen along x, signed like its normal's x
if (Math.abs(s) < 1e-30) return;
xs.push([(w0 * P[A * 3] + w1 * P[B * 3] + w2 * P[C * 3]) / s, s < 0 ? 1 : -1]);
});
xs.sort((p, q) => p[0] - q[0]);
let c = 0, wind = 0;
for (let i = 0; i < nx; i++) {
const x = min[0] + i * g;
while (c < xs.length && xs[c][0] < x) wind += xs[c++][1];
if (wind > 0) d[at(i, j, k)] = -d[at(i, j, k)]; // inside: negative here, turned for manifold below
Level set of the samples
32-bit in part
The distance at any point by blending the eight samples round it, handed to the library that builds the new mesh.
f(x, y, z) = −trilinear blend of the 8 samples; new mesh = level set of f at 0 with edge length = voxel
The blend is 64-bit arithmetic on samples read from the Float32Array, with indices clamped to the grid. The new vertices are copied as they come from the library's vertex array into a new mesh.
Moves each listed vertex to the nearest point of a target surface.
The nearest point comes from nearestOnTris in mesh/modifiers.js as 64-bit coordinates and is written to the mesh unchanged. A vertex for which no point is found stays where it is.
mesh/remesh.js
lines 149 to 159
ModelCraft 0.8.1
/** Put each vertex on the surface (one undo step's worth: run it inside a mesh edit). */
export function projectVerts(m, verts, near) {
let n = 0;
for (const v of verts) {
if (m.vertDead(v)) continue;
const h = near([m.P[v * 3], m.P[v * 3 + 1], m.P[v * 3 + 2]]);
if (!h) continue;
m.setPos(v, h.q[0], h.q[1], h.q[2]); n++;
}
return n;
}
In detail
Method
Signed distance on a grid of half the voxel size: exact point-to-triangle distance (Ericson, 5.1.5, as cited in the code) within two voxels of the surface, sign by a winding count of crossings along +x rows, then the Manifold library's level set at level 0 with the voxel as edge length.
Number types
Float32Array for the distance samples; Float64Array for triangle boxes and positions; 64-bit arithmetic for each distance and crossing.
Tolerances
The sign rows are shifted by 3.1e-7 × the box diagonal in y and 1.7 times that in z; a triangle whose projected area along x is below 1e-30 in absolute value is skipped; the grid may hold at most 24 million samples.
Limits
The voxel size sets how closely the new mesh follows the old one. Samples farther than two voxels from the surface all hold two voxels. Each sample carries about 7 digits.
Approach: 32-bit step, flagged
One step stores or exchanges 32-bit values that reach a number a person reads. It is listed here with its open item, and the step is either moved to 64-bit or the app will warn where the number is read.