Skip to content

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

39.5 KB
Raw Blame
//! Whole-span certificates for analytic planar prism boundaries, read off the curves of schema 4
//! record edges. A record's lines and circles are read as they are; a spline is read span by
//! span (its Bézier pieces): samples propose a circle, and only positive rational Bernstein
//! bounds accept it.
use solidcore_record::brep::{Brep, Curve};
use solidcore_record::{Plane, Seg2, Vec2, Vec3};
use solidcraft_geom::brep::eval::CurveEval;
use solidcraft_geom::bspline::{self, HPoint};
use solidcraft_geom::prelude::*;

const MAX_DEGREE: usize = 32;
/// How far an arc read off a curve may end from the curve's end (mm): half the gap a profile
/// loop may have between segments and still close (`crate::build`).
const ARC_END_TOL: f64 = 5e-7;
const MAX_CONTROLS: usize = 4096;
type H = [f64; 3];

/// A curve over `interval` (in its own parameter), run from `ends[0]` to `ends[1]`: from the
/// interval's min to its max when `forward`, the other way otherwise. The ends are the points
/// the curve must reach there (a record edge's vertices).
#[derive(Clone, Copy, Debug)]
pub(crate) struct Run<'a> {
    pub curve: &'a Curve,
    pub interval: [f64; 2],
    pub forward: bool,
    pub ends: [Vec3; 2],
}

impl<'a> Run<'a> {
    /// Edge `edge` of `record`, run `forward` (from its start vertex to its end) or back.
    pub(crate) fn of(record: &'a Brep, edge: usize, forward: bool) -> Option<Run<'a>> {
        let e = record.edges.get(edge)?;
        let at = |v: u32| record.vertices.get(v as usize).map(|v| Vec3::new(v.point[0], v.point[1], v.point[2]));
        let (start, end) = (at(e.vertices[0])?, at(e.vertices[1])?);
        Some(Run { curve: e.parameters(), interval: e.interval, forward, ends: if forward { [start, end] } else { [end, start] } })
    }

    /// The parameters it runs from and to.
    fn ends_along(&self) -> (f64, f64) {
        let [t0, t1] = self.interval;
        if self.forward { (t0, t1) } else { (t1, t0) }
    }
}

fn charge(work: &mut usize, n: usize) -> Option<()> {
    *work = work.checked_sub(n)?;
    Some(())
}

fn v3(p: [f64; 3]) -> Vec3 {
    Vec3::new(p[0], p[1], p[2])
}

/// The Bézier spans of a B-spline (homogeneous control points `ctrl` on `knots`) over `[t0, t1]`,
/// in parameter order: the piece clamped to the interval (Boehm insertion of its ends), then every
/// interior knot inserted until it repeats `degree` times; the span between two knots is the
/// `degree + 1` control points ending at the last of the knots below it. Exact up to rounding.
fn spline_spans(knots: &[f64], ctrl: &[HPoint], t0: f64, t1: f64, work: &mut usize) -> Option<Vec<Vec<HPoint>>> {
    let degree = knots.len().checked_sub(ctrl.len() + 1)?;
    if !(1..=MAX_DEGREE).contains(&degree) || ctrl.len() > MAX_CONTROLS || knots.len() > 8192 {
        return None;
    }
    if knots.iter().any(|t| !t.is_finite()) || knots.windows(2).any(|w| w[1] < w[0]) || ctrl.iter().any(|p| !p.is_finite()) {
        return None;
    }
    // Charge decomposition before its knot insertion allocations.
    charge(work, ctrl.len().checked_mul(knots.len())?.checked_mul(degree + 1)?)?;
    let (mut k, mut c) = bspline::segment(degree, knots, ctrl, t0, t1).ok()?;
    let mut interior: Vec<f64> = k.iter().copied().filter(|t| *t > t0 && *t < t1).collect();
    interior.dedup();
    for u in interior {
        while k.iter().filter(|t| **t == u).count() < degree {
            (k, c) = bspline::insert_knot(degree, &k, &c, u).ok()?;
        }
    }
    let n = c.len();
    let mut spans = Vec::new();
    for i in degree..n {
        let (Some(a), Some(b)) = (k.get(i), k.get(i + 1)) else { return None };
        if a < b {
            spans.push(c.get(i - degree..=i)?.to_vec());
        }
    }
    Some(spans)
}

/// An ellipse (`o + rx cos t x + ry sin t y`) from `t0` to `t1` (either way round) as rational
/// quadratic Bézier spans of at most a quarter turn each: each the conic through the span's ends
/// whose tangents meet at the apex, with the middle weight the cosine of half its angle. Exact:
/// an affine image of the circle's rational quadratic arcs.
fn ellipse_spans(o: Vec3, x: Vec3, y: Vec3, radii: [f64; 2], t0: f64, t1: f64, work: &mut usize) -> Option<Vec<Vec<HPoint>>> {
    let span = t1 - t0;
    if !span.is_finite() || span.abs() > std::f64::consts::TAU * 2.0 {
        return None;
    }
    let n = (span.abs() / std::f64::consts::FRAC_PI_2).ceil().max(1.0) as usize;
    charge(work, n.checked_mul(3)?)?;
    let at = |t: f64, scale: f64| o + (x * (radii[0] * t.cos()) + y * (radii[1] * t.sin())) * scale;
    let h = span / n as f64 / 2.0;
    let w = h.cos();
    Some(
        (0..n)
            .map(|i| {
                let a = t0 + span * i as f64 / n as f64;
                let m = a + h;
                vec![HPoint::weighted(at(a, 1.0), 1.0), HPoint::weighted(at(m, 1.0 / w), w), HPoint::weighted(at(a + 2.0 * h, 1.0), 1.0)]
            })
            .collect(),
    )
}

/// `run`'s curve as homogeneous Bézier spans in the direction it runs; `None` for a curve that
/// isn't a spline or an ellipse.
fn spans_of(run: &Run, work: &mut usize) -> Option<Vec<Vec<HPoint>>> {
    let [t0, t1] = run.interval;
    let spans = match run.curve {
        Curve::Spline { knots, points } => {
            let ctrl: Vec<HPoint> = points.iter().map(|p| HPoint::weighted(v3(*p), 1.0)).collect();
            spline_spans(knots, &ctrl, t0, t1, work)?
        }
        Curve::RationalSpline { knots, homogeneous } => {
            let ctrl: Vec<HPoint> = homogeneous.iter().map(|p| HPoint { x: p[0], y: p[1], z: p[2], w: p[3] }).collect();
            spline_spans(knots, &ctrl, t0, t1, work)?
        }
        Curve::Ellipse { frame, radii } => {
            let (x, y) = (v3(frame.x_axis), v3(frame.y_axis));
            let (a, b) = run.ends_along();
            return ellipse_spans(v3(frame.origin), x, y, *radii, a, b, work);
        }
        _ => return None,
    };
    Some(if run.forward { spans } else { spans.into_iter().rev().map(|s| s.into_iter().rev().collect()).collect() })
}

/// The spans in `plane`: `[x·w, y·w, w]` per control point (weights scaled to at most 1), and the
/// rounding error of reading them; `None` where a control point lies off the level `h`.
fn controls(spans: Vec<Vec<HPoint>>, plane: &Plane, h: f64, tol: f64) -> Option<(Vec<Vec<H>>, f64)> {
    if spans.is_empty() || spans.len() > 256 || spans.iter().map(Vec::len).sum::<usize>() > 8192 {
        return None;
    }
    let mut error: f64 = 0.;
    let mut out = Vec::new();
    for s in spans {
        if !(2..=MAX_DEGREE + 1).contains(&s.len()) {
            return None;
        }
        let max_w = s.iter().map(|p| p.w).fold(0., f64::max);
        if !max_w.is_finite() || max_w <= 0. {
            return None;
        }
        let mut span = Vec::new();
        for p in s {
            if !p.is_finite() || p.w / max_w < 1e-12 {
                return None;
            }
            let v = Vec3::new(p.x / p.w, p.y / p.w, p.z / p.w);
            let local = plane.to_local(v);
            let magnitude = v.x.abs() + v.y.abs() + v.z.abs() + plane.origin.len();
            let e = magnitude * f64::EPSILON * 256.;
            if !local.x.is_finite() || !local.y.is_finite() || (plane.height(v) - h).abs() + e > tol {
                return None;
            }
            error = error.max(e);
            let w = p.w / max_w;
            span.push([local.x * w, local.y * w, w]);
        }
        out.push(span);
    }
    (error < tol * 0.1).then_some((out, error))
}

fn product(a: &[f64], b: &[f64], work: &mut usize) -> Option<Vec<f64>> {
    charge(work, a.len().checked_mul(b.len())?)?;
    let (m, n) = (a.len() - 1, b.len() - 1);
    let choose = |degree: usize| {
        let mut v = vec![1.; degree + 1];
        for i in 1..=degree {
            v[i] = v[i - 1] * (degree + 1 - i) as f64 / i as f64;
        }
        v
    };
    let (cm, cn, ct) = (choose(m), choose(n), choose(m + n));
    let mut out = vec![0.; m + n + 1];
    for (i, ai) in a.iter().enumerate() {
        for (j, bj) in b.iter().enumerate() {
            out[i + j] += ai * bj * cm[i] * cn[j] / ct[i + j];
        }
    }
    out.iter().all(|x| x.is_finite()).then_some(out)
}

fn derivative(a: &[f64]) -> Vec<f64> {
    let n = (a.len() - 1) as f64;
    a.windows(2).map(|w| (w[1] - w[0]) * n).collect()
}

fn determinant(a: &[f64], b: &[f64], work: &mut usize) -> Option<(Vec<f64>, f64)> {
    let (ab, ba) = (product(a, &derivative(b), work)?, product(b, &derivative(a), work)?);
    let max = |v: &[f64]| v.iter().map(|x| x.abs()).fold(0., f64::max);
    // Bernstein product weights are positive and sum to one. Bound absolute
    // summands from the inputs, never from a possibly cancelled output sum.
    let scale = max(a) * max(&derivative(b)) + max(b) * max(&derivative(a));
    let error = scale * f64::EPSILON * 128. * (a.len() * a.len()) as f64;
    Some((ab.iter().zip(&ba).map(|(x, y)| x - y).collect(), error))
}

fn split(c: &[H]) -> (Vec<H>, Vec<H>) {
    let mut q = c.to_vec();
    let mut left = vec![q[0]];
    let mut right = vec![q[q.len() - 1]];
    while q.len() > 1 {
        q = q.windows(2).map(|p| std::array::from_fn(|i| (p[0][i] + p[1][i]) * 0.5)).collect();
        left.push(q[0]);
        right.push(q[q.len() - 1]);
    }
    right.reverse();
    (left, right)
}

fn point(p: H) -> Vec2 {
    Vec2::new(p[0] / p[2], p[1] / p[2])
}

fn line_span(c: &[H], a: Vec2, b: Vec2, tol: f64, error: f64, work: &mut usize) -> Option<()> {
    let d = b - a;
    let length = d.len();
    if length <= tol {
        return None;
    }
    let d = d / length;
    let mut projected = Vec::new();
    let weights: Vec<_> = c.iter().map(|p| p[2]).collect();
    for p in c {
        let v = point(*p) - a;
        let t = v.dot(d);
        if (v.x * d.y - v.y * d.x).abs() + error > tol || t < -tol + error || t > length + tol - error {
            return None;
        }
        projected.push(t * p[2]);
    }
    // W*T' - T*W' proves oriented traversal, rather than merely collinearity.
    let (der, mut err) = determinant(&weights, &projected, work)?;
    err += error * (c.len() * c.len()) as f64 * 32.;
    if !der.iter().all(|d| *d > err) {
        return None;
    }
    Some(())
}

fn circle_span(c: &[H], center: Vec2, radius: f64, tol: f64, source_error: f64, depth: usize, work: &mut usize) -> Option<f64> {
    charge(work, c.len())?;
    let x: Vec<_> = c.iter().map(|p| p[0] - center.x * p[2]).collect();
    let y: Vec<_> = c.iter().map(|p| p[1] - center.y * p[2]).collect();
    let w: Vec<_> = c.iter().map(|p| p[2]).collect();
    let min_w = w.iter().copied().fold(f64::INFINITY, f64::min);
    if min_w < 1e-12 {
        return None;
    }
    let (xx, yy, ww) = (product(&x, &x, work)?, product(&y, &y, work)?, product(&w, &w, work)?);
    let max = |v: &[f64]| v.iter().map(|x| x.abs()).fold(0., f64::max);
    let scale = max(&x).powi(2) + max(&y).powi(2) + radius * radius * max(&w).powi(2);
    let coordinate_error = source_error + (center.len() + radius) * f64::EPSILON * (depth + 1) as f64 * 128. * c.len() as f64;
    let roundoff = scale * f64::EPSILON * 256. * (c.len() * c.len()) as f64;
    let residual = xx.iter().zip(&yy).zip(&ww).map(|((a, b), w)| (a + b - radius * radius * w).abs()).fold(0., f64::max);
    let radial_tol = tol - coordinate_error;
    if radial_tol <= 0. || (residual + roundoff) / (min_w * min_w) > radial_tol * (2. * radius - radial_tol) {
        return None;
    }
    let (angular, mut error) = determinant(&x, &y, work)?;
    let extent = x.iter().chain(&y).map(|v| v.abs()).fold(0., f64::max);
    error += coordinate_error * extent * (c.len() * c.len()) as f64 * 32.;
    let positive = angular.iter().all(|v| *v > error);
    let negative = angular.iter().all(|v| *v < -error);
    let a = point(c[0]) - center;
    let b = point(c[c.len() - 1]) - center;
    let mid = a + b;
    // One open angular half-plane plus a derivative sign rules out hidden turns.
    let half_plane = mid.len() > radius * 1e-8 && c.iter().all(|p| (point(*p) - center).dot(mid) > coordinate_error * mid.len());
    if (positive || negative) && half_plane {
        let cross = a.x * b.y - a.y * b.x;
        let sweep = cross.atan2(a.dot(b));
        if (positive && sweep > 0.) || (negative && sweep < 0.) {
            return Some(sweep);
        }
        return None;
    }
    if depth >= 12 {
        return None;
    }
    let (left, right) = split(c);
    let a = circle_span(&left, center, radius, tol, source_error, depth + 1, work)?;
    let b = circle_span(&right, center, radius, tol, source_error, depth + 1, work)?;
    (a.signum() == b.signum()).then_some(a + b)
}

/// `run` in `plane` exactly, as lines, circular arcs and free-form segments (each free-form
/// curve one segment): `None` when it doesn't lie in a plane parallel to `plane`, isn't read
/// exactly, isn't finite or goes over the work budget.
pub(crate) fn segment(run: &Run, plane: &Plane, tol: f64, work: &mut usize) -> Option<Vec<Seg2>> {
    read(run, plane, tol, work, false)
}

/// `run` in `plane` exactly as segments: as [`segment`], and a curve of several Bézier spans
/// (a chain of a font's curves, a spline through points) as one segment per span, each the
/// line, conic or Bézier it is, for a planar region's outline. `None` when the edge doesn't lie
/// in a plane parallel to `plane` or isn't read exactly.
pub(crate) fn projected(run: &Run, plane: &Plane, tol: f64, work: &mut usize) -> Option<Vec<Seg2>> {
    read(run, plane, tol, work, true)
}

/// A free-form curve of several Bézier spans in a plane, as the one B-spline it is: its degree,
/// clamped knots, control points in the plane's coordinates and weights (none: a polynomial
/// B-spline). Its first and last control points are its ends.
#[derive(Clone, Debug, PartialEq)]
pub struct PlanarSpline {
    pub degree: usize,
    pub knots: Vec<f64>,
    pub points: Vec<Vec2>,
    pub weights: Vec<f64>,
}

/// One piece of an edge read exactly in a plane: a line, arc or single free-form segment, or a
/// free-form curve of several spans as one [`PlanarSpline`].
#[derive(Clone, Debug, PartialEq)]
pub enum PlanarPiece {
    Seg(Seg2),
    Spline(PlanarSpline),
}

/// `run` in `plane` exactly, for a sketch to project it: as [`segment`], and a curve of several
/// Bézier spans (a spline edge, an elliptical arc past a quarter turn, a chain of a font's
/// curves) as the one B-spline it is, its knots and weights its own. `None` when the edge
/// doesn't lie in a plane parallel to `plane` or isn't read exactly.
pub(crate) fn projected_curves(run: &Run, plane: &Plane, tol: f64, work: &mut usize) -> Option<Vec<PlanarPiece>> {
    if let Some(segs) = read(run, plane, tol, work, false) {
        return Some(segs.into_iter().map(PlanarPiece::Seg).collect());
    }
    one_spline(run, plane, tol, work).map(|s| vec![PlanarPiece::Spline(s)])
}

/// `run`'s spline (or ellipse) over its interval, in the direction it runs, as one clamped
/// B-spline in `plane`: the piece of the curve between the interval's ends (Boehm insertion,
/// exact up to rounding), its control points read in the plane. `None` when a control point lies
/// off the level of the curve's start (the curve is not in a plane parallel to `plane`), the
/// ends miss the run's ends, or the work budget runs out.
fn one_spline(run: &Run, plane: &Plane, tol: f64, work: &mut usize) -> Option<PlanarSpline> {
    if !tol.is_finite() || tol <= 0. || run.interval[1] <= run.interval[0] {
        return None;
    }
    charge(work, 1)?;
    let [t0, t1] = run.interval;
    let clamped = |knots: &[f64], ctrl: Vec<HPoint>, work: &mut usize| -> Option<(usize, Vec<f64>, Vec<HPoint>)> {
        let degree = knots.len().checked_sub(ctrl.len() + 1)?;
        if !(1..=MAX_DEGREE).contains(&degree) || ctrl.len() > MAX_CONTROLS || knots.len() > 8192 {
            return None;
        }
        if knots.iter().any(|t| !t.is_finite()) || knots.windows(2).any(|w| w[1] < w[0]) || ctrl.iter().any(|p| !p.is_finite()) {
            return None;
        }
        charge(work, ctrl.len().checked_mul(degree + 1)?.checked_mul(2)?)?;
        let (k, c) = bspline::segment(degree, knots, &ctrl, t0, t1).ok()?;
        Some((degree, k, c))
    };
    // In the curve's own direction, then the way the run goes.
    let (degree, knots, ctrl) = match run.curve {
        Curve::Spline { knots, points } => along(run, clamped(knots, points.iter().map(|p| HPoint::weighted(v3(*p), 1.0)).collect(), work)?)?,
        Curve::RationalSpline { knots, homogeneous } => {
            along(run, clamped(knots, homogeneous.iter().map(|p| HPoint { x: p[0], y: p[1], z: p[2], w: p[3] }).collect(), work)?)?
        }
        // Rational quadratic spans, already the way the run goes, joined: each joint knot twice.
        Curve::Ellipse { .. } => {
            let spans = spans_of(run, work)?;
            let mut knots = vec![0.0; 3];
            let mut ctrl: Vec<HPoint> = Vec::new();
            for (i, span) in spans.iter().enumerate() {
                let [p0, p1, p2] = span.as_slice() else { return None };
                if let Some(last) = ctrl.last() {
                    if (last.w - p0.w).abs() > 1e-12 * last.w.abs().max(p0.w.abs()) {
                        return None;
                    }
                } else {
                    ctrl.push(*p0);
                }
                ctrl.extend([*p1, *p2]);
                knots.extend([(i + 1) as f64; 2]);
            }
            knots.push(spans.len() as f64);
            (2, knots, ctrl)
        }
        _ => return None,
    };
    let max_w = ctrl.iter().map(|p| p.w).fold(0., f64::max);
    if !(max_w.is_finite() && max_w > 0.) {
        return None;
    }
    let (Some(first), Some(last)) = (ctrl.first().and_then(|p| p.project()), ctrl.last().and_then(|p| p.project())) else { return None };
    let level = plane.height(first);
    let (a, b) = (plane.to_local(first), plane.to_local(last));
    if first.dist(run.ends[0]) > tol || last.dist(run.ends[1]) > tol {
        return None;
    }
    let mut points = Vec::with_capacity(ctrl.len());
    let mut weights = Vec::with_capacity(ctrl.len());
    for p in &ctrl {
        if p.w / max_w < 1e-12 {
            return None;
        }
        let v = p.project()?;
        let error = (v.x.abs() + v.y.abs() + v.z.abs() + plane.origin.len()) * f64::EPSILON * 256.;
        if (plane.height(v) - level).abs() + error > tol || error > tol * 0.1 {
            return None;
        }
        let local = plane.to_local(v);
        if !(local.x.is_finite() && local.y.is_finite()) {
            return None;
        }
        points.push(local);
        weights.push(p.w / max_w);
    }
    // The ends exactly where the curve ends.
    if let Some(p) = points.first_mut() {
        *p = a;
    }
    if let Some(p) = points.last_mut() {
        *p = b;
    }
    if weights.iter().all(|w| (w - 1.).abs() <= 1e-12) {
        weights.clear();
    }
    Some(PlanarSpline { degree, knots, points, weights })
}

/// A clamped B-spline `(degree, knots, control points)` run the way `run` goes: as it is
/// forward, its knots mirrored and its control points reversed back.
fn along(run: &Run, (degree, knots, ctrl): (usize, Vec<f64>, Vec<HPoint>)) -> Option<(usize, Vec<f64>, Vec<HPoint>)> {
    if run.forward {
        return Some((degree, knots, ctrl));
    }
    let sum = knots.first()? + knots.last()?;
    Some((degree, knots.iter().rev().map(|k| sum - k).collect(), ctrl.into_iter().rev().collect()))
}

fn read(run: &Run, plane: &Plane, tol: f64, work: &mut usize, each_span: bool) -> Option<Vec<Seg2>> {
    if !tol.is_finite() || tol <= 0. {
        return None;
    }
    charge(work, 1)?;
    if matches!(run.curve, Curve::SurfaceIntersection { .. }) {
        return None;
    }
    let (ts, te) = run.ends_along();
    if !ts.is_finite() || !te.is_finite() || run.interval[1] <= run.interval[0] {
        return None;
    }
    let eval = CurveEval::new(run.curve).ok()?;
    let (a3, b3) = (eval.point(ts)?, eval.point(te)?);
    let (a, b) = (plane.to_local(a3), plane.to_local(b3));
    if !a3.is_finite()
        || !b3.is_finite()
        || ![a.x, a.y, b.x, b.y].iter().all(|v| v.is_finite())
        || a3.dist(run.ends[0]) > tol
        || b3.dist(run.ends[1]) > tol
    {
        return None;
    }
    let level = plane.height(a3);
    match run.curve {
        Curve::Line { .. } => {
            let error = (a3.len() + b3.len() + plane.origin.len()) * f64::EPSILON * 256.;
            return (error < tol * 0.1 && a.dist(b) > tol && (level - plane.height(b3)).abs() + error <= tol).then_some(vec![Seg2::Line { a, b }]);
        }
        Curve::Polyline { points } => return polyline(points, ts, te, plane, level, tol, work),
        Curve::Circle { frame, radius } => return circle(v3(frame.origin), v3(frame.x_axis), v3(frame.y_axis), *radius, ts, te, a, b, plane, tol),
        _ => {}
    }
    let (spans, error) = controls(spans_of(run, work)?, plane, level, tol)?;
    if spans.windows(2).any(|pair| point(pair[0][pair[0].len() - 1]).dist(point(pair[1][0])) + 2. * error > tol)
        || point(spans.first()?.first().copied()?).dist(a) + error > tol
        || point(spans.last()?.last().copied()?).dist(b) + error > tol
    {
        return None;
    }
    if a.dist(b) > tol && spans.iter().all(|s| line_span(s, a, b, tol, error, work).is_some()) {
        return Some(vec![Seg2::Line { a, b }]);
    }
    arc(&eval, (ts, te), &spans, plane, a, b, tol, error, work)
        .or_else(|| free_form(&spans, a, b, tol))
        .or_else(|| if each_span { span_by_span(&spans, a, b, tol) } else { None })
}

/// A polyline from parameter `ts` to `te` (either way round; segment i spans [i, i + 1]) as its
/// lines, each at level `level` of `plane`.
fn polyline(points: &[[f64; 3]], ts: f64, te: f64, plane: &Plane, level: f64, tol: f64, work: &mut usize) -> Option<Vec<Seg2>> {
    charge(work, points.len())?;
    let (lo, hi) = (ts.min(te), ts.max(te));
    if !(lo >= 0. && hi <= points.len() as f64) {
        return None;
    }
    let at = |t: f64| -> Option<Vec3> {
        let last = points.len().checked_sub(2)?;
        let i = (t.floor().max(0.) as usize).min(last);
        let (p, q) = (v3(*points.get(i)?), v3(*points.get(i + 1)?));
        Some(p + (q - p) * (t - i as f64))
    };
    let mut stations = vec![lo];
    stations.extend((lo.floor() as i64 + 1..=hi.ceil() as i64 - 1).map(|k| k as f64).filter(|k| *k > lo && *k < hi));
    stations.push(hi);
    if ts > te {
        stations.reverse();
    }
    let mut out = Vec::with_capacity(stations.len());
    for pair in stations.windows(2) {
        let (p, q) = (at(pair[0])?, at(pair[1])?);
        let (u, v) = (plane.to_local(p), plane.to_local(q));
        if (plane.height(p) - level).abs() > tol || (plane.height(q) - level).abs() > tol || u.dist(v) <= tol {
            return None;
        }
        out.push(Seg2::Line { a: u, b: v });
    }
    Some(out)
}

/// A circle (`o + r (cos t x + sin t y)`) from `ts` to `te`, ending at `a` and `b` in `plane`, as
/// the arc it is: `None` when it doesn't lie in a plane parallel to `plane`. A whole circle comes
/// back as its two halves.
#[allow(clippy::too_many_arguments)]
fn circle(o: Vec3, x: Vec3, y: Vec3, radius: f64, ts: f64, te: f64, a: Vec2, b: Vec2, plane: &Plane, tol: f64) -> Option<Vec<Seg2>> {
    let n = plane.normal();
    let z = x.cross(y);
    let tilt = radius * z.cross(n).len();
    let error = (o.len() + radius + plane.origin.len()) * f64::EPSILON * 256.;
    if !(radius.is_finite() && radius > tol) || tilt + error > tol || error > tol * 0.1 {
        return None;
    }
    let center = plane.to_local(o);
    let sweep = (te - ts) * z.dot(n).signum();
    let angular_tol = tol / radius;
    if sweep.abs() > std::f64::consts::TAU + angular_tol || sweep.abs() < angular_tol {
        return None;
    }
    let start = (a - center).angle();
    let end = center + Vec2::new((start + sweep).cos(), (start + sweep).sin()) * radius;
    if end.dist(b) + error > tol.min(ARC_END_TOL) || (a.dist(center) - radius).abs() > tol {
        return None;
    }
    if (sweep.abs() - std::f64::consts::TAU).abs() <= angular_tol {
        let h = sweep.signum() * std::f64::consts::PI;
        return Some(vec![Seg2::Arc { center, radius, start, sweep: h }, Seg2::Arc { center, radius, start: start + h, sweep: h }]);
    }
    Some(vec![Seg2::Arc { center, radius, start, sweep }])
}

/// Several `spans` end to end, from `a` to `b`, each as the segment it is: a span whose control
/// polygon lies along its chord a line, the others as [`free_form`] reads them. Spans whose
/// ends meet are left out; each segment starts where the one before ended.
fn span_by_span(spans: &[Vec<H>], a: Vec2, b: Vec2, tol: f64) -> Option<Vec<Seg2>> {
    let spans: Vec<&Vec<H>> = spans.iter().filter(|s| s.first().zip(s.last()).is_some_and(|(p, q)| point(*p).dist(point(*q)) > tol)).collect();
    if spans.len() < 2 {
        return None;
    }
    let mut out = Vec::with_capacity(spans.len());
    let mut start = a;
    for (i, span) in spans.iter().enumerate() {
        let end = if i + 1 == spans.len() { b } else { point(*span.last()?) };
        let seg = match free_form(std::slice::from_ref(*span), start, end, tol) {
            Some(mut s) => s.pop()?,
            None if span.iter().all(|p| (p[2] - 1.).abs() <= 1e-12) && off_chord(&span.iter().map(|p| point(*p)).collect::<Vec<_>>()) <= tol => {
                Seg2::Line { a: start, b: end }
            }
            None => return None,
        };
        out.push(seg);
        start = end;
    }
    Some(out)
}

/// How far the control points `pts` lie off the chord between the first and the last.
fn off_chord(pts: &[Vec2]) -> f64 {
    let (Some(first), Some(last)) = (pts.first().copied(), pts.last().copied()) else { return f64::INFINITY };
    let chord = last - first;
    let len = chord.len();
    if !(len > 0.) {
        return f64::INFINITY;
    }
    pts.iter().map(|p| chord.cross(*p - first).abs()).fold(0., f64::max) / len
}

/// One Bézier span that is neither a line nor an arc, as the exact free-form segment it is
/// (a font's quadratic or cubic, a conic), its ends `a` and `b`. `None` for several spans (a
/// curve that may wind about more than once), degrees past [`solidcore_record::MAX_BEZIER_DEGREE`],
/// rational spans other than conics, and control polygons with no area (a curve doubling back
/// along a line).
fn free_form(spans: &[Vec<H>], a: Vec2, b: Vec2, tol: f64) -> Option<Vec<Seg2>> {
    let [span] = spans else { return None };
    let pts: Vec<Vec2> = span.iter().map(|p| point(*p)).collect();
    let (first, last) = (*pts.first()?, *pts.last()?);
    if first.dist(a) > tol || last.dist(b) > tol || first.dist(last) <= tol {
        return None;
    }
    // Twice the area the control polygon spans off the chord: none is a line, maybe doubling back.
    let chord = last - first;
    let off = pts.iter().map(|p| chord.cross(*p - first).abs()).fold(0., f64::max) / chord.len();
    if !(off > tol) {
        return None;
    }
    let rational = span.iter().any(|p| (p[2] - 1.).abs() > 1e-12);
    let seg = match (pts.len(), rational) {
        (_, false) => solidcraft_geom::bezier(&pts)?,
        (3, true) => {
            // Weights normalised to 1 at the ends: the middle one is the conic's.
            let (w0, w1, w2) = (span[0][2], span[1][2], span[2][2]);
            let w = w1 / (w0 * w2).sqrt();
            if !(w.is_finite() && w > 1e-9) {
                return None;
            }
            Seg2::Conic { a: first, apex: pts[1], b: last, w }
        }
        _ => return None,
    };
    // The exact ends of the edge (the span's agree within the tolerance).
    let seg = match seg {
        Seg2::Cubic { p1, p2, .. } => Seg2::Cubic { p0: a, p1, p2, p3: b },
        Seg2::Conic { apex, w, .. } => Seg2::Conic { a, apex, b, w },
        Seg2::Bezier { n, mut p } => {
            *p.first_mut()? = a;
            *p.get_mut(n as usize)? = b;
            Seg2::Bezier { n, p }
        }
        other => other,
    };
    Some(vec![seg])
}

/// The spline (`eval` from parameter `ts` to `te`; its Bézier `spans` in the plane, from `a` to
/// `b`) as a circular arc, when whole-span proofs show it is one.
#[allow(clippy::too_many_arguments)]
fn arc(
    eval: &CurveEval,
    (ts, te): (f64, f64),
    spans: &[Vec<H>],
    plane: &Plane,
    a: Vec2,
    b: Vec2,
    tol: f64,
    error: f64,
    work: &mut usize,
) -> Option<Vec<Seg2>> {
    // Samples are only a candidate proposal. Whole-span implicit and oriented
    // angular proofs below are required before converting any spline to an arc.
    let q = plane.to_local(eval.point(ts + (te - ts) * 5. / 16.)?) - a;
    let r = plane.to_local(eval.point(ts + (te - ts) * 11. / 16.)?) - a;
    let det = 2. * (q.x * r.y - q.y * r.x);
    if !det.is_finite() || det.abs() < 1e-300 {
        return None;
    }
    let offset = Vec2::new((q.dot(q) * r.y - r.dot(r) * q.y) / det, (q.x * r.dot(r) - r.x * q.dot(q)) / det);
    let (center, radius) = (a + offset, offset.len());
    if !radius.is_finite() || radius <= tol || !center.x.is_finite() || !center.y.is_finite() {
        return None;
    }
    let mut sweep: f64 = 0.;
    for span in spans {
        let ds = circle_span(span, center, radius, tol, error, 0, work)?;
        if sweep != 0. && sweep.signum() != ds.signum() {
            return None;
        }
        sweep += ds;
    }
    let start = (a - center).angle();
    let end = center + Vec2::new((start + sweep).cos(), (start + sweep).sin()) * radius;
    // The arc ends where the curve does, as closely as a profile loop must close: within `tol`
    // only (which grows with the model), a curve that is merely near a circle (a font's) would
    // come back as an arc ending off the next segment's start, and the loop would not close.
    if end.dist(b) + error > tol.min(ARC_END_TOL) {
        return None;
    }
    let closed = a.dist(b) < tol;
    let angular_tol = tol / radius;
    if sweep.abs() > std::f64::consts::TAU + angular_tol || sweep.abs() < angular_tol {
        return None;
    }
    if closed {
        if (sweep.abs() - std::f64::consts::TAU).abs() > angular_tol {
            return None;
        }
        let h = sweep.signum() * std::f64::consts::PI;
        Some(vec![Seg2::Arc { center, radius, start, sweep: h }, Seg2::Arc { center, radius, start: start + h, sweep: h }])
    } else {
        Some(vec![Seg2::Arc { center, radius, start, sweep }])
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::panic)]
mod tests {
    use super::*;

    fn choose(n: usize, k: usize) -> f64 {
        (0..k).fold(1., |v, i| v * (n - i) as f64 / (i + 1) as f64)
    }
    fn bernstein(power: &[f64], degree: usize) -> Vec<f64> {
        (0..=degree).map(|i| (0..=i.min(power.len() - 1)).map(|k| power[k] * choose(i, k) / choose(degree, k)).sum()).collect()
    }
    fn multiply(a: &[f64], b: &[f64]) -> Vec<f64> {
        let mut out = vec![0.; a.len() + b.len() - 1];
        for (i, x) in a.iter().enumerate() {
            for (j, y) in b.iter().enumerate() {
                out[i + j] += x * y;
            }
        }
        out
    }
    /// The power basis `p` (in t) over the span t = a + h s, in s.
    fn shifted(p: &[f64], a: f64, h: f64) -> Vec<f64> {
        let mut out = vec![0.];
        for c in p.iter().rev() {
            out = multiply(&out, &[a, h]);
            out[0] += c;
        }
        out
    }
    /// A spline of `degree` over spans [k/16, (k+1)/16] (k = 0..16), joined C0 (each interior
    /// knot `degree` times), whose homogeneous `x`, `y`, `w` are the power bases `f(k)` gives
    /// in the span's own parameter s ∈ [0, 1]: a curve that bends only between the knots.
    fn spans(degree: usize, f: impl Fn(usize) -> [Vec<f64>; 3]) -> Curve {
        let mut knots = vec![0.; degree + 1];
        let mut homogeneous: Vec<[f64; 4]> = Vec::new();
        for k in 0..16 {
            let [x, y, w] = f(k);
            let (x, y, w) = (bernstein(&x, degree), bernstein(&y, degree), bernstein(&w, degree));
            let controls = x.iter().zip(y).zip(w).map(|((x, y), w)| [*x, y, 0., w]);
            homogeneous.extend(controls.skip(usize::from(k > 0)));
            knots.extend(std::iter::repeat_n((k + 1) as f64 / 16., degree));
        }
        knots.push(1.);
        Curve::RationalSpline { knots, homogeneous }
    }
    /// The bump s (1 - s) / (1/4) in the span's own parameter: 0 at both its ends (every old
    /// sample location k/16 is a knot), 1 half way along the first span (t = 1/32).
    fn bump(k: usize) -> Vec<f64> {
        if k == 0 { vec![0., 4., -4.] } else { vec![0.] }
    }
    fn bezier_knots(degree: usize) -> Vec<f64> {
        std::iter::repeat_n(0., degree + 1).chain(std::iter::repeat_n(1., degree + 1)).collect()
    }
    /// A NURBS curve of homogeneous control points `(x, y, 0, w)` (power bases in `x`, `y`, `w`).
    fn curve(x: &[f64], y: &[f64], w: &[f64], degree: usize) -> Curve {
        let (x, y, w) = (bernstein(x, degree), bernstein(y, degree), bernstein(w, degree));
        let homogeneous = x.iter().zip(y).zip(w).map(|((x, y), w)| [*x, y, 0., w]).collect();
        Curve::RationalSpline { knots: bezier_knots(degree), homogeneous }
    }
    fn at(c: &Curve, t: f64) -> Vec3 {
        CurveEval::new(c).unwrap().point(t).unwrap()
    }
    /// `c` over its whole domain, run forward (or back).
    fn run(c: &Curve, forward: bool) -> Run<'_> {
        let interval = match c.natural() {
            solidcore_record::brep::Natural::Range(a, b) => [a, b],
            solidcore_record::brep::Natural::Periodic => [0., std::f64::consts::TAU],
        };
        let ends = [at(c, interval[0]), at(c, interval[1])];
        Run { curve: c, interval, forward, ends: if forward { ends } else { [ends[1], ends[0]] } }
    }
    /// The quarter circle of radius 10 about the origin from +x to +y, as a rational quadratic
    /// spline.
    fn quarter() -> Curve {
        let w = std::f64::consts::FRAC_1_SQRT_2;
        Curve::RationalSpline { knots: bezier_knots(2), homogeneous: vec![[10., 0., 0., 1.], [10. * w, 10. * w, 0., w], [0., 10., 0., 1.]] }
    }

    /// Sampling must not certify a spline cap that merely passes through the sample points.
    /// Once that took a single polynomial of degree 17 with a root at each of the 17 old sample
    /// locations k/16, more than a B-rep record holds (MAX_SPLINE_DEGREE 16); here the aliasing is
    /// in the knots instead: a C0 quadratic spline with a knot at every k/16, on the line (or
    /// the circle) at each of them, and bowing off it between (by 1 mm, 1/32 along).
    #[test]
    fn sample_aliasing_does_not_certify_spline_caps() {
        let e = spans(2, |k| {
            let h = 1. / 16.;
            [shifted(&[0., 10.], k as f64 * h, h), bump(k), vec![1.]]
        });
        for k in 0..=16 {
            assert!(at(&e, k as f64 / 16.).y.abs() < 1e-12, "old sample locations must see a line");
        }
        assert!((at(&e, 1. / 32.).y - 1.).abs() < 1e-12);
        assert!(segment(&run(&e, true), &Plane::XY, 1e-3, &mut 2_000_000).is_none());
        // The quarter circle of radius 10, its homogeneous coordinates scaled by 1 + bump / 10 but
        // its weight not: radius 10 at every k/16, 11 at 1/32.
        let w = std::f64::consts::FRAC_1_SQRT_2;
        let (x, y, wt) = ([10., 20. * (w - 1.), 10. * (1. - 2. * w)], [0., 20. * w, 10. * (1. - 2. * w)], [1., 2. * (w - 1.), 2. * (1. - w)]);
        let circle = spans(4, |k| {
            let (a, h) = (k as f64 / 16., 1. / 16.);
            let scale: Vec<f64> = bump(k).iter().enumerate().map(|(i, v)| v / 10. + if i == 0 { 1. } else { 0. }).collect();
            [multiply(&shifted(&x, a, h), &scale), multiply(&shifted(&y, a, h), &scale), shifted(&wt, a, h)]
        });
        for k in 0..=16 {
            let p = at(&circle, k as f64 / 16.);
            assert!((p.x.hypot(p.y) - 10.).abs() < 1e-9, "old sample locations must see a circle");
        }
        let p = at(&circle, 1. / 32.);
        assert!((p.x.hypot(p.y) - 11.).abs() < 1e-9);
        assert!(segment(&run(&circle, true), &Plane::XY, 1e-3, &mut 2_000_000).is_none());
    }

    #[test]
    fn genuine_curves_and_oriented_traversal_are_certified() {
        let arc = quarter();
        for forward in [true, false] {
            let result = segment(&run(&arc, forward), &Plane::XY, 1e-5, &mut 2_000_000).unwrap();
            let Seg2::Arc { center, radius, sweep, .. } = result[0] else { panic!("expected arc") };
            assert!(center.len() < 1e-8 && (radius - 10.).abs() < 1e-8);
            assert!((sweep.abs() - std::f64::consts::FRAC_PI_2).abs() < 1e-8);
            assert_eq!(sweep > 0., forward);
        }
        // A line written at the highest degree a B-rep record holds (MAX_SPLINE_DEGREE).
        let line = curve(&[0., 10.], &[0.], &[1.], solidcraft_geom::bspline::MAX_SPLINE_DEGREE);
        assert!(matches!(segment(&run(&line, true), &Plane::XY, 1e-5, &mut 2_000_000).unwrap()[0], Seg2::Line { .. }));
        // The longitudinal derivative is negative at t=1/3, independently
        // establishing genuine retracing rather than a stationary tangent.
        let backtrack = curve(&[0., 10., -35., 35.], &[0.], &[1.], 3);
        assert!((at(&backtrack, 1. / 3. + 1e-6).x - at(&backtrack, 1. / 3.).x) / 1e-6 < -1.);
        assert!(segment(&run(&backtrack, true), &Plane::XY, 1e-5, &mut 2_000_000).is_none());
        assert!(segment(&run(&arc, true), &Plane::XY, 1e-5, &mut 0).is_none());
    }

    /// A curve read as an arc ends where the curve does, however large the tolerance (it grows
    /// with the part): a font's quadratic that is within a micron of a circle, not on one, is
    /// kept as the curve it is. Read as an arc whose end is a micron off, the outline of a letter
    /// cut into a 2 m plate did not close.
    #[test]
    fn a_curve_near_a_circle_is_not_an_arc_ending_off_it() {
        // A parabola within a micron of the circle through its ends and middle.
        let e = curve(&[0., 2., 0.], &[0., 0., 0.2], &[1.], 2);
        let (a, b) = (Vec2::new(0., 0.), Vec2::new(2., 0.2));
        assert!(at(&e, 1.).dist(Vec3::new(2., 0.2, 0.)) < 1e-12);
        for tol in [1e-5, 2e-3] {
            let segs = segment(&run(&e, true), &Plane::XY, tol, &mut 2_000_000).unwrap();
            let (first, last) = (segs.first().unwrap(), segs.last().unwrap());
            assert!(first.start().dist(a) < 1e-9 && last.end().dist(b) < 1e-9, "{tol}: {segs:?}");
        }
        // A true arc is still one at either tolerance.
        let arc = quarter();
        for tol in [1e-5, 2e-3] {
            assert!(matches!(segment(&run(&arc, true), &Plane::XY, tol, &mut 2_000_000).unwrap()[..], [Seg2::Arc { .. }]));
        }
    }

    #[test]
    fn discontinuous_and_multiple_winding_curves_decline() {
        let spline = |knots: Vec<f64>, homogeneous: Vec<[f64; 4]>| Curve::RationalSpline { knots, homogeneous };
        let w = std::f64::consts::FRAC_1_SQRT_2;
        let p = |x, y, w| [x, y, 0., w];
        let disconnected = spline(
            vec![0., 0., 0., 1., 1., 1., 2., 2., 2.],
            vec![p(10., 0., 1.), p(10. * w, 10. * w, w), p(0., 10., 1.), p(-10., 0., 1.), p(-10. * w, -10. * w, w), p(0., -10., 1.)],
        );
        assert!(segment(&run(&disconnected, true), &Plane::XY, 1e-5, &mut 2_000_000).is_none());
        let skipped_line = spline(vec![0., 0., 1., 1., 2., 2.], vec![p(0., 0., 1.), p(2., 0., 1.), p(5., 0., 1.), p(10., 0., 1.)]);
        assert!(segment(&run(&skipped_line, true), &Plane::XY, 1e-5, &mut 2_000_000).is_none());
        let mut points = vec![p(10., 0., 1.)];
        let mut knots = vec![0., 0., 0.];
        for i in 0..8 {
            let a = i as f64 * std::f64::consts::FRAC_PI_2;
            let b = a + std::f64::consts::FRAC_PI_2;
            points.push(p(10. * ((a + b) / 2.).cos(), 10. * ((a + b) / 2.).sin(), w));
            points.push(p(10. * b.cos(), 10. * b.sin(), 1.));
            knots.extend([i as f64 + 1.; 2]);
        }
        knots.push(8.);
        let twice = spline(knots, points);
        assert!(segment(&run(&twice, true), &Plane::XY, 1e-5, &mut 2_000_000).is_none());
    }
}