pub fn find_span(degree: usize, n_ctrl: usize, knots: &[f64], u: f64) -> usize {
debug_assert!(n_ctrl > degree, "need at least degree + 1 control points");
let n = n_ctrl - 1;
if u >= knots[n + 1] {
return n;
}
if u <= knots[degree] {
return degree;
}
let mut low = degree;
let mut high = n + 1;
let mut mid = (low + high) / 2;
while u < knots[mid] || u >= knots[mid + 1] {
if u < knots[mid] {
high = mid;
} else {
low = mid;
}
mid = (low + high) / 2;
}
mid
}
pub fn basis_funcs(span: usize, u: f64, degree: usize, knots: &[f64]) -> Vec<f64> {
let mut n = vec![0.0; degree + 1];
let mut left = vec![0.0; degree + 1];
let mut right = vec![0.0; degree + 1];
n[0] = 1.0;
for j in 1..=degree {
left[j] = u - knots[span + 1 - j];
right[j] = knots[span + j] - u;
let mut saved = 0.0;
for r in 0..j {
let temp = n[r] / (right[r + 1] + left[j - r]);
n[r] = saved + right[r + 1] * temp;
saved = left[j - r] * temp;
}
n[j] = saved;
}
n
}
#[allow(clippy::needless_range_loop)]
pub fn ders_basis_funcs(
span: usize,
u: f64,
degree: usize,
n_ders: usize,
knots: &[f64],
) -> Vec<Vec<f64>> {
let p = degree;
let mut ders = vec![vec![0.0; p + 1]; n_ders + 1];
let mut ndu = vec![vec![0.0; p + 1]; p + 1];
let mut left = vec![0.0; p + 1];
let mut right = vec![0.0; p + 1];
ndu[0][0] = 1.0;
for j in 1..=p {
left[j] = u - knots[span + 1 - j];
right[j] = knots[span + j] - u;
let mut saved = 0.0;
for r in 0..j {
ndu[j][r] = right[r + 1] + left[j - r];
let temp = ndu[r][j - 1] / ndu[j][r];
ndu[r][j] = saved + right[r + 1] * temp;
saved = left[j - r] * temp;
}
ndu[j][j] = saved;
}
for (j, d) in ders[0].iter_mut().enumerate() {
*d = ndu[j][p];
}
let k_max = n_ders.min(p);
if k_max == 0 {
return ders;
}
let mut a = vec![vec![0.0; p + 1]; 2];
for r in 0..=p {
let (mut s1, mut s2) = (0usize, 1usize);
a[0][0] = 1.0;
for k in 1..=k_max {
let mut d = 0.0;
let rk = r as isize - k as isize;
let pk = p as isize - k as isize;
if r as isize >= k as isize {
a[s2][0] = a[s1][0] / ndu[(pk + 1) as usize][rk as usize];
d = a[s2][0] * ndu[rk as usize][pk as usize];
}
let j1 = if rk >= -1 { 1isize } else { -rk };
let j2 = if (r as isize - 1) <= pk {
k as isize - 1
} else {
p as isize - r as isize
};
let mut j = j1;
while j <= j2 {
a[s2][j as usize] = (a[s1][j as usize] - a[s1][(j - 1) as usize])
/ ndu[(pk + 1) as usize][(rk + j) as usize];
d += a[s2][j as usize] * ndu[(rk + j) as usize][pk as usize];
j += 1;
}
if (r as isize) <= pk {
a[s2][k] = -a[s1][k - 1] / ndu[(pk + 1) as usize][r];
d += a[s2][k] * ndu[r][pk as usize];
}
ders[k][r] = d;
std::mem::swap(&mut s1, &mut s2);
}
}
let mut acc = p as f64;
for k in 1..=k_max {
for j in 0..=p {
ders[k][j] *= acc;
}
acc *= (p as isize - k as isize) as f64;
}
ders
}
pub fn binomial(n: usize, k: usize) -> f64 {
if k > n {
return 0.0;
}
let k = k.min(n - k);
let mut acc = 1.0;
for i in 0..k {
acc = acc * (n - i) as f64 / (i + 1) as f64;
}
acc
}
pub fn uniform_clamped_knots(degree: usize, n_ctrl: usize) -> Vec<f64> {
let p = degree;
let m = n_ctrl + p + 1;
let interior = n_ctrl - p - 1;
let mut knots = Vec::with_capacity(m);
knots.extend(std::iter::repeat_n(0.0, p + 1));
for i in 1..=interior {
knots.push(i as f64 / (interior + 1) as f64);
}
knots.extend(std::iter::repeat_n(1.0, p + 1));
debug_assert_eq!(knots.len(), m);
knots
}
pub fn knots_valid(degree: usize, n_ctrl: usize, knots: &[f64]) -> bool {
if n_ctrl <= degree || knots.len() != n_ctrl + degree + 1 {
return false;
}
if knots.windows(2).any(|w| w[1] < w[0]) {
return false;
}
knots[n_ctrl] > knots[degree]
}
#[cfg(test)]
mod tests {
use super::*;
fn open_knots() -> Vec<f64> {
vec![0.0, 0.0, 0.0, 0.0, 0.25, 0.5, 0.75, 1.0, 1.0, 1.0, 1.0]
}
#[test]
fn span_search_matches_linear_scan() {
let knots = open_knots();
let (p, n_ctrl) = (3, 7);
for i in 0..=1000 {
let u = i as f64 / 1000.0;
let span = find_span(p, n_ctrl, &knots, u);
assert!(span >= p && span < n_ctrl);
if u < 1.0 {
assert!(knots[span] <= u && u < knots[span + 1], "u = {u}");
}
}
}
#[test]
fn span_clamps_outside_the_domain() {
let knots = open_knots();
assert_eq!(find_span(3, 7, &knots, -5.0), 3);
assert_eq!(find_span(3, 7, &knots, 5.0), 6);
}
#[test]
fn basis_is_a_partition_of_unity() {
let knots = open_knots();
for i in 0..=500 {
let u = i as f64 / 500.0;
let span = find_span(3, 7, &knots, u);
let n = basis_funcs(span, u, 3, &knots);
let sum: f64 = n.iter().sum();
assert!((sum - 1.0).abs() < 1e-14, "sum = {sum} at u = {u}");
assert!(n.iter().all(|&x| x >= -1e-15), "negative basis at u = {u}");
}
}
#[test]
fn zeroth_derivative_row_equals_the_basis() {
let knots = open_knots();
for i in 0..=100 {
let u = i as f64 / 100.0;
let span = find_span(3, 7, &knots, u);
let n = basis_funcs(span, u, 3, &knots);
let ders = ders_basis_funcs(span, u, 3, 2, &knots);
for j in 0..=3 {
assert!((n[j] - ders[0][j]).abs() < 1e-15);
}
}
}
#[test]
fn derivative_sums_vanish() {
let knots = open_knots();
for i in 1..100 {
let u = i as f64 / 100.0;
let span = find_span(3, 7, &knots, u);
let ders = ders_basis_funcs(span, u, 3, 3, &knots);
for (k, d) in ders.iter().enumerate().take(4).skip(1) {
let sum: f64 = d.iter().sum();
assert!(sum.abs() < 1e-9, "order {k} sum = {sum} at u = {u}");
}
}
}
#[test]
fn binomials() {
assert_eq!(binomial(0, 0), 1.0);
assert_eq!(binomial(5, 0), 1.0);
assert_eq!(binomial(5, 2), 10.0);
assert_eq!(binomial(5, 5), 1.0);
assert_eq!(binomial(5, 6), 0.0);
assert_eq!(binomial(10, 5), 252.0);
}
#[test]
fn knot_validation() {
assert!(knots_valid(3, 7, &open_knots()));
assert!(!knots_valid(3, 6, &open_knots()), "wrong length");
let mut bad = open_knots();
bad[5] = 0.1; assert!(!knots_valid(3, 7, &bad));
assert!(knots_valid(2, 4, &uniform_clamped_knots(2, 4)));
}
}