use crate::common::IndexMask;
use crate::common::points::triangle_area;
use crate::{Mesh3, Result};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PatchLabels {
labels: Vec<u32>,
count: usize,
}
impl PatchLabels {
pub const NO_PATCH: u32 = u32::MAX;
pub fn new(labels: Vec<u32>, count: usize) -> Result<Self> {
for (i, &label) in labels.iter().enumerate() {
if label != Self::NO_PATCH && label as usize >= count {
return Err(format!(
"Face {} carries patch label {}, which is out of range for {} patches",
i, label, count
)
.into());
}
}
Ok(Self { labels, count })
}
pub fn labels(&self) -> &[u32] {
&self.labels
}
pub fn count(&self) -> usize {
self.count
}
pub fn len(&self) -> usize {
self.labels.len()
}
pub fn is_empty(&self) -> bool {
self.labels.is_empty()
}
pub fn label_of(&self, face: usize) -> Option<usize> {
match self.labels.get(face) {
Some(&label) if label != Self::NO_PATCH => Some(label as usize),
_ => None,
}
}
pub fn face_counts(&self) -> Vec<usize> {
let mut counts = vec![0usize; self.count];
for &label in self.labels.iter() {
if label != Self::NO_PATCH {
counts[label as usize] += 1;
}
}
counts
}
pub fn mask_of(&self, patch: usize) -> Result<IndexMask> {
if patch >= self.count {
return Err(format!(
"Patch {} is out of range for a labeling with {} patches",
patch, self.count
)
.into());
}
let mut mask = IndexMask::new(self.labels.len(), false);
let target = patch as u32;
for (i, &label) in self.labels.iter().enumerate() {
if label == target {
mask.set(i, true);
}
}
Ok(mask)
}
pub fn mask_where(&self, keep: impl Fn(usize) -> bool) -> IndexMask {
let keep: Vec<bool> = (0..self.count).map(&keep).collect();
let mut mask = IndexMask::new(self.labels.len(), false);
for (i, &label) in self.labels.iter().enumerate() {
if label != Self::NO_PATCH && keep[label as usize] {
mask.set(i, true);
}
}
mask
}
pub fn to_masks(&self) -> Vec<IndexMask> {
let mut masks = vec![IndexMask::new(self.labels.len(), false); self.count];
for (i, &label) in self.labels.iter().enumerate() {
if label != Self::NO_PATCH {
masks[label as usize].set(i, true);
}
}
masks
}
pub fn compute_stats(&self, mesh: &Mesh3) -> Result<Vec<PatchStats>> {
let faces = mesh.faces();
if faces.len() != self.labels.len() {
return Err(format!(
"A labeling over {} faces does not match a mesh with {} faces",
self.labels.len(),
faces.len()
)
.into());
}
let points = mesh.points();
let mut stats = vec![PatchStats::empty(); self.count];
for (i, &label) in self.labels.iter().enumerate() {
if label == Self::NO_PATCH {
continue;
}
let face = &faces[i];
let entry = &mut stats[label as usize];
let p = [
&points[face[0] as usize],
&points[face[1] as usize],
&points[face[2] as usize],
];
entry.face_count += 1;
entry.area += triangle_area(p[0], p[1], p[2]);
for point in p {
for axis in 0..3 {
entry.min[axis] = entry.min[axis].min(point[axis]);
entry.max[axis] = entry.max[axis].max(point[axis]);
}
}
}
Ok(stats)
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct PatchStats {
pub face_count: usize,
pub area: f64,
pub min: [f64; 3],
pub max: [f64; 3],
}
impl PatchStats {
fn empty() -> Self {
Self {
face_count: 0,
area: 0.0,
min: [f64::INFINITY; 3],
max: [f64::NEG_INFINITY; 3],
}
}
pub fn aabb_diagonal(&self) -> f64 {
if self.face_count == 0 {
return 0.0;
}
let mut total = 0.0;
for axis in 0..3 {
let d = self.max[axis] - self.min[axis];
total += d * d;
}
total.sqrt()
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Default)]
pub struct PatchFilter {
pub min_faces: Option<usize>,
pub min_area: Option<f64>,
pub min_aabb_diagonal: Option<f64>,
pub min_area_fraction: Option<f64>,
pub keep_largest_n: Option<usize>,
}
impl PatchFilter {
pub fn keep_largest() -> Self {
Self {
keep_largest_n: Some(1),
..Default::default()
}
}
pub fn with_min_faces(mut self, min_faces: usize) -> Self {
self.min_faces = Some(min_faces);
self
}
pub fn with_min_area(mut self, min_area: f64) -> Self {
self.min_area = Some(min_area);
self
}
pub fn with_min_aabb_diagonal(mut self, min_aabb_diagonal: f64) -> Self {
self.min_aabb_diagonal = Some(min_aabb_diagonal);
self
}
pub fn with_min_area_fraction(mut self, min_area_fraction: f64) -> Self {
self.min_area_fraction = Some(min_area_fraction);
self
}
pub fn with_keep_largest_n(mut self, keep_largest_n: usize) -> Self {
self.keep_largest_n = Some(keep_largest_n);
self
}
pub fn keep_flags(&self, stats: &[PatchStats]) -> Vec<bool> {
let mut keep = vec![true; stats.len()];
for (i, s) in stats.iter().enumerate() {
if let Some(min) = self.min_faces
&& s.face_count < min
{
keep[i] = false;
}
if let Some(min) = self.min_area
&& s.area < min
{
keep[i] = false;
}
if let Some(min) = self.min_aabb_diagonal
&& s.aabb_diagonal() < min
{
keep[i] = false;
}
}
if let Some(fraction) = self.min_area_fraction {
let largest = stats.iter().map(|s| s.area).fold(0.0, f64::max);
let threshold = largest * fraction;
for (i, s) in stats.iter().enumerate() {
if s.area < threshold {
keep[i] = false;
}
}
}
if let Some(n) = self.keep_largest_n {
let mut order: Vec<usize> = (0..stats.len()).collect();
order.sort_by(|&a, &b| {
stats[b]
.area
.partial_cmp(&stats[a].area)
.unwrap_or(std::cmp::Ordering::Equal)
.then(a.cmp(&b))
});
for &i in order.iter().skip(n) {
keep[i] = false;
}
}
keep
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::Iso3;
use approx::assert_relative_eq;
fn two_boxes() -> Mesh3 {
let mut mesh = Mesh3::create_box(2.0, 4.0, 6.0, false);
let mut other = Mesh3::create_box(1.0, 1.0, 1.0, false);
other.transform_in_place(&Iso3::translation(100.0, 0.0, 0.0));
mesh.append_in_place(&other).unwrap();
mesh
}
#[test]
fn stats_of_known_boxes() {
let mesh = two_boxes();
let labels = mesh.compute_patch_labels(None).unwrap();
assert_eq!(labels.count(), 2);
let stats = labels.compute_stats(&mesh).unwrap();
assert_eq!(stats[0].face_count, 12);
assert_eq!(stats[1].face_count, 12);
assert_relative_eq!(stats[0].area, 2.0 * (8.0 + 12.0 + 24.0), epsilon = 1e-10);
assert_relative_eq!(stats[1].area, 6.0, epsilon = 1e-10);
assert_relative_eq!(stats[0].aabb_diagonal(), 56.0_f64.sqrt(), epsilon = 1e-10);
assert_relative_eq!(stats[1].aabb_diagonal(), 3.0_f64.sqrt(), epsilon = 1e-10);
assert_relative_eq!(stats[1].min[0], 99.5, epsilon = 1e-10);
assert_relative_eq!(stats[1].max[0], 100.5, epsilon = 1e-10);
}
#[test]
fn face_counts_match_stats() {
let mesh = two_boxes();
let labels = mesh.compute_patch_labels(None).unwrap();
let counts = labels.face_counts();
let stats = labels.compute_stats(&mesh).unwrap();
assert_eq!(counts.len(), labels.count());
for (count, stat) in counts.iter().zip(stats.iter()) {
assert_eq!(*count, stat.face_count);
}
assert_eq!(counts.iter().sum::<usize>(), mesh.faces().len());
}
#[test]
fn mask_where_matches_expanded_masks() {
let mesh = two_boxes();
let labels = mesh.compute_patch_labels(None).unwrap();
let masks = labels.to_masks();
for keep in [0usize, 1] {
let selected = labels.mask_where(|p| p == keep);
assert_eq!(selected, masks[keep]);
assert_eq!(selected, labels.mask_of(keep).unwrap());
}
let all = labels.mask_where(|_| true);
assert_eq!(all.count_true(), mesh.faces().len());
let none = labels.mask_where(|_| false);
assert_eq!(none.count_true(), 0);
}
#[test]
fn mask_of_rejects_an_out_of_range_patch() {
let mesh = two_boxes();
let labels = mesh.compute_patch_labels(None).unwrap();
assert!(labels.mask_of(labels.count()).is_err());
}
#[test]
fn stats_reject_a_mesh_of_the_wrong_size() {
let mesh = two_boxes();
let labels = mesh.compute_patch_labels(None).unwrap();
let smaller = Mesh3::create_box(1.0, 1.0, 1.0, false);
assert!(labels.compute_stats(&smaller).is_err());
}
#[test]
fn new_rejects_a_label_beyond_the_count() {
assert!(PatchLabels::new(vec![0, 1, 2], 2).is_err());
assert!(PatchLabels::new(vec![0, 1, PatchLabels::NO_PATCH], 2).is_ok());
}
fn stat(face_count: usize, area: f64, span: f64) -> PatchStats {
PatchStats {
face_count,
area,
min: [0.0; 3],
max: [span, 0.0, 0.0],
}
}
#[test]
fn default_filter_keeps_everything() {
let stats = [stat(1, 0.001, 0.01), stat(100_000, 5000.0, 300.0)];
assert_eq!(PatchFilter::default().keep_flags(&stats), vec![true, true]);
}
#[test]
fn each_threshold_acts_on_its_own_measure() {
let stats = [stat(5000, 0.5, 1.0), stat(20, 400.0, 120.0)];
let by_faces = PatchFilter {
min_faces: Some(100),
..Default::default()
};
assert_eq!(by_faces.keep_flags(&stats), vec![true, false]);
let by_area = PatchFilter {
min_area: Some(10.0),
..Default::default()
};
assert_eq!(by_area.keep_flags(&stats), vec![false, true]);
let by_span = PatchFilter {
min_aabb_diagonal: Some(10.0),
..Default::default()
};
assert_eq!(by_span.keep_flags(&stats), vec![false, true]);
}
#[test]
fn criteria_intersect() {
let stats = [stat(5000, 0.5, 1.0), stat(20, 400.0, 120.0)];
let both = PatchFilter {
min_faces: Some(100),
min_area: Some(10.0),
..Default::default()
};
assert_eq!(both.keep_flags(&stats), vec![false, false]);
}
#[test]
fn area_fraction_is_relative_to_the_largest_patch() {
let stats = [
stat(10, 1000.0, 100.0),
stat(10, 5.0, 5.0),
stat(10, 0.5, 1.0),
];
let filter = PatchFilter {
min_area_fraction: Some(0.001),
..Default::default()
};
assert_eq!(filter.keep_flags(&stats), vec![true, true, false]);
}
#[test]
fn keep_largest_ranks_by_area_not_face_count() {
let stats = [stat(9000, 2.0, 2.0), stat(30, 900.0, 110.0)];
assert_eq!(
PatchFilter::keep_largest().keep_flags(&stats),
vec![false, true]
);
}
#[test]
fn keep_largest_n_takes_the_top_n() {
let stats = [
stat(10, 5.0, 5.0),
stat(10, 100.0, 50.0),
stat(10, 50.0, 25.0),
stat(10, 1.0, 1.0),
];
let filter = PatchFilter {
keep_largest_n: Some(2),
..Default::default()
};
assert_eq!(filter.keep_flags(&stats), vec![false, true, true, false]);
}
#[test]
fn keep_largest_breaks_ties_deterministically() {
let stats = [stat(10, 7.0, 3.0), stat(10, 7.0, 3.0), stat(10, 7.0, 3.0)];
let filter = PatchFilter {
keep_largest_n: Some(2),
..Default::default()
};
for _ in 0..8 {
assert_eq!(filter.keep_flags(&stats), vec![true, true, false]);
}
}
#[test]
fn keep_largest_n_beyond_the_patch_count_keeps_everything() {
let stats = [stat(10, 5.0, 5.0), stat(10, 1.0, 1.0)];
let filter = PatchFilter {
keep_largest_n: Some(10),
..Default::default()
};
assert_eq!(filter.keep_flags(&stats), vec![true, true]);
}
#[test]
fn an_empty_patch_list_filters_to_nothing() {
assert!(PatchFilter::keep_largest().keep_flags(&[]).is_empty());
}
fn body_with_flyer() -> Mesh3 {
let mut mesh = Mesh3::create_box(20.0, 20.0, 20.0, false);
let mut flyer = Mesh3::create_box(0.5, 0.5, 0.5, false);
flyer.transform_in_place(&Iso3::translation(300.0, 0.0, 0.0));
mesh.append_in_place(&flyer).unwrap();
mesh
}
#[test]
fn remove_small_patches_drops_the_flyer() {
let mesh = body_with_flyer();
assert_eq!(mesh.compute_patch_labels(None).unwrap().count(), 2);
let cleaned = mesh
.remove_small_patches(&PatchFilter::keep_largest())
.unwrap();
assert_eq!(cleaned.compute_patch_labels(None).unwrap().count(), 1);
assert_eq!(cleaned.faces().len(), 12);
let stats = cleaned
.compute_patch_labels(None)
.unwrap()
.compute_stats(&cleaned)
.unwrap();
assert_relative_eq!(
stats[0].aabb_diagonal(),
(3.0_f64).sqrt() * 20.0,
epsilon = 1e-9
);
}
#[test]
fn absolute_thresholds_drop_the_flyer() {
let mesh = body_with_flyer();
for filter in [
PatchFilter {
min_area: Some(10.0),
..Default::default()
},
PatchFilter {
min_aabb_diagonal: Some(5.0),
..Default::default()
},
PatchFilter {
min_area_fraction: Some(0.01),
..Default::default()
},
] {
let cleaned = mesh.remove_small_patches(&filter).unwrap();
assert_eq!(
cleaned.faces().len(),
12,
"filter {:?} kept the wrong set",
filter
);
}
}
#[test]
fn attributes_survive_patch_removal() {
let mut mesh = body_with_flyer();
let labels: Vec<u32> = (0..mesh.faces().len() as u32).collect();
mesh.set_face_labels(Some(labels)).unwrap();
let cleaned = mesh
.remove_small_patches(&PatchFilter::keep_largest())
.unwrap();
let kept = cleaned.face_labels().expect("face labels should survive");
assert_eq!(kept.len(), 12);
assert_eq!(kept, &(0..12u32).collect::<Vec<_>>()[..]);
}
#[test]
fn a_filter_that_keeps_everything_is_a_no_op() {
let mesh = body_with_flyer();
let same = mesh.remove_small_patches(&PatchFilter::default()).unwrap();
assert_eq!(same.faces().len(), mesh.faces().len());
assert_eq!(same.points().len(), mesh.points().len());
}
#[test]
fn discarding_every_patch_is_an_error() {
let mesh = body_with_flyer();
let filter = PatchFilter {
min_faces: Some(1_000_000),
..Default::default()
};
assert!(mesh.remove_small_patches(&filter).is_err());
}
#[test]
fn patch_mask_reports_what_would_be_kept() {
let mesh = body_with_flyer();
let mask = mesh.patch_mask(&PatchFilter::keep_largest()).unwrap();
assert_eq!(mask.count_true(), 12);
assert_eq!(mask.len(), mesh.faces().len());
for face in 0..12 {
assert!(mask.get(face));
}
for face in 12..mesh.faces().len() {
assert!(!mask.get(face));
}
}
#[test]
fn masked_faces_are_excluded_from_stats() {
let mesh = two_boxes();
let mut mask = IndexMask::new(mesh.faces().len(), false);
for i in 0..12 {
mask.set(i, true);
}
let labels = mesh.compute_patch_labels(Some(&mask)).unwrap();
assert_eq!(labels.count(), 1);
let stats = labels.compute_stats(&mesh).unwrap();
assert_eq!(stats[0].face_count, 12);
assert_relative_eq!(stats[0].area, 88.0, epsilon = 1e-10);
for face in 12..mesh.faces().len() {
assert_eq!(labels.label_of(face), None);
}
}
}