Resources Numerical accuracy Calculation policy

Sketch intersections with splines

Finds where a sketch spline crosses a line, an arc, a circle or another spline.

How the precision is kept

A spline has no closed-form intersection, so crossings are found by sampling and then refined. Against a line or circle a signed distance is sampled 24 times per knot span and each sign change is bisected down to adjacent 64-bit numbers. Against another spline the two curves are crossed as polylines of 48 segments per span and each hit is refined by Newton's method in two variables.

Calculations under this policy

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

sketch-intersect.js PartCraft 0.8.1 64-bit 3 calculations Reviewed Nov 6, 2026

Tests tools/partcraft-test/test-sketch-tools.mjs

Roots of a function along a span

64-bit

Finds the parameters where a signed distance along the spline is zero.

sample n steps; bisect each sign change until b − a ≤ 1e-16 × max(1, |a|)

Each sign change is bisected until the bracket cannot shrink further or 200 halvings are done, so a found root is at the resolution of 64-bit numbers. The comment above the function mentions a Newton polish; the code refines by bisection only. Roots are found only where the samples change sign or dip below the tolerance.

sketch-intersect.js
lines 121 to 151
PartCraft 0.8.1

/** Roots of f on [lo, hi] by sampling n steps, bisection on sign changes, Newton polish (numeric f′). */
function roots1(f, lo, hi, n, tolF) {
  const out = [];
  let u0 = lo, f0 = f(lo);
  if (Math.abs(f0) <= tolF * 1e-3) out.push(lo);
  let fPrev = null;
  for (let i = 1; i <= n; i++) {
    const u1 = lo + (hi - lo) * i / n, f1 = f(u1);
    if (f1 === 0) out.push(u1);
    else if (f0 !== 0 && (f0 < 0) !== (f1 < 0)) {
      let a = u0, b = u1, fa = f0;
      for (let it = 0; it < 200 && b - a > 1e-16 * Math.max(1, Math.abs(a)); it++) {
        const m = (a + b) / 2, fm = f(m);
        if (fm === 0) { a = b = m; break; }
        if ((fm < 0) === (fa < 0)) { a = m; fa = fm; } else b = m;
      }
      out.push((a + b) / 2);
    } else if (fPrev !== null && Math.abs(f0) < Math.abs(fPrev) && Math.abs(f0) < Math.abs(f1) && Math.abs(f0) <= tolF) {
      // a touch: |f| has a local minimum near zero between samples — refine the minimum (golden section)
      let a = lo + (hi - lo) * (i - 2) / n, b = u1;
      for (let it = 0; it < 100; it++) {
        const m1 = b - (b - a) * 0.618, m2 = a + (b - a) * 0.618;
        if (Math.abs(f(m1)) < Math.abs(f(m2))) b = m2; else a = m1;
      }
      const m = (a + b) / 2;
      if (Math.abs(f(m)) <= tolF * 1e-3) out.push(m);
    }
    fPrev = f0; u0 = u1; f0 = f1;
  }
  return out;
}

Spline against a line or circle

64-bit

Collects the spline parameters where it crosses a line or a circle, span by span.

24 samples per knot span of F(S(u)); line: F = signed distance; circle: F = |S − c| − r

The spline point is evaluated in 64-bit at each sample. The sampling density is fixed at 24 per knot span, whatever the span's length.

sketch-intersect.js
lines 153 to 157
PartCraft 0.8.1

function splineVsImplicit(cv, F, tolF) {
  const out = [];
  for (const [u0, u1] of SP.spans(cv.bs)) for (const u of roots1((u) => F(SP.pointAt(cv.bs, u)), u0, u1, 24, tolF)) out.push(u);
  return out;
}

Spline against spline

64-bit

The parameter pairs at which two splines cross.

Newton: [S₁′(u) −S₂′(v)] · (Δu, Δv) = −(S₁(u) − S₂(v))

Start values come from crossing two polylines of 48 segments per span. Newton runs at most 40 steps and stops when the step is under 1e-15 × max(1, |u| + |v|); a zero determinant ends it early. The pair is kept only if the two curve points then agree within 1e-9 × scale.

sketch-intersect.js
lines 159 to 192
PartCraft 0.8.1

function splineSpline(A, B, scale) {
  const sample = (cv) => {
    const pts = [];
    for (const [u0, u1] of SP.spans(cv.bs)) for (let i = 0; i < 48; i++) { const u = u0 + (u1 - u0) * i / 48; pts.push({ u, p: SP.pointAt(cv.bs, u) }); }
    const [, hi] = SP.domain(cv.bs);
    pts.push({ u: hi, p: SP.pointAt(cv.bs, hi) });
    return pts;
  };
  const pa = sample(A), pb = sample(B), out = [];
  for (let i = 0; i + 1 < pa.length; i++) {
    const a0 = pa[i].p, a1 = pa[i + 1].p;
    const ax0 = Math.min(a0[0], a1[0]), ax1 = Math.max(a0[0], a1[0]), ay0 = Math.min(a0[1], a1[1]), ay1 = Math.max(a0[1], a1[1]);
    for (let j = 0; j + 1 < pb.length; j++) {
      const b0 = pb[j].p, b1 = pb[j + 1].p;
      if (Math.max(b0[0], b1[0]) < ax0 || Math.min(b0[0], b1[0]) > ax1 || Math.max(b0[1], b1[1]) < ay0 || Math.min(b0[1], b1[1]) > ay1) continue;
      const x = lineLine({ a: a0, b: a1 }, { a: b0, b: b1 })[0];
      if (!x || x.ta < -0.01 || x.ta > 1.01 || x.tb < -0.01 || x.tb > 1.01) continue;
      let u = pa[i].u + (pa[i + 1].u - pa[i].u) * x.ta, v = pb[j].u + (pb[j + 1].u - pb[j].u) * x.tb;
      const [la, ha] = SP.domain(A.bs), [lb, hb] = SP.domain(B.bs);
      for (let it = 0; it < 40; it++) {
        const [p, dp] = SP.derivsAt(A.bs, u, 1), [q, dq] = SP.derivsAt(B.bs, v, 1);
        const r = [p[0] - q[0], p[1] - q[1]];
        const det = -dp[0] * dq[1] + dp[1] * dq[0];
        if (!det) break;
        const du = (-r[0] * -dq[1] + r[1] * -dq[0]) / det, dv = (dp[0] * -r[1] - dp[1] * -r[0]) / det;
        u = Math.max(la, Math.min(ha, u + du)); v = Math.max(lb, Math.min(hb, v + dv));
        if (Math.abs(du) + Math.abs(dv) < 1e-15 * Math.max(1, Math.abs(u) + Math.abs(v))) break;
      }
      const p = SP.pointAt(A.bs, u), q = SP.pointAt(B.bs, v);
      if (Math.hypot(p[0] - q[0], p[1] - q[1]) <= 1e-9 * scale) out.push({ ta: u, tb: v });
    }
  }
  return out;
}

In detail

Method: Sampling plus bisection on a scalar function per knot span; golden-section search for a touch; polyline crossing plus 2-D Newton on S₁(u) − S₂(v) = 0.
Number types: 64-bit numbers in plain arrays.
Tolerances: Bisection stops when the bracket is under 1e-16 × max(1, |u|) or after 200 halvings. A touch is accepted when |f| ≤ 1e-12 × scale after 100 golden-section steps. Newton stops when |Δu| + |Δv| < 1e-15 × max(1, |u| + |v|) or after 40 steps; the result is kept when the two points are within 1e-9 × scale.
Limits: Two crossings inside one sample step (1/24 of a span, or one polyline segment) can be missed. A curve that only touches a spline is found only when the sampled distance dips under the tolerance.

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.

Every policy that takes this approach