1use bytemuck::{Pod, Zeroable};
2use serde::{Deserialize, Serialize};
3
4pub const INVALID_INDEX: u32 = u32::MAX;
5
6#[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#[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 {
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 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
135pub 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#[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
305pub 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