Skip to main content

qualia_core_db/specialized_libs/computational_geometry/
connectivity.rs

1//! Connectivity invariants: components, boundary loops, Euler characteristic, genus.
2//!
3//! Given a half-edge mesh, these functions compute graph-theoretic invariants
4//! using the CSR face-adjacency view from [`super::csr_adjacency`]. All
5//! functions are caller-buffered and zero-heap (no `Vec`/`String`/`Box` in
6//! any hot function; test helpers may allocate for setup only).
7//!
8//! # Invariants
9//!
10//! - **Connected components** — BFS over the face-adjacency graph (faces
11//!   connected via twin links belong to the same component). Deterministic:
12//!   seed = face 0, BFS visits neighbours in ascending face-index order.
13//! - **Boundary loops** — count by walking boundary half-edges (twin ==
14//!   `INVALID_INDEX`) and grouping them into cycles via `next` links.
15//! - **Euler characteristic** — χ = V − E + F, where V = vertex count,
16//!   E = unique undirected edges, F = face count.
17//! - **Genus** — for a closed orientable surface: g = (2 − χ) / 2. For
18//!   surfaces with boundary: g = (2 − χ − b) / 2, where b = boundary loop count.
19//!   Returns `None` if the surface is non-orientable or the formula doesn't
20//!   yield a non-negative integer (indicating invalid/inconsistent topology).
21
22use super::topology::{HalfEdge, INVALID_INDEX};
23
24// ---------------------------------------------------------------------------
25// Errors
26// ---------------------------------------------------------------------------
27
28/// Errors raised by the connectivity invariant functions.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub enum ConnectivityError {
31    /// `labels` buffer too small (needs `face_count` entries).
32    LabelBufferTooSmall { required: usize },
33    /// `queue` buffer too small (needs `face_count` entries).
34    QueueBufferTooSmall { required: usize },
35    /// `visited` buffer too small (needs `half_edge_count` entries).
36    VisitedBufferTooSmall { required: usize },
37    /// A half-edge link points outside the half-edge array.
38    HalfEdgeOutOfRange { index: u32 },
39}
40
41/// Summary of mesh connectivity invariants.
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub struct ConnectivitySummary {
44    /// Number of connected components (face-connectivity via twin links).
45    pub component_count: u32,
46    /// Number of boundary loops (cycles of boundary half-edges).
47    pub boundary_loop_count: u32,
48    /// Euler characteristic χ = V − E + F.
49    pub euler_characteristic: i32,
50    /// Genus (None if non-orientable or inconsistent).
51    pub genus: Option<u32>,
52    /// Vertex count.
53    pub vertex_count: u32,
54    /// Edge count (unique undirected edges).
55    pub edge_count: u32,
56    /// Face count.
57    pub face_count: u32,
58}
59
60// ---------------------------------------------------------------------------
61// Connected components via BFS over face adjacency
62// ---------------------------------------------------------------------------
63
64/// Label connected components by BFS over the face-adjacency graph.
65///
66/// Two faces are in the same component if connected by a path of twin-linked
67/// half-edges. `labels[f]` receives the component index (0-based, assigned in
68/// ascending face-index order of first encounter). `queue` is a workspace
69/// buffer of length `face_count`.
70///
71/// Returns the number of connected components.
72///
73/// Zero-heap. Deterministic.
74pub 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        // BFS from this seed.
97        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            // Find all half-edges of this face and follow twins.
108            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        // Advance seed to next unlabelled face.
134        while (seed as usize) < fc && labels[seed as usize] != INVALID_INDEX {
135            seed += 1;
136        }
137    }
138
139    Ok(component)
140}
141
142// ---------------------------------------------------------------------------
143// Boundary loop counting
144// ---------------------------------------------------------------------------
145
146/// Count boundary loops by walking cycles of boundary half-edges.
147///
148/// A boundary half-edge has `twin == INVALID_INDEX`. To walk a boundary loop,
149/// from each boundary half-edge we go to `next` (same face), then if that edge
150/// has a twin, cross to the twin and go to its `next`, repeating until we find
151/// the next boundary edge. This rotates around the destination vertex until
152/// exiting the interior.
153///
154/// `visited` is a workspace buffer of length `half_edges.len()`.
155///
156/// Zero-heap. Deterministic.
157pub 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        // Walk the boundary cycle starting at this boundary half-edge.
180        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            // Find the next boundary half-edge by rotating around the
192            // destination vertex: go to `next`, then cross twins until we
193            // exit the interior.
194            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            // If the candidate is interior (has a twin), rotate: cross to
203            // twin, go to its next, repeat. Bounded by he_len iterations.
204            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                    // Malformed mesh — stuck in a cycle with no boundary.
220                    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// ---------------------------------------------------------------------------
235// Euler characteristic and genus
236// ---------------------------------------------------------------------------
237
238/// Compute the Euler characteristic χ = V − E + F.
239///
240/// - `vertex_count`: number of unique vertices.
241/// - `face_count`: number of faces.
242/// - `half_edges`: the half-edge array. Unique undirected edges are counted
243///   as (total half-edges + boundary half-edges) / 2, since each interior edge
244///   contributes 2 half-edges and each boundary edge contributes 1.
245#[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/// Compute genus from the Euler characteristic and boundary loop count.
256///
257/// For a closed orientable surface: g = (2 − χ) / 2.
258/// For a surface with b boundary loops: g = (2 − χ − b) / 2.
259///
260/// Returns `None` if the result is negative or non-integer (indicating
261/// non-orientable or inconsistent topology).
262#[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
271// ---------------------------------------------------------------------------
272// Full connectivity summary
273// ---------------------------------------------------------------------------
274
275/// Compute the full connectivity summary in one call.
276///
277/// Requires workspace buffers:
278/// - `labels`: `face_count` entries.
279/// - `queue`: `face_count` entries.
280/// - `visited`: `half_edges.len()` entries.
281///
282/// Zero-heap. Deterministic.
283pub 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// ---------------------------------------------------------------------------
314// Tests
315// ---------------------------------------------------------------------------
316
317#[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    // --- connected components ----------------------------------------------
334
335    #[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    // --- boundary loops ----------------------------------------------------
389
390    #[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        // Two triangles sharing an edge → one boundary loop of 4 edges.
401        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    // --- Euler characteristic ----------------------------------------------
424
425    #[test]
426    fn single_triangle_euler_1() {
427        // V=3, E=3, F=1 → χ=1
428        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        // V=4, E=6, F=4 → χ=2
436        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        // V=4, E=5, F=2 → χ=1
444        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    // --- genus --------------------------------------------------------------
450
451    #[test]
452    fn tetrahedron_genus_0() {
453        // χ=2, b=0 → g=(2-2-0)/2=0
454        let g = genus_from_euler(2, 0);
455        assert_eq!(g, Some(0));
456    }
457
458    #[test]
459    fn disk_genus_0() {
460        // Single triangle: χ=1, b=1 → g=(2-1-1)/2=0
461        let g = genus_from_euler(1, 1);
462        assert_eq!(g, Some(0));
463    }
464
465    #[test]
466    fn torus_genus_1() {
467        // Torus: χ=0, b=0 → g=(2-0-0)/2=1
468        let g = genus_from_euler(0, 0);
469        assert_eq!(g, Some(1));
470    }
471
472    #[test]
473    fn invalid_topology_genus_none() {
474        // χ=3, b=0 → g=(2-3-0)/2 = -1/2 → None
475        let g = genus_from_euler(3, 0);
476        assert_eq!(g, None);
477    }
478
479    // --- full summary -------------------------------------------------------
480
481    #[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        // V=6, E=6, F=2 → χ=2
524        assert_eq!(summary.euler_characteristic, 2);
525        // g=(2-2-2)/2 = -1 → None (two disjoint disks, not a single surface)
526        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    // --- buffer size errors ------------------------------------------------
545
546    #[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/// Error for the checked triangle-ordered connectivity traversal.
568#[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
578/// Conservative work units for checked triangle-ordered validation and BFS.
579/// This is a deterministic accounting bound, not a measurement of CPU time.
580pub 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
587/// Label components in the checked contiguous triangle layout emitted by
588/// `topology::build_triangle_half_edges`. Unlike the general `label_components`
589/// API, which accepts arbitrary half-edge ordering, this operation visits only
590/// each face's three half-edges during BFS. Identical input yields identical
591/// labels. `labels` and `queue` are caller-owned; no heap allocation occurs.
592///
593/// Before writing either buffer, the function checks buffer lengths, work cap,
594/// exact `3 * face_count` length, face/next layout and all paired reverse twins.
595/// Invalid inputs refuse without modifying buffers. The work bound covers
596/// validation and traversal, and is independent of hash-probe costs of the
597/// separate half-edge constructor. This validates topological layout only; it
598/// does not establish geometric manifoldness or absence of self-intersections.
599pub 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}