geop_core_topology/model/
iterate.rs

1use crate::{
2    CoedgeGeometry, CoedgeId, EdgeId, FaceId, SolidId, VertexId,
3    boundary::{BoundaryIndex, BoundaryType},
4};
5use geop_core_math::{
6    geop_error::{GeopError, GeopResult},
7    scalars::Scalar,
8};
9
10use super::Model;
11
12/// Walks a single `Loop` boundary, in traversal order, by following `next`
13/// from `anchor` back around to itself. Does not itself bound how many
14/// coedges it will yield — a corrupted `next` chain that never returns to
15/// `anchor` makes this iterate forever, which is exactly what callers
16/// checking that invariant (see `validation::two_way_references`) want to be
17/// able to detect via a `.take(n)` of their own; well-formed loops always
18/// terminate on their own.
19struct LoopCoedges<'a, S: Scalar> {
20    model: &'a Model<S>,
21    anchor: CoedgeId,
22    cursor: Option<CoedgeId>,
23}
24
25impl<'a, S: Scalar> Iterator for LoopCoedges<'a, S> {
26    type Item = CoedgeId;
27
28    fn next(&mut self) -> Option<CoedgeId> {
29        let current = self.cursor?;
30        let next = self.model.coedges[&current].next;
31        self.cursor = if next == self.anchor {
32            None
33        } else {
34            Some(next)
35        };
36        Some(current)
37    }
38}
39
40/// Walks every coedge of every `Loop` boundary of a face, across all of them
41/// in order — a bare `Vertex` boundary contributes nothing (there are no
42/// coedges yet).
43struct FaceCoedges<'a, S: Scalar> {
44    model: &'a Model<S>,
45    boundaries: std::vec::IntoIter<BoundaryType>,
46    current: Option<LoopCoedges<'a, S>>,
47}
48
49impl<'a, S: Scalar> Iterator for FaceCoedges<'a, S> {
50    type Item = CoedgeId;
51
52    fn next(&mut self) -> Option<CoedgeId> {
53        loop {
54            if let Some(loop_iter) = &mut self.current {
55                if let Some(id) = loop_iter.next() {
56                    return Some(id);
57                }
58                self.current = None;
59            }
60            let boundary = self.boundaries.next()?;
61            if let BoundaryType::Loop(anchor) = boundary {
62                self.current = Some(LoopCoedges {
63                    model: self.model,
64                    anchor,
65                    cursor: Some(anchor),
66                });
67            }
68        }
69    }
70}
71
72/// Walks the distinct vertices referenced by a solid's faces, borrowing
73/// `model` for its whole lifetime — so a caller holding one of these live
74/// cannot also call a `&mut self` method like `merge_vertex` on the same
75/// model; the borrow checker enforces it rather than relying on a caller to
76/// remember that a `Vec` snapshot goes stale the moment the model mutates.
77struct SolidVertices<'a, S: Scalar> {
78    model: &'a Model<S>,
79    faces: std::vec::IntoIter<FaceId>,
80    coedges: std::vec::IntoIter<CoedgeId>,
81    seen: std::collections::HashSet<VertexId>,
82    pending: std::collections::VecDeque<VertexId>,
83}
84
85impl<'a, S: Scalar> Iterator for SolidVertices<'a, S> {
86    type Item = VertexId;
87
88    fn next(&mut self) -> Option<VertexId> {
89        loop {
90            if let Some(vertex_id) = self.pending.pop_front() {
91                if self.seen.insert(vertex_id) {
92                    return Some(vertex_id);
93                }
94                continue;
95            }
96
97            let coedge_id = match self.coedges.next() {
98                Some(coedge_id) => coedge_id,
99                None => {
100                    let face_id = self.faces.next()?;
101                    self.coedges = self
102                        .model
103                        .iterate_face_coedges(face_id)
104                        .collect::<Vec<_>>()
105                        .into_iter();
106                    continue;
107                }
108            };
109
110            match self.model.coedges[&coedge_id].geometry {
111                CoedgeGeometry::Edge(edge_id) => {
112                    let edge = &self.model.edges[&edge_id];
113                    self.pending.push_back(edge.start_vertex);
114                    self.pending.push_back(edge.end_vertex);
115                }
116                CoedgeGeometry::Vertex(vertex_id) => {
117                    self.pending.push_back(vertex_id);
118                }
119            }
120        }
121    }
122}
123
124/// Walks the distinct edges referenced by a solid's faces — see
125/// [`SolidVertices`]'s own doc comment for why this borrows `model` instead
126/// of returning an owned snapshot.
127struct SolidEdges<'a, S: Scalar> {
128    model: &'a Model<S>,
129    faces: std::vec::IntoIter<FaceId>,
130    coedges: std::vec::IntoIter<CoedgeId>,
131    seen: std::collections::HashSet<EdgeId>,
132}
133
134impl<'a, S: Scalar> Iterator for SolidEdges<'a, S> {
135    type Item = EdgeId;
136
137    fn next(&mut self) -> Option<EdgeId> {
138        loop {
139            let coedge_id = match self.coedges.next() {
140                Some(coedge_id) => coedge_id,
141                None => {
142                    let face_id = self.faces.next()?;
143                    self.coedges = self
144                        .model
145                        .iterate_face_coedges(face_id)
146                        .collect::<Vec<_>>()
147                        .into_iter();
148                    continue;
149                }
150            };
151
152            if let CoedgeGeometry::Edge(edge_id) = self.model.coedges[&coedge_id].geometry {
153                if self.seen.insert(edge_id) {
154                    return Some(edge_id);
155                }
156            }
157        }
158    }
159}
160
161impl<S: Scalar> Model<S> {
162    /// The (unordered) coedges referencing a given edge. An edge shared by a
163    /// single manifold face pair has exactly two.
164    pub fn coedges_of_edge(&self, edge: EdgeId) -> Vec<CoedgeId> {
165        self.coedges
166            .iter()
167            .filter(|(_, c)| c.geometry == CoedgeGeometry::Edge(edge))
168            .map(|(id, _)| *id)
169            .collect()
170    }
171
172    /// Every coedge of the loop anchored at `anchor`, in traversal order.
173    pub fn iterate_loop_coedges(&self, anchor: CoedgeId) -> impl Iterator<Item = CoedgeId> + '_ {
174        LoopCoedges {
175            model: self,
176            anchor,
177            cursor: Some(anchor),
178        }
179    }
180
181    /// Every coedge of every boundary loop of `face_id` (its outer loop and
182    /// any holes).
183    pub fn iterate_face_coedges(&self, face_id: FaceId) -> impl Iterator<Item = CoedgeId> + '_ {
184        FaceCoedges {
185            model: self,
186            boundaries: self.faces[&face_id]
187                .boundaries()
188                .collect::<Vec<_>>()
189                .into_iter(),
190            current: None,
191        }
192    }
193
194    /// The distinct vertices referenced by `solid_id`'s faces, as an
195    /// iterator borrowing `self` — see [`SolidVertices`]'s own doc comment.
196    pub fn iter_solid_vertices(
197        &self,
198        solid_id: SolidId,
199    ) -> GeopResult<impl Iterator<Item = VertexId> + '_> {
200        let faces = self.solid_faces(solid_id)?;
201        Ok(SolidVertices {
202            model: self,
203            faces: faces.into_iter(),
204            coedges: Vec::new().into_iter(),
205            seen: std::collections::HashSet::new(),
206            pending: std::collections::VecDeque::new(),
207        })
208    }
209
210    /// The distinct edges referenced by `solid_id`'s faces, as an iterator
211    /// borrowing `self` — see [`SolidVertices`]'s own doc comment.
212    pub fn iter_solid_edges(
213        &self,
214        solid_id: SolidId,
215    ) -> GeopResult<impl Iterator<Item = EdgeId> + '_> {
216        let faces = self.solid_faces(solid_id)?;
217        Ok(SolidEdges {
218            model: self,
219            faces: faces.into_iter(),
220            coedges: Vec::new().into_iter(),
221            seen: std::collections::HashSet::new(),
222        })
223    }
224
225    /// Which of `face_id`'s boundaries contains `coedge` — its outer loop or
226    /// one of its holes — found by traversing each `Loop` boundary's `.next`
227    /// chain. A face's boundaries are disjoint loops, so at most one can
228    /// contain any given coedge.
229    ///
230    /// Returns [`BoundaryIndex`] rather than a bare position, because callers
231    /// invariably need to know whether they found the outer loop: joining two
232    /// holes, joining a hole to the outer loop, and joining two points of the
233    /// outer loop are three different restructurings (see
234    /// `Model::splice_edge_into_face`).
235    pub fn find_boundary_containing(
236        &self,
237        face_id: FaceId,
238        coedge: CoedgeId,
239    ) -> GeopResult<BoundaryIndex> {
240        let face = &self.faces[&face_id];
241        let contains = |boundary: BoundaryType| match boundary {
242            BoundaryType::Loop(anchor) => self.iterate_loop_coedges(anchor).any(|c| c == coedge),
243            BoundaryType::Vertex(_) => false,
244        };
245        if contains(face.outer) {
246            return Ok(BoundaryIndex::Outer);
247        }
248        face.holes
249            .iter()
250            .position(|&h| contains(h))
251            .map(BoundaryIndex::Hole)
252            .ok_or_else(|| {
253                GeopError::new(format!(
254                    "Model::find_boundary_containing: could not find a boundary containing coedge={coedge} on face={face_id}"
255                ))
256            })
257    }
258
259    /// Drop the hole `index` names from `face_id`.
260    ///
261    /// Errors on [`BoundaryIndex::Outer`]: a face without an outer boundary
262    /// is not a face. An operation that genuinely consumes a face's outer
263    /// loop is deleting the face, and must say so (see `kef`) rather than
264    /// leaving one behind with nothing bounding it.
265    pub fn remove_boundary(&mut self, face_id: FaceId, index: BoundaryIndex) -> GeopResult<()> {
266        let BoundaryIndex::Hole(i) = index else {
267            return Err(GeopError::new(format!(
268                "Model::remove_boundary: refusing to remove face={face_id}'s outer boundary — a face must always have exactly one"
269            )));
270        };
271        let face = self.get_face_mut(face_id)?;
272        if i >= face.holes.len() {
273            return Err(GeopError::new(format!(
274                "Model::remove_boundary: face={face_id} has no hole at index {i}"
275            )));
276        }
277        face.holes.remove(i);
278        Ok(())
279    }
280
281    /// Every `FaceId` across every shell of `solid_id`.
282    pub fn solid_faces(&self, solid_id: SolidId) -> GeopResult<Vec<FaceId>> {
283        let solid = self.get_solid(solid_id)?;
284        let mut faces = Vec::new();
285        for &shell_id in &solid.shells {
286            faces.extend(self.get_shell(shell_id)?.faces.iter().copied());
287        }
288        Ok(faces)
289    }
290}
geop_core_topology/model/iterate.rs

geop_core_topology/model/
iterate.rs
