SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.
//! Whether the two faces on either side of an edge meet tangentially all along it, decided
//! exactly from the record.
//!
//! Each use of the edge carries its pcurve `(u(t), v(t))` in its face's parameters
//! ([`Face::parameters`]: a plane, or the B-spline surface SMLib holds the face as), on the edge's
//! own parameter `t`, so the two uses' points at one `t` are one point of the edge. The face's
//! natural normal there is `S_u × S_v` at the pcurve's point. On a piece of `t` where the pcurve
//! stays within one span of its own knots and one knot cell of its surface, both are
//! polynomials: `S` of degree `(p, q)` in `(u, v)` (rational: its homogeneous form, of the same
//! degree), the pcurve of degree `r` in `t`. So `S_u × S_v`, scaled by a positive power of the
//! weights, is a polynomial in `t` of degree at most `(2p + 2q - 2) r` (rational: `(4p + 4q - 2) r`,
//! from `(A_u w - A w_u) × (A_v w - A w_v)`), and a plane's is constant. The cross product of the
//! two faces' normals is then a polynomial vector of degree at most the sum `D` of theirs, and a
//! polynomial of degree `D` that vanishes at `D + 1` points vanishes everywhere: the faces are
//! parallel all along the piece exactly when they are at `D + 1` of its points, its Chebyshev
//! points, and on one side (smooth, not folded back on each other) when their outward normals
//! point the same way there. No point is a guess at where the faces part: one where they do is
//! a witness of a crease (or a cusp, the faces folded back), and agreement at all of them is
//! a proof of tangency, within the angle the caller allows at each (between them, the cross
//! product is bounded by its largest value at them times the Lebesgue constant of `D + 1`
//! Chebyshev points, under `1 + (2/π) ln(D + 1)`).
//!
//! The pieces' ends are the pcurves' knots and the parameters where a pcurve crosses a knot line
//! of its surface (periodic copies included), each a root of `U(t) - k W(t)` on one Bézier span
//! of the pcurve, isolated by subdividing its Bernstein coefficients (no sign change: no root;
//! one: exactly one) and found to rounding by bisection.
use solidcore_record::Vec3;
use solidcore_record::brep::{Brep, Curve2, Face, Surface};
use solidcraft_geom::brep::eval::SurfaceEval;
use solidcraft_geom::bspline::{HPoint, segment};
use solidcraft_geom::prelude::*;
use crate::{KernelError, Result};
/// Most points one edge's decision evaluates.
const MAX_POINTS: usize = 1_000_000;
/// Largest degree of a piece's cross product the decision takes.
const MAX_DEGREE: usize = 4096;
/// Subdivisions of one Bernstein polynomial while isolating its roots: its pieces are then
/// 2⁻⁴⁸ of a pcurve span, where a root left unisolated (a pcurve touching a knot line) ends a
/// piece there.
const MAX_DEPTH: u32 = 48;
/// Subdivisions one root isolation may make: a root that touches its knot line (a double root,
/// the only kind that keeps two sign changes as the pieces shrink) costs one a level.
const MAX_SUBDIVISIONS: usize = 4096;
/// Below this sine of the angle between `S_u` and `S_v` a face's normal is undefined at that
/// point (a pole): the normal, and so the cross product, is zero there.
const DEGENERATE: f64 = 1e-9;
/// One use of the edge: its face's surface, the sign turning its natural normal outward, its
/// pcurve and the degree of its normal along a piece.
struct Use<'a> {
surface: SurfaceEval,
sign: f64,
pcurve: &'a Curve2,
degree: usize,
/// The knot lines of the surface in u and v (its distinct knots over its domain) and its
/// periods: a polynomial cell's sides.
lines: [Vec<f64>; 2],
period: [Option<f64>; 2],
}
fn failed(msg: String) -> KernelError {
KernelError::Failed(msg)
}
/// A B-spline's degree from its knot and control point counts.
fn degree_of(knots: usize, count: usize) -> Option<usize> {
knots.checked_sub(count.checked_add(1)?)
}
/// The distinct knots of a knot vector over its domain `[knots[p], knots[n]]`.
fn lines(knots: &[f64], count: usize) -> Option<Vec<f64>> {
let p = degree_of(knots.len(), count)?;
let mut out: Vec<f64> = knots.get(p..=count)?.to_vec();
out.dedup();
Some(out)
}
impl<'a> Use<'a> {
fn new(face: &Face, sign: f64, pcurve: &'a Curve2) -> Result<Use<'a>> {
let surface = face.parameters();
let r = match pcurve {
Curve2::Spline { knots, points } => degree_of(knots.len(), points.len()),
Curve2::RationalSpline { knots, homogeneous } => degree_of(knots.len(), homogeneous.len()),
}
.ok_or_else(|| failed("a pcurve's degree".into()))?;
// The normal's degree in (u, v) and the knot lines.
let (uv_degree, lines) = match surface {
Surface::Plane { .. } | Surface::PlaneThrough { .. } => (0, [Vec::new(), Vec::new()]),
Surface::Spline { u_knots, v_knots, points } => {
let (nu, nv) = (points.len(), points.first().map_or(0, Vec::len));
let (p, q) = (degree_of(u_knots.len(), nu), degree_of(v_knots.len(), nv));
let (Some(p), Some(q), Some(lu), Some(lv)) = (p, q, lines(u_knots, nu), lines(v_knots, nv)) else {
return Err(failed("a spline face's degree".into()));
};
((2 * p + 2 * q).saturating_sub(2), [lu, lv])
}
Surface::RationalSpline { u_knots, v_knots, homogeneous } => {
let (nu, nv) = (homogeneous.len(), homogeneous.first().map_or(0, Vec::len));
let (p, q) = (degree_of(u_knots.len(), nu), degree_of(v_knots.len(), nv));
let (Some(p), Some(q), Some(lu), Some(lv)) = (p, q, lines(u_knots, nu), lines(v_knots, nv)) else {
return Err(failed("a spline face's degree".into()));
};
((4 * p + 4 * q).saturating_sub(2), [lu, lv])
}
// SMLib gives every curved analytic face its NURBS form, which its pcurves are on.
_ => return Err(crate::blend::unsupported("deciding tangency along an edge of a face that is no plane and has no NURBS form")),
};
let eval = SurfaceEval::new(surface).map_err(|e| failed(format!("a face's surface: {e}")))?;
let period = eval.domain().period;
Ok(Use { surface: eval, sign, pcurve, degree: uv_degree.saturating_mul(r), lines, period })
}
/// The outward unit normal at the pcurve's point at `t`; `Ok(None)` where it is undefined (a
/// pole: a zero of the normal).
fn normal(&self, t: f64) -> Result<Option<Vec3>> {
let uv = solidcraft_geom::brep::pcurve::eval(self.pcurve, t).ok_or_else(|| failed(format!("a pcurve at {t}")))?;
let (_, su, sv) = self.surface.derivs(uv[0], uv[1]).ok_or_else(|| failed(format!("a face at ({}, {})", uv[0], uv[1])))?;
let n = su.cross(sv);
if !(n.len() > DEGENERATE * su.len() * sv.len()) {
return Ok(None);
}
Ok(n.normalized().map(|n| n * self.sign))
}
/// The parameters in `(t0, t1)` where the normal stops being one polynomial: the pcurve's
/// own knots, and where it crosses a knot line of the surface.
fn breaks(&self, [t0, t1]: [f64; 2], out: &mut Vec<f64>) -> Result<()> {
let (knots, ctrl): (&[f64], Vec<HPoint>) = match self.pcurve {
Curve2::Spline { knots, points } => (knots, points.iter().map(|p| HPoint { x: p[0], y: p[1], z: 0.0, w: 1.0 }).collect()),
Curve2::RationalSpline { knots, homogeneous } => {
(knots, homogeneous.iter().map(|h| HPoint { x: h[0], y: h[1], z: 0.0, w: h[2] }).collect())
}
};
let r = degree_of(knots.len(), ctrl.len()).ok_or_else(|| failed("a pcurve's degree".into()))?;
let mut spans: Vec<f64> = vec![t0];
spans.extend(knots.iter().copied().filter(|k| *k > t0 && *k < t1));
spans.push(t1);
spans.dedup();
out.extend(spans.iter().copied());
if self.lines.iter().all(Vec::is_empty) {
return Ok(());
}
for w in spans.windows(2) {
let &[a, b] = w else { continue };
let (_, bez) = segment(r, knots, &ctrl, a, b).map_err(|e| failed(format!("a pcurve span: {e}")))?;
if bez.len() != r + 1 {
return Err(failed("a pcurve span is no Bézier piece".into()));
}
for d in 0..2 {
let coord = |h: &HPoint| if d == 0 { h.x } else { h.y };
// The span's range in this direction: its control points' hull (weights > 0).
let along: Vec<f64> = bez.iter().map(|h| coord(h) / h.w).collect();
let lo = along.iter().copied().fold(f64::INFINITY, f64::min);
let hi = along.iter().copied().fold(f64::NEG_INFINITY, f64::max);
if !(lo.is_finite() && hi.is_finite()) {
return Err(failed("a pcurve's control points".into()));
}
for k in cell_sides(&self.lines[d], self.period[d], lo, hi)? {
// Coefficients within rounding of zero are zero: a pcurve running along
// the knot line (a seam, a boundary) crosses none there.
let scale = bez.iter().map(|h| coord(h).abs() + (k * h.w).abs()).fold(0.0, f64::max);
let floor = 64.0 * f64::EPSILON * scale;
let c: Vec<f64> = bez.iter().map(|h| coord(h) - k * h.w).map(|x| if x.abs() <= floor { 0.0 } else { x }).collect();
if c.iter().all(|x| *x == 0.0) {
continue;
}
let mut roots = Vec::new();
let mut work = MAX_SUBDIVISIONS;
bernstein_roots(&c, 0.0, 1.0, MAX_DEPTH, &mut work, &mut roots);
out.extend(roots.into_iter().map(|s| a + (b - a) * s));
}
}
}
Ok(())
}
}
/// The knot lines `lines` (and, with a period, their copies a whole number of periods away) that
/// lie in `[lo, hi]`.
fn cell_sides(lines: &[f64], period: Option<f64>, lo: f64, hi: f64) -> Result<Vec<f64>> {
let Some(p) = period.filter(|p| *p > 0.0) else {
return Ok(lines.iter().copied().filter(|k| *k >= lo && *k <= hi).collect());
};
let (Some(&first), Some(&last)) = (lines.first(), lines.last()) else { return Ok(Vec::new()) };
let (n0, n1) = (((lo - last) / p).floor(), ((hi - first) / p).ceil());
if !(n1 - n0 <= 64.0) {
return Err(failed("a pcurve running round its surface too many times".into()));
}
let mut out = Vec::new();
let mut n = n0;
while n <= n1 {
out.extend(lines.iter().map(|k| k + n * p).filter(|k| *k >= lo && *k <= hi));
n += 1.0;
}
Ok(out)
}
/// The value at `s` of the polynomial with Bernstein coefficients `c` on `[0, 1]` (de Casteljau).
fn bernstein_value(c: &[f64], s: f64) -> f64 {
let mut b = c.to_vec();
while b.len() > 1 {
b = b.windows(2).map(|w| if let [x, y] = w { x * (1.0 - s) + y * s } else { 0.0 }).collect();
}
b.first().copied().unwrap_or(0.0)
}
/// The Bernstein coefficients of the polynomial `c` on `[0, ½]` and `[½, 1]`.
fn bernstein_halves(c: &[f64]) -> (Vec<f64>, Vec<f64>) {
let mut left = Vec::with_capacity(c.len());
let mut right = Vec::with_capacity(c.len());
let mut b = c.to_vec();
while let (Some(&f), Some(&l)) = (b.first(), b.last()) {
left.push(f);
right.push(l);
b = b.windows(2).map(|w| if let [x, y] = w { 0.5 * (x + y) } else { 0.0 }).collect();
}
right.reverse();
(left, right)
}
/// The roots in `[lo, hi]` of the polynomial with Bernstein coefficients `c` there, mapped
/// into `[lo, hi]`'s place in `[0, 1]`: none where the coefficients keep one sign, exactly one
/// where they change sign once (found by bisection to rounding), otherwise those of each half.
fn bernstein_roots(c: &[f64], lo: f64, hi: f64, depth: u32, work: &mut usize, out: &mut Vec<f64>) {
let (Some(&first), Some(&last)) = (c.first(), c.last()) else { return };
if first == 0.0 {
out.push(lo);
}
if last == 0.0 {
out.push(hi);
}
let signs: Vec<bool> = c.iter().filter(|x| **x != 0.0).map(|x| *x > 0.0).collect();
let changes = signs.windows(2).filter(|w| matches!(w, [x, y] if x != y)).count();
if changes == 0 {
return;
}
if changes == 1 && first != 0.0 && last != 0.0 {
let (mut a, mut b) = (0.0, 1.0);
for _ in 0..64 {
let m = 0.5 * (a + b);
if !(m > a && m < b) {
break;
}
if (bernstein_value(c, m) > 0.0) == (first > 0.0) {
a = m;
} else {
b = m;
}
}
out.push(lo + (hi - lo) * 0.5 * (a + b));
return;
}
let mid = 0.5 * (lo + hi);
// Out of depth or work, the roots are within this piece: it ends a piece of the edge at
// both its ends.
if depth == 0 || *work == 0 {
out.extend([lo, hi]);
return;
}
*work -= 1;
let (l, r) = bernstein_halves(c);
bernstein_roots(&l, lo, mid, depth - 1, work, out);
bernstein_roots(&r, mid, hi, depth - 1, work, out);
}
/// Calls `visit` with the outward unit normals of edge `e`'s two uses' faces at one point of the
/// edge after another, `sign(f)` turning face `f`'s natural normal outward: on each piece of the
/// edge where both normals are polynomials, at the `D + 1` Chebyshev points the module
/// documentation describes, skipping a point where either is undefined (a pole). `visit` returns
/// whether to go on. `Ok(None)` for an edge with other than two uses; else whether some point had
/// both normals.
fn normal_pairs(rec: &Brep, sign: impl Fn(usize) -> Option<f64>, e: usize, mut visit: impl FnMut(Vec3, Vec3) -> bool) -> Result<Option<bool>> {
let edge = rec.edges.get(e).ok_or_else(|| failed(format!("edge {e}")))?;
let [ua, ub] = edge.uses.as_slice() else { return Ok(None) };
let use_of = |u: &solidcore_record::brep::EdgeUseRef| -> Result<Use<'_>> {
let face = rec.faces.get(u.face as usize).ok_or_else(|| failed(format!("face {}", u.face)))?;
let oriented = match face.loops.get(u.r#loop as usize) {
Some(solidcore_record::brep::Loop::Edges { edges }) => edges.get(u.position as usize),
_ => None,
}
.ok_or_else(|| failed(format!("a use of edge {e}")))?;
let s = sign(u.face as usize).ok_or_else(|| failed(format!("face {} is in no shell", u.face)))?;
Use::new(face, s, &oriented.pcurve)
};
let (a, b) = (use_of(ua)?, use_of(ub)?);
let degree = a.degree.saturating_add(b.degree);
if degree > MAX_DEGREE {
return Err(failed(format!("deciding tangency along edge {e}: its faces' normals are of degree {degree}")));
}
let interval = edge.interval;
let mut breaks = Vec::new();
a.breaks(interval, &mut breaks)?;
b.breaks(interval, &mut breaks)?;
breaks.retain(|t| *t >= interval[0] && *t <= interval[1]);
breaks.sort_by(f64::total_cmp);
breaks.dedup();
let nodes = degree + 1;
if breaks.len().saturating_mul(nodes) > MAX_POINTS {
return Err(failed(format!("deciding tangency along edge {e}: {} pieces of degree {degree}", breaks.len())));
}
let mut defined = false;
for w in breaks.windows(2) {
let &[t0, t1] = w else { continue };
let (m, h) = (0.5 * (t0 + t1), 0.5 * (t1 - t0));
if !(h > 0.0) {
continue;
}
for j in 0..nodes {
let t = m + h * ((2 * j + 1) as f64 * std::f64::consts::PI / (2 * nodes) as f64).cos();
if let (Some(na), Some(nb)) = (a.normal(t)?, b.normal(t)?) {
defined = true;
if !visit(na, nb) {
return Ok(Some(true));
}
}
}
}
Ok(Some(defined))
}
/// Whether edge `e`'s two uses' faces meet with outward normals within `max_angle` (radians) of
/// each other all along it, `sign(f)` turning face `f`'s natural normal outward. An edge with
/// other than two uses has no such pair: false. See the module documentation.
pub(crate) fn tangent_all_along(rec: &Brep, sign: impl Fn(usize) -> Option<f64>, e: usize, max_angle: f64) -> Result<bool> {
let cos = max_angle.cos();
let mut tangent = true;
let Some(defined) = normal_pairs(rec, sign, e, |na, nb| {
tangent = na.dot(nb) >= cos;
tangent
})?
else {
return Ok(false);
};
if !defined {
return Err(failed(format!("edge {e}: its faces' normals are undefined all along it")));
}
Ok(tangent)
}
/// The least angle (radians, 0 to π) between the outward normals of edge `e`'s two uses' faces
/// at the points [`normal_pairs`] visits: the edge's least angle where it is the same all along
/// the edge (two planes, a plane and a cylinder along a generator), at most a little above it
/// elsewhere. `None` for an edge with other than two uses, or whose normals are undefined
/// everywhere.
pub(crate) fn least_angle_along(rec: &Brep, sign: impl Fn(usize) -> Option<f64>, e: usize) -> Result<Option<f64>> {
let mut least = f64::INFINITY;
let defined = normal_pairs(rec, sign, e, |na, nb| {
least = least.min(na.cross(nb).len().atan2(na.dot(nb)));
true
})?;
Ok(defined.filter(|d| *d).map(|_| least))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn bernstein_roots_are_isolated_and_exact() {
// (s - 0.25)(s - 0.75) = s² - s + 3/16 in Bernstein form on [0, 1]: 3/16, 3/16 - 1/2, 3/16.
let c = [0.1875, 0.1875 - 0.5, 0.1875];
let mut roots = Vec::new();
let mut work = MAX_SUBDIVISIONS;
bernstein_roots(&c, 0.0, 1.0, MAX_DEPTH, &mut work, &mut roots);
roots.sort_by(f64::total_cmp);
assert_eq!(roots.len(), 2, "{roots:?}");
assert!((roots[0] - 0.25).abs() < 1e-15 && (roots[1] - 0.75).abs() < 1e-15, "{roots:?}");
// No sign change: no root.
let mut none = Vec::new();
bernstein_roots(&[1.0, 0.5, 2.0], 0.0, 1.0, MAX_DEPTH, &mut work, &mut none);
assert!(none.is_empty());
}
#[test]
fn periodic_knot_lines_repeat_by_whole_periods() {
let sides = cell_sides(&[0.0, 1.0, 2.0], Some(2.0), 1.5, 4.5).unwrap();
assert_eq!(sides, vec![2.0, 2.0, 3.0, 4.0, 4.0]);
}
}