geop_ops_booleans/
naming.rs

1//! How a boolean names what it creates.
2//!
3//! Everything is named after what it was made from, in terms of the names
4//! the two operands had *before* the boolean — their *origins*. A piece of an
5//! edge split in two has the edge's origin, and so does a piece of that
6//! piece; likewise for faces. With `N` the boolean's [`Namer`]:
7//!
8//! | entity | name |
9//! |---|---|
10//! | the result solid | `N` |
11//! | vertex where edges `E1 < E2` cross | `N(E1,E2,i,n)`: the `i`-th of their `n` crossings, counted along `E1` |
12//! | vertex where edge `E` pierces face `F` | `N(E,F,i,n)`: the `i`-th of the `n` piercings, counted along `E` |
13//! | piece of edge `E` starting at vertex `V` | `N(E,V)` — the piece at `E`'s own start keeps the name `E` |
14//! | edge traced along faces `F1 < F2` from vertex `P` to `Q` (`P < Q`) | `N(F1,F2,P,Q)`, with a trailing `,k` only if several such edges join the same `P` and `Q` |
15//! | piece of face `F` split off along edge `E` | `N(F,E)` — the other piece keeps the name `F` |
16//!
17//! `<` is the order of the names as strings, so each name is independent of
18//! which operand came first and of the order the algorithm found things in.
19//! The one exception is the trailing `,k` of a traced edge: two intersection
20//! branches with the same ends on the same faces (an arc and its complement)
21//! are told apart only by when they were traced.
22//!
23//! A crossing's `i` and `n` are only known once every crossing of those two
24//! entities has been found, and every other name above builds on vertex
25//! names. So [`BooleanNaming`] hands out a provisional name while the
26//! boolean runs, remembers what each entity was made from, and
27//! [`BooleanNaming::finish`] settles all names at once when it is done.
28
29use std::collections::{BTreeMap, HashMap};
30
31use geop_core_math::{
32    geop_error::{GeopError, GeopResult},
33    scalars::Scalar,
34};
35use geop_core_part::{Namer, Part, RefId};
36use geop_core_topology::{EdgeId, FaceId, SolidId, VertexId};
37
38/// What a created entity was made from — everything its final name derives
39/// from (see the module docs).
40enum Recipe<S: Scalar> {
41    /// A vertex where `along` (an edge's origin) meets `other` (an edge's or
42    /// a face's origin), at parameter `t` of `along`.
43    Crossing {
44        vertex: VertexId,
45        along: String,
46        other: String,
47        t: S,
48    },
49    /// A piece of an edge with origin `origin`, starting at `start`.
50    EdgePiece {
51        edge: EdgeId,
52        origin: String,
53        start: VertexId,
54    },
55    /// An edge traced along faces with origins `faces`, between `ends`.
56    Trace {
57        edge: EdgeId,
58        faces: [String; 2],
59        ends: [VertexId; 2],
60    },
61    /// A piece of a face with origin `origin`, split off along `edge`.
62    FacePiece {
63        face: FaceId,
64        origin: String,
65        edge: EdgeId,
66    },
67}
68
69/// The naming bookkeeping of one boolean, see the module docs.
70pub struct BooleanNaming<S: Scalar> {
71    namer: Namer,
72    edge_origin: HashMap<EdgeId, String>,
73    face_origin: HashMap<FaceId, String>,
74    recipes: Vec<Recipe<S>>,
75}
76
77impl<S: Scalar> BooleanNaming<S> {
78    /// Starts naming a boolean of `solids`, remembering the names their
79    /// edges and faces have now as those entities' origins.
80    pub fn new(part: &Part<S>, namer: &Namer, solids: &[SolidId]) -> GeopResult<Self> {
81        let model = part.topology();
82        let name = |id: RefId| {
83            part.name_of(id)
84                .map(str::to_string)
85                .ok_or_else(|| GeopError::new(format!("boolean: operand entity {id} has no name")))
86        };
87        let mut edge_origin = HashMap::new();
88        let mut face_origin = HashMap::new();
89        for &solid in solids {
90            for edge in model.iter_solid_edges(solid)? {
91                edge_origin.insert(edge, name(edge.into())?);
92            }
93            for face in model.solid_faces(solid)? {
94                face_origin.insert(face, name(face.into())?);
95            }
96        }
97        Ok(Self {
98            namer: namer.clone(),
99            edge_origin,
100            face_origin,
101            recipes: Vec::new(),
102        })
103    }
104
105    /// The name for the next entity, until [`BooleanNaming::finish`]
106    /// replaces it. `~` never appears in a final name.
107    pub fn provisional(&self) -> String {
108        self.namer.name(&[&format!("~{}", self.recipes.len())])
109    }
110
111    pub fn edge_origin(&self, edge: EdgeId) -> GeopResult<&str> {
112        self.edge_origin
113            .get(&edge)
114            .map(String::as_str)
115            .ok_or_else(|| {
116                GeopError::new(format!("boolean naming: edge {edge} has no known origin"))
117            })
118    }
119
120    pub fn face_origin(&self, face: FaceId) -> GeopResult<&str> {
121        self.face_origin
122            .get(&face)
123            .map(String::as_str)
124            .ok_or_else(|| {
125                GeopError::new(format!("boolean naming: face {face} has no known origin"))
126            })
127    }
128
129    /// Records that `vertex` was created where edge `edge_a` (at parameter
130    /// `t_a`) crosses edge `edge_b` (at `t_b`).
131    pub fn edge_crossing(
132        &mut self,
133        vertex: VertexId,
134        (edge_a, t_a): (EdgeId, S),
135        (edge_b, t_b): (EdgeId, S),
136    ) -> GeopResult<()> {
137        let a = self.edge_origin(edge_a)?.to_string();
138        let b = self.edge_origin(edge_b)?.to_string();
139        let ((along, t), other) = if a <= b { ((a, t_a), b) } else { ((b, t_b), a) };
140        self.recipes.push(Recipe::Crossing {
141            vertex,
142            along,
143            other,
144            t,
145        });
146        Ok(())
147    }
148
149    /// Records that `vertex` was created where `edge` (at parameter `t`)
150    /// pierces `face`.
151    pub fn piercing(
152        &mut self,
153        vertex: VertexId,
154        edge: EdgeId,
155        t: S,
156        face: FaceId,
157    ) -> GeopResult<()> {
158        let along = self.edge_origin(edge)?.to_string();
159        let other = self.face_origin(face)?.to_string();
160        self.recipes.push(Recipe::Crossing {
161            vertex,
162            along,
163            other,
164            t,
165        });
166        Ok(())
167    }
168
169    /// Records that `new_edge` was split off `edge` at `start`; it inherits
170    /// `edge`'s origin.
171    pub fn edge_split(
172        &mut self,
173        edge: EdgeId,
174        new_edge: EdgeId,
175        start: VertexId,
176    ) -> GeopResult<()> {
177        let origin = self.edge_origin(edge)?.to_string();
178        self.edge_origin.insert(new_edge, origin.clone());
179        self.recipes.push(Recipe::EdgePiece {
180            edge: new_edge,
181            origin,
182            start,
183        });
184        Ok(())
185    }
186
187    /// Records that `edge` was traced along `face_a` and `face_b` between
188    /// `ends`.
189    pub fn trace(
190        &mut self,
191        edge: EdgeId,
192        face_a: FaceId,
193        face_b: FaceId,
194        ends: [VertexId; 2],
195    ) -> GeopResult<()> {
196        let faces = [
197            self.face_origin(face_a)?.to_string(),
198            self.face_origin(face_b)?.to_string(),
199        ];
200        self.recipes.push(Recipe::Trace { edge, faces, ends });
201        Ok(())
202    }
203
204    /// Records that splicing `edge` into `face` split off `new_face`, if it
205    /// did; `new_face` inherits `face`'s origin.
206    pub fn face_split(
207        &mut self,
208        face: FaceId,
209        edge: EdgeId,
210        new_face: Option<FaceId>,
211    ) -> GeopResult<()> {
212        let Some(new_face) = new_face else {
213            return Ok(());
214        };
215        let origin = self.face_origin(face)?.to_string();
216        self.face_origin.insert(new_face, origin.clone());
217        self.recipes.push(Recipe::FacePiece {
218            face: new_face,
219            origin,
220            edge,
221        });
222        Ok(())
223    }
224
225    /// Gives every entity created so far its final name, see the module
226    /// docs. Entities that were created and have since been deleted again
227    /// (an edge piece merged into a coincident edge, say) are skipped.
228    pub fn finish(self, part: &mut Part<S>) -> GeopResult<()> {
229        let n = &self.namer;
230        let ctx = |e: GeopError| e.with_context(format!("naming the entities of {}", n.root()));
231        let alive = |part: &Part<S>, id: RefId| part.name_of(id).is_some();
232        let name_of = |part: &Part<S>, id: RefId| -> GeopResult<String> {
233            part.name_of(id).map(str::to_string).ok_or_else(|| {
234                ctx(GeopError::new(format!(
235                    "{id} is referred to by a name being built, but no longer exists"
236                )))
237            })
238        };
239
240        // Vertices first: every other name is built from vertex names.
241        let mut crossings: BTreeMap<(&str, &str), Vec<(VertexId, S)>> = BTreeMap::new();
242        for recipe in &self.recipes {
243            if let Recipe::Crossing {
244                vertex,
245                along,
246                other,
247                t,
248            } = recipe
249                && alive(part, (*vertex).into())
250            {
251                crossings
252                    .entry((along.as_str(), other.as_str()))
253                    .or_default()
254                    .push((*vertex, *t));
255            }
256        }
257        for ((along, other), mut vertices) in crossings {
258            // Distinct crossings of one edge have disjoint parameters, so
259            // any point of each interval orders them.
260            vertices.sort_by(|a, b| a.1.to_f64().total_cmp(&b.1.to_f64()));
261            let count = vertices.len().to_string();
262            for (i, (vertex, _)) in vertices.iter().enumerate() {
263                part.rename(*vertex, n.name(&[along, other, &i.to_string(), &count]))
264                    .map_err(ctx)?;
265            }
266        }
267
268        let mut traces: BTreeMap<String, Vec<EdgeId>> = BTreeMap::new();
269        for recipe in &self.recipes {
270            match recipe {
271                Recipe::EdgePiece {
272                    edge,
273                    origin,
274                    start,
275                } if alive(part, (*edge).into()) => {
276                    let start = name_of(part, (*start).into())?;
277                    part.rename(*edge, n.name(&[origin, &start])).map_err(ctx)?;
278                }
279                Recipe::Trace { edge, faces, ends } if alive(part, (*edge).into()) => {
280                    let mut faces = faces.clone();
281                    faces.sort();
282                    let mut ends = [
283                        name_of(part, ends[0].into())?,
284                        name_of(part, ends[1].into())?,
285                    ];
286                    ends.sort();
287                    traces
288                        .entry(n.name(&[&faces[0], &faces[1], &ends[0], &ends[1]]))
289                        .or_default()
290                        .push(*edge);
291                }
292                _ => {}
293            }
294        }
295        for (name, edges) in traces {
296            if let [edge] = edges[..] {
297                part.rename(edge, name).map_err(ctx)?;
298            } else {
299                for (k, edge) in edges.into_iter().enumerate() {
300                    // `name` ends in `)`: append the index as one more
301                    // argument.
302                    let indexed = format!("{},{k})", &name[..name.len() - 1]);
303                    part.rename(edge, indexed).map_err(ctx)?;
304                }
305            }
306        }
307
308        // Faces last: they are named after edges.
309        for recipe in &self.recipes {
310            if let Recipe::FacePiece { face, origin, edge } = recipe
311                && alive(part, (*face).into())
312            {
313                let edge = name_of(part, (*edge).into())?;
314                part.rename(*face, n.name(&[origin, &edge])).map_err(ctx)?;
315            }
316        }
317        Ok(())
318    }
319}
geop_ops_booleans/naming.rs

geop_ops_booleans/
naming.rs
