use cadkit_core::{Point3, Vec3};
pub(crate) fn ellipse_points(
center: Point3,
major: Vec3,
ratio: f64,
start: f64,
end: f64,
normal: Vec3,
segments: usize,
) -> Vec<Point3> {
let n = normal.normalized().unwrap_or(Vec3::Z);
let minor = Vec3::new(
(n.y * major.z - n.z * major.y) * ratio,
(n.z * major.x - n.x * major.z) * ratio,
(n.x * major.y - n.y * major.x) * ratio,
);
let mut sweep = end - start;
if sweep <= 0.0 {
sweep += std::f64::consts::TAU;
}
let segments = segments.max(4);
(0..=segments)
.map(|i| {
let t = start + sweep * (i as f64) / (segments as f64);
let (s, c) = t.sin_cos();
Point3::new(
center.x + major.x * c + minor.x * s,
center.y + major.y * c + minor.y * s,
center.z + major.z * c + minor.z * s,
)
})
.collect()
}
pub(crate) fn clamped_knots(n: usize, degree: usize) -> Vec<f64> {
if degree > MAX_DEGREE {
return Vec::new();
}
let m = n.saturating_add(degree).saturating_add(1);
let interior = n.saturating_sub(degree);
(0..m)
.map(|i| {
if i <= degree {
0.0
} else if i >= n {
interior as f64
} else {
(i - degree) as f64
}
})
.collect()
}
pub(crate) const MAX_DEGREE: usize = 64;
const MAX_SAMPLES: usize = 4096;
fn find_span(n: usize, degree: usize, u: f64, knots: &[f64]) -> usize {
let k = |j: usize| knots.get(j).copied().unwrap_or(0.0);
let (mut lo, mut hi) = (degree, n);
while lo + 1 < hi {
let mid = lo + (hi - lo) / 2;
if k(mid) <= u {
lo = mid;
} else {
hi = mid;
}
}
lo
}
fn basis_functions(span: usize, u: f64, degree: usize, knots: &[f64]) -> Vec<f64> {
let k = |j: usize| knots.get(j).copied().unwrap_or(0.0);
let mut n = vec![0.0; degree + 1];
let mut left = vec![0.0; degree + 1];
let mut right = vec![0.0; degree + 1];
if let Some(first) = n.first_mut() {
*first = 1.0;
}
for j in 1..=degree {
if let (Some(l), Some(r)) = (left.get_mut(j), right.get_mut(j)) {
*l = u - k(span + 1 - j);
*r = k(span + j) - u;
}
let mut saved = 0.0;
for r in 0..j {
let rv = right.get(r + 1).copied().unwrap_or(0.0);
let lv = left.get(j - r).copied().unwrap_or(0.0);
let denom = rv + lv;
let nr = n.get(r).copied().unwrap_or(0.0);
let temp = if denom != 0.0 { nr / denom } else { 0.0 };
if let Some(slot) = n.get_mut(r) {
*slot = saved + rv * temp;
}
saved = lv * temp;
}
if let Some(slot) = n.get_mut(j) {
*slot = saved;
}
}
n
}
pub(crate) fn spline_points(
degree: usize,
knots: &[f64],
ctrl: &[Point3],
weights: &[f64],
samples: usize,
) -> Vec<Point3> {
let n = ctrl.len();
if !(1..=MAX_DEGREE).contains(°ree) || n <= degree || knots.len() != n + degree + 1 {
return Vec::new();
}
if knots.iter().any(|k| !k.is_finite())
|| knots
.windows(2)
.any(|w| matches!((w.first(), w.get(1)), (Some(a), Some(b)) if a > b))
{
return Vec::new();
}
let (Some(&u0), Some(&u1)) = (knots.get(degree), knots.get(n)) else {
return Vec::new();
};
if u1 <= u0 {
return Vec::new();
}
let rational = weights.len() == n;
let samples = samples.clamp(2, MAX_SAMPLES);
let mut out = Vec::with_capacity(samples + 1);
for s in 0..=samples {
let u = if s == samples {
u1
} else {
u0 + (u1 - u0) * (s as f64) / (samples as f64)
};
let span = find_span(n, degree, u, knots);
let basis = basis_functions(span, u, degree, knots);
let (mut x, mut y, mut z, mut wsum) = (0.0, 0.0, 0.0, 0.0);
for (j, b) in basis.iter().enumerate() {
let Some(i) = (span + j).checked_sub(degree) else {
continue;
};
let Some(p) = ctrl.get(i) else { continue };
let w = if rational {
weights.get(i).copied().unwrap_or(1.0)
} else {
1.0
};
let b = b * w;
x += b * p.x;
y += b * p.y;
z += b * p.z;
wsum += b;
}
if wsum.abs() > 1e-12 {
out.push(Point3::new(x / wsum, y / wsum, z / wsum));
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn quadratic_bezier() {
let ctrl = [
Point3::xy(0.0, 0.0),
Point3::xy(1.0, 2.0),
Point3::xy(2.0, 0.0),
];
let knots = clamped_knots(3, 2);
let pts = spline_points(2, &knots, &ctrl, &[], 4);
assert_eq!(pts.len(), 5);
let mid = pts[2];
assert!((mid.x - 1.0).abs() < 1e-12 && (mid.y - 1.0).abs() < 1e-12);
assert!((pts[4].x - 2.0).abs() < 1e-9 && pts[4].y.abs() < 1e-9);
}
#[test]
fn high_degree_is_fast_and_bounded() {
let ctrl: Vec<Point3> = (0..70)
.map(|i| Point3::xy(f64::from(i), f64::from(i % 3)))
.collect();
let knots = clamped_knots(70, 60);
let t = std::time::Instant::now();
let pts = spline_points(60, &knots, &ctrl, &[], 8 * 70);
assert!(pts.len() > 500 && t.elapsed().as_secs() < 5);
assert!(clamped_knots(10, usize::MAX).is_empty());
assert!(spline_points(MAX_DEGREE + 1, &knots, &ctrl, &[], 10).is_empty());
let mut bad = knots.clone();
bad[5] = f64::NAN;
assert!(spline_points(60, &bad, &ctrl, &[], 10).is_empty());
}
#[test]
fn ellipse_quarter() {
let pts = ellipse_points(
Point3::xy(0.0, 0.0),
Vec3::new(2.0, 0.0, 0.0),
0.5,
0.0,
std::f64::consts::FRAC_PI_2,
Vec3::Z,
8,
);
let last = pts[pts.len() - 1];
assert!(last.x.abs() < 1e-12 && (last.y - 1.0).abs() < 1e-12);
}
}