ogeom_algo/

convert.rs

//! Whole-shape conversion: everything as NURBS, and general affine
//! transforms over a shape.
//!
//! The geometry-level conversions are exact and were done long ago; what a
//! *shape* needs is the operator that walks it and restates every dependent
//! description, because conversion necessarily reparameterizes: a circle's
//! parameter is its angle and a rational quadratic's is not. So every edge's
//! range moves to its converted curve's domain, and every pcurve is
//! re-derived against a surface whose parameterization has also moved.
//! Re-deriving a pcurve is a *fit* (at the edge's own parameters, so
//! same-parameter holds by construction), which is why this waited for the
//! adaptive fitting core.
//!
//! The affine operator rides on top: an affine map moves a B-spline's
//! control points and nothing else, so the parameterizations of the
//! converted shape survive the transform untouched, including every fitted
//! pcurve, which is the point of converting first.

use crate::build::{attach_pcurve, attach_seam, make_edge_between, make_face_on};
use crate::{Built, History, make_shell, make_solid, make_vertex, make_wire};
use ogeom_core::{OgeomResult, Tolerances, ogeom_bail};
use ogeom_geom::{Curve, Curve2d as _, Curve3d as _, Surface as _, SurfaceGeometry};
use ogeom_math::{GeneralTransform, Point, Point2, Weighted};
use ogeom_topo::{
    EdgeRepr, Filter, Location, Model, NodeData, Orientation, Shape, ShapeType, TShapeId, explore,
    explore_unique,
};
use std::collections::HashMap;

/// One converted edge: the shape, its curve and the curve's own range.
type ConvertedEdge = (Shape, Curve, (f64, f64));

/// A surface's chart window: the `u` then `v` interval.
type ChartWindow = ((f64, f64), (f64, f64));

/// Rebuild a solid with every surface and curve in B-spline form.
///
/// The result is a new solid in world coordinates (every occurrence
/// placement baked in), whose geometry is exactly the original's wherever
/// the conversions are exact (everywhere but the fitted pcurves, whose error
/// is bounded by the fit target derived from the tolerance). History records
/// each original face modified into its converted twin.
///
/// # Errors
///
/// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if the
/// shape is not a solid or a conversion has no exact form (a trimmed
/// surface's basis is converted; nothing else refuses today);
/// [`OgeomError::NotDone`](ogeom_core::OgeomError::NotDone) if a pcurve
/// refit cannot reach its target.
pub fn to_nurbs(model: &mut Model, shape: &Shape, tol: Tolerances) -> OgeomResult<Built> {
    rebuild(model, shape, None, Restate::Nurbs, tol)
}

/// Rebuild a solid with every surface and curve in B-spline form: exactly
/// where a closed form exists, as [`to_nurbs`] does, and fitted within
/// `tolerance` where none does (an offset surface, a helix, an offset
/// curve), where [`to_nurbs`] refuses.
///
/// A fitted curve is same-parameter with the curve it replaces; a fitted
/// surface has its own parameterization, and every trim on it is
/// re-derived.
///
/// # Errors
///
/// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if
/// `tolerance` is not a distance;
/// [`OgeomError::NotDone`](ogeom_core::OgeomError::NotDone) if a fit cannot
/// reach it; as [`to_nurbs`].
pub fn to_nurbs_within(
    model: &mut Model,
    shape: &Shape,
    tolerance: f64,
    tol: Tolerances,
) -> OgeomResult<Built> {
    if !(tolerance.is_finite() && tolerance > 0.0) {
        ogeom_bail!(Construction, "a tolerance of {tolerance} is not a distance");
    }
    let surface = |s: &SurfaceGeometry| -> OgeomResult<Option<(SurfaceGeometry, bool)>> {
        if let Ok(exact) = s.to_bspline(tol) {
            return Ok(Some((exact.into(), false)));
        }
        let fitted = s.fitted_bspline(tolerance, tol)?;
        if !fitted.met {
            ogeom_bail!(
                NotDone,
                "a surface fitted as a spline stays {} away",
                fitted.error
            );
        }
        let fitted: SurfaceGeometry = fitted.curve.into();
        let turned = normals_oppose(s, &fitted, tol)?;
        Ok(Some((fitted, turned)))
    };
    let curve = |c: &Curve, range: (f64, f64)| -> OgeomResult<Option<(Curve, (f64, f64))>> {
        if let Ok(exact) = c.to_bspline_over(range, tol) {
            let exact: Curve = exact.into();
            let domain = exact.domain();
            return Ok(Some((exact, domain)));
        }
        let fitted = c.fitted_bspline_over(range, tolerance, tol)?;
        if !fitted.met {
            ogeom_bail!(
                NotDone,
                "a curve fitted as a spline stays {} away",
                fitted.error
            );
        }
        Ok(Some((fitted.curve.into(), range)))
    };
    rebuild(model, shape, None, Restate::With(&surface, &curve), tol)
}

/// Whether `new`'s normal points against `old`'s where they meet, read
/// off the middle of `old`'s chart: what a restatement reports when it
/// replaces a surface by one of the same points.
///
/// # Errors
///
/// As [`project_on_surface`](crate::project_on_surface), and if either
/// surface has no normal there.
pub fn normals_oppose(
    old: &SurfaceGeometry,
    new: &SurfaceGeometry,
    tol: Tolerances,
) -> OgeomResult<bool> {
    let ((u0, u1), (v0, v1)) = old.domain();
    // Off the exact middle: a revolution's middle can sit on its axis.
    let (u, v) = (u0 + (u1 - u0) * 0.43, v0 + (v1 - v0) * 0.57);
    let p = old.point_at(u, v, tol)?;
    let n_old = old.normal_at(u, v, tol)?;
    let at = crate::measure::project_on_surface(new, p, 16, tol)?.parameters;
    let n_new = new.normal_at(at.0, at.1, tol)?;
    Ok(n_old.vector().dot(n_new.vector()) < 0.0)
}

/// Rebuild a solid with its placements baked into the geometry, keeping
/// every surface and curve in its own analytic vocabulary.
///
/// A uniform-scale placement carries a cylinder to a cylinder and a line to
/// a line (`Transformable` states each exactly), but the stored pcurves
/// describe the *old* parameterizations. This rebuild restates the geometry
/// in world space and re-derives every pcurve against it, exact where the
/// chart alignment allows and projection-fitted with recorded slop where
/// not, which is what lets a scaled shape enter the boolean's analytic
/// pipeline instead of refusing.
///
/// # Errors
///
/// As [`to_nurbs`].
pub fn baked_shape(model: &mut Model, shape: &Shape, tol: Tolerances) -> OgeomResult<Built> {
    rebuild(model, shape, None, Restate::Keep, tol)
}

/// Rebuild a solid under a general affine transform.
///
/// A shear or an uneven scale is not a placement: it carries a circle to an
/// ellipse and a sphere to something with no analytic name here, so the
/// shape is converted to its exact B-spline form and the *control points*
/// are moved, which an affine map does exactly. The pcurves fitted during
/// conversion survive untouched, because an affine map does not
/// reparameterize.
///
/// A similarity is the other case, and it is a placement. The kernel's own
/// types already draw that line: [`Transform`](ogeom_math::Transform) is a
/// similarity by construction and is kept apart from [`GeneralTransform`]
/// precisely so analytic geometry survives one, so a similarity handed in
/// here is applied as the placement it is. Converting it would be worse than
/// wasteful: a restated plane is still that plane but no longer *says* so,
/// and coincidence downstream is decided on what the geometry says. Two
/// coplanar faces would stop being coplanar *surfaces*, no closed form would
/// answer `Same` for them, and the boolean would be handed a coincident pair
/// with nothing to recognize it by.
///
/// # Errors
///
/// As [`to_nurbs`], or as [`transformed`](crate::transformed) for a similarity.
pub fn general_transformed_shape(
    model: &mut Model,
    shape: &Shape,
    transform: &GeneralTransform,
    tol: Tolerances,
) -> OgeomResult<Built> {
    if let Some(similarity) = transform.to_similarity(tol.angular()) {
        return crate::place::transformed(model, shape, similarity);
    }
    rebuild(model, shape, Some(transform), Restate::Nurbs, tol)
}

/// A caller's restatement of a surface: the new surface and whether its
/// normal points against the old one's, or `None` to keep it.
pub type SurfaceRestatement<'a> =
    &'a dyn Fn(&SurfaceGeometry) -> OgeomResult<Option<(SurfaceGeometry, bool)>>;

/// A caller's restatement of a curve over a range: the new curve and the
/// range on it tracing the same points, or `None` to keep it.
pub type CurveRestatement<'a> =
    &'a dyn Fn(&Curve, (f64, f64)) -> OgeomResult<Option<(Curve, (f64, f64))>>;

/// Rebuild a solid with its surfaces and curves restated by the caller,
/// every placement baked in and every pcurve re-derived against the new
/// surfaces at the new edges' parameters.
///
/// `surface` is handed each face's surface, placed and bounded to the face;
/// `curve` each edge's curve, placed, with the edge's range on it. Each
/// answers `None` to keep what it was handed. A restatement must trace the
/// same points: the rebuild re-derives trims, it does not move boundaries.
///
/// # Errors
///
/// As [`to_nurbs`], and whatever a restatement returns.
pub fn restate_geometry(
    model: &mut Model,
    shape: &Shape,
    surface: SurfaceRestatement<'_>,
    curve: CurveRestatement<'_>,
    tol: Tolerances,
) -> OgeomResult<Built> {
    rebuild(model, shape, None, Restate::With(surface, curve), tol)
}

/// How a rebuild restates the geometry it carries.
#[derive(Clone, Copy)]
enum Restate<'a> {
    /// As it is, placed.
    Keep,
    /// As B-splines, exactly.
    Nurbs,
    /// As the caller says.
    With(SurfaceRestatement<'a>, CurveRestatement<'a>),
}

/// The shared engine: convert, refit, optionally move control points.
fn rebuild(
    model: &mut Model,
    shape: &Shape,
    affine: Option<&GeneralTransform>,
    restate: Restate<'_>,
    tol: Tolerances,
) -> OgeomResult<Built> {
    if model.kind_of(shape)? != ShapeType::Solid {
        ogeom_bail!(Construction, "whole-shape conversion rebuilds solids");
    }
    let map = |p: Point| affine.map_or(p, |t| t.apply(p));
    // The fit target for re-derived pcurves: comfortably inside the model's
    // own working band.
    let target = tol.confusion() * 1e2;

    let mut history = History::new();
    let mut new_vertices: HashMap<(TShapeId, [u64; 3]), Shape> = HashMap::new();
    let mut new_edges: HashMap<(TShapeId, [u64; 3]), ConvertedEdge> = HashMap::new();
    let mut shells = Vec::new();

    for shell in explore_unique(model, shape, ShapeType::Shell)? {
        let mut faces = Vec::new();
        for face in model.ordered_children_of(&shell)? {
            let placement = face.transform(model.datums())?;
            let (surface_id_old, old_surface) = {
                let Some(node) = model.node(&face) else {
                    ogeom_bail!(Dangling, "face is not in this model");
                };
                let NodeData::Face(data) = node.data() else {
                    ogeom_bail!(Construction, "face node holds no face data");
                };
                let Some(surface) = model.geometry().surface(data.surface) else {
                    ogeom_bail!(Dangling, "face refers to a surface not in this model");
                };
                (data.surface, surface.clone())
            };
            use ogeom_geom::Transformable as _;
            let placed = old_surface.transformed(&placement, tol)?;
            // Bounded to the face's own chart region first: a plane declares
            // an enormous domain, and a patch over all of it would map the
            // face to a dot in its chart.
            let (placed, old_window) = bounded_to_face(
                model,
                &face,
                surface_id_old,
                &placed,
                placement.scale_factor().abs(),
                tol,
            )?;
            let mut flipped = false;
            let patch_surface: SurfaceGeometry = match restate {
                Restate::Nurbs => {
                    let mut patch = placed.to_bspline(tol)?;
                    if let Some(t) = affine {
                        patch = transformed_patch(&patch, t)?;
                    }
                    patch.into()
                }
                Restate::Keep => placed.clone(),
                Restate::With(surface, _) => match surface(&placed)? {
                    Some((restated, flip)) => {
                        flipped = flip;
                        restated
                    }
                    None => placed.clone(),
                },
            };
            let surface_id = model.geometry_mut().add_surface(patch_surface.clone());

            let mut wires = Vec::new();
            let mut corner_uv: HashMap<TShapeId, Point2> = HashMap::new();
            for wire in model.ordered_children_of(&face)? {
                let mut ring = Vec::new();
                let mut seams_done: Vec<TShapeId> = Vec::new();
                for edge in model.ordered_children_of(&wire)? {
                    let edge_placement = edge.transform(model.datums())?;
                    let key = (edge.node(), placement_bits(&edge_placement));
                    let data = {
                        let Some(data) = model.node(&edge).and_then(|n| n.data().as_edge()) else {
                            ogeom_bail!(Construction, "edge node holds no edge data");
                        };
                        data.clone()
                    };
                    if data.degenerate {
                        // A pole or an apex: still an edge in parameter
                        // space; its pcurve is rebuilt below from the old
                        // chart row's place in the new chart.
                        let Some(vertex) = model.children_of(&edge)?.first().cloned() else {
                            ogeom_bail!(Construction, "a degenerate edge has no vertex");
                        };
                        let at = {
                            let Some(v) = model.node(&vertex).and_then(|n| n.data().as_vertex())
                            else {
                                ogeom_bail!(Construction, "vertex node holds no vertex data");
                            };
                            map(vertex.transform(model.datums())?.apply(v.point))
                        };
                        let new_vertex = new_vertices
                            .entry((vertex.node(), point_bits(at)))
                            .or_insert_with(|| make_vertex(model, at).shape)
                            .clone();
                        let mut degenerate = ogeom_topo::EdgeData::new();
                        degenerate.degenerate = true;
                        let new_edge =
                            model.add_edge(degenerate, &[new_vertex.clone(), new_vertex])?;
                        let row = degenerate_row(
                            model,
                            &data,
                            surface_id_old,
                            &edge,
                            &placed,
                            &patch_surface,
                            tol,
                        )?;
                        attach_pcurve(
                            model,
                            &new_edge,
                            row.into(),
                            surface_id,
                            Location::identity(),
                            row.domain(),
                        )?;
                        ring.push(if edge.orientation() == Orientation::Reversed {
                            new_edge.reversed()
                        } else {
                            new_edge
                        });
                        continue;
                    }

                    let (new_edge, new_curve, new_range) = match new_edges.get(&key) {
                        Some(found) => found.clone(),
                        None => {
                            let built = convert_edge(
                                model,
                                &edge,
                                &data,
                                &map,
                                restate,
                                &mut new_vertices,
                                tol,
                            )?;
                            history.modify(&edge, built.0.clone());
                            new_edges.insert(key, built.clone());
                            built
                        }
                    };

                    // The pcurve on this face: fitted at the new edge's own
                    // parameters, seam sides each fitted against their own
                    // half of the chart.
                    let old_repr = data.pcurve_for(surface_id_old, edge.location()).cloned();
                    let was_seam = matches!(old_repr, Some(EdgeRepr::Seam { .. }));
                    if was_seam {
                        if !seams_done.contains(&new_edge.node()) {
                            seams_done.push(new_edge.node());
                            let (forward, reversed) =
                                exact_seam_columns(&new_curve, new_range, &patch_surface, tol)
                                    .map_or_else(
                                        || {
                                            seam_pcurves(
                                                &new_curve,
                                                new_range,
                                                &patch_surface,
                                                target,
                                                tol,
                                            )
                                        },
                                        Ok,
                                    )?;
                            let seam_range = forward.domain();
                            attach_seam(
                                model,
                                &new_edge,
                                forward,
                                reversed,
                                surface_id,
                                Location::identity(),
                                seam_range,
                            )?;
                        }
                    } else {
                        // The exact path: an edge that ran along the old
                        // chart's iso direction runs along the new chart's,
                        // and the boundary conversion shares the patch
                        // direction's parameterization by construction.
                        if let Some(iso) = exact_iso_pcurve(
                            model,
                            old_repr.as_ref(),
                            old_window,
                            &new_curve,
                            new_range,
                            &patch_surface,
                            tol,
                        )? {
                            let iso_range = iso.domain();
                            attach_pcurve(
                                model,
                                &new_edge,
                                iso,
                                surface_id,
                                Location::identity(),
                                iso_range,
                            )?;
                            ring.push(if edge.orientation() == Orientation::Reversed {
                                new_edge.reversed()
                            } else {
                                new_edge
                            });
                            continue;
                        }
                        let uv_of = |model: &Model,
                                     cache: &mut HashMap<TShapeId, Point2>,
                                     vertex: &Shape|
                         -> OgeomResult<Point2> {
                            if let Some(&uv) = cache.get(&vertex.node()) {
                                return Ok(uv);
                            }
                            let Some(v) = model.node(vertex).and_then(|n| n.data().as_vertex())
                            else {
                                ogeom_bail!(Construction, "vertex node holds no vertex data");
                            };
                            let projection = crate::measure::project_on_surface(
                                &patch_surface,
                                v.point,
                                24,
                                tol,
                            )?;
                            let uv = Point2::new(projection.parameters.0, projection.parameters.1);
                            cache.insert(vertex.node(), uv);
                            Ok(uv)
                        };
                        let bounds = model.children_of(&new_edge)?;
                        // A closed edge (a rim) has one vertex at both
                        // ends, and near a seam its single chart image is
                        // one side's; pinning both ends there would fold the
                        // ring. Its trace closes on its own.
                        let closed_edge =
                            bounds.len() < 2 || bounds[0].node() == bounds[bounds.len() - 1].node();
                        let ends = if closed_edge {
                            (None, None)
                        } else {
                            (
                                Some(uv_of(model, &mut corner_uv, &bounds[0])?),
                                Some(uv_of(model, &mut corner_uv, &bounds[bounds.len() - 1])?),
                            )
                        };
                        // Exact wherever the chart has a closed form: the
                        // melt downstream compares these images against
                        // exact geometry, and a fitted stand-in for a
                        // closed-form projection carries slop for nothing.
                        let derived = match ogeom_intersect::exact_pcurve_over(
                            &new_curve,
                            new_range,
                            &patch_surface,
                            tol,
                        ) {
                            Some(exact) => exact,
                            None => {
                                let fitted = fit_pcurve(
                                    &new_curve,
                                    new_range,
                                    &patch_surface,
                                    None,
                                    ends,
                                    target,
                                    tol,
                                )?;
                                // The fit's honest slop rides the edge, so
                                // every downstream filter widens by it,
                                // and rides its vertices, which bound the
                                // edge and cannot be held tighter than it.
                                let widened = if let Some(node) = model.node_mut(&new_edge)
                                    && let ogeom_topo::NodeData::Edge(data) = node.data_mut()
                                {
                                    data.tolerance = data.tolerance.widen_to(target);
                                    Some(data.tolerance)
                                } else {
                                    None
                                };
                                if let Some(widened) = widened {
                                    for vertex in model.ordered_children_of(&new_edge)? {
                                        model.widen(&vertex, widened)?;
                                    }
                                }
                                fitted
                            }
                        };
                        attach_pcurve(
                            model,
                            &new_edge,
                            derived,
                            surface_id,
                            Location::identity(),
                            new_range,
                        )?;
                    }
                    ring.push(if edge.orientation() == Orientation::Reversed {
                        new_edge.reversed()
                    } else {
                        new_edge
                    });
                }
                wires.push(make_wire(model, &ring, tol)?.shape);
            }
            let built = make_face_on(model, surface_id, &wires, tol)?.shape;
            // The rebuilt chart is right-handed wherever the old one stood;
            // a reflecting placement flipped the old chart's natural normal,
            // and the flag must carry that flip or the baked solid comes
            // out inside-out.
            // A restated surface whose normal turned is the same flip.
            let reflected = !face.location().preserves_handedness(model.datums())? != flipped;
            let built = if (face.orientation() == Orientation::Reversed) != reflected {
                built.reversed()
            } else {
                built
            };
            history.modify(&face, built.clone());
            faces.push(built);
        }
        shells.push(make_shell(model, &faces)?.shape);
    }
    let solid = make_solid(model, &shells)?.shape;
    history.modify(shape, solid.clone());
    Ok(Built::new(solid, history))
}

/// One edge converted: exact B-spline over its range, vertices carried.
fn convert_edge(
    model: &mut Model,
    edge: &Shape,
    data: &ogeom_topo::EdgeData,
    map: &dyn Fn(Point) -> Point,
    restate: Restate<'_>,
    vertices: &mut HashMap<(TShapeId, [u64; 3]), Shape>,
    tol: Tolerances,
) -> OgeomResult<(Shape, Curve, (f64, f64))> {
    let Some(EdgeRepr::Curve3d { curve, range, .. }) = data.curve3d() else {
        ogeom_bail!(Construction, "an edge with no curve cannot be converted");
    };
    let Some(geometry) = model.geometry().curve(*curve).cloned() else {
        ogeom_bail!(Dangling, "curve is not in this model");
    };
    let placement = edge.transform(model.datums())?;
    use ogeom_geom::Transformable as _;
    let placed = geometry.transformed(&placement, tol)?;
    // A placement with scale rescales a length-parameterized curve's domain
    // (the same rule `transformed` itself applies), so the edge's range
    // must move with it or the conversion covers only part of the edge.
    let stretch = placement.scale_factor().abs();
    let range_on_placed = match &geometry {
        Curve::Line(_) => (range.0 * stretch, range.1 * stretch),
        Curve::Trimmed(t) if matches!(t.basis(), Curve::Line(_)) => {
            (range.0 * stretch, range.1 * stretch)
        }
        _ => *range,
    };
    let (curve, new_range): (Curve, (f64, f64)) = if matches!(restate, Restate::Nurbs) {
        let spline = placed.to_bspline_over(range_on_placed, tol)?;
        // The affine map moves control points; the parameterization and the
        // weights stay, which is the whole point of converting first.
        let weighted: Vec<Weighted<Point>> = spline
            .control_points()
            .iter()
            .map(|c| {
                let p = Point::from_vector(c.scaled.to_vector() / c.weight);
                Weighted::new(map(p), c.weight, tol)
            })
            .collect::<OgeomResult<_>>()?;
        let spline = ogeom_geom::BSplineCurve::rational(spline.knots().clone(), weighted)?;
        let curve: Curve = spline.into();
        let range = curve.domain();
        (curve, range)
    } else if let Restate::With(_, restated) = restate {
        restated(&placed, range_on_placed)?.unwrap_or((placed, range_on_placed))
    } else {
        (placed, range_on_placed)
    };
    // Vertices are shared across every edge that meets them: cached by the
    // old node and the old vertex's own mapped point: the same bits every
    // neighbouring edge computes, unlike each spline's evaluated end.
    let old = model.children_of(edge)?;
    if old.is_empty() {
        ogeom_bail!(Construction, "an edge with no vertices cannot be converted");
    }
    let mut resolve = |model: &mut Model, occurrence: &Shape| -> OgeomResult<Shape> {
        let Some(data) = model
            .node(occurrence)
            .and_then(|n| n.data().as_vertex().cloned())
        else {
            ogeom_bail!(Construction, "vertex node holds no vertex data");
        };
        // The vertex's *own* composed placement, not the edge's: a prism's
        // far cap references the profile's vertex nodes under the travel,
        // and an edge placed identically still ends on a moved vertex.
        let at = map(occurrence.transform(model.datums())?.apply(data.point));
        let fresh = vertices
            .entry((occurrence.node(), point_bits(at)))
            .or_insert_with(|| make_vertex(model, at).shape)
            .clone();
        // The old vertex's recorded slop (a file's, or a fit's) is the
        // new one's too: the curves it meets are the same curves, moved
        // exactly, and a vertex born at the default tolerance would refuse
        // the edge its twin accepted.
        if data.tolerance.get() > tol.confusion() {
            model.widen(&fresh, data.tolerance)?;
        }
        Ok(fresh)
    };
    let va = resolve(model, &old[0])?;
    let vb = if old.len() == 1 {
        va.clone()
    } else {
        resolve(model, &old[old.len() - 1])?
    };
    let built = make_edge_between(model, curve.clone(), new_range, &va, &vb, tol)?.shape;
    if data.tolerance.get() > tol.confusion()
        && let Some(node) = model.node_mut(&built)
        && let NodeData::Edge(fresh) = node.data_mut()
    {
        fresh.tolerance = fresh.tolerance.widen_to(data.tolerance.get());
    }
    Ok((built, curve, new_range))
}

/// A pcurve refit at the edge's own parameters, optionally biased toward one
/// side of the chart's `u` seam.
#[allow(clippy::too_many_arguments)]
fn fit_pcurve(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    side: Option<f64>,
    ends: (Option<Point2>, Option<Point2>),
    target: f64,
    tol: Tolerances,
) -> OgeomResult<ogeom_geom::PlanarCurve> {
    const SAMPLES: usize = 48;
    let ((u0, u1), _) = surface.domain();
    let mut parameters = Vec::with_capacity(SAMPLES + 1);
    let mut trace = Vec::with_capacity(SAMPLES + 1);
    for i in 0..=SAMPLES {
        #[allow(clippy::cast_precision_loss)]
        let t = range.0 + (range.1 - range.0) * i as f64 / SAMPLES as f64;
        let p = curve.point_at(t, tol)?;
        let projection = crate::measure::project_on_surface(surface, p, 24, tol)?;
        let (mut u, v) = projection.parameters;
        if let Some(bias) = side {
            // A point exactly on the seam projects to either side; the bias
            // names which column this pcurve is.
            if (u - u0).abs() < (u1 - u0) * 0.25 || (u - u1).abs() < (u1 - u0) * 0.25 {
                u = bias;
            }
        }
        parameters.push(t);
        trace.push(Point2::new(u, v));
    }
    // A closed patch is clamped, not periodic, but its geometry still closes:
    // a trace crossing the closure jumps by the whole u span. Unwrapped, the
    // fit sees the continuous curve the edge is; the pcurve may leave [u0,u1]
    // by a little at the join, which evaluation tolerates.
    let span = u1 - u0;
    for i in 1..trace.len() {
        let mut du = trace[i].x - trace[i - 1].x;
        while du > span * 0.5 {
            trace[i].x -= span;
            du = trace[i].x - trace[i - 1].x;
        }
        while du < -span * 0.5 {
            trace[i].x += span;
            du = trace[i].x - trace[i - 1].x;
        }
    }
    // Ring corners are shared property: every edge meeting a vertex uses the
    // vertex's own chart image, projected once per face, so the ring closes
    // exactly instead of to each fit's own rounding.
    if let Some(start) = ends.0
        && let Some(first) = trace.first_mut()
    {
        *first = start;
    }
    if let Some(end) = ends.1
        && let Some(last) = trace.last_mut()
    {
        *last = end;
    }
    let fitted = ogeom_geom::fit::fit_points_2d_at(&parameters, &trace, 3, target, tol)?;
    Ok(fitted.curve.into())
}

/// An exact iso pcurve in the new chart, when the old one was an iso line.
///
/// Both endpoints project onto the patch; the pcurve is the straight chart
/// segment between them, exact because the boundary conversion and the patch
/// direction share one parameterization. `None` for anything that was not an
/// axis-aligned chart line, which takes the fitted path.
fn exact_iso_pcurve(
    model: &Model,
    old_repr: Option<&EdgeRepr>,
    _old_window: ChartWindow,
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    tol: Tolerances,
) -> OgeomResult<Option<ogeom_geom::PlanarCurve>> {
    let Some(EdgeRepr::PCurve { curve: old_pc, .. }) = old_repr else {
        return Ok(None);
    };
    let Some(ogeom_geom::PlanarCurve::Line(old_line)) = model.geometry().pcurve(*old_pc) else {
        return Ok(None);
    };
    let d = old_line.axis().direction;
    let axis_aligned = d.vector().x.abs() <= 1e-12 || d.vector().y.abs() <= 1e-12;
    if !axis_aligned {
        return Ok(None);
    }
    let ((nu0, nu1), (nv0, nv1)) = surface.domain();
    let start = curve.point_at(range.0, tol)?;
    let end = curve.point_at(range.1, tol)?;
    let a = crate::measure::project_on_surface(surface, start, 24, tol)?;
    let b = crate::measure::project_on_surface(surface, end, 24, tol)?;
    let mut a = Point2::new(a.parameters.0, a.parameters.1);
    let mut b = Point2::new(b.parameters.0, b.parameters.1);
    let row = d.vector().y.abs() <= 1e-12;
    if row {
        // A row's v is one value; the endpoints agree up to projection noise,
        // and a full-width row on a closed chart runs edge to edge, its
        // seam-side endpoints snapped to the chart's own edges.
        let v = f64::midpoint(a.y, b.y);
        a.y = v;
        b.y = v;
        let span = nu1 - nu0;
        // On the closure both chart edges image the same point, and the
        // projection answers with either: a half circle from the seam
        // round the back was drawn as the segment from the seam to the
        // half-way column (the *front* half, mirrored), and the wall's
        // ring lost its far side. The edge's own interior decides which
        // column a seam endpoint is: the image of a point a little way in
        // from that end lies on the same side of the chart.
        let at_seam = |u: &f64| (*u - nu0).abs() < span * 1e-6 || (*u - nu1).abs() < span * 1e-6;
        let inside = |t: f64| -> OgeomResult<f64> {
            let p = curve.point_at(t, tol)?;
            Ok(crate::measure::project_on_surface(surface, p, 24, tol)?
                .parameters
                .0)
        };
        let middle = f64::midpoint(nu0, nu1);
        let step = (range.1 - range.0) * 0.02;
        if at_seam(&a.x) {
            a.x = if inside(range.0 + step)? < middle {
                nu0
            } else {
                nu1
            };
        }
        if at_seam(&b.x) {
            b.x = if inside(range.1 - step)? < middle {
                nu0
            } else {
                nu1
            };
        }
        if (a.x - b.x).abs() < span * 1e-9 {
            // A closed row: the full width, oriented by the curve's start.
            a.x = nu0;
            b.x = nu1;
        }
    } else {
        let u = f64::midpoint(a.x, b.x);
        a.x = u;
        b.x = u;
        if (a.y - b.y).abs() < (nv1 - nv0) * 1e-9 {
            a.y = nv0;
            b.y = nv1;
        }
    }
    Ok(Some(ogeom_geom::Line2d::segment(a, b, tol)?.into()))
}

/// Exact seam pcurves for a closed patch: the chart's two edges the seam
/// runs along (its `u` columns or its `v` rows), each following the seam's
/// projected course at the edge's own parameters. `None` where the seam
/// does not lie on either pair of edges, or its course is not affine in
/// its parameter.
fn exact_seam_columns(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    tol: Tolerances,
) -> Option<(ogeom_geom::PlanarCurve, ogeom_geom::PlanarCurve)> {
    use ogeom_geom::Surface as _;
    let ((u0, u1), (v0, v1)) = surface.domain();
    const N: usize = 8;
    #[allow(clippy::cast_precision_loss)]
    let params: Vec<f64> = (0..=N)
        .map(|i| range.0 + (range.1 - range.0) * i as f64 / N as f64)
        .collect();
    let mut chart: Vec<Point2> = Vec::with_capacity(N + 1);
    for &t in &params {
        let p = curve.point_at(t, tol).ok()?;
        let at = crate::measure::project_on_surface(surface, p, 24, tol).ok()?;
        chart.push(Point2::new(at.parameters.0, at.parameters.1));
    }
    let on = |x: f64, a: f64, b: f64| {
        let eps = (b - a).abs() * 1e-6;
        (x - a).abs() <= eps || (x - b).abs() <= eps
    };
    // Which pair of chart edges the seam runs on, and the coordinate it
    // runs along.
    let (columns, lo, hi, period) = if chart.iter().all(|p| on(p.x, u0, u1)) {
        (true, u0, u1, surface.is_periodic_v().then_some(v1 - v0))
    } else if chart.iter().all(|p| on(p.y, v0, v1)) {
        (false, v0, v1, surface.is_periodic_u().then_some(u1 - u0))
    } else {
        return None;
    };
    let mut run: Vec<f64> = chart
        .iter()
        .map(|p| if columns { p.y } else { p.x })
        .collect();
    if let Some(period) = period {
        for i in 1..run.len() {
            while run[i] - run[i - 1] > period * 0.5 {
                run[i] -= period;
            }
            while run[i] - run[i - 1] < -period * 0.5 {
                run[i] += period;
            }
        }
    }
    let slope = (run[N] - run[0]) / (range.1 - range.0);
    let span = (run[N] - run[0]).abs();
    if span <= tol.parametric() {
        return None;
    }
    let affine = params
        .iter()
        .zip(&run)
        .all(|(t, r)| (run[0] + slope * (t - range.0) - r).abs() <= span * 1e-7);
    if !affine {
        return None;
    }
    let side = |at: f64| -> Option<ogeom_geom::PlanarCurve> {
        let (a, b) = if columns {
            (Point2::new(at, run[0]), Point2::new(at, run[N]))
        } else {
            (Point2::new(run[0], at), Point2::new(run[N], at))
        };
        let knots =
            ogeom_math::KnotVector::new(vec![range.0, range.0, range.1, range.1], 1).ok()?;
        Some(
            ogeom_geom::BSpline2d::new(knots, vec![a, b], tol)
                .ok()?
                .into(),
        )
    };
    Some((side(hi)?, side(lo)?))
}

/// The two seam-side pcurves of a closed patch: the chart's first and last
/// `u` columns, each fitted at the edge's own parameters.
fn seam_pcurves(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    target: f64,
    tol: Tolerances,
) -> OgeomResult<(ogeom_geom::PlanarCurve, ogeom_geom::PlanarCurve)> {
    let ((u0, u1), _) = surface.domain();
    let forward = fit_pcurve(curve, range, surface, Some(u1), (None, None), target, tol)?;
    let reversed = fit_pcurve(curve, range, surface, Some(u0), (None, None), target, tol)?;
    Ok((forward, reversed))
}

/// The pole row of a degenerate edge, restated in the new chart.
fn degenerate_row(
    model: &Model,
    data: &ogeom_topo::EdgeData,
    old_surface: ogeom_topo::SurfaceId,
    edge: &Shape,
    old: &SurfaceGeometry,
    new: &SurfaceGeometry,
    tol: Tolerances,
) -> OgeomResult<ogeom_geom::Line2d> {
    // Which end of the old chart the pole row sat at decides which end of
    // the new chart it sits at: conversion preserves ends.
    let Some(EdgeRepr::PCurve { curve, .. }) = data.pcurve_for(old_surface, edge.location()) else {
        ogeom_bail!(Construction, "a degenerate edge has no pcurve to restate");
    };
    let Some(row) = model.geometry().pcurve(*curve) else {
        ogeom_bail!(Dangling, "pcurve is not in this model");
    };
    let (lo, hi) = row.domain();
    let v_old = f64::midpoint(row.point_at(lo, tol)?.y, row.point_at(hi, tol)?.y);
    let (_, (va_old, vb_old)) = old.domain();
    let ((nu0, nu1), (nv0, nv1)) = new.domain();
    let v_new = if (v_old - va_old).abs() <= (v_old - vb_old).abs() {
        nv0
    } else {
        nv1
    };
    ogeom_geom::Line2d::segment(Point2::new(nu0, v_new), Point2::new(nu1, v_new), tol)
}

/// The surface shrunk to the face's own chart region, with a margin.
///
/// The face's pcurves say which part of the surface the face actually uses;
/// converting the whole declared domain would spend the patch's parameter
/// range on empty plane. Kinds whose windows are structural (a sphere's, a
/// torus's, the closed direction of a cylinder) keep them.
fn bounded_to_face(
    model: &Model,
    face: &Shape,
    surface_id: ogeom_topo::SurfaceId,
    placed: &SurfaceGeometry,
    stretch: f64,
    tol: Tolerances,
) -> OgeomResult<(SurfaceGeometry, ChartWindow)> {
    let (mut u0, mut u1) = (f64::INFINITY, f64::NEG_INFINITY);
    let (mut v0, mut v1) = (f64::INFINITY, f64::NEG_INFINITY);
    for edge in explore(model, face, Filter::OfType(ShapeType::Edge))? {
        let Some(data) = model.node(&edge).and_then(|n| n.data().as_edge()) else {
            continue;
        };
        let mut widen = |pc: ogeom_topo::PCurveId, range: (f64, f64)| -> OgeomResult<()> {
            let Some(pcurve) = model.geometry().pcurve(pc) else {
                return Ok(());
            };
            for i in 0..=8 {
                #[allow(clippy::cast_precision_loss)]
                let t = range.0 + (range.1 - range.0) * f64::from(i) / 8.0;
                let p = pcurve.point_at(t, tol)?;
                u0 = u0.min(p.x);
                u1 = u1.max(p.x);
                v0 = v0.min(p.y);
                v1 = v1.max(p.y);
            }
            Ok(())
        };
        match data.pcurve_for(surface_id, edge.location()) {
            Some(EdgeRepr::PCurve { curve, range, .. }) => widen(*curve, *range)?,
            Some(EdgeRepr::Seam {
                forward,
                reversed,
                range,
                ..
            }) => {
                widen(*forward, *range)?;
                widen(*reversed, *range)?;
            }
            _ => {}
        }
    }
    if !u0.is_finite() || u1 - u0 <= tol.confusion() || v1 - v0 <= tol.confusion() {
        return Ok((placed.clone(), placed.domain()));
    }
    // The window was read off the *old* pcurves, in the old chart's units;
    // a placement with scale stretches the placed chart's length-like
    // directions, and the trim must stretch with them. Angle directions
    // never stretch.
    let (su, sv) = match placed {
        SurfaceGeometry::Plane(_) => (stretch, stretch),
        SurfaceGeometry::Cylinder(_) | SurfaceGeometry::Cone(_) => (1.0, stretch),
        _ => (1.0, 1.0),
    };
    let (u0, u1, v0, v1) = (u0 * su, u1 * su, v0 * sv, v1 * sv);
    let margin = ((u1 - u0) + (v1 - v0)) * 0.05 + tol.confusion();
    let bounded: SurfaceGeometry = match placed {
        SurfaceGeometry::Plane(p) => ogeom_geom::PlaneSurface::over(
            p.plane(),
            (u0 - margin, u1 + margin),
            (v0 - margin, v1 + margin),
        )?
        .into(),
        SurfaceGeometry::Cylinder(c) => {
            ogeom_geom::CylinderSurface::new(c.cylinder(), (v0 - margin, v1 + margin))?.into()
        }
        SurfaceGeometry::Cone(c) => {
            ogeom_geom::ConeSurface::new(c.cone(), (v0 - margin, v1 + margin))?.into()
        }
        // An offset over a plane's or drum's unbounded chart has no
        // extent to fit or convert over; held to the face's window, it has.
        SurfaceGeometry::Offset(o) if !finite(o.basis().domain()) => {
            let ((du0, du1), (dv0, dv1)) = placed.domain();
            ogeom_geom::TrimmedSurface::new(
                placed.clone(),
                ((u0 - margin).max(du0), (u1 + margin).min(du1)),
                ((v0 - margin).max(dv0), (v1 + margin).min(dv1)),
                tol,
            )
            .map_or_else(
                |_| placed.clone(),
                |t| SurfaceGeometry::Trimmed(Box::new(t)),
            )
        }
        other => other.clone(),
    };
    let window = bounded.domain();
    Ok((bounded, window))
}

fn finite(domain: ChartWindow) -> bool {
    [domain.0.0, domain.0.1, domain.1.0, domain.1.1]
        .iter()
        .all(|x| x.is_finite() && x.abs() < 1e6)
}

/// A B-spline patch with its control points carried through an affine map.
fn transformed_patch(
    patch: &ogeom_geom::BSplineSurface,
    transform: &GeneralTransform,
) -> OgeomResult<ogeom_geom::BSplineSurface> {
    let grid = patch.grid();
    let mapped = grid.map(|c| {
        let p = Point::from_vector(c.scaled.to_vector() / c.weight);
        let moved = transform.apply(p);
        Weighted {
            scaled: Point::from_vector(moved.to_vector() * c.weight),
            weight: c.weight,
        }
    });
    ogeom_geom::BSplineSurface::rational(patch.u_knots().clone(), patch.v_knots().clone(), mapped)
}

/// A rigid placement quantized for deduplication keys.
fn placement_bits(t: &ogeom_math::Transform) -> [u64; 3] {
    let p = t.apply(Point::new(0.123_456_789, 9.87, -3.21));
    point_bits(p)
}

fn point_bits(p: Point) -> [u64; 3] {
    [p.x.to_bits(), p.y.to_bits(), p.z.to_bits()]
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;
    use crate::{make_box, make_cylinder, volume_properties};
    use ogeom_math::Frame;
    use ogeom_mesh::Deflection;

    const T: Tolerances = Tolerances::millimetres();

    fn fine() -> Deflection {
        Deflection {
            chord: 1e-3,
            ..Deflection::default()
        }
    }

    #[test]
    fn a_box_converts_to_nurbs_and_measures_the_same() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T).unwrap();
        let converted = to_nurbs(&mut model, &solid.shape, T).unwrap();

        // Every surface is now a spline.
        for face in explore(&model, &converted.shape, Filter::OfType(ShapeType::Face)).unwrap() {
            let NodeData::Face(data) = model.node(&face).unwrap().data() else {
                panic!("face data");
            };
            assert!(matches!(
                model.geometry().surface(data.surface),
                Some(SurfaceGeometry::BSpline(_))
            ));
        }
        let props = volume_properties(&model, &converted.shape, fine(), T).unwrap();
        assert!((props.mass - 24.0).abs() < 1e-6, "volume {}", props.mass);
        assert!(
            crate::check(&model, &converted.shape, T)
                .unwrap()
                .is_valid(),
            "{}",
            crate::check(&model, &converted.shape, T).unwrap()
        );
        assert_eq!(
            converted.history.modified(&solid.shape),
            std::slice::from_ref(&converted.shape)
        );
    }

    #[test]
    fn a_cylinder_converts_seams_poles_and_all() {
        let mut model = Model::new();
        let solid = make_cylinder(&mut model, Frame::WORLD, 2.0, 5.0, T).unwrap();
        let converted = to_nurbs(&mut model, &solid.shape, T).unwrap();
        let exact = core::f64::consts::PI * 4.0 * 5.0;
        let props = volume_properties(&model, &converted.shape, fine(), T).unwrap();
        assert!(
            (props.mass - exact).abs() < exact * 5e-3,
            "volume {} against {exact}",
            props.mass
        );
    }

    #[test]
    fn a_uniform_scale_is_a_placement_and_leaves_the_surfaces_analytic() {
        // The distinction this module is built on, stated as a test. A
        // similarity carries a plane to a plane, so the shape keeps saying
        // what it is; converting it would leave six patches that happen to be
        // flat, and nothing downstream that asks about coincidence can read
        // flatness out of a patch.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T).unwrap();
        let scale = GeneralTransform::new(
            ogeom_math::Matrix3 {
                rows: [[2.0, 0.0, 0.0], [0.0, 2.0, 0.0], [0.0, 0.0, 2.0]],
            },
            ogeom_math::Vector::ZERO,
        );

        let scaled = general_transformed_shape(&mut model, &solid.shape, &scale, T).unwrap();

        for face in explore(&model, &scaled.shape, Filter::OfType(ShapeType::Face)).unwrap() {
            let NodeData::Face(data) = model.node(&face).unwrap().data() else {
                panic!("face data");
            };
            assert!(
                matches!(
                    model.geometry().surface(data.surface),
                    Some(SurfaceGeometry::Plane(_))
                ),
                "a scaled box's face stopped being a plane"
            );
        }
        let props = volume_properties(&model, &scaled.shape, fine(), T).unwrap();
        assert!((props.mass - 192.0).abs() < 1e-6, "scaled {}", props.mass);
    }

    #[test]
    fn a_shear_preserves_volume_and_a_stretch_scales_it() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T).unwrap();

        // A unit-determinant shear: x' = x + 0.5 y.
        let shear = GeneralTransform::new(
            ogeom_math::Matrix3 {
                rows: [[1.0, 0.5, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]],
            },
            ogeom_math::Vector::ZERO,
        );
        let sheared = general_transformed_shape(&mut model, &solid.shape, &shear, T).unwrap();
        let props = volume_properties(&model, &sheared.shape, fine(), T).unwrap();
        assert!((props.mass - 24.0).abs() < 1e-6, "sheared {}", props.mass);

        // An uneven stretch doubles x: volume doubles.
        let stretch = GeneralTransform::new(
            ogeom_math::Matrix3 {
                rows: [[2.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]],
            },
            ogeom_math::Vector::ZERO,
        );
        let stretched = general_transformed_shape(&mut model, &solid.shape, &stretch, T).unwrap();
        let props = volume_properties(&model, &stretched.shape, fine(), T).unwrap();
        assert!((props.mass - 48.0).abs() < 1e-6, "stretched {}", props.mass);
    }

    #[test]
    fn a_sheared_cylinder_still_encloses_its_volume() {
        // The case placements cannot express: the circular rims become
        // ellipses, and the volume is invariant under the unit-det shear.
        let mut model = Model::new();
        let solid = make_cylinder(&mut model, Frame::WORLD, 2.0, 5.0, T).unwrap();
        let shear = GeneralTransform::new(
            ogeom_math::Matrix3 {
                rows: [[1.0, 0.0, 0.4], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]],
            },
            ogeom_math::Vector::ZERO,
        );
        let sheared = general_transformed_shape(&mut model, &solid.shape, &shear, T).unwrap();
        let exact = core::f64::consts::PI * 4.0 * 5.0;
        let props = volume_properties(&model, &sheared.shape, fine(), T).unwrap();
        assert!(
            (props.mass - exact).abs() < exact * 5e-3,
            "sheared cylinder {} against {exact}",
            props.mass
        );
    }
}