mesh_graph/ops/
insert.rs

1use glam::Vec3;
2use slotmap::SecondaryMap;
3use tracing::{error, instrument};
4
5use crate::{Face, FaceId, Halfedge, HalfedgeId, MeshGraph, Vertex, VertexId, error_none};
6
7impl MeshGraph {
8    /// Inserts a vertex and it's position into the mesh graph.
9    /// It doesn't do any connections.
10    pub fn insert_vertex(&mut self, position: Vec3) -> VertexId {
11        let vertex = Vertex::default();
12        let vertex_id = self.vertices.insert(vertex);
13        self.positions.insert(vertex_id, position);
14
15        vertex_id
16    }
17
18    /// Inserts a pair of halfedges and connects them to the given vertices (from and to the halfedge) and each other as twins.
19    /// If the edge already exists or partially exists,
20    /// it returns the existing edge while creating any missing halfedges.
21    ///
22    /// Returns the pair of halfedge ids `(he1, he2)` where `he1` is the halfedge connecting `start_vertex` to `end_vertex`
23    /// and `he2` is the twin halfedge connecting `end_vertex` to `start_vertex`.
24    pub fn insert_or_get_edge(
25        &mut self,
26        start_vertex_id: VertexId,
27        end_vertex_id: VertexId,
28        vertex_to_outgoing_halfedges: &mut SecondaryMap<VertexId, Vec<HalfedgeId>>,
29    ) -> (HalfedgeId, HalfedgeId) {
30        let (he1_id, he2_id) = self
31            .insert_or_get_edge_inner(start_vertex_id, end_vertex_id, vertex_to_outgoing_halfedges)
32            .unwrap_or_else(|| {
33                let he1_id = self.insert_halfedge(end_vertex_id);
34                let he2_id = self.insert_halfedge(start_vertex_id);
35
36                // in `insert_or_get_edge_inner` we made sure that the outgoing Vecs exist
37                vertex_to_outgoing_halfedges[start_vertex_id].push(he1_id);
38                vertex_to_outgoing_halfedges[end_vertex_id].push(he2_id);
39
40                (he1_id, he2_id)
41            });
42
43        // insert_or_get_edge_inner ensures that both halfedges exist.
44        self.halfedges[he1_id].twin = Some(he2_id);
45        self.halfedges[he2_id].twin = Some(he1_id);
46
47        if let Some(start_v) = self.vertices.get_mut(start_vertex_id) {
48            start_v.outgoing_halfedge = Some(he1_id);
49        } else {
50            error!("Vertex not found");
51        }
52
53        if let Some(end_v) = self.vertices.get_mut(end_vertex_id) {
54            end_v.outgoing_halfedge = Some(he2_id);
55        } else {
56            error!("Vertex not found");
57        }
58
59        (he1_id, he2_id)
60    }
61
62    fn halfedge_from_to(
63        &self,
64        start_vertex_id: VertexId,
65        end_vertex_id: VertexId,
66        vertex_to_outgoing_halfedges: &mut SecondaryMap<VertexId, Vec<HalfedgeId>>,
67    ) -> Option<HalfedgeId> {
68        vertex_to_outgoing_halfedges
69            .entry(start_vertex_id)
70            .or_else(error_none!("Start vertex not found"))?
71            .or_insert_with(Vec::new)
72            .iter()
73            .copied()
74            .find(|he_id| {
75                self.halfedges
76                    .get(*he_id)
77                    .or_else(error_none!("Halfedge not found"))
78                    .is_some_and(|he| he.end_vertex == end_vertex_id)
79            })
80    }
81
82    fn insert_or_get_edge_inner(
83        &mut self,
84        start_vertex_id: VertexId,
85        end_vertex_id: VertexId,
86        vertex_to_outgoing_halfedges: &mut SecondaryMap<VertexId, Vec<HalfedgeId>>,
87    ) -> Option<(HalfedgeId, HalfedgeId)> {
88        let mut h1_id =
89            self.halfedge_from_to(start_vertex_id, end_vertex_id, vertex_to_outgoing_halfedges);
90        let mut h2_id =
91            self.halfedge_from_to(end_vertex_id, start_vertex_id, vertex_to_outgoing_halfedges);
92
93        match (h1_id, h2_id) {
94            (Some(h1_id), Some(h2_id)) => {
95                let h1 = self
96                    .halfedges
97                    .get(h1_id)
98                    .or_else(error_none!("Halfedge not found"))?;
99
100                let h2 = self
101                    .halfedges
102                    .get(h2_id)
103                    .or_else(error_none!("Halfedge not found"))?;
104
105                if h1.twin != Some(h2_id) || h2.twin != Some(h1_id) {
106                    error!("Halfedge twins are not consistent.");
107                }
108            }
109            (Some(_h1_id), None) => {
110                h2_id = Some(self.insert_halfedge(start_vertex_id));
111                // we made sure at the start that the outgoing Vec exists
112                vertex_to_outgoing_halfedges[end_vertex_id].push(h2_id.unwrap());
113            }
114            (None, Some(_h2_id)) => {
115                h1_id = Some(self.insert_halfedge(end_vertex_id));
116                // we made sure at the start that the outgoing Vec exists
117                vertex_to_outgoing_halfedges[start_vertex_id].push(h1_id.unwrap());
118            }
119            (None, None) => {
120                // the outer method will handle this case
121                return None;
122            }
123        }
124
125        // we just made sure that h1_id and h2_id are Some(_)
126        let h1_id = h1_id.unwrap();
127        let h2_id = h2_id.unwrap();
128
129        Some((h1_id, h2_id))
130    }
131
132    /// Inserts a halfedge into the mesh graph. It only connects the halfedge to the given end vertex but not the reverse.
133    /// It also doesn't do any other connections.
134    ///
135    /// Use [`insert_or_get_edge`] instead of this when you can to lower the chance of creating an invalid graph.
136    pub fn insert_halfedge(&mut self, end_vertex: VertexId) -> HalfedgeId {
137        let halfedge = Halfedge {
138            end_vertex,
139            next: None,
140            twin: None,
141            face: None,
142        };
143        self.halfedges.insert(halfedge)
144    }
145
146    /// Inserts a face into the mesh graph. It connects the halfedges to the face and the face to the first halfedge.
147    /// Additionally it connects the halfedges' `next` loop around the face.
148    #[instrument(skip(self))]
149    pub fn insert_face(
150        &mut self,
151        he1_id: HalfedgeId,
152        he2_id: HalfedgeId,
153        he3_id: HalfedgeId,
154    ) -> FaceId {
155        let face_id = self.faces.insert_with_key(|id| Face {
156            halfedge: he1_id,
157            index: self.next_index,
158            id,
159        });
160
161        self.index_to_face_id.insert(self.next_index, face_id);
162
163        self.next_index += 1;
164
165        for (he_id, next_he_id) in [(he1_id, he2_id), (he2_id, he3_id), (he3_id, he1_id)] {
166            if let Some(halfedge) = self.halfedges.get_mut(he_id) {
167                halfedge.face = Some(face_id);
168                halfedge.next = Some(next_he_id);
169            } else {
170                error!("Halfedge not found");
171            }
172        }
173
174        face_id
175    }
176}
mesh_graph/ops/insert.rs

mesh_graph/ops/
insert.rs
