mesh_graph/ops/add/
edge.rs

1use tracing::{error, instrument};
2
3use crate::{Halfedge, HalfedgeId, MeshGraph, VertexId, error_none};
4
5impl MeshGraph {
6    /// Inserts a pair of halfedges and connects them to the given vertices (from and to the halfedge) and each other as twins.
7    /// If the edge already exists or partially exists,
8    /// it returns the existing edge while creating any missing halfedges.
9    ///
10    /// See also [`add_edge`].
11    #[instrument(skip(self))]
12    pub fn add_or_get_edge(
13        &mut self,
14        start_vertex_id: VertexId,
15        end_vertex_id: VertexId,
16    ) -> AddOrGetEdge {
17        let ret = self
18            .add_or_get_edge_inner(start_vertex_id, end_vertex_id)
19            .unwrap_or_else(|| {
20                let start_to_end_he_id = self.add_halfedge(start_vertex_id, end_vertex_id);
21                let twin_he_id = self.add_halfedge(end_vertex_id, start_vertex_id);
22
23                AddOrGetEdge {
24                    start_to_end_he_id,
25                    twin_he_id,
26                    new_start_to_end: true,
27                    new_twin: true,
28                }
29            });
30
31        // insert_or_get_edge_inner ensures that both halfedges exist.
32        self.halfedges[ret.start_to_end_he_id].twin = Some(ret.twin_he_id);
33        self.halfedges[ret.twin_he_id].twin = Some(ret.start_to_end_he_id);
34
35        if let Some(start_v) = self.vertices.get_mut(start_vertex_id) {
36            start_v.outgoing_halfedge = Some(ret.start_to_end_he_id);
37        } else {
38            error!("Vertex not found");
39        }
40
41        if let Some(end_v) = self.vertices.get_mut(end_vertex_id) {
42            end_v.outgoing_halfedge = Some(ret.twin_he_id);
43        } else {
44            error!("Vertex not found");
45        }
46
47        ret
48    }
49
50    fn add_or_get_edge_inner(
51        &mut self,
52        start_vertex_id: VertexId,
53        end_vertex_id: VertexId,
54    ) -> Option<AddOrGetEdge> {
55        let mut he1_id = self.halfedge_from_to(start_vertex_id, end_vertex_id);
56        let mut he2_id = self.halfedge_from_to(end_vertex_id, start_vertex_id);
57        let mut new1 = false;
58        let mut new2 = false;
59
60        match (he1_id, he2_id) {
61            (Some(h1_id), Some(h2_id)) => {
62                let h1 = self
63                    .halfedges
64                    .get(h1_id)
65                    .or_else(error_none!("Halfedge not found"))?;
66
67                let h2 = self
68                    .halfedges
69                    .get(h2_id)
70                    .or_else(error_none!("Halfedge not found"))?;
71
72                if h1.twin != Some(h2_id) || h2.twin != Some(h1_id) {
73                    error!("Halfedge twins are not consistent.");
74                }
75            }
76            (Some(_h1_id), None) => {
77                he2_id = Some(self.add_halfedge(end_vertex_id, start_vertex_id));
78                new2 = true;
79            }
80            (None, Some(_h2_id)) => {
81                he1_id = Some(self.add_halfedge(start_vertex_id, end_vertex_id));
82                new1 = true;
83            }
84            (None, None) => {
85                // the outer method will handle this case
86                return None;
87            }
88        }
89
90        // we just made sure that h1_id and h2_id are Some(_)
91        let start_to_end_he_id = he1_id.unwrap();
92        let twin_he_id = he2_id.unwrap();
93
94        Some(AddOrGetEdge {
95            start_to_end_he_id,
96            twin_he_id,
97            new_start_to_end: new1,
98            new_twin: new2,
99        })
100    }
101
102    /// Inserts a pair of halfedges and connects them to the given vertices (from and to the halfedge) and each other as twins.
103    /// This creates two halfedges wether the vertices already have an edge between them or not.
104    ///
105    /// If you don't want this, consider using [`add_or_get_edge`] instead.
106    pub fn add_edge(&mut self, start_vertex: VertexId, end_vertex: VertexId) -> AddEdge {
107        let start_to_end_he_id = self.add_halfedge(start_vertex, end_vertex);
108        let twin_he_id = self.add_halfedge(end_vertex, start_vertex);
109
110        // Just inserted above
111        self.halfedges[start_to_end_he_id].twin = Some(twin_he_id);
112        self.halfedges[twin_he_id].twin = Some(start_to_end_he_id);
113
114        AddEdge {
115            start_to_end_he_id,
116            twin_he_id,
117        }
118    }
119
120    /// Inserts a halfedge into the mesh graph. It only connects the halfedge to the given end vertex but not the reverse.
121    /// It also doesn't do any other connections.
122    ///
123    /// It does insert into `self.outgoing_halfedges`.
124    ///
125    /// Use [`insert_or_get_edge`] instead of this when you can to lower the chance of creating an invalid graph.
126    pub fn add_halfedge(&mut self, start_vertex: VertexId, end_vertex: VertexId) -> HalfedgeId {
127        let halfedge = Halfedge {
128            end_vertex,
129            next: None,
130            twin: None,
131            face: None,
132        };
133        let he_id = self.halfedges.insert(halfedge);
134
135        self.outgoing_halfedges
136            .entry(start_vertex)
137            .expect("we just insterted into halfedges above")
138            .or_default()
139            .push(he_id);
140
141        he_id
142    }
143}
144
145/// Return value of `add_or_get_edge`
146pub struct AddOrGetEdge {
147    /// Id of the halfedge from start vertex to end vertex
148    pub start_to_end_he_id: HalfedgeId,
149    /// Id of the halfedge from end vertex to start vertex
150    pub twin_he_id: HalfedgeId,
151    /// Whether the halfedge from start vertex to end vertex was newly created
152    pub new_start_to_end: bool,
153    /// Whether the halfedge from end vertex to start vertex was newly created
154    pub new_twin: bool,
155}
156
157impl AddOrGetEdge {
158    /// Return the ids of the newly created halfedges
159    pub fn created_he_ids(&self) -> Vec<HalfedgeId> {
160        let mut he_ids = vec![];
161        if self.new_start_to_end {
162            he_ids.push(self.start_to_end_he_id);
163        }
164        if self.new_twin {
165            he_ids.push(self.twin_he_id);
166        }
167        he_ids
168    }
169}
170
171/// Return value of `add_edge`
172pub struct AddEdge {
173    /// Id of the halfedge from start vertex to end vertex
174    pub start_to_end_he_id: HalfedgeId,
175    /// Id of the halfedge from end vertex to start vertex
176    pub twin_he_id: HalfedgeId,
177}
mesh_graph/ops/add/edge.rs

mesh_graph/ops/add/
edge.rs
