use super::{
AlumPolyMesh, CollapseGate, DecimateReport, DecimateStats, DecimateTarget, Placement, Quadric,
QuadricKind, StarFace, Structural, candidate_positions, run_decimation, set_boundary_locks,
};
use crate::common::barycentric::{barycentric_point, closest_barycentric};
use crate::geom3::half_edge3::HalfEdgeMesh3;
use crate::{Point3, Result, Vector3};
use alum::{FH, HH, Handle, HasIterators, HasTopology, VH};
use std::f64::consts::PI;
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct BestEffortOpts {
pub tol: f64,
pub max_normal_deviation: f64,
pub min_aspect: f64,
pub lock_boundary: bool,
pub placement: Placement,
pub target: DecimateTarget,
pub quadric: QuadricKind,
}
impl Default for BestEffortOpts {
fn default() -> Self {
Self {
tol: 0.0,
max_normal_deviation: PI / 4.0,
min_aspect: 0.01,
lock_boundary: true,
placement: Placement::Optimal,
target: DecimateTarget::ToTolerance,
quadric: QuadricKind::Triangle,
}
}
}
impl BestEffortOpts {
pub fn to_tolerance(tol: f64) -> Self {
Self {
tol,
target: DecimateTarget::ToTolerance,
..Default::default()
}
}
pub fn to_face_count(tol: f64, faces: usize) -> Self {
Self {
tol,
target: DecimateTarget::FaceCount(faces),
..Default::default()
}
}
pub fn to_ratio(tol: f64, ratio: f64) -> Self {
Self {
tol,
target: DecimateTarget::Ratio(ratio),
..Default::default()
}
}
pub fn with_max_normal_deviation(mut self, value: f64) -> Self {
self.max_normal_deviation = value;
self
}
pub fn with_min_aspect(mut self, value: f64) -> Self {
self.min_aspect = value;
self
}
pub fn with_lock_boundary(mut self, value: bool) -> Self {
self.lock_boundary = value;
self
}
pub fn with_placement(mut self, value: Placement) -> Self {
self.placement = value;
self
}
pub fn with_quadric(mut self, value: QuadricKind) -> Self {
self.quadric = value;
self
}
fn validate(&self) -> Result<()> {
if self.tol.is_nan() || self.tol <= 0.0 {
return Err(format!(
"A best-effort decimation tolerance must be positive, got {}",
self.tol
)
.into());
}
if self.max_normal_deviation.is_nan() || self.max_normal_deviation <= 0.0 {
return Err("The maximum normal deviation must be positive".into());
}
self.target.validate()
}
}
pub(crate) struct Accepted {
position: Vector3,
quadric: Quadric,
cost: f64,
error: f64,
reassigned: Vec<(u32, FH)>,
cleared: Vec<FH>,
}
pub struct BestEffortDecimator {
opts: BestEffortOpts,
quadrics: Vec<Quadric>,
error: Vec<f64>,
pinned: Vec<bool>,
absorbed: Absorbed,
structural: Structural,
}
struct Absorbed {
points: Vec<Point3>,
owned: Vec<Vec<u32>>,
}
impl Absorbed {
fn new(mesh: &AlumPolyMesh) -> Result<Self> {
let points = mesh.points();
let points = points
.try_borrow()
.map_err(|_| "Failed to borrow points while seeding the absorbed vertices")?;
let mut owned = vec![Vec::new(); mesh.num_faces()];
for v in mesh.vertices() {
if let Some(f) = mesh.vf_ccw_iter(v).next() {
owned[f.index() as usize].push(v.index());
}
}
Ok(Self {
points: mesh.vertices().map(|v| Point3::from(points[v])).collect(),
owned,
})
}
fn in_star<'a>(&'a self, star: &'a [StarFace]) -> impl Iterator<Item = u32> + 'a {
star.iter()
.flat_map(|f| self.owned[f.f.index() as usize].iter().copied())
}
fn apply(&mut self, cleared: &[FH], reassigned: &[(u32, FH)]) {
for f in cleared.iter() {
self.owned[f.index() as usize].clear();
}
for (v, f) in reassigned.iter() {
self.owned[f.index() as usize].push(*v);
}
}
}
impl BestEffortDecimator {
pub fn new(mesh: &HalfEdgeMesh3, opts: BestEffortOpts) -> Result<Self> {
opts.validate()?;
let inner = mesh.as_alum();
let pinned = {
let vstatus = inner.vertex_status_prop();
let vstatus = vstatus
.try_borrow()
.map_err(|_| "Failed to borrow vertex status")?;
inner.vertices().map(|v| vstatus[v].feature()).collect()
};
Ok(Self {
opts,
quadrics: seed(inner, opts.quadric)?,
error: vec![0.0; inner.num_vertices()],
pinned,
absorbed: Absorbed::new(inner)?,
structural: Structural::new(opts.max_normal_deviation, opts.min_aspect),
})
}
fn coverage(
&self,
star: &[StarFace],
surviving: &[(FH, [Point3; 3])],
cap: f64,
mut worst: f64,
) -> Option<(f64, Vec<(u32, FH)>)> {
if surviving.is_empty() {
return None;
}
let mut out = Vec::new();
for v in self.absorbed.in_star(star) {
let p = self.absorbed.points[v as usize];
let mut best = f64::INFINITY;
let mut owner = surviving[0].0;
for (f, q) in surviving.iter() {
let w = closest_barycentric(&q[0], &q[1], &q[2], &p);
let d = (barycentric_point(&q[0], &q[1], &q[2], w) - p).norm();
if d < best {
best = d;
owner = *f;
if best <= worst {
break;
}
}
}
if best > worst {
worst = best;
if worst > cap {
return None;
}
}
out.push((v, owner));
}
Some((worst, out))
}
fn evaluate(&self, mesh: &AlumPolyMesh, h: HH) -> Option<Accepted> {
self.structural.bump_evaluation();
let v1 = h.tail(mesh);
let v2 = h.head(mesh);
let points = mesh.points();
let points = points.try_borrow().ok()?;
let p1 = points[v1];
let p2 = points[v2];
let q = self.quadrics[v1.index() as usize] + self.quadrics[v2.index() as usize];
let inherited = self.error[v1.index() as usize].max(self.error[v2.index() as usize]);
let star = self.structural.stars(mesh, v1, v2, &points)?;
if star.is_empty() {
return None;
}
if inherited > self.opts.tol {
self.structural.bump_error_veto();
return None;
}
let pinned = self
.pinned
.get(v2.index() as usize)
.copied()
.unwrap_or(false);
for candidate in candidate_positions(self.opts.placement, pinned, &q, p1, p2) {
self.structural.bump_acceptance();
let Some(new) = self.structural.reshape(&star, v1, v2, candidate, &points) else {
continue;
};
let surviving: Vec<(FH, [Point3; 3])> = star
.iter()
.zip(new.iter())
.filter(|(f, _)| !f.vanishing)
.map(|(f, q)| (f.f, *q))
.collect();
let Some((cost, reassigned)) = self.coverage(&star, &surviving, self.opts.tol, 0.0)
else {
self.structural.bump_error_veto();
continue;
};
let error = cost.max(inherited);
return Some(Accepted {
position: candidate,
quadric: q,
cost,
error,
reassigned,
cleared: star.iter().map(|f| f.f).collect(),
});
}
None
}
}
fn seed(mesh: &AlumPolyMesh, kind: QuadricKind) -> Result<Vec<Quadric>> {
let points = mesh.points();
let points = points
.try_borrow()
.map_err(|_| "Failed to borrow points while seeding quadrics")?;
let n = mesh.num_vertices();
let mut quadrics = vec![Quadric::default(); n];
for v in mesh.vertices() {
let i = v.index() as usize;
for f in mesh.vf_ccw_iter(v) {
for vs in mesh.triangulated_face_vertices(f) {
let (a, b, c) = (points[vs[0]], points[vs[1]], points[vs[2]]);
quadrics[i] += match kind {
QuadricKind::Triangle => Quadric::triangle_quadric(a, b, c),
QuadricKind::Probabilistic => {
let mean_edge = ((b - a).norm() + (c - b).norm() + (a - c).norm()) / 3.0;
Quadric::probabilistic_triangle_quadric(a, b, c, 0.1 * mean_edge)
}
};
}
}
}
Ok(quadrics)
}
impl CollapseGate for BestEffortDecimator {
type Accepted = Accepted;
fn evaluate(&self, mesh: &AlumPolyMesh, h: HH) -> Option<Accepted> {
BestEffortDecimator::evaluate(self, mesh, h)
}
fn cost(accepted: &Accepted) -> f64 {
accepted.cost
}
fn position(accepted: &Accepted) -> Vector3 {
accepted.position
}
fn commit(&mut self, v: VH, accepted: Accepted) -> Result<()> {
let i = v.index() as usize;
self.quadrics[i] = accepted.quadric;
self.error[i] = accepted.error;
self.absorbed.apply(&accepted.cleared, &accepted.reassigned);
Ok(())
}
fn stats(&self) -> DecimateStats {
self.structural.stats.get()
}
}
impl HalfEdgeMesh3 {
pub fn decimate_best_effort(&mut self, opts: &BestEffortOpts) -> Result<DecimateReport> {
opts.validate()?;
set_boundary_locks(self, opts.lock_boundary)?;
let mut gate = BestEffortDecimator::new(self, *opts)?;
self.set_error_volume_stale();
run_decimation(self, &mut gate, opts.target)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geom3::half_edge3::RepairOpts;
use crate::geom3::half_edge3::difference::ShapeDifference;
use crate::{Mesh3, Point3};
fn flat_grid(n: usize) -> Mesh3 {
let mut points = Vec::new();
for i in 0..=n {
for j in 0..=n {
points.push(Point3::new(i as f64, j as f64, 0.0));
}
}
let mut faces = Vec::new();
let idx = |i: usize, j: usize| (i * (n + 1) + j) as u32;
for i in 0..n {
for j in 0..n {
faces.push([idx(i, j), idx(i + 1, j), idx(i + 1, j + 1)]);
faces.push([idx(i, j), idx(i + 1, j + 1), idx(i, j + 1)]);
}
}
Mesh3::new(points, faces, false)
}
fn decimate_blade(opts: &BestEffortOpts) -> (Mesh3, Mesh3, DecimateReport) {
let original = crate::tests::engine_blade();
let mut he = HalfEdgeMesh3::try_from(&original).unwrap();
let report = he.decimate_best_effort(opts).unwrap();
let out = Mesh3::try_from(&he).unwrap();
(original, out, report)
}
#[test]
fn a_flat_grid_collapses_to_almost_nothing() {
let original = flat_grid(20);
let mut he = HalfEdgeMesh3::try_from(&original).unwrap();
let report = he
.decimate_best_effort(&BestEffortOpts::to_tolerance(1.0e-9))
.unwrap();
assert!(
report.faces_after < 100,
"a flat grid should collapse freely, got {}",
report
);
let out = Mesh3::try_from(&he).unwrap();
for p in out.points().iter() {
assert!(p.z.abs() < 1.0e-12, "left the plane at {:?}", p);
}
}
#[test]
fn every_original_vertex_stays_covered() {
for tol in [0.005, 0.05, 0.5] {
let (original, out, report) = decimate_blade(&BestEffortOpts::to_tolerance(tol));
let diff = ShapeDifference::new(&original, &out).unwrap();
assert!(
diff.old_vertices_to_new <= tol,
"an original vertex ended up {:.6} from the result at a tolerance of {}, \
which the absorbed-vertex tracking is supposed to make impossible ({})",
diff.old_vertices_to_new,
tol,
report
);
}
}
#[test]
fn a_loose_tolerance_leaves_only_a_thin_tail() {
let tol = 0.1;
let (original, out, report) = decimate_blade(&BestEffortOpts::to_tolerance(tol));
let diff = ShapeDifference::with_spread(&original, &out, tol).unwrap();
let spread = diff.spread.unwrap();
assert!(
spread.p99 <= tol,
"99% of the surface should be inside the tolerance, p99 was {:.6} ({})",
spread.p99,
report
);
assert!(
spread.over[0] < 0.02,
"under 2% of samples should exceed the tolerance, got {:.3}% ({})",
spread.over[0] * 100.0,
report
);
assert!(
spread.over[1] < 0.001,
"essentially nothing should exceed twice the tolerance, got {:.3}%: {}",
spread.over[1] * 100.0,
diff
);
}
#[test]
fn the_deviation_is_not_controlled_by_the_tolerance() {
const FLOOR: f64 = 0.15;
for tol in [0.001, 0.005, 0.01, 0.05, 0.1, 0.5] {
let (original, out, report) = decimate_blade(&BestEffortOpts::to_tolerance(tol));
let worst = ShapeDifference::new(&original, &out).unwrap().hausdorff();
assert!(
worst > tol,
"at tol {} the deviation came in under the tolerance, which would mean this \
fixture stopped exercising the difference between the two paths: {:.6}",
tol,
worst
);
assert!(
worst < FLOOR + 10.0 * tol,
"at tol {} the deviation was {:.6}, past the recorded {} + 10x envelope ({})",
tol,
worst,
FLOOR,
report
);
}
}
#[test]
fn it_decimates_further_than_the_guaranteed_path() {
let tol = 0.01;
let (_, _, best) = decimate_blade(&BestEffortOpts::to_tolerance(tol));
let original = crate::tests::engine_blade();
let mut he = HalfEdgeMesh3::try_from(&original).unwrap();
let guaranteed = he
.decimate_guaranteed(&crate::geom3::half_edge3::DecimateOpts::to_tolerance(tol))
.unwrap();
assert!(
(best.faces_after as f64) < 0.8 * guaranteed.faces_after as f64,
"expected the best-effort path to be materially more aggressive; \
best effort {} vs guaranteed {}",
best,
guaranteed
);
}
#[test]
fn a_face_count_target_is_respected() {
let target = 5_000;
let (_, _, report) = decimate_blade(&BestEffortOpts::to_face_count(1.0, target));
assert!(
report.faces_after <= target + 2,
"expected to stop near {}, got {}",
target,
report
);
}
#[test]
fn the_gate_wins_over_an_unreachable_count() {
let (_, _, report) = decimate_blade(&BestEffortOpts::to_face_count(1.0e-5, 100));
assert!(
report.faces_after > 100,
"the tolerance should have stopped this well short of 100 faces, got {}",
report
);
}
#[test]
fn a_locked_boundary_is_not_moved() {
let original = flat_grid(12);
let before = original
.points()
.iter()
.filter(|p| p.x <= 0.0 || p.y <= 0.0 || p.x >= 12.0 || p.y >= 12.0)
.count();
let mut he = HalfEdgeMesh3::try_from(&original).unwrap();
he.decimate_best_effort(&BestEffortOpts::to_tolerance(1.0e-9))
.unwrap();
let out = Mesh3::try_from(&he).unwrap();
let after = out
.points()
.iter()
.filter(|p| p.x <= 0.0 || p.y <= 0.0 || p.x >= 12.0 || p.y >= 12.0)
.count();
assert_eq!(
before, after,
"a locked boundary should keep every one of its vertices"
);
}
#[test]
#[ignore = "measurement harness, not an assertion"]
fn best_effort_distribution() {
distribution_table(
"engine blade",
&crate::tests::engine_blade(),
&[0.001, 0.005, 0.01, 0.05, 0.1, 0.5],
);
}
#[test]
#[ignore = "measurement harness, not an assertion"]
fn bunny_distribution() {
distribution_table(
"stanford bunny",
&crate::tests::stanford_bun_2(),
&[0.0002, 0.0005, 0.001, 0.005, 0.01, 0.05],
);
}
#[test]
#[ignore = "measurement harness, needs the private test data"]
#[cfg(all(feature = "ply", feature = "private_tests"))]
fn reference_scan_distribution() {
let path = std::path::Path::new("../../engeom-test-data")
.join("private-multi-align")
.join("sample_00")
.join("reference.ply");
let data = crate::io::load_ply_mesh_data(&path).unwrap();
let mesh = Mesh3::from_data(data, false).unwrap();
distribution_table(
"ATOS 5 reference scan",
&mesh,
&[0.001, 0.005, 0.01, 0.05, 0.5],
);
}
fn distribution_table(label: &str, input: &Mesh3, tols: &[f64]) {
use std::io::Write;
let (repaired, _) = HalfEdgeMesh3::from_mesh_repaired(input, &RepairOpts::default())
.expect("failed to repair the fixture into half-edge form");
let original = &Mesh3::try_from(&repaired).unwrap();
drop(repaired);
let aabb = original.aabb();
println!(
"\n=== {} ===\n{} faces, {} points, extents {:.1} x {:.1} x {:.1}\n\n\
distances pooled over both directions, as multiples of the stated tolerance.\n\n\
{:>7} {:>10} {:>6} {:>6} {:>6} {:>6} {:>7} {:>8} {:>8} {:>8} {:>8}",
label,
original.faces().len(),
original.points().len(),
aabb.extents().x,
aabb.extents().y,
aabb.extents().z,
"tol",
"faces",
"p50",
"p90",
"p99",
"p99.9",
"max",
"over 1x",
"over 2x",
"over 5x",
"over 10x"
);
for &tol in tols {
for guaranteed in [true, false] {
let mut he = HalfEdgeMesh3::try_from(original).unwrap();
let report = if guaranteed {
he.decimate_guaranteed(&crate::geom3::half_edge3::DecimateOpts::to_tolerance(
tol,
))
} else {
he.decimate_best_effort(&BestEffortOpts::to_tolerance(tol))
}
.unwrap();
let out = Mesh3::try_from(&he).unwrap();
let g = ShapeDifference::with_spread(original, &out, tol).unwrap();
let s = g.spread.unwrap();
println!(
"{:>7} {:>10} {:>5.1}% {:>5.2}x {:>5.2}x {:>5.2}x {:>5.2}x {:>6.1}x \
{:>7.3}% {:>7.3}% {:>7.3}% {:>7.3}%",
tol,
if guaranteed { "guaranteed" } else { "best" },
report.ratio() * 100.0,
s.p50 / tol,
s.p90 / tol,
s.p99 / tol,
s.p999 / tol,
s.max / tol,
s.over[0] * 100.0,
s.over[1] * 100.0,
s.over[2] * 100.0,
s.over[3] * 100.0
);
std::io::stdout().flush().ok();
}
}
}
#[test]
#[ignore = "measurement harness, not an assertion"]
fn best_effort_profile() {
let original = crate::tests::engine_blade();
println!(
"\n{} faces. fwd is original -> result, rev is result -> original.\n\n\
{:>6} {:>6} {:>6} {:>9} {:>9} {:>6} {:>6} {:>9} {:>9}",
original.faces().len(),
"",
"faces",
"time",
"fwd",
"rev",
"faces",
"time",
"fwd",
"rev"
);
println!(
"{:>6} {:>33} {:>33}",
"tol", "----- guaranteed -----", "----- best effort ----"
);
for tol in [0.001, 0.005, 0.01, 0.05, 0.1, 0.5] {
let mut a = HalfEdgeMesh3::try_from(&original).unwrap();
let start = std::time::Instant::now();
let ra = a
.decimate_guaranteed(&crate::geom3::half_edge3::DecimateOpts::to_tolerance(tol))
.unwrap();
let ta = start.elapsed().as_secs_f64();
let ga = ShapeDifference::new(&original, &Mesh3::try_from(&a).unwrap()).unwrap();
let mut b = HalfEdgeMesh3::try_from(&original).unwrap();
let start = std::time::Instant::now();
let rb = b
.decimate_best_effort(&BestEffortOpts::to_tolerance(tol))
.unwrap();
let tb = start.elapsed().as_secs_f64();
let gb = ShapeDifference::new(&original, &Mesh3::try_from(&b).unwrap()).unwrap();
println!(
"{:>6} {:>5.1}% {:>5.2}s {:>8.6} {:>8.6} {:>5.1}% {:>5.2}s {:>8.6} {:>8.6}",
tol,
ra.ratio() * 100.0,
ta,
ga.dense.reference_to_test,
ga.dense.test_to_reference,
rb.ratio() * 100.0,
tb,
gb.dense.reference_to_test,
gb.dense.test_to_reference
);
}
}
#[test]
fn a_bad_tolerance_is_refused() {
let mut he = HalfEdgeMesh3::try_from(&flat_grid(4)).unwrap();
assert!(
he.decimate_best_effort(&BestEffortOpts::to_tolerance(0.0))
.is_err()
);
assert!(
he.decimate_best_effort(&BestEffortOpts::to_tolerance(-1.0))
.is_err()
);
}
}