Resources Numerical accuracy Calculation policy
Builds and checks the knot vectors that NURBS curves and surfaces are defined on.
Knots are 64-bit numbers. Two knots are treated as one when they differ by no more than 1e-12 of the whole knot range, a relative tolerance. The clamping check compares end knots for exact equality. Binomial coefficients are built by whole-number addition.
6 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.
Tests tools/nurbs/test.mjs
How many times a value occurs in a knot vector.
count of |Uᵢ − u| ≤ tol × (U_last − U_first)
The tolerance is 1e-12 by default, scaled by the knot range, so the result does not depend on how the curve is parameterized.
export function multiplicity(U, u, tol = KTOL) {
const span = Math.max(1e-300, U[U.length - 1] - U[0]);
let m = 0;
for (const x of U) if (Math.abs(x - u) <= tol * span) m++;
return m;
}The different knot values with their multiplicities.
a knot joins the previous one when |x − u_prev| ≤ tol × range
Each knot is compared with the first value of the current group, not with its neighbor, so a run of slowly rising knots cannot chain beyond the tolerance. The group keeps its first value.
export function distinctKnots(U, tol = KTOL) {
const span = Math.max(1e-300, U[U.length - 1] - U[0]);
const out = [];
for (const x of U) {
const last = out[out.length - 1];
if (last && Math.abs(x - last.u) <= tol * span) last.m++;
else out.push({ u: x, m: 1 });
}
return out;
}A knot vector with evenly spaced interior knots.
uᵢ = a + (b − a) × i ÷ (inner + 1)
Each interior knot is computed from its index, not by repeated addition of a step. The end knots are a and b themselves.
/** A clamped knot vector with uniform interior knots for `count` control points of degree p on [a, b]. */
export function clampedUniform(count, p, a = 0, b = 1) {
const U = [];
for (let i = 0; i <= p; i++) U.push(a);
const inner = count - p - 1;
for (let i = 1; i <= inner; i++) U.push(a + (b - a) * i / (inner + 1));
for (let i = 0; i <= p; i++) U.push(b);
return U;
}Checks a knot vector read from a file: count, order, clamping and multiplicities.
Order is checked with plain comparisons and clamping with exact equality of the first and last p + 1 knots. Interior multiplicities use the relative 1e-12 grouping of distinctKnots.
export function knotProblem(U, p, count) {
if (!Array.isArray(U) || U.length !== count + p + 1) return 'nurbs.err.knots_count';
for (const x of U) if (typeof x !== 'number' || !Number.isFinite(x)) return 'nurbs.err.knots_value';
for (let i = 1; i < U.length; i++) if (U[i] < U[i - 1]) return 'nurbs.err.knots_order';
const a = U[0], b = U[U.length - 1];
if (!(b > a)) return 'nurbs.err.knots_value';
for (let i = 0; i <= p; i++) if (U[i] !== a || U[U.length - 1 - i] !== b) return 'nurbs.err.knots_clamp';
// an interior knot may repeat at most p times (p + 1 would break the curve in two)
for (const k of distinctKnots(U)) if (k.u !== a && k.u !== b && k.m > p) return 'nurbs.err.knots_mult';
return null;
}One parameter value per control point.
gᵢ = (Uᵢ₊₁ + … + Uᵢ₊ₚ) ÷ p
p knots are added in order and divided once. For degree 0 the mean of two knots is used.
export function greville(U, p, count) {
const out = new Array(count);
for (let i = 0; i < count; i++) { let s = 0; for (let k = 1; k <= p; k++) s += U[i + k]; out[i] = p ? s / p : (U[i] + U[i + 1]) / 2; }
return out;
}The number of ways to choose k of n.
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)
Rows of Pascal's triangle are built by adding whole numbers and kept in a table. The values are exact up to 2⁵³; the file does not check for that bound.
export function binomial(n, k) {
for (let r = BIN.length; r <= n; r++) {
const row = [1];
for (let j = 1; j < r; j++) row.push(BIN[r - 1][j - 1] + BIN[r - 1][j]);
row.push(1);
BIN.push(row);
}
return k < 0 || k > n ? 0 : BIN[n][k];
}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.