ogeom_topo/
shape.rs

1//! The shape triple, orientation, and the identity trichotomy.
2//!
3//! `docs/DATA_MODEL.md` §1, §3 and §4. A [`Shape`] is a *(topology node,
4//! placement, orientation)* triple: cheap to copy, with the heavy data (the
5//! children, the geometry, the tolerances) living once in an arena behind the
6//! node handle. That separation is why boundary representation scales: the same
7//! node appears at many placements and orientations without a byte of geometry
8//! being copied.
9//!
10//! Two consequences run through everything downstream.
11//!
12//! **Traversal composes.** A sub-shape's effective placement is the product of
13//! every placement from the root down, and its effective orientation is the
14//! composition of every orientation on that path. An explorer that yields
15//! sub-shapes without composing both is wrong in a way that produces
16//! plausible-looking garbage rather than an error.
17//!
18//! **Identity is three questions, not one.** See [`Shape::is_partner`],
19//! [`Shape::is_same`] and [`Shape::is_equal`].
20
21use core::hash::{Hash, Hasher};
22
23use ogeom_core::{Key, OgeomResult, Tolerances};
24use ogeom_math::Transform;
25
26use crate::entity::NodeData;
27use crate::location::{DatumStore, Location};
28
29/// What a topology node is.
30///
31/// Ordered by dimension, so `>=` asks a meaningful question ("is this at least
32/// a face?") and sorting a mixed collection groups it sensibly.
33#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
34pub enum ShapeType {
35    /// A point.
36    Vertex,
37    /// A curve bounded by vertices.
38    Edge,
39    /// A connected sequence of edges.
40    Wire,
41    /// A surface bounded by wires.
42    Face,
43    /// A connected set of faces.
44    Shell,
45    /// A volume bounded by shells.
46    Solid,
47    /// A connected set of solids sharing faces.
48    CompSolid,
49    /// An arbitrary collection, of any dimensions.
50    Compound,
51}
52
53impl ShapeType {
54    /// The type of the sub-shapes this type is built from, if any.
55    ///
56    /// A compound has no fixed child type (it holds anything), so this reports
57    /// `None` for it rather than guessing.
58    #[must_use]
59    pub const fn child_type(self) -> Option<Self> {
60        match self {
61            Self::Vertex | Self::Compound => None,
62            Self::Edge => Some(Self::Vertex),
63            Self::Wire => Some(Self::Edge),
64            Self::Face => Some(Self::Wire),
65            Self::Shell => Some(Self::Face),
66            Self::Solid => Some(Self::Shell),
67            Self::CompSolid => Some(Self::Solid),
68        }
69    }
70
71    /// The topological dimension: 0 for a vertex, 3 for a solid.
72    ///
73    /// A compound reports `None`, since it may mix dimensions.
74    #[must_use]
75    pub const fn dimension(self) -> Option<u8> {
76        match self {
77            Self::Vertex => Some(0),
78            Self::Edge | Self::Wire => Some(1),
79            Self::Face | Self::Shell => Some(2),
80            Self::Solid | Self::CompSolid => Some(3),
81            Self::Compound => None,
82        }
83    }
84}
85
86/// Which side of a boundary the material is on.
87///
88/// `docs/DATA_MODEL.md` §3.
89#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
90pub enum Orientation {
91    /// The material is on the surface's default side.
92    #[default]
93    Forward,
94    /// The material is on the other side.
95    Reversed,
96    /// The boundary lies *inside* the material: a stiffener edge embedded in a
97    /// face, an edge that does not separate anything.
98    Internal,
99    /// The boundary lies outside the material: reference geometry, carried
100    /// along but bounding nothing.
101    External,
102}
103
104impl Orientation {
105    /// Compose an outer orientation with an inner one.
106    ///
107    /// Applied at *every* level of descent: an edge's orientation within a face
108    /// depends on that face's orientation within its shell, and so on to the
109    /// root. Reversing a solid must therefore not touch a single child.
110    ///
111    /// `Internal` and `External` absorb: a boundary that lies inside the
112    /// material stays inside it however the shape around it is turned.
113    #[must_use]
114    pub const fn compose(self, inner: Self) -> Self {
115        match self {
116            Self::Forward => inner,
117            Self::Reversed => match inner {
118                Self::Forward => Self::Reversed,
119                Self::Reversed => Self::Forward,
120                other => other,
121            },
122            Self::Internal => Self::Internal,
123            Self::External => Self::External,
124        }
125    }
126
127    /// This orientation reversed.
128    ///
129    /// `Internal` and `External` are unaffected; neither names a side, so
130    /// neither has one to swap.
131    #[must_use]
132    pub const fn reversed(self) -> Self {
133        match self {
134            Self::Forward => Self::Reversed,
135            Self::Reversed => Self::Forward,
136            other => other,
137        }
138    }
139
140    /// Whether this orientation names a side of the material at all.
141    #[must_use]
142    pub const fn is_boundary(self) -> bool {
143        matches!(self, Self::Forward | Self::Reversed)
144    }
145}
146
147/// A topology node: the shared, placeless, orientationless part of a shape.
148///
149/// Held in an arena; a [`Shape`] refers to one by handle. The geometry,
150/// tolerances and edge representations that hang off a node live alongside it,
151/// keyed by the same handle.
152#[derive(Debug, Clone, PartialEq)]
153pub struct TShape {
154    kind: ShapeType,
155    data: NodeData,
156    children: Vec<Shape>,
157}
158
159/// A handle to a [`TShape`].
160pub type TShapeId = Key<TShape>;
161
162impl TShape {
163    /// A node of the given type, with its data and children.
164    #[must_use]
165    pub const fn new(kind: ShapeType, data: NodeData, children: Vec<Shape>) -> Self {
166        Self {
167            kind,
168            data,
169            children,
170        }
171    }
172
173    /// A container node: wire, shell, solid, compsolid or compound.
174    #[must_use]
175    pub const fn container(kind: ShapeType, children: Vec<Shape>) -> Self {
176        Self {
177            kind,
178            data: NodeData::Container,
179            children,
180        }
181    }
182
183    /// A node with data and no children.
184    #[must_use]
185    pub const fn leaf(kind: ShapeType, data: NodeData) -> Self {
186        Self {
187            kind,
188            data,
189            children: Vec::new(),
190        }
191    }
192
193    /// What kind of node this is.
194    #[must_use]
195    pub const fn kind(&self) -> ShapeType {
196        self.kind
197    }
198
199    /// The geometry and tolerance this node carries.
200    #[must_use]
201    pub const fn data(&self) -> &NodeData {
202        &self.data
203    }
204
205    /// Mutable access to the node's data.
206    #[must_use]
207    pub const fn data_mut(&mut self) -> &mut NodeData {
208        &mut self.data
209    }
210
211    /// The direct children, in order.
212    #[must_use]
213    pub fn children(&self) -> &[Shape] {
214        &self.children
215    }
216
217    /// The children, mutably, for binding restored handles to their arena.
218    pub(crate) const fn children_mut(&mut self) -> &mut Vec<Shape> {
219        &mut self.children
220    }
221
222    /// Number of direct children.
223    #[must_use]
224    pub fn child_count(&self) -> usize {
225        self.children.len()
226    }
227}
228
229/// A shape: a topology node, a placement, and an orientation.
230///
231/// Cheap to copy (a key, a small chain and an enum), so it is passed by value
232/// everywhere.
233#[derive(Debug, Clone)]
234pub struct Shape {
235    node: TShapeId,
236    location: Location,
237    orientation: Orientation,
238}
239
240impl Shape {
241    /// A shape from its three parts.
242    #[must_use]
243    pub const fn new(node: TShapeId, location: Location, orientation: Orientation) -> Self {
244        Self {
245            node,
246            location,
247            orientation,
248        }
249    }
250
251    /// A shape at the identity placement, oriented forward.
252    #[must_use]
253    pub fn of(node: TShapeId) -> Self {
254        Self::new(node, Location::identity(), Orientation::Forward)
255    }
256
257    /// The topology node.
258    #[must_use]
259    pub const fn node(&self) -> TShapeId {
260        self.node
261    }
262
263    /// The placement.
264    #[must_use]
265    pub const fn location(&self) -> &Location {
266        &self.location
267    }
268
269    /// The orientation.
270    #[must_use]
271    pub const fn orientation(&self) -> Orientation {
272        self.orientation
273    }
274
275    /// This shape with a different placement.
276    #[must_use]
277    pub fn located(&self, location: Location) -> Self {
278        Self {
279            location,
280            ..self.clone()
281        }
282    }
283
284    /// This shape with its handles bound to the arenas that hold them.
285    ///
286    /// For reading a document back, where the handles are rebuilt before the
287    /// arenas exist. Nothing else should need it.
288    pub(crate) fn rebound(&self, nodes: u32, datums: u32) -> Self {
289        Self {
290            node: self.node.with_scope(nodes),
291            location: self.location.with_datum_scope(datums),
292            orientation: self.orientation,
293        }
294    }
295
296    /// This shape with its handles shifted for landing in a live model.
297    ///
298    /// [`rebound`](Self::rebound)'s sibling for absorbing parts: the indices
299    /// were local to the source document, and its nodes and datums are about
300    /// to land `nodes` and `datums` slots into the target's arenas. The
301    /// handles stay unscoped; binding is a separate, later step.
302    pub(crate) fn shifted(&self, nodes: u32, datums: u32) -> Self {
303        Self {
304            node: crate::entity::shifted_key(self.node, nodes),
305            location: self.location.with_datum_offset(datums),
306            orientation: self.orientation,
307        }
308    }
309
310    /// This shape moved by `outer`, applied before its own placement.
311    ///
312    /// The operation traversal uses on descent: a child's placement within the
313    /// world is its parent's composed with its own.
314    #[must_use]
315    pub fn moved(&self, outer: &Location) -> Self {
316        Self {
317            location: outer.then(&self.location),
318            ..self.clone()
319        }
320    }
321
322    /// This shape with a different orientation.
323    #[must_use]
324    pub fn oriented(&self, orientation: Orientation) -> Self {
325        Self {
326            orientation,
327            ..self.clone()
328        }
329    }
330
331    /// This shape with its orientation reversed.
332    #[must_use]
333    pub fn reversed(&self) -> Self {
334        self.oriented(self.orientation.reversed())
335    }
336
337    /// This shape's orientation composed under `outer`.
338    ///
339    /// The other half of what traversal does on descent.
340    #[must_use]
341    pub fn composed(&self, outer: Orientation) -> Self {
342        self.oriented(outer.compose(self.orientation))
343    }
344
345    /// The composed placement as a transform.
346    ///
347    /// # Errors
348    ///
349    /// As [`Location::composed`].
350    pub fn transform(&self, store: &DatumStore) -> OgeomResult<Transform> {
351        self.location.composed(store)
352    }
353
354    /// Whether two shapes share a topology node, ignoring placement and
355    /// orientation.
356    ///
357    /// "Is this the same underlying topology, anywhere, any way round?": the
358    /// question to ask when relating a shape to another instance of itself
359    /// elsewhere in an assembly.
360    #[must_use]
361    pub fn is_partner(&self, other: &Self) -> bool {
362        self.node == other.node
363    }
364
365    /// Whether two shapes share a node *and* a placement, ignoring orientation.
366    ///
367    /// The common case, and the one most algorithms want: an edge and its
368    /// reverse are the same edge in the same place, and a set of edges should
369    /// hold one of them, not two.
370    #[must_use]
371    pub fn is_same(&self, other: &Self) -> bool {
372        self.node == other.node && self.location == other.location
373    }
374
375    /// Whether two shapes agree in all three parts.
376    ///
377    /// Exact identity. An edge and its reverse are *not* equal, which is what
378    /// makes a wire's direction of travel expressible.
379    #[must_use]
380    pub fn is_equal(&self, other: &Self) -> bool {
381        self.is_same(other) && self.orientation == other.orientation
382    }
383
384    /// Whether two shapes occupy the same place, comparing composed transforms
385    /// rather than chains.
386    ///
387    /// Costlier than [`Shape::is_same`] and answers a different question: two
388    /// placements built by different routes can land in the same position.
389    ///
390    /// # Errors
391    ///
392    /// As [`Location::composed`].
393    pub fn is_same_position(
394        &self,
395        other: &Self,
396        store: &DatumStore,
397        tol: Tolerances,
398    ) -> OgeomResult<bool> {
399        Ok(self.node == other.node
400            && self
401                .location
402                .is_same_placement(&other.location, store, tol)?)
403    }
404}
405
406/// Equality by [`Shape::is_equal`]: node, placement *and* orientation.
407///
408/// The strictest of the three, chosen as the derive-shaped default so that a
409/// plain `==` never silently means something looser than the reader expects.
410/// Code that wants a weaker equivalence says so, through [`SameKey`] or
411/// [`PartnerKey`].
412impl PartialEq for Shape {
413    fn eq(&self, other: &Self) -> bool {
414        self.is_equal(other)
415    }
416}
417
418impl Eq for Shape {}
419
420impl Hash for Shape {
421    fn hash<H: Hasher>(&self, state: &mut H) {
422        self.node.hash(state);
423        self.location.hash(state);
424        self.orientation.hash(state);
425    }
426}
427
428/// A key that hashes and compares by [`Shape::is_same`]: node and placement,
429/// ignoring orientation.
430///
431/// Wrapping rather than offering a custom hasher, because the danger being
432/// guarded against is a map whose comparison and hash disagree: a set keyed on
433/// "same" semantics but hashing the orientation as well will silently hold both
434/// an edge and its reverse. Making the equivalence part of the *type* means the
435/// two can never drift apart.
436#[derive(Debug, Clone)]
437pub struct SameKey(pub Shape);
438
439impl PartialEq for SameKey {
440    fn eq(&self, other: &Self) -> bool {
441        self.0.is_same(&other.0)
442    }
443}
444
445impl Eq for SameKey {}
446
447impl Hash for SameKey {
448    fn hash<H: Hasher>(&self, state: &mut H) {
449        self.0.node.hash(state);
450        self.0.location.hash(state);
451    }
452}
453
454/// A key that hashes and compares by [`Shape::is_partner`]: the node alone.
455#[derive(Debug, Clone)]
456pub struct PartnerKey(pub Shape);
457
458impl PartialEq for PartnerKey {
459    fn eq(&self, other: &Self) -> bool {
460        self.0.is_partner(&other.0)
461    }
462}
463
464impl Eq for PartnerKey {}
465
466impl Hash for PartnerKey {
467    fn hash<H: Hasher>(&self, state: &mut H) {
468        self.0.node.hash(state);
469    }
470}
471
472#[cfg(test)]
473#[allow(clippy::unwrap_used)]
474mod tests {
475    use super::*;
476    use crate::entity::VertexData;
477    use ogeom_core::Arena;
478    use ogeom_math::{Point, Vector};
479    use std::collections::HashSet;
480
481    fn setup() -> (Arena<TShape>, DatumStore, TShapeId, TShapeId, Location) {
482        let mut arena = Arena::new();
483        let a = arena.insert(TShape::leaf(
484            ShapeType::Vertex,
485            NodeData::Vertex(VertexData::new(Point::ORIGIN)),
486        ));
487        let b = arena.insert(TShape::leaf(
488            ShapeType::Vertex,
489            NodeData::Vertex(VertexData::new(Point::ORIGIN)),
490        ));
491        let mut store = DatumStore::new();
492        let datum = store.insert(Transform::translation(Vector::new(1.0, 0.0, 0.0)));
493        (arena, store, a, b, Location::of(datum))
494    }
495
496    #[test]
497    fn orientation_composition_is_a_monoid_with_forward_as_identity() {
498        use Orientation::{External, Forward, Internal, Reversed};
499        for o in [Forward, Reversed, Internal, External] {
500            assert_eq!(Forward.compose(o), o, "forward is a left identity");
501            assert_eq!(o.compose(Forward), o, "and a right identity");
502        }
503        assert_eq!(Reversed.compose(Reversed), Forward);
504        assert_eq!(Reversed.compose(Forward), Reversed);
505    }
506
507    #[test]
508    fn composition_is_associative() {
509        use Orientation::{External, Forward, Internal, Reversed};
510        let all = [Forward, Reversed, Internal, External];
511        for a in all {
512            for b in all {
513                for c in all {
514                    assert_eq!(
515                        a.compose(b).compose(c),
516                        a.compose(b.compose(c)),
517                        "{a:?} {b:?} {c:?}"
518                    );
519                }
520            }
521        }
522    }
523
524    #[test]
525    fn internal_and_external_absorb_and_do_not_reverse() {
526        use Orientation::{External, Forward, Internal, Reversed};
527        // A boundary inside the material stays inside it however the shape
528        // around it is turned.
529        for o in [Forward, Reversed, Internal, External] {
530            assert_eq!(Internal.compose(o), Internal);
531            assert_eq!(External.compose(o), External);
532        }
533        assert_eq!(Internal.reversed(), Internal);
534        assert_eq!(External.reversed(), External);
535        assert!(!Internal.is_boundary());
536        assert!(!External.is_boundary());
537        assert!(Forward.is_boundary() && Reversed.is_boundary());
538    }
539
540    #[test]
541    fn reversal_is_an_involution() {
542        use Orientation::{External, Forward, Internal, Reversed};
543        for o in [Forward, Reversed, Internal, External] {
544            assert_eq!(o.reversed().reversed(), o);
545        }
546    }
547
548    #[test]
549    fn the_identity_trichotomy_distinguishes_three_questions() {
550        let (_, _, a, b, loc) = setup();
551
552        let base = Shape::of(a);
553        let reversed = base.reversed();
554        let moved = base.located(loc.clone());
555        let other_node = Shape::of(b);
556
557        // Same node, same place, opposite orientation.
558        assert!(base.is_partner(&reversed));
559        assert!(base.is_same(&reversed));
560        assert!(
561            !base.is_equal(&reversed),
562            "orientation must distinguish them"
563        );
564
565        // Same node, different place.
566        assert!(base.is_partner(&moved));
567        assert!(!base.is_same(&moved), "placement must distinguish them");
568        assert!(!base.is_equal(&moved));
569
570        // Different node.
571        assert!(!base.is_partner(&other_node));
572        assert!(!base.is_same(&other_node));
573        assert!(!base.is_equal(&other_node));
574
575        // And each is reflexive.
576        assert!(base.is_equal(&base) && base.is_same(&base) && base.is_partner(&base));
577    }
578
579    #[test]
580    fn each_key_type_hashes_consistently_with_its_own_equality() {
581        // The failure this guards: a set whose comparison and hash disagree
582        // holds duplicates it believes it has excluded. Making the equivalence
583        // part of the type is what keeps them together.
584        let (_, _, a, _, loc) = setup();
585        let base = Shape::of(a);
586        let reversed = base.reversed();
587        let moved = base.located(loc);
588
589        let equal: HashSet<Shape> = [base.clone(), reversed.clone(), moved.clone()]
590            .into_iter()
591            .collect();
592        assert_eq!(equal.len(), 3, "all three differ under strict equality");
593
594        let same: HashSet<SameKey> = [base.clone(), reversed.clone(), moved.clone()]
595            .into_iter()
596            .map(SameKey)
597            .collect();
598        assert_eq!(same.len(), 2, "orientation is ignored, placement is not");
599
600        let partner: HashSet<PartnerKey> = [base, reversed, moved]
601            .into_iter()
602            .map(PartnerKey)
603            .collect();
604        assert_eq!(partner.len(), 1, "only the node matters");
605    }
606
607    #[test]
608    fn a_shape_placed_and_composed_reports_the_expected_position() {
609        let (_, store, a, _, loc) = setup();
610        let shape = Shape::of(a).located(loc.clone());
611        assert!(
612            shape
613                .transform(&store)
614                .unwrap()
615                .apply(Point::ORIGIN)
616                .is_equal(Point::new(1.0, 0.0, 0.0), Tolerances::millimetres())
617        );
618
619        // Moving under an outer placement composes rather than replaces.
620        let nested = shape.moved(&loc);
621        assert!(
622            nested
623                .transform(&store)
624                .unwrap()
625                .apply(Point::ORIGIN)
626                .is_equal(Point::new(2.0, 0.0, 0.0), Tolerances::millimetres())
627        );
628        assert_eq!(nested.location().depth(), 1, "same datum, merged power");
629    }
630
631    #[test]
632    fn positions_reached_by_different_routes_compare_equal() {
633        let mut store = DatumStore::new();
634        let a = store.insert(Transform::translation(Vector::X));
635        let b = store.insert(Transform::translation(Vector::X));
636        let mut arena = Arena::new();
637        let node = arena.insert(TShape::leaf(
638            ShapeType::Vertex,
639            NodeData::Vertex(VertexData::new(Point::ORIGIN)),
640        ));
641
642        let via_a = Shape::of(node).located(Location::of(a));
643        let via_b = Shape::of(node).located(Location::of(b));
644        let tol = Tolerances::millimetres();
645
646        assert!(!via_a.is_same(&via_b), "structurally different chains");
647        assert!(
648            via_a.is_same_position(&via_b, &store, tol).unwrap(),
649            "but the same position"
650        );
651    }
652
653    #[test]
654    fn shape_types_report_their_children_and_dimensions() {
655        use ShapeType::{CompSolid, Compound, Edge, Face, Shell, Solid, Vertex, Wire};
656        assert_eq!(Vertex.child_type(), None);
657        assert_eq!(Edge.child_type(), Some(Vertex));
658        assert_eq!(Face.child_type(), Some(Wire));
659        assert_eq!(Solid.child_type(), Some(Shell));
660        assert_eq!(Compound.child_type(), None, "a compound holds anything");
661
662        assert_eq!(Vertex.dimension(), Some(0));
663        assert_eq!(Wire.dimension(), Some(1));
664        assert_eq!(Shell.dimension(), Some(2));
665        assert_eq!(CompSolid.dimension(), Some(3));
666        assert_eq!(Compound.dimension(), None, "a compound may mix dimensions");
667
668        // The ordering makes "at least a face" expressible.
669        assert!(Face > Edge && Solid > Face);
670        assert!(Face >= Face);
671    }
672
673    #[test]
674    fn a_node_carries_its_children_in_order() {
675        let (mut arena, _, a, b, _) = setup();
676        let wire = arena.insert(TShape::container(
677            ShapeType::Wire,
678            vec![Shape::of(a), Shape::of(b).reversed()],
679        ));
680        let node = arena.get(wire).unwrap();
681        assert_eq!(node.kind(), ShapeType::Wire);
682        assert_eq!(node.child_count(), 2);
683        assert_eq!(node.children()[1].orientation(), Orientation::Reversed);
684    }
685}
ogeom_topo/shape.rs

ogeom_topo/
shape.rs
