conspire/geometry/mesh/quality/surface/
mod.rs

1#[cfg(test)]
2mod test;
3mod triangles;
4
5use crate::{
6    geometry::mesh::Mesh,
7    math::{FxHashMap, FxHashSet},
8};
9
10impl<const D: usize> Mesh<D> {
11    pub fn boundary_edges(&self) -> Vec<[usize; 2]> {
12        self.edge_incidence()
13            .into_values()
14            .filter_map(|(edge, count)| (count == 1).then_some(edge))
15            .collect()
16    }
17    pub fn boundary_loops(&self) -> Vec<Vec<usize>> {
18        let mut next: FxHashMap<usize, usize> = self
19            .boundary_edges()
20            .into_iter()
21            .map(|[a, b]| (a, b))
22            .collect();
23        let mut loops = Vec::new();
24        while let Some(&start) = next.keys().next() {
25            let mut nodes = vec![start];
26            let mut node = start;
27            while let Some(following) = next.remove(&node) {
28                if following == start {
29                    break;
30                }
31                nodes.push(following);
32                node = following;
33            }
34            loops.push(nodes);
35        }
36        loops
37    }
38    pub fn non_manifold_edges(&self) -> Vec<[usize; 2]> {
39        self.edge_incidence()
40            .into_values()
41            .filter_map(|(edge, count)| (count > 2).then_some(edge))
42            .collect()
43    }
44    pub fn non_manifold_seams(&self) -> Vec<Vec<[usize; 2]>> {
45        let edges = self.non_manifold_edges();
46        let mut incident = FxHashMap::<usize, Vec<usize>>::default();
47        for (e, &[a, b]) in edges.iter().enumerate() {
48            incident.entry(a).or_default().push(e);
49            incident.entry(b).or_default().push(e);
50        }
51        let mut visited = vec![false; edges.len()];
52        let mut seams = Vec::new();
53        for start in 0..edges.len() {
54            if visited[start] {
55                continue;
56            }
57            visited[start] = true;
58            let mut seam = Vec::new();
59            let mut stack = vec![start];
60            while let Some(e) = stack.pop() {
61                seam.push(edges[e]);
62                for node in edges[e] {
63                    incident[&node].iter().for_each(|&other| {
64                        if !visited[other] {
65                            visited[other] = true;
66                            stack.push(other);
67                        }
68                    });
69                }
70            }
71            seams.push(seam);
72        }
73        seams
74    }
75    pub fn non_manifold_vertices(&self) -> Vec<usize> {
76        let mut faces = Vec::new();
77        self.iter().for_each(|block| {
78            block
79                .iter()
80                .for_each(|element| faces.push(element.to_vec()))
81        });
82        let mut edge_faces = FxHashMap::<[usize; 2], Vec<usize>>::default();
83        let mut vertex_faces = FxHashMap::<usize, Vec<usize>>::default();
84        for (f, face) in faces.iter().enumerate() {
85            for (i, &v) in face.iter().enumerate() {
86                vertex_faces.entry(v).or_default().push(f);
87                let w = face[(i + 1) % face.len()];
88                edge_faces.entry(edge(v, w)).or_default().push(f);
89            }
90        }
91        let mut non_manifold = Vec::new();
92        for (&v, incident) in &vertex_faces {
93            let local: FxHashMap<usize, usize> =
94                incident.iter().enumerate().map(|(i, &f)| (f, i)).collect();
95            let mut parent: Vec<usize> = (0..incident.len()).collect();
96            for &f in incident {
97                let face = &faces[f];
98                let (len, pos) = (face.len(), face.iter().position(|&n| n == v).unwrap());
99                for x in [face[(pos + len - 1) % len], face[(pos + 1) % len]] {
100                    if let Some(shared) = edge_faces.get(&edge(v, x))
101                        && shared.len() == 2
102                    {
103                        union(&mut parent, local[&shared[0]], local[&shared[1]]);
104                    }
105                }
106            }
107            let fans: FxHashSet<usize> =
108                (0..incident.len()).map(|i| find(&mut parent, i)).collect();
109            if fans.len() > 1 {
110                non_manifold.push(v);
111            }
112        }
113        non_manifold
114    }
115    fn edge_incidence(&self) -> FxHashMap<[usize; 2], ([usize; 2], usize)> {
116        let mut edges = FxHashMap::default();
117        self.iter().for_each(|block| {
118            let local_edges = block.local_faces();
119            block.iter().for_each(|element| {
120                local_edges.iter().for_each(|edge| {
121                    let oriented = [element[edge[0]], element[edge[1]]];
122                    let key = if oriented[0] < oriented[1] {
123                        oriented
124                    } else {
125                        [oriented[1], oriented[0]]
126                    };
127                    edges
128                        .entry(key)
129                        .and_modify(|(_, count)| *count += 1)
130                        .or_insert((oriented, 1));
131                })
132            })
133        });
134        edges
135    }
136}
137
138fn edge(a: usize, b: usize) -> [usize; 2] {
139    if a < b { [a, b] } else { [b, a] }
140}
141
142fn find(parent: &mut [usize], i: usize) -> usize {
143    if parent[i] != i {
144        parent[i] = find(parent, parent[i]);
145    }
146    parent[i]
147}
148
149fn union(parent: &mut [usize], a: usize, b: usize) {
150    let (a, b) = (find(parent, a), find(parent, b));
151    parent[a] = b;
152}
conspire/geometry/mesh/quality/surface/mod.rs

conspire/geometry/mesh/quality/surface/
mod.rs
