dedup_mesh 0.2.0

// SPDX-License-Identifier: MIT OR Apache-2.0
// Copyright (c) 2025 lacklustr@protonmail.com https://github.com/eadf

#![deny(
    rust_2018_compatibility,
    rust_2018_idioms,
    nonstandard_style,
    unused,
    future_incompatible,
    non_camel_case_types,
    unused_parens,
    non_upper_case_globals,
    unused_qualifications,
    unused_results,
    unused_imports,
    unused_variables,
    bare_trait_objects,
    ellipsis_inclusive_range_patterns,
    elided_lifetimes_in_paths
)]
#![allow(uncommon_codepoints)]

//! # `dedup_mesh`
//!
//! A library for de-duplicating 3D mesh vertices using spatial hashing and precision-aware clustering.
//!
//! This crate is designed for **robustness, speed, and precision**, with strong support for configurable behavior through **type-level polymorphism**.
//!
//! ## Compile-Time Specialization
//!
//! All major configuration points—such as threading strategy, topology type, pruning behavior, and tolerance handling—are controlled via **type parameters**, not runtime enums.
//!
//! This design enables the compiler to optimize each code path **statically**, resulting in:
//! - **No runtime branching overhead**
//! - **Inlining of behavior-specific logic**
//!
//! Note: If you use multiple distinct configurations (e.g., `Triangulated` and `Edges`), each one will be compiled separately. This increases code size slightly but ensures each variant is optimized independently.
//!
//! ## Flexible Vector Support
//!
//! Input and output vertex types are fully generic:
//!
//! - Any type that implements `Into<[T; 3]> + Clone + Sync` can be used as input
//! - Any type that implements `From<[T; 3]> + Into<[T; 3]> + Clone + Sync` can be used as output
//!
//! This means you can directly pass in or receive vertices using types from libraries like
//! `glam`, `nalgebra`, `cgmath` or your own custom structs
//!
//! ### Example
//! ```rust, ignore
//! use dedup_mesh::prelude::*;
//!
//! let (vertices, indices) = dedup::<f32, usize, glam::Vec3, MultiThreaded, Triangulated>(
//!     &input_vertices,
//!     &input_indices,
//!     0.001,
//!     PruneUnused,
//!     PruneDegenerate,
//!     CheckTolerance,
//! )?;
//! ```
//!
//! ## Features
//! - Spatial hashing with automatic precision scaling
//! - Exact or relaxed tolerance policies
//! - Support for point clouds, edge meshes, and triangles
//! - Single-threaded and multithreaded execution
//! - Zero-cost abstraction: unused features are fully optimized out
//!
//! ## MSRV
//!
//! Minimum Supported Rust Version: **1.85.1** (requires Rust 2024 edition)
//!
//! ## Crate Status
//!
//! - `#![no_std]`: Not yet supported
//! - Parallelism via `rayon`
//!

mod finite_check;
mod hash_grid;
mod index;
mod scalar;
mod threading;
mod topology;
mod util;

use crate::finite_check::CheckFiniteKernel;
use crate::scalar::ScalarKernel;
use crate::threading::CompatibleWith;
use crate::topology::TopologyKernel;
use num_traits::AsPrimitive;
use std::cmp::PartialEq;
use std::fmt::Debug;
use std::hash::Hash;

/// Specifies how to handle vertices that are not referenced by any input indices.
///
/// This affects only the original input vertex/index mapping.
/// If a triangle or edge is later pruned (e.g., due to being degenerate),
/// its vertices are **not** considered unused and will remain in the output.
///
/// See also: [`PruneUnused`] and [`KeepUnused`]
#[derive(Debug, Eq, Clone, Copy, PartialEq)]
pub enum PruneUnusedEnum {
    /// Remove all vertices that are not referenced by any input index.
    ///
    /// This is evaluated **only** on the input.
    /// Vertices from pruned triangles or edges are **not** considered unused.
    PruneUnused,

    /// Retain all vertices, even if they are not referenced by any index.
    KeepUnused,
}

#[derive(Debug, Eq, Clone, Copy, PartialEq)]
/// Defines how to handle degenerate mesh elements such as zero-area triangles or zero-length edges.
///
/// See [`PruneDegenerate`] & [`KeepDegenerate`] for usage examples.
///
/// # Behavior by Topology
///
/// - [`Triangulated`]: Removes triangles with repeated indices or zero area.
/// - [`Edges`]: Removes edges where both endpoints are the same.
/// - [`PointCloud`]: **No effect** — since points are atomic, no degeneracy is possible.
///
/// Use this policy when mesh cleanup or simplification is required.
pub enum PruneDegenerateEnum {
    /// Degenerate mesh objects (zero are triangles, zero length edges) are removed.
    PruneDegenerate,
    /// Degenerate mesh elements are retained as-is.
    KeepDegenerate,
}

#[derive(Debug, Eq, Clone, Copy, PartialEq)]
/// Defines how to treat the user provided tolerance.
/// See [`CheckTolerance`] & [`RelaxTolerance`]
pub enum ToleranceEnum {
    /// Check that the tolerance will fit the hash grid, report error if it does not
    CheckTolerance,
    /// Adjust the tolerance if it is too small to fit the hash grid.
    RelaxTolerance,
}

#[derive(Debug)]
/// The error type thrown when an error is detected, typically when a NaN or infinite vertex value
/// is detected.  
pub struct DeDupError(pub String);

impl std::fmt::Display for DeDupError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "DeDupError occurred: {}", self.0)
    }
}
impl std::error::Error for DeDupError {}

/// Threading policy for vertex de-duplication.
///
/// Selects how the algorithm executes: single-threaded, multithreaded, or auto-adaptive.
///
/// # Available Policies
///
/// - [`SingleThreaded`]: Uses only one core. Has the lowest per-core CPU overhead.
/// - [`MultiThreaded`]: Uses all available CPU cores via [`rayon`] (requires `parallel` feature).
/// - [`Auto`]: Automatically picks the best mode based on mesh size and feature availability.
///
/// # Performance Tradeoffs
///
/// - `SingleThreaded` mode is generally **more efficient per CPU cycle**, making it ideal for small-to-medium meshes.
/// - `MultiThreaded` mode is typically **faster in wall-clock time** on large meshes, thanks to parallelism.
///   It achieves this by scaling across cores, but at the cost of some coordination overhead.
///
/// # Feature Flag
///
/// - The `parallel` crate feature must be enabled to use [`MultiThreaded`] or allow [`Auto`] to select it.
///   Without it, [`Auto`] will always fall back to [`SingleThreaded`].
///
/// [`rayon`]: https://crates.io/crates/rayon
pub trait ThreadingPolicy: threading::ThreadingDispatch {}

/// Specify how input indices are interpreted (e.g., as [`Edges`], [`PointCloud`] or [`Triangulated`]).
pub trait TopologyPolicy: TopologyKernel {}

/// Choose between checking/no checking scalars for finite values by  [`CheckFinite`] or [`SkipCheckFinite`].
/// [`CheckFinite`] is required when using [`MultiThreaded`]
pub trait CheckFinitePolicy: CheckFiniteKernel {}

/// The scalar type used by the vertices, f32 or f64.
pub trait Scalar: ScalarKernel {}

/// Only `usize`, `u32`, and `u16` are possible as index types.
pub trait IndexType: index::IndexKernel {}

//pub trait ScalingPolicy: scaling::ScalingKernel {}

pub use finite_check::{CheckFinite, SkipCheckFinite};
#[cfg(feature = "parallel")]
pub use threading::MultiThreaded;
pub use threading::{Auto, SingleThreaded};

pub use PruneDegenerateEnum::{KeepDegenerate, PruneDegenerate};
pub use PruneUnusedEnum::{KeepUnused, PruneUnused};
pub use ToleranceEnum::{CheckTolerance, RelaxTolerance};
pub use topology::{Edges, PointCloud, Triangulated};

/// Performs de-duplication of 3D vertices in a mesh using spatial hashing.
///
/// Identifies vertices within a specified `tolerance` distance and merges them
/// into centroids. Returns deduplicated vertices and remapped indices.
///
/// # Spatial Hashing Strategy
///
/// Uses adaptive spatial hashing for efficient clustering:
/// 1. Computes bounding box and assesses coordinate precision
/// 2. Centers coordinates to maximize numerical precision  
/// 3. Selects optimal (smallest) integer type (`i16`, `i32`, `i64`) for hash grid
/// 4. Maps vertices to 3D grid cells of size `tolerance * 2`
///
/// # Type Parameters
///
/// - `T`: Scalar coordinate type (`f32`, `f64`) implementing [`Scalar`]
/// - `Index`: Index type (`u16`, `u32`, `usize`) implementing [`IndexType`]
/// - `Vout`: Output Vertex type. Must implement `Into<[T; 3]> + From<[T; 3]> + Clone + Sync`.
///   Note that this type can be different from the input vertex type.
/// - `Threading`: [`SingleThreaded`], [`MultiThreaded`], or [`Auto`]
/// - `Topology`: [`PointCloud`], [`Edges`], or [`Triangulated`]
///
/// # Arguments
///
/// - `vertices`: Input vertices (must implement `Into<[T; 3]> + Clone + Sync`)
/// - `indices`: Connectivity indices for the vertices
/// - `tolerance`: Maximum distance for vertices to be considered duplicates
/// - `prune_unused`: [`PruneUnused`] or [`KeepUnused`] for handling unused vertices
/// - `prune_degenerate`: [`PruneDegenerate`] or [`KeepDegenerate`] for topology cleanup
/// - `tolerance_policy`: [`CheckTolerance`] or [`RelaxTolerance`] for precision handling
///
/// # Returns
///
/// - `Ok((deduplicated_vertices, remapped_indices))` on success
/// - `Err(DeDupError)` for validation failures or precision issues
///
/// # Errors
///
/// - Input validation failures (empty data, mismatched indices, non-finite coordinates)
/// - **With [`CheckTolerance`]**: Precision limits exceeded for given tolerance
/// - **With [`RelaxTolerance`]**: Scaling cannot resolve precision issues (rare)
///
/// # Examples
///
/// ```rust
/// use dedup_mesh::prelude::*;
///
/// let vertices = vec![
///     [0.0, 0.0, 0.0],
///     [0.001, 0.0, 0.0],  // Within tolerance
///     [1.0, 0.0, 0.0],
/// ];
/// let indices = vec![0, 1, 2];
///
/// let (new_vertices, new_indices) = dedup::<f32, usize, [f32; 3], SingleThreaded, PointCloud>(
///     &vertices, &indices, 0.01, PruneUnused, KeepDegenerate, CheckTolerance
/// )?;
///
/// assert_eq!(new_vertices.len(), 2); // First two merged
/// # Ok::<(), DeDupError>(())
/// ```
///
/// # Performance Notes
///
/// - Single-threaded recommended for <2K vertices
/// - Performance depends on hash range ratio (`coordinate_span / tolerance`)
/// - Both tolerance policies have equivalent performance (minimal preprocessing overhead)
/// - [`CheckTolerance`]: Preserves user tolerance exactly, fails if numerical precision insufficient
/// - [`RelaxTolerance`]: May override tolerance with smallest achievable value for given mesh dimensions
///
/// # See Also
///
/// - [`ToleranceEnum`]: Detailed precision and scaling behavior
/// - [`ThreadingPolicy`]: Threading strategy comparison
/// - [`TopologyPolicy`]: Input interpretation modes
pub fn dedup<T, Index, Vout, Threading, 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,
    Threading: ThreadingPolicy,
    Topology: TopologyPolicy,
    usize: AsPrimitive<T>,
{
    if let Some(value) = Topology::handle_insufficient_data::<T, Index, Vout>(indices, prune_unused)
    {
        return Ok(value);
    }
    Threading::dedup_dispatch::<T, Index, Vout, Topology>(
        vertices,
        indices,
        tolerance,
        prune_unused,
        prune_degenerate,
        tolerance_policy,
    )
}

/// Performs bitwise-exact de-duplication of vertices.
///
/// This variant only merges **identical vertices**, without any tolerance. It's ideal for formats like STL,
/// where coordinates are often repeated byte-for-byte.
///
/// Unlike the main [`dedup`] function, this version does **not** use spatial hashing and has **no floating-point tolerance logic**.
///
/// # Compile-Time Customization
///
/// The behavior of this function is controlled entirely via type parameters:
///
/// - [`ThreadingPolicy`]: Controls threading. Currently only [`SingleThreaded`] and [`Auto`] are supported.
/// - [`TopologyPolicy`]: Controls how indices are interpreted: as points, edges, or triangles.
/// - [`CheckFinitePolicy`]: Optionally checks for NaN/Inf in coordinates.
///
/// # Type Parameters
///
/// - `T`: Scalar type for coordinates (e.g., `f32`, `f64`). Must implement [`Scalar`].
/// - `Index`: Index type. Use `u16`, `u32`, or `usize`.
/// - `Vout`: Output vertex type. Must implement `Into<[T; 3]> + From<[T; 3]> + Clone + Sync`.
///   Note that this type can be different from the input vertex type.
/// - `Threading`: Threading policy. Currently supports [`SingleThreaded`] and [`Auto`] only.
/// - `Topology`: Topology policy. Use [`PointCloud`], [`Edges`], or [`Triangulated`].
/// - `CheckFinite`: Finite check policy. Use [`CheckFinite`] or [`SkipCheckFinite`].
///
/// # Arguments
///
/// - `vertices`: Input vertices. Each must implement `Into<[T; 3]> + Clone + Sync`.
/// - `indices`: Index list describing connectivity, interpreted by the `Topology` policy.
/// - `prune_unused`: Whether to remove unreferenced vertices.
/// - `prune_degenerate`: Whether to remove degenerate geometry (e.g., zero-area triangles).
///
/// # Returns
///
/// - `Ok((deduplicated_vertices, remapped_indices))` — If processing succeeds.
/// - `Err(DeDupError)` — On validation or consistency failure.
///
/// # Errors
///
/// Returns [`DeDupError`] if input is invalid (e.g., non-finite values, mismatched index bounds).
///
/// # Example
///
/// ```rust
/// use dedup_mesh::prelude::*;
///
/// let vertices = vec![
///     [0.0, 0.0, 0.0],
///     [0.0, 0.0, 0.0],
///     [1.0, 0.0, 0.0],
/// ];
/// let indices = vec![0, 1, 2];
///
/// let (deduped_vertices, remapped_indices) = dedup_exact::<f32, usize, [f32;3], SingleThreaded, Triangulated, CheckFinite>(
///     &vertices, &indices, PruneUnused, PruneDegenerate
/// )?;
///
/// assert_eq!(deduped_vertices.len(), 2); // First two vertices merged
/// // The triangle becomes degenerate (0, 0, 1) and is pruned.
/// # Ok::<(), DeDupError>(())
/// ```
///
/// # Performance Notes
///
/// - Unlike [`dedup`], this function avoids spatial hashing and uses a deterministic hashing strategy based on coordinate bits.
/// - Multithreading is **not yet supported**, though `Auto` is accepted for forward compatibility.
/// - Performance is generally excellent for small to medium meshes, but may degrade linearly with very large inputs.
///
/// # See Also
///
/// - [`dedup`] — For tolerance-based spatial merging
/// - [`ThreadingPolicy`]: [`SingleThreaded`], [`Auto`] (currently supported)
/// - [`TopologyPolicy`]: [`PointCloud`], [`Edges`], [`Triangulated`]
/// - [`CheckFinitePolicy`]: [`CheckFinite`], [`SkipCheckFinite`]
//
// While dedup_exact() could be implemented as a thin wrapper over dedup_exact_from_iter(),
// it is provided as a standalone implementation to allow future optimizations — particularly for
// multithreaded backends. Unlike general iterators, slices (&[T]) offer tighter bounds on
// performance: they are contiguous, indexable, and cache-friendly. If a future [MultiThreaded]
// variant is enabled, this structure allows for more efficient partitioning and better
// SIMD/parallelism opportunities. Until then, both functions are functionally equivalent,
// but dedup_exact() is preferred when working directly with slices.
pub fn dedup_exact<T, Index, Vout, Threading, 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,
    Threading: ThreadingPolicy + CompatibleWith<CheckFinite>,
    Topology: TopologyPolicy,
    CheckFinite: CheckFinitePolicy,
{
    if let Some(value) = Topology::handle_insufficient_data::<T, Index, Vout>(indices, prune_unused)
    {
        return Ok(value);
    }
    Threading::dedup_exact_dispatch::<T, Index, Vout, Topology, CheckFinite>(
        vertices,
        indices,
        prune_unused,
        prune_degenerate,
    )
}

/// Performs bitwise-exact de-duplication of vertices.
///
/// This variant is optimized for scenarios like STL parsing or other cases where you:
/// - Have a flat stream of indices (not necessarily a slice),
/// - Use a custom function to retrieve vertex data from index-like keys,
/// - Want exact, zero-tolerance matching of vertices.
///
/// This function builds an internal vertex map via [`Hash`] and groups identical vertices.
/// All policy behavior is determined at compile time via type parameters.
///
/// # Type Parameters
///
/// - `T`: Scalar type (`f32`, `f64`). Must implement [`Scalar`].
/// - `OutputIndex`: Index type for the output index buffer. Use `u16`, `u32`, or `usize`.
/// - `Vout`: Output vertex type. Must implement `Into<[T; 3]> + From<[T; 3]> + Clone + Sync`.
///   Note that this type can be different from `Vin` type.
/// - `Topology`: Topology interpretation policy. See [`PointCloud`], [`Edges`], [`Triangulated`].
/// - `CheckFinite`: Policy for checking that vertex values are finite. Use [`CheckFinite`] or [`SkipCheckFinite`].
/// - `InputIndex`: Key/index type used by the input iterator and vertex accessor. Must implement `Hash + Eq + Clone + Sync`.
/// - `Vin`: Vertex type returned by `vertex_fn`. Must implement `Into<[T; 3]> + Clone + Sync`.
///
/// # Arguments
///
/// - `indices_iter`: An iterator over input indices (`impl IntoIterator<Item = InputIndex>`).
/// - `vertex_fn`: A function mapping `InputIndex` to a 3D vertex of type `Vin`.
/// - `estimated_vertices_len`: A rough upper bound on the number of unique input vertices. Used for preallocating capacity.
///   This improves performance by avoiding repeated reallocations.
///   If unsure, passing `0` is safe and equivalent to using `Vec::new()` internally.
/// - `prune_degenerate`: Whether to discard degenerate topology elements. See [`PruneDegenerate`] and [`KeepDegenerate`].
///
/// # Returns
///
/// On success, returns a tuple:
/// - `deduplicated_vertices`: A `Vec<Vout>` containing the merged, unique vertices.
/// - `remapped_indices`: A `Vec<OutputIndex>` with indices remapped to the new vertex list.
///
/// # Errors
///
/// Returns [`DeDupError`] if input contains invalid or non-finite coordinates (if [`CheckFinite`] is enabled)
///
/// # Example
///
/// ```rust
/// use dedup_mesh::prelude::*;
///
/// let vertices = vec![
///     [0.0_f32, 0.0, 0.0],
///     [0.0, 0.0, 0.0],
///     [1.0, 0.0, 0.0],
/// ];
/// let indices = vec![0, 1, 2];
///
/// let (deduped_vertices, remapped_indices) = dedup_exact_from_iter::<f32, usize, [f32; 3], Triangulated, CheckFinite, _, _>(
///     indices.into_iter(), |i: usize| vertices[i], vertices.len(), PruneDegenerate
/// )?;
///
/// assert_eq!(deduped_vertices.len(), 2);
/// assert_eq!(remapped_indices.len(), 0); // triangle was degenerate and pruned
/// # Ok::<(), DeDupError>(())
/// ```
///
/// # See Also
///
/// - [`dedup_exact`]: Simpler version using slices of vertices and indices
/// - [`TopologyPolicy`]: [`PointCloud`], [`Edges`], [`Triangulated`]
/// - [`CheckFinitePolicy`]: [`CheckFinite`], [`SkipCheckFinite`]
pub fn dedup_exact_from_iter<T, OutputIndex, Vout, Topology, CheckFinite, InputIndex, Vin>(
    indices_iter: impl IntoIterator<Item = InputIndex>,
    vertex_fn: impl Fn(InputIndex) -> Vin,
    estimated_vertices_len: usize,
    prune_degenerate: PruneDegenerateEnum,
) -> Result<(Vec<Vout>, Vec<OutputIndex>), DeDupError>
where
    T: Scalar,
    InputIndex: Hash + Eq + Clone + Sync,
    OutputIndex: IndexType,
    Vin: Into<[T; 3]> + Clone + Sync,
    Vout: Into<[T; 3]> + From<[T; 3]> + Clone + Sync,
    Topology: TopologyPolicy,
    CheckFinite: CheckFinitePolicy,
{
    match prune_degenerate {
        PruneDegenerate => threading::dedup_vertices_exact_from_iter::<
            T,
            InputIndex,
            OutputIndex,
            Vin,
            Vout,
            Topology,
            CheckFinite,
            true,
        >(indices_iter, vertex_fn, estimated_vertices_len),
        KeepDegenerate => threading::dedup_vertices_exact_from_iter::<
            T,
            InputIndex,
            OutputIndex,
            Vin,
            Vout,
            Topology,
            CheckFinite,
            false,
        >(indices_iter, vertex_fn, estimated_vertices_len),
    }
}

pub mod prelude {
    #[cfg(feature = "parallel")]
    pub use super::MultiThreaded;
    pub use super::{
        Auto, CheckFinitePolicy, DeDupError, Edges, IndexType, PointCloud,
        PruneDegenerateEnum::{self, KeepDegenerate, PruneDegenerate},
        PruneUnusedEnum::{self, KeepUnused, PruneUnused},
        Scalar, SingleThreaded, ThreadingPolicy,
        ToleranceEnum::{self, CheckTolerance, RelaxTolerance},
        TopologyPolicy, Triangulated, dedup, dedup_exact, dedup_exact_from_iter,
        finite_check::{CheckFinite, SkipCheckFinite},
    };
}