ogeom_algo/

convert.rs

//! Whole-shape conversion: everything as NURBS, and general affine
//! transforms over a shape.
//!
//! The geometry-level conversions are exact. 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.
//!
//! 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_compound, make_shell, make_solid, make_vertex, make_wire};
use ogeom_core::FastMap;
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,
};

/// 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, a shell, a face, or a compound of them, with every
/// surface and curve in B-spline form.
///
/// The result is a new shape of the same kind 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, edge occurrence and
/// container modified into its converted twin.
///
/// # Errors
///
/// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if the
/// shape is not a solid, a shell, a face or a compound of them, or a
/// conversion has no exact form (a trimmed
/// surface's basis is converted; nothing else refuses);
/// [`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 shape 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, a shell, a face, or a compound of them, with its
/// placements baked into the geometry, keeping every surface and curve in
/// its own analytic vocabulary.
///
/// History records each face, edge occurrence and container modified into
/// its twin: an edge node placed twice (a prism's two ends) has two twins,
/// one per placement, each read back through the placed occurrence.
///
/// 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)
}

/// The shape with its placements baked in where any is placed, as
/// [`baked_shape`] rebuilds it; the shape itself, with an empty history,
/// where no face, surface, edge occurrence or edge curve in it is placed.
///
/// What an operation that reads geometry in its own coordinates calls on
/// its input: a prism's far end edges are its profile's edges under the
/// prism's translation, and read through this they are edges in place.
/// [`History::trace`] on the result's history answers where any face or
/// edge occurrence of the input went.
///
/// # Errors
///
/// As [`baked_shape`].
pub fn baked_where_placed(model: &mut Model, shape: &Shape, tol: Tolerances) -> OgeomResult<Built> {
    let mut placed = !shape.location().is_identity();
    for face in explore(model, shape, Filter::OfType(ShapeType::Face))? {
        let Some(NodeData::Face(data)) = model.node(&face).map(|n| n.data()) else {
            ogeom_bail!(Dangling, "face is not in this model");
        };
        placed |= !face.location().is_identity() || !data.location.is_identity();
    }
    for edge in explore(model, shape, Filter::OfType(ShapeType::Edge))? {
        let Some(data) = model.node(&edge).and_then(|n| n.data().as_edge()) else {
            ogeom_bail!(Dangling, "edge is not in this model");
        };
        placed |= !edge.location().is_identity()
            || matches!(data.curve3d(), Some(EdgeRepr::Curve3d { location, .. }) if !location.is_identity());
    }
    if placed {
        baked_shape(model, shape, tol)
    } else {
        Ok(Built::new(shape.clone(), History::identity()))
    }
}

/// Rebuild a solid, a shell, a face, or a compound of them, 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.
///
/// The history records the shape and every container, face, wire, edge and
/// vertex below it as modified into its rebuilt twin, as
/// [`transformed`](crate::transformed) records each into its moved
/// occurrence, so `trace` answers for every sub-shape either way.
///
/// # 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 shape 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> {
    let mut state = Rebuild {
        affine,
        restate,
        tol,
        history: History::new(),
        new_vertices: NewVertices::default(),
        new_edges: FastMap::default(),
        rederived: Vec::new(),
    };
    let rebuilt = state.shape(model, shape)?;
    // A re-derived pcurve is held to its target where it was built, at
    // its samples; each such edge states how far its pcurves stand off
    // its curve anywhere along it.
    crate::pcurve_gap::state_pcurve_gaps_of(model, &state.rederived, tol)?;
    Ok(Built::new(rebuilt, state.history))
}

/// A rebuild under way: how it restates, and what it has made so far.
struct Rebuild<'a> {
    affine: Option<&'a GeneralTransform>,
    restate: Restate<'a>,
    tol: Tolerances,
    history: History,
    /// Each vertex occurrence's twin, by node and position.
    new_vertices: NewVertices,
    /// Each edge occurrence's twin, by node and placement.
    new_edges: FastMap<(TShapeId, [u64; 3]), ConvertedEdge>,
    /// The edges given a pcurve that is not a closed form of their curve
    /// on the new surface: an iso line or a fit.
    rederived: Vec<Shape>,
}

impl Rebuild<'_> {
    /// A solid, a shell, a face, or a compound of them, rebuilt: each
    /// container anew over its rebuilt children, which carry the
    /// container's orientation and placement down.
    fn shape(&mut self, model: &mut Model, shape: &Shape) -> OgeomResult<Shape> {
        let kind = model.kind_of(shape)?;
        let rebuilt = match kind {
            ShapeType::Face => return self.face(model, shape),
            ShapeType::Shell | ShapeType::Solid | ShapeType::Compound => {
                let mut children = Vec::new();
                for child in model.ordered_children_of(shape)? {
                    children.push(self.shape(model, &child)?);
                }
                match kind {
                    ShapeType::Shell => make_shell(model, &children)?.shape,
                    ShapeType::Solid => make_solid(model, &children)?.shape,
                    _ => make_compound(model, &children)?.shape,
                }
            }
            other => ogeom_bail!(
                Construction,
                "whole-shape conversion rebuilds solids, shells, faces and \
                 compounds of them; this is a {other:?}"
            ),
        };
        self.history.modify(shape, rebuilt.clone());
        Ok(rebuilt)
    }

    /// One face rebuilt on its restated surface, bounded by its restated
    /// edges, each with a pcurve re-derived on the new surface.
    #[expect(
        clippy::too_many_lines,
        reason = "one walk over a face's wires, restating each edge in place"
    )]
    fn face(&mut self, model: &mut Model, face: &Shape) -> OgeomResult<Shape> {
        let (affine, restate, tol) = (self.affine, self.restate, self.tol);
        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 face = face.clone();
        let history = &mut self.history;
        let new_vertices = &mut self.new_vertices;
        let new_edges = &mut self.new_edges;
        let rederived = &mut self.rederived;
        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;
        // Under an affine map the turn is measured on the spline before
        // the map moves it, where the old surface's normal still means
        // something, and the map's own reflection goes on top.
        let mut turned_before_affine = None;
        let patch_surface: SurfaceGeometry = match restate {
            Restate::Nurbs => {
                let mut patch = profile_held(&placed, old_window, tol).to_bspline(tol)?;
                if let Some(t) = affine {
                    let unmapped: SurfaceGeometry = patch.clone().into();
                    turned_before_affine =
                        turned_by_rebuild(&old_surface, &placement, old_window, &unmapped, tol)
                            .map(|turned| turned != (t.linear.determinant() < 0.0));
                    patch = transformed_patch(&patch, t)?;
                }
                patch.into()
            }
            Restate::Keep => on_right_handed_frame(&placed, tol)?.unwrap_or_else(|| 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());

        // 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.
        //
        // Whether a reflection turns a surface's natural normal depends
        // on the surface: a mirrored cylinder is stored about a
        // right-handed frame again and keeps its normal away from the
        // axis. So where it can be, the turn is measured: the old
        // normal carried through the placement against the new one at
        // the same point. Handedness is the fallback where the
        // measurement cannot be taken, and under an affine map, which
        // does not carry normals as vectors.
        let measured = if affine.is_none() {
            turned_by_rebuild(&old_surface, &placement, old_window, &patch_surface, tol)
        } else {
            turned_before_affine
        };
        let reflecting = !face.location().preserves_handedness(model.datums())?;
        let reflected = measured.unwrap_or(reflecting != flipped);
        // The rings keep the face on their left in the old chart. A spline
        // whose control points the affine map moved keeps that chart; any
        // other new chart runs the other way round where the placement
        // reflects and the normal did not turn with it, or the normal
        // turned under a placement that does not reflect, and the rings
        // are walked back to keep the face on their left in it.
        let walked_back = affine.is_none() && reflecting != reflected;

        let mut rings = Vec::new();
        let mut old_wires = Vec::new();
        let mut corner_uv: FastMap<TShapeId, Point2> = FastMap::default();
        // The wires are read as the face stores them, its own sense left
        // out: the rebuilt face takes that sense back below, and reading
        // them under it as well would turn every ring of a reversed face
        // around.
        for wire in model.ordered_children_of(&face.oriented(Orientation::Forward))? {
            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 reach = model
                        .node(&vertex)
                        .and_then(|n| n.data().as_vertex())
                        .map_or(0.0, |v| v.tolerance.get());
                    let new_vertex = new_vertices.at(model, vertex.node(), at, reach, tol);
                    let mut degenerate = ogeom_topo::EdgeData::new();
                    degenerate.degenerate = true;
                    let new_edge = model.add_edge(degenerate, &[new_vertex.clone(), new_vertex])?;
                    record(history, &edge, &new_edge);
                    record_vertices(model, &edge, &map, new_vertices, history, tol)?;
                    let row = degenerate_row(
                        model,
                        &data,
                        surface_id_old,
                        &edge,
                        &placed,
                        &patch_surface,
                        at,
                        walked_back,
                        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;
                }

                // An occurrence placed differently may still lie where
                // one already converted lies (a rotated copy of a profile
                // shares its edge on the axis of the turn), and is then
                // that edge.
                let found = match new_edges.get(&key) {
                    Some(found) => Some(found.clone()),
                    None => {
                        let at = occurrence_points(model, &edge, &data, &map, tol)?;
                        let same = new_edges
                            .iter()
                            .filter(|((node, _), _)| *node == edge.node())
                            .find(|(_, (_, curve, range))| lies_at(curve, *range, at, tol))
                            .map(|(_, found)| found.clone());
                        if let Some(same) = &same {
                            new_edges.insert(key, same.clone());
                        }
                        same
                    }
                };
                let (new_edge, new_curve, new_range) = match found {
                    Some(found) => found,
                    None => {
                        let built =
                            convert_edge(model, &edge, &data, &map, restate, new_vertices, tol)?;
                        new_edges.insert(key, built.clone());
                        built
                    }
                };
                record(history, &edge, &new_edge);
                record_vertices(model, &edge, &map, new_vertices, history, tol)?;

                // 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());
                        // Whether the old seam ran along a row or a column.
                        let old_iso = match &old_repr {
                            Some(EdgeRepr::Seam { forward, range, .. }) => {
                                match model.geometry().pcurve(*forward) {
                                    Some(side) => iso_direction(side, *range, tol)?,
                                    None => None,
                                }
                            }
                            _ => None,
                        };
                        let exact =
                            match exact_seam_columns(&new_curve, new_range, &patch_surface, tol) {
                                Some(sides) => Some(sides),
                                None => match old_iso {
                                    Some(row) => {
                                        seam_lines(&new_curve, new_range, &patch_surface, row, tol)?
                                    }
                                    None => None,
                                },
                            };
                        let (forward, reversed) = match exact {
                            Some(sides) => sides,
                            None => {
                                seam_pcurves(&new_curve, new_range, &patch_surface, target, tol)?
                            }
                        };
                        let seam_range = forward.domain();
                        rederived.push(new_edge.clone());
                        attach_seam(
                            model,
                            &new_edge,
                            forward,
                            reversed,
                            surface_id,
                            Location::identity(),
                            seam_range,
                        )?;
                    }
                } else {
                    // The iso path: an edge that ran along the old chart's
                    // iso direction runs along the new chart's. An exact
                    // conversion shares the boundary's parameterization by
                    // construction; a fitted surface has its own, and its
                    // iso line may stray from the edge, so the line is kept
                    // only where it follows the edge within the fit target.
                    let stated = model
                        .node(&new_edge)
                        .and_then(|n| n.data().as_edge())
                        .map_or(0.0, |d| d.tolerance.get());
                    let iso = exact_iso_pcurve(
                        model,
                        old_repr.as_ref(),
                        old_window,
                        &new_curve,
                        new_range,
                        &patch_surface,
                        (edge.orientation() == Orientation::Reversed) == walked_back,
                        tol,
                    )?;
                    let iso = match iso {
                        Some(iso)
                            if crate::pcurve_gap::pcurve_gap(
                                (&new_curve, new_range),
                                (&iso, iso.domain()),
                                &patch_surface,
                                stated,
                                tol,
                            )? <= target.max(stated) =>
                        {
                            Some(iso)
                        }
                        _ => None,
                    };
                    if let Some(iso) = iso {
                        let iso_range = iso.domain();
                        rederived.push(new_edge.clone());
                        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 FastMap<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)?;
                                }
                            }
                            rederived.push(new_edge.clone());
                            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
                });
            }
            rings.push(ring);
            old_wires.push(wire);
        }
        let mut wires = Vec::with_capacity(rings.len());
        for (ring, old) in rings.into_iter().zip(&old_wires) {
            let ring: Vec<Shape> = if walked_back {
                ring.iter().rev().map(Shape::reversed).collect()
            } else {
                ring
            };
            let wire = make_wire(model, &ring, tol)?.shape;
            record(history, old, &wire);
            wires.push(wire);
        }
        let built = make_face_on(model, surface_id, &wires, tol)?.shape;
        let built = if (face.orientation() == Orientation::Reversed) != reflected {
            built.reversed()
        } else {
            built
        };
        history.modify(&face, built.clone());
        Ok(built)
    }
}

/// An analytic surface placed by a reflection, restated on its frame's
/// right-handed twin (the same origin and axis, `y` reversed): the same
/// points, turning the other way. Downstream code reads a surface's frame
/// as right-handed, as every surface built from scratch has it; the face's
/// flag takes the turn, which the rebuild measures. A plane's `v` runs the
/// other way on the twin, and its window with it. `None` for a surface on
/// a right-handed frame, or of another kind.
fn on_right_handed_frame(
    surface: &SurfaceGeometry,
    tol: Tolerances,
) -> OgeomResult<Option<SurfaceGeometry>> {
    use ogeom_geom::{ConeSurface, CylinderSurface, PlaneSurface, SphereSurface, TorusSurface};
    use ogeom_math::{Cone, Cylinder, Frame, Handedness, Plane, Sphere, Torus};
    let twin = |frame: Frame| -> OgeomResult<Option<Frame>> {
        if frame.handedness() == Handedness::Right {
            return Ok(None);
        }
        Ok(Some(Frame::new(frame.origin(), frame.z(), frame.x(), tol)?))
    };
    let ((u0, u1), (v0, v1)) = surface.domain();
    Ok(match surface {
        SurfaceGeometry::Plane(p) => match twin(p.plane().frame())? {
            Some(f) => Some(PlaneSurface::over(Plane::new(f), (u0, u1), (-v1, -v0))?.into()),
            None => None,
        },
        SurfaceGeometry::Cylinder(c) => {
            let cylinder = c.cylinder();
            match twin(cylinder.frame())? {
                Some(f) => Some(
                    CylinderSurface::new(Cylinder::new(f, cylinder.radius(), tol)?, (v0, v1))?
                        .into(),
                ),
                None => None,
            }
        }
        SurfaceGeometry::Cone(c) => {
            let cone = c.cone();
            match twin(cone.frame())? {
                Some(f) => Some(
                    ConeSurface::new(
                        Cone::new(f, cone.reference_radius(), cone.half_angle(), tol)?,
                        (v0, v1),
                    )?
                    .into(),
                ),
                None => None,
            }
        }
        SurfaceGeometry::Sphere(s) => {
            let sphere = s.sphere();
            match twin(sphere.frame())? {
                Some(f) => Some(SphereSurface::new(Sphere::new(f, sphere.radius(), tol)?).into()),
                None => None,
            }
        }
        SurfaceGeometry::Torus(t) => {
            let torus = t.torus();
            match twin(torus.frame())? {
                Some(f) => Some(
                    TorusSurface::new(Torus::new(
                        f,
                        torus.major_radius(),
                        torus.minor_radius(),
                        tol,
                    )?)
                    .into(),
                ),
                None => None,
            }
        }
        _ => None,
    })
}

/// An edge occurrence's start, middle and end, placed and mapped.
fn occurrence_points(
    model: &Model,
    edge: &Shape,
    data: &ogeom_topo::EdgeData,
    map: &dyn Fn(Point) -> Point,
    tol: Tolerances,
) -> OgeomResult<Option<[Point; 3]>> {
    let Some(EdgeRepr::Curve3d {
        curve,
        range,
        location,
    }) = data.curve3d()
    else {
        return Ok(None);
    };
    let Some(geometry) = model.geometry().curve(*curve) else {
        return Ok(None);
    };
    let placement = edge.transform(model.datums())? * location.composed(model.datums())?;
    let mut out = [Point::ORIGIN; 3];
    for (slot, t) in out
        .iter_mut()
        .zip([range.0, f64::midpoint(range.0, range.1), range.1])
    {
        *slot = map(placement.apply(geometry.point_at(t, tol)?));
    }
    Ok(Some(out))
}

/// Whether a converted curve over `range` runs through `at`'s start,
/// middle and end.
fn lies_at(curve: &Curve, range: (f64, f64), at: Option<[Point; 3]>, tol: Tolerances) -> bool {
    let Some([a, m, b]) = at else {
        return false;
    };
    let near = |t: f64, p: Point| {
        curve
            .point_at(t, tol)
            .is_ok_and(|q| q.distance(p) <= tol.confusion() * 1e2)
    };
    near(range.0, a) && near(f64::midpoint(range.0, range.1), m) && near(range.1, b)
}

/// 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 NewVertices,
    tol: Tolerances,
) -> OgeomResult<(Shape, Curve, (f64, f64))> {
    let Some(EdgeRepr::Curve3d {
        curve,
        range,
        location,
    }) = 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())? * location.composed(model.datums())?;
    use ogeom_geom::Transformable as _;
    let placed = geometry.transformed(&placement, tol)?;
    // A placement with scale rescales a length-parameterized curve's domain
    // (a line's, a parabola's, anything built on one), so the edge's range
    // moves with the domain or the conversion covers only part of the edge.
    let (from, to) = (geometry.domain(), placed.domain());
    let range_on_placed = (
        ogeom_geom::carried(range.0, from, to),
        ogeom_geom::carried(range.1, from, to),
    );
    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 point 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.at(model, occurrence.node(), at, data.tolerance.get(), tol);
        // 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() {
        model.widen(&built, data.tolerance)?;
    }
    Ok((built, curve, new_range))
}

/// A pcurve refit at the edge's own parameters, optionally biased toward one
/// side of the chart's seam (`side`: whether the seam is a `u` column, and
/// the column or row): sampled more densely until its image lies
/// within `target` of the edge halfway between the samples too, which a fit
/// held only at them need not.
#[allow(clippy::too_many_arguments)]
fn fit_pcurve(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    side: Option<(bool, f64)>,
    ends: (Option<Point2>, Option<Point2>),
    target: f64,
    tol: Tolerances,
) -> OgeomResult<ogeom_geom::PlanarCurve> {
    use ogeom_geom::Curve2d as _;
    let mut samples = 48;
    loop {
        let fitted = fit_pcurve_at(curve, range, surface, side, ends, target, samples, tol)?;
        if samples >= 384 {
            return Ok(fitted);
        }
        let mut held = true;
        for i in 0..samples {
            #[allow(clippy::cast_precision_loss)]
            let t = range.0 + (range.1 - range.0) * (i as f64 + 0.5) / samples as f64;
            let at = fitted.point_at(t, tol)?;
            // Where the fit overhangs the chart at a closure there is no
            // surface to lift it to; its samples there hold it.
            let Ok(lifted) = surface.point_at(at.x, at.y, tol) else {
                continue;
            };
            if lifted.distance(curve.point_at(t, tol)?) > target {
                held = false;
                break;
            }
        }
        if held {
            return Ok(fitted);
        }
        samples *= 2;
    }
}

/// [`fit_pcurve`] through `samples` spans of the edge.
#[allow(clippy::too_many_arguments)]
fn fit_pcurve_at(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    side: Option<(bool, f64)>,
    ends: (Option<Point2>, Option<Point2>),
    target: f64,
    samples: usize,
    tol: Tolerances,
) -> OgeomResult<ogeom_geom::PlanarCurve> {
    let ((u0, u1), (v0, v1)) = 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, mut v) = projection.parameters;
        // A point exactly on the seam projects to either side; the bias
        // names which column, or row, this pcurve is.
        match side {
            Some((true, bias))
                if (u - u0).abs() < (u1 - u0) * 0.25 || (u - u1).abs() < (u1 - u0) * 0.25 =>
            {
                u = bias;
            }
            Some((false, bias))
                if (v - v0).abs() < (v1 - v0) * 0.25 || (v - v1).abs() < (v1 - v0) * 0.25 =>
            {
                v = bias;
            }
            _ => {}
        }
        parameters.push(t);
        trace.push(Point2::new(u, v));
    }
    // A sample on a pole images to every column there, and the projection
    // answers with any of them; the trace reaches the pole along the column
    // of the sample beside it, which is where it stands in the chart. A
    // pole is where the chart's whole width of columns spans no more than
    // the confusion distance: the rate across columns times the width.
    let on_pole: Vec<bool> = trace
        .iter()
        .map(|p| {
            surface
                .d1_at(p.x, p.y, tol)
                .is_ok_and(|(du, _)| du.magnitude() * (u1 - u0).abs() <= tol.confusion())
        })
        .collect();
    if on_pole.iter().any(|&p| p) && !on_pole.iter().all(|&p| p) {
        for i in 0..trace.len() {
            if !on_pole[i] {
                continue;
            }
            let beside = (1..trace.len())
                .flat_map(|k| [i.checked_sub(k), (i + k < trace.len()).then_some(i + k)])
                .flatten()
                .find(|&j| !on_pole[j]);
            if let Some(j) = beside {
                trace[i].x = trace[j].x;
            }
        }
    }
    // 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. A vertex on the
    // closure has an image on either side of it, and the one projected for
    // the ring need not be the side this edge arrives at: it is taken the
    // whole periods round that put it where the unwrapped trace stands.
    let beside = |corner: Point2, at: Point2| -> Point2 {
        if !span.is_finite() || span <= 0.0 {
            return corner;
        }
        let turns = ((at.x - corner.x) / span).round();
        Point2::new(turns.mul_add(span, corner.x), corner.y)
    };
    // A corner on a pole names its row only: the column stays the one the
    // trace arrives along.
    let at_pole = |k: usize| on_pole.get(k).copied().unwrap_or(false);
    let last_index = trace.len().saturating_sub(1);
    if let Some(start) = ends.0
        && let Some(first) = trace.first_mut()
    {
        *first = if at_pole(0) {
            Point2::new(first.x, start.y)
        } else {
            beside(start, *first)
        };
    }
    if let Some(end) = ends.1
        && let Some(last) = trace.last_mut()
    {
        *last = if at_pole(last_index) {
            Point2::new(last.x, end.y)
        } else {
            beside(end, *last)
        };
    }
    // The target holds in space, where the edge is compared with its
    // pcurve's image; the chart stretches a step in `u` or `v` by up to its
    // largest partial along the trace, so the fit answers to that in the
    // chart, with half again for the stretch between samples.
    let mut stretch: f64 = 1.0;
    for p in &trace {
        let (du, dv) = surface.d1_at(p.x, p.y, tol)?;
        stretch = stretch.max(du.magnitude()).max(dv.magnitude());
    }
    let fitted =
        ogeom_geom::fit::fit_points_2d_at(&parameters, &trace, 3, target / (2.0 * stretch), 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. `along` says
/// whether the face's ring, which keeps the face on its left in the new
/// chart, runs the edge the way its curve does.
#[allow(clippy::too_many_arguments)]
fn exact_iso_pcurve(
    model: &Model,
    old_repr: Option<&EdgeRepr>,
    _old_window: ChartWindow,
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    along: bool,
    tol: Tolerances,
) -> OgeomResult<Option<ogeom_geom::PlanarCurve>> {
    let Some(EdgeRepr::PCurve {
        curve: old_pc,
        range: old_range,
        ..
    }) = old_repr
    else {
        return Ok(None);
    };
    let Some(old_pcurve) = model.geometry().pcurve(*old_pc) else {
        return Ok(None);
    };
    // An iso line however it is stated: a line, or a spline (a divided
    // face's cut is a linear one), whose points all share one coordinate.
    let Some(row) = iso_direction(old_pcurve, *old_range, tol)? else {
        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 mut a = foot(surface, start, tol)?;
    let mut b = foot(surface, end, tol)?;
    let closed_u = surface.is_periodic_u() || surface.is_closed_u(tol);
    let closed_v = surface.is_periodic_v() || surface.is_closed_v(tol);
    // The image of the edge's point at `t`.
    let inside = |t: f64| -> OgeomResult<Point2> { foot(surface, curve.point_at(t, tol)?, tol) };
    if row {
        // A row's v is one value; the endpoints agree up to projection noise.
        let mut v = f64::midpoint(a.y, b.y);
        (a.x, b.x) = run_ends(
            (a.x, b.x),
            (nu0, nu1),
            closed_u,
            range,
            |t| Ok(inside(t)?.x),
        )?;
        // A row the ring runs along the chart has the face above it in `v`.
        if let Some(side) = beside_face(&[a.y, b.y], (nv0, nv1), closed_v, (b.x > a.x) == along) {
            v = side;
        }
        a.y = v;
        b.y = v;
    } else {
        // A column's end on a pole images to every u there, and the
        // projection answers with any of them; the edge's middle images
        // to its own column. Of the three, the median is the column
        // whichever end, if either, stands on a pole.
        let m = inside(f64::midpoint(range.0, range.1))?.x;
        let mut u = a.x.max(b.x).min(m).max(a.x.min(b.x));
        (a.y, b.y) = run_ends(
            (a.y, b.y),
            (nv0, nv1),
            closed_v,
            range,
            |t| Ok(inside(t)?.y),
        )?;
        // A column the ring runs up the chart has the face below it in `u`.
        if let Some(side) = beside_face(&[u], (nu0, nu1), closed_u, (b.y > a.y) != along) {
            u = side;
        }
        a.x = u;
        b.x = u;
    }
    Ok(Some(ogeom_geom::Line2d::segment(a, b, tol)?.into()))
}

/// Where `p` stands in `surface`'s chart: its projection, polished by
/// Newton steps on the foot conditions until a step moves the parameters
/// less than the parametric tolerance. The projection stops once the gap
/// along the surface is under the confusion distance, which on a surface
/// curving tightly (a thin tube) is a sizeable part of the chart; an iso
/// line placed there stands that far off the line it images.
fn foot(surface: &SurfaceGeometry, p: Point, tol: Tolerances) -> OgeomResult<Point2> {
    use ogeom_geom::Surface as _;
    let (mut u, mut v) = crate::measure::project_on_surface(surface, p, 24, tol)?.parameters;
    for _ in 0..8 {
        let Ok(jet) = surface.jet_at(u, v, tol) else {
            break;
        };
        let gap = jet.point - p;
        let r = [gap.dot(jet.du), gap.dot(jet.dv)];
        let j = [
            [
                jet.du.dot(jet.du) + gap.dot(jet.d2u),
                jet.du.dot(jet.dv) + gap.dot(jet.duv),
            ],
            [
                jet.du.dot(jet.dv) + gap.dot(jet.duv),
                jet.dv.dot(jet.dv) + gap.dot(jet.d2v),
            ],
        ];
        let det = j[0][0] * j[1][1] - j[0][1] * j[1][0];
        // Singular on a pole, where the column is free and the row is the
        // projection's.
        if !det.is_finite() || det.abs() <= f64::EPSILON * j[0][0].abs() * j[1][1].abs() {
            break;
        }
        let (du, dv) = (
            (r[0] * j[1][1] - r[1] * j[0][1]) / det,
            (r[1] * j[0][0] - r[0] * j[1][0]) / det,
        );
        let (nu, nv) = (u - du, v - dv);
        let closer = surface
            .point_at(nu, nv, tol)
            .is_ok_and(|q| q.distance(p) <= jet.point.distance(p));
        if !closer {
            break;
        }
        (u, v) = (nu, nv);
        if du.hypot(dv) <= tol.parametric() {
            break;
        }
    }
    Ok(Point2::new(u, v))
}

/// Whether `pcurve` over `range` is a row (`Some(true)`: every point at one
/// `v`) or a column (`Some(false)`: at one `u`), read at evenly spaced
/// points; `None` where it is neither, or does not move.
fn iso_direction(
    pcurve: &ogeom_geom::PlanarCurve,
    range: (f64, f64),
    tol: Tolerances,
) -> OgeomResult<Option<bool>> {
    const SAMPLES: u32 = 8;
    let mut points = Vec::with_capacity(SAMPLES as usize + 1);
    for i in 0..=SAMPLES {
        let t = range.0 + (range.1 - range.0) * f64::from(i) / f64::from(SAMPLES);
        points.push(pcurve.point_at(t, tol)?);
    }
    let first = points[0];
    let spread = |coordinate: fn(Point2) -> f64| {
        points
            .iter()
            .map(|p| (coordinate(*p) - coordinate(first)).abs())
            .fold(0.0, f64::max)
    };
    let (across_u, across_v) = (spread(|p| p.x), spread(|p| p.y));
    let still = tol.parametric();
    Ok(match (across_u <= still, across_v <= still) {
        (false, true) => Some(true),
        (true, false) => Some(false),
        _ => None,
    })
}

/// The ends of an iso line in the coordinate it runs along, `ends` as its
/// end points project onto a chart spanning `(lo, hi)` that way; `at`
/// answers that coordinate for the edge's point at a parameter in `range`.
///
/// On the closure of a closed chart both chart edges image the same point,
/// and the projection answers with either: taken wrong, a half circle from
/// the seam round the back becomes the segment from the seam to the
/// half-way line (the *front* half, mirrored), and the face's ring loses
/// its far side. The edge's own interior decides which edge a closure end
/// is: the image of a point a little way in from that end lies on the same
/// side of the chart. A line whose ends meet is closed and runs the full
/// width, oriented by the curve's start.
fn run_ends(
    ends: (f64, f64),
    (lo, hi): (f64, f64),
    closed: bool,
    range: (f64, f64),
    at: impl Fn(f64) -> OgeomResult<f64>,
) -> OgeomResult<(f64, f64)> {
    let (mut from, mut to) = ends;
    let span = hi - lo;
    let on_closure = |x: f64| (x - lo).abs() < span * 1e-6 || (x - hi).abs() < span * 1e-6;
    let middle = f64::midpoint(lo, hi);
    let step = (range.1 - range.0) * 0.02;
    if closed && on_closure(from) {
        from = if at(range.0 + step)? < middle { lo } else { hi };
    }
    if closed && on_closure(to) {
        to = if at(range.1 - step)? < middle { lo } else { hi };
    }
    if (from - to).abs() < span * 1e-9 {
        (from, to) = (lo, hi);
    }
    Ok((from, to))
}

/// The chart edge an iso line on the closure of a closed chart stands on,
/// or `None` where `at`, the line's fixed coordinate as its points project,
/// is not on the closure or the chart does not close across the line.
///
/// On the closure both of the chart's edges image the line, and its own
/// points, all on the closure, cannot tell which. The face can: the ring
/// keeps it on its left, so the line stands on the chart's first edge
/// across it where the face lies above it (`face_above`) and on the last
/// where the face lies below.
fn beside_face(at: &[f64], (lo, hi): (f64, f64), closed: bool, face_above: bool) -> Option<f64> {
    let span = hi - lo;
    let on_closure = |x: &f64| (x - lo).abs() < span * 1e-6 || (x - hi).abs() < span * 1e-6;
    (closed && at.iter().any(on_closure)).then_some(if face_above { lo } else { hi })
}

/// 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. A closed run's samples near its far end project to either
    // copy of the closure, so a closed direction unwraps like a periodic one.
    let (columns, lo, hi, period) = if chart.iter().all(|p| on(p.x, u0, u1)) {
        let closed = surface.is_periodic_v() || surface.is_closed_v(tol);
        (true, u0, u1, closed.then_some(v1 - v0))
    } else if chart.iter().all(|p| on(p.y, v0, v1)) {
        let closed = surface.is_periodic_u() || surface.is_closed_u(tol);
        (false, v0, v1, closed.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;
            }
        }
        // A seam running against the chart's direction unwraps below the
        // window from its start; the chart's own copy lies a period up.
        let (w0, w1) = if columns { (v0, v1) } else { (u0, u1) };
        let eps = period * 1e-9;
        let low = run.iter().copied().fold(f64::INFINITY, f64::min);
        let high = run.iter().copied().fold(f64::NEG_INFINITY, f64::max);
        let shift = if low < w0 - eps {
            ((w0 - eps - low) / period).ceil() * period
        } else if high > w1 + eps {
            -((high - w1 - eps) / period).ceil() * period
        } else {
            0.0
        };
        for r in &mut run {
            *r += shift;
        }
    }
    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 sides of a seam that runs along an iso line of the new chart, a
/// row (`row`) or a column: the chart's last and first line that way, each
/// straight between where the edge's ends stand along it. The line is the
/// seam's own image, so the sides are exact whatever pace the edge's curve
/// keeps along it. `None` where the ends do not stand apart along it, or
/// the chart does not close across it.
fn seam_lines(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    row: bool,
    tol: Tolerances,
) -> OgeomResult<Option<(ogeom_geom::PlanarCurve, ogeom_geom::PlanarCurve)>> {
    use ogeom_geom::Surface as _;
    let ((u0, u1), (v0, v1)) = surface.domain();
    let (across, along, closes_across, closes_along) = if row {
        (
            (v0, v1),
            (u0, u1),
            surface.is_periodic_v() || surface.is_closed_v(tol),
            surface.is_periodic_u() || surface.is_closed_u(tol),
        )
    } else {
        (
            (u0, u1),
            (v0, v1),
            surface.is_periodic_u() || surface.is_closed_u(tol),
            surface.is_periodic_v() || surface.is_closed_v(tol),
        )
    };
    if !closes_across {
        return Ok(None);
    }
    // The seam stands on the closure across it, as `exact_seam_columns`
    // reads a seam's samples; a chart whose closure lies elsewhere (a
    // surface restated about a turned frame) has its seam fitted.
    let middle = foot(
        surface,
        curve.point_at(f64::midpoint(range.0, range.1), tol)?,
        tol,
    )?;
    let fixed = if row { middle.y } else { middle.x };
    let reach = (across.1 - across.0).abs() * 1e-6;
    if (fixed - across.0).abs() > reach && (fixed - across.1).abs() > reach {
        return Ok(None);
    }
    let free = |t: f64| -> OgeomResult<f64> {
        let at = foot(surface, curve.point_at(t, tol)?, tol)?;
        Ok(if row { at.x } else { at.y })
    };
    let (a, b) = run_ends(
        (free(range.0)?, free(range.1)?),
        along,
        closes_along,
        range,
        free,
    )?;
    if (b - a).abs() <= tol.parametric() {
        return Ok(None);
    }
    let side = |at: f64| -> OgeomResult<ogeom_geom::PlanarCurve> {
        let (from, to) = if row {
            (Point2::new(a, at), Point2::new(b, at))
        } else {
            (Point2::new(at, a), Point2::new(at, b))
        };
        let knots = ogeom_math::KnotVector::new(vec![range.0, range.0, range.1, range.1], 1)?;
        Ok(ogeom_geom::BSpline2d::new(knots, vec![from, to], tol)?.into())
    };
    Ok(Some((side(across.1)?, side(across.0)?)))
}

/// The two seam-side pcurves of a closed patch: the chart's first and last
/// `u` columns, or its first and last `v` rows where the seam runs along
/// the closure in `v` (a torus's tube seam), each fitted at the edge's own
/// parameters. Which closure the seam runs on is read at its middle, where
/// it stands on one of them and on no pole.
fn seam_pcurves(
    curve: &Curve,
    range: (f64, f64),
    surface: &SurfaceGeometry,
    target: f64,
    tol: Tolerances,
) -> OgeomResult<(ogeom_geom::PlanarCurve, ogeom_geom::PlanarCurve)> {
    use ogeom_geom::Surface as _;
    let ((u0, u1), (v0, v1)) = surface.domain();
    let middle = curve.point_at(f64::midpoint(range.0, range.1), tol)?;
    let (u, v) = crate::measure::project_on_surface(surface, middle, 24, tol)?.parameters;
    let off = |x: f64, a: f64, b: f64| (x - a).abs().min((x - b).abs()) / (b - a).abs();
    let on_rows =
        (surface.is_periodic_v() || surface.is_closed_v(tol)) && off(v, v0, v1) < off(u, u0, u1);
    let (column, lo, hi) = if on_rows {
        (false, v0, v1)
    } else {
        (true, u0, u1)
    };
    let forward = fit_pcurve(
        curve,
        range,
        surface,
        Some((column, hi)),
        (None, None),
        target,
        tol,
    )?;
    let reversed = fit_pcurve(
        curve,
        range,
        surface,
        Some((column, lo)),
        (None, None),
        target,
        tol,
    )?;
    Ok((forward, reversed))
}

/// The pole row of a degenerate edge, restated in the new chart; `pole` is
/// its vertex where the new surface holds it. The row runs with the new
/// chart's `u` as the old one's does, or against it where the face's
/// rings are walked back.
#[expect(
    clippy::too_many_arguments,
    reason = "the old and new charts of one edge"
)]
fn degenerate_row(
    model: &Model,
    data: &ogeom_topo::EdgeData,
    old_surface: ogeom_topo::SurfaceId,
    edge: &Shape,
    old: &SurfaceGeometry,
    new: &SurfaceGeometry,
    pole: Point,
    walked_back: bool,
    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,
        range: row_range,
        ..
    }) = data.pcurve_for(old_surface, edge.location())
    else {
        ogeom_bail!(Construction, "a degenerate edge has no pcurve to restate");
    };
    let row_range = *row_range;
    let Some(row) = model.geometry().pcurve(*curve) else {
        ogeom_bail!(Dangling, "pcurve is not in this model");
    };
    let (lo, hi) = row.domain();
    let at = row.point_at(f64::midpoint(lo, hi), tol)?;
    let v_old = at.y;
    let ((ua_old, ub_old), (va_old, vb_old)) = old.domain();
    let ((nu0, nu1), (nv0, nv1)) = new.domain();
    // The row where the new surface reaches the pole: a profile running
    // past its pole (a whole circle revolved) puts the pole inside the
    // chart, not at an end. Where the rows never reach it, conversion
    // preserves ends, and the old row's nearer end is the new one's.
    let v_new =
        pole_row(new, pole, tol).unwrap_or(if (v_old - va_old).abs() <= (v_old - vb_old).abs() {
            nv0
        } else {
            nv1
        });
    // A pole row spanning only part of the old chart's width (a face cut
    // from a ball) spans the columns its ends stand on: each read off the
    // old surface's middle row, away from the pole where every column
    // meets, and imaged onto the new surface, an end on the chart's
    // closure placed by a point a little way in, as an iso line's ends are.
    let (row_u0, row_u1) = (
        row.point_at(row_range.0, tol)?.x,
        row.point_at(row_range.1, tol)?.x,
    );
    let partial = (row_u1 - row_u0).abs() < (ub_old - ua_old).abs() - tol.parametric();
    let middle = f64::midpoint(va_old, vb_old);
    if partial && middle.is_finite() {
        let column = |t: f64| -> OgeomResult<f64> {
            let u = row.point_at(t, tol)?.x;
            let p = old.point_at(u, middle, tol)?;
            Ok(foot(new, p, tol)?.x)
        };
        let closed_u = new.is_periodic_u() || new.is_closed_u(tol);
        let (a, b) = run_ends(
            (column(row_range.0)?, column(row_range.1)?),
            (nu0, nu1),
            closed_u,
            row_range,
            column,
        )?;
        return ogeom_geom::Line2d::segment(Point2::new(a, v_new), Point2::new(b, v_new), tol);
    }
    let (from, to) = (Point2::new(nu0, v_new), Point2::new(nu1, v_new));
    if walked_back {
        ogeom_geom::Line2d::segment(to, from, tol)
    } else {
        ogeom_geom::Line2d::segment(from, to, tol)
    }
}

/// The `v` at which a surface's middle column reaches `pole`, to the
/// confusion distance, or `None` where it does not come that close: the
/// column sampled, the nearest sample narrowed by golden sections.
fn pole_row(surface: &SurfaceGeometry, pole: Point, tol: Tolerances) -> Option<f64> {
    const SAMPLES: u32 = 256;
    let ((u0, u1), (v0, v1)) = surface.domain();
    let u = f64::midpoint(u0, u1);
    let gap = |v: f64| {
        surface
            .point_at(u, v, tol)
            .map_or(f64::INFINITY, |p| p.distance(pole))
    };
    let at = |k: u32| v0 + (v1 - v0) * f64::from(k) / f64::from(SAMPLES);
    let best = (0..=SAMPLES).min_by(|&a, &b| gap(at(a)).total_cmp(&gap(at(b))))?;
    let (mut lo, mut hi) = (at(best.saturating_sub(1)), at((best + 1).min(SAMPLES)));
    let golden = (5.0_f64.sqrt() - 1.0) / 2.0;
    for _ in 0..80 {
        let (a, b) = (hi - golden * (hi - lo), lo + golden * (hi - lo));
        if gap(a) <= gap(b) {
            hi = b;
        } else {
            lo = a;
        }
    }
    let v = f64::midpoint(lo, hi);
    (gap(v) <= tol.confusion()).then_some(v)
}

/// Whether a face's new surface has its natural normal against the old
/// surface's carried through the placement, read in the middle of the
/// face's own chart window; `None` where the surfaces cannot be read there.
fn turned_by_rebuild(
    old: &SurfaceGeometry,
    placement: &ogeom_math::Transform,
    window: ChartWindow,
    new: &SurfaceGeometry,
    tol: Tolerances,
) -> Option<bool> {
    let ((u0, u1), (v0, v1)) = window;
    if !(u0.is_finite() && u1.is_finite() && v0.is_finite() && v1.is_finite()) {
        return None;
    }
    // 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 at = placement.apply(old.point_at(u, v, tol).ok()?);
    let was = placement.apply_vector(old.normal_at(u, v, tol).ok()?.vector());
    let foot = crate::measure::project_on_surface(new, at, 16, tol).ok()?;
    let (nu, nv) = foot.parameters;
    let now = new.normal_at(nu, nv, tol).ok()?.vector();
    Some(was.dot(now) < 0.0)
}

/// A revolution's profile held to the rows the face uses, exactly, for
/// converting: a profile running on past a pole (a whole circle turned)
/// would put the pole inside the converted chart, where no row of it is an
/// end. The turn stays whole. Any other surface is itself.
fn profile_held(
    surface: &SurfaceGeometry,
    window: ChartWindow,
    tol: Tolerances,
) -> SurfaceGeometry {
    let SurfaceGeometry::Revolution(_) = surface else {
        return surface.clone();
    };
    let ((du0, du1), (dv0, dv1)) = surface.domain();
    let (_, (v0, v1)) = window;
    if !(v0.is_finite() && v1.is_finite()) || v1 - v0 <= tol.parametric() {
        return surface.clone();
    }
    ogeom_geom::TrimmedSurface::new(surface.clone(), (du0, du1), (v0.max(dv0), v1.min(dv1)), tol)
        .map_or_else(
            |_| surface.clone(),
            |t| SurfaceGeometry::Trimmed(Box::new(t)),
        )
}

/// 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) => {
            // The margin stops at the apex: past it lies the other nappe,
            // which the face never reaches and a patch over it would take in.
            let cone = c.cone();
            let slope = cone.half_angle().tan();
            let (mut low, mut high) = (v0 - margin, v1 + margin);
            if slope.abs() > tol.angular() {
                let apex = -cone.reference_radius() / slope;
                if v0 >= apex - tol.confusion() {
                    low = low.max(apex);
                }
                if v1 <= apex + tol.confusion() {
                    high = high.min(apex);
                }
            }
            ogeom_geom::ConeSurface::new(cone, (low, high))?.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)),
            )
        }
        // A revolution keeps its whole surface for the restatements that
        // recognise it, and reports the rows the face uses, which is what
        // its conversion is held to.
        SurfaceGeometry::Revolution(_) => {
            let ((du0, du1), _) = placed.domain();
            return Ok((placed.clone(), ((du0, du1), (v0, v1))));
        }
        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)
}

/// The rebuilt vertices, by the old vertex node they stand for.
///
/// One old vertex placed at two points that coincide within its tolerance
/// (a profile's end on the axis of a turn, under the profile's placement
/// and under the turn's) is one new vertex, so every edge that meets it
/// there ends on the same node.
#[derive(Default)]
struct NewVertices(FastMap<TShapeId, Vec<(Point, Shape)>>);

impl NewVertices {
    /// The new vertex for the old `node` placed at `at`, made on first ask.
    fn at(
        &mut self,
        model: &mut Model,
        node: TShapeId,
        at: Point,
        reach: f64,
        tol: Tolerances,
    ) -> Shape {
        if let Some(found) = self.find(node, at, reach, tol) {
            return found;
        }
        let fresh = make_vertex(model, at).shape;
        self.0.entry(node).or_default().push((at, fresh.clone()));
        fresh
    }

    /// The new vertex already made for the old `node` placed at `at`.
    fn find(&self, node: TShapeId, at: Point, reach: f64, tol: Tolerances) -> Option<Shape> {
        let reach = reach.max(tol.confusion());
        self.0
            .get(&node)?
            .iter()
            .find(|(p, _)| p.distance(at) <= reach)
            .map(|(_, found)| found.clone())
    }
}

/// Record `input` as modified into `image`, once: a sub-shape reached along
/// several paths in the walk has one image, not one per path.
fn record(history: &mut History, input: &Shape, image: &Shape) {
    if !history.modified(input).iter().any(|s| s.is_same(image)) {
        history.modify(input, image.clone());
    }
}

/// Record each vertex occurrence bounding the old `edge` as modified into
/// the new vertex made for it.
fn record_vertices(
    model: &Model,
    edge: &Shape,
    map: &dyn Fn(Point) -> Point,
    vertices: &NewVertices,
    history: &mut History,
    tol: Tolerances,
) -> OgeomResult<()> {
    for vertex in model.children_of(edge)? {
        let Some(data) = model.node(&vertex).and_then(|n| n.data().as_vertex()) else {
            ogeom_bail!(Construction, "vertex node holds no vertex data");
        };
        let at = map(vertex.transform(model.datums())?.apply(data.point));
        if let Some(twin) = vertices.find(vertex.node(), at, data.tolerance.get(), tol) {
            record(history, &vertex, &twin);
        }
    }
    Ok(())
}

/// 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()
        }
    }

    /// A prism's near cap is its profile turned round. Baked, each face
    /// keeps its rings as it stored them and takes its sense back on top,
    /// so every edge is still walked once each way.
    #[test]
    fn a_baked_prism_walks_each_edge_once_each_way() {
        let mut model = Model::new();
        let block = make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T)
            .unwrap()
            .shape;
        let face = ogeom_topo::explore_unique(&model, &block, ShapeType::Face).unwrap()[0].clone();
        let prism = crate::make_prism(&mut model, &face, ogeom_math::Vector::new(0.0, 0.0, 5.0), T)
            .unwrap()
            .shape;
        let baked = baked_shape(&mut model, &prism, T).unwrap().shape;
        assert_eq!(crate::check::edges_walked_one_way(&model, &baked), 0);
    }

    #[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 a spline after conversion.
        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
        );
    }

    /// A box, a cylinder and a sphere (whose poles are degenerate edges)
    /// under a shear and an uneven stretch: every face, wire, edge and
    /// vertex of the input traces to exactly one sub-shape of its kind in
    /// the result and reads as affected, and each vertex's image stands
    /// where the map carries the old point.
    #[test]
    fn every_sub_shape_traces_to_its_twin_under_an_affine_map() {
        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::new(1.0, 2.0, 3.0),
        );
        let stretch = GeneralTransform::new(
            ogeom_math::Matrix3 {
                rows: [[2.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 0.5]],
            },
            ogeom_math::Vector::ZERO,
        );
        let mut model = Model::new();
        let block = make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T)
            .unwrap()
            .shape;
        let drum = make_cylinder(&mut model, Frame::WORLD, 2.0, 5.0, T)
            .unwrap()
            .shape;
        let ball = crate::make_sphere(&mut model, Frame::WORLD, 2.0, T)
            .unwrap()
            .shape;
        for solid in [&block, &drum, &ball] {
            for transform in [&shear, &stretch] {
                let built = general_transformed_shape(&mut model, solid, transform, T).unwrap();
                assert!(built.history.trace(solid)[0].is_same(&built.shape));
                for kind in [
                    ShapeType::Face,
                    ShapeType::Wire,
                    ShapeType::Edge,
                    ShapeType::Vertex,
                ] {
                    let parts = ogeom_topo::explore_unique(&model, solid, kind).unwrap();
                    let result = ogeom_topo::explore_unique(&model, &built.shape, kind).unwrap();
                    assert_eq!(parts.len(), result.len(), "{kind:?}");
                    for part in &parts {
                        assert!(built.history.is_affected(part), "{kind:?}");
                        let images = built.history.trace(part);
                        assert_eq!(images.len(), 1, "{kind:?}");
                        let found: Vec<&Shape> =
                            result.iter().filter(|r| r.is_same(&images[0])).collect();
                        assert_eq!(found.len(), 1, "{kind:?}");
                        if kind == ShapeType::Vertex {
                            let point = |v: &Shape| {
                                let data = model.node(v).unwrap().data().as_vertex().unwrap();
                                v.transform(model.datums()).unwrap().apply(data.point)
                            };
                            let want = transform.apply(point(part));
                            assert!(point(found[0]).distance(want) < 1e-9);
                        }
                    }
                }
            }
        }
    }
}