The basis functions and derivatives under every NURBS curve and surface.
How the precision is kept
Written in 64-bit from the published algorithms (Piegl and Tiller, The NURBS Book, A2.1 to A2.3). Two knots closer than 1e-12 of the domain length count as one knot; the end of the domain belongs to the last span, so an evaluation at the last parameter never falls off the curve.
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.
Which span of the knot vector a parameter falls in.
i such that U[i] ≤ u < U[i + 1], by bisection
Comparisons only: no arithmetic is done on the parameter. The halving uses a 32-bit shift on the span index, which is a whole number, not a measured value.
nurbs/basis.js
lines 26 to 35
ModelCraft 0.8.1
export function findSpan(n, p, u, U) {
if (u >= U[n + 1]) return n;
if (u <= U[p]) return p;
let lo = p, hi = n + 1, mid = (lo + hi) >> 1;
while (u < U[mid] || u >= U[mid + 1]) {
if (u < U[mid]) hi = mid; else lo = mid;
mid = (lo + hi) >> 1;
}
return mid;
}
Basis functions
64-bit
The p + 1 basis functions that are not zero at a parameter.
N(i, p)(u) by the Cox-de Boor recurrence (A2.2)
Inside the span every term of the recurrence is zero or positive, so nothing cancels: the values stay accurate to the last few bits and add up to 1.
nurbs/basis.js
lines 37 to 52
ModelCraft 0.8.1
export function basisFuns(i, u, p, U) {
const N = new Array(p + 1), left = new Array(p + 1), right = new Array(p + 1);
N[0] = 1;
for (let j = 1; j <= p; j++) {
left[j] = u - U[i + 1 - j];
right[j] = U[i + j] - u;
let saved = 0;
for (let r = 0; r < j; r++) {
const temp = N[r] / (right[r + 1] + left[j - r]);
N[r] = saved + right[r + 1] * temp;
saved = left[j - r] * temp;
}
N[j] = saved;
}
return N;
}
Basis function derivatives
64-bit
The basis functions and their derivatives up to a chosen order.
N⁽ᵏ⁾(i, p)(u) for k = 0 … d (A2.3)
Derivatives are differences of basis values divided by knot differences, so each order of derivative costs some digits. That is a property of the mathematics, not of the code.
nurbs/basis.js
lines 54 to 91
ModelCraft 0.8.1
export function dersBasisFuns(i, u, p, d, U) {
const ndu = Array.from({ length: p + 1 }, () => new Array(p + 1).fill(0));
const left = new Array(p + 1), right = new Array(p + 1);
ndu[0][0] = 1;
for (let j = 1; j <= p; j++) {
left[j] = u - U[i + 1 - j];
right[j] = U[i + j] - u;
let saved = 0;
for (let r = 0; r < j; r++) {
ndu[j][r] = right[r + 1] + left[j - r]; // lower triangle: knot differences
const temp = ndu[r][j - 1] / ndu[j][r];
ndu[r][j] = saved + right[r + 1] * temp; // upper triangle: basis functions
saved = left[j - r] * temp;
}
ndu[j][j] = saved;
}
const ders = Array.from({ length: d + 1 }, () => new Array(p + 1).fill(0));
for (let j = 0; j <= p; j++) ders[0][j] = ndu[j][p];
const a = [new Array(p + 1).fill(0), new Array(p + 1).fill(0)];
for (let r = 0; r <= p; r++) {
let s1 = 0, s2 = 1;
a[0][0] = 1;
for (let k = 1; k <= d; k++) {
let dd = 0;
const rk = r - k, pk = p - k;
if (r >= k) { a[s2][0] = a[s1][0] / ndu[pk + 1][rk]; dd = a[s2][0] * ndu[rk][pk]; }
const j1 = rk >= -1 ? 1 : -rk;
const j2 = r - 1 <= pk ? k - 1 : p - r;
for (let j = j1; j <= j2; j++) { a[s2][j] = (a[s1][j] - a[s1][j - 1]) / ndu[pk + 1][rk + j]; dd += a[s2][j] * ndu[rk + j][pk]; }
if (r <= pk) { a[s2][k] = -a[s1][k - 1] / ndu[pk + 1][r]; dd += a[s2][k] * ndu[r][pk]; }
ders[k][r] = dd;
const t = s1; s1 = s2; s2 = t;
}
}
let f = p;
for (let k = 1; k <= d; k++) { for (let j = 0; j <= p; j++) ders[k][j] *= f; f *= p - k; }
return ders;
}
In detail
Method
FindSpan (A2.1), BasisFuns (A2.2) and DersBasisFuns (A2.3) from The NURBS Book, written from the published algorithms.
Number types
64-bit numbers throughout.
Tolerances
Two knots closer than 1e-12 of the domain length are one knot.
Checked by
The NURBS library tests.
Limits
Every curve and surface is clamped: the first and last knots repeat degree + 1 times.
Approach: 64-bit, direct
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.