1use super::topology::{HalfEdge, INVALID_INDEX};
23
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub enum ConnectivityError {
31 LabelBufferTooSmall { required: usize },
33 QueueBufferTooSmall { required: usize },
35 VisitedBufferTooSmall { required: usize },
37 HalfEdgeOutOfRange { index: u32 },
39}
40
41#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub struct ConnectivitySummary {
44 pub component_count: u32,
46 pub boundary_loop_count: u32,
48 pub euler_characteristic: i32,
50 pub genus: Option<u32>,
52 pub vertex_count: u32,
54 pub edge_count: u32,
56 pub face_count: u32,
58}
59
60pub fn label_components(
75 face_count: u32,
76 half_edges: &[HalfEdge],
77 labels: &mut [u32],
78 queue: &mut [u32],
79) -> Result<u32, ConnectivityError> {
80 let fc = face_count as usize;
81 if labels.len() < fc {
82 return Err(ConnectivityError::LabelBufferTooSmall { required: fc });
83 }
84 if queue.len() < fc {
85 return Err(ConnectivityError::QueueBufferTooSmall { required: fc });
86 }
87
88 for l in &mut labels[..fc] {
89 *l = INVALID_INDEX;
90 }
91
92 let mut component = 0u32;
93 let mut seed = 0u32;
94
95 while (seed as usize) < fc {
96 let mut head = 0usize;
98 let mut tail = 0usize;
99 queue[tail] = seed;
100 tail += 1;
101 labels[seed as usize] = component;
102
103 while head < tail {
104 let face = queue[head];
105 head += 1;
106
107 for he in half_edges.iter() {
109 if he.face != face {
110 continue;
111 }
112 if he.twin == INVALID_INDEX {
113 continue;
114 }
115 let twin_idx = he.twin as usize;
116 if twin_idx >= half_edges.len() {
117 return Err(ConnectivityError::HalfEdgeOutOfRange { index: he.twin });
118 }
119 let neighbour = half_edges[twin_idx].face;
120 if neighbour == INVALID_INDEX || (neighbour as usize) >= fc {
121 continue;
122 }
123 if labels[neighbour as usize] == INVALID_INDEX {
124 labels[neighbour as usize] = component;
125 queue[tail] = neighbour;
126 tail += 1;
127 }
128 }
129 }
130
131 component += 1;
132
133 while (seed as usize) < fc && labels[seed as usize] != INVALID_INDEX {
135 seed += 1;
136 }
137 }
138
139 Ok(component)
140}
141
142pub fn count_boundary_loops(
158 half_edges: &[HalfEdge],
159 visited: &mut [bool],
160) -> Result<u32, ConnectivityError> {
161 if visited.len() < half_edges.len() {
162 return Err(ConnectivityError::VisitedBufferTooSmall {
163 required: half_edges.len(),
164 });
165 }
166
167 for v in &mut visited[..half_edges.len()] {
168 *v = false;
169 }
170
171 let mut loop_count = 0u32;
172 let he_len = half_edges.len();
173
174 for start in 0..he_len {
175 if visited[start] || half_edges[start].twin != INVALID_INDEX {
176 continue;
177 }
178
179 loop_count += 1;
181 let mut cur = start as u32;
182 loop {
183 if (cur as usize) >= he_len {
184 return Err(ConnectivityError::HalfEdgeOutOfRange { index: cur });
185 }
186 if visited[cur as usize] {
187 break;
188 }
189 visited[cur as usize] = true;
190
191 let next_in_face = half_edges[cur as usize].next;
195 if (next_in_face as usize) >= he_len {
196 return Err(ConnectivityError::HalfEdgeOutOfRange {
197 index: next_in_face,
198 });
199 }
200
201 let mut candidate = next_in_face;
202 let mut rotations = 0;
205 while half_edges[candidate as usize].twin != INVALID_INDEX {
206 let twin = half_edges[candidate as usize].twin;
207 if (twin as usize) >= he_len {
208 return Err(ConnectivityError::HalfEdgeOutOfRange { index: twin });
209 }
210 let next_after_twin = half_edges[twin as usize].next;
211 if (next_after_twin as usize) >= he_len {
212 return Err(ConnectivityError::HalfEdgeOutOfRange {
213 index: next_after_twin,
214 });
215 }
216 candidate = next_after_twin;
217 rotations += 1;
218 if rotations > he_len {
219 return Err(ConnectivityError::HalfEdgeOutOfRange { index: candidate });
221 }
222 }
223
224 cur = candidate;
225 if cur as usize == start {
226 break;
227 }
228 }
229 }
230
231 Ok(loop_count)
232}
233
234#[inline]
246pub fn euler_characteristic(vertex_count: u32, face_count: u32, half_edges: &[HalfEdge]) -> i32 {
247 let boundary = half_edges
248 .iter()
249 .filter(|he| he.twin == INVALID_INDEX)
250 .count() as u32;
251 let edge_count = (half_edges.len() as u32 + boundary) / 2;
252 (vertex_count as i32) - (edge_count as i32) + (face_count as i32)
253}
254
255#[inline]
263pub fn genus_from_euler(euler: i32, boundary_loops: u32) -> Option<u32> {
264 let numerator = 2 - euler - boundary_loops as i32;
265 if numerator < 0 || numerator % 2 != 0 {
266 return None;
267 }
268 Some((numerator / 2) as u32)
269}
270
271pub fn compute_connectivity(
284 vertex_count: u32,
285 face_count: u32,
286 half_edges: &[HalfEdge],
287 labels: &mut [u32],
288 queue: &mut [u32],
289 visited: &mut [bool],
290) -> Result<ConnectivitySummary, ConnectivityError> {
291 let component_count = label_components(face_count, half_edges, labels, queue)?;
292 let boundary_loop_count = count_boundary_loops(half_edges, visited)?;
293
294 let boundary = half_edges
295 .iter()
296 .filter(|he| he.twin == INVALID_INDEX)
297 .count() as u32;
298 let edge_count = (half_edges.len() as u32 + boundary) / 2;
299 let euler = euler_characteristic(vertex_count, face_count, half_edges);
300 let genus = genus_from_euler(euler, boundary_loop_count);
301
302 Ok(ConnectivitySummary {
303 component_count,
304 boundary_loop_count,
305 euler_characteristic: euler,
306 genus,
307 vertex_count,
308 edge_count,
309 face_count,
310 })
311}
312
313#[cfg(test)]
318mod tests {
319 use super::*;
320 use crate::specialized_libs::computational_geometry::topology::{
321 build_triangle_half_edges, required_edge_slots, EdgeSlot,
322 };
323
324 fn build_he(vertex_count: u32, triangles: &[[u32; 3]]) -> (Vec<HalfEdge>, u32) {
325 let n = triangles.len() * 3;
326 let mut edges = vec![HalfEdge::default(); n];
327 let mut slots = vec![EdgeSlot::default(); required_edge_slots(triangles.len())];
328 let summary =
329 build_triangle_half_edges(vertex_count, triangles, &mut edges, &mut slots).unwrap();
330 (edges, summary.boundary_half_edges)
331 }
332
333 #[test]
336 fn single_triangle_one_component() {
337 let (edges, _) = build_he(3, &[[0, 1, 2]]);
338 let mut labels = [0u32; 1];
339 let mut queue = [0u32; 1];
340 let count = label_components(1, &edges, &mut labels, &mut queue).unwrap();
341 assert_eq!(count, 1);
342 assert_eq!(labels, [0]);
343 }
344
345 #[test]
346 fn two_disjoint_triangles_two_components() {
347 let (edges, _) = build_he(6, &[[0, 1, 2], [3, 4, 5]]);
348 let mut labels = [0u32; 2];
349 let mut queue = [0u32; 2];
350 let count = label_components(2, &edges, &mut labels, &mut queue).unwrap();
351 assert_eq!(count, 2);
352 assert_eq!(labels[0], 0);
353 assert_eq!(labels[1], 1);
354 }
355
356 #[test]
357 fn two_shared_edge_triangles_one_component() {
358 let (edges, _) = build_he(4, &[[0, 1, 2], [2, 1, 3]]);
359 let mut labels = [0u32; 2];
360 let mut queue = [0u32; 2];
361 let count = label_components(2, &edges, &mut labels, &mut queue).unwrap();
362 assert_eq!(count, 1);
363 assert_eq!(labels, [0, 0]);
364 }
365
366 #[test]
367 fn tetrahedron_one_component() {
368 let (edges, _) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
369 let mut labels = [0u32; 4];
370 let mut queue = [0u32; 4];
371 let count = label_components(4, &edges, &mut labels, &mut queue).unwrap();
372 assert_eq!(count, 1);
373 assert!(labels.iter().all(|&l| l == 0));
374 }
375
376 #[test]
377 fn components_deterministic() {
378 let (edges, _) = build_he(6, &[[0, 1, 2], [3, 4, 5]]);
379 let mut l1 = [0u32; 2];
380 let mut q1 = [0u32; 2];
381 let mut l2 = [0u32; 2];
382 let mut q2 = [0u32; 2];
383 label_components(2, &edges, &mut l1, &mut q1).unwrap();
384 label_components(2, &edges, &mut l2, &mut q2).unwrap();
385 assert_eq!(l1, l2);
386 }
387
388 #[test]
391 fn single_triangle_one_boundary_loop() {
392 let (edges, _) = build_he(3, &[[0, 1, 2]]);
393 let mut visited = [false; 3];
394 let loops = count_boundary_loops(&edges, &mut visited).unwrap();
395 assert_eq!(loops, 1);
396 }
397
398 #[test]
399 fn two_shared_edge_triangles_one_boundary_loop() {
400 let (edges, _) = build_he(4, &[[0, 1, 2], [2, 1, 3]]);
402 let mut visited = [false; 6];
403 let loops = count_boundary_loops(&edges, &mut visited).unwrap();
404 assert_eq!(loops, 1);
405 }
406
407 #[test]
408 fn tetrahedron_zero_boundary_loops() {
409 let (edges, _) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
410 let mut visited = [false; 12];
411 let loops = count_boundary_loops(&edges, &mut visited).unwrap();
412 assert_eq!(loops, 0);
413 }
414
415 #[test]
416 fn two_disjoint_triangles_two_boundary_loops() {
417 let (edges, _) = build_he(6, &[[0, 1, 2], [3, 4, 5]]);
418 let mut visited = [false; 6];
419 let loops = count_boundary_loops(&edges, &mut visited).unwrap();
420 assert_eq!(loops, 2);
421 }
422
423 #[test]
426 fn single_triangle_euler_1() {
427 let (edges, _) = build_he(3, &[[0, 1, 2]]);
429 let chi = euler_characteristic(3, 1, &edges);
430 assert_eq!(chi, 1);
431 }
432
433 #[test]
434 fn tetrahedron_euler_2() {
435 let (edges, _) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
437 let chi = euler_characteristic(4, 4, &edges);
438 assert_eq!(chi, 2);
439 }
440
441 #[test]
442 fn two_shared_edge_triangles_euler_1() {
443 let (edges, _) = build_he(4, &[[0, 1, 2], [2, 1, 3]]);
445 let chi = euler_characteristic(4, 2, &edges);
446 assert_eq!(chi, 1);
447 }
448
449 #[test]
452 fn tetrahedron_genus_0() {
453 let g = genus_from_euler(2, 0);
455 assert_eq!(g, Some(0));
456 }
457
458 #[test]
459 fn disk_genus_0() {
460 let g = genus_from_euler(1, 1);
462 assert_eq!(g, Some(0));
463 }
464
465 #[test]
466 fn torus_genus_1() {
467 let g = genus_from_euler(0, 0);
469 assert_eq!(g, Some(1));
470 }
471
472 #[test]
473 fn invalid_topology_genus_none() {
474 let g = genus_from_euler(3, 0);
476 assert_eq!(g, None);
477 }
478
479 #[test]
482 fn summary_tetrahedron() {
483 let (edges, _) = build_he(4, &[[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]]);
484 let mut labels = [0u32; 4];
485 let mut queue = [0u32; 4];
486 let mut visited = [false; 12];
487 let summary =
488 compute_connectivity(4, 4, &edges, &mut labels, &mut queue, &mut visited).unwrap();
489 assert_eq!(summary.component_count, 1);
490 assert_eq!(summary.boundary_loop_count, 0);
491 assert_eq!(summary.euler_characteristic, 2);
492 assert_eq!(summary.genus, Some(0));
493 assert_eq!(summary.vertex_count, 4);
494 assert_eq!(summary.edge_count, 6);
495 assert_eq!(summary.face_count, 4);
496 }
497
498 #[test]
499 fn summary_single_triangle() {
500 let (edges, _) = build_he(3, &[[0, 1, 2]]);
501 let mut labels = [0u32; 1];
502 let mut queue = [0u32; 1];
503 let mut visited = [false; 3];
504 let summary =
505 compute_connectivity(3, 1, &edges, &mut labels, &mut queue, &mut visited).unwrap();
506 assert_eq!(summary.component_count, 1);
507 assert_eq!(summary.boundary_loop_count, 1);
508 assert_eq!(summary.euler_characteristic, 1);
509 assert_eq!(summary.genus, Some(0));
510 assert_eq!(summary.edge_count, 3);
511 }
512
513 #[test]
514 fn summary_two_disjoint_triangles() {
515 let (edges, _) = build_he(6, &[[0, 1, 2], [3, 4, 5]]);
516 let mut labels = [0u32; 2];
517 let mut queue = [0u32; 2];
518 let mut visited = [false; 6];
519 let summary =
520 compute_connectivity(6, 2, &edges, &mut labels, &mut queue, &mut visited).unwrap();
521 assert_eq!(summary.component_count, 2);
522 assert_eq!(summary.boundary_loop_count, 2);
523 assert_eq!(summary.euler_characteristic, 2);
525 assert_eq!(summary.genus, None);
527 }
528
529 #[test]
530 fn summary_deterministic_across_runs() {
531 let (edges, _) = build_he(4, &[[0, 1, 2], [2, 1, 3]]);
532 let mut l1 = [0u32; 2];
533 let mut q1 = [0u32; 2];
534 let mut v1 = [false; 6];
535 let mut l2 = [0u32; 2];
536 let mut q2 = [0u32; 2];
537 let mut v2 = [false; 6];
538 let s1 = compute_connectivity(4, 2, &edges, &mut l1, &mut q1, &mut v1).unwrap();
539 let s2 = compute_connectivity(4, 2, &edges, &mut l2, &mut q2, &mut v2).unwrap();
540 assert_eq!(s1, s2);
541 assert_eq!(l1, l2);
542 }
543
544 #[test]
547 fn label_components_rejects_small_label_buffer() {
548 let (edges, _) = build_he(3, &[[0, 1, 2]]);
549 let mut labels = [0u32; 0];
550 let mut queue = [0u32; 1];
551 let err = label_components(1, &edges, &mut labels, &mut queue).unwrap_err();
552 assert_eq!(err, ConnectivityError::LabelBufferTooSmall { required: 1 });
553 }
554
555 #[test]
556 fn count_boundary_loops_rejects_small_visited() {
557 let (edges, _) = build_he(3, &[[0, 1, 2]]);
558 let mut visited = [false; 2];
559 let err = count_boundary_loops(&edges, &mut visited).unwrap_err();
560 assert_eq!(
561 err,
562 ConnectivityError::VisitedBufferTooSmall { required: 3 }
563 );
564 }
565}
566
567#[derive(Debug, Clone, Copy, PartialEq, Eq)]
569pub enum OrderedConnectivityError {
570 SizeOverflow,
571 HalfEdgeLengthMismatch { required: usize, actual: usize },
572 LabelBufferTooSmall { required: usize },
573 QueueBufferTooSmall { required: usize },
574 WorkLimitExceeded { required: usize },
575 InvalidLayout { index: u32 },
576}
577
578pub fn triangle_ordered_component_work(face_count: u32) -> Result<usize, OrderedConnectivityError> {
581 let faces=face_count as usize;
582 if face_count > u32::MAX/3 { return Err(OrderedConnectivityError::SizeOverflow); }
583 let edges=faces.checked_mul(3).ok_or(OrderedConnectivityError::SizeOverflow)?;
584 edges.checked_mul(16).and_then(|x|x.checked_add(faces.checked_mul(8)?)).and_then(|x|x.checked_add(64)).ok_or(OrderedConnectivityError::SizeOverflow)
585}
586
587pub fn label_components_triangle_ordered(
600 face_count:u32, half_edges:&[HalfEdge], max_work:usize,
601 labels:&mut [u32], queue:&mut [u32],
602) -> Result<u32,OrderedConnectivityError> {
603 let required_work=triangle_ordered_component_work(face_count)?;
604 if max_work<required_work { return Err(OrderedConnectivityError::WorkLimitExceeded{required:required_work}); }
605 let faces=face_count as usize;
606 let required=faces.checked_mul(3).ok_or(OrderedConnectivityError::SizeOverflow)?;
607 if half_edges.len()!=required { return Err(OrderedConnectivityError::HalfEdgeLengthMismatch{required,actual:half_edges.len()}); }
608 if labels.len()<faces { return Err(OrderedConnectivityError::LabelBufferTooSmall{required:faces}); }
609 if queue.len()<faces { return Err(OrderedConnectivityError::QueueBufferTooSmall{required:faces}); }
610 for (i,edge) in half_edges.iter().enumerate() {
611 let face=i/3;let base=face*3;
612 let next=(base+(i%3+1)%3) as u32;
613 if edge.face!=face as u32 || edge.next!=next { return Err(OrderedConnectivityError::InvalidLayout{index:i as u32}); }
614 if edge.twin!=INVALID_INDEX {
615 let t=edge.twin as usize;
616 if t>=required || half_edges[t].twin!=i as u32 || half_edges[t].face==edge.face {
617 return Err(OrderedConnectivityError::InvalidLayout{index:i as u32});
618 }
619 let tn=half_edges[t].next as usize;
620 if tn>=required || half_edges[t].origin!=half_edges[next as usize].origin || half_edges[tn].origin!=edge.origin {
621 return Err(OrderedConnectivityError::InvalidLayout{index:i as u32});
622 }
623 }
624 }
625 labels[..faces].fill(INVALID_INDEX);
626 let mut components=0u32;
627 for seed in 0..faces {
628 if labels[seed]!=INVALID_INDEX {continue;}
629 let mut head=0usize;let mut tail=1usize;
630 queue[0]=seed as u32;labels[seed]=components;
631 while head<tail {
632 let face=queue[head] as usize;head+=1;
633 let base=face*3;
634 for edge in &half_edges[base..base+3] {
635 if edge.twin==INVALID_INDEX {continue;}
636 let neighbor=half_edges[edge.twin as usize].face as usize;
637 if labels[neighbor]==INVALID_INDEX {
638 labels[neighbor]=components;queue[tail]=neighbor as u32;tail+=1;
639 }
640 }
641 }
642 components+=1;
643 }
644 Ok(components)
645}
646
647#[cfg(test)]
648mod triangle_ordered_connectivity_tests {
649 use super::*;
650 use super::super::topology::{build_triangle_half_edges,required_edge_slots,EdgeSlot};
651 const TET:[[u32;3];4]=[[0,2,1],[0,1,3],[1,2,3],[2,0,3]];
652 fn fixture() -> Vec<HalfEdge> {
653 let mut edges=vec![HalfEdge::default();12]; let mut slots=vec![EdgeSlot::default();required_edge_slots(4)];
654 build_triangle_half_edges(4,&TET,&mut edges,&mut slots).unwrap();edges
655 }
656 #[test]
657 fn ordered_bfs_matches_general_owner_for_connected_and_disconnected_meshes() {
658 let mut tris=TET.to_vec();tris.extend(TET.iter().map(|t|t.map(|v|v+4)));
659 let mut edges=vec![HalfEdge::default();tris.len()*3];let mut slots=vec![EdgeSlot::default();required_edge_slots(tris.len())];
660 build_triangle_half_edges(8,&tris,&mut edges,&mut slots).unwrap();
661 let mut a=vec![0;tris.len()];let mut aq=a.clone();let mut b=a.clone();let mut bq=a.clone();
662 let general=label_components(tris.len() as u32,&edges,&mut a,&mut aq).unwrap();
663 let ordered=label_components_triangle_ordered(tris.len() as u32,&edges,triangle_ordered_component_work(tris.len() as u32).unwrap(),&mut b,&mut bq).unwrap();
664 assert_eq!(general,2);assert_eq!(ordered,general);assert_eq!(a,b);
665 }
666 #[test]
667 fn malformed_layout_and_insufficient_work_refuse_without_scratch_mutation() {
668 let mut edges=fixture();let mut labels=vec![77;4];let mut queue=vec![88;4];
669 let work=triangle_ordered_component_work(4).unwrap();
670 assert_eq!(label_components_triangle_ordered(4,&edges,work-1,&mut labels,&mut queue),Err(OrderedConnectivityError::WorkLimitExceeded{required:work}));
671 assert_eq!(labels,vec![77;4]);assert_eq!(queue,vec![88;4]);
672 edges[0].next=0;
673 assert_eq!(label_components_triangle_ordered(4,&edges,work,&mut labels,&mut queue),Err(OrderedConnectivityError::InvalidLayout{index:0}));
674 assert_eq!(labels,vec![77;4]);assert_eq!(queue,vec![88;4]);
675 let mut edges=fixture();edges[0].twin=99;
676 assert_eq!(label_components_triangle_ordered(4,&edges,work,&mut labels,&mut queue),Err(OrderedConnectivityError::InvalidLayout{index:0}));
677 assert_eq!(labels,vec![77;4]);assert_eq!(queue,vec![88;4]);
678 let mut edges=fixture();let twin=edges[0].twin as usize;edges[twin].origin=99;
679 assert_eq!(label_components_triangle_ordered(4,&edges,work,&mut labels,&mut queue),Err(OrderedConnectivityError::InvalidLayout{index:0}));
680 assert_eq!(labels,vec![77;4]);assert_eq!(queue,vec![88;4]);
681 let edges=fixture();
682 assert_eq!(label_components_triangle_ordered(4,&edges,work,&mut labels[..3],&mut queue),Err(OrderedConnectivityError::LabelBufferTooSmall{required:4}));
683 assert_eq!(labels,vec![77;4]);assert_eq!(queue,vec![88;4]);
684 assert_eq!(label_components_triangle_ordered(4,&edges,work,&mut labels,&mut queue[..3]),Err(OrderedConnectivityError::QueueBufferTooSmall{required:4}));
685 assert_eq!(labels,vec![77;4]);assert_eq!(queue,vec![88;4]);
686 }
687 #[test]
688 fn old_general_api_still_accepts_non_contiguous_order() {
689 let edges=[HalfEdge{origin:0,twin:INVALID_INDEX,next:2,face:0},HalfEdge{origin:2,twin:INVALID_INDEX,next:0,face:0},HalfEdge{origin:1,twin:INVALID_INDEX,next:1,face:0}];
690 let mut labels=[77];let mut queue=[88];
691 assert_eq!(label_components(1,&edges,&mut labels,&mut queue).unwrap(),1);
692 labels=[77];queue=[88];
693 assert_eq!(label_components_triangle_ordered(1,&edges,triangle_ordered_component_work(1).unwrap(),&mut labels,&mut queue),Err(OrderedConnectivityError::InvalidLayout{index:0}));
694 assert_eq!(labels,[77]);assert_eq!(queue,[88]);
695 }
696}