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  edges     : BTreeMap <EdgeKey,     Edge>,
11  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  /// Returns None if triangle already exists in the mesh
59  pub fn insert (&mut self, v0 : u32, v1 : u32, v2 : u32) -> Option <Triangle> {
60    self.insert_ (v0, v1, v2).map (|inserted| inserted.1)
61  }
62  fn insert_ (&mut self, v0 : u32, v1 : u32, v2 : u32)
63    -> Option <(TriangleKey, Triangle)>
64  {
65    let triangle_key = TriangleKey (v0, v1, v2);
66    if self.triangles.contains_key (&triangle_key) {
67      return None
68    }
69    let mut triangle = Triangle::new (v0, v1, v2);
70    let mut i0 = 2;
71    let mut i1 = 0;
72    while i1 < 3 {
73      let edge_key = EdgeKey::new (triangle.vertices[i0], triangle.vertices[i1]);
74      if let Some (mut edge) = self.edges.get (&edge_key).copied() {
75        // TODO: the original implementation has a "manifold" check here
76        if edge.triangles[1].is_some() {
77          return None
78        }
79        edge.triangles[1] = Some (triangle_key);
80        let adjacent_key  = edge.triangles[0].unwrap();
81        let adjacent      = self.triangles.get_mut (&adjacent_key).unwrap();
82        for (i, e_key) in adjacent.edges.iter().enumerate() {
83          if e_key == &Some (edge_key) {
84            adjacent.adjacent_triangles[i] = Some (triangle_key);
85            break
86          }
87        }
88        triangle.edges[i0] = Some (edge_key);
89        triangle.adjacent_triangles[i0] = Some (adjacent_key);
90        *self.edges.get_mut (&edge_key).unwrap() = edge;
91      } else {
92        let mut new_edge = Edge::new (edge_key.0, edge_key.1);
93        new_edge.triangles[0] = Some (triangle_key);
94        triangle.edges[i0]    = Some (edge_key);
95        let inserted = self.edges.insert (edge_key, new_edge);
96        debug_assert!(inserted.is_none());
97      }
98      // iter
99      i0 = i1;
100      i1 += 1;
101    }
102    let inserted = self.triangles.insert (triangle_key, triangle);
103    debug_assert!(inserted.is_none());
104    Some ((triangle_key, triangle))
105  }
106
107  #[expect(clippy::missing_panics_doc)]
108  pub fn remove (&mut self, v0 : u32, v1 : u32, v2 : u32) -> bool {
109    let triangle_key = TriangleKey (v0, v1, v2);
110    if let Some (triangle) = self.triangles.remove (&triangle_key) {
111      for (i, edge_key) in triangle.edges.iter().map (|k| k.unwrap()).enumerate() {
112        let edge = self.edges.get_mut (&edge_key).unwrap();
113        if edge.triangles[0] == Some (triangle_key) {
114          edge.triangles[0] = edge.triangles[1];
115          edge.triangles[1] = None;
116        } else if edge.triangles[1] == Some (triangle_key) {
117          edge.triangles[1] = None;
118        } else {
119          unreachable!()
120        }
121        if edge.triangles[0].is_none() && edge.triangles[1].is_none() {
122          self.edges.remove (&edge_key);
123        }
124        if let Some (adjacent_key) = triangle.adjacent_triangles[i] {
125          let adjacent = self.triangles.get_mut (&adjacent_key).unwrap();
126          for key in adjacent.adjacent_triangles.iter_mut() {
127            if key == &Some (triangle_key) {
128              *key = None;
129              break
130            }
131          }
132        }
133      }
134      true
135    } else {
136      false
137    }
138  }
139
140  // TODO: more methods
141}
142
143impl VertexEdgeTriangleMesh {
144  #[inline]
145  pub fn get_vertex (&self, index : u32) -> Option <&Vertex> {
146    self.vertices.get (&index)
147  }
148
149  #[inline]
150  pub const fn vertices (&self) -> &BTreeMap <u32, Vertex> {
151    &self.vertices
152  }
153
154  /// Returns None if triangle already exists in the mesh
155  #[expect(clippy::missing_panics_doc)]
156  pub fn insert (&mut self, v0 : u32, v1 : u32, v2 : u32) -> Option <Triangle> {
157    let (triangle_key, triangle) = self.et_mesh.insert_ (v0, v1, v2)?;
158    for index in triangle.vertices.iter() {
159      let vertex = self.vertices.entry (*index).or_insert_with (|| Vertex::new (*index));
160      vertex.adjacent_triangles.insert (triangle_key);
161      for edge_key in triangle.edges.iter().map (|k| k.unwrap()) {
162        let edge = self.et_mesh.edges.get (&edge_key).unwrap();
163        if edge.vertices[0] == *index {
164          vertex.adjacent_vertices.insert (edge.vertices[1]);
165          vertex.adjacent_edges.insert (edge_key);
166        } else if edge.vertices[1] == *index {
167          vertex.adjacent_vertices.insert (edge.vertices[0]);
168          vertex.adjacent_edges.insert (edge_key);
169        }
170      }
171    }
172    Some (triangle)
173  }
174
175  #[expect(clippy::missing_panics_doc)]
176  pub fn remove (&mut self, v0 : u32, v1 : u32, v2 : u32) -> bool {
177    let triangle_key = TriangleKey (v0, v1, v2);
178    if let Some (triangle) = self.et_mesh.triangles.get (&triangle_key) {
179      for index in triangle.vertices.iter() {
180        let vertex = self.vertices.get_mut (index).unwrap();
181        for edge_key in triangle.edges.iter().map (|k| k.unwrap()) {
182          let edge = self.et_mesh.edges.get (&edge_key).unwrap();
183          if edge.triangles[0].is_some() && edge.triangles[1].is_none() {
184            if edge.vertices[0] == *index {
185              vertex.adjacent_vertices.remove (&edge.vertices[1]);
186              vertex.adjacent_edges.remove (&edge_key);
187            } else if edge.vertices[1] == *index {
188              vertex.adjacent_vertices.remove (&edge.vertices[0]);
189              vertex.adjacent_edges.remove (&edge_key);
190            }
191          }
192        }
193        vertex.adjacent_triangles.remove (&triangle_key);
194        if vertex.adjacent_triangles.is_empty() {
195          self.vertices.remove (index);
196        }
197      }
198      self.et_mesh.remove (v0, v1, v2)
199    } else {
200      false
201    }
202  }
203
204  // TODO: more methods
205}
206
207impl std::ops::Deref for VertexEdgeTriangleMesh {
208  type Target = EdgeTriangleMesh;
209  fn deref (&self) -> &EdgeTriangleMesh {
210    &self.et_mesh
211  }
212}
213
214impl Vertex {
215  pub const fn new (index : u32) -> Self {
216    Self {
217      index,
218      adjacent_vertices:  BTreeSet::new(),
219      adjacent_edges:     BTreeSet::new(),
220      adjacent_triangles: BTreeSet::new()
221    }
222  }
223  pub const fn index (&self) -> u32 {
224    self.index
225  }
226  pub const fn adjacent_vertices (&self) -> &BTreeSet <u32> {
227    &self.adjacent_vertices
228  }
229  pub const fn adjacent_edges (&self) -> &BTreeSet <EdgeKey> {
230    &self.adjacent_edges
231  }
232  pub const fn adjacent_triangles (&self) -> &BTreeSet <TriangleKey> {
233    &self.adjacent_triangles
234  }
235}
236
237impl Edge {
238  pub const fn new (v0 : u32, v1 : u32) -> Self {
239    Edge {
240      vertices:  [v0, v1],
241      triangles: [None, None],
242    }
243  }
244  #[inline]
245  pub const fn vertices (&self) -> &[u32; 2] {
246    &self.vertices
247  }
248  #[inline]
249  pub const fn triangles (&self) -> &[Option <TriangleKey>; 2] {
250    &self.triangles
251  }
252}
253
254impl Triangle {
255  pub const fn new (v0 : u32, v1 : u32, v2 : u32) -> Self {
256    Triangle {
257      vertices:           [v0, v1, v2],
258      edges:              [None, None, None],
259      adjacent_triangles: [None, None, None]
260    }
261  }
262
263  #[inline]
264  pub const fn vertices (&self) -> &[u32; 3] {
265    &self.vertices
266  }
267  #[inline]
268  pub const fn edges (&self) -> &[Option <EdgeKey>; 3] {
269    &self.edges
270  }
271  #[inline]
272  pub const fn adjacent_triangles (&self) -> &[Option <TriangleKey>; 3] {
273    &self.adjacent_triangles
274  }
275}
276
277impl EdgeKey {
278  pub const fn new (a : u32, b : u32) -> Self {
279    if a < b {
280      EdgeKey (a, b)
281    } else {
282      EdgeKey (b, a)
283    }
284  }
285}
math_utils/geometry/mesh/edge_triangle.rs

math_utils/geometry/mesh/
edge_triangle.rs
