use crate::bspline;
use crate::math::*;
use crate::model::{BSpline, BSplineSurface};
use crate::nurbs::Spline;
fn above(a: f64, b: f64) -> bool {
a > b
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SurfacePoint {
pub point: [f64; 3],
pub du: [f64; 3],
pub dv: [f64; 3],
pub duu: [f64; 3],
pub duv: [f64; 3],
pub dvv: [f64; 3],
}
#[derive(Debug)]
pub struct Evaluator(Spline);
impl Evaluator {
pub fn new(surface: &BSplineSurface) -> Result<Evaluator, String> {
Spline::check(surface)?;
Ok(Evaluator(Spline::new(surface)))
}
pub fn domain(&self) -> ([f64; 2], [f64; 2]) {
self.0.domain()
}
pub fn eval(&self, u: f64, v: f64) -> [f64; 3] {
self.0.eval(u, v).arr()
}
pub fn derivatives(&self, u: f64, v: f64) -> SurfacePoint {
let d = self.0.ders(u, v, 2);
SurfacePoint {
point: d[0][0].arr(),
du: d[1][0].arr(),
dv: d[0][1].arr(),
duu: d[2][0].arr(),
duv: d[1][1].arr(),
dvv: d[0][2].arr(),
}
}
pub fn normal(&self, u: f64, v: f64) -> [f64; 3] {
self.0.normal(u, v).arr()
}
pub fn project(&self, p: [f64; 3]) -> [f64; 2] {
let (u, v) = self.0.project(V::from(p), false);
[u, v]
}
pub fn project_extended(&self, p: [f64; 3]) -> [f64; 2] {
let (u, v) = self.0.project(V::from(p), true);
[u, v]
}
}
pub fn interpolate_curve(points: &[[f64; 3]], params: &[f64]) -> Result<BSpline<3>, String> {
check_params(points.len(), params)?;
if points.iter().flatten().any(|x| !x.is_finite()) {
return Err("a point is not finite".into());
}
Ok(bspline::interpolate_at(points, params))
}
fn check_params(n: usize, params: &[f64]) -> Result<(), String> {
if n < 2 || params.len() != n {
return Err(format!(
"{n} points and {} parameters (at least 2 of each, as many of one as the other)",
params.len()
));
}
if params.iter().any(|x| !x.is_finite()) || params.windows(2).any(|w| w[1] <= w[0]) {
return Err("parameters are not increasing".into());
}
Ok(())
}
#[derive(Clone, Debug, PartialEq)]
pub struct FittedCurves {
pub curves: Vec<BSpline<3>>,
pub error: f64,
}
pub fn fit_curves(
fs: &[&dyn Fn(f64) -> [f64; 3]],
range: [f64; 2],
tolerance: f64,
max_points: usize,
) -> Result<FittedCurves, String> {
if fs.is_empty() || !above(range[1], range[0]) || !above(tolerance, 0.0) {
return Err("no functions, an empty range or no tolerance".into());
}
let mut n = 8usize;
loop {
let ts: Vec<f64> = (0..=n)
.map(|k| range[0] + (range[1] - range[0]) * k as f64 / n as f64)
.collect();
let mut curves = Vec::with_capacity(fs.len());
let mut error = 0.0f64;
for f in fs {
let pts: Vec<[f64; 3]> = ts.iter().map(|&t| f(t)).collect();
let c = interpolate_curve(&pts, &ts)?;
for k in 0..n {
let t = 0.5 * (ts[k] + ts[k + 1]);
error = error.max((V::from(bspline::eval(&c, t)) - V::from(f(t))).len());
}
curves.push(c);
}
if error <= tolerance {
return Ok(FittedCurves { curves, error });
}
if 2 * n + 1 > max_points {
return Err(format!(
"{} points leave the curves {error:.2e} from their functions",
n + 1
));
}
n *= 2;
}
}
pub fn interpolate_surface(
points: &[Vec<[f64; 3]>],
us: &[f64],
vs: &[f64],
) -> Result<BSplineSurface, String> {
check_params(points.len(), us)?;
for row in points {
check_params(row.len(), vs)?;
}
if points.iter().flatten().flatten().any(|x| !x.is_finite()) {
return Err("a point is not finite".into());
}
let rows: Vec<BSpline<3>> = points
.iter()
.map(|row| bspline::interpolate_at(row, vs))
.collect();
let nv = rows[0].control.len();
let cols: Vec<BSpline<3>> = (0..nv)
.map(|j| {
let pts: Vec<[f64; 3]> = rows.iter().map(|r| r.control[j]).collect();
bspline::interpolate_at(&pts, us)
})
.collect();
let nu = cols[0].control.len();
Ok(BSplineSurface {
degree_u: cols[0].degree,
degree_v: rows[0].degree,
control: (0..nu)
.map(|i| cols.iter().map(|c| c.control[i]).collect())
.collect(),
weights: None,
knots_u: cols[0].knots.clone(),
knots_v: rows[0].knots.clone(),
})
}
#[derive(Clone, Debug, PartialEq)]
pub struct FittedSurface {
pub surface: BSplineSurface,
pub error: f64,
}
pub fn fit_surface(
f: &dyn Fn(f64, f64) -> [f64; 3],
u_range: [f64; 2],
v_range: [f64; 2],
tolerance: f64,
max_points: usize,
) -> Result<FittedSurface, String> {
if !above(u_range[1], u_range[0]) || !above(v_range[1], v_range[0]) || !above(tolerance, 0.0) {
return Err("an empty range or no tolerance".into());
}
let lin = |r: [f64; 2], n: usize| -> Vec<f64> {
(0..=n)
.map(|k| r[0] + (r[1] - r[0]) * k as f64 / n as f64)
.collect()
};
let (mut nu, mut nv) = (8usize, 8usize);
loop {
let (us, vs) = (lin(u_range, nu), lin(v_range, nv));
let pts: Vec<Vec<[f64; 3]>> = us
.iter()
.map(|&u| vs.iter().map(|&v| f(u, v)).collect())
.collect();
let surface = interpolate_surface(&pts, &us, &vs)?;
let ev = Spline::new(&surface);
let gap = |u: f64, v: f64| (ev.eval(u, v) - V::from(f(u, v))).len();
let mid = |xs: &[f64], k: usize| 0.5 * (xs[k] + xs[k + 1]);
let (mut eu, mut evv, mut ec) = (0.0f64, 0.0f64, 0.0f64);
for i in 0..=nu {
for j in 0..=nv {
if i < nu {
eu = eu.max(gap(mid(&us, i), vs[j]));
}
if j < nv {
evv = evv.max(gap(us[i], mid(&vs, j)));
}
if i < nu && j < nv {
ec = ec.max(gap(mid(&us, i), mid(&vs, j)));
}
}
}
let error = eu.max(evv).max(ec);
if error <= tolerance {
return Ok(FittedSurface { surface, error });
}
let more_u = eu > tolerance || (ec > tolerance && eu >= evv);
let more_v = evv > tolerance || (ec > tolerance && evv >= eu);
let (nu2, nv2) = (
if more_u { 2 * nu } else { nu },
if more_v { 2 * nv } else { nv },
);
if (nu2 + 1) * (nv2 + 1) > max_points {
return Err(format!(
"a {} by {} grid leaves the surface {error:.2e} from the function",
nu + 1,
nv + 1
));
}
nu = nu2;
nv = nv2;
}
}
fn compatible(cs: &[&BSpline<3>]) -> Result<(), String> {
let c0 = cs[0];
for c in cs {
let p = c.degree as usize;
if !(1..=7).contains(&p) || c.control.len() <= p || c.knots.len() != c.control.len() + p + 1
{
return Err("a curve's degree, control points and knots do not agree".into());
}
if c.degree != c0.degree || c.knots != c0.knots {
return Err("the curves do not share a degree and a knot vector".into());
}
if c.control.iter().flatten().any(|x| !x.is_finite()) {
return Err("a control point is not finite".into());
}
}
let k = &c0.knots;
let (p, n) = (c0.degree as usize, c0.control.len());
if k.windows(2).any(|w| w[1] < w[0])
|| k[..=p].iter().any(|&x| x != k[0])
|| k[n..].iter().any(|&x| x != k[n])
|| k[p] >= k[n]
{
return Err("the knots are not clamped and non-decreasing".into());
}
Ok(())
}
fn circle_distance(q: V, c: V, n: V, r: f64) -> f64 {
let d = q - c;
let h = d.dot(n);
let rho = d.reject(n).len();
((rho - r) * (rho - r) + h * h).sqrt()
}
pub fn canal_surface(
spine: &BSpline<3>,
foot_a: &BSpline<3>,
foot_b: &BSpline<3>,
radius: f64,
) -> Result<FittedSurface, String> {
compatible(&[spine, foot_a, foot_b])?;
if !above(radius, 0.0) || !radius.is_finite() {
return Err("the radius is not positive".into());
}
let p = spine.degree as usize;
let n = spine.control.len();
let knots = &spine.knots;
let g = bspline::greville(knots, p, n);
let at = |t: f64| {
(
V::from(bspline::eval(spine, t)),
V::from(bspline::eval(foot_a, t)),
V::from(bspline::eval(foot_b, t)),
)
};
let mut h: Vec<[f64; 4]> = Vec::with_capacity(n);
for &t in &g {
let (c, a, b) = at(t);
let (da, db) = (a - c, b - c);
let (la, lb) = (da.len(), db.len());
if !above(la, 0.0) || !above(lb, 0.0) {
return Err(format!("a foot point is on the spine at {t}"));
}
let cos = da.dot(db) / (la * lb);
if !above(cos, -1.0 + 1e-6) {
return Err(format!("the arc at {t} is a half circle or more"));
}
let w = (0.5 * (1.0 + cos)).sqrt();
let m = c + (da + db) * (1.0 / (1.0 + cos));
h.push([m.x * w, m.y * w, m.z * w, w]);
}
let mid =
bspline::interpolate_knots(&h, &g, knots, p).ok_or("the stations do not fit the knots")?;
if mid.control.iter().any(|q| !above(q[3], 0.0)) {
return Err("an interpolated weight is not positive".into());
}
let surface = BSplineSurface {
degree_u: 2,
degree_v: p as u32,
control: vec![
foot_a.control.clone(),
mid.control
.iter()
.map(|q| [q[0] / q[3], q[1] / q[3], q[2] / q[3]])
.collect(),
foot_b.control.clone(),
],
weights: Some(vec![
vec![1.0; n],
mid.control.iter().map(|q| q[3]).collect(),
vec![1.0; n],
]),
knots_u: vec![0.0, 0.0, 0.0, 1.0, 1.0, 1.0],
knots_v: knots.clone(),
};
Spline::check(&surface)?;
let ev = Spline::new(&surface);
let mut error = 0.0f64;
for (a0, b0) in bspline::spans(spine) {
for k in 0..=4 {
let t = a0 + (b0 - a0) * k as f64 / 4.0;
let (c, a, b) = at(t);
let nrm = (a - c).cross(b - c).norm();
error = error
.max(((a - c).len() - radius).abs())
.max(((b - c).len() - radius).abs());
for i in 1..8 {
let q = ev.eval(i as f64 / 8.0, t);
error = error.max(circle_distance(q, c, nrm, radius));
}
}
}
Ok(FittedSurface { surface, error })
}
pub fn ruled_surface(a: &BSpline<3>, b: &BSpline<3>) -> Result<BSplineSurface, String> {
compatible(&[a, b])?;
let surface = BSplineSurface {
degree_u: 1,
degree_v: a.degree,
control: vec![a.control.clone(), b.control.clone()],
weights: None,
knots_u: vec![0.0, 0.0, 1.0, 1.0],
knots_v: a.knots.clone(),
};
Spline::check(&surface)?;
Ok(surface)
}
#[cfg(test)]
mod tests {
use super::*;
fn circle(r: f64, z: f64) -> impl Fn(f64) -> [f64; 3] {
move |t: f64| [r * cos(t), r * sin(t), z]
}
#[test]
fn fitted_curves_share_knots_and_meet_the_tolerance() {
let (a, b) = (circle(10.0, 0.0), circle(7.0, 3.0));
let f = fit_curves(&[&a, &b], [0.0, PI / 2.0], 1e-8, 10_000).unwrap();
assert!(f.error <= 1e-8);
assert_eq!(f.curves[0].knots, f.curves[1].knots);
let q = bspline::eval(&f.curves[0], 0.3);
assert!((V::from(q) - V::from(a(0.3))).len() < 1e-8);
}
#[test]
fn a_fitted_surface_meets_the_tolerance() {
let f = |u: f64, v: f64| [u, v, 0.3 * sin(u) * cos(2.0 * v)];
let fit = fit_surface(&f, [0.0, 3.0], [0.0, 2.0], 1e-7, 100_000).unwrap();
assert!(fit.error <= 1e-7);
let ev = Evaluator::new(&fit.surface).unwrap();
let q = ev.eval(1.234, 0.567);
assert!((V::from(q) - V::from(f(1.234, 0.567))).len() < 1e-6);
let [u, v] = ev.project([1.234, 0.567, 1.0]);
let n = ev.normal(u, v);
let d = (V::from([1.234, 0.567, 1.0]) - V::from(ev.eval(u, v))).norm();
assert!(V::from(n).cross(d).len() < 1e-9);
}
#[test]
fn a_canal_surface_with_a_straight_spine_is_a_cylinder() {
let line = |y: f64, z: f64| move |t: f64| [t, y, z];
let (s, a, b) = (line(2.0, 2.0), line(2.0, 0.0), line(0.0, 2.0));
let f = fit_curves(&[&s, &a, &b], [0.0, 10.0], 1e-9, 1000).unwrap();
let c = canal_surface(&f.curves[0], &f.curves[1], &f.curves[2], 2.0).unwrap();
assert!(c.error < 1e-12, "{}", c.error);
let ev = Evaluator::new(&c.surface).unwrap();
for i in 0..=8 {
for j in 0..=8 {
let q = V::from(ev.eval(i as f64 / 8.0, 10.0 * j as f64 / 8.0));
let r = ((q.y - 2.0).powi(2) + (q.z - 2.0).powi(2)).sqrt();
assert!((r - 2.0).abs() < 1e-13);
}
}
let q = V::from(ev.eval(0.5, 5.0));
let n = V::from(ev.normal(0.5, 5.0));
assert!(n.dot(v(5.0, 2.0, 2.0) - q) > 0.0);
}
#[test]
fn a_canal_surface_round_a_circle_is_near_the_torus() {
let s = |t: f64| [7.0 * cos(t), 7.0 * sin(t), 2.0];
let a = |t: f64| [7.0 * cos(t), 7.0 * sin(t), 0.0];
let b = |t: f64| [5.0 * cos(t), 5.0 * sin(t), 2.0];
let f = fit_curves(&[&s, &a, &b], [0.0, PI / 2.0], 1e-9, 10_000).unwrap();
let c = canal_surface(&f.curves[0], &f.curves[1], &f.curves[2], 2.0).unwrap();
assert!(c.error < 1e-8, "{}", c.error);
let ev = Evaluator::new(&c.surface).unwrap();
for i in 0..=8 {
for j in 0..=16 {
let q = V::from(ev.eval(i as f64 / 8.0, PI / 2.0 * j as f64 / 16.0));
let rho = (q.x * q.x + q.y * q.y).sqrt();
let d = ((rho - 7.0).powi(2) + (q.z - 2.0).powi(2)).sqrt();
assert!((d - 2.0).abs() < 1e-8, "{d}");
}
}
}
#[test]
fn mismatched_curves_are_refused() {
let a = interpolate_curve(&[[0.0; 3], [1.0, 0.0, 0.0]], &[0.0, 1.0]).unwrap();
let b = interpolate_curve(&[[0.0; 3], [1.0, 1.0, 0.0]], &[0.0, 2.0]).unwrap();
assert!(ruled_surface(&a, &b).is_err());
let b = interpolate_curve(&[[0.0, 0.0, 1.0], [1.0, 1.0, 1.0]], &[0.0, 1.0]).unwrap();
assert!(ruled_surface(&a, &b).is_ok());
}
}