use crate::hash_grid::{HashGrid, HashType};
use crate::scalar::ScalarKernel;
use crate::threading::{CompatibleWith, ThreadingDispatch, ThreadingKernel, compute_centroid};
use crate::util::UnsafeVob;
use crate::util::{Aabb, Array3};
use crate::{
CheckFinitePolicy, DeDupError, KeepDegenerate, KeepUnused, PruneDegenerate,
PruneDegenerateEnum, PruneUnused, PruneUnusedEnum, RelaxTolerance, Scalar, ToleranceEnum,
TopologyPolicy,
};
use crate::{IndexType, SingleThreaded};
use num_traits::AsPrimitive;
use rustc_hash::FxHashMap;
use smallvec::{SmallVec, smallvec};
use vob::Vob;
impl<F: CheckFinitePolicy> CompatibleWith<F> for SingleThreaded {}
impl ThreadingDispatch for SingleThreaded {
fn dedup_dispatch<T, Index, Vout, Topology>(
vertices: &[impl Into<[T; 3]> + Clone + Sync],
indices: &[Index],
tolerance: T,
prune_unused: PruneUnusedEnum,
prune_degenerate: PruneDegenerateEnum,
tolerance_policy: ToleranceEnum,
) -> Result<(Vec<Vout>, Vec<Index>), DeDupError>
where
T: Scalar,
Index: IndexType,
Vout: Into<[T; 3]> + From<[T; 3]> + Clone + Sync,
Topology: TopologyPolicy,
usize: AsPrimitive<T>,
{
let used_vertices = match prune_unused {
PruneUnused => Self::get_unused_vertices::<T, Index>(vertices, indices)?,
KeepUnused => None,
};
T::dedup_with_optimal_hash::<Index, Vout, Self, Topology>(
vertices,
indices,
tolerance,
prune_degenerate,
used_vertices,
tolerance_policy == RelaxTolerance,
)
}
fn dedup_exact_dispatch<T, Index, Vout, Topology, CheckFinite>(
vertices: &[impl Into<[T; 3]> + Clone + Sync],
indices: &[Index],
prune_unused: PruneUnusedEnum,
prune_degenerate: PruneDegenerateEnum,
) -> Result<(Vec<Vout>, Vec<Index>), DeDupError>
where
T: Scalar,
Index: IndexType,
Vout: Into<[T; 3]> + From<[T; 3]> + Clone + Sync,
Topology: TopologyPolicy,
CheckFinite: CheckFinitePolicy,
{
let used_vertices = match prune_unused {
PruneUnused => Self::get_unused_vertices::<T, Index>(vertices, indices)?,
KeepUnused => None,
};
let (vertices, remap) =
Self::dedup_vertices_exact::<T, Index, Vout, CheckFinite>(vertices, used_vertices)?;
match prune_degenerate {
PruneDegenerate => {
Topology::remap_indices::<T, Index, Vout, true>(vertices, indices, &remap)
}
KeepDegenerate => {
Topology::remap_indices::<T, Index, Vout, false>(vertices, indices, &remap)
}
}
}
}
impl ThreadingKernel for SingleThreaded {
fn dedup_vertices<T, Index, Vout, H, const AXIS: usize>(
_aabb: Aabb<T>,
aabb_center: [T; 3],
input_vertices: &[impl Into<[T; 3]> + Clone + Sync],
tolerance: T,
used_vertices: Option<Vob>,
) -> Result<(Vec<Vout>, Vec<Index>), DeDupError>
where
T: ScalarKernel,
Index: IndexType,
Vout: Into<[T; 3]> + From<[T; 3]> + Clone + Sync,
H: HashType<T>,
usize: AsPrimitive<T>,
{
let original_vertex_count = input_vertices.len();
let mut spatial_index =
HashGrid::<T, H>::with_tolerance_and_capacity(tolerance, input_vertices.len());
let mut clusters: Vec<SmallVec<[usize; 1]>> = Vec::with_capacity(input_vertices.len());
if let Some(ref used_vertices) = used_vertices {
cluster_vertices::<T, H, _, _>(
used_vertices
.iter_set_bits(..)
.map(|i| (i, &input_vertices[i])),
aabb_center,
&mut spatial_index,
&mut clusters,
)?;
} else {
cluster_vertices::<T, H, _, _>(
input_vertices.iter().enumerate(),
aabb_center,
&mut spatial_index,
&mut clusters,
)?;
}
let mut unique_vertices: Vec<Vout> = Vec::with_capacity(clusters.len());
let mut remap = vec![Index::MAX; original_vertex_count];
for cluster in clusters {
let representative_idx = Index::from_usize(unique_vertices.len());
unique_vertices.push(
compute_centroid::<T, 0>(&cluster, input_vertices)
.unwrap()
.into(),
);
for &original_idx in &cluster {
remap[original_idx] = representative_idx;
}
}
Ok((unique_vertices, remap))
}
fn dedup_vertices_exact<T, Index, Vout, CheckFinite>(
vertices: &[impl Into<[T; 3]> + Clone + Sync],
used_vertices: Option<Vob>,
) -> Result<(Vec<Vout>, Vec<Index>), DeDupError>
where
T: ScalarKernel,
Index: IndexType,
Vout: Into<[T; 3]> + From<[T; 3]> + Clone + Sync,
CheckFinite: CheckFinitePolicy,
{
use crate::util::Array3;
let mut index_map = FxHashMap::with_capacity_and_hasher(vertices.len(), Default::default());
let mut new_vertices: Vec<Vout> = Vec::with_capacity(vertices.len());
let mut remap = vec![Index::MAX; vertices.len()];
let mut get_index_or_insert = |point: [T; 3]| -> Result<Index, DeDupError> {
if CheckFinite::CHECK_FINITE
&& !(point[0].is_finite() && point[1].is_finite() && point[2].is_finite())
{
return Err(DeDupError(
format!("Non finite vertex coordinate found: {point:?}").to_string(),
));
}
let index = index_map.entry(point.get_hash()).or_insert_with(|| {
let new_index = new_vertices.len();
new_vertices.push(point.into());
new_index
});
Ok(Index::from_usize(*index))
};
if let Some(used_vertices) = used_vertices {
for old_index in used_vertices.iter_set_bits(..) {
let new_index = get_index_or_insert(vertices[old_index].clone().into())?;
remap[old_index] = new_index;
}
} else {
for (old_index, v) in vertices.iter().enumerate() {
let new_index = get_index_or_insert(v.clone().into())?;
remap[old_index] = new_index;
}
}
Ok((new_vertices, remap))
}
fn get_unused_vertices<T, Index>(
vertices: &[impl Into<[T; 3]> + Clone + Sync],
indices: &[Index],
) -> Result<Option<Vob>, DeDupError>
where
T: ScalarKernel,
Index: IndexType,
{
let mut used_vertices = Vob::from_elem(false, vertices.len());
for &idx in indices {
if idx.to_usize() > vertices.len() {
return Err(DeDupError(
format!("Mesh index out of bounds {idx:?} >= {} ", vertices.len()).to_string(),
));
}
used_vertices.ᚦset(idx.to_usize(), true);
}
Ok(Some(used_vertices))
}
}
fn cluster_vertices<'a, T, H, V, I>(
vertex_iter: I,
center: [T; 3],
spatial_index: &mut HashGrid<T, H>,
clusters: &mut Vec<SmallVec<[usize; 1]>>,
) -> Result<(), DeDupError>
where
T: ScalarKernel,
H: HashType<T>,
V: Into<[T; 3]> + Clone + 'a,
I: Iterator<Item = (usize, &'a V)>,
usize: AsPrimitive<T>,
{
for (vertex_index, vertex) in vertex_iter {
let point: [T; 3] = vertex.clone().into().sub(center);
if let Some(closest) = spatial_index.query_point(point) {
clusters[closest].push(vertex_index);
} else {
let cluster_id = clusters.len();
clusters.push(smallvec![vertex_index]);
spatial_index.insert(point, cluster_id);
}
}
Ok(())
}