mesh_repair/
components.rs

1//! Connected component analysis for meshes.
2//!
3//! This module provides tools for detecting and handling disconnected mesh components.
4//! A connected component is a set of faces that are connected to each other through
5//! shared edges or vertices.
6
7use std::cmp::Reverse;
8
9use hashbrown::{HashMap, HashSet};
10use tracing::{debug, info};
11
12use crate::adjacency::MeshAdjacency;
13use crate::types::Mesh;
14
15/// Result of connected component analysis.
16#[derive(Debug, Clone)]
17pub struct ComponentAnalysis {
18    /// Number of connected components found.
19    pub component_count: usize,
20    /// Face indices for each component, sorted by component size (largest first).
21    pub components: Vec<Vec<u32>>,
22    /// Size of the largest component (number of faces).
23    pub largest_component_size: usize,
24    /// Size of the smallest component (number of faces).
25    pub smallest_component_size: usize,
26}
27
28impl ComponentAnalysis {
29    /// Check if the mesh is fully connected (single component).
30    pub fn is_connected(&self) -> bool {
31        self.component_count == 1
32    }
33
34    /// Get the face indices of the largest component.
35    pub fn largest_component(&self) -> &[u32] {
36        self.components.first().map(|v| v.as_slice()).unwrap_or(&[])
37    }
38}
39
40impl std::fmt::Display for ComponentAnalysis {
41    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42        writeln!(f, "Component Analysis:")?;
43        writeln!(f, "  Connected components: {}", self.component_count)?;
44        if self.component_count > 0 {
45            writeln!(
46                f,
47                "  Largest component: {} faces",
48                self.largest_component_size
49            )?;
50            writeln!(
51                f,
52                "  Smallest component: {} faces",
53                self.smallest_component_size
54            )?;
55            if self.component_count > 1 {
56                writeln!(f, "  Component sizes:")?;
57                for (i, comp) in self.components.iter().enumerate() {
58                    writeln!(f, "    Component {}: {} faces", i + 1, comp.len())?;
59                }
60            }
61        }
62        Ok(())
63    }
64}
65
66/// Find all connected components in a mesh.
67///
68/// Uses a flood-fill algorithm starting from each unvisited face.
69/// Two faces are connected if they share an edge.
70///
71/// # Arguments
72/// * `mesh` - The mesh to analyze
73///
74/// # Returns
75/// A `ComponentAnalysis` containing the component information.
76///
77/// # Example
78/// ```
79/// use mesh_repair::{Mesh, Vertex};
80/// use mesh_repair::components::find_connected_components;
81///
82/// let mut mesh = Mesh::new();
83/// // Add two disconnected triangles
84/// mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
85/// mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
86/// mesh.vertices.push(Vertex::from_coords(0.0, 1.0, 0.0));
87/// mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
88/// mesh.vertices.push(Vertex::from_coords(11.0, 0.0, 0.0));
89/// mesh.vertices.push(Vertex::from_coords(10.0, 1.0, 0.0));
90/// mesh.faces.push([0, 1, 2]);
91/// mesh.faces.push([3, 4, 5]);
92///
93/// let analysis = find_connected_components(&mesh);
94/// assert_eq!(analysis.component_count, 2);
95/// ```
96pub fn find_connected_components(mesh: &Mesh) -> ComponentAnalysis {
97    if mesh.faces.is_empty() {
98        return ComponentAnalysis {
99            component_count: 0,
100            components: Vec::new(),
101            largest_component_size: 0,
102            smallest_component_size: 0,
103        };
104    }
105
106    let adjacency = MeshAdjacency::build(&mesh.faces);
107    let face_count = mesh.faces.len();
108
109    // Build face-to-face adjacency via shared edges
110    let mut face_neighbors: Vec<Vec<u32>> = vec![Vec::new(); face_count];
111    for faces in adjacency.edge_to_faces.values() {
112        if faces.len() == 2 {
113            let f0 = faces[0];
114            let f1 = faces[1];
115            face_neighbors[f0 as usize].push(f1);
116            face_neighbors[f1 as usize].push(f0);
117        }
118    }
119
120    // Flood-fill to find connected components
121    let mut visited = vec![false; face_count];
122    let mut components: Vec<Vec<u32>> = Vec::new();
123
124    for start_face in 0..face_count {
125        if visited[start_face] {
126            continue;
127        }
128
129        // BFS flood fill from this face
130        let mut component = Vec::new();
131        let mut queue = vec![start_face as u32];
132        visited[start_face] = true;
133
134        while let Some(face_idx) = queue.pop() {
135            component.push(face_idx);
136
137            for &neighbor in &face_neighbors[face_idx as usize] {
138                if !visited[neighbor as usize] {
139                    visited[neighbor as usize] = true;
140                    queue.push(neighbor);
141                }
142            }
143        }
144
145        components.push(component);
146    }
147
148    // Sort components by size (largest first)
149    components.sort_by_key(|c| Reverse(c.len()));
150
151    let component_count = components.len();
152    let largest_component_size = components.first().map(|c| c.len()).unwrap_or(0);
153    let smallest_component_size = components.last().map(|c| c.len()).unwrap_or(0);
154
155    info!(
156        "Found {} connected component(s) in mesh with {} faces",
157        component_count, face_count
158    );
159
160    if component_count > 1 {
161        debug!(
162            "Component sizes: {:?}",
163            components.iter().map(|c| c.len()).collect::<Vec<_>>()
164        );
165    }
166
167    ComponentAnalysis {
168        component_count,
169        components,
170        largest_component_size,
171        smallest_component_size,
172    }
173}
174
175/// Split a mesh into separate meshes, one per connected component.
176///
177/// Each resulting mesh is independent and has its own vertex and face arrays.
178/// The original vertex attributes (normals, tags, offsets) are preserved.
179///
180/// # Arguments
181/// * `mesh` - The mesh to split
182///
183/// # Returns
184/// A vector of meshes, one per component, sorted by size (largest first).
185///
186/// # Example
187/// ```
188/// use mesh_repair::{Mesh, Vertex};
189/// use mesh_repair::components::split_into_components;
190///
191/// let mut mesh = Mesh::new();
192/// // Add two disconnected triangles
193/// mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
194/// mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
195/// mesh.vertices.push(Vertex::from_coords(0.0, 1.0, 0.0));
196/// mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
197/// mesh.vertices.push(Vertex::from_coords(11.0, 0.0, 0.0));
198/// mesh.vertices.push(Vertex::from_coords(10.0, 1.0, 0.0));
199/// mesh.faces.push([0, 1, 2]);
200/// mesh.faces.push([3, 4, 5]);
201///
202/// let components = split_into_components(&mesh);
203/// assert_eq!(components.len(), 2);
204/// assert_eq!(components[0].face_count(), 1);
205/// assert_eq!(components[1].face_count(), 1);
206/// ```
207pub fn split_into_components(mesh: &Mesh) -> Vec<Mesh> {
208    let analysis = find_connected_components(mesh);
209
210    if analysis.component_count <= 1 {
211        // Return clone of original if single component or empty
212        return vec![mesh.clone()];
213    }
214
215    info!(
216        "Splitting mesh into {} components",
217        analysis.component_count
218    );
219
220    let mut result = Vec::with_capacity(analysis.component_count);
221
222    for (comp_idx, face_indices) in analysis.components.iter().enumerate() {
223        // Collect all vertices used by this component
224        let mut used_vertices: HashSet<u32> = HashSet::new();
225        for &face_idx in face_indices {
226            let face = &mesh.faces[face_idx as usize];
227            used_vertices.insert(face[0]);
228            used_vertices.insert(face[1]);
229            used_vertices.insert(face[2]);
230        }
231
232        // Create mapping from old vertex index to new vertex index
233        let mut old_to_new: HashMap<u32, u32> = HashMap::new();
234        let mut new_vertices = Vec::with_capacity(used_vertices.len());
235
236        for old_idx in used_vertices {
237            let new_idx = new_vertices.len() as u32;
238            old_to_new.insert(old_idx, new_idx);
239            new_vertices.push(mesh.vertices[old_idx as usize].clone());
240        }
241
242        // Remap face indices
243        let new_faces: Vec<[u32; 3]> = face_indices
244            .iter()
245            .map(|&face_idx| {
246                let face = &mesh.faces[face_idx as usize];
247                [
248                    *old_to_new.get(&face[0]).unwrap(),
249                    *old_to_new.get(&face[1]).unwrap(),
250                    *old_to_new.get(&face[2]).unwrap(),
251                ]
252            })
253            .collect();
254
255        debug!(
256            "Component {}: {} vertices, {} faces",
257            comp_idx + 1,
258            new_vertices.len(),
259            new_faces.len()
260        );
261
262        result.push(Mesh {
263            vertices: new_vertices,
264            faces: new_faces,
265        });
266    }
267
268    result
269}
270
271/// Keep only the largest connected component in a mesh.
272///
273/// Modifies the mesh in-place, removing all faces and vertices that don't belong
274/// to the largest connected component.
275///
276/// # Arguments
277/// * `mesh` - The mesh to modify
278///
279/// # Returns
280/// The number of components that were removed.
281///
282/// # Example
283/// ```
284/// use mesh_repair::{Mesh, Vertex};
285/// use mesh_repair::components::keep_largest_component;
286///
287/// let mut mesh = Mesh::new();
288/// // Add two disconnected triangles
289/// mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
290/// mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
291/// mesh.vertices.push(Vertex::from_coords(0.0, 1.0, 0.0));
292/// mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
293/// mesh.vertices.push(Vertex::from_coords(11.0, 0.0, 0.0));
294/// mesh.vertices.push(Vertex::from_coords(10.0, 1.0, 0.0));
295/// mesh.faces.push([0, 1, 2]);
296/// mesh.faces.push([3, 4, 5]);
297///
298/// let removed = keep_largest_component(&mut mesh);
299/// assert_eq!(removed, 1);
300/// assert_eq!(mesh.face_count(), 1);
301/// ```
302pub fn keep_largest_component(mesh: &mut Mesh) -> usize {
303    let analysis = find_connected_components(mesh);
304
305    if analysis.component_count <= 1 {
306        return 0;
307    }
308
309    let components_removed = analysis.component_count - 1;
310
311    info!(
312        "Keeping largest component ({} faces), removing {} smaller component(s)",
313        analysis.largest_component_size, components_removed
314    );
315
316    // Get the largest component (first one, since sorted by size)
317    let largest = split_into_components(mesh).into_iter().next().unwrap();
318
319    // Replace mesh contents with largest component
320    mesh.vertices = largest.vertices;
321    mesh.faces = largest.faces;
322
323    components_removed
324}
325
326/// Keep only components that meet a minimum face count threshold.
327///
328/// Useful for removing small noise components from scanned meshes.
329///
330/// # Arguments
331/// * `mesh` - The mesh to modify
332/// * `min_faces` - Minimum number of faces a component must have to be kept
333///
334/// # Returns
335/// The number of components that were removed.
336///
337/// # Example
338/// ```
339/// use mesh_repair::{Mesh, Vertex};
340/// use mesh_repair::components::remove_small_components;
341///
342/// let mut mesh = Mesh::new();
343/// // Create mesh with components of different sizes...
344/// // remove_small_components(&mut mesh, 100); // Remove components < 100 faces
345/// ```
346pub fn remove_small_components(mesh: &mut Mesh, min_faces: usize) -> usize {
347    let analysis = find_connected_components(mesh);
348
349    if analysis.component_count <= 1 {
350        if analysis.largest_component_size < min_faces {
351            // Single component but too small - clear the mesh
352            mesh.vertices.clear();
353            mesh.faces.clear();
354            return 1;
355        }
356        return 0;
357    }
358
359    // Find components to keep
360    let components_to_keep: Vec<&Vec<u32>> = analysis
361        .components
362        .iter()
363        .filter(|c| c.len() >= min_faces)
364        .collect();
365
366    if components_to_keep.is_empty() {
367        mesh.vertices.clear();
368        mesh.faces.clear();
369        return analysis.component_count;
370    }
371
372    let components_removed = analysis.component_count - components_to_keep.len();
373
374    if components_removed == 0 {
375        return 0;
376    }
377
378    info!(
379        "Removing {} component(s) with fewer than {} faces",
380        components_removed, min_faces
381    );
382
383    // Collect face indices to keep
384    let face_indices_to_keep: HashSet<u32> = components_to_keep
385        .iter()
386        .flat_map(|c| c.iter().copied())
387        .collect();
388
389    // Collect vertices used by kept faces
390    let mut used_vertices: HashSet<u32> = HashSet::new();
391    for &face_idx in &face_indices_to_keep {
392        let face = &mesh.faces[face_idx as usize];
393        used_vertices.insert(face[0]);
394        used_vertices.insert(face[1]);
395        used_vertices.insert(face[2]);
396    }
397
398    // Create new vertex array and mapping
399    let mut old_to_new: HashMap<u32, u32> = HashMap::new();
400    let mut new_vertices = Vec::with_capacity(used_vertices.len());
401
402    for old_idx in 0..mesh.vertices.len() as u32 {
403        if used_vertices.contains(&old_idx) {
404            let new_idx = new_vertices.len() as u32;
405            old_to_new.insert(old_idx, new_idx);
406            new_vertices.push(mesh.vertices[old_idx as usize].clone());
407        }
408    }
409
410    // Create new face array with remapped indices
411    let new_faces: Vec<[u32; 3]> = (0..mesh.faces.len())
412        .filter(|&i| face_indices_to_keep.contains(&(i as u32)))
413        .map(|i| {
414            let face = &mesh.faces[i];
415            [
416                *old_to_new.get(&face[0]).unwrap(),
417                *old_to_new.get(&face[1]).unwrap(),
418                *old_to_new.get(&face[2]).unwrap(),
419            ]
420        })
421        .collect();
422
423    mesh.vertices = new_vertices;
424    mesh.faces = new_faces;
425
426    components_removed
427}
428
429#[cfg(test)]
430mod tests {
431    use super::*;
432    use crate::Vertex;
433
434    fn create_single_triangle() -> Mesh {
435        let mut mesh = Mesh::new();
436        mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
437        mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
438        mesh.vertices.push(Vertex::from_coords(0.0, 1.0, 0.0));
439        mesh.faces.push([0, 1, 2]);
440        mesh
441    }
442
443    fn create_two_disconnected_triangles() -> Mesh {
444        let mut mesh = Mesh::new();
445        // First triangle
446        mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
447        mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
448        mesh.vertices.push(Vertex::from_coords(0.0, 1.0, 0.0));
449        // Second triangle (disconnected)
450        mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
451        mesh.vertices.push(Vertex::from_coords(11.0, 0.0, 0.0));
452        mesh.vertices.push(Vertex::from_coords(10.0, 1.0, 0.0));
453        mesh.faces.push([0, 1, 2]);
454        mesh.faces.push([3, 4, 5]);
455        mesh
456    }
457
458    fn create_two_connected_triangles() -> Mesh {
459        let mut mesh = Mesh::new();
460        mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
461        mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
462        mesh.vertices.push(Vertex::from_coords(0.5, 1.0, 0.0));
463        mesh.vertices.push(Vertex::from_coords(1.5, 1.0, 0.0));
464        // Two triangles sharing edge (1, 2)
465        mesh.faces.push([0, 1, 2]);
466        mesh.faces.push([1, 3, 2]);
467        mesh
468    }
469
470    fn create_three_components() -> Mesh {
471        let mut mesh = Mesh::new();
472
473        // Component 1: 2 triangles
474        mesh.vertices.push(Vertex::from_coords(0.0, 0.0, 0.0));
475        mesh.vertices.push(Vertex::from_coords(1.0, 0.0, 0.0));
476        mesh.vertices.push(Vertex::from_coords(0.5, 1.0, 0.0));
477        mesh.vertices.push(Vertex::from_coords(1.5, 1.0, 0.0));
478        mesh.faces.push([0, 1, 2]);
479        mesh.faces.push([1, 3, 2]);
480
481        // Component 2: 1 triangle
482        mesh.vertices.push(Vertex::from_coords(10.0, 0.0, 0.0));
483        mesh.vertices.push(Vertex::from_coords(11.0, 0.0, 0.0));
484        mesh.vertices.push(Vertex::from_coords(10.0, 1.0, 0.0));
485        mesh.faces.push([4, 5, 6]);
486
487        // Component 3: 1 triangle
488        mesh.vertices.push(Vertex::from_coords(20.0, 0.0, 0.0));
489        mesh.vertices.push(Vertex::from_coords(21.0, 0.0, 0.0));
490        mesh.vertices.push(Vertex::from_coords(20.0, 1.0, 0.0));
491        mesh.faces.push([7, 8, 9]);
492
493        mesh
494    }
495
496    #[test]
497    fn test_empty_mesh() {
498        let mesh = Mesh::new();
499        let analysis = find_connected_components(&mesh);
500        assert_eq!(analysis.component_count, 0);
501        assert!(!analysis.is_connected());
502    }
503
504    #[test]
505    fn test_single_component() {
506        let mesh = create_single_triangle();
507        let analysis = find_connected_components(&mesh);
508        assert_eq!(analysis.component_count, 1);
509        assert!(analysis.is_connected());
510        assert_eq!(analysis.largest_component_size, 1);
511    }
512
513    #[test]
514    fn test_two_disconnected_components() {
515        let mesh = create_two_disconnected_triangles();
516        let analysis = find_connected_components(&mesh);
517        assert_eq!(analysis.component_count, 2);
518        assert!(!analysis.is_connected());
519        assert_eq!(analysis.largest_component_size, 1);
520        assert_eq!(analysis.smallest_component_size, 1);
521    }
522
523    #[test]
524    fn test_connected_triangles() {
525        let mesh = create_two_connected_triangles();
526        let analysis = find_connected_components(&mesh);
527        assert_eq!(analysis.component_count, 1);
528        assert!(analysis.is_connected());
529        assert_eq!(analysis.largest_component_size, 2);
530    }
531
532    #[test]
533    fn test_three_components_sorted_by_size() {
534        let mesh = create_three_components();
535        let analysis = find_connected_components(&mesh);
536        assert_eq!(analysis.component_count, 3);
537        assert_eq!(analysis.largest_component_size, 2);
538        assert_eq!(analysis.smallest_component_size, 1);
539        // Largest component should be first
540        assert_eq!(analysis.components[0].len(), 2);
541    }
542
543    #[test]
544    fn test_split_single_component() {
545        let mesh = create_single_triangle();
546        let components = split_into_components(&mesh);
547        assert_eq!(components.len(), 1);
548        assert_eq!(components[0].face_count(), 1);
549        assert_eq!(components[0].vertex_count(), 3);
550    }
551
552    #[test]
553    fn test_split_two_components() {
554        let mesh = create_two_disconnected_triangles();
555        let components = split_into_components(&mesh);
556        assert_eq!(components.len(), 2);
557        // Each component should have its own vertices (not shared)
558        assert_eq!(components[0].vertex_count(), 3);
559        assert_eq!(components[1].vertex_count(), 3);
560        assert_eq!(components[0].face_count(), 1);
561        assert_eq!(components[1].face_count(), 1);
562    }
563
564    #[test]
565    fn test_split_preserves_geometry() {
566        let mesh = create_two_disconnected_triangles();
567        let components = split_into_components(&mesh);
568
569        // Check that face indices are valid in each component
570        for comp in &components {
571            for face in &comp.faces {
572                assert!(face[0] < comp.vertices.len() as u32);
573                assert!(face[1] < comp.vertices.len() as u32);
574                assert!(face[2] < comp.vertices.len() as u32);
575            }
576        }
577    }
578
579    #[test]
580    fn test_keep_largest_single_component() {
581        let mut mesh = create_single_triangle();
582        let removed = keep_largest_component(&mut mesh);
583        assert_eq!(removed, 0);
584        assert_eq!(mesh.face_count(), 1);
585    }
586
587    #[test]
588    fn test_keep_largest_multiple_components() {
589        let mut mesh = create_three_components();
590        let removed = keep_largest_component(&mut mesh);
591        assert_eq!(removed, 2);
592        assert_eq!(mesh.face_count(), 2); // Kept the component with 2 faces
593    }
594
595    #[test]
596    fn test_remove_small_components_none_removed() {
597        let mut mesh = create_three_components();
598        let removed = remove_small_components(&mut mesh, 1);
599        assert_eq!(removed, 0);
600        assert_eq!(mesh.face_count(), 4); // All components kept
601    }
602
603    #[test]
604    fn test_remove_small_components_some_removed() {
605        let mut mesh = create_three_components();
606        let removed = remove_small_components(&mut mesh, 2);
607        assert_eq!(removed, 2); // Removed the two 1-face components
608        assert_eq!(mesh.face_count(), 2); // Only 2-face component kept
609    }
610
611    #[test]
612    fn test_remove_small_components_all_removed() {
613        let mut mesh = create_three_components();
614        let removed = remove_small_components(&mut mesh, 10);
615        assert_eq!(removed, 3);
616        assert_eq!(mesh.face_count(), 0);
617        assert_eq!(mesh.vertex_count(), 0);
618    }
619
620    #[test]
621    fn test_component_analysis_display() {
622        let mesh = create_three_components();
623        let analysis = find_connected_components(&mesh);
624        let output = format!("{}", analysis);
625        assert!(output.contains("Connected components: 3"));
626        assert!(output.contains("Largest component: 2 faces"));
627    }
628}
mesh_repair/components.rs

mesh_repair/
components.rs
