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

math_utils/geometry/mesh/
edge_triangle.rs
