ogeom_heal/
free_bounds.rs

1//! Free bounds: the edges of a shape only one face walks, chained into the
2//! contours they form.
3//!
4//! A shell open along some of its edges is open along contours: the rim of
5//! a sheet, the edge of a hole where a face is missing. Each free edge is
6//! walked by its one face in the direction that face's material keeps to
7//! the left of, so where the faces agree in orientation, the free edges
8//! chain head to tail round each opening. A contour that comes back to the
9//! vertex it left from is closed: an opening a face could fill. One that
10//! stops where no free edge carries on (two openings meeting at vertices
11//! the model holds apart, or faces that disagree in orientation) is open.
12//!
13//! An edge or vertex is one per placed occurrence: two placements of one
14//! open face are two openings, though they share every node.
15//!
16//! Nothing is joined here. Free edges within the tolerances they state are
17//! already one edge to sewing, and [`fix_shape`](crate::fix_shape()) says
18//! which pairs farther apart are each other's twins.
19
20use ogeom_algo::edge_vertices;
21use ogeom_core::{FastMap, OgeomResult};
22use ogeom_topo::{Model, SameKey, Shape, ShapeType, explore_unique};
23
24/// The free edges of a shape, chained.
25#[derive(Debug, Clone, Default)]
26pub struct FreeBounds {
27    /// Contours that come back to where they began: each the edges in the
28    /// order they walk, as their faces walk them.
29    pub closed: Vec<Vec<Shape>>,
30    /// Chains that stop at a vertex where no free edge carries on.
31    pub open: Vec<Vec<Shape>>,
32}
33
34impl FreeBounds {
35    /// Whether the shape has no free edge at all.
36    #[must_use]
37    pub fn is_empty(&self) -> bool {
38        self.closed.is_empty() && self.open.is_empty()
39    }
40
41    /// Each contour as a wire of its edges in the order they walk, the
42    /// closed contours first, then the open chains.
43    ///
44    /// # Errors
45    ///
46    /// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if an
47    /// edge is not in `model`.
48    pub fn wires(&self, model: &mut Model) -> OgeomResult<Vec<Shape>> {
49        self.closed
50            .iter()
51            .chain(&self.open)
52            .map(|edges| model.add_wire(edges))
53            .collect()
54    }
55}
56
57/// One free edge as its face walks it.
58struct Free {
59    edge: Shape,
60    from: SameKey,
61    to: SameKey,
62    /// The free edge its wire walks next, where that is one.
63    next_in_wire: Option<usize>,
64}
65
66/// The free bounds of `shape`: every edge only one of its faces walks, a
67/// degenerate edge aside, chained head to tail into contours. See the
68/// module documentation.
69///
70/// At a vertex where more than one free edge carries on, the one the same
71/// wire walks next is taken first, so a face's own rim comes out whole.
72///
73/// # Errors
74///
75/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if a handle
76/// fails to resolve.
77pub fn free_bounds(model: &Model, shape: &Shape) -> OgeomResult<FreeBounds> {
78    let faces = explore_unique(model, shape, ShapeType::Face)?;
79    let mut walks: Vec<Vec<Shape>> = Vec::new();
80    let mut uses: FastMap<SameKey, usize> = FastMap::default();
81    for face in &faces {
82        for wire in model.ordered_children_of(face)? {
83            let edges = model.ordered_children_of(&wire)?;
84            for edge in &edges {
85                *uses.entry(SameKey(edge.clone())).or_default() += 1;
86            }
87            walks.push(edges);
88        }
89    }
90    let is_free = |edge: &Shape| {
91        uses.get(&SameKey(edge.clone())) == Some(&1)
92            && !model
93                .node(edge)
94                .and_then(|n| n.data().as_edge())
95                .is_some_and(|d| d.degenerate)
96    };
97    let mut free: Vec<Free> = Vec::new();
98    for edges in &walks {
99        let first = free.len();
100        let mut at: Vec<Option<usize>> = Vec::with_capacity(edges.len());
101        for edge in edges {
102            if !is_free(edge) {
103                at.push(None);
104                continue;
105            }
106            let Some((start, end)) = edge_vertices(model, edge)? else {
107                at.push(None);
108                continue;
109            };
110            let (from, to) = (SameKey(start), SameKey(end));
111            at.push(Some(free.len()));
112            free.push(Free {
113                edge: edge.clone(),
114                from,
115                to,
116                next_in_wire: None,
117            });
118        }
119        if free.len() == first {
120            continue;
121        }
122        for i in 0..at.len() {
123            if let (Some(k), Some(next)) = (at[i], at[(i + 1) % at.len()]) {
124                free[k].next_in_wire = Some(next);
125            }
126        }
127    }
128
129    let mut leaving: FastMap<SameKey, Vec<usize>> = FastMap::default();
130    let mut arriving: FastMap<SameKey, usize> = FastMap::default();
131    for (k, f) in free.iter().enumerate() {
132        leaving.entry(f.from.clone()).or_default().push(k);
133        *arriving.entry(f.to.clone()).or_default() += 1;
134    }
135    let mut used = vec![false; free.len()];
136    let mut out = FreeBounds::default();
137    // Chains from vertices no free edge arrives at first, so an open chain
138    // is found whole from its head; what is left goes round.
139    let heads: Vec<usize> = (0..free.len())
140        .filter(|&k| !arriving.contains_key(&free[k].from))
141        .collect();
142    let rest = 0..free.len();
143    for start in heads.into_iter().chain(rest) {
144        if used[start] {
145            continue;
146        }
147        used[start] = true;
148        let mut chain = vec![start];
149        let mut last = start;
150        while free[last].to != free[start].from {
151            let next = free[last]
152                .next_in_wire
153                .filter(|&n| !used[n] && free[n].from == free[last].to)
154                .or_else(|| {
155                    leaving
156                        .get(&free[last].to)
157                        .and_then(|ks| ks.iter().copied().find(|&n| !used[n]))
158                });
159            let Some(next) = next else { break };
160            used[next] = true;
161            chain.push(next);
162            last = next;
163        }
164        let edges: Vec<Shape> = chain.iter().map(|&k| free[k].edge.clone()).collect();
165        if free[last].to == free[start].from {
166            out.closed.push(edges);
167        } else {
168            out.open.push(edges);
169        }
170    }
171    Ok(out)
172}
ogeom_heal/free_bounds.rs

ogeom_heal/
free_bounds.rs
