axiolid_mesh/
component.rs

1//! Splitting a mesh into connected components, and recombining them (#85).
2//!
3//! Two providers already walked this graph to count components and returned
4//! only the count, discarding the partition they had just built. This owns
5//! the partition; the counters become callers of it.
6//!
7//! Connectivity is by shared vertex index, not by geometric proximity: two
8//! triangles that touch in space but reference distinct indices belong to
9//! distinct components. Welding is `axiolid-heal`'s job and stays there.
10
11use crate::TriMesh;
12use std::collections::BTreeMap;
13
14/// Disjoint-set over vertex indices, unioned across each triangle's corners.
15struct Partition {
16    parent: Vec<usize>,
17}
18
19impl Partition {
20    fn new(count: usize) -> Self {
21        Self {
22            parent: (0..count).collect(),
23        }
24    }
25
26    fn find(&mut self, mut node: usize) -> usize {
27        while self.parent[node] != node {
28            self.parent[node] = self.parent[self.parent[node]];
29            node = self.parent[node];
30        }
31        node
32    }
33
34    fn union(&mut self, a: usize, b: usize) {
35        let (ra, rb) = (self.find(a), self.find(b));
36        if ra != rb {
37            self.parent[rb] = ra;
38        }
39    }
40}
41
42/// Build the vertex partition for a mesh.
43fn partition_of(mesh: &TriMesh) -> Partition {
44    let mut partition = Partition::new(mesh.positions.len());
45    for triangle in mesh.indices.chunks_exact(3) {
46        let first = triangle[0] as usize;
47        for corner in &triangle[1..] {
48            partition.union(first, *corner as usize);
49        }
50    }
51    partition
52}
53
54/// Number of connected components, counting only referenced vertices.
55///
56/// An unreferenced position is unused data, not a component of its own.
57pub fn component_count(mesh: &TriMesh) -> usize {
58    if mesh.indices.is_empty() {
59        return 0;
60    }
61    let mut partition = partition_of(mesh);
62    let mut roots = std::collections::BTreeSet::new();
63    for index in &mesh.indices {
64        let root = partition.find(*index as usize);
65        roots.insert(root);
66    }
67    roots.len()
68}
69
70/// Split a mesh into its connected components.
71///
72/// Components are ordered by the smallest triangle index they contain, so
73/// the same input always produces the same order -- iteration order of a
74/// hash map would not, and #85 requires determinism.
75///
76/// A single-body mesh returns one component whose triangles are in input
77/// order, so decomposing a connected mesh is not a reindexing hazard.
78pub fn decompose(mesh: &TriMesh) -> Vec<TriMesh> {
79    if mesh.indices.is_empty() {
80        return Vec::new();
81    }
82    let mut partition = partition_of(mesh);
83
84    // Group triangles by the root of their first corner. BTreeMap keyed by
85    // first appearance keeps the order deterministic and input-shaped.
86    let mut order: BTreeMap<usize, usize> = BTreeMap::new();
87    let mut groups: Vec<Vec<usize>> = Vec::new();
88    for (triangle_index, triangle) in mesh.indices.chunks_exact(3).enumerate() {
89        let root = partition.find(triangle[0] as usize);
90        let slot = *order.entry(root).or_insert_with(|| {
91            groups.push(Vec::new());
92            groups.len() - 1
93        });
94        groups[slot].push(triangle_index);
95    }
96
97    // A connected mesh comes back exactly as it went in. Reindexing a
98    // single-body mesh would make "decompose defensively" cost a rebuild and
99    // invalidate any index the caller already holds.
100    if groups.len() == 1 && mesh.positions.len() == referenced(mesh) {
101        return vec![mesh.clone()];
102    }
103
104    groups
105        .into_iter()
106        .map(|triangles| extract(mesh, &triangles))
107        .collect()
108}
109
110/// Count of distinct vertices actually referenced by a triangle.
111fn referenced(mesh: &TriMesh) -> usize {
112    mesh.indices
113        .iter()
114        .collect::<std::collections::BTreeSet<_>>()
115        .len()
116}
117
118/// Build one component mesh from a triangle selection.
119///
120/// Vertices are emitted in first-use order and reindexed, so a component
121/// carries only the positions it references.
122fn extract(mesh: &TriMesh, triangles: &[usize]) -> TriMesh {
123    let mut remap: BTreeMap<u32, u32> = BTreeMap::new();
124    let mut positions = Vec::new();
125    let mut indices = Vec::with_capacity(triangles.len() * 3);
126    for &triangle in triangles {
127        for corner in 0..3 {
128            let old = mesh.indices[triangle * 3 + corner];
129            let new = *remap.entry(old).or_insert_with(|| {
130                positions.push(mesh.positions[old as usize]);
131                (positions.len() - 1) as u32
132            });
133            indices.push(new);
134        }
135    }
136    TriMesh::new(positions, indices)
137}
138
139/// Combine meshes into one, rebasing each mesh's indices.
140///
141/// The inverse of [`decompose`] up to vertex ordering: positions are
142/// concatenated in argument order and never merged, so composing meshes
143/// that share a coordinate leaves them as separate components. Merging
144/// coincident vertices is `axiolid-heal`'s weld, deliberately not done here.
145pub fn compose(meshes: &[TriMesh]) -> TriMesh {
146    let mut positions = Vec::new();
147    let mut indices = Vec::new();
148    for mesh in meshes {
149        let base = positions.len() as u32;
150        positions.extend_from_slice(&mesh.positions);
151        indices.extend(mesh.indices.iter().map(|index| index + base));
152    }
153    TriMesh::new(positions, indices)
154}
axiolid_mesh/component.rs

axiolid_mesh/
component.rs
