use crate::geom3::mesh::SurfaceDeviation;
use crate::geom3::mesh::measurement::{derived_spacing, sample_distances};
use crate::{Mesh3, Point3, Result};
const BOUNDARY_SAMPLES_PER_SEGMENT: usize = 4;
pub(crate) const OVER_MULTIPLES: [f64; 4] = [1.0, 2.0, 5.0, 10.0];
#[derive(Debug, Clone, Copy, PartialEq)]
pub(crate) struct Spread {
pub p50: f64,
pub p90: f64,
pub p99: f64,
pub p999: f64,
pub max: f64,
pub over: [f64; 4],
}
impl std::fmt::Display for Spread {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"p50 {:.6} p90 {:.6} p99 {:.6} p99.9 {:.6} max {:.6}, \
over {:.3}% / {:.3}% / {:.3}% / {:.3}% at 1x / 2x / 5x / 10x",
self.p50,
self.p90,
self.p99,
self.p999,
self.max,
self.over[0] * 100.0,
self.over[1] * 100.0,
self.over[2] * 100.0,
self.over[3] * 100.0
)
}
}
#[derive(Debug, Clone, PartialEq)]
pub(crate) struct ShapeDifference {
pub old_vertices_to_new: f64,
pub new_vertices_to_old: f64,
pub dense: SurfaceDeviation,
pub spread: Option<Spread>,
pub boundary: Option<f64>,
pub volume_ratio: Option<f64>,
}
impl ShapeDifference {
pub(crate) fn new(old: &Mesh3, new: &Mesh3) -> Result<Self> {
Self::build(old, new, None)
}
pub(crate) fn with_spread(old: &Mesh3, new: &Mesh3, threshold: f64) -> Result<Self> {
Self::build(old, new, Some(threshold))
}
fn build(old: &Mesh3, new: &Mesh3, threshold: Option<f64>) -> Result<Self> {
let dense = old.measure_surface_deviation(new, None)?;
let spread = match threshold {
Some(t) => {
let mut all = sample_distances(old, new, derived_spacing(old)?, "reference")?;
all.extend(sample_distances(new, old, derived_spacing(new)?, "test")?);
Some(Spread::from_samples(&mut all, t))
}
None => None,
};
Ok(Self {
old_vertices_to_new: worst_vertex_distance(old, new),
new_vertices_to_old: worst_vertex_distance(new, old),
dense,
spread,
boundary: boundary_deviation(old, new),
volume_ratio: volume_ratio(old, new),
})
}
pub(crate) fn hausdorff(&self) -> f64 {
self.dense.hausdorff()
}
pub(crate) fn assert_within(&self, tol: f64) {
assert!(
self.hausdorff() <= tol,
"surfaces deviate by more than the tolerance of {}\n {}",
tol,
self
);
}
}
impl std::fmt::Display for ShapeDifference {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "dense: {}", self.dense)?;
write!(
f,
"\n vertices only (diagnostic): old->new {:.6}, new->old {:.6}",
self.old_vertices_to_new, self.new_vertices_to_old
)?;
if let Some(s) = self.spread {
write!(f, "\n spread: {}", s)?;
}
if let Some(b) = self.boundary {
write!(f, "\n boundary: {:.6}", b)?;
}
if let Some(v) = self.volume_ratio {
write!(f, "\n volume ratio: {:.6}", v)?;
}
Ok(())
}
}
impl Spread {
fn from_samples(samples: &mut [f64], threshold: f64) -> Self {
samples.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
if samples.is_empty() {
return Self {
p50: 0.0,
p90: 0.0,
p99: 0.0,
p999: 0.0,
max: 0.0,
over: [0.0; 4],
};
}
let at = |q: f64| samples[(((samples.len() - 1) as f64) * q).round() as usize];
let n = samples.len() as f64;
let fraction_over =
|m: f64| samples.iter().filter(|d| **d > threshold * m).count() as f64 / n;
Self {
p50: at(0.5),
p90: at(0.9),
p99: at(0.99),
p999: at(0.999),
max: at(1.0),
over: std::array::from_fn(|i| fraction_over(OVER_MULTIPLES[i])),
}
}
}
fn worst_vertex_distance(from: &Mesh3, to: &Mesh3) -> f64 {
from.points()
.iter()
.map(|p| to.distance_closest_to(p))
.fold(0.0f64, f64::max)
}
fn boundary_deviation(old: &Mesh3, new: &Mesh3) -> Option<f64> {
let a = boundary_segments(old);
let b = boundary_segments(new);
match (a.is_empty(), b.is_empty()) {
(true, true) => None,
(true, false) | (false, true) => Some(f64::INFINITY),
(false, false) => Some(one_sided_boundary(&a, &b).max(one_sided_boundary(&b, &a))),
}
}
fn boundary_segments(mesh: &Mesh3) -> Vec<[Point3; 2]> {
let points = mesh.points();
mesh.compute_nav()
.boundary_edges(None)
.into_iter()
.map(|e| [points[e[0] as usize], points[e[1] as usize]])
.collect()
}
fn one_sided_boundary(from: &[[Point3; 2]], to: &[[Point3; 2]]) -> f64 {
let mut worst = 0.0f64;
for seg in from.iter() {
for i in 0..BOUNDARY_SAMPLES_PER_SEGMENT {
let t = i as f64 / (BOUNDARY_SAMPLES_PER_SEGMENT - 1) as f64;
let p = seg[0] + (seg[1] - seg[0]) * t;
let nearest = to
.iter()
.map(|s| point_to_segment(&p, &s[0], &s[1]))
.fold(f64::INFINITY, f64::min);
worst = worst.max(nearest);
}
}
worst
}
fn point_to_segment(p: &Point3, a: &Point3, b: &Point3) -> f64 {
let ab = b - a;
let denom = ab.norm_squared();
let t = if denom <= 0.0 {
0.0
} else {
((p - a).dot(&ab) / denom).clamp(0.0, 1.0)
};
(p - (a + ab * t)).norm()
}
fn volume_ratio(old: &Mesh3, new: &Mesh3) -> Option<f64> {
if !boundary_segments(old).is_empty() || !boundary_segments(new).is_empty() {
return None;
}
let before = signed_volume(old);
if before.abs() <= f64::MIN_POSITIVE {
return None;
}
Some(signed_volume(new) / before)
}
fn signed_volume(mesh: &Mesh3) -> f64 {
let points = mesh.points();
let total: f64 = mesh
.faces()
.iter()
.map(|f| {
let a = points[f[0] as usize].coords;
let b = points[f[1] as usize].coords;
let c = points[f[2] as usize].coords;
a.dot(&b.cross(&c))
})
.sum();
total / 6.0
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_mesh_matches_itself_exactly() {
let mesh = crate::tests::engine_blade();
let g = ShapeDifference::new(&mesh, &mesh).unwrap();
assert!(g.hausdorff() < 1.0e-9, "{}", g);
assert!(g.old_vertices_to_new < 1.0e-9, "{}", g);
assert!(g.new_vertices_to_old < 1.0e-9, "{}", g);
g.assert_within(1.0e-9);
}
#[test]
fn vertex_measures_miss_what_the_dense_measure_catches() {
let points = vec![
Point3::new(-1.0, -1.0, 1.0),
Point3::new(1.0, -1.0, -1.0),
Point3::new(1.0, 1.0, 1.0),
Point3::new(-1.0, 1.0, -1.0),
];
let one = Mesh3::new(points.clone(), vec![[0, 1, 2], [0, 2, 3]], false);
let two = Mesh3::new(points, vec![[0, 1, 3], [1, 2, 3]], false);
let g = ShapeDifference::new(&one, &two).unwrap();
assert!(g.old_vertices_to_new < 1.0e-9, "the vertices are shared");
assert!(g.new_vertices_to_old < 1.0e-9, "the vertices are shared");
assert!(g.hausdorff() > 0.1, "the surfaces genuinely differ: {}", g);
}
#[test]
fn a_known_offset_measures_as_itself() {
let a = Mesh3::create_box(4.0, 4.0, 4.0, false);
let b = a.transform_copy(&crate::Iso3::translation(0.25, 0.0, 0.0));
let g = ShapeDifference::new(&a, &b).unwrap();
assert!(
(g.hausdorff() - 0.25).abs() < 1.0e-9,
"expected 0.25, got {}",
g
);
}
#[test]
fn a_rigid_motion_preserves_the_volume() {
let a = Mesh3::create_box(4.0, 4.0, 4.0, false);
let b = a.transform_copy(&crate::Iso3::translation(0.25, 0.0, 0.0));
let ratio = ShapeDifference::new(&a, &b).unwrap().volume_ratio.unwrap();
assert!((ratio - 1.0).abs() < 1.0e-9, "got {}", ratio);
}
#[test]
fn the_optional_measures_decline_when_they_do_not_apply() {
let closed = Mesh3::create_box(4.0, 4.0, 4.0, false);
let g = ShapeDifference::new(&closed, &closed).unwrap();
assert!(g.boundary.is_none(), "a closed mesh has no outline");
assert!(g.volume_ratio.is_some());
let open = crate::tests::stanford_bun_4();
let g = ShapeDifference::new(&open, &open).unwrap();
assert!(g.boundary.is_some(), "an open mesh has an outline");
assert!(g.boundary.unwrap() < 1.0e-9, "matched against itself");
assert!(g.volume_ratio.is_none(), "an open mesh encloses nothing");
}
#[test]
fn the_boundary_measure_sees_an_outline_move() {
let square = |w: f64| {
Mesh3::new(
vec![
Point3::new(0.0, 0.0, 0.0),
Point3::new(w, 0.0, 0.0),
Point3::new(w, 1.0, 0.0),
Point3::new(0.0, 1.0, 0.0),
],
vec![[0, 1, 2], [0, 2, 3]],
false,
)
};
let g = ShapeDifference::new(&square(1.0), &square(0.7)).unwrap();
let b = g.boundary.unwrap();
assert!((b - 0.3).abs() < 1.0e-9, "expected 0.3, got {}", b);
}
#[test]
fn the_spread_agrees_with_the_criterion() {
let a = Mesh3::create_box(4.0, 4.0, 4.0, false);
let b = a.transform_copy(&crate::Iso3::translation(0.25, 0.0, 0.0));
assert!(ShapeDifference::new(&a, &b).unwrap().spread.is_none());
let g = ShapeDifference::with_spread(&a, &b, 0.1).unwrap();
let s = g.spread.unwrap();
assert!((s.max - g.hausdorff()).abs() < 1.0e-9, "{}", g);
assert!(s.p50 <= s.p90 && s.p90 <= s.p99 && s.p99 <= s.p999 && s.p999 <= s.max);
assert!(
s.over[0] > 0.3,
"a 0.25 offset is over a 0.1 threshold: {}",
g
);
assert!(s.over[1] > 0.3, "and over 2x it: {}", g);
assert_eq!(s.over[2], 0.0, "but nothing is over 5x it: {}", g);
assert!(
s.over.windows(2).all(|w| w[0] >= w[1]),
"the exceedance fractions must fall as the multiple rises: {}",
g
);
}
}