ogeom_fillet/

corner.rs

//! Rounding a vertex: the ball-and-block tool at a planar corner.
//!
//! The ball's centre may sit anywhere a radius in from every host plane.
//! At a corner one ball touches, that region's tip is a point and the
//! rounded corner is one spherical patch; at a corner no single ball
//! touches, the tip is a few points joined by short ridges, and the
//! rounded corner is a sphere at each and a cylinder along each ridge:
//! the exact envelope of the rolling ball, where the setback family fits
//! a plate through the bands' ends instead.

use ogeom_algo::Built;
use ogeom_core::{OgeomError, OgeomResult, Tolerances, ogeom_bail};
use ogeom_math::{Direction, Frame, Point, Vector};
use ogeom_topo::{Model, Shape, ShapeType};

/// Round a solid's vertex with a ball of `radius`.
///
/// The corner block spanned by the edges, less the ball seated a radius in
/// from every host plane, is exactly the spike a rounded corner sheds, and
/// the general boolean does the shedding. The block's faces through the
/// ball's centre are square to the edges, so each edge's flush band ends
/// on the ball's rim: three sequential fillets at a box corner followed by
/// this call round the vertex the setback way. At a vertex of more edges
/// the corner goes first and the fillets follow (four bands built before
/// the corner crash into each other at a pyramid's apex) and the block is
/// the polyhedron of the N host planes and the N planes square to the
/// edges.
///
/// Where one ball touches every face, a band that another of the corner's
/// bands stopped short of the block is carried back to it first. Rounded
/// one at a time, an edge's band runs out past the vertex where the face
/// there leans out past its cap, and the band of an edge it crosses stops
/// flush against it, further out than the block reaches. Carried back,
/// that band too ends on the ball's rim, as every band does at a corner
/// where none ran out. A band stopped by anything else (a notch across its
/// crease) is left as it stands, and the crease before it stays sharp.
///
/// A vertex whose planes share no tangent ball (a rectangular pyramid's
/// apex, any general N-edged vertex) is rounded by the envelope of every
/// ball a radius in from all of them: a sphere at each vertex of the
/// region the ball's centre may occupy and a cylinder along each ridge
/// between two of them, each cut with its own compartment, the spheres
/// by the one-ball tool on their three planes and the ridges by the flush
/// fillet of a virtual crease. The compartments meet on the planes
/// square to the ridges, cap to cap.
///
/// A vertex where a curved face meets (fewer than three planes pass
/// through it) is rounded by the one ball touching the three surfaces that
/// do, wherever they curve: its centre walked to a radius in from each,
/// the compartment bounded by the three planes through the centre and two
/// touch points, clipped to the solid, less the ball.
///
/// What `solid` shares with other shapes is copied before it is
/// worked on ([`ogeom_algo::on_own_nodes`]), which leaves them as they are.
///
/// # Errors
///
/// [`OgeomError::Construction`] if the
/// vertex is not a vertex of the solid; if fewer than three planes pass
/// through it and other than three surfaces do, or the ball does not seat
/// inside every face; if the region the ball's centre may occupy has a tip vertex touching more than three planes
/// without one ball touching all of the corner's, or with other than three
/// edges leaving it; or if the corner turns out concave, where a ball adds
/// material instead of shedding it and a tool built from a cut cannot say
/// so. The corner may be oblique: the block is then the hexahedron bounded
/// by the host planes and the three planes through the ball's centre
/// square to the edges.
pub fn round_vertex(
    model: &mut Model,
    solid: &Shape,
    vertex: &Shape,
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Built> {
    ogeom_algo::on_own_nodes(
        model,
        solid,
        std::slice::from_ref(vertex),
        |model, solid, parts| round_vertex_own(model, solid, &parts[0], radius, tol),
    )
}

/// [`round_vertex`] on a shape every node below which is its own.
fn round_vertex_own(
    model: &mut Model,
    solid: &Shape,
    vertex: &Shape,
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Built> {
    round_vertex_with(model, solid, vertex, radius, None, tol)
}

/// [`round_vertex`], with the one-ball corner held to the labelling
/// `forced` names (by index, the ring's start then its direction) instead
/// of offered each in turn.
pub(crate) fn round_vertex_with(
    model: &mut Model,
    solid: &Shape,
    vertex: &Shape,
    radius: f64,
    forced: Option<usize>,
    tol: Tolerances,
) -> OgeomResult<Built> {
    match corner_at(model, solid, vertex, radius, tol)? {
        Corner::Curved(corner) => {
            crate::corner_curved::curved_corner(model, solid, vertex, corner, radius, tol)
        }
        Corner::Setback(corner, m) => setback_corner(model, solid, vertex, corner, &m, radius, tol),
        Corner::OneBall(one) => one_ball_corner(model, solid, vertex, &one, radius, forced, tol),
    }
}

/// The kind of corner a vertex of a solid is to a ball of some radius.
enum Corner {
    /// Fewer than three planes pass through the corner: a curved face
    /// meets there.
    Curved(Point),
    /// No one ball touches every plane through the corner, whose inward
    /// normals these are.
    Setback(Point, Vec<Vector>),
    /// One ball touches every plane through a convex corner.
    OneBall(OneBall),
}

/// A convex planar corner one ball touches every face of.
struct OneBall {
    /// The vertex where it stands.
    corner: Point,
    /// The ball's centre.
    far: Point,
    /// The inward normal of each plane through the corner.
    m: Vec<Vector>,
    /// The planes in their order round the vertex.
    ring: Vec<usize>,
    /// Edge `k`, from the vertex into the solid, where plane `ring[k]` and
    /// plane `ring[k + 1]` meet.
    d: Vec<Direction>,
    /// The points whose containment in the solid told the corner convex.
    probes: Vec<Point>,
}

impl OneBall {
    /// The box round the corner's block: the vertex, the foot of each edge
    /// on its plane through the ball's centre, the point where the ball
    /// touches each plane, and the centre.
    fn block_bounds(&self, radius: f64) -> ogeom_math::Aabb {
        let mut points = vec![self.corner, self.far];
        for (dk, mk) in self.d.iter().zip(&self.m) {
            points.push(self.foot(dk.vector()));
            points.push(self.far - *mk * radius);
        }
        ogeom_math::Aabb::of_points(&points)
    }

    /// Where the plane through the ball's centre square to `along` meets
    /// the edge leaving the vertex along it.
    fn foot(&self, along: Vector) -> Point {
        self.corner + along * (self.far - self.corner).dot(along)
    }
}

/// The corner `vertex` of `solid` is to a ball of `radius`, and every check
/// that the tool speaks it.
fn corner_at(
    model: &Model,
    solid: &Shape,
    vertex: &Shape,
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Corner> {
    if model.kind_of(vertex)? != ShapeType::Vertex {
        ogeom_bail!(Construction, "round_vertex rounds a vertex");
    }
    if radius <= tol.confusion() {
        ogeom_bail!(Construction, "a blend radius must be a positive distance");
    }
    let Some(raw) = model
        .node(vertex)
        .and_then(|n| n.data().as_vertex().map(|d| d.point))
    else {
        ogeom_bail!(Construction, "the vertex holds no point");
    };
    // Where the vertex stands, not where its node was built: a prism's far
    // end is its near end moved, and read unplaced the far corner is the
    // near one, so the tool would round the wrong corner of the solid.
    let corner = vertex.transform(model.datums())?.apply(raw);

    // The corner's frame comes from the planes that pass through the
    // vertex's point, not from the vertex's own adjacency, which the very
    // sequence this tool serves destroys: after three fillets the tip is
    // consumed, but the three shrunk planes still contain the corner, and
    // still say exactly which corner it was. The vertex argument may
    // therefore come from an earlier state of the solid (the sharp box's
    // corner captured before the fillets) and anchors the history. Each
    // plane's material side is read off its face, which the fillets shrink
    // but never turn over.
    let mut m: Vec<Vector> = Vec::new();
    for face in ogeom_topo::explore_unique(model, solid, ShapeType::Face)? {
        let Some(data) = model.node(&face).and_then(|n| n.data().as_face()) else {
            continue;
        };
        let Some(surface) = model.geometry().surface(data.surface) else {
            continue;
        };
        if !matches!(surface, ogeom_geom::SurfaceGeometry::Plane(_)) {
            continue;
        }
        let (origin, outward) = ogeom_algo::face_normal(model, &face, tol)?;
        if (corner - origin).dot(outward).abs() > tol.confusion() * 100.0 {
            continue;
        }
        // One vote per plane: coplanar trims share it.
        if m.iter()
            .any(|n| n.cross(outward).magnitude() < tol.angular() * 10.0)
        {
            continue;
        }
        m.push(-outward);
    }
    let n = m.len();
    if n < 3 {
        // A curved face meets here: the one-ball corner on whatever
        // surfaces pass through the vertex.
        return Ok(Corner::Curved(corner));
    }
    // The ball's centre: the point a radius in from every plane. Three
    // planes that span always hold one; more only when they share a
    // tangent ball, which the least-squares fit's residual tells: a
    // square pyramid's apex does, a general N-edged vertex does not, and
    // that vertex takes the general setback patch instead.
    let centre_for = |m: &[Vector]| -> Option<(Point, f64)> {
        // m_k · (c − corner) = radius over all k: solved directly for
        // three planes, through the normal equations for more. Three are
        // solved directly for the last bit, not for speed: the boolean's
        // paving at the touch points is sensitive to an ulp of the centre,
        // and an oblique corner closes on the direct solve's value.
        let mut a = [[0.0_f64; 3]; 3];
        let mut b = [0.0_f64; 3];
        if m.len() == 3 {
            for (i, mk) in m.iter().enumerate() {
                a[i] = [mk.x, mk.y, mk.z];
                b[i] = radius;
            }
        } else {
            for mk in m {
                let v = [mk.x, mk.y, mk.z];
                for i in 0..3 {
                    b[i] += radius * v[i];
                    for j in 0..3 {
                        a[i][j] += v[i] * v[j];
                    }
                }
            }
        }
        let det3 = |a: &[[f64; 3]; 3]| -> f64 {
            a[0][0].mul_add(
                a[1][1].mul_add(a[2][2], -(a[1][2] * a[2][1])),
                -a[0][1].mul_add(
                    a[1][0].mul_add(a[2][2], -(a[1][2] * a[2][0])),
                    -(a[0][2] * a[1][0].mul_add(a[2][1], -(a[1][1] * a[2][0]))),
                ),
            )
        };
        let det = det3(&a);
        if !det.is_finite() || det.abs() <= 1e-12 {
            return None;
        }
        let mut x = [0.0_f64; 3];
        for (k, xk) in x.iter_mut().enumerate() {
            let mut ak = a;
            for (row, bi) in ak.iter_mut().zip(b) {
                row[k] = bi;
            }
            *xk = det3(&ak) / det;
        }
        let centre = corner + Vector::new(x[0], x[1], x[2]);
        let residual = m
            .iter()
            .map(|mk| (mk.dot(centre - corner) - radius).abs())
            .fold(0.0, f64::max);
        Some((centre, residual))
    };
    let Some((far, residual)) = centre_for(&m) else {
        ogeom_bail!(
            Construction,
            "the {n} planes through this vertex do not span a corner"
        );
    };
    if residual > tol.confusion() * 10.0 {
        // No one ball touches every face: the rounded corner is the
        // envelope of every ball a radius in from all of them, which is
        // more than one sphere. Its pieces are read off the region the
        // ball's centre may occupy.
        return Ok(Corner::Setback(corner, m));
    }
    // A concave vertex puts the ball's centre outside the material: a ball
    // there adds material instead of shedding it, and a tool built from a
    // cut cannot say so.
    let boundary = ogeom_algo::SolidBoundary::of(model, solid, tol.confusion() * 1e4, tol)?;
    let mut probes = vec![far];
    if boundary.holds(model, far, tol)? != ogeom_algo::Containment::In {
        ogeom_bail!(
            Construction,
            "no material a radius in from every face at this vertex; a \
             concave vertex gains a ball instead of shedding one, and this \
             tool cannot round it"
        );
    }
    // The corner's edges: where two of the planes meet along a ray that
    // lies inside all the others, directed from the vertex into the solid.
    // A simple convex corner has one edge per plane, and the edges chain the
    // planes into a ring round the vertex.
    let mut edges: Vec<(usize, usize, Direction)> = Vec::new();
    for i in 0..n {
        for j in i + 1..n {
            let cross = m[i].cross(m[j]);
            let length = cross.magnitude();
            if length <= tol.angular() * 10.0 {
                continue;
            }
            for sign in [1.0, -1.0] {
                let d = cross * (sign / length);
                let inside = (0..n)
                    .filter(|&k| k != i && k != j)
                    .all(|k| m[k].dot(d) >= -tol.angular() * 10.0);
                if inside {
                    edges.push((i, j, Direction::new(d, tol)?));
                    break;
                }
            }
        }
    }
    if edges.len() != n {
        ogeom_bail!(
            Construction,
            "the {n} planes through this vertex meet along {} edges, not {n}; \
             the corner is not the simple convex one this tool speaks",
            edges.len()
        );
    }
    // The planes taken whole make any corner look convex, but a re-entrant
    // one (an L-bracket's step, where a concave edge meets two convex ones)
    // has material outside a plane beside one of its edges. At a convex
    // corner the solid lies within every plane near the vertex, however
    // much of it earlier blends have cut away, so a point just off one of
    // an edge's planes, and in from the other, is outside it.
    {
        let boundary = ogeom_algo::SolidBoundary::of(model, solid, tol.confusion() * 1e4, tol)?;
        let step = (radius * 1e-2).max(tol.confusion() * 1e3);
        for &(i, j, d) in &edges {
            for (k, other) in [(i, j), (j, i)] {
                let off = corner + (d.vector() - m[k] + m[other]) * step;
                probes.push(off);
                if boundary.holds(model, off, tol)? == ogeom_algo::Containment::In {
                    ogeom_bail!(
                        Construction,
                        "material stands outside a plane through this vertex beside \
                         one of its edges; the corner is re-entrant, not the simple \
                         convex one this tool speaks"
                    );
                }
            }
        }
    }
    let mut ring: Vec<usize> = vec![0];
    let mut last_edge: Option<usize> = None;
    loop {
        let here = *ring.last().unwrap_or(&0);
        let Some((e, other)) = edges.iter().enumerate().find_map(|(e, &(i, j, _))| {
            if Some(e) == last_edge {
                None
            } else if i == here {
                Some((e, j))
            } else if j == here {
                Some((e, i))
            } else {
                None
            }
        }) else {
            ogeom_bail!(
                Construction,
                "the planes through this vertex do not chain into a ring round it"
            );
        };
        last_edge = Some(e);
        if other == 0 {
            break;
        }
        if ring.contains(&other) || ring.len() >= n {
            ogeom_bail!(
                Construction,
                "the planes through this vertex do not chain into a ring round it"
            );
        }
        ring.push(other);
    }
    if ring.len() != n {
        ogeom_bail!(
            Construction,
            "the planes through this vertex do not chain into a ring round it"
        );
    }
    // Plane `ring[k]` and plane `ring[k+1]` meet along edge k.
    let d: Vec<Direction> = (0..n)
        .map(|k| {
            let (p, q) = (ring[k], ring[(k + 1) % n]);
            edges
                .iter()
                .find(|&&(i, j, _)| (i == p && j == q) || (i == q && j == p))
                .map(|&(_, _, dir)| dir)
        })
        .collect::<Option<_>>()
        .ok_or_else(|| {
            ogeom_core::ogeom_err!(Construction, "the corner's edges lost their ring")
        })?;
    Ok(Corner::OneBall(OneBall {
        corner,
        far,
        m,
        ring,
        d,
        probes,
    }))
}

/// A convex planar corner one ball touches every face of, read as
/// [`round_vertex`] reads it: the vertex's point, the ball's centre, each
/// plane's inward normal, the planes in their order round the vertex, and
/// edge `k`'s direction into the solid, where plane `ring[k]` meets plane
/// `ring[k + 1]`.
pub(crate) struct CornerFrame {
    pub corner: Point,
    pub far: Point,
    pub m: Vec<Vector>,
    pub ring: Vec<usize>,
    pub d: Vec<Direction>,
}

/// The frame of `vertex` of `solid` as a corner one ball of `radius`
/// touches every plane of, refused by name where it is another kind.
pub(crate) fn corner_frame(
    model: &Model,
    solid: &Shape,
    vertex: &Shape,
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<CornerFrame> {
    match corner_at(model, solid, vertex, radius, tol)? {
        Corner::OneBall(one) => Ok(CornerFrame {
            corner: one.corner,
            far: one.far,
            m: one.m,
            ring: one.ring,
            d: one.d,
        }),
        Corner::Curved(_) => ogeom_bail!(
            Construction,
            "a setback corner where a curved face meets the vertex is still \
             owed; see docs/CAPABILITIES.md, fillet.setback-corners"
        ),
        Corner::Setback(..) => ogeom_bail!(
            Construction,
            "a setback corner whose planes share no tangent ball is still \
             owed; see docs/CAPABILITIES.md, fillet.setback-corners"
        ),
    }
}

/// [`round_vertex_with`] at a corner one ball touches every face of.
fn one_ball_corner(
    model: &mut Model,
    solid: &Shape,
    vertex: &Shape,
    one: &OneBall,
    radius: f64,
    forced: Option<usize>,
    tol: Tolerances,
) -> OgeomResult<Built> {
    let OneBall {
        corner,
        far,
        ref m,
        ref ring,
        ref d,
        ..
    } = *one;
    let n = m.len();

    // A band left short of the block by another band's run-out is carried
    // back to it first, so the block's cut ends it as it ends a flush one.
    // The wedge carrying it starts at the vertex or on the block's plane:
    // the same material either way, which the boolean resolves in one or
    // the other. Where neither carries it the corner is cut as it stands.
    let carry = |model: &mut Model, from_vertex: bool| -> OgeomResult<Built> {
        let mut carried = Built::from_nothing(solid.clone());
        for k in 0..n {
            let planes = [m[ring[k]], m[ring[(k + 1) % n]]];
            if let Some(band) = band_gap(
                model,
                &carried.shape,
                corner,
                far,
                d,
                k,
                planes,
                radius,
                from_vertex,
                tol,
            )? {
                carried = Built {
                    shape: band.shape,
                    history: carried.history.then(&band.history),
                };
            }
        }
        Ok(carried)
    };

    // Which edge is first and which way the ring runs is the tool's
    // labelling ([`one_ball_tool`]), and the solid it builds is the same
    // for all 2N. The tool offers each labelling in turn and the first that
    // closes stands, so a corner no labelling closes is refused by name. A
    // failed attempt's nodes stay in the model unreferenced, under their
    // own operation.
    let attempt = |model: &mut Model, held: &Built, start: usize, reverse| -> OgeomResult<Built> {
        let tool = one_ball_tool(model, one, radius, start, reverse, tol)?;
        let rounded = ogeom_bool::cut(model, &held.shape, &tool.shape, tol)?;
        Ok(Built {
            shape: rounded.shape,
            history: held.history.then(&tool.history).then(&rounded.history),
        })
    };
    let mut outcome: Option<Built> = None;
    let mut last: Option<ogeom_core::OgeomError> = None;
    let mut tried: Vec<Shape> = Vec::new();
    'carries: for from_vertex in [Some(true), Some(false), None] {
        let carried = match from_vertex {
            Some(from_vertex) => match carry(model, from_vertex) {
                Ok(carried) => carried,
                Err(err @ (OgeomError::NotDone(_) | OgeomError::Construction(_))) => {
                    last = Some(err);
                    continue;
                }
                Err(err) => return Err(err),
            },
            None => Built::from_nothing(solid.clone()),
        };
        // A corner with no band to carry is cut once.
        if tried.iter().any(|held| held.is_same(&carried.shape)) {
            continue;
        }
        tried.push(carried.shape.clone());
        let labellings = (0..2 * n).map(|index| (index % n, index >= n));
        for (index, (start, reverse)) in labellings.enumerate() {
            if forced.is_some_and(|f| f != index) {
                continue;
            }
            match attempt(model, &carried, start, reverse) {
                Ok(built) => {
                    outcome = Some(built);
                    break 'carries;
                }
                Err(err) => last = Some(err),
            }
        }
    }
    let Some(rounded) = outcome else {
        ogeom_bail!(
            NotDone,
            "the corner tool's cut closed on none of the corner's {} \
             labellings; the last said: {}",
            2 * n,
            last.map_or_else(String::new, |e| e.to_string())
        );
    };
    let mut built = rounded;
    built.history.modify(vertex, built.shape.clone());
    Ok(built)
}

/// The corners at `vertices` of `solid` rounded in one cut, each as
/// [`round_vertex_with`] rounds it alone; `None` where that is not shown
/// to round them as rounding them one after another would, and the caller
/// rounds them so.
///
/// Every face of the solid must be planar, every corner one a single ball
/// touches every face of, and every corner's tool clear of every other
/// corner. With no curved face no band stands to be carried back to a
/// block. A tool lies within its block, and a corner whose block keeps a
/// margin from every other corner's leaves what that corner is read from
/// as it found it: the faces through its vertex keep their pieces round
/// it, the points its convexity was probed at stay as far inside or
/// outside, and no plane square to an edge of it passes through another
/// vertex to add a face there. A face of the solid on a plane through the
/// vertex that no face at the vertex lies on could be cut away whole; such
/// a corner is left to the caller. Each corner is then the same corner,
/// and its tool the same solid, before and after the others are cut, and
/// cutting the solid by every tool at once takes away the union of the
/// tools, as cutting by them in turn does. The margin is the chord the
/// convexity probes' classifier draws trims at, which also stands well
/// clear of the band in which a plane counts as passing through a vertex.
///
/// Cut in turn, a corner's patch meets the balls of the corners cut
/// before it, and a patch whose pole comes within the boolean's touching
/// distance of another ball is recharted, seams and all, which one cut of
/// a solid with no curved face never does. Every two balls therefore
/// stand further apart than that: no point of one comes that close to the
/// other.
///
/// The tool of each corner is built under the first labelling that builds
/// one; which labelling holds decides only the charts of the patch, as it
/// does when the corners are rounded in turn. Where the one cut does not
/// close, the tolerances it widened are put back.
pub(crate) fn round_vertices_together(
    model: &mut Model,
    solid: &Shape,
    vertices: &[Shape],
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Option<Built>> {
    let mark = model.note_widened();
    match vertices_together(model, solid, vertices, radius, tol) {
        Ok(Some(built)) => {
            model.keep_widened(mark);
            Ok(Some(built))
        }
        Err(OgeomError::Cancelled) => {
            model.keep_widened(mark);
            Err(OgeomError::Cancelled)
        }
        Ok(None) | Err(_) => {
            model.undo_widened(mark);
            Ok(None)
        }
    }
}

/// [`round_vertices_together`], before what a cut that does not close
/// widened is put back.
fn vertices_together(
    model: &mut Model,
    solid: &Shape,
    vertices: &[Shape],
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Option<Built>> {
    let margin = tol.confusion() * 1e4;
    let faces = ogeom_topo::explore_unique(model, solid, ShapeType::Face)?;
    let planar = |face: &Shape| {
        model
            .node(face)
            .and_then(|n| n.data().as_face())
            .is_some_and(|data| {
                matches!(
                    model.geometry().surface(data.surface),
                    Some(ogeom_geom::SurfaceGeometry::Plane(_))
                )
            })
    };
    if !faces.iter().all(planar) {
        return Ok(None);
    }
    let mut corners: Vec<OneBall> = Vec::with_capacity(vertices.len());
    for vertex in vertices {
        let Corner::OneBall(one) = corner_at(model, solid, vertex, radius, tol)? else {
            return Ok(None);
        };
        // Every plane through the vertex is one a face at the vertex lies on.
        let mut at_vertex: Vec<Vector> = Vec::new();
        for face in &faces {
            let holds = ogeom_topo::explore_unique(model, face, ShapeType::Vertex)?
                .iter()
                .any(|v| v.is_same(vertex));
            if holds {
                at_vertex.push(ogeom_algo::face_normal(model, face, tol)?.1);
            }
        }
        let held = one.m.iter().all(|mk| {
            at_vertex
                .iter()
                .any(|n| n.cross(*mk).magnitude() < tol.angular() * 10.0)
        });
        if !held {
            return Ok(None);
        }
        corners.push(one);
    }
    let bounds: Vec<ogeom_math::Aabb> = corners.iter().map(|c| c.block_bounds(radius)).collect();
    for (i, one) in corners.iter().enumerate() {
        for (j, other) in corners.iter().enumerate() {
            if i == j {
                continue;
            }
            let apart = one.far.distance(other.far) - radius * 2.0;
            let clear = apart > radius * ogeom_bool::POLE_TOUCHING + margin
                && bounds[i].distance_to_box(&bounds[j]) > margin
                && other
                    .probes
                    .iter()
                    .all(|p| bounds[i].distance_to(*p) > margin)
                && one.d.iter().all(|dk| {
                    let along = dk.vector();
                    (other.corner - one.foot(along)).dot(along).abs() > margin
                });
            if !clear {
                return Ok(None);
            }
        }
    }
    let mut tools = Vec::with_capacity(corners.len());
    let mut history = ogeom_algo::History::new();
    for one in &corners {
        let n = one.m.len();
        let tool = (0..2 * n).find_map(|index| {
            match one_ball_tool(model, one, radius, index % n, index >= n, tol) {
                Ok(tool) => Some(Ok(tool)),
                Err(OgeomError::Cancelled) => Some(Err(OgeomError::Cancelled)),
                Err(_) => None,
            }
        });
        let Some(tool) = tool.transpose()? else {
            return Ok(None);
        };
        history = history.then(&tool.history);
        tools.push(tool.shape);
    }
    let compound = model.add_compound(&tools)?;
    let rounded = ogeom_bool::cut(model, solid, &compound, tol)?;
    let mut history = history.then(&rounded.history);
    for vertex in vertices {
        history.modify(vertex, rounded.shape.clone());
    }
    Ok(Some(Built {
        shape: rounded.shape,
        history,
    }))
}

/// The tool that rounds a one-ball corner: its block less its ball, under
/// the labelling whose first edge is `start` and whose ring runs backwards
/// where `reverse`.
///
/// The block: the corner bounded by its N host planes and, through the
/// ball's centre, the N planes square to its edges, where each band's
/// circle and the ball's own rim coincide, so the cut ends the band and
/// starts the patch on one curve. On a square corner it is the box of
/// side `radius`; on an oblique one a hexahedron; at a pyramid's apex a
/// polyhedron of eight faces. Its corners: the vertex, the foot of each
/// edge on its cutting plane, on each host plane the point where the
/// ball touches it, and the centre itself.
///
/// The ball on the corner's axes: a pole at one corner of the patch it
/// leaves and its seam meridian out past the block through the first
/// edge: the pole axis is the inward normal of the host plane holding
/// the first two edges, the third edge itself on a square corner. The
/// charts the block's faces and the ball wear differ between labellings
/// (where a rim is exact and where fitted, where a seam falls against a
/// patch arc); the solid does not.
fn one_ball_tool(
    model: &mut Model,
    one: &OneBall,
    radius: f64,
    start: usize,
    reverse: bool,
    tol: Tolerances,
) -> OgeomResult<Built> {
    let OneBall {
        corner,
        far,
        ref m,
        ref ring,
        ref d,
        ..
    } = *one;
    let n = m.len();
    let inward_of = |k: usize| m[ring[k % n]];
    // Edge t of the labelling and the host plane holding edges t and t+1.
    let edge_at = |t: usize| -> usize {
        if reverse {
            (start + n - t % n) % n
        } else {
            (start + t) % n
        }
    };
    let dl: Vec<Direction> = (0..n).map(|t| d[edge_at(t)]).collect();
    let ml: Vec<Vector> = (0..n)
        .map(|t| {
            // Forward: edges t, t+1 are E_s+t, E_s+t+1, both on plane
            // ring[s+t+1]. Reverse: E_s−t, E_s−t−1, both on ring[s−t].
            if reverse {
                inward_of((start + n - t % n) % n)
            } else {
                inward_of(edge_at(t) + 1)
            }
        })
        .collect();
    let along = |t: usize| -> Point { one.foot(dl[t].vector()) };
    let touch = |t: usize| -> Point { far - ml[t] * radius };
    if std::env::var_os("OGEOM_DEBUG_CORNER").is_some() {
        eprintln!(
            "CORNER attempt start {start} reverse {reverse} far {far:?} d {:?} m {ml:?}",
            dl.iter().map(|x| x.vector()).collect::<Vec<_>>()
        );
    }
    model.begin_operation();
    let mut points: Vec<Point> = vec![corner];
    points.extend((0..n).map(along));
    points.extend((0..n).map(touch));
    points.push(far);
    let mut rings: Vec<Vec<usize>> = Vec::with_capacity(2 * n);
    for t in 0..n {
        // The host face on plane t: vertex, edge t's foot, the touch
        // point, edge t+1's foot.
        rings.push(vec![0, 1 + t, 1 + n + t, 1 + (t + 1) % n]);
        // The face square to edge t: its foot, the touch points either
        // side, the centre.
        rings.push(vec![1 + t, 1 + n + (t + n - 1) % n, 1 + 2 * n, 1 + n + t]);
    }
    let block = ogeom_algo::make_polyhedron(model, &points, &rings, tol)?.shape;
    let ball_frame = Frame::new(far, Direction::new(ml[0], tol)?, dl[0], tol)?;
    let ball = ogeom_algo::make_sphere(model, ball_frame, radius, tol)?.shape;
    let tool = ogeom_bool::cut(model, &block, &ball, tol)?;
    if std::env::var_os("OGEOM_DEBUG_CORNER").is_some() {
        let faces = ogeom_topo::explore_unique(model, &tool.shape, ShapeType::Face)?;
        let kinds: Vec<String> = faces
            .iter()
            .map(|f| {
                let kind = model
                    .node(f)
                    .and_then(|n| n.data().as_face())
                    .and_then(|d| model.geometry().surface(d.surface))
                    .map_or("?", |sg| match sg {
                        ogeom_geom::SurfaceGeometry::Plane(_) => "plane",
                        ogeom_geom::SurfaceGeometry::Sphere(_) => "sphere",
                        _ => "other",
                    });
                let edges =
                    ogeom_topo::explore_unique(model, f, ShapeType::Edge).map_or(0, |e| e.len());
                format!("{kind}/{edges}")
            })
            .collect();
        eprintln!(
            "CORNER tool for start {start} reverse {reverse}: {} faces {kinds:?}",
            faces.len()
        );
    }
    Ok(tool)
}

/// The band along edge `k` of a one-ball corner carried back to the
/// corner's block, where a band another edge of the corner ran out left it
/// short.
///
/// Edge `k`'s band is the cylinder of `radius` about the line through the
/// ball's centre `far` along the edge's direction, between the two host
/// planes with inward normals `planes`; the block ends it on the plane
/// through `far` square to the edge. Rounded one at a time, another edge's
/// band may run out past the vertex and across this edge's crease, and
/// this band then stands flush against that one, further out than the
/// block reaches. In the section square to the edge, the material outside
/// the cylinder and within the two host planes is what no ball a radius in
/// from both planes reaches, so the band's wedge is cut back to the block,
/// `from_vertex` starting it at the vertex rather than on the block's
/// plane: behind that plane the block's cut takes the stretch anyway.
///
/// Only that band is carried: its near end stands against the band of
/// another edge of the corner (the crease's point there lies on that
/// band's cylinder), and no stretch of the crease between the vertex and
/// the band is still a sharp edge of the solid. A band ending against
/// anything else (a notch across the crease, a piece of the crease nobody
/// rounded) is left as it stands. `None` where no band is carried.
#[allow(clippy::too_many_arguments, reason = "one question, all its data")]
fn band_gap(
    model: &mut Model,
    solid: &Shape,
    corner: Point,
    far: Point,
    axes: &[Direction],
    k: usize,
    planes: [Vector; 2],
    radius: f64,
    from_vertex: bool,
    tol: Tolerances,
) -> OgeomResult<Option<Built>> {
    let along = axes[k].vector();
    let on_line = tol.confusion() * 100.0;
    let point_of = |model: &Model, v: &Shape| -> OgeomResult<Option<Point>> {
        let Some(p) = model
            .node(v)
            .and_then(|n| n.data().as_vertex().map(|d| d.point))
        else {
            return Ok(None);
        };
        Ok(Some(v.transform(model.datums())?.apply(p)))
    };
    // Where the band starts along the edge, from the block's plane: the
    // nearest of its vertices.
    let mut ends: Vec<Point> = Vec::new();
    for face in ogeom_topo::explore_unique(model, solid, ShapeType::Face)? {
        if !on_band(model, &face, far, along, radius, tol) {
            continue;
        }
        for v in ogeom_topo::explore_unique(model, &face, ShapeType::Vertex)? {
            if let Some(p) = point_of(model, &v)? {
                ends.push(p);
            }
        }
    }
    let Some(start) = ends
        .iter()
        .map(|p| (*p - far).dot(along))
        .min_by(f64::total_cmp)
    else {
        return Ok(None);
    };
    if start <= tol.confusion() {
        return Ok(None);
    }
    // The band's near end stands against another edge's band of this
    // corner: where its section there meets the crease, a point on that
    // band's cylinder.
    let from = (corner - far).dot(along);
    let gap = |p: Point, axis: Vector| {
        let w = p - far;
        ((w - axis * w.dot(axis)).magnitude() - radius).abs()
    };
    let crease_end = corner + along * (start - from);
    if !axes
        .iter()
        .enumerate()
        .any(|(j, axis)| j != k && gap(crease_end, axis.vector()) <= on_line)
    {
        return Ok(None);
    }
    // No stretch of the crease between the vertex and the band is still a
    // sharp edge of the solid. The crease leaves the other band at its rail,
    // where the band is tangent to the host plane the crease lies in, so
    // the two stand apart only quadratically there and the boolean places
    // the crossing within its vertices' tolerances. A piece each of whose
    // ends lies on one other band's cylinder within the end's own
    // tolerance lies on it within those tolerances all along (a line's
    // distance from a cylinder it stays outside is convex along it): it is
    // that band's boundary, not a stretch of sharp crease.
    for edge in ogeom_topo::explore_unique(model, solid, ShapeType::Edge)? {
        let Some((a, b)) = ogeom_algo::edge_vertices(model, &edge)? else {
            continue;
        };
        let (Some(pa), Some(pb)) = (point_of(model, &a)?, point_of(model, &b)?) else {
            continue;
        };
        let crease = |p: Point| {
            let w = p - corner;
            (w - along * w.dot(along)).magnitude() <= on_line
        };
        if !crease(pa) || !crease(pb) {
            continue;
        }
        let reach = |v: &Shape| {
            model
                .node(v)
                .and_then(|n| n.data().as_vertex())
                .map_or(0.0, |d| d.tolerance.get())
        };
        let (reach_a, reach_b) = (reach(&a), reach(&b));
        let on_band_seam = axes.iter().enumerate().any(|(j, axis)| {
            j != k && gap(pa, axis.vector()) <= reach_a && gap(pb, axis.vector()) <= reach_b
        });
        if on_band_seam {
            continue;
        }
        let (ta, tb) = ((pa - far).dot(along), (pb - far).dot(along));
        if ta.max(tb) > from + on_line && ta.min(tb) < start - on_line {
            return Ok(None);
        }
    }
    let face_on = |model: &Model, inward: Vector| -> OgeomResult<Option<Shape>> {
        for face in ogeom_topo::explore_unique(model, solid, ShapeType::Face)? {
            let Some(data) = model.node(&face).and_then(|n| n.data().as_face()) else {
                continue;
            };
            if !matches!(
                model.geometry().surface(data.surface),
                Some(ogeom_geom::SurfaceGeometry::Plane(_))
            ) {
                continue;
            }
            let (origin, outward) = ogeom_algo::face_normal(model, &face, tol)?;
            if (corner - origin).dot(outward).abs() <= on_line
                && outward.cross(inward).magnitude() < tol.angular() * 10.0
                && outward.dot(inward) < 0.0
            {
                return Ok(Some(face));
            }
        }
        Ok(None)
    };
    let (Some(first), Some(second)) = (face_on(model, planes[0])?, face_on(model, planes[1])?)
    else {
        return Ok(None);
    };
    let foot = corner + along * (far - corner).dot(along);
    let seat = crate::support::Seat {
        start: if from_vertex { corner } else { foot },
        end: foot + along * start,
        along,
        normals: [-planes[0], -planes[1]],
        faces: [first, second],
        convex: true,
    };
    let cut = crate::fillet::seated_fillet(model, solid, &seat, radius, None, &[], tol)?;
    // The carried band and the band it reaches lie on one cylinder: one
    // face, as the band the corner closes in one call is.
    let on_axis: Vec<Shape> = ogeom_topo::explore_unique(model, &cut.shape, ShapeType::Face)?
        .into_iter()
        .filter(|face| on_band(model, face, far, along, radius, tol))
        .collect();
    let (unified, _) = ogeom_heal::unify_same_domain_around(model, &cut.shape, &on_axis, tol)?;
    Ok(Some(Built {
        shape: unified.shape,
        history: cut.history.then(&unified.history),
    }))
}

/// Whether `face` lies on the cylinder of `radius` about the line through
/// `far` along `along`.
fn on_band(
    model: &Model,
    face: &Shape,
    far: Point,
    along: Vector,
    radius: f64,
    tol: Tolerances,
) -> bool {
    let Some(data) = model.node(face).and_then(|n| n.data().as_face()) else {
        return false;
    };
    let Some(ogeom_geom::SurfaceGeometry::Cylinder(c)) = model.geometry().surface(data.surface)
    else {
        return false;
    };
    let frame = c.cylinder().frame();
    let axis = frame.z().vector();
    let off = far - frame.origin();
    (c.cylinder().radius() - radius).abs() <= tol.confusion()
        && axis.cross(along).magnitude() <= tol.angular()
        && (off - axis * off.dot(axis)).magnitude() <= tol.confusion()
}

/// A vertex of the region the ball's centre may occupy: a point a radius
/// in from three or more of the host planes and at least a radius from the
/// rest, with the planes it touches.
struct TipVertex {
    centre: Point,
    planes: Vec<usize>,
}

/// An edge of that region's tip between two of its vertices: the ball
/// rolling from one to the other touches two planes all the way, and
/// sweeps a cylinder.
struct Ridge {
    from: usize,
    to: usize,
    planes: [usize; 2],
}

/// Round a convex planar vertex whose faces no single ball touches.
///
/// The ball's centre may sit anywhere a radius in from every host plane:
/// a convex region whose tip, at a vertex one ball touches, is a single
/// point, and otherwise a few points joined by short edges: a rectangular
/// pyramid's apex has two, joined along the two long slopes. The rounded
/// corner is the envelope of every ball centred in that region: a sphere
/// at each tip vertex, a cylinder along each edge between them, and the
/// host planes themselves elsewhere. Exact, constant-radius, and what the
/// rolling ball leaves, where a plate would be fitted through the bands'
/// ends instead.
///
/// Each piece is cut with its own block: at a tip vertex, the corner
/// bounded by its three planes and the three planes through the centre
/// square to its edges, less the ball (the one-ball tool exactly) and
/// along an edge between two centres, the prism over the kite of the
/// virtual crease, the two touch points and the centre, between the two
/// planes square to the edge, less the cylinder. The compartments tile
/// the corner and meet on the planes square to the edges, where each
/// sphere's rim and the cylinder's end coincide, so the cuts consume one
/// another's flush faces cap to cap. An original edge leaves its tip
/// vertex along a ray, and the plane square to it there is where the
/// edge's band ends when the flush fillets follow.
fn setback_corner(
    model: &mut Model,
    solid: &Shape,
    vertex: &Shape,
    corner: Point,
    m: &[Vector],
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Built> {
    let n = m.len();
    let slack = tol.confusion() * 10.0;
    // The tip's vertices: every triple that meets at a point a radius in
    // from all the planes, merged where several triples name one point.
    let mut tips: Vec<TipVertex> = Vec::new();
    for i in 0..n {
        for j in i + 1..n {
            for k in j + 1..n {
                let Some(centre) = ball_centre(corner, &[m[i], m[j], m[k]], radius) else {
                    continue;
                };
                let feasible = m.iter().all(|mk| mk.dot(centre - corner) >= radius - slack);
                if !feasible {
                    continue;
                }
                if tips.iter().any(|t| t.centre.distance(centre) <= slack) {
                    continue;
                }
                let planes: Vec<usize> = (0..n)
                    .filter(|&l| (m[l].dot(centre - corner) - radius).abs() <= slack)
                    .collect();
                tips.push(TipVertex { centre, planes });
            }
        }
    }
    if std::env::var_os("OGEOM_DEBUG_CORNER").is_some() {
        for tip in &tips {
            eprintln!("TIP {:?} planes {:?}", tip.centre, tip.planes);
        }
    }
    if tips.is_empty() {
        ogeom_bail!(
            Construction,
            "the {n} planes through this vertex hold no ball a radius in from \
             all of them"
        );
    }
    // Each tip vertex's edges: along every pair of its planes, the way the
    // rest of its planes allow; bounded where another plane becomes
    // tangent (a ridge to the tip vertex there) and a ray otherwise, the
    // way an original edge's band runs. A ray that lies along no original
    // edge, or a vertex with other than three edges, is a corner this tool
    // does not speak.
    let mut ridges: Vec<Ridge> = Vec::new();
    let mut rays: Vec<Vec<(Vector, [usize; 2])>> = vec![Vec::new(); tips.len()];
    for (index, tip) in tips.iter().enumerate() {
        for (a, b) in tip
            .planes
            .iter()
            .flat_map(|&a| tip.planes.iter().map(move |&b| (a, b)))
        {
            if a >= b {
                continue;
            }
            let cross = m[a].cross(m[b]);
            let length = cross.magnitude();
            if length <= tol.angular() * 10.0 {
                continue;
            }
            let Some(direction) = [1.0, -1.0]
                .into_iter()
                .map(|sign| cross * (sign / length))
                .find(|d| {
                    tip.planes
                        .iter()
                        .filter(|&&l| l != a && l != b)
                        .all(|&l| m[l].dot(*d) >= -tol.angular() * 10.0)
                })
            else {
                continue;
            };
            // The first other plane the ball meets rolling this way.
            let mut nearest: Option<(f64, usize)> = None;
            for (l, ml) in m.iter().enumerate() {
                if tip.planes.contains(&l) {
                    continue;
                }
                let rate = ml.dot(direction);
                if rate >= -tol.angular() {
                    continue;
                }
                let t = (radius - ml.dot(tip.centre - corner)) / rate;
                if t > slack && nearest.is_none_or(|(held, _)| t < held) {
                    nearest = Some((t, l));
                }
            }
            match nearest {
                Some((t, _)) => {
                    let end = tip.centre + direction * t;
                    let Some(to) = tips.iter().position(|o| o.centre.distance(end) <= slack) else {
                        ogeom_bail!(
                            Construction,
                            "the ball rolling between two of this vertex's faces meets a \
                             third where no tip vertex stands"
                        );
                    };
                    if index < to {
                        ridges.push(Ridge {
                            from: index,
                            to,
                            planes: [a, b],
                        });
                    }
                }
                None => rays[index].push((direction, [a, b])),
            }
        }
    }
    let concave = {
        let boundary = ogeom_algo::SolidBoundary::of(model, solid, tol.confusion() * 1e4, tol)?;
        let mut concave = false;
        for tip in &tips {
            if boundary.holds(model, tip.centre, tol)? != ogeom_algo::Containment::In {
                concave = true;
            }
        }
        concave
    };
    if concave {
        ogeom_bail!(
            Construction,
            "no material a radius in from every face at this vertex; a \
             concave vertex gains a ball instead of shedding one, and this \
             tool cannot round it"
        );
    }

    model.begin_operation();
    let mut rounded = solid.clone();
    let mut history = ogeom_algo::History::new();
    // The sphere at each tip vertex, with its own compartment: the wedge of
    // its planes, cut by the plane square to each of its edges through the
    // centre. A ridge's plane faces the corner, and the corner itself lies
    // in the ridge's compartment, not this one.
    for (index, tip) in tips.iter().enumerate() {
        // The vertex's edges, each on two of its planes: its rays and the
        // ridges that start or end here.
        let mut edges: Vec<(Vector, [usize; 2])> = rays[index].clone();
        for ridge in &ridges {
            let other = if ridge.from == index {
                ridge.to
            } else if ridge.to == index {
                ridge.from
            } else {
                continue;
            };
            let direction = (tips[other].centre - tip.centre).normalized(tol)?;
            edges.push((direction, ridge.planes));
        }
        let k = tip.planes.len();
        if edges.len() != k {
            ogeom_bail!(
                Construction,
                "a tip vertex of this corner touches {k} planes along {} edges, not \
                 {k}; the corner is not the simple convex one this tool speaks",
                edges.len()
            );
        }
        // In ring order, consecutive edges sharing a plane, so that host t
        // holds edges t and t+1: the labelling the ball's frame is read
        // off, its pole along a host and its seam out through an edge.
        let shared = |x: &[usize; 2], y: &[usize; 2]| -> Option<usize> {
            x.iter().copied().find(|p| y.contains(p))
        };
        let mut ring: Vec<(Vector, [usize; 2])> = vec![edges[0]];
        let mut used = vec![false; k];
        used[0] = true;
        while ring.len() < k {
            let last = ring[ring.len() - 1];
            let Some(next) = (0..k).find(|&i| {
                !used[i]
                    && shared(&edges[i].1, &last.1).is_some_and(|p| {
                        // The plane shared with the previous edge is not
                        // the one shared with the edge before that.
                        ring.len() < 2 || shared(&ring[ring.len() - 2].1, &last.1) != Some(p)
                    })
            }) else {
                ogeom_bail!(Construction, "the tip vertex's edges do not chain")
            };
            used[next] = true;
            ring.push(edges[next]);
        }
        let hosts: Vec<Vector> = (0..k)
            .map(|t| {
                shared(&ring[t].1, &ring[(t + 1) % k].1)
                    .map(|p| m[p])
                    .ok_or_else(|| {
                        ogeom_core::ogeom_err!(Construction, "the tip vertex's edges do not chain")
                    })
            })
            .collect::<OgeomResult<_>>()?;
        let directions: Vec<Vector> = ring.iter().map(|(d, _)| *d).collect();
        // Whether edge t is a ridge, whose rim plane a later cut's cap
        // stands in: a pole along a plane holding a ridge would put both
        // poles in that cap, and the cap's circle would have no chart
        // image. Labellings whose pole host holds no ridge go first.
        let is_ridge: Vec<bool> = ring
            .iter()
            .map(|(d, _)| !rays[index].iter().any(|(r, _)| r.dot(*d) > 1.0 - 1e-9))
            .collect();
        let mut walls: Vec<(Vector, Point)> = tip.planes.iter().map(|&p| (m[p], corner)).collect();
        for direction in &directions {
            walls.push((-*direction, tip.centre));
        }
        let tool = ball_block(
            model,
            &walls,
            corner,
            tip.centre,
            &hosts,
            &directions,
            &is_ridge,
            radius,
            tol,
        )?;
        let cut = ogeom_bool::cut(model, &rounded, &tool.shape, tol).map_err(|e| {
            ogeom_core::ogeom_err!(
                NotDone,
                "the cut by the ball's block at tip vertex {index} failed: {e}"
            )
        })?;
        history = history.then(&tool.history).then(&cut.history);
        rounded = cut.shape;
    }
    // The cylinder along each ridge: the flush fillet of a virtual crease (
    // the line the two planes it touches would meet along) between the
    // planes square to the ridge through its two centres, which are the
    // caps' own planes. The planar fillet builds that wedge face by face,
    // band, legs and caps, and melts it; the caps meet the spheres' rims
    // on the planes the vertex compartments already cut.
    for ridge in &ridges {
        let (v1, v2) = (tips[ridge.from].centre, tips[ridge.to].centre);
        let along = (v2 - v1).normalized(tol)?;
        let [a, c] = ridge.planes;
        let on_crease = |v: Point| corner + along * (v - corner).dot(along);
        let face_on = |model: &Model, inward: Vector| -> OgeomResult<Shape> {
            for face in ogeom_topo::explore_unique(model, &rounded, ShapeType::Face)? {
                let Some(data) = model.node(&face).and_then(|n| n.data().as_face()) else {
                    continue;
                };
                if !matches!(
                    model.geometry().surface(data.surface),
                    Some(ogeom_geom::SurfaceGeometry::Plane(_))
                ) {
                    continue;
                }
                let (origin, outward) = ogeom_algo::face_normal(model, &face, tol)?;
                if (corner - origin).dot(outward).abs() <= tol.confusion() * 100.0
                    && outward.cross(inward).magnitude() < tol.angular() * 10.0
                    && outward.dot(inward) < 0.0
                {
                    return Ok(face);
                }
            }
            ogeom_bail!(
                Construction,
                "the ridge's host plane is no longer a face of the solid"
            )
        };
        let faces = [face_on(model, m[a])?, face_on(model, m[c])?];
        let seat = crate::support::Seat {
            start: on_crease(v1),
            end: on_crease(v2),
            along,
            normals: [-m[a], -m[c]],
            faces,
            convex: true,
        };
        let cut = crate::fillet::seated_fillet(model, &rounded, &seat, radius, None, &[], tol)
            .map_err(|e| ogeom_core::ogeom_err!(NotDone, "the ridge's flush fillet failed: {e}"))?;
        history = history.then(&cut.history);
        rounded = cut.shape;
    }
    history.modify(vertex, rounded.clone());
    Ok(Built {
        shape: rounded,
        history,
    })
}

/// A convex polytope from the half-spaces that bound it, each given by
/// its inward normal and a point on its plane.
///
/// Its corners are the feasible meetings of three planes; each plane's
/// face is those of its corners that lie on it, walked round the face's
/// centroid. The polyhedron builder checks what this hands it (planarity,
/// every edge shared by two faces) so a set of half-spaces that bounds
/// nothing, or bounds a sliver, is refused rather than built.
pub(crate) fn convex_block(
    model: &mut Model,
    walls: &[(Vector, Point)],
    tol: Tolerances,
) -> OgeomResult<Shape> {
    let slack = tol.confusion() * 100.0;
    let n = walls.len();
    let mut points: Vec<Point> = Vec::new();
    for i in 0..n {
        for j in i + 1..n {
            for k in j + 1..n {
                let Some(p) = planes_meet(&walls[i], &walls[j], &walls[k]) else {
                    continue;
                };
                if walls
                    .iter()
                    .any(|(normal, on)| normal.dot(p - *on) < -slack)
                {
                    continue;
                }
                if points.iter().any(|q| q.distance(p) <= slack) {
                    continue;
                }
                points.push(p);
            }
        }
    }
    let mut rings: Vec<Vec<usize>> = Vec::new();
    for (normal, on) in walls {
        let mine: Vec<usize> = (0..points.len())
            .filter(|&i| normal.dot(points[i] - *on).abs() <= slack)
            .collect();
        if mine.len() < 3 {
            continue;
        }
        let centroid = mine
            .iter()
            .fold(Vector::ZERO, |acc, &i| acc + (points[i] - Point::ORIGIN))
            * (1.0 / f64::from(u32::try_from(mine.len()).unwrap_or(u32::MAX)));
        let centroid = Point::ORIGIN + centroid;
        let axis = normal.normalized(tol)?;
        let first = (points[mine[0]] - centroid).normalized(tol)?;
        let second = axis.cross(first);
        let mut ordered: Vec<(f64, usize)> = mine
            .iter()
            .map(|&i| {
                let v = points[i] - centroid;
                (v.dot(second).atan2(v.dot(first)), i)
            })
            .collect();
        ordered.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(core::cmp::Ordering::Equal));
        rings.push(ordered.into_iter().map(|(_, i)| i).collect());
    }
    Ok(ogeom_algo::make_polyhedron(model, &points, &rings, tol)?.shape)
}

/// Where three planes meet, or `None` where they do not span.
pub(crate) fn planes_meet(
    a: &(Vector, Point),
    b: &(Vector, Point),
    c: &(Vector, Point),
) -> Option<Point> {
    let m = [a.0, b.0, c.0];
    let rhs = [
        a.0.dot(a.1 - Point::ORIGIN),
        b.0.dot(b.1 - Point::ORIGIN),
        c.0.dot(c.1 - Point::ORIGIN),
    ];
    let x = solve3(&m, rhs)?;
    Some(Point::ORIGIN + x)
}

/// `m_k · x = rhs_k` for three rows, or `None` where they do not span.
fn solve3(m: &[Vector; 3], rhs: [f64; 3]) -> Option<Vector> {
    let a: [[f64; 3]; 3] = std::array::from_fn(|i| [m[i].x, m[i].y, m[i].z]);
    let det3 = |a: &[[f64; 3]; 3]| -> f64 {
        a[0][0].mul_add(
            a[1][1].mul_add(a[2][2], -(a[1][2] * a[2][1])),
            -a[0][1].mul_add(
                a[1][0].mul_add(a[2][2], -(a[1][2] * a[2][0])),
                -(a[0][2] * a[1][0].mul_add(a[2][1], -(a[1][1] * a[2][0]))),
            ),
        )
    };
    let det = det3(&a);
    if !det.is_finite() || det.abs() <= 1e-12 {
        return None;
    }
    let mut x = [0.0_f64; 3];
    for (k, xk) in x.iter_mut().enumerate() {
        let mut ak = a;
        for (row, r) in ak.iter_mut().zip(rhs) {
            row[k] = r;
        }
        *xk = det3(&ak) / det;
    }
    Some(Vector::new(x[0], x[1], x[2]))
}

/// The point a radius in from three planes through `corner`, or `None`
/// where they do not span.
fn ball_centre(corner: Point, m: &[Vector; 3], radius: f64) -> Option<Point> {
    solve3(m, [radius; 3]).map(|x| corner + x)
}

/// A compartment less the ball centred in it: the block from its walls,
/// cut by the sphere at `far`.
///
/// Host `t` holds edges `t` and `t + 1`. The ball's pole stands along a
/// host's normal and its seam meridian runs out through the first of that
/// host's edges (in a rim plane, so the seam doubles as a trim rather
/// than crossing a patch) and every labelling is offered in turn, the
/// first that closes standing. A cut that closes on a tool reaching past
/// its own block is a wrong tool, not a closed one, and is passed over
/// too.
#[allow(clippy::too_many_arguments, reason = "one construction, all its data")]
fn ball_block(
    model: &mut Model,
    walls: &[(Vector, Point)],
    corner: Point,
    far: Point,
    hosts: &[Vector],
    directions: &[Vector],
    is_ridge: &[bool],
    radius: f64,
    tol: Tolerances,
) -> OgeomResult<Built> {
    let n = directions.len();
    let mut last: Option<ogeom_core::OgeomError> = None;
    // The ball's frames, best first. Along a ridge, the ridge's rim plane
    // is the sphere's equator, both poles stand outside the patch (the
    // patch lies on the corner's side of every rim plane, the poles on
    // the ridge's own axis either side of it) and a seam meridian turned
    // away from the corner never crosses it; the ridge fillet's cap, in
    // that same rim plane, then meets the sphere on a circle the chart
    // images exactly. Then the classic labellings: the pole along host t,
    // the seam out through edge t, hosts holding no ridge first.
    // The patch's corners are the touch points, a radius from the centre
    // against each host; a frame is judged by how far its seam meridian
    // keeps from every corner in longitude about the pole, and a pole the
    // patch itself contains (inside every rim plane's kept side) is no
    // frame at all, since a chart's degenerate point cannot stand inside
    // a face. Either sense of every ridge is offered, with the seam turned
    // from the corner or from the corners' mean, the clearest first.
    let touches: Vec<Vector> = hosts.iter().map(|m| -*m).collect();
    let inside_patch = |direction: Vector| -> bool {
        directions
            .iter()
            .all(|e| e.dot(direction) <= tol.angular() * 10.0)
    };
    let mut scored: Vec<(f64, Vector, Vector)> = Vec::new();
    for t in 0..n {
        if !is_ridge[t] {
            continue;
        }
        for pole in [directions[t], -directions[t]] {
            if inside_patch(pole) || inside_patch(-pole) {
                continue;
            }
            let flat = |v: Vector| v - pole * v.dot(pole);
            let mean = touches.iter().fold(Vector::ZERO, |acc, t| acc + *t);
            for seam in [flat(-mean), flat(far - corner)] {
                if seam.magnitude() <= tol.angular() * 10.0 {
                    continue;
                }
                let x = seam / seam.magnitude();
                let y = pole.cross(x);
                let clearance = touches
                    .iter()
                    .map(|t| t.dot(y).atan2(t.dot(x)).abs())
                    .fold(f64::INFINITY, f64::min);
                scored.push((clearance, pole, seam));
            }
        }
    }
    scored.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap_or(core::cmp::Ordering::Equal));
    if std::env::var_os("OGEOM_DEBUG_CORNER").is_some() {
        for (clearance, pole, seam) in &scored {
            eprintln!("FRAME clearance {clearance:.3} pole {pole:?} seam {seam:?}");
        }
    }
    let mut frames: Vec<(Vector, Vector)> = scored.into_iter().map(|(_, p, s)| (p, s)).collect();
    // Host t holds edges t and t+1; a labelling's pole host is `start`
    // forward and `start − 1` reversed.
    let pole_host = |index: usize| -> usize {
        let (start, reverse) = (index % n, index >= n);
        if reverse {
            (start + 2 * n - 1) % n
        } else {
            start
        }
    };
    let clean = |index: usize| -> bool {
        let h = pole_host(index);
        !is_ridge[h] && !is_ridge[(h + 1) % n]
    };
    let mut order: Vec<usize> = (0..2 * n).collect();
    order.sort_by_key(|&index| !clean(index));
    frames.extend(
        order
            .iter()
            .map(|&index| (hosts[pole_host(index)], directions[index % n])),
    );
    for (index, (pole, seam)) in frames.into_iter().enumerate() {
        model.begin_operation();
        let attempt = (|| -> OgeomResult<Built> {
            let block = convex_block(model, walls, tol)?;
            let block_bound = ogeom_algo::shape_bounds(model, &block, tol)?;
            let ball_frame = Frame::new(
                far,
                Direction::new(pole, tol)?,
                Direction::new(seam, tol)?,
                tol,
            )?;
            let ball = ogeom_algo::make_sphere(model, ball_frame, radius, tol)?.shape;
            let tool = ogeom_bool::cut(model, &block, &ball, tol)?;
            let tool_bound = ogeom_algo::shape_bounds(model, &tool.shape, tol)?;
            let reach = tol.confusion() * 1e3;
            let (Some(block_lo), Some(block_hi), Some(tool_lo), Some(tool_hi)) = (
                block_bound.low(),
                block_bound.high(),
                tool_bound.low(),
                tool_bound.high(),
            ) else {
                ogeom_bail!(NotDone, "the ball's cut left no tool");
            };
            if tool_lo.x < block_lo.x - reach
                || tool_lo.y < block_lo.y - reach
                || tool_lo.z < block_lo.z - reach
                || tool_hi.x > block_hi.x + reach
                || tool_hi.y > block_hi.y + reach
                || tool_hi.z > block_hi.z + reach
            {
                ogeom_bail!(
                    NotDone,
                    "the ball's cut left a tool reaching past its own block"
                );
            }
            Ok(tool)
        })();
        match attempt {
            Ok(tool) => {
                if std::env::var_os("OGEOM_DEBUG_CORNER").is_some() {
                    eprintln!("BALL frame {index} closed");
                }
                return Ok(tool);
            }
            Err(err) => {
                if std::env::var_os("OGEOM_DEBUG_CORNER").is_some() {
                    eprintln!("BALL frame {index} pole {pole:?} seam {seam:?}: {err}");
                }
                last = Some(err);
            }
        }
    }
    ogeom_bail!(
        NotDone,
        "the corner tool's block closed on none of its {} frames; the last said: {}",
        2 * n,
        last.map_or_else(String::new, |e| e.to_string())
    )
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used, reason = "test code")]
    use super::{round_vertex_with, round_vertices_together};
    use ogeom_core::Tolerances;
    use ogeom_math::{Point, Vector};
    use ogeom_topo::{Model, Shape, ShapeType};

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

    fn vertex_at(model: &Model, shape: &Shape, at: Point) -> Shape {
        ogeom_topo::explore_unique(model, shape, ShapeType::Vertex)
            .unwrap()
            .into_iter()
            .find(|v| {
                model
                    .node(v)
                    .and_then(|n| n.data().as_vertex())
                    .is_some_and(|d| d.point.distance(at) < 1e-9)
            })
            .unwrap()
    }

    fn volume(model: &Model, shape: &Shape) -> f64 {
        ogeom_algo::volume_properties(model, shape, ogeom_mesh::Deflection::default(), T)
            .unwrap()
            .mass
    }

    /// Every labelling of a corner closes in the cut and builds one solid:
    /// the charts differ, the construction does not.
    fn every_labelling_agrees(model: &mut Model, solid: &Shape, vertex: &Shape, count: usize) {
        let mut volumes = Vec::with_capacity(count);
        for index in 0..count {
            let rounded = round_vertex_with(model, solid, vertex, 2.0, Some(index), T)
                .unwrap_or_else(|e| panic!("labelling {index} did not close: {e}"));
            let diagnosis = ogeom_algo::check(model, &rounded.shape, T).unwrap();
            assert!(
                diagnosis.is_valid(),
                "labelling {index}: {:?}",
                diagnosis.problems
            );
            volumes.push(volume(model, &rounded.shape));
        }
        // A labelling decides where a rim is exact and where fitted, and a
        // rim fitted to a tenth of a micron moves a few square millimetres
        // of patch by a few millionths of a cubic millimetre: one part in
        // ten million of these solids covers it.
        for (index, v) in volumes.iter().enumerate() {
            assert!(
                (v - volumes[0]).abs() < 1e-7 * volumes[0],
                "labelling {index} builds {v}, labelling 0 {}",
                volumes[0]
            );
        }
    }

    /// The box's eight corners and the solid each rounds to, the corners
    /// rounded one after another.
    fn box_corners_in_turn(model: &mut Model, radius: f64) -> (Shape, Vec<Shape>, Shape) {
        let solid = ogeom_algo::make_box(model, ogeom_math::Frame::WORLD, (10.0, 10.0, 10.0), T)
            .unwrap()
            .shape;
        let vertices = ogeom_topo::explore_unique(model, &solid, ShapeType::Vertex).unwrap();
        let mut rounded = solid.clone();
        for vertex in &vertices {
            rounded = round_vertex_with(model, &rounded, vertex, radius, None, T)
                .unwrap()
                .shape;
        }
        (solid, vertices, rounded)
    }

    fn counts(model: &Model, shape: &Shape) -> [usize; 3] {
        [ShapeType::Face, ShapeType::Edge, ShapeType::Vertex].map(|kind| {
            ogeom_topo::explore_unique(model, shape, kind)
                .unwrap()
                .len()
        })
    }

    /// Corners whose tools and balls stand clear of each other are cut in
    /// one boolean, which gathers fewer faces than cutting them in turn and
    /// builds the same solid.
    #[test]
    fn corners_clear_of_each_other_round_in_one_cut_as_in_turn() {
        for radius in [1.0, 2.0] {
            let mut model = Model::new();
            let ((solid, vertices, in_turn), one_by_one) =
                ogeom_bool::work::counted(|| box_corners_in_turn(&mut model, radius));
            let (together, at_once) = ogeom_bool::work::counted(|| {
                round_vertices_together(&mut model, &solid, &vertices, radius, T).unwrap()
            });
            let together = together.unwrap();
            assert!(
                ogeom_algo::check(&model, &together.shape, T)
                    .unwrap()
                    .is_valid()
            );
            let (want, got) = (volume(&model, &in_turn), volume(&model, &together.shape));
            assert!(
                (got - want).abs() <= want * 1e-9,
                "r {radius}: {got} against {want}"
            );
            assert_eq!(counts(&model, &together.shape), counts(&model, &in_turn));
            assert!(
                at_once.faces_gathered < one_by_one.faces_gathered,
                "r {radius}: {at_once:?} at once against {one_by_one:?} in turn"
            );
            for vertex in &vertices {
                assert_eq!(
                    together.history.modified(vertex),
                    core::slice::from_ref(&together.shape)
                );
            }
        }
    }

    /// Balls within the boolean's touching distance of each other are left
    /// to be cut in turn: there a patch cut later is recharted against the
    /// ball of one cut before it, which one cut never does.
    #[test]
    fn corners_whose_balls_come_close_round_in_turn() {
        let mut model = Model::new();
        let solid =
            ogeom_algo::make_box(&mut model, ogeom_math::Frame::WORLD, (10.0, 10.0, 10.0), T)
                .unwrap()
                .shape;
        let vertices = ogeom_topo::explore_unique(&model, &solid, ShapeType::Vertex).unwrap();
        let together = round_vertices_together(&mut model, &solid, &vertices, 4.9, T).unwrap();
        assert!(together.is_none());
    }

    #[test]
    fn an_oblique_corner_rounds_the_same_under_every_labelling() {
        let mut model = Model::new();
        let (a, b, c) = (
            Vector::new(20.0, 0.0, 0.0),
            Vector::new(6.0, 20.0, 0.0),
            Vector::new(3.6, 6.0, 20.0),
        );
        let block = ogeom_algo::make_parallelepiped(&mut model, Point::ORIGIN, [a, b, c], T)
            .unwrap()
            .shape;
        let vertex = vertex_at(&model, &block, Point::ORIGIN);
        every_labelling_agrees(&mut model, &block, &vertex, 6);
    }

    #[test]
    fn a_square_pyramid_apex_rounds_the_same_under_every_labelling() {
        let mut model = Model::new();
        let apex = Point::new(0.0, 0.0, 15.0);
        let base = [
            Point::new(-10.0, -10.0, 0.0),
            Point::new(10.0, -10.0, 0.0),
            Point::new(10.0, 10.0, 0.0),
            Point::new(-10.0, 10.0, 0.0),
        ];
        // Four slopes and the base, each wound about its outward normal.
        let mut faces = Vec::new();
        for k in 0..4 {
            let (p, q) = (base[k], base[(k + 1) % 4]);
            let outward = (q - p).cross(apex - p);
            faces.push(crate::support::planar_face(&mut model, &[p, q, apex], outward, T).unwrap());
        }
        let reversed: Vec<Point> = base.iter().rev().copied().collect();
        faces.push(crate::support::planar_face(&mut model, &reversed, -Vector::Z, T).unwrap());
        let sewn = ogeom_algo::sew(&mut model, &faces, T).unwrap();
        let pyramid = ogeom_algo::make_solid(&mut model, &sewn.shells[..1])
            .unwrap()
            .shape;
        let vertex = vertex_at(&model, &pyramid, apex);
        every_labelling_agrees(&mut model, &pyramid, &vertex, 8);
    }
}