use super::Mesh3;
use crate::{Point3, Result};
use std::collections::{HashMap, HashSet};
type EdgesFacesLoops = (Vec<[u32; 2]>, Vec<[u32; 3]>, Vec<Vec<u32>>);
pub struct MeshEdges<'a> {
mesh: &'a Mesh3,
pub edges: Vec<[u32; 2]>,
pub edge_lengths: Vec<f64>,
pub face_edges: Vec<[u32; 3]>,
pub boundary_loops: Vec<Vec<u32>>,
}
impl<'a> MeshEdges<'a> {
pub fn mesh(&self) -> &Mesh3 {
self.mesh
}
pub fn points(&self) -> &[Point3] {
self.mesh.shape.vertices()
}
pub fn faces(&self) -> &[[u32; 3]] {
self.mesh.shape.indices()
}
pub fn new(mesh: &'a Mesh3) -> Result<Self> {
let (edges, face_edges, boundary_loops) = identify_edges(mesh.faces())?;
let edge_lengths = edges
.iter()
.map(|edge| {
let v0 = mesh.points()[edge[0] as usize];
let v1 = mesh.points()[edge[1] as usize];
(v1 - v0).norm()
})
.collect();
Ok(Self {
mesh,
edges,
edge_lengths,
face_edges,
boundary_loops,
})
}
}
pub fn edge_key(edge: &[u32; 2]) -> [u32; 2] {
let x = edge[0].min(edge[1]);
let y = edge[0].max(edge[1]);
[x, y]
}
pub fn naive_edges(faces: &[[u32; 3]]) -> Vec<[u32; 2]> {
let mut edges = Vec::new();
for face in faces {
edges.push([face[1], face[2]]);
edges.push([face[2], face[0]]);
edges.push([face[0], face[1]]);
}
edges
}
pub fn unique_edges(all_edges: &[[u32; 2]]) -> Vec<([u32; 2], usize)> {
let mut unique = HashMap::new();
for edge in all_edges {
let key = edge_key(edge);
let count = unique.entry(key).or_insert(0);
*count += 1;
}
let mut unique_count: Vec<_> = unique.into_iter().collect();
unique_count.sort();
unique_count
}
fn boundary_loops(boundary_map: HashMap<u32, u32>) -> Vec<Vec<u32>> {
let mut all_loops = Vec::new();
let mut working = Vec::new();
let mut queue: HashSet<u32> = boundary_map.keys().copied().collect();
while !queue.is_empty() {
if let Some(last_id) = working.last() {
let next_id = boundary_map[last_id];
queue.remove(&next_id);
if *working.first().unwrap() == next_id {
working.reverse();
all_loops.push(working);
working = Vec::new();
} else {
working.push(next_id);
}
} else {
let start_id = *queue.iter().next().unwrap();
working.push(start_id);
}
}
all_loops
}
fn identify_edges(faces: &[[u32; 3]]) -> Result<EdgesFacesLoops> {
let direct_edges = naive_edges(faces);
let unique_edge_count = unique_edges(&direct_edges);
if unique_edge_count.iter().any(|(_, count)| *count > 2) {
return Err("Non-manifold edges detected".into());
}
let to_unique_index: HashMap<[u32; 2], usize> = unique_edge_count
.iter()
.enumerate()
.map(|(i, (edge, _))| (*edge, i))
.collect();
let mut boundary_map = HashMap::new();
let mut face_edges = Vec::new();
for face_chunk in direct_edges.chunks(3) {
let i0 = to_unique_index[&edge_key(&face_chunk[0])];
let i1 = to_unique_index[&edge_key(&face_chunk[1])];
let i2 = to_unique_index[&edge_key(&face_chunk[2])];
face_edges.push([i0 as u32, i1 as u32, i2 as u32]);
if unique_edge_count[i0].1 == 1 {
boundary_map.insert(face_chunk[0][0], face_chunk[0][1]);
}
if unique_edge_count[i1].1 == 1 {
boundary_map.insert(face_chunk[1][0], face_chunk[1][1]);
}
if unique_edge_count[i2].1 == 1 {
boundary_map.insert(face_chunk[2][0], face_chunk[2][1]);
}
}
let loops = boundary_loops(boundary_map);
let edges = unique_edge_count.iter().map(|(edge, _)| *edge).collect();
Ok((edges, face_edges, loops))
}