use std::cmp::Ordering;
use super::Mesh;
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub struct Decimation {
pub ratio: f64,
pub max_triangles: Option<usize>,
pub max_error: f64,
}
impl Decimation {
pub fn ratio(ratio: f64) -> Self {
Self {
ratio,
max_triangles: None,
max_error: f64::INFINITY,
}
}
#[must_use]
pub fn with_max_triangles(mut self, triangles: usize) -> Self {
self.max_triangles = Some(triangles);
self
}
#[must_use]
pub fn with_max_error(mut self, error: f64) -> Self {
self.max_error = error;
self
}
pub fn target(&self, triangles: usize) -> usize {
let by_ratio = (triangles as f64 * self.ratio).ceil() as usize;
self.max_triangles.map_or(by_ratio, |m| m.min(by_ratio))
}
}
#[derive(Debug, Clone, Copy, Default)]
struct Quadric([f64; 10]);
impl Quadric {
fn plane(n: [f64; 3], d: f64) -> Self {
let [a, b, c] = n;
Self([
a * a,
a * b,
a * c,
a * d,
b * b,
b * c,
b * d,
c * c,
c * d,
d * d,
])
}
fn add(&mut self, o: &Quadric) {
for (x, y) in self.0.iter_mut().zip(o.0) {
*x += y;
}
}
fn eval(&self, p: [f64; 3]) -> f64 {
let q = &self.0;
let [x, y, z] = p;
q[0] * x * x
+ 2.0 * q[1] * x * y
+ 2.0 * q[2] * x * z
+ 2.0 * q[3] * x
+ q[4] * y * y
+ 2.0 * q[5] * y * z
+ 2.0 * q[6] * y
+ q[7] * z * z
+ 2.0 * q[8] * z
+ q[9]
}
}
fn sub(a: [f64; 3], b: [f64; 3]) -> [f64; 3] {
[a[0] - b[0], a[1] - b[1], a[2] - b[2]]
}
fn cross(a: [f64; 3], b: [f64; 3]) -> [f64; 3] {
[
a[1] * b[2] - a[2] * b[1],
a[2] * b[0] - a[0] * b[2],
a[0] * b[1] - a[1] * b[0],
]
}
fn dot(a: [f64; 3], b: [f64; 3]) -> f64 {
a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
}
fn quality(a: [f64; 3], b: [f64; 3], c: [f64; 3]) -> f64 {
let n = cross(sub(b, a), sub(c, a));
let area2 = dot(n, n).sqrt();
let l = [
dot(sub(b, a), sub(b, a)),
dot(sub(c, b), sub(c, b)),
dot(sub(a, c), sub(a, c)),
];
let longest = l.iter().fold(0.0f64, |m, &x| m.max(x));
if longest == 0.0 {
0.0
} else {
area2 / longest * (2.0 / 3f64.sqrt())
}
}
#[derive(Debug, Clone, Copy)]
struct Candidate {
error: f64,
from: u32,
to: u32,
}
impl PartialEq for Candidate {
fn eq(&self, o: &Self) -> bool {
self.cmp(o) == Ordering::Equal
}
}
impl Eq for Candidate {}
impl PartialOrd for Candidate {
fn partial_cmp(&self, o: &Self) -> Option<Ordering> {
Some(self.cmp(o))
}
}
impl Ord for Candidate {
fn cmp(&self, o: &Self) -> Ordering {
o.error
.total_cmp(&self.error)
.then(o.from.cmp(&self.from))
.then(o.to.cmp(&self.to))
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct DecimationStats {
pub triangles_before: usize,
pub triangles_after: usize,
pub collapses: usize,
}
const NONE: u32 = u32::MAX;
struct Corners {
head: Vec<u32>,
next: Vec<u32>,
}
impl Corners {
fn new(vertices: usize, tris: &[[u32; 3]]) -> Self {
let mut head = vec![NONE; vertices];
let mut next = vec![NONE; 3 * tris.len()];
for (t, tri) in tris.iter().enumerate() {
for (k, &v) in tri.iter().enumerate() {
let c = 3 * t + k;
next[c] = head[v as usize];
head[v as usize] = c as u32;
}
}
Self { head, next }
}
fn of(&self, v: u32) -> impl Iterator<Item = u32> + '_ {
let mut c = self.head[v as usize];
std::iter::from_fn(move || {
(c != NONE).then(|| {
let out = c;
c = self.next[c as usize];
out
})
})
}
fn alive_tris<'a>(&'a self, v: u32, alive_tri: &'a [bool]) -> impl Iterator<Item = u32> + 'a {
self.of(v)
.map(|c| c / 3)
.filter(move |&t| alive_tri[t as usize])
}
fn merge(&mut self, u: u32, v: u32, alive_tri: &[bool]) {
let mut c = self.head[u as usize];
while c != NONE {
let following = self.next[c as usize];
if alive_tri[(c / 3) as usize] {
self.next[c as usize] = self.head[v as usize];
self.head[v as usize] = c;
}
c = following;
}
self.head[u as usize] = NONE;
let mut prev = NONE;
let mut c = self.head[v as usize];
while c != NONE {
let following = self.next[c as usize];
if alive_tri[(c / 3) as usize] {
prev = c;
} else if prev == NONE {
self.head[v as usize] = following;
} else {
self.next[prev as usize] = following;
}
c = following;
}
}
}
fn neighbours_into(
x: u32,
corners: &Corners,
tris: &[[u32; 3]],
alive_tri: &[bool],
out: &mut Vec<u32>,
) {
out.clear();
out.extend(
corners
.alive_tris(x, alive_tri)
.flat_map(|t| tris[t as usize])
.filter(|&w| w != x),
);
out.sort_unstable();
out.dedup();
}
const MIN_QUALITY: f64 = 0.05;
const MIN_NORMAL_COS: f64 = 0.2;
pub fn decimate(mesh: &mut Mesh, options: &Decimation) -> DecimationStats {
let nv = mesh.positions.len();
let before = mesh.triangles.len();
let target = options.target(before);
let mut stats = DecimationStats {
triangles_before: before,
triangles_after: before,
collapses: 0,
};
if target >= before || nv == 0 {
return stats;
}
let positions = &mesh.positions;
let pos = |i: u32| positions[i as usize].map(f64::from);
let mut tris: Vec<[u32; 3]> = std::mem::take(&mut mesh.triangles);
let mut alive_tri = vec![true; tris.len()];
let mut corners = Corners::new(nv, &tris);
let vertex_component = &mesh.vertex_component;
let comp_of = |v: u32| vertex_component.get(v as usize).copied().unwrap_or(0);
let ncomp = vertex_component
.iter()
.copied()
.max()
.map_or(1, |m| m as usize + 1);
let mut comp_tris = vec![0usize; ncomp];
for tri in &tris {
comp_tris[comp_of(tri[0]) as usize] += 1;
}
let mut quadric = vec![Quadric::default(); nv];
for tri in &tris {
let [a, b, c] = tri.map(pos);
let n = cross(sub(b, a), sub(c, a));
let len = dot(n, n).sqrt();
if len == 0.0 {
continue;
}
let n = n.map(|x| x / len);
let q = Quadric::plane(n, -dot(n, a));
for &v in tri {
quadric[v as usize].add(&q);
}
}
let mut alive_v = vec![true; nv];
let limit = if options.max_error.is_finite() {
options.max_error * options.max_error
} else {
f64::INFINITY
};
let (mut nbrs, mut ut, mut shared, mut nu, mut nv_) =
(Vec::new(), Vec::new(), Vec::new(), Vec::new(), Vec::new());
let mut candidates: Vec<Candidate> = Vec::with_capacity(before / 2 * 3 + 3);
let mut touched = vec![false; nv];
let mut remaining = before;
'passes: while remaining > target {
candidates.clear();
for v in 0..nv as u32 {
if !alive_v[v as usize] {
continue;
}
neighbours_into(v, &corners, &tris, &alive_tri, &mut nbrs);
for &w in &nbrs {
if w < v {
continue;
}
let mut q = quadric[v as usize];
q.add(&quadric[w as usize]);
let a = q.eval(pos(w)).max(0.0);
let b = q.eval(pos(v)).max(0.0);
let c = if a <= b {
Candidate {
error: a,
from: v,
to: w,
}
} else {
Candidate {
error: b,
from: w,
to: v,
}
};
if c.error <= limit {
candidates.push(c);
}
}
}
crate::par::sort_unstable(&mut candidates);
candidates.reverse();
touched.fill(false);
let mut collapsed = 0usize;
for c in &candidates {
if remaining <= target {
break 'passes;
}
let (u, v) = (c.from, c.to);
if touched[u as usize] || touched[v as usize] {
continue;
}
ut.clear();
ut.extend(corners.alive_tris(u, &alive_tri));
shared.clear();
shared.extend(
ut.iter()
.copied()
.filter(|&t| tris[t as usize].contains(&v)),
);
if shared.len() != 2 || comp_tris[comp_of(u) as usize] <= 4 {
continue;
}
neighbours_into(u, &corners, &tris, &alive_tri, &mut nu);
neighbours_into(v, &corners, &tris, &alive_tri, &mut nv_);
let common = nu.iter().filter(|w| nv_.binary_search(w).is_ok()).count();
if common != 2 {
continue;
}
let ok = ut.iter().filter(|t| !shared.contains(t)).all(|&t| {
let tri = tris[t as usize];
let old = tri.map(pos);
let new = tri.map(|i| pos(if i == u { v } else { i }));
let n0 = cross(sub(old[1], old[0]), sub(old[2], old[0]));
let n1 = cross(sub(new[1], new[0]), sub(new[2], new[0]));
let (l0, l1) = (dot(n0, n0).sqrt(), dot(n1, n1).sqrt());
l0 > 0.0
&& l1 > 0.0
&& dot(n0, n1) / (l0 * l1) >= MIN_NORMAL_COS
&& quality(new[0], new[1], new[2]) >= MIN_QUALITY
});
if !ok {
continue;
}
for &t in &shared {
alive_tri[t as usize] = false;
}
for &t in &ut {
if alive_tri[t as usize] {
for x in &mut tris[t as usize] {
if *x == u {
*x = v;
}
}
}
}
corners.merge(u, v, &alive_tri);
remaining -= 2;
comp_tris[comp_of(u) as usize] -= 2;
alive_v[u as usize] = false;
let qu = quadric[u as usize];
quadric[v as usize].add(&qu);
stats.collapses += 1;
collapsed += 1;
touched[u as usize] = true;
touched[v as usize] = true;
for &w in &nu {
touched[w as usize] = true;
}
for &w in &nv_ {
touched[w as usize] = true;
}
}
if collapsed == 0 {
break;
}
}
drop((candidates, corners, quadric, alive_v, touched));
let mut remap = vec![u32::MAX; nv];
let mut out = Mesh::default();
let used: Vec<bool> = {
let mut u = vec![false; nv];
for (t, tri) in tris.iter().enumerate() {
if alive_tri[t] {
for &v in tri {
u[v as usize] = true;
}
}
}
u
};
let has_normals = !mesh.normals.is_empty();
for v in 0..nv {
if !used[v] {
continue;
}
remap[v] = out.positions.len() as u32;
out.positions.push(mesh.positions[v]);
if has_normals {
out.normals.push(mesh.normals[v]);
}
out.vertex_atom.push(mesh.vertex_atom[v]);
out.vertex_patch.push(mesh.vertex_patch[v]);
if let Some(&c) = mesh.vertex_component.get(v) {
out.vertex_component.push(c);
}
}
out.triangles = tris
.iter()
.zip(&alive_tri)
.filter(|(_, a)| **a)
.map(|(t, _)| t.map(|v| remap[v as usize]))
.collect();
stats.triangles_after = out.triangles.len();
*mesh = out;
stats
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Sphere, SurfaceParams, compute_surface, mesh};
#[test]
fn halves_a_sphere_mesh_and_keeps_it_valid() {
let out = compute_surface(
&[Sphere::new([0.0; 3], 3.0)],
&SurfaceParams::vdw().with_spacing(0.2),
)
.unwrap();
let mut m = out.mesh.clone();
let stats = decimate(&mut m, &Decimation::ratio(0.5).with_max_error(0.5));
assert!(mesh::validate(&m).is_ok(), "{:?}", mesh::validate(&m));
assert!(
stats.triangles_after <= stats.triangles_before / 2 + 2,
"{stats:?}"
);
for p in &m.positions {
let r = p.iter().map(|c| f64::from(*c).powi(2)).sum::<f64>().sqrt();
assert!((r - 3.0).abs() < 1e-4, "{r}");
}
let (_, comps) = mesh::components(&m);
assert_eq!(comps.len(), 1);
assert_eq!(comps[0].euler, 2);
}
#[test]
fn error_bound_stops_collapses() {
let out = compute_surface(
&[Sphere::new([0.0; 3], 3.0)],
&SurfaceParams::vdw().with_spacing(0.3),
)
.unwrap();
let mut m = out.mesh.clone();
let stats = decimate(&mut m, &Decimation::ratio(0.01).with_max_error(1e-6));
assert!(stats.collapses < stats.triangles_before / 20, "{stats:?}");
assert!(mesh::validate(&m).is_ok());
}
#[test]
fn targets() {
assert_eq!(Decimation::ratio(0.5).target(100), 50);
assert_eq!(
Decimation::ratio(0.5).with_max_triangles(10).target(100),
10
);
let mut m = Mesh::default();
assert_eq!(decimate(&mut m, &Decimation::ratio(0.5)).collapses, 0);
}
}