ogeom_algo/

sew.rs

//! Joining loose topology: ordering a bag of edges into a wire, and sewing free
//! faces into a shell.
//!
//! Both exist because geometry arrives disconnected. An imported file gives a
//! pile of faces that *touch* but share nothing; a sketch gives edges in
//! whatever order they were drawn. Topologically these are unrelated pieces,
//! and every algorithm that walks a boundary treats them that way: a shell of
//! faces that merely abut has a free edge everywhere two of them meet, encloses
//! no volume, and cannot be classified against.
//!
//! # Sewing is a topological operation, not a geometric one
//!
//! It does not move anything. Two edges within tolerance of each other are
//! decided to be *one* edge, and every face that used either uses that one,
//! so the shell closes because the topology says so, not because the geometry
//! was nudged until it did. A version that moved geometry to close gaps would
//! be a repair, would need to decide which of two positions is right, and would
//! quietly invalidate every tolerance in the neighbourhood.
//!
//! What it will not do is claim a closure it did not achieve. Faces that do not
//! meet within tolerance stay in separate shells, and the result says how many
//! there are.

use std::collections::{HashMap, HashSet};

use ogeom_core::{OgeomResult, Tolerances, ogeom_bail};
use ogeom_geom::Curve3d;
use ogeom_math::Point;
use ogeom_topo::{
    EdgeRepr, Model, NodeData, Orientation, Shape, ShapeType, TShapeId, explore_unique,
};

use crate::bins::Bins;
use crate::build::{edge_vertices, make_face_on, make_shell, make_wire};
use crate::history::{Built, History};

/// Roles sewing assigns.
pub mod roles {
    use ogeom_core::Role;

    /// An edge that two faces were found to share.
    pub const SEWN_EDGE: Role = Role::op_defined(40);
    /// A face rebuilt on shared edges.
    pub const SEWN_FACE: Role = Role::op_defined(41);
}

/// Put a bag of edges into an order that walks them end to end.
///
/// Reverses an edge where the chain reaches its far end first, so the result is
/// a path rather than a set. [`make_wire`] then accepts it: it checks that
/// consecutive edges meet, and a bag in the order it happened to be built in
/// almost never does.
///
/// Follows the chain from one end. Where an end meets more than two edges the
/// path is genuinely ambiguous (that is a branching network, not a wire), and
/// this refuses rather than picking one, because picking one silently discards
/// the branch nobody asked it to drop.
///
/// # Errors
///
/// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if the list is
/// empty, an edge is unbounded, the edges do not form a single connected path,
/// or a vertex joins three or more of them.
pub fn order_edges(model: &Model, edges: &[Shape], tol: Tolerances) -> OgeomResult<Vec<Shape>> {
    if edges.is_empty() {
        ogeom_bail!(Construction, "there are no edges to order");
    }
    if edges.len() == 1 {
        return Ok(edges.to_vec());
    }

    let mut ends = Vec::with_capacity(edges.len());
    for edge in edges {
        let Some((start, finish)) = edge_vertices(model, edge)? else {
            ogeom_bail!(
                Construction,
                "an unbounded edge cannot be shown to join anything"
            );
        };
        ends.push((placed(model, &start)?, placed(model, &finish)?));
    }

    // How many edge-ends meet at each position. Three is a branch, and a branch
    // has no single walk through it.
    for i in 0..edges.len() {
        for at in [ends[i].0, ends[i].1] {
            let meeting = ends
                .iter()
                .filter(|(a, b)| a.is_equal(at, tol) || b.is_equal(at, tol))
                .count();
            if meeting > 2 {
                ogeom_bail!(
                    Construction,
                    "{meeting} edges meet at {at:?}; that is a branching \
                     network rather than a wire, and choosing a path through it \
                     would silently drop the branches not chosen"
                );
            }
        }
    }

    // Start from a free end if there is one, so an open chain comes out running
    // the way it reads. A closed loop has none, and any edge will do.
    let start = (0..edges.len())
        .find(|&i| {
            !ends.iter().enumerate().any(|(j, (a, b))| {
                j != i && (a.is_equal(ends[i].0, tol) || b.is_equal(ends[i].0, tol))
            })
        })
        .unwrap_or(0);

    let mut used = vec![false; edges.len()];
    let mut out = Vec::with_capacity(edges.len());
    used[start] = true;
    out.push(edges[start].clone());
    let mut reach = ends[start].1;

    while out.len() < edges.len() {
        let mut stepped = false;
        for i in 0..edges.len() {
            if used[i] {
                continue;
            }
            let (a, b) = ends[i];
            if a.is_equal(reach, tol) {
                out.push(edges[i].clone());
                reach = b;
            } else if b.is_equal(reach, tol) {
                // The chain arrived at this edge's far end, so it is walked
                // backwards. Reversing the occurrence is what keeps the wire a
                // path; leaving it would make `make_wire` report a gap that is
                // really a direction.
                out.push(edges[i].reversed());
                reach = a;
            } else {
                continue;
            }
            used[i] = true;
            stepped = true;
            break;
        }
        if !stepped {
            ogeom_bail!(
                Construction,
                "the edges do not form one connected path: {} of {} could not \
                 be reached from the first",
                edges.len() - out.len(),
                edges.len()
            );
        }
    }
    Ok(out)
}

/// Build a wire from edges in any order.
///
/// [`order_edges`] then [`make_wire`].
///
/// # Errors
///
/// As [`order_edges`] and [`make_wire`].
pub fn make_wire_unordered(
    model: &mut Model,
    edges: &[Shape],
    tol: Tolerances,
) -> OgeomResult<Built> {
    let ordered = order_edges(model, edges, tol)?;
    make_wire(model, &ordered, tol)
}

/// What sewing produced.
#[derive(Debug, Clone)]
pub struct Sewn {
    /// One shell per connected group of faces.
    ///
    /// More than one means the faces did not all meet. That is reported rather
    /// than papered over: a single shell containing disconnected pieces would
    /// claim a closure that is not there.
    pub shells: Vec<Shape>,
    /// How many pairs of edges were found to be the same edge.
    pub joined: usize,
    /// Edges still used by exactly one face after sewing.
    ///
    /// Zero means every shell is closed. Anything else is the boundary that
    /// remains, and a caller that needs a solid needs this to be empty.
    pub free_edges: Vec<Shape>,
    /// History, as every operation reports.
    pub history: History,
}

/// Sew free faces into shells by finding the edges they share.
///
/// Two edges are the same edge when their ends coincide within tolerance
/// (either way round) *and* a point along them does too. The midpoint test is
/// what stops two different arcs between the same pair of vertices from being
/// merged into one, which is a real case: the two halves of a circle share both
/// ends.
///
/// Nothing is moved. See the module documentation.
///
/// # Errors
///
/// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if `faces` is
/// empty or holds something that is not a face;
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if a handle fails to
/// resolve.
pub fn sew(model: &mut Model, faces: &[Shape], tol: Tolerances) -> OgeomResult<Sewn> {
    if faces.is_empty() {
        ogeom_bail!(Construction, "there are no faces to sew");
    }
    for face in faces {
        if model.kind_of(face)? != ShapeType::Face {
            ogeom_bail!(Construction, "sewing joins faces");
        }
    }
    model.begin_operation();

    // Vertices first, and this is not an optimisation; it is what makes the
    // rest work. Deciding that two edges are one edge leaves the *neighbouring*
    // edges ending at the vertices they always had, which sit at the same
    // places as the survivor's but are different nodes. A wire built from that
    // mixture is reported to have a gap, because it has one: `is_same_position`
    // asks whether one node appears at two placements, which is the right
    // question and not this one.
    let mut vertices = merge_vertices(model, faces, tol)?;
    // Two edges decided to be one must end on the same vertices, or the
    // faces that bounded the dropped one keep its neighbours ending where
    // the dropped one did, and their wires open. Twins whose ends are still
    // two vertices (each within its own span of the other edge's end, not
    // of the other vertex) have those vertices joined, and the edges are
    // rebuilt on them and matched again.
    let mut rounds = 0;
    let (rebuilt_edges, merged, joined) = loop {
        let rebuilt_edges = rebuild_edges(model, faces, &vertices)?;

        // Every distinct edge node used by the faces, with the geometry that
        // decides whether two of them are the same edge.
        let mut catalogue: Vec<(TShapeId, Fingerprint)> = Vec::new();
        let mut catalogued: HashSet<TShapeId> = HashSet::new();
        for face in faces {
            for edge in explore_unique(model, face, ShapeType::Edge)? {
                let id = rebuilt_edges
                    .get(&edge.node())
                    .copied()
                    .unwrap_or(edge.node());
                if !catalogued.insert(id) {
                    continue;
                }
                if let Some(print) = fingerprint(model, &Shape::of(id), tol)? {
                    catalogue.push((id, print));
                }
            }
        }

        // Which node each edge is decided to *be*, and whether it runs the other
        // way from the one it replaced.
        let mut merged: HashMap<TShapeId, (TShapeId, bool)> = HashMap::new();
        let mut joined = 0;
        // The widest reach any pair compares its ends at.
        let reach = catalogue
            .iter()
            .fold(tol.confusion(), |acc, (_, print)| acc.max(print.width));
        let mut starts = Bins::new(reach);
        for (index, (_, print)) in catalogue.iter().enumerate() {
            starts.insert(print.start, index);
        }
        for i in 0..catalogue.len() {
            if merged.contains_key(&catalogue[i].0) {
                continue;
            }
            for j in twin_candidates(&catalogue, &starts, reach, i) {
                if merged.contains_key(&catalogue[j].0) {
                    continue;
                }
                let Some(flipped) = catalogue[i].1.same_as(&catalogue[j].1, tol)? else {
                    continue;
                };
                // The survivor now answers for both descriptions of the edge,
                // and its vertices must reach the twin's ends: two fingerprints
                // that matched within their stated widths may still disagree by
                // more than a fresh vertex's tolerance, and the disagreement is
                // recorded where the data model records it.
                let (kept_fp, dropped_fp) = (catalogue[i].1.clone(), catalogue[j].1.clone());
                let survivor = Shape::of(catalogue[i].0);
                let ends = if flipped {
                    [
                        (kept_fp.start, dropped_fp.end),
                        (kept_fp.end, dropped_fp.start),
                    ]
                } else {
                    [
                        (kept_fp.start, dropped_fp.start),
                        (kept_fp.end, dropped_fp.end),
                    ]
                };
                let bounds = model.children_of(&survivor)?;
                for vertex in &bounds {
                    if let Some(data) = model.node(vertex).and_then(|n| n.data().as_vertex()) {
                        let at = data.point;
                        let mut need = data.tolerance.get();
                        for (a, b) in &ends {
                            if at.distance(*a) <= need.max(tol.confusion() * 1e2) {
                                need = need.max(a.distance(*b) + tol.confusion());
                            }
                        }
                        if need > data.tolerance.get()
                            && let Some(node) = model.node_mut(vertex)
                            && let NodeData::Vertex(v) = node.data_mut()
                        {
                            v.tolerance = v.tolerance.widen_to(need);
                        }
                    }
                }
                merged.insert(catalogue[j].0, (catalogue[i].0, flipped));
                joined += 1;
            }
        }
        let apart = twin_ends_apart(model, &merged)?;
        if apart.is_empty() || rounds == 3 {
            break (rebuilt_edges, merged, joined);
        }
        rounds += 1;
        for (gone, keep) in apart {
            join_vertex(model, &mut vertices, gone, keep, tol)?;
        }
    };

    // The survivor has to carry the pcurves of the edge it replaced, or the
    // face that used the replaced one loses its description in parameter space
    // and stops being triangulable.
    //
    // Carrying is not copying. When the merge *flipped* (the two edges run
    // opposite ways), the dropped edge's pcurve traverses the shared points
    // backwards relative to the survivor's own curve, and copied unchanged it
    // makes the survivor's face walk one edge of its boundary the wrong way:
    // the parameter-space ring zigzags to zero area and the face stops being
    // triangulable. The boolean found this by sewing faces whose edges were
    // annotated before sewing decided which twin survives. The pcurve is
    // consumed by *proportional* same-parameter mapping, so reversing its
    // traversal exactly is swapping the stored range's ends.
    //
    // Nor is it copying when the two edges describe one curve at different
    // paces: a fitted rim against the exact circle it traces, which the
    // match admits by asking each middle to lie on the other's stretch. The
    // dropped edge's pcurve is same-parameter with the *dropped* curve; on
    // the survivor's parameter it drifts along the edge, and a face walks
    // its boundary off the vertex it shares. Such a pcurve is refitted at
    // the survivor's own parameters: the survivor's point at each, found
    // on the dropped curve, read through the pcurve into the chart.
    for (dropped, (kept, flipped)) in merged.clone() {
        let carried: Vec<EdgeRepr> = model
            .node_by_id(dropped)
            .and_then(|n| n.data().as_edge())
            .map(|d| {
                d.representations
                    .iter()
                    .filter(|r| r.is_parametric())
                    .cloned()
                    .collect()
            })
            .unwrap_or_default();
        if carried.is_empty() {
            continue;
        }
        let survivor = Shape::of(kept);
        let paced = repaced_carry(
            model,
            &Shape::of(dropped),
            &survivor,
            flipped,
            &carried,
            tol,
        )?;
        let Some(node) = model.node_mut(&survivor) else {
            ogeom_bail!(Dangling, "an edge is not in this model");
        };
        let NodeData::Edge(data) = node.data_mut() else {
            ogeom_bail!(Construction, "edge node holds no edge data");
        };
        for repr in paced {
            data.add(repr);
        }
    }

    // One map from every original edge to what it is now: rebuilt onto merged
    // vertices, then possibly merged with a coincident twin.
    let mut substitution: HashMap<TShapeId, (TShapeId, bool)> = HashMap::new();
    for (original, rebuilt) in &rebuilt_edges {
        let (final_id, flipped) = merged.get(rebuilt).copied().unwrap_or((*rebuilt, false));
        substitution.insert(*original, (final_id, flipped));
    }
    for (dropped, kept) in &merged {
        substitution.entry(*dropped).or_insert(*kept);
    }

    let mut history = History::new();
    let mut rebuilt = Vec::with_capacity(faces.len());
    for face in faces {
        let Some(sewn) = rebuild_face(model, face, &substitution, tol)? else {
            history.delete(face);
            continue;
        };
        model.set_derived(&sewn, std::slice::from_ref(face), roles::SEWN_FACE)?;
        history.modify(face, sewn.clone());
        rebuilt.push(sewn);
    }

    let groups = connected_groups(model, &rebuilt)?;
    let mut shells = Vec::with_capacity(groups.len());
    for group in groups {
        let shell = make_shell(model, &group)?.shape;
        for face in &group {
            history.generate(face, shell.clone());
        }
        shells.push(shell);
    }

    let free_edges = free_edges(model, &rebuilt)?;
    Ok(Sewn {
        shells,
        joined,
        free_edges,
        history,
    })
}

/// Decide which coincident vertices are the same vertex.
///
/// Returns only the ones that were replaced, mapping each to its survivor.
fn merge_vertices(
    model: &mut Model,
    faces: &[Shape],
    tol: Tolerances,
) -> OgeomResult<HashMap<TShapeId, TShapeId>> {
    let tolerance_of = |model: &Model, vertex: &Shape| {
        model
            .node(vertex)
            .and_then(|n| n.data().as_vertex())
            .map_or(0.0, |d| d.tolerance.get())
    };
    // The survivors, binned by position on cells as wide as the loosest
    // vertex; a vertex is compared with the survivors within the widest
    // reach any comparison can have, in the order they were kept.
    let mut loosest = tol.confusion();
    for face in faces {
        for vertex in explore_unique(model, face, ShapeType::Vertex)? {
            loosest = loosest.max(tolerance_of(model, &vertex));
        }
    }
    let mut bins = Bins::new(loosest);
    let mut seen: Vec<(TShapeId, Point, f64)> = Vec::new();
    let mut index_of: HashMap<TShapeId, usize> = HashMap::new();
    let mut widest = tol.confusion();
    let mut out = HashMap::new();
    for face in faces {
        for vertex in explore_unique(model, face, ShapeType::Vertex)? {
            if index_of.contains_key(&vertex.node()) {
                continue;
            }
            let at = placed(model, &vertex)?;
            let own = tolerance_of(model, &vertex);
            // Two vertices are one junction within what their *stated*
            // tolerances allow, not within a fresh vertex's default: a
            // vertex that recorded a welded gap reaches that far, and
            // merging by raw confusion would leave its twin standing a
            // recorded-but-ignored distance away.
            let meets = |(_, p, w): &&(TShapeId, Point, f64)| {
                p.distance(at) <= tol.confusion().max(*w).max(own)
            };
            let hit = match bins.near(at, widest.max(own)) {
                Some(near) => near.into_iter().map(|i| &seen[i]).find(meets),
                None => seen.iter().find(meets),
            }
            .map(|(kept, p, w)| (*kept, *p, *w));
            match hit {
                Some((kept, p, w)) => {
                    // The survivor answers for the absorbed vertex: its
                    // tolerance widens to reach the absorbed position plus
                    // whatever that vertex itself was allowed to stray.
                    let need = p.distance(at) + own + tol.confusion();
                    if need > w
                        && let Some(node) = model.node_mut(&Shape::of(kept))
                        && let NodeData::Vertex(v) = node.data_mut()
                    {
                        v.tolerance = v.tolerance.widen_to(need);
                    }
                    if let Some(entry) = index_of.get(&kept).map(|&i| &mut seen[i]) {
                        entry.2 = entry.2.max(need);
                        widest = widest.max(entry.2);
                    }
                    out.insert(vertex.node(), kept);
                }
                None => {
                    bins.insert(at, seen.len());
                    index_of.insert(vertex.node(), seen.len());
                    seen.push((vertex.node(), at, own));
                    widest = widest.max(own);
                }
            }
        }
    }
    Ok(out)
}

/// The vertex pairs twin edges end on that are not yet one vertex: the
/// dropped edge's end first, the survivor's second.
fn twin_ends_apart(
    model: &Model,
    merged: &HashMap<TShapeId, (TShapeId, bool)>,
) -> OgeomResult<Vec<(TShapeId, TShapeId)>> {
    let ends = |id: TShapeId| -> Option<(TShapeId, TShapeId)> {
        let children = model.node_by_id(id)?.children();
        Some((children.first()?.node(), children.last()?.node()))
    };
    let mut out = Vec::new();
    let mut pairs: Vec<(&TShapeId, &(TShapeId, bool))> = merged.iter().collect();
    pairs.sort_by_key(|(dropped, _)| dropped.index());
    for (dropped, (kept, flipped)) in pairs {
        let (Some((d0, d1)), Some((k0, k1))) = (ends(*dropped), ends(*kept)) else {
            continue;
        };
        let matched = if *flipped {
            [(d0, k1), (d1, k0)]
        } else {
            [(d0, k0), (d1, k1)]
        };
        for (d, k) in matched {
            if d != k && !out.contains(&(d, k)) {
                out.push((d, k));
            }
        }
    }
    Ok(out)
}

/// Make `gone` one vertex with `keep`: every vertex mapped to either now
/// maps to `keep`'s survivor, whose tolerance reaches `gone`'s span.
fn join_vertex(
    model: &mut Model,
    vertices: &mut HashMap<TShapeId, TShapeId>,
    gone: TShapeId,
    keep: TShapeId,
    tol: Tolerances,
) -> OgeomResult<()> {
    let resolve = |vertices: &HashMap<TShapeId, TShapeId>, mut v: TShapeId| {
        while let Some(&next) = vertices.get(&v) {
            if next == v {
                break;
            }
            v = next;
        }
        v
    };
    let (gone, keep) = (resolve(vertices, gone), resolve(vertices, keep));
    if gone == keep {
        return Ok(());
    }
    let (Some(g), Some(k)) = (
        model
            .node_by_id(gone)
            .and_then(|n| n.data().as_vertex())
            .map(|d| (d.point, d.tolerance.get())),
        model
            .node_by_id(keep)
            .and_then(|n| n.data().as_vertex())
            .map(|d| d.point),
    ) else {
        return Ok(());
    };
    let need = g.0.distance(k) + g.1 + tol.confusion();
    if let Some(node) = model.node_mut(&Shape::of(keep))
        && let NodeData::Vertex(v) = node.data_mut()
    {
        v.tolerance = v.tolerance.widen_to(need);
    }
    for target in vertices.values_mut() {
        if *target == gone {
            *target = keep;
        }
    }
    vertices.insert(gone, keep);
    Ok(())
}

/// The dropped edge's parametric representations as the survivor carries
/// them: reversed when the merge flipped, and refitted at the survivor's
/// parameters when the two curves pace one stretch differently. Two edges
/// on one curve object, or on curves whose middle parameters land within
/// the pair's honesty of each other, are carried as they are.
fn repaced_carry(
    model: &mut Model,
    dropped: &Shape,
    survivor: &Shape,
    flipped: bool,
    carried: &[EdgeRepr],
    tol: Tolerances,
) -> OgeomResult<Vec<EdgeRepr>> {
    let as_is = || -> Vec<EdgeRepr> {
        carried
            .iter()
            .cloned()
            .map(|r| if flipped { reversed_repr(r) } else { r })
            .collect()
    };
    let (Some(dropped_fp), Some(kept_fp)) = (
        fingerprint(&*model, dropped, tol)?,
        fingerprint(&*model, survivor, tol)?,
    ) else {
        return Ok(as_is());
    };
    let reach = tol.confusion().max(dropped_fp.width).max(kept_fp.width);
    if dropped_fp.middle.distance(kept_fp.middle) <= reach {
        if std::env::var_os("OGEOM_DEBUG_SEW").is_some() {
            eprintln!(
                "SEW carry as is: flipped {flipped}, middles {:.2e} apart, kept {:?} {:?} dropped {:?} {:?}",
                dropped_fp.middle.distance(kept_fp.middle),
                kept_fp.start,
                kept_fp.end,
                dropped_fp.start,
                dropped_fp.end
            );
        }
        return Ok(as_is());
    }
    const SAMPLES: usize = 24;
    let (klo, khi) = (kept_fp.range.0, kept_fp.range.1);
    let mut out = Vec::with_capacity(carried.len());
    let mut pending: Vec<(
        ogeom_topo::SurfaceId,
        ogeom_topo::Location,
        ogeom_geom::PlanarCurve,
        (f64, f64),
    )> = Vec::new();
    for repr in carried {
        let EdgeRepr::PCurve {
            curve: pc_id,
            surface,
            location,
            range: prange,
        } = repr
        else {
            out.push(if flipped {
                reversed_repr(repr.clone())
            } else {
                repr.clone()
            });
            continue;
        };
        let Some(pcurve) = model.geometry().pcurve(*pc_id) else {
            ogeom_bail!(Dangling, "pcurve is not in this model");
        };
        let periods = model.geometry().surface(*surface).map(|sg| {
            use ogeom_geom::Surface as _;
            let ((ua, ub), (va, vb)) = sg.domain();
            (
                if sg.is_periodic_u() { ub - ua } else { 0.0 },
                if sg.is_periodic_v() { vb - va } else { 0.0 },
            )
        });
        let (dlo, dhi) = (dropped_fp.range.0, dropped_fp.range.1);
        let mut params = Vec::with_capacity(SAMPLES + 1);
        let mut image: Vec<ogeom_math::Point2> = Vec::with_capacity(SAMPLES + 1);
        for k in 0..=SAMPLES {
            #[allow(clippy::cast_precision_loss)]
            let t = klo + (khi - klo) * (k as f64) / (SAMPLES as f64);
            let p = kept_fp.curve.point_at(t, tol)?;
            let foot = crate::project_on_curve(&dropped_fp.curve, p, 64, tol)?;
            // The foot's parameter on the dropped curve, then through the
            // proportional map onto the pcurve's own window. On a curve that
            // closes on itself the foot may come back a turn away from the
            // stretch (a rim's last piece, seen from its own points, sits
            // at the start of the loop as much as at its end) and is
            // carried across the turn before it is clamped.
            let (lo, hi) = (dlo.min(dhi), dlo.max(dhi));
            let (da, db) = dropped_fp.curve.domain();
            let turn = db - da;
            let mut s = foot.parameter;
            if turn > 0.0 {
                if s < lo - tol.parametric() && s + turn <= hi + tol.parametric() {
                    s += turn;
                } else if s > hi + tol.parametric() && s - turn >= lo - tol.parametric() {
                    s -= turn;
                }
            }
            let s = s.clamp(lo, hi);
            let pt = if (dhi - dlo).abs() <= f64::MIN_POSITIVE {
                prange.0
            } else {
                prange.0 + (prange.1 - prange.0) * (s - dlo) / (dhi - dlo)
            };
            let mut uv = ogeom_geom::Curve2d::point_at(pcurve, pt, tol)?;
            if let (Some((pu, pv)), Some(prev)) = (periods, image.last()) {
                for (coord, period, before) in [(&mut uv.x, pu, prev.x), (&mut uv.y, pv, prev.y)] {
                    if period > 0.0 {
                        while *coord - before > period / 2.0 {
                            *coord -= period;
                        }
                        while before - *coord > period / 2.0 {
                            *coord += period;
                        }
                    }
                }
            }
            params.push(t);
            image.push(uv);
        }
        let fitted =
            ogeom_geom::fit::fit_points_2d_at(&params, &image, 3, tol.confusion() * 10.0, tol)?;
        if std::env::var_os("OGEOM_DEBUG_SEW").is_some() {
            use ogeom_geom::Surface as _;
            let mut worst_sample = 0.0_f64;
            let mut worst_fit = 0.0_f64;
            if let Some(sg) = model.geometry().surface(*surface) {
                for (t, uv) in params.iter().zip(&image) {
                    let p = kept_fp.curve.point_at(*t, tol)?;
                    worst_sample = worst_sample.max(sg.point_at(uv.x, uv.y, tol)?.distance(p));
                    let f = ogeom_geom::Curve2d::point_at(&fitted.curve, *t, tol)?;
                    worst_fit = worst_fit.max(sg.point_at(f.x, f.y, tol)?.distance(p));
                }
            }
            eprintln!(
                "SEW refit: samples off surface by {worst_sample:.2e}, fit off by {worst_fit:.2e} (fit error {:.2e} met {}) domain {:?} over ({klo:.4}, {khi:.4}); dropped range {:?}",
                fitted.error,
                fitted.met,
                ogeom_geom::Curve2d::domain(&fitted.curve),
                dropped_fp.range
            );
        }
        if !fitted.met || fitted.error > reach.max(tol.confusion() * 1e3) {
            // A refit that misses its budget is no description of the edge;
            // the pcurve is carried as it came, its drift along the edge and
            // all, rather than replaced by a worse one.
            out.push(if flipped {
                reversed_repr(repr.clone())
            } else {
                repr.clone()
            });
            continue;
        }
        pending.push((*surface, location.clone(), fitted.curve.into(), (klo, khi)));
    }
    for (surface, location, planar, range) in pending {
        let curve = model.geometry_mut().add_pcurve(planar);
        out.push(EdgeRepr::PCurve {
            curve,
            surface,
            location,
            range,
        });
    }
    Ok(out)
}

/// A parametric representation running the other way.
///
/// The consumers map a 3D-curve parameter onto the stored range
/// proportionally, so swapping the range's ends reverses the traversal
/// exactly, with no new geometry. A seam also swaps which pcurve is the
/// forward one, since "forward" is defined by the traversal that just
/// reversed.
fn reversed_repr(repr: EdgeRepr) -> EdgeRepr {
    match repr {
        EdgeRepr::PCurve {
            curve,
            surface,
            location,
            range,
        } => EdgeRepr::PCurve {
            curve,
            surface,
            location,
            range: (range.1, range.0),
        },
        EdgeRepr::Seam {
            forward,
            reversed,
            surface,
            location,
            range,
        } => EdgeRepr::Seam {
            forward: reversed,
            reversed: forward,
            surface,
            location,
            range: (range.1, range.0),
        },
        other => other,
    }
}

/// Rebuild every edge whose bounding vertices were merged away.
///
/// An edge's bounds live in its node, so an edge cannot be pointed at a
/// different vertex; it has to be built again. Its data comes across whole,
/// representations included, so the new edge describes itself exactly as the
/// old one did and only its ends have changed.
fn rebuild_edges(
    model: &mut Model,
    faces: &[Shape],
    vertices: &HashMap<TShapeId, TShapeId>,
) -> OgeomResult<HashMap<TShapeId, TShapeId>> {
    let mut out = HashMap::new();
    if vertices.is_empty() {
        return Ok(out);
    }
    let mut done: HashSet<TShapeId> = HashSet::new();
    for face in faces {
        for edge in explore_unique(model, face, ShapeType::Edge)? {
            if !done.insert(edge.node()) {
                continue;
            }

            let Some(node) = model.node(&edge) else {
                ogeom_bail!(Dangling, "edge is not in this model");
            };
            let bounds: Vec<Shape> = node.children().to_vec();
            if !bounds.iter().any(|b| vertices.contains_key(&b.node())) {
                continue;
            }
            let NodeData::Edge(data) = node.data().clone() else {
                continue;
            };
            let moved: Vec<Shape> = bounds
                .iter()
                .map(|b| match vertices.get(&b.node()) {
                    Some(kept) => Shape::new(*kept, b.location().clone(), b.orientation()),
                    None => b.clone(),
                })
                .collect();
            let fresh = model.add_edge(*data, &moved)?;
            out.insert(edge.node(), fresh.node());
        }
    }
    Ok(out)
}

/// What decides whether two edges are the same edge.
#[derive(Debug, Clone)]
struct Fingerprint {
    start: Point,
    middle: Point,
    end: Point,
    /// The edge's curve in space and the stretch it covers, for the middle
    /// of another edge to be asked whether it lies on this one.
    curve: ogeom_geom::Curve,
    range: (f64, f64),
    /// How far this edge's own stated tolerances let it stray: the widest of
    /// the edge's and its vertices'. An edge whose junction was welded across
    /// a recorded gap carries that gap here, and the comparison honours it:
    /// per-entity tolerances are the data model's, not a nicety of import.
    width: f64,
}

impl Fingerprint {
    /// How far `p` sits from this edge's own stretch of its curve.
    fn off(&self, p: Point, tol: Tolerances) -> OgeomResult<f64> {
        let foot = crate::project_on_curve(&self.curve, p, 64, tol)?;
        let (lo, hi) = (
            self.range.0.min(self.range.1),
            self.range.0.max(self.range.1),
        );
        let mut t = foot.parameter;
        if self.curve.is_periodic() {
            let (dlo, dhi) = self.curve.domain();
            let period = dhi - dlo;
            if period > 0.0 {
                t = lo + (t - lo).rem_euclid(period);
            }
        }
        if t >= lo - tol.parametric() && t <= hi + tol.parametric() {
            return Ok(foot.distance);
        }
        Ok(p.distance(self.start).min(p.distance(self.end)))
    }

    /// Whether two edges coincide, and if so whether the second runs backwards.
    fn same_as(&self, other: &Self, tol: Tolerances) -> OgeomResult<Option<bool>> {
        let reach = tol.confusion().max(self.width).max(other.width);
        let near = |a: Point, b: Point| a.distance(b) <= reach;
        // Ends first: they cost a distance each, and most candidates that
        // start near this edge end somewhere else. The middle is asked only
        // of a pair whose ends already agree.
        let along = near(self.start, other.start) && near(self.end, other.end);
        let against = near(self.start, other.end) && near(self.end, other.start);
        if !along && !against {
            return Ok(None);
        }
        // The midpoint is not a nicety. Two arcs between the same pair of
        // vertices (the two halves of a circle) agree at both ends and are
        // not the same edge, and merging them would fuse a shape to itself.
        // Two descriptions of one curve need not agree on where its middle
        // *parameter* falls (a fitted rim against the exact circle it
        // traces paces itself differently), so each middle is asked to lie
        // on the other's stretch instead, which the far half of a circle
        // still fails.
        if !near(self.middle, other.middle)
            && !(other.off(self.middle, tol)? <= reach && self.off(other.middle, tol)? <= reach)
        {
            if std::env::var_os("OGEOM_DEBUG_SEW").is_some() {
                let foot = crate::project_on_curve(&other.curve, self.middle, 64, tol)?;
                eprintln!(
                    "SEW near miss: ends agree within {reach:.2e}, middles off {:.2e} / {:.2e} (widths {:.2e}, {:.2e}) at {:?}; foot on other at {:.6} (range {:?}, domain {:?}, periodic {}) distance {:.2e}",
                    other.off(self.middle, tol)?,
                    self.off(other.middle, tol)?,
                    self.width,
                    other.width,
                    self.middle,
                    foot.parameter,
                    other.range,
                    other.curve.domain(),
                    other.curve.is_periodic(),
                    foot.distance
                );
            }
            return Ok(None);
        }
        Ok(Some(!along))
    }
}

/// The edges after `i` in the catalogue that could be the same edge as
/// edge `i`, in catalogue order.
///
/// Two edges are one only when each end of one meets an end of the other,
/// so an edge's twin starts within reach of one of its ends: the edges
/// binned by where they start, near either end of edge `i`, are every edge
/// that could match, and an edge is asked about those alone rather than
/// about the whole catalogue.
fn twin_candidates(
    catalogue: &[(TShapeId, Fingerprint)],
    starts: &Bins,
    reach: f64,
    i: usize,
) -> Vec<usize> {
    let print = &catalogue[i].1;
    let (Some(from_start), Some(from_end)) = (
        starts.near(print.start, reach),
        starts.near(print.end, reach),
    ) else {
        return ((i + 1)..catalogue.len()).collect();
    };
    let mut out: Vec<usize> = from_start
        .into_iter()
        .chain(from_end)
        .filter(|&j| j > i)
        .collect();
    out.sort_unstable();
    out.dedup();
    out
}

/// An edge's ends and midpoint, in space.
fn fingerprint(model: &Model, edge: &Shape, tol: Tolerances) -> OgeomResult<Option<Fingerprint>> {
    let Some(data) = model.node(edge).and_then(|n| n.data().as_edge()) else {
        return Ok(None);
    };
    let Some(EdgeRepr::Curve3d { curve, range, .. }) = data.curve3d() else {
        // A degenerate edge has no curve and no length; there is nothing about
        // it that could match another edge's geometry.
        return Ok(None);
    };
    let Some(geometry) = model.geometry().curve(*curve) else {
        ogeom_bail!(Dangling, "curve is not in this model");
    };
    let placement = edge.transform(model.datums())?;
    let mut width = data.tolerance.get();
    for vertex in model.children_of(edge)? {
        if let Some(v) = model.node(&vertex).and_then(|n| n.data().as_vertex()) {
            width = width.max(v.tolerance.get());
        }
    }
    use ogeom_geom::Transformable as _;
    Ok(Some(Fingerprint {
        start: placement.apply(geometry.point_at(range.0, tol)?),
        middle: placement.apply(geometry.point_at(f64::midpoint(range.0, range.1), tol)?),
        end: placement.apply(geometry.point_at(range.1, tol)?),
        curve: geometry.clone().transformed(&placement, tol)?,
        range: *range,
        width,
    }))
}

/// A vertex's position in space.
fn placed(model: &Model, vertex: &Shape) -> OgeomResult<Point> {
    let Some(data) = model.node(vertex).and_then(|n| n.data().as_vertex()) else {
        ogeom_bail!(Construction, "expected a vertex");
    };
    Ok(vertex.transform(model.datums())?.apply(data.point))
}

/// Rebuild a face with merged edges in place of the ones they replaced.
fn rebuild_face(
    model: &mut Model,
    face: &Shape,
    merged: &HashMap<TShapeId, (TShapeId, bool)>,
    tol: Tolerances,
) -> OgeomResult<Option<Shape>> {
    let Some(data) = model.node(face).and_then(|n| n.data().as_face()).cloned() else {
        ogeom_bail!(Construction, "expected a face");
    };
    // Nothing to substitute: the face is already built on the shared edges, and
    // rebuilding it would only mint a node identical to the one there.
    let mut touched = false;

    let mut wires = Vec::new();
    for wire in model.ordered_children_of(face)? {
        let mut ring = Vec::new();
        for edge in model.ordered_children_of(&wire)? {
            match merged.get(&edge.node()) {
                Some((kept, flipped)) => {
                    touched = true;
                    let mut replacement =
                        Shape::new(*kept, edge.location().clone(), edge.orientation());
                    if *flipped {
                        replacement = replacement.reversed();
                    }
                    ring.push(replacement);
                }
                None => ring.push(edge),
            }
        }
        // A ring that merging collapsed onto one edge, walked out and back,
        // bounds no area: the sliver between two coincident strands that the
        // sew has just found to be one edge. Such a ring is dropped, and a
        // face whose outer ring it was with it.
        let one_edge = !ring.is_empty() && ring.iter().all(|e| e.node() == ring[0].node());
        if one_edge && ring.len() >= 2 {
            if wires.is_empty() {
                return Ok(None);
            }
            continue;
        }
        let wire = match make_wire(model, &ring, tol) {
            Ok(w) => w.shape,
            Err(e) => {
                if std::env::var_os("OGEOM_DEBUG_SEW").is_some() {
                    eprintln!("SEW WIRE FAIL: {e}");
                    for edge in &ring {
                        if let Some((a, b)) = edge_vertices(model, edge)? {
                            let (pa, pb) = (placed(model, &a)?, placed(model, &b)?);
                            let fp = fingerprint(model, edge, tol)?;
                            eprintln!(
                                "   edge {:?}{} ({:.5},{:.5},{:.5}) v{} -> ({:.5},{:.5},{:.5}) v{} width {:.2e}",
                                edge.node(),
                                if edge.orientation() == ogeom_topo::Orientation::Reversed {
                                    " rev"
                                } else {
                                    ""
                                },
                                pa.x,
                                pa.y,
                                pa.z,
                                a.node().index(),
                                pb.x,
                                pb.y,
                                pb.z,
                                b.node().index(),
                                fp.map_or(0.0, |f| f.width)
                            );
                        }
                    }
                }
                return Err(e);
            }
        };
        wires.push(wire);
    }
    if !touched {
        return Ok(Some(face.clone()));
    }
    if wires.is_empty() {
        return Ok(None);
    }
    let sewn = match make_face_on(model, data.surface, &wires, tol) {
        Ok(built) => built.shape,
        Err(e) => {
            if std::env::var_os("OGEOM_DEBUG_SEW").is_some() {
                eprintln!("SEW FACE FAIL: {e}");
                for (wi, wire) in wires.iter().enumerate() {
                    for edge in model.ordered_children_of(wire)? {
                        if let Some((a, b)) = edge_vertices(model, &edge)? {
                            let (pa, pb) = (placed(model, &a)?, placed(model, &b)?);
                            eprintln!(
                                "   wire {wi} edge {:?}{} ({:.5},{:.5},{:.5}) v{} -> ({:.5},{:.5},{:.5}) v{}",
                                edge.node(),
                                if edge.orientation() == ogeom_topo::Orientation::Reversed {
                                    " rev"
                                } else {
                                    ""
                                },
                                pa.x,
                                pa.y,
                                pa.z,
                                a.node().index(),
                                pb.x,
                                pb.y,
                                pb.z,
                                b.node().index()
                            );
                        }
                    }
                }
            }
            return Err(e);
        }
    };
    Ok(if face.orientation() == Orientation::Reversed {
        Some(sewn.reversed())
    } else {
        Some(sewn)
    })
}

/// Group faces by whether they share an edge, transitively.
fn connected_groups(model: &Model, faces: &[Shape]) -> OgeomResult<Vec<Vec<Shape>>> {
    let mut group_of: Vec<usize> = (0..faces.len()).collect();
    let mut edges_of = Vec::with_capacity(faces.len());
    for face in faces {
        edges_of.push(
            explore_unique(model, face, ShapeType::Edge)?
                .into_iter()
                .map(|e| e.node())
                .collect::<Vec<_>>(),
        );
    }

    // Union-find: each face joins the first face seen with each of its
    // edges, which joins it to every face sharing that edge transitively.
    let mut first_user: HashMap<TShapeId, usize> = HashMap::new();
    for (i, edges) in edges_of.iter().enumerate() {
        for edge in edges {
            let j = *first_user.entry(*edge).or_insert(i);
            let (a, b) = (find(&mut group_of, j), find(&mut group_of, i));
            if a != b {
                group_of[b] = a;
            }
        }
    }

    let mut groups: HashMap<usize, Vec<Shape>> = HashMap::new();
    for (i, face) in faces.iter().enumerate() {
        groups
            .entry(find(&mut group_of, i))
            .or_default()
            .push(face.clone());
    }
    let mut out: Vec<Vec<Shape>> = groups.into_values().collect();
    // Deterministic: a result whose shells come back in a different order each
    // run is one nobody can compare against.
    out.sort_by_key(|group| group.first().map(Shape::node));
    Ok(out)
}

/// Follow a union-find chain to its root.
fn find(parent: &mut [usize], mut i: usize) -> usize {
    // Halving the path on the way up keeps every chain short.
    while parent[i] != i {
        parent[i] = parent[parent[i]];
        i = parent[i];
    }
    i
}

/// Edges still used by exactly one face.
fn free_edges(model: &Model, faces: &[Shape]) -> OgeomResult<Vec<Shape>> {
    let mut uses: HashMap<TShapeId, (usize, Shape)> = HashMap::new();
    for face in faces {
        for wire in model.children_of(face)? {
            for edge in model.children_of(&wire)? {
                if model
                    .node(&edge)
                    .and_then(|n| n.data().as_edge())
                    .is_some_and(|d| d.degenerate)
                {
                    continue;
                }
                let entry = uses.entry(edge.node()).or_insert((0, edge.clone()));
                entry.0 += 1;
            }
        }
    }
    let mut out: Vec<Shape> = uses
        .into_values()
        .filter(|(count, _)| count % 2 == 1)
        .map(|(_, edge)| edge)
        .collect();
    out.sort_by_key(Shape::node);
    Ok(out)
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;
    use crate::{check_tessellation, is_shell_closed, make_box, make_polygon};
    use ogeom_geom::PlaneSurface;
    use ogeom_math::{Frame, Plane, Vector};
    use ogeom_topo::Location;

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

    fn fine() -> ogeom_mesh::Deflection {
        ogeom_mesh::Deflection {
            chord: 0.02,
            ..ogeom_mesh::Deflection::default()
        }
    }

    /// A square face in the z = `at` plane, built from its own fresh edges so
    /// it shares nothing with anything else.
    fn loose_square(model: &mut Model, corners: [Point; 4]) -> Shape {
        let wire = make_polygon(model, &corners, true, T).unwrap().shape;
        let normal =
            ogeom_math::Direction::from_cross(corners[1] - corners[0], corners[2] - corners[1], T)
                .unwrap();
        let frame = ogeom_math::Frame::new(
            corners[0],
            normal,
            ogeom_math::Direction::new(corners[1] - corners[0], T).unwrap(),
            T,
        )
        .unwrap();
        let surface = model
            .geometry_mut()
            .add_surface(PlaneSurface::new(Plane::new(frame)).into());
        for edge in model.children_of(&wire).unwrap() {
            let (a, b) = crate::edge_vertices(model, &edge).unwrap().unwrap();
            let (pa, pb) = (placed(model, &a).unwrap(), placed(model, &b).unwrap());
            let flat = |p: Point| {
                let l = frame.to_local(p);
                ogeom_math::Point2::new(l.x, l.y)
            };
            crate::attach_pcurve(
                model,
                &edge,
                ogeom_geom::Line2d::segment(flat(pa), flat(pb), T)
                    .unwrap()
                    .into(),
                surface,
                Location::identity(),
                (0.0, pa.distance(pb)),
            )
            .unwrap();
        }
        crate::make_face_on(model, surface, std::slice::from_ref(&wire), T)
            .unwrap()
            .shape
    }

    #[test]
    fn edges_in_any_order_come_back_as_a_path() {
        let mut model = Model::new();
        let corners = [
            Point::new(0.0, 0.0, 0.0),
            Point::new(1.0, 0.0, 0.0),
            Point::new(1.0, 1.0, 0.0),
            Point::new(0.0, 1.0, 0.0),
        ];
        let wire = make_polygon(&mut model, &corners, true, T).unwrap().shape;
        let mut edges = model.children_of(&wire).unwrap();
        // Shuffled, and some of them turned round.
        edges.swap(0, 2);
        edges[1] = edges[1].reversed();
        edges[3] = edges[3].reversed();

        let ordered = order_edges(&model, &edges, T).unwrap();
        assert_eq!(ordered.len(), 4);
        // A wire only builds if consecutive edges actually meet, so this is the
        // property under test rather than a separate one.
        let rebuilt = make_wire(&mut model, &ordered, T).unwrap().shape;
        assert!(crate::is_wire_closed(&model, &rebuilt, T).unwrap());
    }

    #[test]
    fn edges_that_do_not_form_one_path_are_refused() {
        let mut model = Model::new();
        let a = make_polygon(
            &mut model,
            &[Point::ORIGIN, Point::new(1.0, 0.0, 0.0)],
            false,
            T,
        )
        .unwrap()
        .shape;
        let b = make_polygon(
            &mut model,
            &[Point::new(5.0, 0.0, 0.0), Point::new(6.0, 0.0, 0.0)],
            false,
            T,
        )
        .unwrap()
        .shape;
        let mut edges = model.children_of(&a).unwrap();
        edges.extend(model.children_of(&b).unwrap());

        let err = order_edges(&model, &edges, T).unwrap_err();
        assert!(
            err.to_string().contains("connected path"),
            "unexpected message: {err}"
        );
        assert!(order_edges(&model, &[], T).is_err());
    }

    #[test]
    fn a_branching_network_is_refused_rather_than_arbitrarily_walked() {
        // Three edges from one point. Any path through it drops a branch, and
        // dropping one silently is worse than saying there is no answer.
        let mut model = Model::new();
        let hub = Point::ORIGIN;
        let mut edges = Vec::new();
        for tip in [
            Point::new(1.0, 0.0, 0.0),
            Point::new(0.0, 1.0, 0.0),
            Point::new(0.0, 0.0, 1.0),
        ] {
            let w = make_polygon(&mut model, &[hub, tip], false, T)
                .unwrap()
                .shape;
            edges.extend(model.children_of(&w).unwrap());
        }
        let err = order_edges(&model, &edges, T).unwrap_err();
        assert!(
            err.to_string().contains("branching"),
            "unexpected message: {err}"
        );
    }

    #[test]
    fn two_faces_that_touch_are_sewn_into_one_shell() {
        let mut model = Model::new();
        let left = loose_square(
            &mut model,
            [
                Point::new(0.0, 0.0, 0.0),
                Point::new(1.0, 0.0, 0.0),
                Point::new(1.0, 1.0, 0.0),
                Point::new(0.0, 1.0, 0.0),
            ],
        );
        let right = loose_square(
            &mut model,
            [
                Point::new(1.0, 0.0, 0.0),
                Point::new(2.0, 0.0, 0.0),
                Point::new(2.0, 1.0, 0.0),
                Point::new(1.0, 1.0, 0.0),
            ],
        );

        // Before: eight edges, nothing shared.
        let before = explore_unique(&model, &left, ShapeType::Edge)
            .unwrap()
            .len()
            + explore_unique(&model, &right, ShapeType::Edge)
                .unwrap()
                .len();
        assert_eq!(before, 8);

        let sewn = sew(&mut model, &[left.clone(), right.clone()], T).unwrap();
        assert_eq!(sewn.shells.len(), 1, "they touch, so they are one shell");
        assert_eq!(sewn.joined, 1, "one shared edge");
        assert_eq!(
            explore_unique(&model, &sewn.shells[0], ShapeType::Edge)
                .unwrap()
                .len(),
            7,
            "the shared edge is one edge now, not two"
        );
        // A sheet, so it still has a boundary: six free edges round the
        // outside, and the shared one is not among them.
        assert_eq!(sewn.free_edges.len(), 6);
        assert!(!is_shell_closed(&model, &sewn.shells[0]).unwrap());
        assert!(sewn.history.is_affected(&left));
    }

    /// Twin edges whose ends are two vertices apart by more than either
    /// vertex's own tolerance, though within the edges': the right square's
    /// corner sits a hundredth below the left's, and its shared edge is loose
    /// enough to be the left's. Merged, the edges must end on one vertex, or
    /// the right square's bottom edge still ends at its own corner and its
    /// wire opens.
    #[test]
    fn twin_edges_join_the_vertices_they_end_on() {
        let mut model = Model::new();
        let left = loose_square(
            &mut model,
            [
                Point::new(0.0, 0.0, 0.0),
                Point::new(1.0, 0.0, 0.0),
                Point::new(1.0, 1.0, 0.0),
                Point::new(0.0, 1.0, 0.0),
            ],
        );
        let right = loose_square(
            &mut model,
            [
                Point::new(1.0, -0.01, 0.0),
                Point::new(2.0, 0.0, 0.0),
                Point::new(2.0, 1.0, 0.0),
                Point::new(1.0, 1.0, 0.0),
            ],
        );
        for edge in explore_unique(&model, &right, ShapeType::Edge).unwrap() {
            let (a, b) = crate::edge_vertices(&model, &edge).unwrap().unwrap();
            let (pa, pb) = (placed(&model, &a).unwrap(), placed(&model, &b).unwrap());
            if (pa.x - 1.0).abs() < 1e-9
                && (pb.x - 1.0).abs() < 1e-9
                && let Some(node) = model.node_mut(&edge)
                && let NodeData::Edge(data) = node.data_mut()
            {
                data.tolerance = data.tolerance.widen_to(0.012);
            }
        }
        let sewn = sew(&mut model, &[left, right], T).unwrap();
        assert_eq!(sewn.joined, 1, "the loose edge is the left square's");
        assert_eq!(sewn.shells.len(), 1);
        assert_eq!(
            explore_unique(&model, &sewn.shells[0], ShapeType::Vertex)
                .unwrap()
                .len(),
            6,
            "the two corners at the bottom of the shared edge are one"
        );
        assert_eq!(sewn.free_edges.len(), 6);
    }

    #[test]
    fn faces_that_do_not_meet_stay_in_separate_shells() {
        // Claiming one shell would claim a closure that is not there.
        let mut model = Model::new();
        let here = loose_square(
            &mut model,
            [
                Point::new(0.0, 0.0, 0.0),
                Point::new(1.0, 0.0, 0.0),
                Point::new(1.0, 1.0, 0.0),
                Point::new(0.0, 1.0, 0.0),
            ],
        );
        let far = loose_square(
            &mut model,
            [
                Point::new(50.0, 0.0, 0.0),
                Point::new(51.0, 0.0, 0.0),
                Point::new(51.0, 1.0, 0.0),
                Point::new(50.0, 1.0, 0.0),
            ],
        );
        let sewn = sew(&mut model, &[here, far], T).unwrap();
        assert_eq!(sewn.shells.len(), 2);
        assert_eq!(sewn.joined, 0);
        assert_eq!(sewn.free_edges.len(), 8);
    }

    #[test]
    fn a_boxs_faces_taken_apart_and_sewn_back_close_again() {
        // The end-to-end case. The faces already share edges here, so what is
        // under test is that sewing does not *break* a shell that was closed,
        // and that the mesh still agrees with the topology afterwards, which is
        // the check a re-built face is most likely to fail.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T)
            .unwrap()
            .shape;
        let faces = explore_unique(&model, &solid, ShapeType::Face).unwrap();

        let sewn = sew(&mut model, &faces, T).unwrap();
        assert_eq!(sewn.shells.len(), 1);
        assert!(sewn.free_edges.is_empty(), "a box has no free edges");
        assert!(is_shell_closed(&model, &sewn.shells[0]).unwrap());
        assert!(
            check_tessellation(&model, &sewn.shells[0], fine(), T)
                .unwrap()
                .is_valid()
        );
    }

    #[test]
    fn two_arcs_between_the_same_vertices_are_not_the_same_edge() {
        // The reason the fingerprint samples the middle. Both halves of a
        // circle agree at both ends; merging them would fuse the shape to
        // itself and the mistake would look like a successful sew.
        let mut model = Model::new();
        let circle = ogeom_math::Circle::new(Frame::WORLD, 1.0, T).unwrap();
        let upper = crate::make_edge(
            &mut model,
            ogeom_geom::CircleCurve::new(circle).into(),
            (0.0, std::f64::consts::PI),
            T,
        )
        .unwrap()
        .shape;
        let lower = crate::make_edge(
            &mut model,
            ogeom_geom::CircleCurve::new(circle).into(),
            (std::f64::consts::PI, std::f64::consts::TAU),
            T,
        )
        .unwrap()
        .shape;

        let a = fingerprint(&model, &upper, T).unwrap().unwrap();
        let b = fingerprint(&model, &lower, T).unwrap().unwrap();
        assert!(
            a.same_as(&b, T).unwrap().is_none(),
            "two different arcs were called the same edge"
        );
        assert!(a.same_as(&a, T).unwrap() == Some(false));
    }

    #[test]
    fn an_edge_found_the_other_way_round_is_reversed_rather_than_dropped() {
        let mut model = Model::new();
        let up = Point::new(0.0, 0.0, 1.0);
        let down = Point::new(0.0, 0.0, 0.0);
        let a = crate::make_edge(
            &mut model,
            ogeom_geom::LineCurve::segment(down, up, T).unwrap().into(),
            (0.0, 1.0),
            T,
        )
        .unwrap()
        .shape;
        let b = crate::make_edge(
            &mut model,
            ogeom_geom::LineCurve::segment(up, down, T).unwrap().into(),
            (0.0, 1.0),
            T,
        )
        .unwrap()
        .shape;

        let pa = fingerprint(&model, &a, T).unwrap().unwrap();
        let pb = fingerprint(&model, &b, T).unwrap().unwrap();
        assert_eq!(
            pa.same_as(&pb, T).unwrap(),
            Some(true),
            "the same edge, running the other way"
        );
    }

    #[test]
    fn flipped_merges_carry_their_pcurves_the_right_way_round() {
        // Six faces of a unit cube, each built loose with its own vertices
        // and pre-attached pcurves, wound counter-clockwise around the
        // outward normal as a shell is. Sewing merges all twelve edge pairs,
        // and every merge is *flipped*: the two faces walk their shared
        // edge opposite ways. A carried pcurve copied unchanged then makes
        // the losing face walk edges backwards in parameter space; with
        // several such edges in one ring the boundary zigzags, and faces
        // stop triangulating or triangulate degenerately. Two squares are
        // not enough to see it (a single backwards two-point edge self-heals
        // in ring assembly), which is why this test is a cube.
        //
        // The carry must reverse with the merge: consumers map 3D parameters
        // onto the pcurve range proportionally, so swapping the stored
        // range's ends reverses the traversal exactly. The boolean found
        // this by sewing faces annotated before sewing decided which twin
        // survives.
        let mut model = Model::new();
        let c = Point::new;
        let faces = [
            [c(0., 0., 0.), c(0., 1., 0.), c(1., 1., 0.), c(1., 0., 0.)],
            [c(0., 0., 1.), c(1., 0., 1.), c(1., 1., 1.), c(0., 1., 1.)],
            [c(0., 0., 0.), c(1., 0., 0.), c(1., 0., 1.), c(0., 0., 1.)],
            [c(0., 1., 0.), c(0., 1., 1.), c(1., 1., 1.), c(1., 1., 0.)],
            [c(0., 0., 0.), c(0., 0., 1.), c(0., 1., 1.), c(0., 1., 0.)],
            [c(1., 0., 0.), c(1., 1., 0.), c(1., 1., 1.), c(1., 0., 1.)],
        ];
        let built: Vec<Shape> = faces.iter().map(|f| loose_square(&mut model, *f)).collect();
        let sewn = sew(&mut model, &built, T).unwrap();
        assert_eq!(sewn.joined, 12, "every edge pair merged");
        assert!(sewn.free_edges.is_empty());
        for face in ogeom_topo::explore(
            &model,
            &sewn.shells[0],
            ogeom_topo::Filter::OfType(ShapeType::Face),
        )
        .unwrap()
        {
            let mesh = ogeom_mesh::triangulate(&model, &face, fine(), T).unwrap();
            assert_eq!(
                mesh.triangles.len(),
                2,
                "a unit square triangulates into two triangles, whichever twin \
                 survived and whichever way it runs"
            );
        }
    }

    #[test]
    fn sewing_nothing_and_sewing_the_wrong_kind_are_refused() {
        let mut model = Model::new();
        assert!(sew(&mut model, &[], T).is_err());
        let vertex = model.add_point(Point::ORIGIN);
        assert!(sew(&mut model, &[vertex], T).is_err());
    }

    #[test]
    fn sewing_does_not_move_anything() {
        // A repair that closes gaps by moving geometry has to decide which of
        // two positions is right, and would invalidate every tolerance nearby.
        // This decides that two edges *are* one edge and leaves the points
        // where they were.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let faces = explore_unique(&model, &solid, ShapeType::Face).unwrap();
        let before: Vec<Point> = explore_unique(&model, &solid, ShapeType::Vertex)
            .unwrap()
            .iter()
            .map(|v| placed(&model, v).unwrap())
            .collect();

        let sewn = sew(&mut model, &faces, T).unwrap();
        let after: Vec<Point> = explore_unique(&model, &sewn.shells[0], ShapeType::Vertex)
            .unwrap()
            .iter()
            .map(|v| placed(&model, v).unwrap())
            .collect();
        assert_eq!(before.len(), after.len());
        for p in &after {
            assert!(
                before.iter().any(|q| q.is_equal(*p, T)),
                "a vertex moved: {p:?}"
            );
        }
        let _ = Vector::ZERO;
    }
}