nsys-math-utils 1.1.0

//! Edge-triangle meshes
// code from GeometricTools:
// <https://github.com/davideberly/GeometricTools/blob/f78dd0b65bc3a0a4723586de6991dd2c339b08ad/GTE/Mathematics/ETManifoldMesh.h>
// <https://github.com/davideberly/GeometricTools/blob/f78dd0b65bc3a0a4723586de6991dd2c339b08ad/GTE/Mathematics/VETManifoldMesh.h>

use std::collections::{BTreeMap, BTreeSet};

#[derive(Default)]
pub struct EdgeTriangleMesh {
  pub(crate) edges     : BTreeMap <EdgeKey,     Edge>,
  pub(crate) triangles : BTreeMap <TriangleKey, Triangle>,
}

#[derive(Default)]
pub struct VertexEdgeTriangleMesh {
  et_mesh  : EdgeTriangleMesh,
  vertices : BTreeMap <u32, Vertex>
}

/// Note edge-keys are *un-ordered*
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct EdgeKey (u32, u32);
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct TriangleKey (u32, u32, u32);

#[derive(Clone, Eq, Ord, PartialEq, PartialOrd)]
pub struct Vertex {
  index              : u32,
  adjacent_vertices  : BTreeSet <u32>,
  adjacent_edges     : BTreeSet <EdgeKey>,
  adjacent_triangles : BTreeSet <TriangleKey>
}

#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
pub struct Edge {
  vertices  : [u32; 2],
  triangles : [Option <TriangleKey>; 2]
}

#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
pub struct Triangle {
  /// Vertices listed in counter-clockwise order
  vertices           : [u32; 3],
  edges              : [Option <EdgeKey>; 3],
  /// Triangle `i` points to the adjecent triangle sharing edge `i`
  adjacent_triangles : [Option <TriangleKey>; 3],
}

impl EdgeTriangleMesh {
  #[inline]
  pub fn get_edge (&self, key : &EdgeKey) -> Option <&Edge> {
    self.edges.get (key)
  }
  #[inline]
  pub fn get_triangle (&self, key : &TriangleKey) -> Option <&Triangle> {
    self.triangles.get (key)
  }
  #[inline]
  pub const fn edges (&self) -> &BTreeMap <EdgeKey, Edge> {
    &self.edges
  }
  #[inline]
  pub const fn triangles (&self) -> &BTreeMap <TriangleKey, Triangle> {
    &self.triangles
  }

  /// Returns None if triangle already exists in the mesh
  pub fn insert (&mut self, v0 : u32, v1 : u32, v2 : u32) -> Option <Triangle> {
    self.insert_ (v0, v1, v2).map (|inserted| inserted.1)
  }
  fn insert_ (&mut self, v0 : u32, v1 : u32, v2 : u32)
    -> Option <(TriangleKey, Triangle)>
  {
    let triangle_key = TriangleKey (v0, v1, v2);
    if self.triangles.contains_key (&triangle_key) {
      return None
    }
    let mut triangle = Triangle::new (v0, v1, v2);
    let mut i0 = 2;
    let mut i1 = 0;
    while i1 < 3 {
      let edge_key = EdgeKey::new (triangle.vertices[i0], triangle.vertices[i1]);
      if let Some (mut edge) = self.edges.get (&edge_key).copied() {
        // TODO: the original implementation has a "manifold" check here
        if edge.triangles[1].is_some() {
          return None
        }
        edge.triangles[1] = Some (triangle_key);
        let adjacent_key  = edge.triangles[0].unwrap();
        let adjacent      = self.triangles.get_mut (&adjacent_key).unwrap();
        for (i, e_key) in adjacent.edges.iter().enumerate() {
          if e_key == &Some (edge_key) {
            adjacent.adjacent_triangles[i] = Some (triangle_key);
            break
          }
        }
        triangle.edges[i0] = Some (edge_key);
        triangle.adjacent_triangles[i0] = Some (adjacent_key);
        *self.edges.get_mut (&edge_key).unwrap() = edge;
      } else {
        let mut new_edge = Edge::new (edge_key.0, edge_key.1);
        new_edge.triangles[0] = Some (triangle_key);
        triangle.edges[i0]    = Some (edge_key);
        let inserted = self.edges.insert (edge_key, new_edge);
        debug_assert!(inserted.is_none());
      }
      // iter
      i0 = i1;
      i1 += 1;
    }
    let inserted = self.triangles.insert (triangle_key, triangle);
    debug_assert!(inserted.is_none());
    Some ((triangle_key, triangle))
  }

  #[expect(clippy::missing_panics_doc)]
  pub fn remove (&mut self, v0 : u32, v1 : u32, v2 : u32) -> bool {
    let triangle_key = TriangleKey (v0, v1, v2);
    if let Some (triangle) = self.triangles.remove (&triangle_key) {
      for (i, edge_key) in triangle.edges.iter().map (|k| k.unwrap()).enumerate() {
        let edge = self.edges.get_mut (&edge_key).unwrap();
        if edge.triangles[0] == Some (triangle_key) {
          edge.triangles[0] = edge.triangles[1];
          edge.triangles[1] = None;
        } else if edge.triangles[1] == Some (triangle_key) {
          edge.triangles[1] = None;
        } else {
          unreachable!()
        }
        if edge.triangles[0].is_none() && edge.triangles[1].is_none() {
          self.edges.remove (&edge_key);
        }
        if let Some (adjacent_key) = triangle.adjacent_triangles[i] {
          let adjacent = self.triangles.get_mut (&adjacent_key).unwrap();
          for key in adjacent.adjacent_triangles.iter_mut() {
            if key == &Some (triangle_key) {
              *key = None;
              break
            }
          }
        }
      }
      true
    } else {
      false
    }
  }

  // TODO: more methods
}

impl VertexEdgeTriangleMesh {
  #[inline]
  pub fn with_vertex (vertex : Vertex) -> Self {
    let mut mesh = VertexEdgeTriangleMesh::default();
    mesh.vertices.insert (vertex.index, vertex);
    mesh
  }
  #[inline]
  pub fn with_edge (edge : Edge) -> Self {
    let mut mesh = VertexEdgeTriangleMesh::default();
    let edge_key = EdgeKey::new (edge.vertices[0], edge.vertices[1]);
    let v0 = Vertex {
      index: edge_key.0,
      adjacent_vertices:  BTreeSet::from_iter ([edge_key.1]),
      adjacent_edges:     BTreeSet::from_iter ([edge_key]),
      adjacent_triangles: BTreeSet::new()
    };
    let v1 = Vertex {
      index: edge_key.1,
      adjacent_vertices:  BTreeSet::from_iter ([edge_key.0]),
      adjacent_edges:     BTreeSet::from_iter ([edge_key]),
      adjacent_triangles: BTreeSet::new()
    };
    mesh.vertices.insert (v0.index, v0);
    mesh.vertices.insert (v1.index, v1);
    mesh.et_mesh.edges.insert (edge_key, edge);
    mesh
  }
  #[inline]
  pub fn get_vertex (&self, index : u32) -> Option <&Vertex> {
    self.vertices.get (&index)
  }

  #[inline]
  pub const fn edges (&self) -> &BTreeMap <EdgeKey, Edge> {
    self.et_mesh.edges()
  }

  #[inline]
  pub const fn triangles (&self) -> &BTreeMap <TriangleKey, Triangle> {
    self.et_mesh.triangles()
  }

  #[inline]
  pub const fn vertices (&self) -> &BTreeMap <u32, Vertex> {
    &self.vertices
  }

  /// Returns None if triangle already exists in the mesh
  #[expect(clippy::missing_panics_doc)]
  pub fn insert (&mut self, v0 : u32, v1 : u32, v2 : u32) -> Option <Triangle> {
    let (triangle_key, triangle) = self.et_mesh.insert_ (v0, v1, v2)?;
    for index in triangle.vertices.iter() {
      let vertex = self.vertices.entry (*index).or_insert_with (|| Vertex::new (*index));
      vertex.adjacent_triangles.insert (triangle_key);
      for edge_key in triangle.edges.iter().map (|k| k.unwrap()) {
        let edge = self.et_mesh.edges.get (&edge_key).unwrap();
        if edge.vertices[0] == *index {
          vertex.adjacent_vertices.insert (edge.vertices[1]);
          vertex.adjacent_edges.insert (edge_key);
        } else if edge.vertices[1] == *index {
          vertex.adjacent_vertices.insert (edge.vertices[0]);
          vertex.adjacent_edges.insert (edge_key);
        }
      }
    }
    Some (triangle)
  }

  #[expect(clippy::missing_panics_doc)]
  pub fn remove (&mut self, v0 : u32, v1 : u32, v2 : u32) -> bool {
    let triangle_key = TriangleKey (v0, v1, v2);
    if let Some (triangle) = self.et_mesh.triangles.get (&triangle_key) {
      for index in triangle.vertices.iter() {
        let vertex = self.vertices.get_mut (index).unwrap();
        for edge_key in triangle.edges.iter().map (|k| k.unwrap()) {
          let edge = self.et_mesh.edges.get (&edge_key).unwrap();
          if edge.triangles[0].is_some() && edge.triangles[1].is_none() {
            if edge.vertices[0] == *index {
              vertex.adjacent_vertices.remove (&edge.vertices[1]);
              vertex.adjacent_edges.remove (&edge_key);
            } else if edge.vertices[1] == *index {
              vertex.adjacent_vertices.remove (&edge.vertices[0]);
              vertex.adjacent_edges.remove (&edge_key);
            }
          }
        }
        vertex.adjacent_triangles.remove (&triangle_key);
        if vertex.adjacent_triangles.is_empty() {
          self.vertices.remove (index);
        }
      }
      self.et_mesh.remove (v0, v1, v2)
    } else {
      false
    }
  }

  /// Re-write vertex indices to be consecutive [0..N] on the order of vertex keys
  pub fn reindex (&mut self) {
    #[expect(clippy::cast_possible_truncation)]
    self.vertices.values_mut().enumerate().for_each (|(i, v)| v.index = i as u32);
    self.et_mesh.edges.values_mut().for_each (|edge|
      edge.vertices.iter_mut().for_each (|v| *v = self.vertices[v].index));
    self.et_mesh.triangles.values_mut().for_each (|triangle|
      triangle.vertices.iter_mut().for_each (|v| *v = self.vertices[v].index));
    #[expect(clippy::needless_collect)]   // false positive
    for i in self.vertices.keys().copied().collect::<Vec<_>>() {
      self.vertices.get_mut (&i).unwrap().adjacent_vertices = self.vertices[&i]
        .adjacent_vertices.iter().map (|i| self.vertices[i].index).collect();
    }
    self.vertices = {
      #[expect(clippy::cast_possible_truncation)]
      self.vertices.values().cloned().enumerate().map (|(i, v)| (i as u32, v)).collect()
    };
  }

  // TODO: more methods
}

impl std::ops::Deref for VertexEdgeTriangleMesh {
  type Target = EdgeTriangleMesh;
  fn deref (&self) -> &EdgeTriangleMesh {
    &self.et_mesh
  }
}

impl Vertex {
  pub const fn new (index : u32) -> Self {
    Self {
      index,
      adjacent_vertices:  BTreeSet::new(),
      adjacent_edges:     BTreeSet::new(),
      adjacent_triangles: BTreeSet::new()
    }
  }
  pub const fn index (&self) -> u32 {
    self.index
  }
  pub const fn adjacent_vertices (&self) -> &BTreeSet <u32> {
    &self.adjacent_vertices
  }
  pub const fn adjacent_edges (&self) -> &BTreeSet <EdgeKey> {
    &self.adjacent_edges
  }
  pub const fn adjacent_triangles (&self) -> &BTreeSet <TriangleKey> {
    &self.adjacent_triangles
  }
}

impl Edge {
  pub const fn new (v0 : u32, v1 : u32) -> Self {
    Edge {
      vertices:  [v0, v1],
      triangles: [None, None],
    }
  }
  #[inline]
  pub const fn vertices (&self) -> &[u32; 2] {
    &self.vertices
  }
  #[inline]
  pub const fn triangles (&self) -> &[Option <TriangleKey>; 2] {
    &self.triangles
  }
}

impl Triangle {
  pub const fn new (v0 : u32, v1 : u32, v2 : u32) -> Self {
    Triangle {
      vertices:           [v0, v1, v2],
      edges:              [None, None, None],
      adjacent_triangles: [None, None, None]
    }
  }

  #[inline]
  pub const fn vertices (&self) -> [u32; 3] {
    self.vertices
  }
  #[inline]
  pub const fn edges (&self) -> [Option <EdgeKey>; 3] {
    self.edges
  }
  #[inline]
  pub const fn adjacent_triangles (&self) -> [Option <TriangleKey>; 3] {
    self.adjacent_triangles
  }
}

impl EdgeKey {
  pub const fn new (a : u32, b : u32) -> Self {
    if a < b {
      EdgeKey (a, b)
    } else {
      EdgeKey (b, a)
    }
  }
}