ogeom_algo/

place.rs

//! Placing and duplicating shapes.
//!
//! # A rigid move copies nothing
//!
//! [`transformed`] returns the *same* topology at a different
//! [`Location`]. No node is created, no curve is
//! re-evaluated, and the result compares equal to the original under
//! [`Shape::is_partner`], which is how "these thousand bolts are the same
//! bolt" stays a fact the model knows rather than one an application has to
//! remember (`docs/DATA_MODEL.md` §2, §3).
//!
//! That is only sound because a location is a rigid motion with a uniform
//! scale. Such a motion carries a line to a line and a circle to a circle, so
//! the geometry underneath still describes the moved shape. An affine transform
//! that shears or scales unevenly does not: it carries a circle to an ellipse,
//! and no amount of placement makes a circle record that. The type system says
//! so: [`transformed`] takes a [`Transform`], which is a similarity by
//! construction, and a general affine transform is a different type it will not
//! accept. Applying one means rebuilding the geometry, which is what
//! `general_transformed_shape` does.
//!
//! # A copy is for editing, not for moving
//!
//! [`copied`] duplicates the topology so the two can diverge. It shares the
//! *geometry*: curves and surfaces are immutable values in an arena, so two
//! shapes naming one circle can never disagree about it, and copying it would
//! only make the model larger. What a copy buys is independent topology:
//! tolerances, representations and children that one shape can change without
//! the other seeing it.

use ogeom_core::FastMap;

use ogeom_core::{OgeomResult, ogeom_bail};
use ogeom_math::Transform;
use ogeom_topo::{Location, Model, NodeData, Shape, ShapeType, TShapeId, explore_unique};

use crate::history::{Built, History};

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

    /// An entity that is a copy of another.
    pub const COPY: Role = Role::op_defined(30);
}

/// Move a shape by a rigid motion, sharing everything.
///
/// Cheap and exact: the result names the same topology nodes and the same
/// geometry, at a new placement.
///
/// The history records the shape and every sub-shape below it as modified
/// into its occurrence in the moved shape: the same node under the new
/// placement. A placement is part of a sub-shape's identity, so without the
/// record a face of the input would trace to itself, which is no face of
/// the result. The records cost one walk of the input's unique sub-shapes;
/// no node is made.
///
/// There is no way to pass something that is *not* a placement. [`Transform`]
/// is a similarity by construction (rigid motion with a uniform scale), and a
/// shear or a non-uniform scale is a
/// [`GeneralTransform`](ogeom_math::GeneralTransform), which this does not accept.
/// That is deliberate: such a transform carries a circle to an ellipse, and
/// recording it as a placement would leave every circle in the shape claiming
/// to be a circle while sitting on an ellipse. The type refuses it, so no
/// runtime check has to.
///
/// # Errors
///
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if the shape does not
/// resolve in this model.
pub fn transformed(model: &mut Model, shape: &Shape, transform: Transform) -> OgeomResult<Built> {
    if model.node(shape).is_none() {
        ogeom_bail!(Dangling, "shape refers to a node not in this model");
    }
    model.begin_operation();
    let datum = model.add_datum(transform);
    let by = Location::of(datum);
    let moved = shape.moved(&by);

    let mut history = History::new();
    history.modify(shape, moved.clone());
    for kind in [
        ShapeType::CompSolid,
        ShapeType::Solid,
        ShapeType::Shell,
        ShapeType::Face,
        ShapeType::Wire,
        ShapeType::Edge,
        ShapeType::Vertex,
    ] {
        for part in explore_unique(model, shape, kind)? {
            if !part.is_same(shape) {
                let image = part.moved(&by);
                history.modify(&part, image);
            }
        }
    }
    Ok(Built::new(moved, history))
}

/// Duplicate a shape's topology so the two can be edited apart.
///
/// Geometry is shared, not duplicated; see the module docs.
///
/// # Errors
///
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if the shape does not
/// resolve in this model.
pub fn copied(model: &mut Model, shape: &Shape) -> OgeomResult<Built> {
    if model.node(shape).is_none() {
        ogeom_bail!(Dangling, "shape refers to a node not in this model");
    }
    model.begin_operation();

    let mut done: FastMap<TShapeId, Shape> = FastMap::default();
    let mut history = History::new();
    let bare = duplicate(model, shape, &mut done, &mut history)?;
    // The root's own placement and orientation, applied here and nowhere else.
    let root = bare.moved(shape.location()).composed(shape.orientation());
    Ok(Built::new(root, history))
}

/// Copy one node and everything below it, memoized. Returns the *bare* copy
/// (the new node at identity, forward), never the occurrence it was reached by.
///
/// The memo is not an optimization. A shared edge appears under two faces, and
/// copying it twice would give the copy two edges where the original had one;
/// the shell would then be open along every shared boundary, and nothing about
/// the geometry would say why.
///
/// The recursion is keyed by *node*, and each level copies its children from
/// what the node **stores**, not from what [`Model::children_of`] returns.
/// That accessor composes the parent's placement and orientation onto each
/// child, which is right for traversal and wrong for copying: storing the
/// composed occurrence and then returning it composed again applies the
/// parent's transform twice. A doubled placement merely puts the copy in the
/// wrong place, but a doubled orientation takes a wire apart: reversing a
/// wire is *reverse the order and flip every sense*, and `children_of` carries
/// only the sense half, so the second application flips the senses back while
/// the order stays put and consecutive edges stop meeting. A parent's
/// `(location, orientation)` is applied exactly once: by whoever stores the
/// occurrence, or by [`copied`] at the root.
fn duplicate(
    model: &mut Model,
    shape: &Shape,
    done: &mut FastMap<TShapeId, Shape>,
    history: &mut History,
) -> OgeomResult<Shape> {
    if let Some(existing) = done.get(&shape.node()) {
        return Ok(existing.clone());
    }

    let Some(node) = model.node(shape) else {
        ogeom_bail!(Dangling, "shape refers to a node not in this model");
    };
    let kind = node.kind();
    let data = node.data().clone();
    let stored = node.children().to_vec();

    // Children first: a node is built from the shapes below it, so they have to
    // exist before it does.
    let mut children = Vec::new();
    for raw in &stored {
        // History and provenance are keyed by where the child stands in the
        // world, which is the occurrence `children_of` would have handed back.
        let world = raw.moved(shape.location()).composed(shape.orientation());
        let bare = duplicate(model, &world, done, history)?;
        // The copied child stands where the original's stored entry said, with
        // that entry's own placement and sense carried over verbatim.
        // `Shape::new` rather than `moved`/`composed` because composition
        // absorbs `Internal` and `External`, and a copy must not quietly
        // convert them into a plain reversal.
        children.push(Shape::new(
            bare.node(),
            raw.location().clone(),
            raw.orientation(),
        ));
    }

    let fresh = match (kind, data) {
        (ShapeType::Vertex, NodeData::Vertex(v)) => model.add_vertex(v),
        (ShapeType::Edge, NodeData::Edge(e)) => model.add_edge(*e, &children)?,
        (ShapeType::Wire, _) => model.add_wire(&children)?,
        (ShapeType::Face, NodeData::Face(f)) => model.add_face(*f, &children)?,
        (ShapeType::Shell, _) => model.add_shell(&children)?,
        (ShapeType::Solid, _) => model.add_solid(&children)?,
        (ShapeType::CompSolid, _) => model.add_compsolid(&children)?,
        (ShapeType::Compound, _) => model.add_compound(&children)?,
        (other, _) => ogeom_bail!(
            Construction,
            "a {other:?} node does not hold the data its kind requires, so it \
             cannot be copied"
        ),
    };

    // The copy names what it came from, so a reference into the original still
    // resolves after the copy is edited.
    let bare = Shape::of(fresh.node());
    model.set_derived(&bare, std::slice::from_ref(shape), roles::COPY)?;
    history.modify(shape, bare.clone());
    done.insert(shape.node(), bare.clone());

    Ok(bare)
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;
    use crate::check::check;
    use crate::mass::volume_properties;
    use crate::{make_box, make_cylinder};
    use approx::assert_relative_eq;
    use ogeom_core::Tolerances;
    use ogeom_math::{Axis, Direction, Frame, Point, Vector};
    use ogeom_mesh::Deflection;

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

    fn deflection() -> Deflection {
        Deflection {
            chord: 0.01,
            ..Deflection::default()
        }
    }

    #[test]
    fn a_rigid_move_creates_no_topology_at_all() {
        // The whole point. A thousand identical bolts should cost one bolt and
        // a thousand placements, not a thousand bolts.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 2.0, 3.0), T)
            .unwrap()
            .shape;
        let before = model.node_count();

        let moved = transformed(&mut model, &solid, Transform::translation(Vector::X * 10.0))
            .unwrap()
            .shape;

        assert_eq!(model.node_count(), before, "a placement copied something");
        assert!(moved.is_partner(&solid), "the same topology, elsewhere");
        assert!(!moved.is_same(&solid), "but at a different placement");
    }

    /// Each face, edge and vertex of a box, moved, mirrored or scaled,
    /// traces to exactly one sub-shape of the result of its kind, the one
    /// with its role, and reads as affected.
    #[test]
    fn every_sub_shape_traces_to_its_occurrence_in_the_moved_shape() {
        let mut model = Model::new();
        let cube = make_box(&mut model, Frame::WORLD, (10.0, 10.0, 10.0), T)
            .unwrap()
            .shape;
        for transform in [
            Transform::translation(Vector::new(100.0, 0.0, 0.0)),
            Transform::plane_mirror(Point::ORIGIN, Direction::X),
            Transform::scaling(Point::ORIGIN, 2.0, T).unwrap(),
        ] {
            let moved = transformed(&mut model, &cube, transform).unwrap();
            assert!(moved.history.trace(&cube)[0].is_same(&moved.shape));
            for (kind, count) in [
                (ShapeType::Face, 6),
                (ShapeType::Edge, 12),
                (ShapeType::Vertex, 8),
            ] {
                let result = explore_unique(&model, &moved.shape, kind).unwrap();
                let parts = explore_unique(&model, &cube, kind).unwrap();
                assert_eq!(parts.len(), count);
                for part in &parts {
                    assert!(moved.history.is_affected(part));
                    let found: Vec<&Shape> = result
                        .iter()
                        .filter(|r| moved.history.trace(part).iter().any(|t| t.is_same(r)))
                        .collect();
                    assert_eq!(found.len(), 1, "{kind:?}");
                    assert_eq!(found[0].node(), part.node());
                    assert_eq!(model.provenance_of(found[0]), model.provenance_of(part));
                }
            }
        }
    }

    #[test]
    fn a_moved_shape_measures_the_same_and_sits_elsewhere() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 2.0, 3.0), T)
            .unwrap()
            .shape;
        let offset = Vector::new(10.0, -20.0, 30.0);
        let moved = transformed(&mut model, &solid, Transform::translation(offset))
            .unwrap()
            .shape;

        let here = volume_properties(&model, &solid, deflection(), T).unwrap();
        let there = volume_properties(&model, &moved, deflection(), T).unwrap();
        assert_relative_eq!(here.mass, there.mass, epsilon = 1e-9);
        assert!(there.centre.distance(here.centre + offset) < 1e-9);

        assert!(check(&model, &moved, T).unwrap().is_valid());
    }

    #[test]
    fn a_rotation_is_a_placement_and_a_reflection_still_is() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 2.0, 3.0), T)
            .unwrap()
            .shape;
        for transform in [
            Transform::rotation(Axis::Z, 0.7),
            Transform::scaling(Point::ORIGIN, 2.0, T).unwrap(),
            Transform::plane_mirror(Point::ORIGIN, Direction::Z),
        ] {
            assert!(
                transformed(&mut model, &solid, transform).is_ok(),
                "a rigid or uniformly scaled motion should be a placement"
            );
        }
    }

    #[test]
    fn a_uniform_scale_scales_the_volume_by_its_cube() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let bigger = transformed(
            &mut model,
            &solid,
            Transform::scaling(Point::ORIGIN, 3.0, T).unwrap(),
        )
        .unwrap()
        .shape;
        let props = volume_properties(&model, &bigger, deflection(), T).unwrap();
        assert_relative_eq!(props.mass, 27.0, epsilon = 1e-9);
    }

    #[test]
    fn a_copy_has_its_own_topology_and_the_same_geometry() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (2.0, 2.0, 2.0), T)
            .unwrap()
            .shape;
        let (curves, pcurves, surfaces) = model.geometry().counts();

        let copy = copied(&mut model, &solid).unwrap().shape;
        assert!(!copy.is_partner(&solid), "a copy is not the same topology");
        assert_eq!(
            model.geometry().counts(),
            (curves, pcurves, surfaces),
            "geometry is immutable and shared; copying it buys nothing"
        );

        // And it is a whole, valid solid, not a shell of loose faces.
        assert!(check(&model, &copy, T).unwrap().is_valid());
        let props = volume_properties(&model, &copy, deflection(), T).unwrap();
        assert_relative_eq!(props.mass, 8.0, epsilon = 1e-9);
    }

    #[test]
    fn a_copy_keeps_shared_edges_shared() {
        // The memo is what makes this true. Copying each edge once per face
        // would give the copy twice the edges, and the shell would be open
        // along every one of them with nothing in the geometry to say so.
        let mut model = Model::new();
        let solid = make_cylinder(&mut model, Frame::WORLD, 2.0, 3.0, T)
            .unwrap()
            .shape;
        let copy = copied(&mut model, &solid).unwrap().shape;

        for kind in [
            ShapeType::Face,
            ShapeType::Edge,
            ShapeType::Vertex,
            ShapeType::Wire,
        ] {
            assert_eq!(
                explore_unique(&model, &copy, kind).unwrap().len(),
                explore_unique(&model, &solid, kind).unwrap().len(),
                "the copy has a different number of {kind:?}"
            );
        }
        assert!(check(&model, &copy, T).unwrap().is_valid());
    }

    #[test]
    fn a_copy_of_a_prism_with_instanced_caps_is_still_a_closed_solid() {
        // A box is the easy case: every occurrence it stores is forward and at
        // identity, so copying it cannot tell whether a parent's placement is
        // being applied once or twice. A prism can: its near cap is the
        // profile *reversed* and its far cap is that same node at a
        // displacement, and a wire is where a doubled orientation shows,
        // because reversing one reverses the walk as well as each edge.
        let mut model = Model::new();
        let solid = prism_of_a_square(&mut model);

        let copy = copied(&mut model, &solid).unwrap().shape;

        let diagnosis = check(&model, &copy, T).unwrap();
        assert!(diagnosis.is_valid(), "{:?}", diagnosis.problems);
        let props = volume_properties(&model, &copy, deflection(), T).unwrap();
        assert_relative_eq!(props.mass, 500.0, epsilon = 1e-9);

        // And the instancing survived: one cap node used twice, not two.
        for kind in [
            ShapeType::Face,
            ShapeType::Edge,
            ShapeType::Vertex,
            ShapeType::Wire,
        ] {
            assert_eq!(
                explore_unique(&model, &copy, kind).unwrap().len(),
                explore_unique(&model, &solid, kind).unwrap().len(),
                "the copy has a different number of {kind:?}"
            );
        }
    }

    #[test]
    fn a_copy_of_a_prism_bakes_cleanly() {
        // The bake walks every wire in traversal order and rebuilds it, so it
        // is the shortest path to the question "do this copy's edges still
        // meet?", and it is the path a mirrored operand takes into the
        // boolean.
        let mut model = Model::new();
        let solid = prism_of_a_square(&mut model);
        let copy = copied(&mut model, &solid).unwrap().shape;

        let baked = crate::convert::baked_shape(&mut model, &copy, T)
            .unwrap()
            .shape;

        let diagnosis = check(&model, &baked, T).unwrap();
        assert!(diagnosis.is_valid(), "{:?}", diagnosis.problems);
        let props = volume_properties(&model, &baked, deflection(), T).unwrap();
        assert_relative_eq!(props.mass, 500.0, epsilon = 1e-6);
    }

    /// A 10×10×5 prism built the way a pad is: a profile face, swept.
    fn prism_of_a_square(model: &mut Model) -> Shape {
        use crate::build::{make_face_with_pcurves, make_polygon};
        use crate::sweep::make_prism;
        use ogeom_geom::{PlaneSurface, SurfaceGeometry};
        use ogeom_math::Plane;

        let pts = [
            Point::new(0.0, 0.0, 0.0),
            Point::new(10.0, 0.0, 0.0),
            Point::new(10.0, 10.0, 0.0),
            Point::new(0.0, 10.0, 0.0),
        ];
        let wire = make_polygon(model, &pts, true, T).unwrap().shape;
        let surface = PlaneSurface::over(Plane::XY, (-1.0, 11.0), (-1.0, 11.0)).unwrap();
        let edges = model.children_of(&wire).unwrap();
        let face = make_face_with_pcurves(model, SurfaceGeometry::Plane(surface), &[edges], T)
            .unwrap()
            .shape;
        make_prism(model, &face, Vector::new(0.0, 0.0, 5.0), T)
            .unwrap()
            .shape
    }

    #[test]
    fn a_copy_names_what_it_came_from() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let built = copied(&mut model, &solid).unwrap();

        assert_eq!(
            model
                .provenance_of(&built.shape)
                .and_then(ogeom_core::Provenance::role),
            Some(roles::COPY)
        );
        // And the history says the original became it, so a reference into the
        // original still resolves.
        assert_eq!(
            built.history.modified(&solid),
            std::slice::from_ref(&built.shape)
        );
        assert!(!built.history.is_deleted(&solid));
    }

    #[test]
    fn placing_or_copying_a_stranger_is_an_error() {
        let mut other = Model::new();
        for _ in 0..4 {
            other.add_vertex(ogeom_topo::VertexData::new(Point::ORIGIN));
        }
        let beyond = other.add_vertex(ogeom_topo::VertexData::new(Point::ORIGIN));

        let mut empty = Model::new();
        assert!(transformed(&mut empty, &beyond, Transform::IDENTITY).is_err());
        assert!(copied(&mut empty, &beyond).is_err());
    }
}