Skip to content

SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.

14.1 KB
Raw Blame
//! Geometric continuity of order `n` (G0 … G4) between two surfaces that share a curve, in the
//! linkage-curve formulation, as the fill imposes it and as a seam is measured.
//!
//! **The criterion.** Two surfaces meeting along a curve are G^n there exactly when the
//! *linkage curves* crossing it — a curve on one surface continued by a curve on the other — are
//! G^n curves (Pegna & Wolter, "Geometrical criteria to guarantee curvature continuity of blend
//! surfaces", J. Mech. Des. 114, 1992, for n = 2; Hermann, Lukács & Wolter, "Geometrical
//! criteria on the higher order smoothness of composite surfaces", CAGD 16, 1999, for any n).
//! In a form that needs no reparameterisation: write the neighbour, near a point `p` of the
//! curve, as a height `H` over its tangent plane along its unit normal `n`,
//! `q = p + x + H(x)·n` for `x` in the tangent plane, so that `H(0) = 0` and `∇H(0) = 0`. A
//! curve `c(σ)` from `p` lies on a surface meeting the neighbour with G^n exactly when its height
//! above the neighbour, `n·(c(σ) − p) − H(x(σ))` with `x(σ)` the part of `c(σ) − p` in the
//! tangent plane, vanishes to order `n` in σ. With `H(x) = Σ_{m ≥ 2} H_m(x) / m!` (`H_m` the
//! m-th derivative of `H` at `p`, a form of degree m) and `x(σ) = Σ_j x_j σʲ / j!`
//! (`x_j` the tangent-plane part of `c⁽ʲ⁾`), the condition of order `k` is
//!
//! `n·c⁽ᵏ⁾ = k! · [σᵏ] Σ_{m=2}^{k} H_m(x(σ)) / m!`,
//!
//! whose right-hand side reads `c′ … c⁽ᵏ⁻¹⁾` only: order 1 is `n·c′ = 0` (the tangent plane),
//! order 2 `n·c″ = H₂(x₁)` (the normal curvature in the curve's direction), order 3
//! `n·c‴ = 3·H₂(x₁, x₂) + H₃(x₁)` (the rate of change of that curvature), and order 4 its rate of
//! change in turn. For a unit `a`, `H₂(a)` is the curvature of the normal section along `a` and
//! `H₃(a)`, `H₄(a)` are its first and second derivatives by arc length.
//!
//! **The jet.** [`surface_jet`] reads `H₂ … H_n` off a surface record's exact partial
//! derivatives: along a tangent vector `a`, the curve on the surface whose foot in the tangent
//! plane runs straight along `a` at unit rate has `n·γ⁽ᵐ⁾(0) = H_m(a)`; its parameter series
//! `(u(τ), v(τ))` is found order by order (the part of each coefficient of `S(u(τ), v(τ))` in the
//! tangent plane is `a`, then zero), and `H_m` as a binary form from its values along
//! `t + λ·w` at `m + 1` values of λ (a polynomial of degree m in λ, so exactly).
//!
//! Input is hostile: orders are capped at [`MAX_CONTINUITY`], and every evaluation is checked.

use crate::brep::eval::SurfaceEval;
use crate::prelude::*;
use crate::tess::partials::{MAX_PARTIAL_ORDER, Partials};
use solidcore_record::Vec3;

/// The highest continuity order handled: G4, the highest order of the surfaces' exact partials.
pub const MAX_CONTINUITY: usize = MAX_PARTIAL_ORDER;

/// A surface near a point as a height over its tangent plane, to order `order` (2 … 4): the
/// forms `H_m` for `m = 2 ..= order` on the frame `t = n × w`, `w` (both unit, in the tangent
/// plane; `w` the direction the surface leaves the shared curve in). `forms[m − 2][j]` is the
/// coefficient of `x_t^(m−j)·x_w^j` in `H_m(x)`.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Jet {
    pub order: usize,
    pub forms: [[f64; MAX_CONTINUITY + 1]; MAX_CONTINUITY - 1],
}

impl Jet {
    /// `H_m(a)` for a tangent vector given by its components `(a_t, a_w)`.
    pub fn form(&self, m: usize, a: [f64; 2]) -> Option<f64> {
        let coefficients = self.forms.get(m.checked_sub(2)?).filter(|_| (2..=self.order).contains(&m))?;
        Some((0..=m).map(|j| coefficients.get(j).copied().unwrap_or(0.0) * a[0].powi((m - j) as i32) * a[1].powi(j as i32)).sum())
    }

    /// Whether every coefficient is finite.
    pub fn is_finite(&self) -> bool {
        self.forms.iter().flatten().all(|x| x.is_finite())
    }

    /// What orders `2 ..= self.order` ask of `n·c⁽ᵏ⁾` (module docs), for a curve whose first
    /// derivatives have the tangent-plane components `x[j − 1] = (x_j·t, x_j·w)`: element
    /// `k − 2` is order k's (it reads `x[0 .. k − 1]`). `None` when too few derivatives are given.
    pub fn targets(&self, x: &[[f64; 2]]) -> Option<Vec<f64>> {
        Some(self.linearised(x)?.into_iter().map(|t| t.value).collect())
    }

    /// [`Jet::targets`] with their exact gradients: element `k − 2` is order k's target and its
    /// derivative with respect to each component of each `x_j` (`gradient[j − 1]`), so that the
    /// condition `n·c⁽ᵏ⁾ = target(x)` can be linearised about a curve (Newton's method).
    pub fn linearised(&self, x: &[[f64; 2]]) -> Option<Vec<Target>> {
        let top = self.order;
        if x.len() + 1 < top || top > MAX_CONTINUITY {
            return None;
        }
        // x(σ) as truncated Taylor series in each component (no constant term), each coefficient
        // a dual number seeded with its own component.
        let mut series = [vec![Dual::ZERO; top + 1], vec![Dual::ZERO; top + 1]];
        for (j, xj) in x.iter().enumerate().take(top.saturating_sub(1)) {
            for (c, (s, value)) in series.iter_mut().zip(xj).enumerate() {
                if let Some(slot) = s.get_mut(j + 1) {
                    *slot = Dual::seed(*value, 2 * j + c).scale(1.0 / factorial(j + 1));
                }
            }
        }
        let mut height = vec![Dual::ZERO; top + 1];
        for m in 2..=top {
            let coefficients = self.forms.get(m - 2)?;
            for (j, c) in coefficients.iter().enumerate().take(m + 1) {
                let monomial = mul(&power(&series[0], m - j, top), &power(&series[1], j, top), top);
                for (h, x) in height.iter_mut().zip(&monomial) {
                    *h = *h + x.scale(c / factorial(m));
                }
            }
        }
        Some(
            (2..=top)
                .map(|k| {
                    let d = height.get(k).copied().unwrap_or(Dual::ZERO).scale(factorial(k));
                    let mut gradient = [[0.0; 2]; MAX_CONTINUITY - 1];
                    for (j, g) in gradient.iter_mut().enumerate() {
                        *g = [d.grad[2 * j], d.grad[2 * j + 1]];
                    }
                    Target { value: d.value, gradient }
                })
                .collect(),
        )
    }
}

/// One order's target and its gradient (see [`Jet::linearised`]).
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Target {
    pub value: f64,
    /// `gradient[j − 1]`: the derivative with respect to `(x_j·t, x_j·w)`.
    pub gradient: [[f64; 2]; MAX_CONTINUITY - 1],
}

/// Gradients carried: two components of each of `x₁ … x₃`.
const SEEDS: usize = 2 * (MAX_CONTINUITY - 1);

/// A number with its gradient with respect to the [`SEEDS`] components (forward differentiation:
/// the targets are polynomials in them, so the gradient is exact).
#[derive(Clone, Copy, Debug, PartialEq)]
struct Dual {
    value: f64,
    grad: [f64; SEEDS],
}

impl Dual {
    const ZERO: Dual = Dual { value: 0.0, grad: [0.0; SEEDS] };
    const ONE: Dual = Dual { value: 1.0, grad: [0.0; SEEDS] };

    fn seed(value: f64, at: usize) -> Dual {
        let mut grad = [0.0; SEEDS];
        if let Some(g) = grad.get_mut(at) {
            *g = 1.0;
        }
        Dual { value, grad }
    }

    fn scale(self, k: f64) -> Dual {
        Dual { value: self.value * k, grad: self.grad.map(|g| g * k) }
    }
}

impl std::ops::Add for Dual {
    type Output = Dual;
    fn add(self, o: Dual) -> Dual {
        let mut grad = self.grad;
        for (g, h) in grad.iter_mut().zip(o.grad) {
            *g += h;
        }
        Dual { value: self.value + o.value, grad }
    }
}

impl std::ops::Mul for Dual {
    type Output = Dual;
    fn mul(self, o: Dual) -> Dual {
        let mut grad = [0.0; SEEDS];
        for ((g, a), b) in grad.iter_mut().zip(self.grad).zip(o.grad) {
            *g = a * o.value + self.value * b;
        }
        Dual { value: self.value * o.value, grad }
    }
}

/// `k!` as a float (small k).
fn factorial(k: usize) -> f64 {
    (1..=k).map(|i| i as f64).product()
}

/// The numbers the series below are over: plain floats and [`Dual`]s.
trait Coefficient: Copy + std::ops::Add<Output = Self> + std::ops::Mul<Output = Self> {
    const ZERO: Self;
    const ONE: Self;
}

impl Coefficient for f64 {
    const ZERO: f64 = 0.0;
    const ONE: f64 = 1.0;
}

impl Coefficient for Dual {
    const ZERO: Dual = Dual::ZERO;
    const ONE: Dual = Dual::ONE;
}

/// The product of two truncated series (coefficients of `σ⁰ … σ^top`).
fn mul<T: Coefficient>(a: &[T], b: &[T], top: usize) -> Vec<T> {
    let mut out = vec![T::ZERO; top + 1];
    for (i, x) in a.iter().enumerate().take(top + 1) {
        for (j, y) in b.iter().enumerate().take(top + 1 - i) {
            if let Some(slot) = out.get_mut(i + j) {
                *slot = *slot + *x * *y;
            }
        }
    }
    out
}

/// A truncated series to the power `e`.
fn power<T: Coefficient>(a: &[T], e: usize, top: usize) -> Vec<T> {
    let mut one = vec![T::ZERO; top + 1];
    if let Some(c) = one.first_mut() {
        *c = T::ONE;
    }
    (0..e).fold(one, |acc, _| mul(&acc, a, top))
}

/// The surface `s` near `uv` as a height along its unit normal `n` (either sign) over its tangent
/// plane, to order `order` (2 ..= [`MAX_CONTINUITY`]), on the frame `t = n × w`, `w` (`w` a unit
/// tangent vector): see [`Jet`] and the module docs. `None` where the surface has no tangent
/// plane (a pole) or cannot be evaluated.
pub fn surface_jet(s: &SurfaceEval, uv: [f64; 2], n: Vec3, w: Vec3, order: usize) -> Option<Jet> {
    if !(2..=MAX_CONTINUITY).contains(&order) {
        return None;
    }
    let d = s.partials(uv[0], uv[1])?;
    let t = n.cross(w);
    let mut forms = [[0.0; MAX_CONTINUITY + 1]; MAX_CONTINUITY - 1];
    // H_m(t + λ w) is a polynomial of degree m in λ: its coefficients are the form's.
    const NODES: [f64; MAX_CONTINUITY + 1] = [0.0, 1.0, -1.0, 2.0, -2.0];
    let along: Vec<Vec<f64>> = NODES.iter().map(|l| heights(&d, n, t + w * *l, order)).collect::<Option<_>>()?;
    for m in 2..=order {
        let values: Vec<f64> = along.iter().take(m + 1).map(|h| h.get(m).copied().unwrap_or(f64::NAN)).collect();
        let coefficients = polynomial_through(NODES.get(..=m)?, &values)?;
        let slot = forms.get_mut(m - 2)?;
        for (x, c) in slot.iter_mut().zip(coefficients) {
            *x = c;
        }
    }
    let jet = Jet { order, forms };
    jet.is_finite().then_some(jet)
}

/// `H_m(a)` for `m = 0 ..= order` from the partials `d` (`d[i][j] = S^(i,j)`): the curve on
/// the surface whose foot runs straight along `a` (module docs), its parameter series solved
/// order by order. `None` where the tangent plane degenerates.
fn heights(d: &Partials, n: Vec3, a: Vec3, order: usize) -> Option<Vec<f64>> {
    let at = |i: usize, j: usize| d.get(i).and_then(|r| r.get(j)).copied();
    let (su, sv) = (at(1, 0)?, at(0, 1)?);
    let (e, f, g) = (su.dot(su), su.dot(sv), sv.dot(sv));
    let det = e * g - f * f;
    // A pole: one parameter direction collapses against the other (or the two run together).
    if !(e.min(g) > 1e-20 * e.max(g) && det > 1e-12 * e * g) {
        return None;
    }
    // The rates (du, dv) whose image S_u du + S_v dv has tangent-plane part `b`.
    let rates = |b: Vec3| {
        let (bu, bv) = (b.dot(su), b.dot(sv));
        ((g * bu - f * bv) / det, (e * bv - f * bu) / det)
    };
    let tangential = |x: Vec3| x - n * x.dot(n);
    let mut du = vec![0.0; order + 1];
    let mut dv = vec![0.0; order + 1];
    for k in 1..=order {
        // The coefficient of τᵏ with this order's rates still nought, then the rates that make
        // its tangent-plane part `a` (k = 1) or zero.
        let have = composed(d, &du, &dv, order)?.get(k).copied()?;
        let want = if k == 1 { tangential(a) } else { Vec3::ZERO };
        let (x, y) = rates(want - tangential(have));
        *du.get_mut(k)? = x;
        *dv.get_mut(k)? = y;
    }
    let c = composed(d, &du, &dv, order)?;
    Some(c.iter().enumerate().map(|(k, x)| factorial(k) * n.dot(*x)).collect())
}

/// The Taylor coefficients of `S(u₀ + δu(τ), v₀ + δv(τ)) − S(u₀, v₀)` to order `order`, for the
/// series `δu`, `δv` (no constant term) and the partials `d`.
fn composed(d: &Partials, du: &[f64], dv: &[f64], order: usize) -> Option<Vec<Vec3>> {
    let mut out = vec![Vec3::ZERO; order + 1];
    for (i, row) in d.iter().enumerate() {
        for (j, partial) in row.iter().enumerate() {
            if i + j == 0 || i + j > order {
                continue;
            }
            let term = mul(&power(du, i, order), &power(dv, j, order), order);
            let scale = 1.0 / (factorial(i) * factorial(j));
            for (o, x) in out.iter_mut().zip(&term) {
                *o += *partial * (x * scale);
            }
        }
    }
    out.iter().all(|p| p.is_finite()).then_some(out)
}

/// The coefficients `c₀ … c_m` of the polynomial of degree `m = nodes.len() − 1` through
/// `(nodes[i], values[i])` (Newton's divided differences, expanded).
fn polynomial_through(nodes: &[f64], values: &[f64]) -> Option<Vec<f64>> {
    let m = nodes.len();
    if values.len() != m || m == 0 {
        return None;
    }
    let mut dd = values.to_vec();
    for level in 1..m {
        for i in (level..m).rev() {
            let span = nodes.get(i)? - nodes.get(i - level)?;
            if span == 0.0 {
                return None;
            }
            *dd.get_mut(i)? = (dd.get(i)? - dd.get(i - 1)?) / span;
        }
    }
    // Horner on the Newton form: p(λ) = dd₀ + (λ − x₀)(dd₁ + (λ − x₁)(…)).
    let mut c = vec![0.0; m];
    for i in (0..m).rev() {
        // c ← c·(λ − x_i) + dd_i.
        let x = *nodes.get(i)?;
        let mut next = vec![0.0; m];
        for (k, ck) in c.iter().enumerate() {
            if let Some(slot) = next.get_mut(k + 1) {
                *slot += ck;
            }
            if let Some(slot) = next.get_mut(k) {
                *slot -= ck * x;
            }
        }
        if let Some(slot) = next.get_mut(0) {
            *slot += dd.get(i)?;
        }
        c = next;
    }
    c.iter().all(|x| x.is_finite()).then_some(c)
}

#[cfg(test)]
#[path = "linkage_tests.rs"]
mod tests;