Skip to main content

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]
66/// `Default::required_edge_slots`.
67pub fn required_edge_slots(triangle_count: usize) -> usize {
68    triangle_count
69        .saturating_mul(6)
70        .max(1)
71        .checked_next_power_of_two()
72        .unwrap_or(usize::MAX)
73}
74
75#[inline]
76fn edge_key(from: u32, to: u32) -> u64 {
77    ((from as u64) << 32) | to as u64
78}
79
80#[inline]
81fn hash_key(key: u64) -> usize {
82    // SplitMix64 finalizer: fast, deterministic, and strong on sequential IDs.
83    let mut x = key;
84    x ^= x >> 30;
85    x = x.wrapping_mul(0xbf58_476d_1ce4_e5b9);
86    x ^= x >> 27;
87    x = x.wrapping_mul(0x94d0_49bb_1331_11eb);
88    (x ^ (x >> 31)) as usize
89}
90
91fn find_slot(slots: &[EdgeSlot], key: u64) -> Option<u32> {
92    let mask = slots.len() - 1;
93    let mut at = hash_key(key) & mask;
94    for _ in 0..slots.len() {
95        let slot = slots[at];
96        if slot.half_edge == INVALID_INDEX {
97            return None;
98        }
99        if slot.key == key {
100            return Some(slot.half_edge);
101        }
102        at = (at + 1) & mask;
103    }
104    None
105}
106
107fn insert_slot(
108    slots: &mut [EdgeSlot],
109    key: u64,
110    half_edge: u32,
111    from: u32,
112    to: u32,
113) -> Result<(), TopologyError> {
114    let mask = slots.len() - 1;
115    let mut at = hash_key(key) & mask;
116    for _ in 0..slots.len() {
117        if slots[at].half_edge == INVALID_INDEX {
118            slots[at] = EdgeSlot {
119                key,
120                half_edge,
121                _reserved: 0,
122            };
123            return Ok(());
124        }
125        if slots[at].key == key {
126            return Err(TopologyError::DuplicateDirectedEdge { from, to });
127        }
128        at = (at + 1) & mask;
129    }
130    Err(TopologyError::SlotBufferTooSmall {
131        required: slots.len().saturating_mul(2),
132    })
133}
134
135/// Build a half-edge graph from triangle indices without heap allocation.
136///
137/// The output requires `3 * triangles.len()` entries. `slots` requires
138/// `required_edge_slots(triangles.len())()` entries and is cleared by this
139/// function. Oppositely directed edges become twins; unmatched edges are the
140/// boundary. Duplicate directions and edges with more than two incident faces
141/// fail closed as non-manifold input.
142pub fn build_triangle_half_edges(
143    vertex_count: u32,
144    triangles: &[[u32; 3]],
145    out: &mut [HalfEdge],
146    slots: &mut [EdgeSlot],
147) -> Result<TopologySummary, TopologyError> {
148    if triangles.len() > (u32::MAX as usize) / 3 {
149        return Err(TopologyError::TooManyFaces);
150    }
151    let edge_count = triangles.len() * 3;
152    if out.len() < edge_count {
153        return Err(TopologyError::HalfEdgeBufferTooSmall {
154            required: edge_count,
155        });
156    }
157    let required_slots = required_edge_slots(triangles.len());
158    if slots.len() < required_slots || !slots.len().is_power_of_two() {
159        return Err(TopologyError::SlotBufferTooSmall {
160            required: required_slots,
161        });
162    }
163    for slot in slots.iter_mut() {
164        *slot = EdgeSlot::default();
165    }
166
167    for (face, triangle) in triangles.iter().copied().enumerate() {
168        if triangle[0] == triangle[1] || triangle[1] == triangle[2] || triangle[2] == triangle[0] {
169            return Err(TopologyError::DegenerateFace { face });
170        }
171        for &vertex in &triangle {
172            if vertex >= vertex_count {
173                return Err(TopologyError::VertexOutOfRange { face, vertex });
174            }
175        }
176
177        let base = face * 3;
178        for local in 0..3 {
179            let from = triangle[local];
180            let to = triangle[(local + 1) % 3];
181            let current = (base + local) as u32;
182            out[base + local] = HalfEdge {
183                origin: from,
184                twin: INVALID_INDEX,
185                next: (base + (local + 1) % 3) as u32,
186                face: face as u32,
187            };
188
189            if let Some(reverse) = find_slot(slots, edge_key(to, from)) {
190                if out[reverse as usize].twin != INVALID_INDEX {
191                    return Err(TopologyError::NonManifoldEdge { from, to });
192                }
193                out[base + local].twin = reverse;
194                out[reverse as usize].twin = current;
195            }
196            insert_slot(slots, edge_key(from, to), current, from, to)?;
197        }
198    }
199
200    let boundary_half_edges = out[..edge_count]
201        .iter()
202        .filter(|edge| edge.twin == INVALID_INDEX)
203        .count() as u32;
204    Ok(TopologySummary {
205        vertex_count,
206        face_count: triangles.len() as u32,
207        half_edge_count: edge_count as u32,
208        boundary_half_edges,
209    })
210}
211
212#[cfg(test)]
213mod tests {
214    use super::*;
215
216    #[test]
217    fn two_triangles_share_twinned_edge() {
218        let triangles = [[0, 1, 2], [2, 1, 3]];
219        let mut edges = [HalfEdge::default(); 6];
220        let mut slots = [EdgeSlot::default(); 16];
221        let summary = build_triangle_half_edges(4, &triangles, &mut edges, &mut slots).unwrap();
222        assert_eq!(summary.boundary_half_edges, 4);
223        assert_eq!(edges[1].twin, 3);
224        assert_eq!(edges[3].twin, 1);
225        assert_eq!(edges[0].next, 1);
226        assert_eq!(edges[2].next, 0);
227    }
228
229    #[test]
230    fn rejects_duplicate_oriented_edge() {
231        let triangles = [[0, 1, 2], [0, 1, 3]];
232        let mut edges = [HalfEdge::default(); 6];
233        let mut slots = [EdgeSlot::default(); 16];
234        assert_eq!(
235            build_triangle_half_edges(4, &triangles, &mut edges, &mut slots),
236            Err(TopologyError::DuplicateDirectedEdge { from: 0, to: 1 })
237        );
238    }
239
240    #[test]
241    fn reports_fixed_buffer_requirements() {
242        let triangles = [[0, 1, 2]];
243        let mut edges = [HalfEdge::default(); 2];
244        let mut slots = [EdgeSlot::default(); 8];
245        assert_eq!(
246            build_triangle_half_edges(3, &triangles, &mut edges, &mut slots),
247            Err(TopologyError::HalfEdgeBufferTooSmall { required: 3 })
248        );
249    }
250}
251
252/// Actual-probe budget exhaustion or the existing topology error.
253#[derive(Debug, Clone, Copy, PartialEq, Eq)]
254pub enum BudgetedTopologyError { Topology(TopologyError), WorkLimitExceeded }
255fn find_slot_budgeted(slots: &[EdgeSlot], key: u64, remaining: &mut usize) -> Result<Option<u32>, BudgetedTopologyError> {
256    let mask = slots.len() - 1;
257    let mut at = hash_key(key) & mask;
258    for _ in 0..slots.len() {
259        if *remaining == 0 { return Err(BudgetedTopologyError::WorkLimitExceeded); }
260        *remaining -= 1;
261        let slot = slots[at];
262        if slot.half_edge == INVALID_INDEX {
263            return Ok(None);
264        }
265        if slot.key == key {
266            return Ok(Some(slot.half_edge));
267        }
268        at = (at + 1) & mask;
269    }
270    Ok(None)
271}
272
273fn insert_slot_budgeted(
274    slots: &mut [EdgeSlot],
275    key: u64,
276    half_edge: u32,
277    from: u32,
278    to: u32,
279    remaining: &mut usize,
280) -> Result<(), BudgetedTopologyError> {
281    let mask = slots.len() - 1;
282    let mut at = hash_key(key) & mask;
283    for _ in 0..slots.len() {
284        if *remaining == 0 { return Err(BudgetedTopologyError::WorkLimitExceeded); }
285        *remaining -= 1;
286        if slots[at].half_edge == INVALID_INDEX {
287            slots[at] = EdgeSlot {
288                key,
289                half_edge,
290                _reserved: 0,
291            };
292            return Ok(());
293        }
294        if slots[at].key == key {
295            return Err(BudgetedTopologyError::Topology(TopologyError::DuplicateDirectedEdge { from, to }));
296        }
297        at = (at + 1) & mask;
298    }
299    Err(BudgetedTopologyError::Topology(TopologyError::SlotBufferTooSmall {
300        required: slots.len().saturating_mul(2),
301    }))
302}
303
304
305/// Charges every hash probe. Caller budgets non-probe work; scratch can be dirty on failure.
306pub fn build_triangle_half_edges_budgeted(
307    vertex_count: u32,
308    triangles: &[[u32; 3]],
309    out: &mut [HalfEdge],
310    slots: &mut [EdgeSlot],
311    remaining_probes: &mut usize,
312) -> Result<TopologySummary, BudgetedTopologyError> {
313    if triangles.len() > (u32::MAX as usize) / 3 {
314        return Err(BudgetedTopologyError::Topology(TopologyError::TooManyFaces));
315    }
316    let edge_count = triangles.len() * 3;
317    if out.len() < edge_count {
318        return Err(BudgetedTopologyError::Topology(TopologyError::HalfEdgeBufferTooSmall {
319            required: edge_count,
320        }));
321    }
322    let required_slots = required_edge_slots(triangles.len());
323    if slots.len() < required_slots || !slots.len().is_power_of_two() {
324        return Err(BudgetedTopologyError::Topology(TopologyError::SlotBufferTooSmall {
325            required: required_slots,
326        }));
327    }
328    if *remaining_probes == 0 && edge_count != 0 { return Err(BudgetedTopologyError::WorkLimitExceeded); }
329    for slot in slots.iter_mut() {
330        *slot = EdgeSlot::default();
331    }
332
333    for (face, triangle) in triangles.iter().copied().enumerate() {
334        if triangle[0] == triangle[1] || triangle[1] == triangle[2] || triangle[2] == triangle[0] {
335            return Err(BudgetedTopologyError::Topology(TopologyError::DegenerateFace { face }));
336        }
337        for &vertex in &triangle {
338            if vertex >= vertex_count {
339                return Err(BudgetedTopologyError::Topology(TopologyError::VertexOutOfRange { face, vertex }));
340            }
341        }
342
343        let base = face * 3;
344        for local in 0..3 {
345            let from = triangle[local];
346            let to = triangle[(local + 1) % 3];
347            let current = (base + local) as u32;
348            out[base + local] = HalfEdge {
349                origin: from,
350                twin: INVALID_INDEX,
351                next: (base + (local + 1) % 3) as u32,
352                face: face as u32,
353            };
354
355            if let Some(reverse) = find_slot_budgeted(slots, edge_key(to, from), remaining_probes)? {
356                if out[reverse as usize].twin != INVALID_INDEX {
357                    return Err(BudgetedTopologyError::Topology(TopologyError::NonManifoldEdge { from, to }));
358                }
359                out[base + local].twin = reverse;
360                out[reverse as usize].twin = current;
361            }
362            insert_slot_budgeted(slots, edge_key(from, to), current, from, to, remaining_probes)?;
363        }
364    }
365
366    let boundary_half_edges = out[..edge_count]
367        .iter()
368        .filter(|edge| edge.twin == INVALID_INDEX)
369        .count() as u32;
370    Ok(TopologySummary {
371        vertex_count,
372        face_count: triangles.len() as u32,
373        half_edge_count: edge_count as u32,
374        boundary_half_edges,
375    })
376}
377