Evaluates a spline, builds one through fit points or from control points, turns it into points for drawing and measuring, and inserts control points without changing the curve.
How the precision is kept
A point on the curve is computed by de Boor's algorithm in 64-bit, in weighted form for rational splines. Wherever the curve is used as points (drawing, converting to a polyline) the number of pieces is set by a rule, so those results are approximations of the curve. The end of the parameter range is evaluated a hair inside the range.
Open item. Evaluate the last point of a spline at the end of its range exactly, not 1e-12 of the range before it.
Calculations under this policy
12 calculations in 2 source files. 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.
de Boor: dⱼ = (1 − a)·dⱼ₋₁ + a·dⱼ, a = (u − kᵢ) ÷ (kᵢ₊ₚ₋ᵣ₊₁ − kᵢ); point = (Σ w·P) ÷ Σ w
Convex combinations in 64-bit, so nothing is subtracted except the knots. A parameter at or past the top of the range is moved to 1e-12 × max(1, range) below it, so the end point returned differs from the true end by that parameter step times the curve's speed there. A zero knot interval is treated as a = 0.
spline.js
lines 95 to 111
CadCraft 0.8.2
/** The curve at parameter u (de Boor; rational when `weights` are not all 1). */
export function pointAt(e, u) {
const p = e.degree, n = e.ctrl.length, k = e.knots;
const [lo, hi] = [k[p], k[n]];
if (u <= lo) u = lo;
if (u >= hi) u = hi - 1e-12 * Math.max(1, Math.abs(hi - lo));
let span = p;
while (span < n - 1 && u >= k[span + 1]) span++;
const w = e.weights;
const d = [];
for (let j = 0; j <= p; j++) { const q = e.ctrl[span - p + j], wt = w ? w[span - p + j] : 1; d.push([q.x * wt, q.y * wt, wt]); }
for (let r = 1; r <= p; r++) for (let j = p; j >= r; j--) {
const i = span - p + j, den = k[i + p - r + 1] - k[i], a = den === 0 ? 0 : (u - k[i]) / den;
d[j] = [(1 - a) * d[j - 1][0] + a * d[j][0], (1 - a) * d[j - 1][1] + a * d[j][1], (1 - a) * d[j - 1][2] + a * d[j][2]];
}
return P(d[p][0] / d[p][2], d[p][1] / d[p][2]);
}
Clamped knots
Exact
The knot list for a spline that starts and ends on its first and last control points.
p + 1 zeros, 1 … n − p − 1, p + 1 values of n − p
The knots are whole numbers pushed in order, with no arithmetic beyond counting, so a spline made here has exact knot values.
spline.js
lines 37 to 44
CadCraft 0.8.2
/** Clamped uniform knots for n control points of degree p: p + 1 zeros, 1 … n − p − 1, p + 1 of n − p. */
export function clampedKnots(n, p) {
const k = [];
for (let i = 0; i <= p; i++) k.push(0);
for (let i = 1; i < n - p; i++) k.push(i);
for (let i = 0; i <= p; i++) k.push(n - p);
return k;
}
Spline through fit points
64-bit
Builds the spline that passes through the points picked.
two points: control points at 0, ⅓, ⅔ and 1 of the segment; more: clamped cubic with chord-length parameters
Neighboring points within 1e-9 drawing units, an absolute limit, are dropped first. End tangents are passed to the solver as unit directions; a closed curve leaves and arrives along the chord across the join. The control points come from fitSplineControl of dwg/spline-fit.js.
spline.js
lines 46 to 74
CadCraft 0.8.2
/** A spline through fit points: a clamped cubic with chord-length parameters (the same one a DWG's fit-point spline means). */
export function fitSpline(fit, { closed = false, st = null, et = null, degree = 3 } = {}) {
let pts = clean(fit);
// drop repeated neighbours: the curve cannot pass the same place twice in a row
pts = pts.filter((p, i) => i === 0 || dist(p, pts[i - 1]) > 1e-9);
if (closed && pts.length > 2 && dist(pts[0], pts[pts.length - 1]) <= 1e-9) pts.pop();
if (pts.length < 2) return null;
if (pts.length === 2) { // a straight curve through two points: a degree-1 spline would not be a spline any more, keep a cubic with its control points on the line
const [a, b] = pts;
const ctrl = [a, P(a.x + (b.x - a.x) / 3, a.y + (b.y - a.y) / 3), P(a.x + 2 * (b.x - a.x) / 3, a.y + 2 * (b.y - a.y) / 3), b];
return { type: 'spline', degree: 3, closed: false, fit: pts, ctrl, knots: clampedKnots(4, 3) };
}
const us = unit(st || P(0, 0)), ue = unit(et || P(0, 0)); // the end derivatives are given to the solver as unit directions
st = us; et = ue;
let q = pts, t0 = st ? { x: st.x, y: st.y, z: 0 } : null, t1 = et ? { x: et.x, y: et.y, z: 0 } : null;
if (closed) {
// a closed curve: the first point again at the end, both ends leaving along the chord across the join (one smooth curve)
const a = pts[pts.length - 1], b = pts[0], c = pts[1];
const dir = unit(P(c.x - a.x, c.y - a.y)) || P(1, 0);
q = [...pts, P(b.x, b.y)];
t0 = { x: dir.x, y: dir.y, z: 0 }; t1 = { x: dir.x, y: dir.y, z: 0 };
}
const r = fitSplineControl(q.map((p) => ({ x: p.x, y: p.y, z: 0 })), degree, t0, t1, 0);
if (!r) return null;
const e = { type: 'spline', degree: 3, closed: !!closed, fit: pts, ctrl: r.control.map((p) => P(p.x, p.y)), knots: r.knots };
if (st && !closed) e.st = P(st.x, st.y);
if (et && !closed) e.et = P(et.x, et.y);
return e;
}
Spline from control points
64-bit
Builds a spline with a given control polygon, clamped or closed.
closed: control points wrapped by the degree, knots 0, 1, 2, …
Control points are kept as given. Weights are kept only when at least one differs from 1 by more than 1e-12. A closed spline uses uniform whole-number knots.
spline.js
lines 76 to 87
CadCraft 0.8.2
/** A spline with a control polygon. Closed: the polygon wraps (periodic, uniform knots). */
export function cvSpline(ctrl, { degree = 3, closed = false, weights = null } = {}) {
const c = clean(ctrl);
const p = Math.max(1, Math.min(5, degree | 0 || 3));
const w = Array.isArray(weights) && weights.length === c.length && weights.every((x) => Number.isFinite(x) && x > 0) && weights.some((x) => Math.abs(x - 1) > 1e-12) ? weights.slice() : null;
if (c.length < p + 1 || (closed && c.length < 3)) return null;
if (!closed) return { type: 'spline', degree: p, closed: false, ctrl: c, knots: clampedKnots(c.length, p), ...(w ? { weights: w } : {}) };
const wrap = c.concat(c.slice(0, p)), ww = w ? w.concat(w.slice(0, p)) : null;
const knots = [];
for (let i = 0; i < wrap.length + p + 1; i++) knots.push(i);
return { type: 'spline', degree: p, closed: true, periodic: true, ctrl: wrap, knots, ...(ww ? { weights: ww } : {}) };
}
A spline as points
64-bit
The curve as a list of points for drawing and for anything that works from points.
pieces per span = max(4·max(1, p − 1), ⌈√(polygon length ÷ tol)⌉), within a budget of 4000
The piece count comes from a rule based on the control polygon's length; the distance from the true curve is not measured. With no tolerance given it is 0.0004 × the larger extent of the control points. The last point is replaced by pointAt at the end of the range.
spline.js
lines 121 to 148
CadCraft 0.8.2
/** The curve as points: each span in as many pieces as keep it within `tol` of the true curve (flatness by the control polygon). */
export function points(e, { tol = 0 } = {}) {
const key = tol > 0 ? tol : 0;
const hit = cache.get(e);
if (hit && hit.key === key) return hit.pts;
const pts = [];
if (!valid(e)) { cache.set(e, { key, pts }); return pts; }
const sp = spans(e);
const ctrl = e.ctrl;
const w = Math.max(...ctrl.map((q) => q.x)) - Math.min(...ctrl.map((q) => q.x)), h = Math.max(...ctrl.map((q) => q.y)) - Math.min(...ctrl.map((q) => q.y));
const size = Math.max(w, h, 1e-9);
const eps = key || size * 4e-4;
let budget = MAX_POINTS;
for (let s = 0; s < sp.length; s++) {
const [a, b] = sp[s];
// pieces from the length of the control polygon over this span: more bend = more pieces
const i0 = Math.min(e.ctrl.length - 1, e.degree + s);
let poly = 0;
for (let j = Math.max(0, i0 - e.degree); j < Math.min(e.ctrl.length - 1, i0); j++) poly += dist(e.ctrl[j], e.ctrl[j + 1]);
const n = Math.max(4 * Math.max(1, e.degree - 1), Math.min(Math.floor(budget / Math.max(1, sp.length - s)), Math.ceil(Math.sqrt(poly / eps))));
for (let i = s === 0 ? 0 : 1; i <= n; i++) pts.push(pointAt(e, a + (b - a) * (i / n)));
budget -= n;
}
// the closing point is the true end of the curve
if (pts.length) pts[pts.length - 1] = pointAt(e, domain(e)[1]);
cache.set(e, { key, pts });
return pts;
}
A spline as a polyline
64-bit
Points for converting a spline to a polyline, a set number of segments per knot span.
u = a + (b − a) × i ÷ n, n = 1 … 99 (10 unless given)
Vertices lie on the curve; between them the polyline is straight, so the result is an approximation set by n. On a closed spline a last point within 1e-9 of the first is dropped.
spline.js
lines 161 to 168
CadCraft 0.8.2
/** Points for a polyline: `precision` segments in each knot span (at least 1; PEDIT / SPLINEDIT › Convert to polyline). */
export function polyline(e, precision = 10) {
const n = Math.max(1, Math.min(99, precision | 0 || 10));
const sp = spans(e), out = [];
sp.forEach(([a, b], s) => { for (let i = s === 0 ? 0 : 1; i <= n; i++) out.push(pointAt(e, a + (b - a) * (i / n))); });
if (out.length) out[out.length - 1] = pointAt(e, domain(e)[1]);
return e.closed && out.length > 2 && dist(out[0], out[out.length - 1]) < 1e-9 ? out.slice(0, -1) : out;
}
Adding a control point
64-bit
The same curve with one more control point at a parameter.
Qᵢ = (1 − a)·Pᵢ₋₁ + a·Pᵢ, a = (u − kᵢ) ÷ (kᵢ₊ₚ − kᵢ), in weighted form
Convex combinations of weighted control points, divided back by the weight. The parameter must be more than 1e-12 inside the range. The curve is unchanged in exact arithmetic; in 64-bit the new control points carry one rounding each.
spline.js
lines 240 to 267
CadCraft 0.8.2
/**
* The same curve with one more control point at parameter u (Boehm knot insertion) — SPLINEDIT › Refine › Add control point.
* Fit data is dropped (the curve now has more control points than fit points describe).
*/
export function insertKnot(e, u) {
const p = e.degree, k = e.knots, n = e.ctrl.length;
const [lo, hi] = domain(e);
if (!(u > lo + EPS && u < hi - EPS)) return e;
let s = p;
while (s < n - 1 && u >= k[s + 1]) s++;
const w = e.weights || e.ctrl.map(() => 1);
const Q = [], W = [];
const hom = (i) => [e.ctrl[i].x * w[i], e.ctrl[i].y * w[i], w[i]];
for (let i = 0; i <= n; i++) {
if (i <= s - p) { Q.push(hom(i)); continue; }
if (i > s) { Q.push(hom(i - 1)); continue; }
const den = k[i + p] - k[i], a = den === 0 ? 0 : (u - k[i]) / den;
const A = hom(i - 1), B = hom(i);
Q.push([(1 - a) * A[0] + a * B[0], (1 - a) * A[1] + a * B[1], (1 - a) * A[2] + a * B[2]]);
}
const knots = [...k.slice(0, s + 1), u, ...k.slice(s + 1)];
const ctrl = Q.map((q) => P(q[0] / q[2], q[1] / q[2]));
const rational = Q.some((q) => Math.abs(q[2] - 1) > 1e-12);
W.push(...Q.map((q) => q[2]));
const { fit, st, et, ...rest } = e;
void fit; void st; void et;
return { ...rest, ctrl, knots, ...(rational ? { weights: W } : { weights: undefined }) };
}
Reversing a spline
64-bit
The same curve run the other way.
knot′ = (first + last) − knot, in reverse order
Control points and weights are reversed unchanged. Each knot is reflected with one subtraction, which is exact for the whole-number knots made here and rounded for others.
spline.js
lines 214 to 221
CadCraft 0.8.2
export function reverse(e) {
const k = e.knots, hi = k[k.length - 1] + k[0];
const knots = k.map((x) => hi - x).reverse();
const out = { ...e, ctrl: e.ctrl.slice().reverse(), knots };
if (e.weights) out.weights = e.weights.slice().reverse();
if (e.fit) { out.fit = e.fit.slice().reverse(); if (e.st || e.et) { out.st = e.et ? P(-e.et.x, -e.et.y) : undefined; out.et = e.st ? P(-e.st.x, -e.st.y) : undefined; if (!out.st) delete out.st; if (!out.et) delete out.et; } }
return out;
}
Control-point spline to fit points
64-bit
Samples points on a spline and builds a fit-point spline through them.
n points evenly spaced in the parameter (12 unless given, at least 3)
The result passes through the sampled points but is a new curve: between them it need not follow the original.
spline.js
lines 223 to 229
CadCraft 0.8.2
/** Sample n fit points on the curve (evenly in parameter): a spline given by control points becomes a fit-point one. */
export function toFit(e, n = 12) {
const [a, b] = domain(e), pts = [];
const m = Math.max(3, n);
for (let i = 0; i < m; i++) pts.push(pointAt(e, a + (b - a) * (e.closed ? i / m : i / (m - 1))));
return fitSpline(pts, { closed: e.closed });
}
Where along the curve a new control point is added.
nearest of 401 samples evenly spaced in the parameter
The parameter is the best of 401 samples, not the true nearest point of the curve; it is off by up to half a sample step.
spline-cmd.js
lines 194 to 195
CadCraft 0.8.2
for (let i = 0; i <= 400; i++) { const u = lo + (hi - lo) * (i / 400), q = S.pointAt(e, u), d = dist(q, p); if (d < bd) { bd = d; bu = u; } }
const n = S.insertKnot(e, bu);
Arc as a polyline segment
64-bit
Turns an arc into a two-point polyline with a bulge.
ends = c + r(cos a, sin a); bulge = tan((a₁ − a₀) ÷ 4)
The end angle is raised by whole turns until it is above the start, then one tangent gives the bulge. The center and radius are no longer stored: they are implied by the two computed end points and the bulge.
A polyline redrawn as a smooth curve through or along its vertices, kept as many short segments.
8 segments per knot span unless given
The stored polyline is the curve sampled at a fixed count per span, so its length and area are those of the short segments. The original corners are kept in frame and can be restored.
spline-cmd.js
lines 230 to 239
CadCraft 0.8.2
/** Fit curve / spline curve through (or along) a polyline's vertices, as a polyline with many short segments; the corners stay in `frame`. */
export function curvePoly(e, kind, perSpan = 8) {
const frame = (e.frame || e.pts).map((p) => ({ x: p.x, y: p.y, b: 0 }));
if (frame.length < 3) return e;
const sp = kind === 'fit' ? S.fitSpline(frame, { closed: !!e.closed }) : S.cvSpline(frame, { degree: kind === 'quad' ? 2 : 3, closed: !!e.closed });
if (!sp) return e;
const pts = S.polyline(sp, perSpan).map((p) => ({ x: p.x, y: p.y, b: 0 }));
if (pts.length < 2) return e;
return { ...e, pts, frame, curve: kind };
}
In detail
Method
de Boor evaluation; Boehm knot insertion (named in the code's comment); fit-point splines as a clamped cubic with chord-length parameters, solved by dwg/spline-fit.js.
Number types
64-bit numbers; knots of splines made here are whole numbers.
Tolerances
EPS = 1e-12 for zero-length knot spans and vectors (absolute). Repeated fit points within 1e-9 are dropped. Weights within 1e-12 of 1 count as 1. Top of the range is evaluated at 1e-12 × max(1, range) below the end. Drawing tolerance, when none is given, is 0.0004 × the control polygon's larger extent.
Limits
points() chooses the piece count as ⌈√(control polygon length ÷ tolerance)⌉ per span, a rule of thumb and not a computed bound; at most about 4000 points. Converting to a polyline uses a fixed count of segments per knot span.
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.