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            node: self.node,
318            location: outer.then(&self.location),
319            orientation: self.orientation,
320        }
321    }
322
323    /// This shape as a child of a parent placed at `outer` with sense
324    /// `sense`: [`Self::moved`] and [`Self::composed`] in one step, with
325    /// one placement built rather than three copied.
326    #[must_use]
327    pub fn beneath(&self, outer: &Location, sense: Orientation) -> Self {
328        Self {
329            node: self.node,
330            location: outer.then(&self.location),
331            orientation: sense.compose(self.orientation),
332        }
333    }
334
335    /// This shape with a different orientation.
336    #[must_use]
337    pub fn oriented(&self, orientation: Orientation) -> Self {
338        Self {
339            node: self.node,
340            location: self.location.clone(),
341            orientation,
342        }
343    }
344
345    /// This shape with its orientation reversed.
346    #[must_use]
347    pub fn reversed(&self) -> Self {
348        self.oriented(self.orientation.reversed())
349    }
350
351    /// This shape's orientation composed under `outer`.
352    ///
353    /// The other half of what traversal does on descent.
354    #[must_use]
355    pub fn composed(&self, outer: Orientation) -> Self {
356        self.oriented(outer.compose(self.orientation))
357    }
358
359    /// The composed placement as a transform.
360    ///
361    /// # Errors
362    ///
363    /// As [`Location::composed`].
364    pub fn transform(&self, store: &DatumStore) -> OgeomResult<Transform> {
365        self.location.composed(store)
366    }
367
368    /// Whether two shapes share a topology node, ignoring placement and
369    /// orientation.
370    ///
371    /// "Is this the same underlying topology, anywhere, any way round?": the
372    /// question to ask when relating a shape to another instance of itself
373    /// elsewhere in an assembly.
374    #[must_use]
375    pub fn is_partner(&self, other: &Self) -> bool {
376        self.node == other.node
377    }
378
379    /// Whether two shapes share a node *and* a placement, ignoring orientation.
380    ///
381    /// The common case, and the one most algorithms want: an edge and its
382    /// reverse are the same edge in the same place, and a set of edges should
383    /// hold one of them, not two.
384    #[must_use]
385    pub fn is_same(&self, other: &Self) -> bool {
386        self.node == other.node && self.location == other.location
387    }
388
389    /// Whether two shapes agree in all three parts.
390    ///
391    /// Exact identity. An edge and its reverse are *not* equal, which is what
392    /// makes a wire's direction of travel expressible.
393    #[must_use]
394    pub fn is_equal(&self, other: &Self) -> bool {
395        self.is_same(other) && self.orientation == other.orientation
396    }
397
398    /// Whether two shapes occupy the same place, comparing composed transforms
399    /// rather than chains.
400    ///
401    /// Costlier than [`Shape::is_same`] and answers a different question: two
402    /// placements built by different routes can land in the same position.
403    ///
404    /// # Errors
405    ///
406    /// As [`Location::composed`].
407    pub fn is_same_position(
408        &self,
409        other: &Self,
410        store: &DatumStore,
411        tol: Tolerances,
412    ) -> OgeomResult<bool> {
413        Ok(self.node == other.node
414            && self
415                .location
416                .is_same_placement(&other.location, store, tol)?)
417    }
418}
419
420/// Equality by [`Shape::is_equal`]: node, placement *and* orientation.
421///
422/// The strictest of the three, chosen as the derive-shaped default so that a
423/// plain `==` never silently means something looser than the reader expects.
424/// Code that wants a weaker equivalence says so, through [`SameKey`] or
425/// [`PartnerKey`].
426impl PartialEq for Shape {
427    fn eq(&self, other: &Self) -> bool {
428        self.is_equal(other)
429    }
430}
431
432impl Eq for Shape {}
433
434impl Hash for Shape {
435    fn hash<H: Hasher>(&self, state: &mut H) {
436        self.node.hash(state);
437        self.location.hash(state);
438        self.orientation.hash(state);
439    }
440}
441
442/// A key that hashes and compares by [`Shape::is_same`]: node and placement,
443/// ignoring orientation.
444///
445/// Wrapping rather than offering a custom hasher, because the danger being
446/// guarded against is a map whose comparison and hash disagree: a set keyed on
447/// "same" semantics but hashing the orientation as well will silently hold both
448/// an edge and its reverse. Making the equivalence part of the *type* means the
449/// two can never drift apart.
450#[derive(Debug, Clone)]
451pub struct SameKey(pub Shape);
452
453impl PartialEq for SameKey {
454    fn eq(&self, other: &Self) -> bool {
455        self.0.is_same(&other.0)
456    }
457}
458
459impl Eq for SameKey {}
460
461impl Hash for SameKey {
462    fn hash<H: Hasher>(&self, state: &mut H) {
463        self.0.node.hash(state);
464        self.0.location.hash(state);
465    }
466}
467
468/// A key that hashes and compares by [`Shape::is_partner`]: the node alone.
469#[derive(Debug, Clone)]
470pub struct PartnerKey(pub Shape);
471
472impl PartialEq for PartnerKey {
473    fn eq(&self, other: &Self) -> bool {
474        self.0.is_partner(&other.0)
475    }
476}
477
478impl Eq for PartnerKey {}
479
480impl Hash for PartnerKey {
481    fn hash<H: Hasher>(&self, state: &mut H) {
482        self.0.node.hash(state);
483    }
484}
485
486#[cfg(test)]
487#[allow(clippy::unwrap_used)]
488mod tests {
489    use super::*;
490    use crate::entity::VertexData;
491    use ogeom_core::Arena;
492    use ogeom_core::FastSet;
493    use ogeom_math::{Point, Vector};
494
495    fn setup() -> (Arena<TShape>, DatumStore, TShapeId, TShapeId, Location) {
496        let mut arena = Arena::new();
497        let a = arena.insert(TShape::leaf(
498            ShapeType::Vertex,
499            NodeData::Vertex(VertexData::new(Point::ORIGIN)),
500        ));
501        let b = arena.insert(TShape::leaf(
502            ShapeType::Vertex,
503            NodeData::Vertex(VertexData::new(Point::ORIGIN)),
504        ));
505        let mut store = DatumStore::new();
506        let datum = store.insert(Transform::translation(Vector::new(1.0, 0.0, 0.0)));
507        (arena, store, a, b, Location::of(datum))
508    }
509
510    #[test]
511    fn orientation_composition_is_a_monoid_with_forward_as_identity() {
512        use Orientation::{External, Forward, Internal, Reversed};
513        for o in [Forward, Reversed, Internal, External] {
514            assert_eq!(Forward.compose(o), o, "forward is a left identity");
515            assert_eq!(o.compose(Forward), o, "and a right identity");
516        }
517        assert_eq!(Reversed.compose(Reversed), Forward);
518        assert_eq!(Reversed.compose(Forward), Reversed);
519    }
520
521    #[test]
522    fn composition_is_associative() {
523        use Orientation::{External, Forward, Internal, Reversed};
524        let all = [Forward, Reversed, Internal, External];
525        for a in all {
526            for b in all {
527                for c in all {
528                    assert_eq!(
529                        a.compose(b).compose(c),
530                        a.compose(b.compose(c)),
531                        "{a:?} {b:?} {c:?}"
532                    );
533                }
534            }
535        }
536    }
537
538    #[test]
539    fn internal_and_external_absorb_and_do_not_reverse() {
540        use Orientation::{External, Forward, Internal, Reversed};
541        // A boundary inside the material stays inside it however the shape
542        // around it is turned.
543        for o in [Forward, Reversed, Internal, External] {
544            assert_eq!(Internal.compose(o), Internal);
545            assert_eq!(External.compose(o), External);
546        }
547        assert_eq!(Internal.reversed(), Internal);
548        assert_eq!(External.reversed(), External);
549        assert!(!Internal.is_boundary());
550        assert!(!External.is_boundary());
551        assert!(Forward.is_boundary() && Reversed.is_boundary());
552    }
553
554    #[test]
555    fn reversal_is_an_involution() {
556        use Orientation::{External, Forward, Internal, Reversed};
557        for o in [Forward, Reversed, Internal, External] {
558            assert_eq!(o.reversed().reversed(), o);
559        }
560    }
561
562    #[test]
563    fn the_identity_trichotomy_distinguishes_three_questions() {
564        let (_, _, a, b, loc) = setup();
565
566        let base = Shape::of(a);
567        let reversed = base.reversed();
568        let moved = base.located(loc.clone());
569        let other_node = Shape::of(b);
570
571        // Same node, same place, opposite orientation.
572        assert!(base.is_partner(&reversed));
573        assert!(base.is_same(&reversed));
574        assert!(
575            !base.is_equal(&reversed),
576            "orientation must distinguish them"
577        );
578
579        // Same node, different place.
580        assert!(base.is_partner(&moved));
581        assert!(!base.is_same(&moved), "placement must distinguish them");
582        assert!(!base.is_equal(&moved));
583
584        // Different node.
585        assert!(!base.is_partner(&other_node));
586        assert!(!base.is_same(&other_node));
587        assert!(!base.is_equal(&other_node));
588
589        // And each is reflexive.
590        assert!(base.is_equal(&base) && base.is_same(&base) && base.is_partner(&base));
591    }
592
593    #[test]
594    fn each_key_type_hashes_consistently_with_its_own_equality() {
595        // The failure this guards: a set whose comparison and hash disagree
596        // holds duplicates it believes it has excluded. Making the equivalence
597        // part of the type is what keeps them together.
598        let (_, _, a, _, loc) = setup();
599        let base = Shape::of(a);
600        let reversed = base.reversed();
601        let moved = base.located(loc);
602
603        let equal: FastSet<Shape> = [base.clone(), reversed.clone(), moved.clone()]
604            .into_iter()
605            .collect();
606        assert_eq!(equal.len(), 3, "all three differ under strict equality");
607
608        let same: FastSet<SameKey> = [base.clone(), reversed.clone(), moved.clone()]
609            .into_iter()
610            .map(SameKey)
611            .collect();
612        assert_eq!(same.len(), 2, "orientation is ignored, placement is not");
613
614        let partner: FastSet<PartnerKey> = [base, reversed, moved]
615            .into_iter()
616            .map(PartnerKey)
617            .collect();
618        assert_eq!(partner.len(), 1, "only the node matters");
619    }
620
621    #[test]
622    fn a_shape_placed_and_composed_reports_the_expected_position() {
623        let (_, store, a, _, loc) = setup();
624        let shape = Shape::of(a).located(loc.clone());
625        assert!(
626            shape
627                .transform(&store)
628                .unwrap()
629                .apply(Point::ORIGIN)
630                .is_equal(Point::new(1.0, 0.0, 0.0), Tolerances::millimetres())
631        );
632
633        // Moving under an outer placement composes rather than replaces.
634        let nested = shape.moved(&loc);
635        assert!(
636            nested
637                .transform(&store)
638                .unwrap()
639                .apply(Point::ORIGIN)
640                .is_equal(Point::new(2.0, 0.0, 0.0), Tolerances::millimetres())
641        );
642        assert_eq!(nested.location().depth(), 1, "same datum, merged power");
643    }
644
645    #[test]
646    fn positions_reached_by_different_routes_compare_equal() {
647        let mut store = DatumStore::new();
648        let a = store.insert(Transform::translation(Vector::X));
649        let b = store.insert(Transform::translation(Vector::X));
650        let mut arena = Arena::new();
651        let node = arena.insert(TShape::leaf(
652            ShapeType::Vertex,
653            NodeData::Vertex(VertexData::new(Point::ORIGIN)),
654        ));
655
656        let via_a = Shape::of(node).located(Location::of(a));
657        let via_b = Shape::of(node).located(Location::of(b));
658        let tol = Tolerances::millimetres();
659
660        assert!(!via_a.is_same(&via_b), "structurally different chains");
661        assert!(
662            via_a.is_same_position(&via_b, &store, tol).unwrap(),
663            "but the same position"
664        );
665    }
666
667    #[test]
668    fn shape_types_report_their_children_and_dimensions() {
669        use ShapeType::{CompSolid, Compound, Edge, Face, Shell, Solid, Vertex, Wire};
670        assert_eq!(Vertex.child_type(), None);
671        assert_eq!(Edge.child_type(), Some(Vertex));
672        assert_eq!(Face.child_type(), Some(Wire));
673        assert_eq!(Solid.child_type(), Some(Shell));
674        assert_eq!(Compound.child_type(), None, "a compound holds anything");
675
676        assert_eq!(Vertex.dimension(), Some(0));
677        assert_eq!(Wire.dimension(), Some(1));
678        assert_eq!(Shell.dimension(), Some(2));
679        assert_eq!(CompSolid.dimension(), Some(3));
680        assert_eq!(Compound.dimension(), None, "a compound may mix dimensions");
681
682        // The ordering makes "at least a face" expressible.
683        assert!(Face > Edge && Solid > Face);
684        assert!(Face >= Face);
685    }
686
687    #[test]
688    fn a_node_carries_its_children_in_order() {
689        let (mut arena, _, a, b, _) = setup();
690        let wire = arena.insert(TShape::container(
691            ShapeType::Wire,
692            vec![Shape::of(a), Shape::of(b).reversed()],
693        ));
694        let node = arena.get(wire).unwrap();
695        assert_eq!(node.kind(), ShapeType::Wire);
696        assert_eq!(node.child_count(), 2);
697        assert_eq!(node.children()[1].orientation(), Orientation::Reversed);
698    }
699}
ogeom_topo/shape.rs

ogeom_topo/
shape.rs
