Finds the height of the tool tip over the part for parallel and scallop finishing, and the spacing of passes for a given cusp height.
How the precision is kept
The tool is dropped onto the part's display mesh, whose vertices have 32-bit precision, and the first search runs on a height grid stored in a Float32Array; a grid sample can be the value returned. Refinement on facets and on triangle edges is 64-bit arithmetic on the same vertices. Lines are subdivided until the mid-point lies within half the tolerance of the chord. The resulting heights are the Z values of the finishing moves.
Open item. Store the drop-cutter height grid in a Float64Array and take surface heights from the exact faces or a 64-bit mesh, so finishing Z values do not start from 32-bit numbers.
Calculations under this policy
14 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.
cam-finish.jsPartCraft 0.8.1 32-bit in part14 calculationsReviewed
Tests tools/partcraft-test/test-cam-finish.mjs
Height grid of the part
32-bit in part
Samples the part's top surface on a grid for the first search of the tool-tip height.
H[i, j] = height at cell center; cell = max(0.02, R ÷ 8)
The heights are stored in a Float32Array, which rounds each sample to about 7 significant digits, up or down. The header's statement that every value is a point of the real surface therefore holds only to 32-bit rounding.
The lowest height at which the tool at (x, y) touches the part without cutting into it.
z = max(H − h(ρ)) over grid samples within R; refine at ρ* = A + r_c s ÷ √(1 + s²) uphill; then max over triangle edges by ternary search; result = max(z + leave, floor)
The starting value comes from the 32-bit grid and stays if neither refinement finds a higher contact. Refinement accepts a new contact only when it is higher by more than 1e-12 and runs at most 6 times. The edge search runs 44 ternary steps on a function with a penalty of 1e6 per mm beyond the tool radius.
cam-finish.js
lines 65 to 118
PartCraft 0.8.1
/** Tool-tip height at (x, y) (−Infinity when no model is within reach). */
tip(x, y) {
const { R, c, nx, ny, x0, y0, H, prof, model } = this;
let best = model.heightAt(x, y), qx = x, qy = y;
const i0 = Math.max(0, Math.floor((x - R - x0) / c)), i1 = Math.min(nx - 1, Math.floor((x + R - x0) / c));
const j0 = Math.max(0, Math.floor((y - R - y0) / c)), j1 = Math.min(ny - 1, Math.floor((y + R - y0) / c));
for (let j = j0; j <= j1; j++) {
const dy = y0 + (j + 0.5) * c - y;
for (let i = i0; i <= i1; i++) {
const hh = H[j * nx + i];
if (hh === -Infinity) continue;
const dx = x0 + (i + 0.5) * c - x;
const rho = hyp(dx, dy);
if (rho > R) continue;
const v = hh - prof.h(rho);
if (v > best) { best = v; qx = x + dx; qy = y + dy; }
}
}
if (best === -Infinity) return -Infinity;
for (let it = 0; it < 6; it++) {
const pl = model.topPlane(qx, qy);
if (!pl) break;
const s = hyp(pl.gx, pl.gy);
let rx = x, ry = y;
if (s > 1e-9) { const rho = this.A + (this.rc * s) / Math.sqrt(1 + s * s); rx = x + (rho * pl.gx) / s; ry = y + (rho * pl.gy) / s; }
const rho = hyp(rx - x, ry - y);
const hq = model.heightAt(rx, ry);
if (hq === -Infinity || rho > R + 1e-9) break;
const v = hq - prof.h(Math.min(rho, R));
if (v > best + 1e-12) { best = v; qx = rx; qy = ry; } else break;
}
// edge and vertex contacts of the triangles round the best contact: along an edge z is linear and h(ρ) is convex, so the
// value is concave in the position on the edge and a ternary search finds it (a position beyond the tool radius costs a steep penalty)
const rN = 3 * c, I = model.mesh.indices, P3 = model.mesh.positions;
for (const tr of model.trianglesIn(qx - rN, qy - rN, qx + rN, qy + rN)) {
for (let e = 0; e < 3; e++) {
const a = I[tr * 3 + e] * 3, b = I[tr * 3 + ((e + 1) % 3)] * 3;
const ax = P3[a], ay = P3[a + 1], az = P3[a + 2], bx = P3[b] - ax, by = P3[b + 1] - ay, bz = P3[b + 2] - az;
const f = (u) => { const rho = hyp(ax + bx * u - x, ay + by * u - y); return az + bz * u - (rho <= R ? prof.h(rho) : prof.h(R) + 1e6 * (rho - R)); };
let lo = 0, hi = 1;
for (let k = 0; k < 44; k++) {
const m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
if (f(m1) < f(m2)) lo = m1; else hi = m2;
}
for (const u of [(lo + hi) / 2, 0, 1]) {
const rho = hyp(ax + bx * u - x, ay + by * u - y);
if (rho > R + 1e-9) continue;
const v = az + bz * u - prof.h(Math.min(rho, R));
if (v > best) best = v;
}
}
}
return Math.max(best + this.leave, this.floor);
}
Slope filter
32-bit in part
Whether the surface under a point is within the slope range chosen for the operation.
s = √(g_x² + g_y²); tan(from) − 1e-9 ≤ s ≤ tan(to) + 1e-9
The slope is that of the mesh facet under the point, from cam.js. A facet's slope is constant across it, so the edge of a slope band follows facet boundaries.
cam-finish.js
lines 58 to 64
PartCraft 0.8.1
/** Is there model surface under (x, y) with a slope inside the asked range? */
ok(x, y) {
const p = this.model.topPlane(x, y);
if (!p) return false;
const s = hyp(p.gx, p.gy);
return s >= this.sMin && s <= this.sMax;
}
Finishing one straight line
64-bit
The 3D points of a straight pass over the part, dense enough to stay within the tolerance.
split a span while |z(mid) − (z₀ + z₁) ÷ 2| > tol ÷ 2
The tolerance test is made at each span's mid-point only, down to spans of 0.02 mm or 14 levels of halving, so a narrow feature between test points can be passed over. Ends of finishable stretches are found by 12 bisection steps.
cam-finish.js
lines 121 to 160
PartCraft 0.8.1
/** The pieces of the straight line a → b (2D) that can be finished: [[x, y, z] …] each, within tol of the true tip height. */
export function cutLine(dr, a, b, { tol = 0.01, ds = 0 } = {}) {
const L = hyp(b[0] - a[0], b[1] - a[1]);
const step = ds > 0 ? ds : Math.min(dr.R / 4, 1);
const at = (u) => [a[0] + (b[0] - a[0]) * u, a[1] + (b[1] - a[1]) * u];
const good = (u) => { const p = at(u); return dr.ok(p[0], p[1]); };
const pt = (u) => { const p = at(u); return [p[0], p[1], dr.tip(p[0], p[1])]; };
const n = Math.max(1, Math.ceil(L / step));
const runs = [];
let from = -1;
const edge = (bad, ok) => { for (let k = 0; k < 12; k++) { const m = (bad + ok) / 2; if (good(m)) ok = m; else bad = m; } return ok; };
for (let k = 0; k <= n; k++) {
const g = good(k / n);
if (g && from < 0) from = k;
if ((!g || k === n) && from >= 0) {
const last = g ? k : k - 1;
const u0 = from === 0 ? 0 : edge((from - 1) / n, from / n);
const u1 = last === n ? 1 : edge((last + 1) / n, last / n);
runs.push([u0, u1]);
from = -1;
}
}
const out = [];
for (const [u0, u1] of runs) {
if ((u1 - u0) * L < 1e-6) continue;
const m = Math.max(1, Math.ceil(((u1 - u0) * L) / step));
const line = [pt(u0)];
const rec = (p0, t0, p1, t1, depth) => {
if (depth < 14 && (t1 - t0) * L > 0.02) {
const tm = (t0 + t1) / 2, pm = pt(tm);
if (Math.abs(pm[2] - (p0[2] + p1[2]) / 2) > tol / 2) { rec(p0, t0, pm, tm, depth + 1); rec(pm, tm, p1, t1, depth + 1); return; }
}
line.push(p1);
};
let prev = line[0], tp = u0;
for (let k = 1; k <= m; k++) { const tk = u0 + ((u1 - u0) * k) / m, pk = pt(tk); rec(prev, tp, pk, tk, 0); prev = pk; tp = tk; }
out.push(thin(line, tol * 0.1));
}
return out;
}
Thinning a pass
64-bit
Drops points that lie on a straight run between their neighbors.
drop p when its distance to the line through the last kept point and the next point ≤ tol ÷ 10
Distance to an unbounded 3D line by projection. The dropped points move the path by at most a tenth of the tolerance each.
cam-finish.js
lines 161 to 176
PartCraft 0.8.1
/** Drop points that lie within eps of the line through their neighbours (a flat or straight run stays two points). */
function thin(pts, eps) {
if (pts.length < 3) return pts;
const keep = [pts[0]];
let a = pts[0];
for (let k = 1; k < pts.length - 1; k++) {
const b = pts[k + 1];
const ux = b[0] - a[0], uy = b[1] - a[1], uz = b[2] - a[2], L2 = ux * ux + uy * uy + uz * uz;
const p = pts[k];
const tt = L2 > 0 ? ((p[0] - a[0]) * ux + (p[1] - a[1]) * uy + (p[2] - a[2]) * uz) / L2 : 0;
const d = hyp(p[0] - a[0] - ux * tt, p[1] - a[1] - uy * tt, p[2] - a[2] - uz * tt);
if (d > eps) { keep.push(p); a = p; }
}
keep.push(pts[pts.length - 1]);
return keep;
}
Parallel pass lines
64-bit
The positions of the raster lines across the part at the chosen angle.
n = ceil((v₁ − v₀) ÷ (stepover × d) − 1e-9); line k at v₀ + (v₁ − v₀) k ÷ n
The model's box corners are projected on the pass direction with cos and sin of the angle; lines are evenly spaced between the extremes, each computed from the ends.
The height of the ridge left between two ball passes a given distance apart on a flat surface.
h = R − √(R² − (s ÷ 2)²)
For a spacing much smaller than the radius the two terms are nearly equal and their difference loses digits; the square root's argument is clamped at 0.
cam-finish.js
lines 243 to 244
PartCraft 0.8.1
/** Cusp height between two ball passes `s` apart on a flat surface: h = R − √(R² − (s/2)²). */
export const cuspHeight = (R, s) => R - Math.sqrt(Math.max(0, R * R - (s / 2) * (s / 2)));
Pass spacing for a cusp height
64-bit
The distance between passes that leaves ridges of a given height.
s = 2 √(2 R h − h²); s = 2 R when h ≥ R
One expression with no near-cancellation for a small cusp height, since 2Rh dominates h².
cam-finish.js
lines 245 to 246
PartCraft 0.8.1
/** The pass spacing that leaves cusps of height h: s = 2·√(2·R·h − h²). */
export const spacingFor = (R, h) => (h >= R ? 2 * R : 2 * Math.sqrt(2 * R * h - h * h));
Distance over the surface
64-bit
The distance along the part's top surface from the starting cells to every other cell.
A shortest-path search on a Float64Array grid; each cell's distance is a sum of step lengths. Paths are limited to the step directions of the table below, so a straight run in another direction comes out slightly long.
cam-finish.js
lines 296 to 331
PartCraft 0.8.1
/**
* Distance over the model's surface (mm along it, 32-direction steps: the length of a straight run is at most ≈ 0.5 % over) from the sources to every cell of the model's top surface. → {g (Float64Array, Infinity off the model), nx, ny, c, x0, y0}
*/
export function surfaceDistance(model, c, from, maxCells = 1.5e6) {
const b = model.box;
const w = b.max[0] - b.min[0], h = b.max[1] - b.min[1];
while ((w / c + 1) * (h / c + 1) > maxCells) c *= 1.25;
const nx = Math.max(1, Math.ceil(w / c)), ny = Math.max(1, Math.ceil(h / c)), x0 = b.min[0], y0 = b.min[1];
const H = new Float64Array(nx * ny);
let top = -Infinity;
for (let j = 0; j < ny; j++) for (let i = 0; i < nx; i++) { const z = model.heightAt(x0 + (i + 0.5) * c, y0 + (j + 0.5) * c); H[j * nx + i] = z; if (z > top) top = z; }
const g = new Float64Array(nx * ny).fill(Infinity);
const heap = new Heap();
const on = (i, j) => i >= 0 && j >= 0 && i < nx && j < ny && H[j * nx + i] > -Infinity;
for (let j = 0; j < ny; j++) for (let i = 0; i < nx; i++) {
if (!on(i, j)) continue;
const src = from === 'top' ? H[j * nx + i] >= top - 1e-6 : !(on(i - 1, j) && on(i + 1, j) && on(i, j - 1) && on(i, j + 1));
if (src) { g[j * nx + i] = 0; heap.push(0, j * nx + i); }
}
while (heap.size) {
const [d, k] = heap.pop();
if (d > g[k]) continue;
const i = k % nx, j = (k - i) / nx;
for (const { di, dj, via } of NB) {
const ii = i + di, jj = j + dj;
if (!on(ii, jj)) continue;
let clear = true;
for (const [a, b] of via) if (!on(i + a, j + b)) { clear = false; break; }
if (!clear) continue;
const k2 = jj * nx + ii;
const nd = d + hyp(di * c, dj * c, H[k2] - H[k]);
if (nd < g[k2]) { g[k2] = nd; heap.push(nd, k2); }
}
}
return { g, H, nx, ny, c, x0, y0, top };
}
Step directions of the distance search
Exact
The set of grid steps the surface-distance search may take.
all (di, dj) with |di|, |dj| ≤ 5 and no common factor
The loops run from −5 to 5, which gives 80 directions. The comment above the table describes steps up to 3 and 32 directions, and the comment on surfaceDistance repeats the 32; the code is the wider set.
cam-finish.js
lines 278 to 294
PartCraft 0.8.1
// Steps of the distance search: every (di, dj) with gcd 1 and |di|, |dj| ≤ 3 (32 directions, at most 9° apart), each with the cells
// the straight step passes through (all must be on the model).
const NB = (() => {
const gcd = (a, b) => (b ? gcd(b, a % b) : a);
const out = [];
for (let di = -5; di <= 5; di++) for (let dj = -5; dj <= 5; dj++) {
if ((!di && !dj) || gcd(Math.abs(di), Math.abs(dj)) !== 1) continue;
const n = Math.max(Math.abs(di), Math.abs(dj)), seen = new Set(), via = [];
for (let k = 1; k < 8 * n; k++) {
const a = Math.round((di * k) / (8 * n)), b = Math.round((dj * k) / (8 * n)), key = a + ',' + b;
if ((a === 0 && b === 0) || (a === di && b === dj) || seen.has(key)) continue;
seen.add(key); via.push([a, b]);
}
out.push({ di, dj, len: Math.hypot(di, dj), via });
}
return out;
})();
Lines of equal surface distance
64-bit
Traces the lines at a given surface distance, which become the scallop passes.
crossing on a cell edge at f = (level − a) ÷ (b − a)
Linear interpolation between two cell values on either side of the level, so the divisor is not zero. Cells with any corner off the model are skipped.
cam-finish.js
lines 333 to 389
PartCraft 0.8.1
/** Marching squares on the distance field at one level → polylines [[x, y] …] (closed ones repeat the first point). */
export function isoLines(F, level) {
const { g, nx, ny, c, x0, y0 } = F;
const segs = [];
const key = (i, j, o) => 2 * (j * nx + i) + o; // o 0: edge (i,j)–(i+1,j), 1: edge (i,j)–(i,j+1)
const pos = new Map();
const cross = (i, j, o) => {
const k = key(i, j, o);
let p = pos.get(k);
if (!p) {
const a = g[j * nx + i], bb = o === 0 ? g[j * nx + i + 1] : g[(j + 1) * nx + i];
const f = (level - a) / (bb - a);
p = [x0 + (i + 0.5 + (o === 0 ? f : 0)) * c, y0 + (j + 0.5 + (o === 1 ? f : 0)) * c];
pos.set(k, p);
}
return k;
};
for (let j = 0; j < ny - 1; j++) for (let i = 0; i < nx - 1; i++) {
const v00 = g[j * nx + i], v10 = g[j * nx + i + 1], v01 = g[(j + 1) * nx + i], v11 = g[(j + 1) * nx + i + 1];
if (!(v00 < Infinity && v10 < Infinity && v01 < Infinity && v11 < Infinity)) continue;
const m = (v00 < level ? 1 : 0) | (v10 < level ? 2 : 0) | (v11 < level ? 4 : 0) | (v01 < level ? 8 : 0);
if (m === 0 || m === 15) continue;
const eb = () => cross(i, j, 0), er = () => cross(i + 1, j, 1), et = () => cross(i, j + 1, 0), el = () => cross(i, j, 1);
const center = (v00 + v10 + v01 + v11) / 4 < level;
switch (m) {
case 1: case 14: segs.push([el(), eb()]); break;
case 2: case 13: segs.push([eb(), er()]); break;
case 3: case 12: segs.push([el(), er()]); break;
case 4: case 11: segs.push([er(), et()]); break;
case 6: case 9: segs.push([eb(), et()]); break;
case 7: case 8: segs.push([el(), et()]); break;
case 5: if (center) { segs.push([el(), et()], [eb(), er()]); } else { segs.push([el(), eb()], [er(), et()]); } break;
case 10: if (center) { segs.push([el(), eb()], [er(), et()]); } else { segs.push([el(), et()], [eb(), er()]); } break;
default: break;
}
}
const adj = new Map();
for (const [a, bb] of segs) { (adj.get(a) || adj.set(a, []).get(a)).push(bb); (adj.get(bb) || adj.set(bb, []).get(bb)).push(a); }
const used = new Set();
const ek = (a, bb) => (a < bb ? a + ':' + bb : bb + ':' + a);
const lines = [];
const walk = (start) => {
const keys = [start];
let cur = start;
for (;;) {
const next = (adj.get(cur) || []).find((n) => !used.has(ek(cur, n)));
if (next === undefined) break;
used.add(ek(cur, next));
keys.push(next); cur = next;
if (cur === start) break;
}
return keys;
};
for (const [k, nb] of adj) if (nb.length === 1) { const ks = walk(k); if (ks.length > 1) lines.push(ks); }
for (const [k] of adj) { const ks = walk(k); if (ks.length > 2) lines.push(ks); }
return lines.map((ks) => ks.map((k) => pos.get(k)));
}
Scallop spacing and levels
64-bit
The spacing of scallop passes from the cusp height, and the surface distances they are placed at.
R_b = ball or corner radius + leave; s = spacing(R_b, cusp); level k = (k + ½) s; grid cell = max(0.02, min(s ÷ 3, d ÷ 8))
Levels are multiples of the spacing computed by multiplication, capped just below the largest distance on the grid. The cusp relation is for a flat surface; on a curved surface the real cusp differs.
cam-finish.js
lines 417 to 427
PartCraft 0.8.1
const Rb = (tool.kind === 'ball' ? tool.d / 2 : tool.cornerR) + p.leave;
const s = spacingFor(Rb, p.height);
const F = surfaceDistance(model, Math.max(0.02, Math.min(s / 3, tool.d / 8)), p.from);
let gmax = 0;
for (let k = 0; k < F.g.length; k++) if (F.g[k] < Infinity && F.g[k] > gmax) gmax = F.g[k];
const nL = Math.max(1, Math.ceil(gmax / s - 1e-9));
const runs = [];
let passes = 0;
const side = F.c;
for (let k = 0; k < nL; k++) {
const level = Math.min((k + 0.5) * s, Math.max(gmax - 1e-6, F.c));
Simplifying a scallop pass
64-bit
Reduces the points of a 3D pass while staying within a quarter of the tolerance.
keep the point farthest from the chord when its distance > tolerance ÷ 4, then repeat on both halves
Distance to the chord segment in 3D, with the projection clamped to the segment.
cam-finish.js
lines 396 to 409
PartCraft 0.8.1
/** Douglas–Peucker in 3D. */
function simplify(pts, eps) {
if (pts.length < 3) return pts;
const keep = new Uint8Array(pts.length);
keep[0] = keep[pts.length - 1] = 1;
const stack = [[0, pts.length - 1]];
while (stack.length) {
const [i, j] = stack.pop();
let md = 0, mk = -1;
for (let k = i + 1; k < j; k++) { const d = perpDeviation(pts[i], pts[j], pts[k]); if (d > md) { md = d; mk = k; } }
if (mk >= 0 && md > eps) { keep[mk] = 1; stack.push([i, mk], [mk, j]); }
}
return pts.filter((_, k) => keep[k]);
}
Tool grown by the stock to leave
64-bit
Models stock to leave by making the cutter larger.
Drop cutter: z(x, y) = max over model points within the tool radius of (point height − tool profile height), as given in the file's header; refinement at ρ* = A + r_c s ÷ √(1 + s²) on the facet; ternary search on triangle edges. Scallop: surface distance by shortest paths on a grid, contours at multiples of the spacing s = 2 √(2 R h − h²).
Number types
Float32Array for the height grid; 64-bit numbers for the search; mesh vertices of 32-bit precision; Float64Array for the surface-distance grid.
Tolerances
Height grid cell max(0.02, R ÷ 8), coarsened by 1.25 until at most 3,000,000 cells. Refinement stops when the gain is at most 1e-12 or after 6 rounds. Ternary search 44 steps per edge. Line sampling every min(R ÷ 4, 1) mm, split while the mid-point is more than tolerance ÷ 2 off, down to 0.02 mm or 14 levels; points within tolerance ÷ 10 of a straight run dropped. Slope limits have 1e-9 slack.
Limits
The header states them: the tool center stays over the model, undercuts are not finished, no holder check. The surface is the mesh, so heights also carry its chord tolerance. Surface distance is measured along grid steps in a fixed set of directions.
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.