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

math_utils/geometry/mesh/
edge_triangle.rs
