math_utils/geometry/mesh/
edge_triangle.rs

1//! Edge-triangle meshes
2// code from GeometricTools:
3// <https://github.com/davideberly/GeometricTools/blob/f78dd0b65bc3a0a4723586de6991dd2c339b08ad/GTE/Mathematics/ETManifoldMesh.h>
4// <https://github.com/davideberly/GeometricTools/blob/f78dd0b65bc3a0a4723586de6991dd2c339b08ad/GTE/Mathematics/VETManifoldMesh.h>
5
6use std::collections::{BTreeMap, BTreeSet};
7#[cfg(feature = "derive_serdes")]
8use serde::{Deserialize, Serialize};
9
10#[derive(Clone, Debug, Default, Eq, PartialEq)]
11#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
12pub struct VertexEdgeTriangleMesh {
13  et_mesh  : EdgeTriangleMesh,
14  vertices : BTreeMap <u32, Vertex>
15}
16
17#[derive(Clone, Debug, Default, Eq, PartialEq)]
18#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
19pub struct EdgeTriangleMesh {
20  pub(crate) edges     : BTreeMap <EdgeKey,     Edge>,
21  pub(crate) triangles : BTreeMap <TriangleKey, Triangle>,
22}
23
24/// Note edge-keys are *un-ordered*
25#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
26#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
27pub struct EdgeKey (u32, u32);
28#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
29#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
30pub struct TriangleKey (u32, u32, u32);
31
32#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
33#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
34pub struct Vertex {
35  index              : u32,
36  adjacent_vertices  : BTreeSet <u32>,
37  adjacent_edges     : BTreeSet <EdgeKey>,
38  adjacent_triangles : BTreeSet <TriangleKey>
39}
40
41#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
42#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
43pub struct Edge {
44  vertices  : [u32; 2],
45  triangles : [Option <TriangleKey>; 2]
46}
47
48#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
49#[cfg_attr(feature = "derive_serdes", derive(Serialize, Deserialize))]
50pub struct Triangle {
51  /// Vertices listed in counter-clockwise order
52  vertices           : [u32; 3],
53  edges              : [Option <EdgeKey>; 3],
54  /// Triangle `i` points to the adjecent triangle sharing edge `i`
55  adjacent_triangles : [Option <TriangleKey>; 3],
56}
57
58impl EdgeTriangleMesh {
59  #[inline]
60  pub fn get_edge (&self, key : &EdgeKey) -> Option <&Edge> {
61    self.edges.get (key)
62  }
63  #[inline]
64  pub fn get_triangle (&self, key : &TriangleKey) -> Option <&Triangle> {
65    self.triangles.get (key)
66  }
67  #[inline]
68  pub const fn edges (&self) -> &BTreeMap <EdgeKey, Edge> {
69    &self.edges
70  }
71  #[inline]
72  pub const fn triangles (&self) -> &BTreeMap <TriangleKey, Triangle> {
73    &self.triangles
74  }
75
76  /// Returns None if triangle already exists in the mesh
77  pub fn insert (&mut self, v0 : u32, v1 : u32, v2 : u32) -> Option <Triangle> {
78    self.insert_ (v0, v1, v2).map (|inserted| inserted.1)
79  }
80  fn insert_ (&mut self, v0 : u32, v1 : u32, v2 : u32)
81    -> Option <(TriangleKey, Triangle)>
82  {
83    let triangle_key = TriangleKey (v0, v1, v2);
84    if self.triangles.contains_key (&triangle_key) {
85      return None
86    }
87    let mut triangle = Triangle::new (v0, v1, v2);
88    let mut i0 = 2;
89    let mut i1 = 0;
90    while i1 < 3 {
91      let edge_key = EdgeKey::new (triangle.vertices[i0], triangle.vertices[i1]);
92      if let Some (mut edge) = self.edges.get (&edge_key).copied() {
93        // TODO: the original implementation has a "manifold" check here
94        if edge.triangles[1].is_some() {
95          return None
96        }
97        edge.triangles[1] = Some (triangle_key);
98        let adjacent_key  = edge.triangles[0].unwrap();
99        let adjacent      = self.triangles.get_mut (&adjacent_key).unwrap();
100        for (i, e_key) in adjacent.edges.iter().enumerate() {
101          if e_key == &Some (edge_key) {
102            adjacent.adjacent_triangles[i] = Some (triangle_key);
103            break
104          }
105        }
106        triangle.edges[i0] = Some (edge_key);
107        triangle.adjacent_triangles[i0] = Some (adjacent_key);
108        *self.edges.get_mut (&edge_key).unwrap() = edge;
109      } else {
110        let mut new_edge = Edge::new (edge_key.0, edge_key.1);
111        new_edge.triangles[0] = Some (triangle_key);
112        triangle.edges[i0]    = Some (edge_key);
113        let inserted = self.edges.insert (edge_key, new_edge);
114        debug_assert!(inserted.is_none());
115      }
116      // iter
117      i0 = i1;
118      i1 += 1;
119    }
120    let inserted = self.triangles.insert (triangle_key, triangle);
121    debug_assert!(inserted.is_none());
122    Some ((triangle_key, triangle))
123  }
124
125  #[expect(clippy::missing_panics_doc)]
126  pub fn remove (&mut self, v0 : u32, v1 : u32, v2 : u32) -> bool {
127    let triangle_key = TriangleKey (v0, v1, v2);
128    if let Some (triangle) = self.triangles.remove (&triangle_key) {
129      for (i, edge_key) in triangle.edges.iter().map (|k| k.unwrap()).enumerate() {
130        let edge = self.edges.get_mut (&edge_key).unwrap();
131        if edge.triangles[0] == Some (triangle_key) {
132          edge.triangles[0] = edge.triangles[1];
133          edge.triangles[1] = None;
134        } else if edge.triangles[1] == Some (triangle_key) {
135          edge.triangles[1] = None;
136        } else {
137          unreachable!()
138        }
139        if edge.triangles[0].is_none() && edge.triangles[1].is_none() {
140          self.edges.remove (&edge_key);
141        }
142        if let Some (adjacent_key) = triangle.adjacent_triangles[i] {
143          let adjacent = self.triangles.get_mut (&adjacent_key).unwrap();
144          for key in adjacent.adjacent_triangles.iter_mut() {
145            if key == &Some (triangle_key) {
146              *key = None;
147              break
148            }
149          }
150        }
151      }
152      true
153    } else {
154      false
155    }
156  }
157
158  // TODO: more methods
159}
160
161impl VertexEdgeTriangleMesh {
162  #[inline]
163  pub fn with_vertex (vertex : Vertex) -> Self {
164    let mut mesh = VertexEdgeTriangleMesh::default();
165    mesh.vertices.insert (vertex.index, vertex);
166    mesh
167  }
168  #[inline]
169  pub fn with_edge (edge : Edge) -> Self {
170    let mut mesh = VertexEdgeTriangleMesh::default();
171    let edge_key = EdgeKey::new (edge.vertices[0], edge.vertices[1]);
172    let v0 = Vertex {
173      index: edge_key.0,
174      adjacent_vertices:  BTreeSet::from_iter ([edge_key.1]),
175      adjacent_edges:     BTreeSet::from_iter ([edge_key]),
176      adjacent_triangles: BTreeSet::new()
177    };
178    let v1 = Vertex {
179      index: edge_key.1,
180      adjacent_vertices:  BTreeSet::from_iter ([edge_key.0]),
181      adjacent_edges:     BTreeSet::from_iter ([edge_key]),
182      adjacent_triangles: BTreeSet::new()
183    };
184    mesh.vertices.insert (v0.index, v0);
185    mesh.vertices.insert (v1.index, v1);
186    mesh.et_mesh.edges.insert (edge_key, edge);
187    mesh
188  }
189  #[inline]
190  pub fn get_vertex (&self, index : u32) -> Option <&Vertex> {
191    self.vertices.get (&index)
192  }
193
194  #[inline]
195  pub const fn edges (&self) -> &BTreeMap <EdgeKey, Edge> {
196    self.et_mesh.edges()
197  }
198
199  #[inline]
200  pub const fn triangles (&self) -> &BTreeMap <TriangleKey, Triangle> {
201    self.et_mesh.triangles()
202  }
203
204  #[inline]
205  pub const fn vertices (&self) -> &BTreeMap <u32, Vertex> {
206    &self.vertices
207  }
208
209  /// Returns None if triangle already exists in the mesh
210  #[expect(clippy::missing_panics_doc)]
211  pub fn insert (&mut self, v0 : u32, v1 : u32, v2 : u32) -> Option <Triangle> {
212    let (triangle_key, triangle) = self.et_mesh.insert_ (v0, v1, v2)?;
213    for index in triangle.vertices.iter() {
214      let vertex = self.vertices.entry (*index).or_insert_with (|| Vertex::new (*index));
215      vertex.adjacent_triangles.insert (triangle_key);
216      for edge_key in triangle.edges.iter().map (|k| k.unwrap()) {
217        let edge = self.et_mesh.edges.get (&edge_key).unwrap();
218        if edge.vertices[0] == *index {
219          vertex.adjacent_vertices.insert (edge.vertices[1]);
220          vertex.adjacent_edges.insert (edge_key);
221        } else if edge.vertices[1] == *index {
222          vertex.adjacent_vertices.insert (edge.vertices[0]);
223          vertex.adjacent_edges.insert (edge_key);
224        }
225      }
226    }
227    Some (triangle)
228  }
229
230  #[expect(clippy::missing_panics_doc)]
231  pub fn remove (&mut self, v0 : u32, v1 : u32, v2 : u32) -> bool {
232    let triangle_key = TriangleKey (v0, v1, v2);
233    if let Some (triangle) = self.et_mesh.triangles.get (&triangle_key) {
234      for index in triangle.vertices.iter() {
235        let vertex = self.vertices.get_mut (index).unwrap();
236        for edge_key in triangle.edges.iter().map (|k| k.unwrap()) {
237          let edge = self.et_mesh.edges.get (&edge_key).unwrap();
238          if edge.triangles[0].is_some() && edge.triangles[1].is_none() {
239            if edge.vertices[0] == *index {
240              vertex.adjacent_vertices.remove (&edge.vertices[1]);
241              vertex.adjacent_edges.remove (&edge_key);
242            } else if edge.vertices[1] == *index {
243              vertex.adjacent_vertices.remove (&edge.vertices[0]);
244              vertex.adjacent_edges.remove (&edge_key);
245            }
246          }
247        }
248        vertex.adjacent_triangles.remove (&triangle_key);
249        if vertex.adjacent_triangles.is_empty() {
250          self.vertices.remove (index);
251        }
252      }
253      self.et_mesh.remove (v0, v1, v2)
254    } else {
255      false
256    }
257  }
258
259  /// Re-write vertex indices to be consecutive [0..N] on the order of vertex keys
260  pub fn reindex (&mut self) {
261    #[expect(clippy::cast_possible_truncation)]
262    self.vertices.values_mut().enumerate().for_each (|(i, v)| v.index = i as u32);
263    self.et_mesh.edges.values_mut().for_each (|edge|
264      edge.vertices.iter_mut().for_each (|v| *v = self.vertices[v].index));
265    self.et_mesh.triangles.values_mut().for_each (|triangle|
266      triangle.vertices.iter_mut().for_each (|v| *v = self.vertices[v].index));
267    #[expect(clippy::needless_collect)]   // false positive
268    for i in self.vertices.keys().copied().collect::<Vec<_>>() {
269      self.vertices.get_mut (&i).unwrap().adjacent_vertices = self.vertices[&i]
270        .adjacent_vertices.iter().map (|i| self.vertices[i].index).collect();
271    }
272    self.vertices = {
273      #[expect(clippy::cast_possible_truncation)]
274      self.vertices.values().cloned().enumerate().map (|(i, v)| (i as u32, v)).collect()
275    };
276  }
277
278  // TODO: more methods
279}
280
281impl std::ops::Deref for VertexEdgeTriangleMesh {
282  type Target = EdgeTriangleMesh;
283  fn deref (&self) -> &EdgeTriangleMesh {
284    &self.et_mesh
285  }
286}
287
288impl Vertex {
289  pub const fn new (index : u32) -> Self {
290    Self {
291      index,
292      adjacent_vertices:  BTreeSet::new(),
293      adjacent_edges:     BTreeSet::new(),
294      adjacent_triangles: BTreeSet::new()
295    }
296  }
297  pub const fn index (&self) -> u32 {
298    self.index
299  }
300  pub const fn adjacent_vertices (&self) -> &BTreeSet <u32> {
301    &self.adjacent_vertices
302  }
303  pub const fn adjacent_edges (&self) -> &BTreeSet <EdgeKey> {
304    &self.adjacent_edges
305  }
306  pub const fn adjacent_triangles (&self) -> &BTreeSet <TriangleKey> {
307    &self.adjacent_triangles
308  }
309}
310
311impl Edge {
312  pub const fn new (v0 : u32, v1 : u32) -> Self {
313    Edge {
314      vertices:  [v0, v1],
315      triangles: [None, None],
316    }
317  }
318  #[inline]
319  pub const fn vertices (&self) -> &[u32; 2] {
320    &self.vertices
321  }
322  #[inline]
323  pub const fn triangles (&self) -> &[Option <TriangleKey>; 2] {
324    &self.triangles
325  }
326}
327
328impl Triangle {
329  pub const fn new (v0 : u32, v1 : u32, v2 : u32) -> Self {
330    Triangle {
331      vertices:           [v0, v1, v2],
332      edges:              [None, None, None],
333      adjacent_triangles: [None, None, None]
334    }
335  }
336
337  #[inline]
338  pub const fn vertices (&self) -> [u32; 3] {
339    self.vertices
340  }
341  #[inline]
342  pub const fn edges (&self) -> [Option <EdgeKey>; 3] {
343    self.edges
344  }
345  #[inline]
346  pub const fn adjacent_triangles (&self) -> [Option <TriangleKey>; 3] {
347    self.adjacent_triangles
348  }
349}
350
351impl EdgeKey {
352  pub const fn new (a : u32, b : u32) -> Self {
353    if a < b {
354      EdgeKey (a, b)
355    } else {
356      EdgeKey (b, a)
357    }
358  }
359}
math_utils/geometry/mesh/edge_triangle.rs

math_utils/geometry/mesh/
edge_triangle.rs
