qualia_core_db/specialized_libs/computational_geometry/
topology.rs

1use bytemuck::{Pod, Zeroable};
2use serde::{Deserialize, Serialize};
3
4pub const INVALID_INDEX: u32 = u32::MAX;
5
6/// One directed edge in a triangle half-edge graph.
7#[repr(C)]
8#[derive(Debug, Clone, Copy, PartialEq, Eq, Pod, Zeroable, Serialize, Deserialize)]
9pub struct HalfEdge {
10    pub origin: u32,
11    pub twin: u32,
12    pub next: u32,
13    pub face: u32,
14}
15
16impl Default for HalfEdge {
17    fn default() -> Self {
18        Self {
19            origin: INVALID_INDEX,
20            twin: INVALID_INDEX,
21            next: INVALID_INDEX,
22            face: INVALID_INDEX,
23        }
24    }
25}
26
27/// Caller-owned open-addressing slot used while constructing twins.
28#[repr(C)]
29#[derive(Debug, Clone, Copy, PartialEq, Eq, Pod, Zeroable, Serialize, Deserialize)]
30pub struct EdgeSlot {
31    pub key: u64,
32    pub half_edge: u32,
33    pub _reserved: u32,
34}
35
36impl Default for EdgeSlot {
37    fn default() -> Self {
38        Self {
39            key: 0,
40            half_edge: INVALID_INDEX,
41            _reserved: 0,
42        }
43    }
44}
45
46#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
47pub struct TopologySummary {
48    pub vertex_count: u32,
49    pub face_count: u32,
50    pub half_edge_count: u32,
51    pub boundary_half_edges: u32,
52}
53
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
55pub enum TopologyError {
56    TooManyFaces,
57    HalfEdgeBufferTooSmall { required: usize },
58    SlotBufferTooSmall { required: usize },
59    VertexOutOfRange { face: usize, vertex: u32 },
60    DegenerateFace { face: usize },
61    DuplicateDirectedEdge { from: u32, to: u32 },
62    NonManifoldEdge { from: u32, to: u32 },
63}
64
65#[inline]
66pub fn required_edge_slots(triangle_count: usize) -> usize {
67    triangle_count
68        .saturating_mul(6)
69        .max(1)
70        .checked_next_power_of_two()
71        .unwrap_or(usize::MAX)
72}
73
74#[inline]
75fn edge_key(from: u32, to: u32) -> u64 {
76    ((from as u64) << 32) | to as u64
77}
78
79#[inline]
80fn hash_key(key: u64) -> usize {
81    // SplitMix64 finalizer: fast, deterministic, and strong on sequential IDs.
82    let mut x = key;
83    x ^= x >> 30;
84    x = x.wrapping_mul(0xbf58_476d_1ce4_e5b9);
85    x ^= x >> 27;
86    x = x.wrapping_mul(0x94d0_49bb_1331_11eb);
87    (x ^ (x >> 31)) as usize
88}
89
90fn find_slot(slots: &[EdgeSlot], key: u64) -> Option<u32> {
91    let mask = slots.len() - 1;
92    let mut at = hash_key(key) & mask;
93    for _ in 0..slots.len() {
94        let slot = slots[at];
95        if slot.half_edge == INVALID_INDEX {
96            return None;
97        }
98        if slot.key == key {
99            return Some(slot.half_edge);
100        }
101        at = (at + 1) & mask;
102    }
103    None
104}
105
106fn insert_slot(
107    slots: &mut [EdgeSlot],
108    key: u64,
109    half_edge: u32,
110    from: u32,
111    to: u32,
112) -> Result<(), TopologyError> {
113    let mask = slots.len() - 1;
114    let mut at = hash_key(key) & mask;
115    for _ in 0..slots.len() {
116        if slots[at].half_edge == INVALID_INDEX {
117            slots[at] = EdgeSlot {
118                key,
119                half_edge,
120                _reserved: 0,
121            };
122            return Ok(());
123        }
124        if slots[at].key == key {
125            return Err(TopologyError::DuplicateDirectedEdge { from, to });
126        }
127        at = (at + 1) & mask;
128    }
129    Err(TopologyError::SlotBufferTooSmall {
130        required: slots.len().saturating_mul(2),
131    })
132}
133
134/// Build a half-edge graph from triangle indices without heap allocation.
135///
136/// The output requires `3 * triangles.len()` entries. `slots` requires
137/// [`required_edge_slots(triangles.len())`] entries and is cleared by this
138/// function. Oppositely directed edges become twins; unmatched edges are the
139/// boundary. Duplicate directions and edges with more than two incident faces
140/// fail closed as non-manifold input.
141pub fn build_triangle_half_edges(
142    vertex_count: u32,
143    triangles: &[[u32; 3]],
144    out: &mut [HalfEdge],
145    slots: &mut [EdgeSlot],
146) -> Result<TopologySummary, TopologyError> {
147    if triangles.len() > (u32::MAX as usize) / 3 {
148        return Err(TopologyError::TooManyFaces);
149    }
150    let edge_count = triangles.len() * 3;
151    if out.len() < edge_count {
152        return Err(TopologyError::HalfEdgeBufferTooSmall {
153            required: edge_count,
154        });
155    }
156    let required_slots = required_edge_slots(triangles.len());
157    if slots.len() < required_slots || !slots.len().is_power_of_two() {
158        return Err(TopologyError::SlotBufferTooSmall {
159            required: required_slots,
160        });
161    }
162    for slot in slots.iter_mut() {
163        *slot = EdgeSlot::default();
164    }
165
166    for (face, triangle) in triangles.iter().copied().enumerate() {
167        if triangle[0] == triangle[1] || triangle[1] == triangle[2] || triangle[2] == triangle[0] {
168            return Err(TopologyError::DegenerateFace { face });
169        }
170        for &vertex in &triangle {
171            if vertex >= vertex_count {
172                return Err(TopologyError::VertexOutOfRange { face, vertex });
173            }
174        }
175
176        let base = face * 3;
177        for local in 0..3 {
178            let from = triangle[local];
179            let to = triangle[(local + 1) % 3];
180            let current = (base + local) as u32;
181            out[base + local] = HalfEdge {
182                origin: from,
183                twin: INVALID_INDEX,
184                next: (base + (local + 1) % 3) as u32,
185                face: face as u32,
186            };
187
188            if let Some(reverse) = find_slot(slots, edge_key(to, from)) {
189                if out[reverse as usize].twin != INVALID_INDEX {
190                    return Err(TopologyError::NonManifoldEdge { from, to });
191                }
192                out[base + local].twin = reverse;
193                out[reverse as usize].twin = current;
194            }
195            insert_slot(slots, edge_key(from, to), current, from, to)?;
196        }
197    }
198
199    let boundary_half_edges = out[..edge_count]
200        .iter()
201        .filter(|edge| edge.twin == INVALID_INDEX)
202        .count() as u32;
203    Ok(TopologySummary {
204        vertex_count,
205        face_count: triangles.len() as u32,
206        half_edge_count: edge_count as u32,
207        boundary_half_edges,
208    })
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214
215    #[test]
216    fn two_triangles_share_twinned_edge() {
217        let triangles = [[0, 1, 2], [2, 1, 3]];
218        let mut edges = [HalfEdge::default(); 6];
219        let mut slots = [EdgeSlot::default(); 16];
220        let summary = build_triangle_half_edges(4, &triangles, &mut edges, &mut slots).unwrap();
221        assert_eq!(summary.boundary_half_edges, 4);
222        assert_eq!(edges[1].twin, 3);
223        assert_eq!(edges[3].twin, 1);
224        assert_eq!(edges[0].next, 1);
225        assert_eq!(edges[2].next, 0);
226    }
227
228    #[test]
229    fn rejects_duplicate_oriented_edge() {
230        let triangles = [[0, 1, 2], [0, 1, 3]];
231        let mut edges = [HalfEdge::default(); 6];
232        let mut slots = [EdgeSlot::default(); 16];
233        assert_eq!(
234            build_triangle_half_edges(4, &triangles, &mut edges, &mut slots),
235            Err(TopologyError::DuplicateDirectedEdge { from: 0, to: 1 })
236        );
237    }
238
239    #[test]
240    fn reports_fixed_buffer_requirements() {
241        let triangles = [[0, 1, 2]];
242        let mut edges = [HalfEdge::default(); 2];
243        let mut slots = [EdgeSlot::default(); 8];
244        assert_eq!(
245            build_triangle_half_edges(3, &triangles, &mut edges, &mut slots),
246            Err(TopologyError::HalfEdgeBufferTooSmall { required: 3 })
247        );
248    }
249}
qualia_core_db/specialized_libs/computational_geometry/topology.rs

qualia_core_db/specialized_libs/computational_geometry/
topology.rs
