remesh 0.0.5

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

mod check_connectivity;

use crate::common::VertexIndex;
use crate::common::macros::integrity_println;
use crate::corner_table::{CornerIndex, CornerTable};
use crate::prelude::RemeshError;
use rustc_hash::FxHashMap;
use smallvec::SmallVec;

#[derive(Debug, Clone)]
pub(crate) struct NonManifoldEdge {
    pub v_i: VertexIndex,
    pub v_j: VertexIndex,
    pub corners: SmallVec<[CornerIndex; 2]>, // All 'opposite' corners sharing this edge
}

enum EdgeFixResult {
    #[allow(dead_code)]
    /// Edge was successfully fixed, no further processing needed
    Done,

    /// Mesh needs vertex manifold checking before it can be processed
    NeedsVertexManifoldCheck,

    /// Edge couldn't be fixed now, retry later
    RetryLater(NonManifoldEdge),
}

impl<const ENABLE_UNSAFE: bool> CornerTable<ENABLE_UNSAFE> {
    /// Build corner table from triangle indices, detecting non-manifold edge geometry
    /// Returns the corner table AND lists of problematic edges for fixing.
    /// (´vertex_of_corner´ are vertex indices in groups of 3 forming a triangle)
    fn from_triangles_with_detection(
        vertex_of_corner: Vec<VertexIndex>,
        max_vertex_index: u32,
    ) -> Result<(Self, Vec<NonManifoldEdge>), RemeshError> {
        let num_corners =
            crate::corner_table::build_manifold::validate_num_corners(vertex_of_corner.len())?;

        // Initialize arrays
        let mut opposite_corner = vec![CornerIndex::INVALID; num_corners as usize];
        let mut corner_of_vertex = vec![CornerIndex::INVALID; max_vertex_index as usize + 1];

        // Set up corner_of_vertex mapping (last corner wins)
        for (corner, &vertex) in vertex_of_corner.iter().enumerate() {
            corner_of_vertex[vertex.0 as usize] = CornerIndex(corner as u32);
        }

        // Use SmallVec to collect ALL corners per edge (not just first two)
        let mut edge_map: FxHashMap<(VertexIndex, VertexIndex), SmallVec<[CornerIndex; 2]>> = {
            let capacity = (num_corners / 2)
                .checked_mul(3)
                .ok_or_else(|| RemeshError("Capacity calculation overflow".to_string()))?;
            FxHashMap::with_capacity_and_hasher(capacity as usize, Default::default())
        };

        for corner_id in (0..num_corners).map(CornerIndex) {
            let (next_corner_id, prev_corner_id) = corner_id.next_prev();

            let v_i = vertex_of_corner[next_corner_id.usize()];
            let v_j = vertex_of_corner[prev_corner_id.usize()];
            let key = VertexIndex::canonical_pair(v_i, v_j);

            edge_map.entry(key).or_default().push(corner_id);
        }

        // Process edges: set opposites for first pair, collect non-manifold cases
        let mut non_manifold_edges = Vec::new();

        for ((v_i, v_j), corners) in edge_map.into_iter() {
            match corners.len() {
                0 => {
                    // Should never happen, but handle defensively
                    return Err(RemeshError(format!(
                        "Internal error: empty edge entry for {:?}-{:?}",
                        v_i, v_j
                    )));
                }
                1 => {
                    // Boundary edge - not supported
                    return Err(RemeshError(format!(
                        "Boundary edge not supported: edge {:?}-{:?} has only one adjacent triangle",
                        v_i, v_j
                    )));
                }
                2 => {
                    let c0 = corners[0];
                    let c1 = corners[1];
                    Self::check_edge_winding(c0, c1, &vertex_of_corner)?;
                    // Correct winding - set opposites
                    opposite_corner[c0.usize()] = c1;
                    opposite_corner[c1.usize()] = c0;
                }
                3 | 5 => {
                    // Odd number of triangles - likely boundary confusion or bad topology
                    return Err(RemeshError(format!(
                        "Unsupported edge configuration: edge {:?}-{:?} has {} adjacent triangles \
                 (odd numbers indicate boundary/malformed mesh)",
                        v_i,
                        v_j,
                        corners.len()
                    )));
                }
                4 => {
                    // Non-manifold edge with 4 triangles - supported for fixing
                    non_manifold_edges.push(NonManifoldEdge { v_i, v_j, corners });
                }
                5.. => {
                    // Too many triangles sharing an edge - unsolvable mess
                    return Err(RemeshError(format!(
                        "Unsupported edge configuration: edge {:?}-{:?} has {} adjacent triangles \
                 (maximum supported is 4 for non-manifold repair)",
                        v_i,
                        v_j,
                        corners.len()
                    )));
                }
            }
        }

        let corner_table = Self::new(vertex_of_corner, opposite_corner, corner_of_vertex);
        #[cfg(any(feature = "integrity_check", debug_assertions))]
        corner_table.validate_partial().unwrap();

        Ok((corner_table, non_manifold_edges))
    }

    /// Build corner table from triangle indices using hashmap for O(n) performance
    /// (´triangles´ are vertex indices in groups of 3)
    /// This code assumes a watertight input mesh and fixes non-manifold vertices and edges by duplication.
    ///
    /// # Parameters
    /// * `vertex_of_corner` - Triangle vertex indices (length must be divisible by 3)
    /// * `max_vertex_index` - Highest vertex index in vertex_of_corner
    /// * `vertices` - Mutable vertex data array. New vertices will be appended when fixing non-manifold geometry
    pub(crate) fn from_non_manifold_triangles<T: Clone>(
        vertex_of_corner: Vec<VertexIndex>,
        max_vertex_index: u32,
        vertices: &mut Vec<T>,
    ) -> Result<Self, RemeshError> {
        //let mut run_vertex_manifold_check = false;

        let (mut corner_table, mut problem_edges) =
            Self::from_triangles_with_detection(vertex_of_corner, max_vertex_index)?;

        if problem_edges.is_empty() {
            corner_table.fix_non_manifold_vertices(vertices)?;
            return Ok(corner_table);
        }

        let max_iterations = 5;
        let mut iteration = max_iterations;
        while iteration > 0 {
            let mut still_broken = Vec::new();
            // Process each problem edge independently
            for edge in problem_edges.into_iter() {
                integrity_println!(
                    "Fixing edge {:?}-{:?} [{}]",
                    edge.v_i,
                    edge.v_j,
                    corner_table.dbg_corners(&edge.corners)
                );

                match Self::try_fix_edge(edge.clone(), &mut corner_table, vertices)? {
                    EdgeFixResult::Done => {} // Continue to next edge
                    EdgeFixResult::NeedsVertexManifoldCheck => {
                        //run_vertex_manifold_check = true;
                    }
                    EdgeFixResult::RetryLater(edge) => {
                        still_broken.push(edge);
                    }
                }
                //if let Some(problem_edge) = Self::try_fix_edge(edge, &mut corner_table, vertices)? {
                //    still_broken.push(problem_edge);
                //}
            }
            if still_broken.is_empty() {
                problem_edges = still_broken;
                break;
            }
            println!("still_broken: {:?}", still_broken);
            problem_edges = still_broken;
            iteration -= 1;
        }
        if !problem_edges.is_empty() {
            let edge = &problem_edges[0];
            return Err(RemeshError(format!(
                "Could not fix non-manifold edge {:?}-{:?} [{}], and {} more after {max_iterations} iterations",
                edge.v_i,
                edge.v_j,
                corner_table.dbg_corners(&edge.corners),
                problem_edges.len() - 1
            )));
        }
        //if run_vertex_manifold_check {
        corner_table.fix_non_manifold_vertices(vertices)?;
        //}
        Ok(corner_table)
    }

    fn fix_non_manifold_vertices<T: Clone>(
        &mut self,
        vertices: &mut Vec<T>,
    ) -> Result<(), RemeshError> {
        // Detect and fix non-manifold vertices
        let mut corners_per_vertex: Vec<SmallVec<[CornerIndex; 8]>> =
            vec![SmallVec::new(); self.data.corner_of_vertex_vec.len()];

        for (corner_idx, &vertex) in self.data.vertex_of_corner_vec.iter().enumerate() {
            corners_per_vertex[vertex.usize()].push(CornerIndex(corner_idx as u32));
        }

        // Reusable visited bitsets (allocated once outside the loop)
        let mut visited = SmallVec::<[bool; 16]>::new();
        let mut component_visited = SmallVec::<[bool; 16]>::new();

        let loop_range = 0..(self.data.corner_of_vertex_vec.len() as u32); // break clippy warning
        // Check each vertex with multiple corners
        for vertex in loop_range.map(VertexIndex) {
            let corners = &corners_per_vertex[vertex.usize()];

            if corners.len() <= 1 {
                continue;
            }

            // Reuse visited vec by resizing and clearing
            visited.clear();
            visited.resize(corners.len(), false);
            visited[0] = true;
            let mut visited_count = 1;

            // Try swinging around from the first corner
            let start_corner = corners[0];
            let mut current = start_corner;

            loop {
                // Swing to next corner around vertex
                let next_corner = self.swing_ccw(current);

                if next_corner == CornerIndex::INVALID || next_corner == start_corner {
                    break;
                }

                // Mark this corner as visited
                if let Some(pos) = corners.iter().position(|&c| c == next_corner) {
                    if !visited[pos] {
                        visited[pos] = true;
                        visited_count += 1;
                    }
                }

                current = next_corner;
            }

            // If we didn't visit all corners, vertex is non-manifold
            if visited_count < corners.len() {
                // Split the vertex into multiple vertices
                // Keep the first component on the original vertex

                // First, ensure the original vertex points to a corner in the first component
                self.set_corner_of_vertex(vertex, start_corner);

                for (i, &corner) in corners.iter().enumerate() {
                    if !visited[i] {
                        // This corner belongs to a different component
                        // Find all corners in this component
                        let mut component = vec![corner];

                        // Reuse component_visited vec
                        component_visited.clear();
                        component_visited.resize(corners.len(), false);
                        component_visited[i] = true;

                        let mut current = corner;
                        loop {
                            let next_corner = self.swing_ccw(current);

                            if !next_corner.is_valid() || next_corner == corner {
                                break;
                            }

                            if let Some(pos) = corners.iter().position(|&c| c == next_corner) {
                                if !component_visited[pos] {
                                    component_visited[pos] = true;
                                    component.push(next_corner);
                                }
                            }

                            current = next_corner;
                        }

                        // Assign a new vertex index to this component
                        let new_vertex = self.clone_vertex(vertices, vertex);
                        integrity_println!(
                            "(vertex) cloning vertex #{vertex:?} placing the clone at #{new_vertex:?}"
                        );

                        for &comp_corner in &component {
                            self.link_corner_vertex(comp_corner, new_vertex);
                        }

                        // Mark these corners as visited so we don't process them again
                        for (j, &is_in_component) in component_visited.iter().enumerate() {
                            if is_in_component {
                                visited[j] = true;
                            }
                        }
                    }
                }
            }
        }

        #[cfg(any(feature = "integrity_check", debug_assertions))]
        self.check_integrity(self.data.corner_of_vertex_vec.len() as u32)
            .unwrap();
        Ok(())
    }

    fn try_fix_edge<T: Clone>(
        edge: NonManifoldEdge,
        corner_table: &mut CornerTable<ENABLE_UNSAFE>,
        _vertices: &mut Vec<T>,
    ) -> Result<EdgeFixResult, RemeshError> {
        use check_connectivity::{ConfigurationTest, EdgeConfigurationSet};

        for &corner in edge.corners.iter() {
            let (nc, pc) = corner_table.next_prev(corner);
            println!(
                "candidate corner:{:?},{:?},{:?}",
                corner_table.dbg_corner(corner),
                corner_table.dbg_corner(nc),
                corner_table.dbg_corner(pc)
            )
        }
        let c_set = EdgeConfigurationSet::from_corners(edge.clone(), corner_table).unwrap();
        println!("{:?}", c_set);
        // Test both alternative configurations
        let config_a_result =
            ConfigurationTest::evaluate(&c_set.config_a, c_set.edge_vertices, corner_table);
        println!("{:?}", config_a_result);
        let config_b_result =
            ConfigurationTest::evaluate(&c_set.config_b, c_set.edge_vertices, corner_table);

        println!("{:?}", config_b_result);

        if config_a_result.is_simple_edge(config_b_result) {
            println!("applying a");
            config_a_result.config.apply_configuration(corner_table);
            return Ok(EdgeFixResult::NeedsVertexManifoldCheck);
        }
        if config_b_result.is_simple_edge(config_a_result) {
            println!("applying b");
            config_b_result.config.apply_configuration(corner_table);
            return Ok(EdgeFixResult::NeedsVertexManifoldCheck);
        }

        // First, verify the options are comparable (same vertices and valences)
        if config_a_result.vertex_0_result.vertex != config_b_result.vertex_0_result.vertex
            || config_a_result.vertex_0_result.valence != config_b_result.vertex_0_result.valence
            || config_a_result.vertex_1_result.vertex != config_b_result.vertex_1_result.vertex
            || config_a_result.vertex_1_result.valence != config_b_result.vertex_1_result.valence
        {
            // Options aren't comparable
            return Ok(EdgeFixResult::RetryLater(edge));
        }

        // Determine which vertex has higher valence
        let (higher_valence_a, higher_valence_b) =
            if config_a_result.vertex_0_result.valence > config_a_result.vertex_1_result.valence {
                (
                    &config_a_result.vertex_0_result,
                    &config_b_result.vertex_0_result,
                )
            } else {
                (
                    &config_a_result.vertex_1_result,
                    &config_b_result.vertex_1_result,
                )
            };

        // Pick the option where the higher valence vertex is manifold
        let config_to_apply = if higher_valence_a.is_manifold && !higher_valence_b.is_manifold {
            println!("applying config_a");
            &config_a_result.config
        } else {
            //if !higher_valence_a.is_manifold && higher_valence_b.is_manifold {
            println!("applying config_b");
            &config_b_result.config
        }; //else {
        // Both or neither have manifold on higher valence vertex
        //  return return Ok(Some(edge));
        //};

        config_to_apply.apply_configuration(corner_table);
        Ok(EdgeFixResult::NeedsVertexManifoldCheck)
    }
}