remesh 0.0.5

Isotropic remeshing library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

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

use crate::common::VertexIndex;
#[allow(unused_imports)]
use crate::common::macros::{integrity_print, integrity_println};
use crate::corner_table::{CornerIndex, CornerTable};
use crate::prelude::RemeshError;
use rustc_hash::FxHashMap;

pub(super) fn validate_num_corners(num_corners: usize) -> Result<u32, RemeshError> {
    let num_corners: u32 = num_corners.try_into().map_err(|e| {
        RemeshError(format!("Triangle list too large for u32 corners. {e:?}").to_string())
    })?;

    // Validate input
    if !num_corners.is_multiple_of(3) {
        return Err(RemeshError(
            "Triangle list must have length divisible by 3".to_string(),
        ));
    }
    // Guard against overflow in hashmap capacity calculation
    if num_corners >= u32::MAX / 2 {
        return Err(RemeshError(
            "Triangle list too large for u32 corners".to_string(),
        ));
    }
    Ok(num_corners)
}

impl<const ENABLE_UNSAFE: bool> CornerTable<ENABLE_UNSAFE> {
    pub(super) fn check_edge_winding(
        c0: CornerIndex,
        c1: CornerIndex,
        vertex_of_corner: &[VertexIndex],
    ) -> Result<(), RemeshError> {
        // Verify edge winding before setting opposites
        let (c0_next, c0_prev) = c0.next_prev();
        let (c1_next, c1_prev) = c1.next_prev();

        let c0_edge = (
            vertex_of_corner[c0_next.usize()],
            vertex_of_corner[c0_prev.usize()],
        );
        let c1_edge = (
            vertex_of_corner[c1_next.usize()],
            vertex_of_corner[c1_prev.usize()],
        );

        // Edges must be reversed: c0=(a,b) and c1=(b,a)
        if !(c0_edge.0 == c1_edge.1 && c0_edge.1 == c1_edge.0) {
            // Inconsistent winding detected
            return Err(RemeshError(format!(
                "Inconsistent triangle winding at edge V{:?}-V{:?}: \
             triangle T{:?} has edge {:?}→{:?}, \
             triangle T{:?} has edge {:?}→{:?} (should be reversed)",
                c0_edge.0,
                c0_edge.1,
                c0.triangle(),
                c0_edge.0,
                c0_edge.1,
                c1.triangle(),
                c1_edge.0,
                c1_edge.1
            )));
        }
        Ok(())
    }

    /// Build corner table from triangle indices using hashmap for O(n) performance
    /// (´triangles´ are vertex indices in groups of 3)
    /// This code assumes a manifold, watertight input mesh.
    /// Build corner table from triangle indices using hashmap for O(n) performance
    /// (´triangles´ are vertex indices in groups of 3)
    /// This code assumes a manifold, watertight input mesh.
    pub(crate) fn from_manifold_triangles(
        vertex_of_corner: Vec<VertexIndex>,
        max_vertex_index: u32,
    ) -> Result<Self, RemeshError> {
        let num_corners = 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.usize()] = CornerIndex(corner as u32);
        }

        // Step 2: Use hashmap to find opposite corners efficiently
        let mut edge_map: FxHashMap<(VertexIndex, VertexIndex), CornerIndex> = {
            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) {
            // Each corner represents the edge OPPOSITE to its vertex in the triangle
            let (next_corner_id, prev_corner_id) = corner_id.next_prev();

            let v_i = vertex_of_corner[next_corner_id.usize()]; // Next vertex in triangle
            let v_j = vertex_of_corner[prev_corner_id.usize()]; // Prev vertex in triangle

            // This corner represents the edge v_i -> v_j (the edge opposite to this corner's vertex)
            // Create canonical edge key (min, max) to ensure consistent ordering
            let key = VertexIndex::canonical_pair(v_i, v_j);

            // Check if we've seen the opposite edge
            if let Some(&stored_corner) = edge_map.get(&key) {
                Self::check_edge_winding(stored_corner, corner_id, &vertex_of_corner)?;

                // Found matching edge - these are opposites
                opposite_corner[corner_id.usize()] = stored_corner;
                opposite_corner[stored_corner.usize()] = corner_id;

                // Remove the matched edge from the map
                let _ = edge_map.remove(&key);
            } else {
                // First time seeing this edge, add it to the map
                let _ = edge_map.insert(key, corner_id);
            }
        }

        // Any edges remaining in edge_map are boundary edges (opposite remains CornerIndex::INVALID_INDEX)
        // For a watertight mesh, this should be empty
        if !edge_map.is_empty() {
            Err(RemeshError(format!(
                "{} boundary edges found",
                edge_map.len()
            )))?
        }

        Ok(Self::new(
            vertex_of_corner,
            opposite_corner,
            corner_of_vertex,
        ))
    }
}