use std::collections::HashMap;
use crate::core::BufferGeometry;
use super::{triangles, V3};
#[derive(Debug, Clone)]
pub struct DefectCluster {
pub at: V3,
pub count: usize,
pub radius: f64,
}
#[derive(Debug, Clone)]
pub struct MeshReport {
pub triangles: usize,
pub bounds: (V3, V3),
pub volume: f64,
pub watertight: bool,
pub boundary_edges: usize,
pub overused_edges: usize,
pub shells: usize,
pub open_shells: usize,
pub clusters: Vec<DefectCluster>,
}
impl MeshReport {
pub fn summary(&self) -> String {
let [sx, sy, sz] = [
self.bounds.1[0] - self.bounds.0[0],
self.bounds.1[1] - self.bounds.0[1],
self.bounds.1[2] - self.bounds.0[2],
];
format!(
"{} tris · {sx:.3} x {sy:.3} x {sz:.3} mm · {:.2} cm^3 · {}",
self.triangles,
self.volume / 1000.0,
if self.watertight {
format!(
"watertight{}",
if self.shells > 1 {
format!(", {} shells", self.shells)
} else {
String::new()
}
)
} else {
format!(
"BROKEN: {} of {} shells open ({} boundary, {} overused)",
self.open_shells, self.shells, self.boundary_edges, self.overused_edges
)
}
)
}
}
fn key(p: V3) -> (i64, i64, i64) {
(
(p[0] * 1e4).round() as i64,
(p[1] * 1e4).round() as i64,
(p[2] * 1e4).round() as i64,
)
}
pub fn mesh_report(g: &BufferGeometry) -> MeshReport {
let tris = triangles(g);
let (mut lo, mut hi) = ([f64::MAX; 3], [f64::MIN; 3]);
let mut volume = 0.0f64;
for t in &tris {
for v in t {
for k in 0..3 {
lo[k] = lo[k].min(v[k]);
hi[k] = hi[k].max(v[k]);
}
}
let (a, b, c) = (t[0], t[1], t[2]);
volume += (a[0] * (b[1] * c[2] - c[1] * b[2]) - a[1] * (b[0] * c[2] - c[0] * b[2])
+ a[2] * (b[0] * c[1] - c[0] * b[1]))
/ 6.0;
}
if tris.is_empty() {
lo = [0.0; 3];
hi = [0.0; 3];
}
let (labels, shells) = shell_labels(&tris);
type EdgeUse = HashMap<[(i64, i64, i64); 2], (u32, V3)>;
let mut per_shell: Vec<EdgeUse> = vec![HashMap::new(); shells.max(1)];
for (ti, t) in tris.iter().enumerate() {
let sh = labels.get(ti).copied().unwrap_or(0);
for e in 0..3 {
let (p, q) = (t[e], t[(e + 1) % 3]);
let (kp, kq) = (key(p), key(q));
let k = if kp <= kq { [kp, kq] } else { [kq, kp] };
let mid = [
(p[0] + q[0]) / 2.0,
(p[1] + q[1]) / 2.0,
(p[2] + q[2]) / 2.0,
];
per_shell[sh].entry(k).or_insert((0, mid)).0 += 1;
}
}
let mut boundary = 0usize;
let mut overused = 0usize;
let mut open_shells = 0usize;
let mut bad: Vec<V3> = Vec::new();
for m in &per_shell {
let before = boundary + overused;
for (count, mid) in m.values() {
match *count {
2 => {}
1 => {
boundary += 1;
bad.push(*mid);
}
_ => {
overused += 1;
bad.push(*mid);
}
}
}
if boundary + overused > before {
open_shells += 1;
}
}
let span = (hi[0] - lo[0])
.max(hi[1] - lo[1])
.max(hi[2] - lo[2])
.max(1e-9);
let tol = span * 0.05;
let mut clusters: Vec<DefectCluster> = Vec::new();
for p in bad {
let mut placed = false;
for c in clusters.iter_mut() {
let d =
((p[0] - c.at[0]).powi(2) + (p[1] - c.at[1]).powi(2) + (p[2] - c.at[2]).powi(2))
.sqrt();
if d <= tol {
let n = c.count as f64;
for (k, at) in c.at.iter_mut().enumerate() {
*at = (*at * n + p[k]) / (n + 1.0);
}
c.count += 1;
c.radius = c.radius.max(d);
placed = true;
break;
}
}
if !placed {
clusters.push(DefectCluster {
at: p,
count: 1,
radius: 0.0,
});
}
}
clusters.sort_by_key(|c| std::cmp::Reverse(c.count));
MeshReport {
triangles: tris.len(),
bounds: (lo, hi),
volume,
watertight: boundary == 0 && overused == 0,
boundary_edges: boundary,
overused_edges: overused,
shells,
open_shells,
clusters,
}
}
fn shell_labels(tris: &[[V3; 3]]) -> (Vec<usize>, usize) {
if tris.is_empty() {
return (Vec::new(), 0);
}
let mut label = vec![usize::MAX; tris.len()];
let mut of_vertex: HashMap<(i64, i64, i64), Vec<usize>> = HashMap::new();
for (i, t) in tris.iter().enumerate() {
for v in t {
of_vertex.entry(key(*v)).or_default().push(i);
}
}
let mut shells = 0;
let mut stack: Vec<usize> = Vec::new();
for start in 0..tris.len() {
if label[start] != usize::MAX {
continue;
}
label[start] = shells;
stack.push(start);
while let Some(i) = stack.pop() {
for v in &tris[i] {
if let Some(nb) = of_vertex.get(&key(*v)) {
for &j in nb {
if label[j] == usize::MAX {
label[j] = shells;
stack.push(j);
}
}
}
}
}
shells += 1;
}
(label, shells)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::openscad::{cube, sphere_fn};
#[test]
fn clean_cube_reports_watertight() {
let r = mesh_report(&cube([10.0, 20.0, 30.0]).to_geometry_exact());
assert!(r.watertight, "{}", r.summary());
assert_eq!(r.shells, 1);
assert!(r.clusters.is_empty());
assert!((r.volume - 6000.0).abs() < 1e-6, "volume {}", r.volume);
}
#[test]
fn two_disjoint_solids_report_two_shells() {
let s = cube([4.0, 4.0, 4.0]).union(sphere_fn(2.0, 16).translate([40.0, 0.0, 0.0]));
let r = mesh_report(&s.to_geometry_exact());
assert_eq!(r.shells, 2, "{}", r.summary());
assert!(r.watertight);
}
#[test]
fn open_mesh_locates_its_hole() {
use crate::{BufferAttribute, BufferGeometry};
let mut g = BufferGeometry::new();
g.set_attribute(
"position",
BufferAttribute::new(vec![0.0, 0.0, 0.0, 10.0, 0.0, 0.0, 0.0, 10.0, 0.0], 3),
);
let r = mesh_report(&g);
assert!(!r.watertight);
assert_eq!(r.boundary_edges, 3);
assert_eq!(r.clusters.iter().map(|c| c.count).sum::<usize>(), 3);
for c in &r.clusters {
assert!(c.at[0] >= -1e-9 && c.at[0] <= 10.0, "x {}", c.at[0]);
assert!(c.at[1] >= -1e-9 && c.at[1] <= 10.0, "y {}", c.at[1]);
assert!(c.at[2].abs() < 1e-9, "z {}", c.at[2]);
}
}
}