use crate::budget::Budget;
use crate::remap::{weld_position, weld_table_len};
use crate::workspace::{checked_bytes, Work};
use crate::{Error, Positions, Workspace};
use alloc::vec::Vec;
const NONE: u32 = u32::MAX;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct SanitizeOptions(u32);
impl SanitizeOptions {
pub const EMPTY: Self = Self(0);
pub const REJECT_INVALID: Self = Self(1);
pub const COINCIDENT_CORNERS: Self = Self(2);
pub const WELD_POSITIONS: Self = Self(4);
pub const IGNORE_ORIENTATION: Self = Self(8);
pub const fn from_bits(bits: u32) -> Result<Self, Error> {
if bits & !15 != 0 {
Err(Error::UnknownFlags)
} else {
Ok(Self(bits))
}
}
pub const fn bits(self) -> u32 {
self.0
}
pub const fn contains(self, other: Self) -> bool {
self.0 & other.0 == other.0
}
}
impl core::ops::BitOr for SanitizeOptions {
type Output = Self;
fn bitor(self, rhs: Self) -> Self {
Self(self.0 | rhs.0)
}
}
impl core::ops::BitOrAssign for SanitizeOptions {
fn bitor_assign(&mut self, rhs: Self) {
self.0 |= rhs.0;
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct SanitizeReport {
pub input_triangles: usize,
pub output_triangles: usize,
pub out_of_range: usize,
pub non_finite: usize,
pub repeated_index: usize,
pub coincident_corners: usize,
pub duplicate: usize,
pub reversed_duplicate: usize,
}
impl SanitizeReport {
pub const fn removed(&self) -> usize {
self.out_of_range
+ self.non_finite
+ self.repeated_index
+ self.coincident_corners
+ self.duplicate
+ self.reversed_duplicate
}
pub const fn index_count(&self) -> usize {
self.output_triangles * 3
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct SanitizedMeshGeneric<I: crate::Index = u32> {
pub indices: Vec<I>,
pub report: SanitizeReport,
}
#[inline]
pub fn sanitize_generic<I: crate::Index>(
indices: &[I],
positions: Positions<'_>,
options: SanitizeOptions,
workspace: &mut Workspace,
) -> Result<SanitizedMeshGeneric<I>, Error> {
I::with_input(indices, workspace, |indices, workspace| {
sanitize_u32(indices, positions, options, workspace)
.and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
})
}
fn sanitize_u32(
indices: &[u32],
positions: Positions<'_>,
options: SanitizeOptions,
workspace: &mut Workspace,
) -> Result<SanitizedMeshGeneric, Error> {
let mut work = workspace.begin();
let result = (|| {
let mut budget = Budget::new(workspace);
let (keep, report) = classify(indices, positions, options, &mut budget, &mut work)?;
let mut out = budget.reserved::<u32>(report.index_count())?;
emit(indices, &keep, &mut work, |triangle| {
out.extend_from_slice(triangle);
})?;
Ok(SanitizedMeshGeneric {
indices: out,
report,
})
})();
workspace.finish(&work);
result
}
pub const fn sanitize_bound(index_count: usize) -> usize {
index_count
}
#[inline]
pub fn sanitize_into_generic<I: crate::Index>(
destination: &mut [I],
indices: &[I],
positions: Positions<'_>,
options: SanitizeOptions,
workspace: &mut Workspace,
) -> Result<SanitizeReport, Error> {
I::with_input(indices, workspace, |indices, workspace| {
I::with_mut(destination, workspace, |destination, workspace| {
sanitize_into_u32(destination, indices, positions, options, workspace)
})
})
}
fn sanitize_into_u32(
destination: &mut [u32],
indices: &[u32],
positions: Positions<'_>,
options: SanitizeOptions,
workspace: &mut Workspace,
) -> Result<SanitizeReport, Error> {
let mut work = workspace.begin();
let result = (|| {
let mut budget = Budget::new(workspace);
let (keep, report) = classify(indices, positions, options, &mut budget, &mut work)?;
let Some(out) = destination.get_mut(..report.index_count()) else {
return Err(Error::BufferTooSmall);
};
let mut write = 0;
emit(indices, &keep, &mut work, |triangle| {
out[write..write + 3].copy_from_slice(triangle);
write += 3;
})?;
Ok(report)
})();
workspace.finish(&work);
result
}
fn emit(
indices: &[u32],
keep: &[bool],
work: &mut Work,
mut write: impl FnMut(&[u32; 3]),
) -> Result<(), Error> {
let triangles = indices.as_chunks::<3>().0;
work.add(triangles.len())?;
for (triangle, &kept) in triangles.iter().zip(keep) {
if kept {
write(triangle);
}
}
Ok(())
}
#[inline]
pub(crate) fn canonical(t: [u32; 3]) -> [u32; 3] {
let a = t;
let b = [t[1], t[2], t[0]];
let c = [t[2], t[0], t[1]];
let first = if b < a { b } else { a };
if c < first {
c
} else {
first
}
}
pub(crate) fn steps(n: usize) -> usize {
(usize::BITS - n.leading_zeros()) as usize + 1
}
pub(crate) fn sort_work(n: usize) -> Result<usize, Error> {
n.checked_mul(steps(n)).ok_or(Error::SizeOverflow)
}
#[derive(Clone, Copy)]
struct Face {
class: [u32; 3],
index: u32,
mirrored: bool,
}
#[inline]
fn finite(p: [f32; 3]) -> bool {
p.iter().all(|v| v.is_finite())
}
fn classify(
indices: &[u32],
positions: Positions<'_>,
options: SanitizeOptions,
budget: &mut Budget<'_>,
work: &mut Work,
) -> Result<(Vec<bool>, SanitizeReport), Error> {
if !indices.len().is_multiple_of(3) {
return Err(Error::InvalidTopology);
}
checked_bytes(indices.len(), 4)?;
let triangles = indices.as_chunks::<3>().0;
budget.ws.charge_retained()?;
let mut keep = budget.filled(triangles.len(), false)?;
let mut report = SanitizeReport {
input_triangles: triangles.len(),
..SanitizeReport::default()
};
let candidates = if let Some(packed) = positions.packed_values() {
screen(options, triangles, &mut keep, &mut report, work, |i| {
packed.get(i as usize).copied()
})?
} else {
screen(options, triangles, &mut keep, &mut report, work, |i| {
positions.get(i as usize)
})?
};
if candidates > 0 {
let read = |i: u32| positions.get(i as usize);
dedup(
options,
triangles,
&mut keep,
&mut report,
budget,
work,
read,
)?;
}
Ok((keep, report))
}
pub(crate) fn screen(
options: SanitizeOptions,
triangles: &[[u32; 3]],
keep: &mut [bool],
report: &mut SanitizeReport,
work: &mut Work,
read: impl Fn(u32) -> Option<[f32; 3]>,
) -> Result<usize, Error> {
let reject = options.contains(SanitizeOptions::REJECT_INVALID);
let coincident = options.contains(SanitizeOptions::COINCIDENT_CORNERS);
let mut candidates = 0;
for (&[a, b, c], kept) in triangles.iter().zip(keep.iter_mut()) {
work.add(1)?;
let (Some(pa), Some(pb), Some(pc)) = (read(a), read(b), read(c)) else {
if reject {
return Err(Error::IndexOutOfBounds);
}
report.out_of_range += 1;
continue;
};
if !(finite(pa) && finite(pb) && finite(pc)) {
if reject {
return Err(Error::NumericalFailure);
}
report.non_finite += 1;
continue;
}
if a == b || a == c || b == c {
report.repeated_index += 1;
continue;
}
if coincident && (pa == pb || pa == pc || pb == pc) {
report.coincident_corners += 1;
continue;
}
*kept = true;
candidates += 1;
}
Ok(candidates)
}
fn dedup(
options: SanitizeOptions,
triangles: &[[u32; 3]],
keep: &mut [bool],
report: &mut SanitizeReport,
budget: &mut Budget<'_>,
work: &mut Work,
read: impl Fn(u32) -> Option<[f32; 3]>,
) -> Result<(), Error> {
let candidates = keep.iter().filter(|&&k| k).count();
u32::try_from(triangles.len()).map_err(|_| Error::SizeOverflow)?;
let welded = if options.contains(SanitizeOptions::WELD_POSITIONS) {
Some(weld_candidates(
triangles, keep, candidates, budget, work, &read,
)?)
} else {
None
};
let reversed = options.contains(SanitizeOptions::IGNORE_ORIENTATION);
work.add(candidates)?;
work.add(sort_work(candidates)?)?;
let mut faces = budget.reserved::<Face>(candidates)?;
let mut nth = 0;
for (index, (triangle, &kept)) in triangles.iter().zip(keep.iter()).enumerate() {
if !kept {
continue;
}
let corners = welded.as_ref().map_or(*triangle, |w| w[nth]);
nth += 1;
let key = canonical(corners);
let mirror = canonical([corners[0], corners[2], corners[1]]);
let (class, mirrored) = if reversed && mirror < key {
(mirror, true)
} else {
(key, false)
};
faces.push(Face {
class,
index: index as u32,
mirrored,
});
}
if let Some(welded) = welded {
budget.release(welded);
}
faces.sort_unstable_by(|a, b| a.class.cmp(&b.class).then(a.index.cmp(&b.index)));
let mut first: Option<([u32; 3], bool)> = None;
for face in &faces {
match first {
Some((class, mirrored)) if class == face.class => {
keep[face.index as usize] = false;
if mirrored == face.mirrored {
report.duplicate += 1;
} else {
report.reversed_duplicate += 1;
}
}
_ => {
first = Some((face.class, face.mirrored));
report.output_triangles += 1;
}
}
}
budget.release(faces);
Ok(())
}
fn weld_candidates(
triangles: &[[u32; 3]],
keep: &[bool],
candidates: usize,
budget: &mut Budget<'_>,
work: &mut Work,
read: &impl Fn(u32) -> Option<[f32; 3]>,
) -> Result<Vec<[u32; 3]>, Error> {
let corner_count = candidates.checked_mul(3).ok_or(Error::SizeOverflow)?;
work.add(corner_count)?;
work.add(sort_work(corner_count)?)?;
let mut referenced = budget.reserved::<u32>(corner_count)?;
for (triangle, _) in triangles.iter().zip(keep).filter(|(_, &k)| k) {
referenced.extend_from_slice(triangle);
}
referenced.sort_unstable();
referenced.dedup();
let unique = referenced.len();
if unique >= NONE as usize {
return Err(Error::SizeOverflow);
}
work.add(unique)?;
let mut compact = budget.reserved::<[f32; 3]>(unique)?;
for &vertex in &referenced {
compact.push(read(vertex).ok_or(Error::IndexOutOfBounds)?);
}
let table_len = weld_table_len(unique)?;
work.add(unique)?;
work.add(table_len)?;
let mut remap = budget.filled(unique, NONE)?;
let mut table = budget.filled(table_len, NONE)?;
work.add(sort_work(corner_count)?)?;
let mut welded = budget.reserved::<[u32; 3]>(candidates)?;
let compact_positions = Positions::from_packed(&compact);
let result = (|| {
for (triangle, _) in triangles.iter().zip(keep).filter(|(_, &k)| k) {
let mut corners = [0; 3];
for (corner, &vertex) in corners.iter_mut().zip(triangle) {
let id = referenced
.binary_search(&vertex)
.map_err(|_| Error::IndexOutOfBounds)?;
*corner =
weld_position(id as u32, &mut remap, &mut table, compact_positions, work)?;
}
welded.push(corners);
}
Ok(())
})();
budget.release(referenced);
budget.release(compact);
budget.release(remap);
budget.release(table);
result?;
Ok(welded)
}
#[inline]
pub fn sanitize(
indices: &[u32],
positions: Positions<'_>,
options: SanitizeOptions,
workspace: &mut Workspace,
) -> Result<SanitizedMesh, Error> {
sanitize_generic::<u32>(indices, positions, options, workspace).map(Into::into)
}
#[inline]
pub fn sanitize_into(
destination: &mut [u32],
indices: &[u32],
positions: Positions<'_>,
options: SanitizeOptions,
workspace: &mut Workspace,
) -> Result<SanitizeReport, Error> {
sanitize_into_generic::<u32>(destination, indices, positions, options, workspace)
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct SanitizedMesh {
pub indices: Vec<u32>,
pub report: SanitizeReport,
}
impl From<SanitizedMeshGeneric<u32>> for SanitizedMesh {
#[inline]
fn from(value: SanitizedMeshGeneric<u32>) -> Self {
Self {
indices: value.indices,
report: value.report,
}
}
}
impl From<SanitizedMesh> for SanitizedMeshGeneric<u32> {
#[inline]
fn from(value: SanitizedMesh) -> Self {
Self {
indices: value.indices,
report: value.report,
}
}
}