Skip to content

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

62.2 KB
Raw Blame
//! Surfaces of portable B-rep faces with a parameter chart, inversion, ray intersection and
//! analytic recognition. Planes are closed form; revolutions are reduced to their 2D profile;
//! spline surfaces use Newton iterations seeded from a sample grid. Records' surfaces are unbounded:
//! a cylinder, cone, sphere, torus or revolution gets its chart's bounds from its face.

use super::HlrError;
use super::curve::{C3, as_circle, frame_axes, v3};
use crate::brep::eval::SurfaceEval;
use crate::brep::{form, placement::Rigid};
use crate::bspline::{HPoint, NurbsSurface};
use crate::prelude::*;
use solidcore_record::Vec3;
use solidcore_record::brep::{Curve, Face, Frame, Surface};

const TAU: f64 = std::f64::consts::TAU;

#[derive(Clone, Debug)]
pub(crate) struct Rev {
    o: Vec3,
    pub a: Vec3,
    e1: Vec3,
    e2: Vec3,
    profile: C3,
    dom: [f64; 2],
    theta: [f64; 2],
    closed: bool,
    /// Profile samples `[s, r, h]`.
    samples: Vec<[f64; 3]>,
    pub rmax: f64,
    hrange: [f64; 2],
}

#[derive(Clone, Debug)]
pub(crate) struct Nurbs {
    s: NurbsSurface,
    dom: [[f64; 2]; 2],
    g: usize,
    /// `(g+1)²` samples, u fastest.
    grid: Vec<Vec3>,
}

#[derive(Clone, Debug)]
pub(crate) enum S3 {
    Plane { o: Vec3, u: Vec3, v: Vec3, n: Vec3 },
    Rev(Box<Rev>),
    Nurbs(Box<Nurbs>),
}

/// What a surface is, when it is a quadric or torus regardless of its record.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) enum Analytic {
    Plane,
    /// A point on the axis, unit axis, radius.
    Cylinder {
        p: Vec3,
        a: Vec3,
        r: f64,
    },
    /// Apex, unit axis (opening direction), half angle.
    Cone {
        apex: Vec3,
        a: Vec3,
        half: f64,
    },
    Sphere {
        c: Vec3,
        r: f64,
    },
    Torus {
        c: Vec3,
        a: Vec3,
        major: f64,
        minor: f64,
    },
    Other,
}

impl Analytic {
    /// Distance from `q` to the whole surface (a cone's nappe near `q`); infinite for planes
    /// and other surfaces, which are not checked this way.
    fn distance(&self, q: Vec3) -> f64 {
        let rh = |o: Vec3, a: Vec3| {
            let w = q - o;
            let h = w.dot(a);
            ((w - a * h).len(), h)
        };
        match *self {
            Analytic::Cylinder { p, a, r } => (rh(p, a).0 - r).abs(),
            Analytic::Cone { apex, a, half } => {
                let (rho, h) = rh(apex, a);
                (rho * half.cos() - h * half.sin()).abs()
            }
            Analytic::Sphere { c, r } => (q.dist(c) - r).abs(),
            Analytic::Torus { c, a, major, minor } => {
                let (rho, h) = rh(c, a);
                ((rho - major).hypot(h) - minor).abs()
            }
            Analytic::Plane | Analytic::Other => f64::INFINITY,
        }
    }

    /// The degree of the surface's implicit equation: 2 for quadrics, 4 for a torus.
    fn implicit_degree(&self) -> usize {
        match self {
            Analytic::Torus { .. } => 4,
            _ => 2,
        }
    }
}

#[derive(Clone, Copy, Debug)]
pub(crate) struct Hit {
    pub lam: f64,
    pub uv: [f64; 2],
    pub grazing: bool,
}

fn perp(a: Vec3) -> Vec3 {
    a.any_perp().normalized().unwrap_or(Vec3::new(1., 0., 0.))
}

impl S3 {
    /// The chart of a face: its surface, in its own parameters where it is a plane or a spline
    /// and in angle and height (angle and angle) where it is a cylinder, cone, sphere or torus,
    /// over the part its NURBS form spans ([`Face::domain`]).
    pub fn of_face(face: &Face) -> Result<S3, HlrError> {
        Ok(match &face.surface {
            Surface::Plane { origin, u_axis, v_axis } => {
                let (u, v) = (v3(*u_axis), v3(*v_axis));
                let n = u.cross(v).normalized().ok_or(HlrError::Unsupported("degenerate plane"))?;
                S3::Plane { o: v3(*origin), u, v, n }
            }
            // The plane through three points: parameter (1, 0) at `u_point`, (0, 1) at `v_point`.
            Surface::PlaneThrough { origin, u_point, v_point } => {
                let o = v3(*origin);
                let (u, v) = (v3(*u_point) - o, v3(*v_point) - o);
                let n = u.cross(v).normalized().ok_or(HlrError::Unsupported("degenerate plane"))?;
                S3::Plane { o, u, v, n }
            }
            Surface::Spline { u_knots, v_knots, points } => {
                let h = points.iter().map(|r| r.iter().map(|p| [p[0], p[1], p[2], 1.]).collect()).collect::<Vec<Vec<_>>>();
                S3::Nurbs(Box::new(Nurbs::new(u_knots, v_knots, &h)?))
            }
            Surface::RationalSpline { u_knots, v_knots, homogeneous } => S3::Nurbs(Box::new(Nurbs::new(u_knots, v_knots, homogeneous)?)),
            Surface::PlacedRevolution { .. } => placed_revolution(face)?,
            label => S3::bounded(label, form_box(face, label)?)?,
        })
    }

    /// A cylinder, cone, sphere or torus over `[angle, along]`: `along` the height on the frame's
    /// axis of a cylinder or cone, the latitude of a sphere, a torus's tube angle from the frame
    /// (its tube start counted in).
    pub fn bounded(s: &Surface, [angle, along]: [[f64; 2]; 2]) -> Result<S3, HlrError> {
        let rev = match s {
            Surface::Cylinder { frame, radius } => {
                let (o, x, _, z) = axes(frame);
                let line = C3::Line { a: o + x * *radius + z * along[0], b: o + x * *radius + z * along[1] };
                Rev::new(o, z, Some(x), line, angle)?
            }
            Surface::Cone { frame, radius_at_origin, half_angle } => {
                let (o, x, _, z) = axes(frame);
                let r = |h: f64| radius_at_origin + h * half_angle.tan();
                let line = C3::Line { a: o + x * r(along[0]) + z * along[0], b: o + x * r(along[1]) + z * along[1] };
                Rev::new(o, z, Some(x), line, angle)?
            }
            Surface::Sphere { frame, radius } => {
                let (o, x, _, z) = axes(frame);
                let arc = C3::Arc { o, x, y: z, r: [*radius, *radius], range: along };
                Rev::new(o, z, Some(x), arc, angle)?
            }
            Surface::Torus { frame, major_radius, minor_radius, .. } => {
                let (o, x, _, z) = axes(frame);
                let arc = C3::Arc { o: o + x * *major_radius, x, y: z, r: [*minor_radius, *minor_radius], range: along };
                Rev::new(o, z, Some(x), arc, angle)?
            }
            _ => return Err(HlrError::Unsupported("surface chart")),
        };
        Ok(S3::Rev(Box::new(rev)))
    }

    /// The recognised quadric or torus as a revolution chart: closed-form inversion and exact
    /// points for trimming, whatever record (spline, rational spline) the face was stored as.
    /// `h` bounds the axial extent of cylinders and cones (the face's boundary along the axis);
    /// `toward` points from a sphere's centre to the face.
    pub fn from_analytic(an: &Analytic, h: [f64; 2], toward: Vec3) -> Option<S3> {
        let rev = match *an {
            Analytic::Cylinder { p, a, r } => {
                let e1 = perp(a);
                Rev::new(p, a, Some(e1), C3::Line { a: p + e1 * r + a * h[0], b: p + e1 * r + a * h[1] }, [0., TAU])
            }
            Analytic::Cone { apex, a, half } => {
                let e1 = perp(a);
                let at = |x: f64| apex + a * x + e1 * (x * half.tan());
                Rev::new(apex, a, Some(e1), C3::Line { a: at(h[0].max(0.)), b: at(h[1].max(0.)) }, [0., TAU])
            }
            Analytic::Sphere { c, r } => {
                // An axis square to the patch's direction keeps the poles off the patch.
                let a = perp(toward);
                let e1 = toward.normalized().unwrap_or_else(|| perp(a));
                let half = std::f64::consts::FRAC_PI_2;
                Rev::new(c, a, Some(e1), C3::Arc { o: c, x: e1, y: a, r: [r, r], range: [-half, half] }, [0., TAU])
            }
            Analytic::Torus { c, a, major, minor } => {
                let e1 = perp(a);
                Rev::new(c, a, Some(e1), C3::Arc { o: c + e1 * major, x: e1, y: a, r: [minor, minor], range: [0., TAU] }, [0., TAU])
            }
            Analytic::Plane | Analytic::Other => return None,
        };
        rev.ok().map(|r| S3::Rev(Box::new(r)))
    }

    /// A box that contains the whole surface for certain: the control-point hull of a spline
    /// (weights are positive), the turned profile's hull for a revolution; `None` for planes.
    pub fn bound(&self) -> Option<(Vec3, Vec3)> {
        let hull = |pts: &mut dyn Iterator<Item = Vec3>| {
            pts.fold(None, |acc: Option<(Vec3, Vec3)>, p| Some(acc.map_or((p, p), |(lo, hi)| (lo.min(p), hi.max(p)))))
        };
        match self {
            S3::Plane { .. } => None,
            S3::Nurbs(n) => hull(&mut n.s.homogeneous().iter().filter_map(|h| h.project())),
            S3::Rev(r) => {
                // Radial distance is convex, so its maximum over the profile's hull is at a vertex.
                let pts: Vec<Vec3> = match &r.profile {
                    C3::Line { a, b } => vec![*a, *b],
                    C3::Polyline(p) => p.clone(),
                    C3::Spline { points, .. } => {
                        points.iter().filter(|h| h[3] > 0.).map(|h| Vec3::new(h[0] / h[3], h[1] / h[3], h[2] / h[3])).collect()
                    }
                    C3::Arc { o, x, y, r: rad, .. } => {
                        // The whole circle's bounding square in its plane.
                        let m = rad[0].max(rad[1]);
                        vec![*o + *x * m + *y * m, *o + *x * m - *y * m, *o - *x * m + *y * m, *o - *x * m - *y * m]
                    }
                };
                let (mut rmax, mut h0, mut h1) = (0f64, f64::MAX, f64::MIN);
                for p in &pts {
                    let w = *p - r.o;
                    let h = w.dot(r.a);
                    rmax = rmax.max((w - r.a * h).len());
                    h0 = h0.min(h);
                    h1 = h1.max(h);
                }
                if !(h1 >= h0) {
                    return None;
                }
                let (c0, c1) = (r.o + r.a * h0, r.o + r.a * h1);
                let ext = |k: f64| rmax * (1. - k * k).max(0.).sqrt();
                let e = Vec3::new(ext(r.a.x), ext(r.a.y), ext(r.a.z));
                Some((c0.min(c1) - e, c0.max(c1) + e))
            }
        }
    }

    /// Silhouette points of a revolution for direction `d`, traced along the profile: at each
    /// profile parameter the normal is perpendicular to `d` at up to two angles. Returns
    /// polylines of exact points with their chord deviation, and exact circles when `d` is the axis.
    pub fn rev_silhouette(&self, d: Vec3) -> Vec<(C3, f64)> {
        let S3::Rev(r) = self else { return Vec::new() };
        r.silhouette(d)
    }

    /// A spline patch whose control points all lie in one plane (to `tol` of its size) as that
    /// plane; the convex hull property puts the whole patch in it.
    pub fn flat(&self, tol: f64) -> Option<S3> {
        let S3::Nurbs(n) = self else { return None };
        let pts: Vec<Vec3> = n.s.homogeneous().iter().filter_map(|h| h.project()).collect();
        let o = *pts.first()?;
        let far = |key: &dyn Fn(Vec3) -> f64| pts.iter().copied().max_by(|a, b| key(*a).total_cmp(&key(*b)));
        let p1 = far(&|p| p.dist(o))?;
        let u = (p1 - o).normalized()?;
        let p2 = far(&|p| (p - o).cross(u).len())?;
        let nrm = u.cross(p2 - o).normalized()?;
        let size = (p1 - o).len();
        pts.iter().all(|p| (*p - o).dot(nrm).abs() <= tol * size).then(|| S3::Plane { o, u, v: nrm.cross(u), n: nrm })
    }

    pub fn domain(&self) -> [[f64; 2]; 2] {
        match self {
            S3::Plane { .. } => [[f64::NEG_INFINITY, f64::INFINITY]; 2],
            S3::Rev(r) => [r.theta, r.dom],
            S3::Nurbs(n) => n.dom,
        }
    }

    pub fn periods(&self) -> [Option<f64>; 2] {
        match self {
            S3::Rev(r) => [((r.theta[1] - r.theta[0]) >= TAU - 1e-9).then_some(TAU), r.closed.then_some(r.dom[1] - r.dom[0])],
            _ => [None, None],
        }
    }

    pub fn point(&self, uv: [f64; 2]) -> Vec3 {
        match self {
            S3::Plane { o, u, v, .. } => *o + *u * uv[0] + *v * uv[1],
            S3::Rev(r) => r.point(uv),
            S3::Nurbs(n) => n.point(uv),
        }
    }

    pub fn partials(&self, uv: [f64; 2]) -> (Vec3, Vec3) {
        match self {
            S3::Plane { u, v, .. } => (*u, *v),
            _ => {
                let d = self.domain();
                let fd = |k: usize| {
                    let span = d[k][1] - d[k][0];
                    let h = span * 1e-6;
                    let lo = if self.periods()[k].is_some() { uv[k] - h } else { (uv[k] - h).max(d[k][0]) };
                    let hi = if self.periods()[k].is_some() { uv[k] + h } else { (uv[k] + h).min(d[k][1]) };
                    let (mut a, mut b) = (uv, uv);
                    a[k] = lo;
                    b[k] = hi;
                    if hi - lo <= 0. { Vec3::ZERO } else { (self.point(b) - self.point(a)) / (hi - lo) }
                };
                (fd(0), fd(1))
            }
        }
    }

    /// The chart normal `Su x Sv`, unit, or `None` at a singular point.
    pub fn normal(&self, uv: [f64; 2]) -> Option<Vec3> {
        match self {
            S3::Plane { n, .. } => Some(*n),
            _ => {
                let (su, sv) = self.partials(uv);
                su.cross(sv).normalized()
            }
        }
    }

    /// Chart coordinates of a point on (or very near) the surface. `hint` guides spline
    /// Newton iterations and the choice of periodic branch.
    pub fn inverse(&self, p: Vec3, hint: Option<[f64; 2]>) -> Option<[f64; 2]> {
        match self {
            S3::Plane { o, u, v, .. } => {
                let w = p - *o;
                let (uu, uv, vv) = (u.dot(*u), u.dot(*v), v.dot(*v));
                let det = uu * vv - uv * uv;
                if det.abs() <= 1e-300 {
                    return None;
                }
                let (bu, bv) = (w.dot(*u), w.dot(*v));
                Some([(bu * vv - bv * uv) / det, (bv * uu - bu * uv) / det])
            }
            S3::Rev(r) => r.inverse(p, hint),
            S3::Nurbs(n) => n.inverse(p, hint),
        }
    }

    /// Ray hits along unit `d` from `p0` with `lam` in `range` (the face's box along the ray).
    pub fn ray(&self, p0: Vec3, d: Vec3, range: [f64; 2], out: &mut Vec<Hit>) {
        match self {
            S3::Plane { n, .. } => {
                let nd = n.dot(d);
                if nd.abs() < 1e-12 {
                    return;
                }
                let lam = n.dot(self.point([0., 0.]) - p0) / nd;
                if lam >= range[0]
                    && lam <= range[1]
                    && let Some(uv) = self.inverse(p0 + d * lam, None)
                {
                    out.push(Hit { lam, uv, grazing: nd.abs() < 1e-6 });
                }
            }
            S3::Rev(r) => r.ray(p0, d, range, out),
            S3::Nurbs(n) => n.ray(p0, d, range, out),
        }
    }

    /// Ray hits using the recognised analytic form when there is one (closed form for
    /// quadrics, a sampled quartic for tori), else the record's own intersection.
    pub fn ray_as(&self, an: &Analytic, p0: Vec3, d: Vec3, range: [f64; 2], out: &mut Vec<Hit>) {
        let lams = match *an {
            Analytic::Cylinder { p, a, r } => {
                let (w, v) = (p0 - p, d - a * d.dot(a));
                let w = w - a * w.dot(a);
                quadratic(v.dot(v), 2. * v.dot(w), w.dot(w) - r * r)
            }
            Analytic::Cone { apex, a, half } => {
                let w = p0 - apex;
                let c2 = half.cos().powi(2);
                let (da, wa) = (d.dot(a), w.dot(a));
                let roots = quadratic(da * da - c2, 2. * (da * wa - c2 * d.dot(w)), wa * wa - c2 * w.dot(w));
                roots.into_iter().filter(|(l, _)| (w + d * *l).dot(a) >= 0.).collect()
            }
            Analytic::Sphere { c, r } => {
                let w = p0 - c;
                quadratic(1., 2. * d.dot(w), w.dot(w) - r * r)
            }
            Analytic::Torus { c, a, major, minor } => torus_roots(p0 - c, d, a, major, minor, range),
            Analytic::Plane | Analytic::Other => return self.ray(p0, d, range, out),
        };
        for (lam, grazing) in lams {
            if lam >= range[0] && lam <= range[1] {
                // The analytic surface extends past this record's domain: keep hits on it only.
                let p = p0 + d * lam;
                if let Some(uv) = self.inverse(p, None).filter(|uv| self.point(*uv).dist(p) <= 1e-7 * (1. + p.len())) {
                    out.push(Hit { lam, uv, grazing });
                }
            }
        }
    }

    /// Which analytic surface this is, checked at sample points to `tol` relative to its size.
    pub fn analytic(&self, tol: f64) -> Analytic {
        match self {
            S3::Plane { .. } => Analytic::Plane,
            S3::Rev(r) => r.analytic(tol),
            S3::Nurbs(n) => n.analytic(tol),
        }
    }
}

/// Real roots of `a x^2 + b x + c`, a double root flagged as grazing.
pub(crate) fn quadratic(a: f64, b: f64, c: f64) -> Vec<(f64, bool)> {
    let scale = b * b + (a * c).abs();
    if a.abs() <= 1e-14 * (1. + b.abs()) {
        return if b.abs() > 1e-300 { vec![(-c / b, false)] } else { Vec::new() };
    }
    let disc = b * b - 4. * a * c;
    if disc < -1e-12 * scale {
        return Vec::new();
    }
    if disc <= 1e-12 * scale {
        return vec![(-b / (2. * a), true)];
    }
    // Numerically stable pair.
    let q = -0.5 * (b + b.signum() * disc.sqrt());
    vec![(q / a, false), (c / q, false)]
}

/// Roots of the torus implicit function along a ray, by sampling and bisection; dips that
/// touch zero without a sign change are grazing.
pub(crate) fn torus_roots(w: Vec3, d: Vec3, a: Vec3, big: f64, small: f64, range: [f64; 2]) -> Vec<(f64, bool)> {
    // Signed distance from the tube: distance to the centre circle less the tube radius,
    // computed directly (no quartic), so a thin tube on a large ring keeps its precision.
    let g = |l: f64| {
        let p = w + d * l;
        let z = p.dot(a);
        let rho = (p - a * z).len();
        (rho - big).hypot(z) - small
    };
    // Sample only where the ray is inside the shell |z| <= r, R - r <= rho <= R + r, in steps
    // of a quarter of the tube radius: the shell is short along any ray, so the steps are few.
    // The shell is padded: a crossing exactly on its surface (rho = R + r at z = 0, say) must
    // fall strictly inside a sampled piece.
    let m = 0.5 * small + 1e-9 * big;
    let (z0, dz) = (w.dot(a), d.dot(a));
    let mut span = range;
    if dz.abs() > 1e-300 {
        let (l0, l1) = ((-small - m - z0) / dz, (small + m - z0) / dz);
        span = [span[0].max(l0.min(l1)), span[1].min(l0.max(l1))];
    } else if z0.abs() > small + m {
        return Vec::new();
    }
    // rho^2 along the ray: |w_perp + l d_perp|^2.
    let (wp, dp) = (w - a * z0, d - a * dz);
    let (qa, qb, qc) = (dp.dot(dp), 2. * wp.dot(dp), wp.dot(wp));
    let within = |r2: f64| -> Option<[f64; 2]> {
        // Where rho^2 <= r2.
        if qa <= 1e-300 {
            return (qc <= r2).then_some([f64::NEG_INFINITY, f64::INFINITY]);
        }
        let disc = qb * qb - 4. * qa * (qc - r2);
        (disc >= 0.).then(|| [(-qb - disc.sqrt()) / (2. * qa), (-qb + disc.sqrt()) / (2. * qa)])
    };
    let Some(outer) = within((big + small + m).powi(2)) else { return Vec::new() };
    span = [span[0].max(outer[0]), span[1].min(outer[1])];
    if !(span[1] > span[0]) {
        return Vec::new();
    }
    // Remove the inside of the inner radius, leaving up to two pieces.
    let mut pieces = vec![span];
    if big > small + m
        && let Some(inner) = within((big - small - m).powi(2))
    {
        pieces = vec![[span[0], span[1].min(inner[0])], [span[0].max(inner[1]), span[1]]];
    }
    // |g| is 1-Lipschitz along the ray: two samples whose values share a sign and add up to
    // more than their distance cannot have a crossing between them. Other pairs are halved down
    // to a thousandth of the tube radius, so a shallow cut through the tube (a chord shorter than
    // the sample step) is still found.
    let fine = 1e-3 * small;
    let mut out = Vec::new();
    for [s0, s1] in pieces.into_iter().filter(|p| p[1] > p[0]) {
        let n = ((s1 - s0) / (0.25 * small)).ceil().clamp(8., 1_000_000.) as usize;
        let at = |i: usize| s0 + (s1 - s0) * i as f64 / n as f64;
        let mut stack: Vec<(f64, f64, f64, f64)> = Vec::new();
        let vals: Vec<f64> = (0..=n).map(|i| g(at(i))).collect();
        for i in 0..n {
            if let (Some(&ga), Some(&gb)) = (vals.get(i), vals.get(i + 1)) {
                stack.push((at(i), at(i + 1), ga, gb));
            }
        }
        stack.reverse();
        let mut budget = 1_000_000usize;
        while let Some((lo0, hi0, ga, gb)) = stack.pop() {
            budget = budget.saturating_sub(1);
            if budget == 0 {
                break;
            }
            if ga != 0. && gb != 0. && ga.signum() != gb.signum() {
                let (mut lo, mut hi, mut glo) = (lo0, hi0, ga);
                for _ in 0..80 {
                    let mid = 0.5 * (lo + hi);
                    let gm = g(mid);
                    if gm.signum() == glo.signum() {
                        lo = mid;
                        glo = gm;
                    } else {
                        hi = mid;
                    }
                }
                out.push((0.5 * (lo + hi), false));
                continue;
            }
            if ga.abs() + gb.abs() > hi0 - lo0 {
                continue;
            }
            if hi0 - lo0 <= fine {
                // Close to the tube without crossing it: a touch when it is a dip inside the shell.
                let m = 0.5 * (lo0 + hi0);
                let gm = g(m);
                if gm > 0. && gm <= ga && gm <= gb && lo0 > s0 && hi0 < s1 && gm < 1e-4 * small.max(1e-9 * big) {
                    out.push((m, true));
                }
                continue;
            }
            let m = 0.5 * (lo0 + hi0);
            let gm = g(m);
            stack.push((m, hi0, gm, gb));
            stack.push((lo0, m, ga, gm));
        }
    }
    out.sort_by(|x, y| x.0.total_cmp(&y.0));
    out.dedup_by(|x, y| (x.0 - y.0).abs() <= fine && x.1 == y.1);
    out
}

/// Steps per direction when a face's NURBS form is read back onto its label: along a direction
/// that turns (at most a turn, in rational quarter arcs) each step stays well within half a turn.
const FORM_STEPS: usize = 16;

/// The angle `x` on the turn nearest `near`.
fn unwrapped(x: f64, near: f64) -> f64 {
    x + TAU * ((near - x) / TAU).round()
}

/// A cylinder, cone, sphere or torus face's box on its label ([`S3::bounded`]): where its form's
/// points over its domain lie on the label's frame, whichever way round the form runs.
fn form_box(face: &Face, label: &Surface) -> Result<[[f64; 2]; 2], HlrError> {
    let frame = match label {
        Surface::Cylinder { frame, .. } | Surface::Cone { frame, .. } | Surface::Sphere { frame, .. } | Surface::Torus { frame, .. } => frame,
        _ => return Err(HlrError::Unsupported("surface chart")),
    };
    let (o, x, y, z) = axes(frame);
    let along = |w: Vec3, rho: f64| match label {
        Surface::Sphere { .. } => w.dot(z).atan2(rho),
        Surface::Torus { major_radius, .. } => w.dot(z).atan2(rho - major_radius),
        _ => w.dot(z),
    };
    let turns = matches!(label, Surface::Torus { .. });
    let (angle, mut second) = sampled_box(face, turns, &|p| {
        let w = p - o;
        let (a, b) = (w.dot(x), w.dot(y));
        let rho = a.hypot(b);
        [rho, b.atan2(a), along(w, rho)]
    })?;
    if !(second[0] < second[1]) {
        return Err(HlrError::Invalid("surface form domain"));
    }
    if turns && second[1] - second[0] >= TAU - 1e-9 {
        second[1] = second[0] + TAU;
    }
    Ok([angle, second])
}

/// The range of the angle about the axis and of a second coordinate over a form's points on a grid
/// of the face's domain; `at` gives a point's distance from the axis, angle and second coordinate,
/// the second an angle too when `turns`. Angles are unwrapped from point to point, row after row, so
/// a face that goes round comes to one turn. On the axis (a pole, an apex) there is no angle.
fn sampled_box(face: &Face, turns: bool, at: &dyn Fn(Vec3) -> [f64; 3]) -> Result<([f64; 2], [f64; 2]), HlrError> {
    let form = face.nurbs.as_ref().ok_or(HlrError::Invalid("analytic surface without its form"))?;
    let eval = SurfaceEval::new(form).map_err(|_| HlrError::Invalid("surface form"))?;
    let [[u0, u1], [v0, v1]] = face.domain;
    let step = |a: f64, b: f64, k: usize| a + (b - a) * k as f64 / FORM_STEPS as f64;
    let mut samples = Vec::with_capacity((FORM_STEPS + 1) * (FORM_STEPS + 1));
    for j in 0..=FORM_STEPS {
        for i in 0..=FORM_STEPS {
            let p = eval.point([step(u0, u1, i), step(v0, v1, j)]).filter(|p| p.is_finite()).ok_or(HlrError::Invalid("surface form"))?;
            samples.push(at(p));
        }
    }
    let widest = samples.iter().fold(0f64, |m, s| m.max(s[0]));
    let (mut angle, mut second) = ([f64::INFINITY, f64::NEG_INFINITY], [f64::INFINITY, f64::NEG_INFINITY]);
    // Each row starts next to the start of the one before.
    let (mut row_a, mut row_s): (Option<f64>, Option<f64>) = (None, None);
    for row in samples.chunks(FORM_STEPS + 1) {
        let (mut last_a, mut last_s) = (row_a, row_s);
        for (i, &[rho, a, s]) in row.iter().enumerate() {
            if rho > 1e-6 * widest {
                let a = last_a.map_or(a, |l| unwrapped(a, l));
                angle = [angle[0].min(a), angle[1].max(a)];
                last_a = Some(a);
                if i == 0 || row_a.is_none() {
                    row_a = Some(a);
                }
            }
            let s = if turns { last_s.map_or(s, |l| unwrapped(s, l)) } else { s };
            second = [second[0].min(s), second[1].max(s)];
            last_s = Some(s);
            if i == 0 {
                row_s = Some(s);
            }
        }
    }
    if !(angle[0] < angle[1]) {
        return Err(HlrError::Invalid("surface form domain"));
    }
    Ok((angle, second))
}

/// A placed revolution's chart. Its placement must be rigid: then it is a revolution of the placed
/// profile about the placed axis. Any other (which may scale it unevenly) is refused. The profile's
/// range is `domain` along it: its own parameter, a conic's on its form's quarter grid.
fn placed_revolution(face: &Face) -> Result<S3, HlrError> {
    let Surface::PlacedRevolution { profile, origin, axis, matrix, forward } = &face.surface else {
        return Err(HlrError::Unsupported("surface chart"));
    };
    let Some(rigid) = Rigid::of_matrix(matrix) else { return Err(HlrError::Unsupported("placed revolution surface")) };
    let along = if *forward { face.domain[0] } else { face.domain[1] };
    let range = match profile.as_ref() {
        Curve::Circle { .. } | Curve::Ellipse { .. } => [form::angle(along[0]), form::angle(along[1])],
        _ => along,
    };
    if matches!(profile.as_ref(), Curve::Circle { .. } | Curve::Ellipse { .. }) && !(range[1] - range[0] <= TAU * (1. + 1e-9)) {
        return Err(HlrError::Invalid("revolution profile range"));
    }
    let rows = rigid.rotation.map(v3);
    let direction = |d: Vec3| Vec3::new(rows[0].dot(d), rows[1].dot(d), rows[2].dot(d));
    let point = |p: Vec3| direction(p) + v3(rigid.translation);
    let curve = C3::bounded(profile, range)?.placed(&point, &direction)?;
    let (o, a) = (point(v3(*origin)), direction(v3(*axis)).normalized().ok_or(HlrError::Unsupported("zero revolution axis"))?);
    let [t0, _] = curve.domain();
    let start = curve.at(t0) - o;
    let e1 = (start - a * start.dot(a)).normalized().unwrap_or_else(|| perp(a));
    let e2 = a.cross(e1);
    let (angle, _) = sampled_box(face, false, &|p| {
        let w = p - o;
        let h = w.dot(a);
        let radial = w - a * h;
        [radial.len(), radial.dot(e2).atan2(radial.dot(e1)), h]
    })?;
    Ok(S3::Rev(Box::new(Rev::new(o, a, Some(e1), curve, angle)?)))
}

fn axes(f: &Frame) -> (Vec3, Vec3, Vec3, Vec3) {
    let (o, x, y) = frame_axes(f);
    (o, x, y, x.cross(y))
}

impl Rev {
    fn new(o: Vec3, axis: Vec3, e1: Option<Vec3>, profile: C3, angle: [f64; 2]) -> Result<Rev, HlrError> {
        let a = axis.normalized().ok_or(HlrError::Unsupported("zero revolution axis"))?;
        let dom = profile.domain();
        let e1 = e1.unwrap_or_else(|| {
            let w = profile.at(dom[0]) - o;
            (w - a * w.dot(a)).normalized().unwrap_or_else(|| perp(a))
        });
        let e2 = a.cross(e1);
        let closed = profile.at(dom[0]).dist(profile.at(dom[1])) <= 1e-9 * (1. + profile.at(dom[0]).dist(o));
        let n = 512;
        let mut samples = Vec::with_capacity(n + 1);
        let (mut rmax, mut hlo, mut hhi) = (0f64, f64::MAX, f64::MIN);
        for i in 0..=n {
            let s = dom[0] + (dom[1] - dom[0]) * i as f64 / n as f64;
            let w = profile.at(s) - o;
            let h = w.dot(a);
            let r = (w - a * h).len();
            rmax = rmax.max(r);
            hlo = hlo.min(h);
            hhi = hhi.max(h);
            samples.push([s, r, h]);
        }
        if !(rmax.is_finite() && hlo.is_finite() && hhi.is_finite()) {
            return Err(HlrError::Unsupported("non-finite revolution profile"));
        }
        // Chart theta is measured from e1; a full turn is [0, 2pi).
        let theta = if angle[1] - angle[0] >= TAU - 1e-9 { [0., TAU] } else { angle };
        Ok(Rev { o, a, e1, e2, profile, dom, theta, closed, samples, rmax, hrange: [hlo, hhi] })
    }

    fn rh(&self, s: f64) -> [f64; 2] {
        let w = self.profile.at(s) - self.o;
        let h = w.dot(self.a);
        [(w - self.a * h).len(), h]
    }

    fn rh_d(&self, s: f64) -> [f64; 2] {
        // Exact for line and arc profiles: a one-sided difference at the domain's ends misses
        // zeros that sit there (a half torus's equators). A difference for the rest.
        let dw = match &self.profile {
            C3::Line { a, b } => Some(*b - *a),
            C3::Arc { x, y, r, .. } => Some(*x * (-r[0] * s.sin()) + *y * (r[1] * s.cos())),
            _ => None,
        };
        if let Some(dw) = dw {
            let w = self.profile.at(s) - self.o;
            let radial = w - self.a * w.dot(self.a);
            let r = radial.len();
            if r > 1e-12 * (1. + self.rmax) {
                return [radial.dot(dw) / r, dw.dot(self.a)];
            }
        }
        let h = (self.dom[1] - self.dom[0]) * 1e-7;
        let (a, b) = ((s - h).max(self.dom[0]), (s + h).min(self.dom[1]));
        if b - a <= 0. {
            return [0., 0.];
        }
        let (p, q) = (self.rh(a), self.rh(b));
        [(q[0] - p[0]) / (b - a), (q[1] - p[1]) / (b - a)]
    }

    fn point(&self, uv: [f64; 2]) -> Vec3 {
        let [r, h] = self.rh(uv[1]);
        self.o + self.a * h + (self.e1 * uv[0].cos() + self.e2 * uv[0].sin()) * r
    }

    /// Profile parameters where component `k` of the profile's (r, h) tangent vanishes: sign
    /// changes between samples, refined by bisection, exact zeros at samples, and for a closed
    /// profile the change across the seam where its ends meet.
    fn roots(&self, ss: &[f64], k: usize) -> Vec<f64> {
        let f = |s: f64| self.rh_d(s).get(k).copied().unwrap_or(0.);
        let vals: Vec<f64> = ss.iter().map(|s| f(*s)).collect();
        let scale = vals.iter().fold(0f64, |m, v| m.max(v.abs())).max(1e-300);
        let zero = |v: f64| v.abs() <= 1e-12 * scale;
        let mut out: Vec<f64> = Vec::new();
        let mut pairs: Vec<(usize, usize)> = (0..ss.len().saturating_sub(1)).map(|i| (i, i + 1)).collect();
        if self.closed && ss.len() > 2 {
            // The last sample repeats the first; the pair across the seam is (n-1, 1).
            pairs.push((ss.len() - 2, 1));
        }
        for (i, sv) in vals.iter().enumerate() {
            if zero(*sv)
                && !(self.closed && i + 1 == vals.len())
                && let Some(s0) = ss.get(i)
            {
                out.push(*s0);
            }
        }
        for (i, j) in pairs {
            let (Some(&a), Some(&b), Some(&sa), Some(&sb)) = (vals.get(i), vals.get(j), ss.get(i), ss.get(j)) else { continue };
            if zero(a) || zero(b) || a.signum() == b.signum() {
                continue;
            }
            // Across the seam, walk sb forward a period so the interval is increasing.
            let sb = if sb < sa { sb + (self.dom[1] - self.dom[0]) } else { sb };
            let wrap = |x: f64| if x > self.dom[1] { x - (self.dom[1] - self.dom[0]) } else { x };
            let (mut lo, mut hi, mut flo) = (sa, sb, a);
            for _ in 0..60 {
                let mid = 0.5 * (lo + hi);
                let fm = f(wrap(mid));
                if fm.signum() == flo.signum() && !zero(fm) {
                    lo = mid;
                    flo = fm;
                } else {
                    hi = mid;
                }
            }
            out.push(wrap(0.5 * (lo + hi)));
        }
        out.sort_by(f64::total_cmp);
        let span = self.dom[1] - self.dom[0];
        out.dedup_by(|x, y| (*x - *y).abs() <= 1e-9 * span);
        // A closed profile's start and end are one point: one root there, not two.
        if self.closed
            && let (Some(&first), Some(&last)) = (out.first(), out.last())
            && out.len() > 1
            && (first + span - last).abs() <= 1e-9 * span
        {
            out.pop();
        }
        out
    }

    /// cos(theta - phi) = dr (a.d) / (dh rho) along the profile; see `S3::rev_silhouette`.
    fn silhouette(&self, d: Vec3) -> Vec<(C3, f64)> {
        let (d1, d2, da) = (d.dot(self.e1), d.dot(self.e2), d.dot(self.a));
        let rho = (d1 * d1 + d2 * d2).sqrt();
        let phi = d2.atan2(d1);
        let n = 720usize;
        let mut ss: Vec<f64> = (0..=n).map(|i| self.dom[0] + (self.dom[1] - self.dom[0]) * i as f64 / n as f64).collect();
        let mut out = Vec::new();
        if rho > 1e-12 {
            // The silhouette exists where |dr (a.d)| <= |dh| rho; near the axis direction those
            // intervals shrink around the zeros of dr, which are sampled so none is stepped over.
            let extra = self.roots(&ss, 0);
            ss.extend(extra);
            ss.sort_by(f64::total_cmp);
            ss.dedup_by(|x, y| (*x - *y).abs() <= 1e-15 * (self.dom[1] - self.dom[0]));
        }
        if rho <= 1e-12 {
            // Along the axis: circles where the profile runs parallel to the axis (dr = 0).
            for s0 in self.roots(&ss, 0) {
                let [r, h] = self.rh(s0);
                if r > 1e-12 {
                    out.push((C3::Arc { o: self.o + self.a * h, x: self.e1, y: self.e2, r: [r, r], range: [0., TAU] }, 0.));
                }
            }
            return out;
        }
        if da.abs() <= 1e-12 {
            // Square to the axis: where the profile runs radially (dh = 0) the normal is the
            // axis, square to d for every angle, so the whole parallel circle is a silhouette.
            for s0 in self.roots(&ss, 1) {
                let [r, h] = self.rh(s0);
                if r > 1e-12 {
                    out.push((C3::Arc { o: self.o + self.a * h, x: self.e1, y: self.e2, r: [r, r], range: [0., TAU] }, 0.));
                }
            }
        }
        let c = |s: f64| {
            let t = self.rh_d(s);
            if t[1].abs() <= 1e-300 { f64::INFINITY } else { t[0] * da / (t[1] * rho) }
        };
        let at = |sign: f64, s: f64| self.point([phi + sign * c(s).clamp(-1., 1.).acos(), s]);
        // The parameter between a (|c| <= 1) and b (|c| > 1) where |c| = 1.
        let edge = |a: f64, b: f64| {
            let (mut lo, mut hi) = (a, b);
            for _ in 0..60 {
                let mid = 0.5 * (lo + hi);
                if c(mid).abs() <= 1. {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
            lo
        };
        // Chords are halved where their middle is further than this from the curve; the angle
        // moves fastest where a branch starts or ends, so uniform samples alone are coarse there.
        let target = 1e-7 * (1. + self.rmax + (self.hrange[1] - self.hrange[0]));
        // One polyline per branch while |c| <= 1.
        for sign in [1., -1.] {
            let mut run: Vec<f64> = Vec::new();
            let flush = |run: &mut Vec<f64>, out: &mut Vec<(C3, f64)>| {
                if run.len() >= 2 {
                    for _ in 0..40 {
                        let mut next = Vec::with_capacity(run.len() * 2);
                        let mut split = false;
                        for w in run.windows(2) {
                            let (Some(&a), Some(&b)) = (w.first(), w.get(1)) else { continue };
                            next.push(a);
                            let m = 0.5 * (a + b);
                            if next.len() < 1 << 16 && at(sign, m).dist_to_segment(at(sign, a), at(sign, b)) > target {
                                next.push(m);
                                split = true;
                            }
                        }
                        if let Some(&last) = run.last() {
                            next.push(last);
                        }
                        *run = next;
                        if !split {
                            break;
                        }
                    }
                    let pts: Vec<Vec3> = run.iter().map(|s| at(sign, *s)).collect();
                    let mut dev = 0f64;
                    for (w, q) in run.windows(2).zip(pts.windows(2)) {
                        let (Some(a), Some(b), Some(pa), Some(pb)) = (w.first(), w.get(1), q.first(), q.get(1)) else { continue };
                        dev = dev.max(at(sign, 0.5 * (a + b)).dist_to_segment(*pa, *pb));
                    }
                    out.push((C3::Polyline(pts), dev));
                }
                run.clear();
            };
            for i in 0..ss.len() {
                let Some(&s) = ss.get(i) else { continue };
                let inside = c(s).abs() <= 1.;
                let prev = i.checked_sub(1).and_then(|j| ss.get(j).copied());
                match (inside, prev.map(|p| c(p).abs() <= 1.)) {
                    (true, Some(false)) => {
                        if let Some(p) = prev {
                            run.push(edge(s, p));
                        }
                        run.push(s);
                    }
                    (true, _) => run.push(s),
                    (false, Some(true)) => {
                        if let Some(p) = prev {
                            run.push(edge(p, s));
                        }
                        flush(&mut run, &mut out);
                    }
                    (false, _) => {}
                }
            }
            flush(&mut run, &mut out);
        }
        out
    }

    /// Closest profile parameter to `(r, h)`, with the squared distance.
    fn closest(&self, q: [f64; 2]) -> (f64, f64) {
        if let C3::Line { .. } = self.profile {
            let (p0, p1) = (self.rh(self.dom[0]), self.rh(self.dom[1]));
            let e = [p1[0] - p0[0], p1[1] - p0[1]];
            let l2 = e[0] * e[0] + e[1] * e[1];
            let t = if l2 > 0. { (((q[0] - p0[0]) * e[0] + (q[1] - p0[1]) * e[1]) / l2).clamp(0., 1.) } else { 0. };
            let s = self.dom[0] + (self.dom[1] - self.dom[0]) * t;
            let p = self.rh(s);
            return (s, (p[0] - q[0]).powi(2) + (p[1] - q[1]).powi(2));
        }
        // Coarse scan, then the finer samples around the best coarse one.
        let mut best = (0usize, f64::MAX);
        for (i, smp) in self.samples.iter().enumerate().step_by(8) {
            let d2 = (smp[1] - q[0]).powi(2) + (smp[2] - q[1]).powi(2);
            if d2 < best.1 {
                best = (i, d2);
            }
        }
        let mut best = (self.samples.get(best.0).map_or(self.dom[0], |s| s[0]), best.1, best.0);
        for i in best.2.saturating_sub(8)..(best.2 + 9).min(self.samples.len()) {
            if let Some(smp) = self.samples.get(i) {
                let d2 = (smp[1] - q[0]).powi(2) + (smp[2] - q[1]).powi(2);
                if d2 < best.1 {
                    best = (smp[0], d2, i);
                }
            }
        }
        let best = (best.0, best.1);
        let mut s = best.0;
        for _ in 0..30 {
            let p = self.rh(s);
            let d = self.rh_d(s);
            let f = (p[0] - q[0]) * d[0] + (p[1] - q[1]) * d[1];
            let fp = d[0] * d[0] + d[1] * d[1];
            if fp <= 1e-300 {
                break;
            }
            let next = (s - f / fp).clamp(self.dom[0], self.dom[1]);
            if (next - s).abs() <= 1e-15 * (1. + s.abs()) {
                s = next;
                break;
            }
            s = next;
        }
        let p = self.rh(s);
        (s, (p[0] - q[0]).powi(2) + (p[1] - q[1]).powi(2))
    }

    fn inverse(&self, p: Vec3, hint: Option<[f64; 2]>) -> Option<[f64; 2]> {
        let w = p - self.o;
        let h = w.dot(self.a);
        let radial = w - self.a * h;
        let r = radial.len();
        let theta = if r > 1e-12 * (1. + self.rmax) { radial.dot(self.e2).atan2(radial.dot(self.e1)) } else { hint.map_or(0., |u| u[0]) };
        let (s, _) = self.closest([r, h]);
        // Of a part of a turn, the copy nearest its middle: an end rounds either way.
        let t =
            if self.theta[1] - self.theta[0] >= TAU - 1e-9 { theta.rem_euclid(TAU) } else { unwrapped(theta, 0.5 * (self.theta[0] + self.theta[1])) };
        Some([t, s])
    }

    /// Signed distance of `(r, h)` from the profile, or `None` beyond an open profile's ends.
    fn signed(&self, q: [f64; 2]) -> Option<f64> {
        let (s, d2) = self.closest(q);
        let at_end = !self.closed && ((s - self.dom[0]).abs() <= 1e-12 * (1. + s.abs()) || (s - self.dom[1]).abs() <= 1e-12 * (1. + s.abs()));
        let p = self.rh(s);
        let t = self.rh_d(s);
        if at_end {
            // Beyond the end the normal distance is undefined unless q projects onto it.
            let along = (q[0] - p[0]) * t[0] + (q[1] - p[1]) * t[1];
            let outward = if (s - self.dom[0]).abs() < (s - self.dom[1]).abs() { -along } else { along };
            if outward > 1e-12 * (1. + self.rmax) {
                return None;
            }
        }
        let cross = t[0] * (q[1] - p[1]) - t[1] * (q[0] - p[0]);
        Some(cross.signum() * d2.sqrt())
    }

    fn ray(&self, p0: Vec3, d: Vec3, range: [f64; 2], out: &mut Vec<Hit>) {
        let rh = |lam: f64| {
            let w = p0 + d * lam - self.o;
            let h = w.dot(self.a);
            [(w - self.a * h).len(), h]
        };
        // Clip the ray to the bounding cylinder, coarsely, by sampling.
        let pad = 1e-6 * (1. + self.rmax + (self.hrange[1] - self.hrange[0]));
        let n = 400usize;
        let f = |lam: f64| {
            let q = rh(lam);
            if q[0] > self.rmax + pad || q[1] < self.hrange[0] - pad || q[1] > self.hrange[1] + pad { None } else { self.signed(q) }
        };
        // Values within the noise floor carry no sign (a ray tangent at its start, say).
        let floor = 1e-9 * (1. + self.rmax + (self.hrange[1] - self.hrange[0]));
        let mut prev: Option<(f64, f64)> = None;
        let mut minima: Vec<(f64, f64)> = Vec::new();
        let mut last: Option<f64> = None;
        let mut falling = false;
        let at = |i: usize| range[0] + (range[1] - range[0]) * i as f64 / n as f64;
        for i in 0..=n {
            let lam = at(i);
            let v = f(lam);
            match (prev, v) {
                (Some((la, fa)), Some(fb)) if fa.abs() > floor && fb.abs() > floor && fa.signum() != fb.signum() => {
                    let (mut lo, mut hi, mut flo) = (la, lam, fa);
                    for _ in 0..80 {
                        let mid = 0.5 * (lo + hi);
                        match f(mid) {
                            Some(fm) if fm.signum() == flo.signum() => {
                                lo = mid;
                                flo = fm;
                            }
                            Some(_) => hi = mid,
                            None => break,
                        }
                    }
                    let lam = 0.5 * (lo + hi);
                    if lam >= range[0]
                        && let Some(uv) = self.inverse(p0 + d * lam, None)
                    {
                        out.push(Hit { lam, uv, grazing: false });
                    }
                }
                _ => {}
            }
            // Interior dips only: the range's first sample is never a minimum.
            if let Some(fb) = v {
                let a = fb.abs();
                if let Some(l) = last {
                    if falling && a > l {
                        minima.push((at(i - 1), l));
                    }
                    falling = a < l;
                }
                last = Some(a);
            } else {
                falling = false;
                last = None;
            }
            match v {
                Some(fb) if fb.abs() > floor => prev = Some((lam, fb)),
                Some(_) => {}
                None => prev = None,
            }
        }
        // Near-tangent rays: a dip close to zero without a sign change.
        let tol = 1e-4 * (1. + self.rmax);
        for (lam, a) in minima {
            if a < tol
                && lam >= range[0]
                && !out.iter().any(|h| (h.lam - lam).abs() < 2. * (range[1] - range[0]) / n as f64)
                && let Some(uv) = self.inverse(p0 + d * lam, None)
            {
                out.push(Hit { lam, uv, grazing: true });
            }
        }
    }

    fn analytic(&self, tol: f64) -> Analytic {
        let size = self.rmax.max(self.hrange[1] - self.hrange[0]).max(1e-9);
        let pts: Vec<[f64; 2]> = self.samples.iter().map(|s| [s[1], s[2]]).collect();
        let (Some(first), Some(last)) = (pts.first(), pts.last()) else { return Analytic::Other };
        // A straight profile: cylinder (constant r), cone, or a plane square to the axis.
        let e = [last[0] - first[0], last[1] - first[1]];
        let el = (e[0] * e[0] + e[1] * e[1]).sqrt();
        let straight = el > 0. && pts.iter().all(|p| ((p[0] - first[0]) * e[1] - (p[1] - first[1]) * e[0]).abs() / el <= tol * size);
        if straight {
            if e[0].abs() <= tol * el {
                return Analytic::Cylinder { p: self.o, a: self.a, r: first[0] };
            }
            if e[1].abs() <= tol * el {
                return Analytic::Plane;
            }
            // Apex where r = 0 on the line.
            let t = -first[0] / e[0];
            let h_apex = first[1] + t * e[1];
            let dir = if e[1] * e[0] > 0. { self.a } else { -self.a };
            let half = (e[0].abs() / el).asin();
            return Analytic::Cone { apex: self.o + self.a * h_apex, a: dir, half };
        }
        // A circular profile: sphere when its centre is on the axis, torus otherwise.
        if let Some((c, _, r)) = as_circle(&self.profile, tol) {
            let w = c - self.o;
            let h = w.dot(self.a);
            let rc = (w - self.a * h).len();
            if rc <= tol * size {
                return Analytic::Sphere { c: self.o + self.a * h, r };
            }
            return Analytic::Torus { c: self.o + self.a * h, a: self.a, major: rc, minor: r };
        }
        Analytic::Other
    }
}

impl Nurbs {
    fn new(u: &[f64], v: &[f64], rows: &[Vec<[f64; 4]>]) -> Result<Nurbs, HlrError> {
        let nu = rows.len();
        let nv = rows.first().map_or(0, Vec::len);
        let pu = u.len().checked_sub(nu + 1).ok_or(HlrError::Unsupported("surface knots"))?;
        let pv = v.len().checked_sub(nv + 1).ok_or(HlrError::Unsupported("surface knots"))?;
        let mut ctrl = Vec::with_capacity(nu * nv);
        for j in 0..nv {
            for row in rows {
                let p = row.get(j).ok_or(HlrError::Unsupported("ragged surface"))?;
                ctrl.push(HPoint { x: p[0], y: p[1], z: p[2], w: p[3] });
            }
        }
        let s = NurbsSurface::from_homogeneous([pu, pv], [u.to_vec(), v.to_vec()], ctrl).map_err(|_| HlrError::Unsupported("spline surface"))?;
        let dom = s.domain();
        let g = (4 * nu.max(nv)).clamp(16, 64);
        let mut n = Nurbs { s, dom, g, grid: Vec::new() };
        let mut grid = Vec::with_capacity((g + 1) * (g + 1));
        for j in 0..=g {
            for i in 0..=g {
                grid.push(n.point(n.grid_uv(i, j)));
            }
        }
        if grid.iter().any(|p| !p.is_finite()) {
            return Err(HlrError::Unsupported("spline surface evaluation"));
        }
        n.grid = grid;
        Ok(n)
    }

    pub fn grid_uv(&self, i: usize, j: usize) -> [f64; 2] {
        let f = |k: usize, x: usize| self.dom[k][0] + (self.dom[k][1] - self.dom[k][0]) * x as f64 / self.g as f64;
        [f(0, i), f(1, j)]
    }

    fn point(&self, uv: [f64; 2]) -> Vec3 {
        let u = uv[0].clamp(self.dom[0][0], self.dom[0][1]);
        let v = uv[1].clamp(self.dom[1][0], self.dom[1][1]);
        self.s.eval(u, v).unwrap_or(Vec3::new(f64::NAN, f64::NAN, f64::NAN))
    }

    fn partials(&self, uv: [f64; 2]) -> (Vec3, Vec3) {
        let fd = |k: usize| {
            let h = (self.dom[k][1] - self.dom[k][0]) * 1e-6;
            let (mut a, mut b) = (uv, uv);
            a[k] = (uv[k] - h).max(self.dom[k][0]);
            b[k] = (uv[k] + h).min(self.dom[k][1]);
            if b[k] - a[k] <= 0. { Vec3::ZERO } else { (self.point(b) - self.point(a)) / (b[k] - a[k]) }
        };
        (fd(0), fd(1))
    }

    fn clamp(&self, uv: [f64; 2]) -> [f64; 2] {
        [uv[0].clamp(self.dom[0][0], self.dom[0][1]), uv[1].clamp(self.dom[1][0], self.dom[1][1])]
    }

    fn inverse(&self, p: Vec3, hint: Option<[f64; 2]>) -> Option<[f64; 2]> {
        let mut uv = match hint {
            Some(h) => self.clamp(h),
            None => {
                let mut best = (0usize, f64::MAX);
                for (k, q) in self.grid.iter().enumerate() {
                    let d = q.dist(p);
                    if d < best.1 {
                        best = (k, d);
                    }
                }
                self.grid_uv(best.0 % (self.g + 1), best.0 / (self.g + 1))
            }
        };
        for _ in 0..40 {
            let (su, sv) = self.partials(uv);
            let r = self.point(uv) - p;
            let (a, b, c) = (su.dot(su), su.dot(sv), sv.dot(sv));
            let det = a * c - b * b;
            if det.abs() <= 1e-300 {
                break;
            }
            let (gu, gv) = (su.dot(r), sv.dot(r));
            let du = (gu * c - gv * b) / det;
            let dv = (gv * a - gu * b) / det;
            let next = self.clamp([uv[0] - du, uv[1] - dv]);
            let moved = (next[0] - uv[0]).abs() + (next[1] - uv[1]).abs();
            uv = next;
            if moved <= 1e-15 * (1. + uv[0].abs() + uv[1].abs()) {
                break;
            }
        }
        uv[0].is_finite().then_some(uv)
    }

    fn ray(&self, p0: Vec3, d: Vec3, range: [f64; 2], out: &mut Vec<Hit>) {
        let ep = perp(d);
        let eq = d.cross(ep);
        let q2 = |p: Vec3| [(p - p0).dot(ep), (p - p0).dot(eq)];
        let g = self.g;
        let start = out.len();
        let proj: Vec<[f64; 2]> = self.grid.iter().map(|p| q2(*p)).collect();
        for j in 0..g {
            for i in 0..g {
                let corners = [(i, j), (i + 1, j), (i + 1, j + 1), (i, j + 1)];
                let pts: Vec<[f64; 2]> = corners.iter().filter_map(|(a, b)| proj.get(b * (g + 1) + a).copied()).collect();
                let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
                for p in &pts {
                    lo = [lo[0].min(p[0]), lo[1].min(p[1])];
                    hi = [hi[0].max(p[0]), hi[1].max(p[1])];
                }
                let pad = 0.25 * ((hi[0] - lo[0]).max(hi[1] - lo[1]));
                if lo[0] - pad > 0. || hi[0] + pad < 0. || lo[1] - pad > 0. || hi[1] + pad < 0. {
                    continue;
                }
                let (a, b) = (self.grid_uv(i, j), self.grid_uv(i + 1, j + 1));
                let mut uv = [0.5 * (a[0] + b[0]), 0.5 * (a[1] + b[1])];
                let mut ok = false;
                for _ in 0..40 {
                    let p = self.point(uv);
                    let f = q2(p);
                    let (su, sv) = self.partials(uv);
                    let (j11, j12, j21, j22) = (su.dot(ep), sv.dot(ep), su.dot(eq), sv.dot(eq));
                    let det = j11 * j22 - j12 * j21;
                    if det.abs() <= 1e-300 {
                        break;
                    }
                    let du = (f[0] * j22 - f[1] * j12) / det;
                    let dv = (f[1] * j11 - f[0] * j21) / det;
                    uv = self.clamp([uv[0] - du, uv[1] - dv]);
                    if du.abs() + dv.abs() <= 1e-14 * (1. + uv[0].abs() + uv[1].abs()) {
                        let r = q2(self.point(uv));
                        ok = r[0].abs() + r[1].abs() <= 1e-9 * (1. + self.size_hint());
                        break;
                    }
                }
                // Keep roots inside this cell (with slack) so neighbouring cells don't repeat them.
                let slack = [(b[0] - a[0]) * 1e-6, (b[1] - a[1]) * 1e-6];
                if !ok || uv[0] < a[0] - slack[0] || uv[0] > b[0] + slack[0] || uv[1] < a[1] - slack[1] || uv[1] > b[1] + slack[1] {
                    continue;
                }
                let p = self.point(uv);
                let lam = (p - p0).dot(d);
                if lam >= range[0] && lam <= range[1] && !out.iter().skip(start).any(|h| (h.lam - lam).abs() <= 1e-9 * (1. + lam)) {
                    let (su, sv) = self.partials(uv);
                    let grazing = su.cross(sv).normalized().is_none_or(|n| n.dot(d).abs() < 1e-6);
                    out.push(Hit { lam, uv, grazing });
                }
            }
        }
    }

    fn size_hint(&self) -> f64 {
        self.grid.first().zip(self.grid.last()).map_or(1., |(a, b)| a.dist(*b))
    }

    /// The recognised form, checked over the whole patch: on each knot span the implicit
    /// equation of a surface of degree d, multiplied out by the weight, is a polynomial of
    /// degree d p by d q in the span's parameters, so it is zero everywhere when zero at
    /// d p + 1 by d q + 1 points. It is checked at d p + 3 by d q + 3 Chebyshev points of
    /// every span and the span's corners: nothing between samples can hide a bump.
    fn analytic(&self, tol: f64) -> Analytic {
        let an = self.candidate(tol);
        if matches!(an, Analytic::Other | Analytic::Plane) {
            return an;
        }
        let pts: Vec<Vec3> = self.s.homogeneous().iter().filter_map(|h| h.project()).collect();
        let hull = pts.iter().skip(1).fold(pts.first().map(|p| (*p, *p)), |acc, p| acc.map(|(lo, hi)| (lo.min(*p), hi.max(*p))));
        let size = hull.map_or(1., |(lo, hi)| (hi - lo).len()).max(1e-9);
        let [pu, pv] = self.s.degree();
        let d = an.implicit_degree();
        let spans = |k: usize| -> Vec<[f64; 2]> {
            let (Some(ks), Some(dom)) = (self.s.knots().get(k), self.dom.get(k)) else { return Vec::new() };
            let mut cuts: Vec<f64> = ks.iter().copied().filter(|x| *x > dom[0] && *x < dom[1]).collect();
            cuts.push(dom[0]);
            cuts.push(dom[1]);
            cuts.sort_by(f64::total_cmp);
            cuts.dedup();
            cuts.windows(2).filter_map(|w| Some([*w.first()?, *w.get(1)?])).collect()
        };
        let nodes = |deg: usize, s: [f64; 2]| -> Vec<f64> {
            let n = d * deg + 3;
            let (mid, half) = (0.5 * (s[0] + s[1]), 0.5 * (s[1] - s[0]));
            let inner = (0..n).map(move |k| mid + half * (std::f64::consts::PI * (2 * k + 1) as f64 / (2 * n) as f64).cos());
            [s[0], s[1]].into_iter().chain(inner).collect()
        };
        // As for circles (curve::as_circle): the largest distance at the points, times the
        // tensor Lebesgue constant (below 16) and the weights' spread to the power d, bounds the
        // distance anywhere on the patch.
        let (w_min, w_max) = self.s.homogeneous().iter().fold((f64::MAX, f64::MIN), |(lo, hi), h| (lo.min(h.w), hi.max(h.w)));
        if !(w_min > 0. && w_max.is_finite()) {
            return Analytic::Other;
        }
        let (su, sv) = (spans(0), spans(1));
        let mut far = 0f64;
        for a in &su {
            let us = nodes(pu, *a);
            for b in &sv {
                for v in nodes(pv, *b) {
                    for u in &us {
                        far = far.max(an.distance(self.point([*u, v])));
                    }
                }
            }
        }
        if 16. * (w_max / w_min).powi(d as i32) * far <= tol * size { an } else { Analytic::Other }
    }

    /// Cylinder/cone/sphere/torus candidates from iso-curves and grid samples.
    fn candidate(&self, tol: f64) -> Analytic {
        let size = self.size_hint().max(1e-9);
        let iso = |k: usize, x: f64| -> C3 {
            let n = 24;
            let pts = (0..=n)
                .map(|i| {
                    let t = self.dom[k][0] + (self.dom[k][1] - self.dom[k][0]) * i as f64 / n as f64;
                    if k == 0 { self.point([t, x]) } else { self.point([x, t]) }
                })
                .collect();
            C3::Polyline(pts)
        };
        let straight = |c: &C3| {
            let C3::Polyline(p) = c else { return false };
            let (Some(a), Some(b)) = (p.first(), p.last()) else { return false };
            let Some(e) = (*b - *a).normalized() else { return false };
            p.iter().all(|q| ((*q - *a) - e * (*q - *a).dot(e)).len() <= tol * size)
        };
        let circle_of = |k: usize, x: f64| -> Option<(Vec3, Vec3, f64)> {
            // Fit through exact surface points, then verify densely.
            let at = |f: f64| {
                let t = self.dom[k][0] + (self.dom[k][1] - self.dom[k][0]) * f;
                if k == 0 { self.point([t, x]) } else { self.point([x, t]) }
            };
            let pts: Vec<Vec3> = (0..=32).map(|i| at(i as f64 / 32.)).collect();
            let sp = C3::Polyline(pts.clone());
            let (a, m, b) = (pts.first().copied()?, pts.get(16).copied()?, pts.get(8).copied()?);
            let (u, v) = (m - a, b - a);
            let n = u.cross(v);
            let n2 = n.len2();
            // Nearly collinear relative to the points' own spacing.
            if n2 <= 1e-24 * u.len2() * v.len2() {
                return None;
            }
            let c = a + (v * u.len2() - u * v.len2()).cross(n) * (1. / (2. * n2));
            let nn = n.normalized()?;
            let r = c.dist(a);
            let ok = match &sp {
                C3::Polyline(p) => p.iter().all(|q| (q.dist(c) - r).abs() <= tol * r && (*q - c).dot(nn).abs() <= tol * r),
                _ => false,
            };
            ok.then_some((c, nn, r))
        };
        for (line_dir, circ_dir) in [(1usize, 0usize), (0, 1)] {
            let mids = [0., 0.5, 1.].map(|f| self.dom[circ_dir][0] + (self.dom[circ_dir][1] - self.dom[circ_dir][0]) * f);
            if !mids.iter().all(|x| straight(&iso(line_dir, *x))) {
                continue;
            }
            let ends = [0., 0.5, 1.].map(|f| self.dom[line_dir][0] + (self.dom[line_dir][1] - self.dom[line_dir][0]) * f);
            let circles: Option<Vec<_>> = ends.iter().map(|x| circle_of(circ_dir, *x)).collect();
            let Some(circles) = circles else { continue };
            let (Some(c0), Some(c2)) = (circles.first(), circles.last()) else { continue };
            let Some(axis) = (c2.0 - c0.0).normalized() else { continue };
            if c0.1.cross(axis).len() > tol {
                continue;
            }
            if (c0.2 - c2.2).abs() <= tol * c0.2 {
                return Analytic::Cylinder { p: c0.0, a: axis, r: c0.2 };
            }
            let dr = (c2.2 - c0.2) / c0.0.dist(c2.0);
            let half = dr.abs().atan();
            let dir = if dr > 0. { axis } else { -axis };
            let apex = c0.0 - dir * (c0.2 / dr.abs());
            return Analytic::Cone { apex, a: dir, half };
        }
        // Sphere: every grid point equidistant from the centre of four spread points. Several
        // spreads are tried: on a patch closed around (a full band) the corners meet at its seam.
        let g = self.g;
        let pick = |i: usize, j: usize| self.grid.get(j * (g + 1) + i).copied();
        let spreads = [
            [(0, 0), (g, 0), (g / 2, g / 2), (0, g)],
            [(0, 0), (g / 2, 0), (g / 4, g), (3 * g / 4, g / 2)],
            [(g / 3, 0), (0, g / 2), (2 * g / 3, g), (g, g / 3)],
        ];
        for q in spreads {
            let (Some(a), Some(b), Some(c), Some(d)) = (pick(q[0].0, q[0].1), pick(q[1].0, q[1].1), pick(q[2].0, q[2].1), pick(q[3].0, q[3].1))
            else {
                continue;
            };
            let Some(centre) = sphere_centre(a, b, c, d) else { continue };
            let r = centre.dist(a);
            if r > 0. && self.grid.iter().all(|p| (p.dist(centre) - r).abs() <= tol * r) {
                return Analytic::Sphere { c: centre, r };
            }
        }
        // Torus: circles both ways, a meridian giving the tube's centre and radius and a
        // parallel the axis; then every grid point on that torus.
        let mid = |k: usize| self.dom.get(k).map_or(0., |d| 0.5 * (d[0] + d[1]));
        for (meridian, parallel) in [(0usize, 1usize), (1, 0)] {
            let (Some(m), Some(p)) = (circle_of(meridian, mid(parallel)), circle_of(parallel, mid(meridian))) else { continue };
            let (a, minor) = (p.1, m.2);
            let c = p.0 + a * (m.0 - p.0).dot(a);
            let major = m.0.dist(c);
            if !(major > 0. && minor > 0.) {
                continue;
            }
            let on = self.grid.iter().all(|q| {
                let w = *q - c;
                let h = w.dot(a);
                (((w - a * h).len() - major).hypot(h) - minor).abs() <= tol * (major + minor)
            });
            if on {
                return Analytic::Torus { c, a, major, minor };
            }
        }
        Analytic::Other
    }
}

fn sphere_centre(a: Vec3, b: Vec3, c: Vec3, d: Vec3) -> Option<Vec3> {
    // Solve 2(p_i - a).x = |p_i|^2 - |a|^2 for i = b, c, d.
    let rows = [b - a, c - a, d - a];
    let rhs = [b.len2() - a.len2(), c.len2() - a.len2(), d.len2() - a.len2()].map(|v| v * 0.5);
    let [r0, r1, r2] = rows;
    let det = r0.dot(r1.cross(r2));
    if det.abs() <= 1e-18 * (1. + r0.len() * r1.len() * r2.len()) {
        return None;
    }
    let x = (r1.cross(r2) * rhs[0] + r2.cross(r0) * rhs[1] + r0.cross(r1) * rhs[2]) / det;
    x.is_finite().then_some(x)
}