threecrate_core/
mesh_analysis.rs

1//! Mesh health and measurement: is a mesh watertight and printable, and how
2//! big is it.
3
4use crate::{Point3f, TriangleMesh};
5use std::collections::{HashMap, VecDeque};
6
7/// Health and measurement report for a triangle mesh, from [`analyze_mesh`].
8#[derive(Debug, Clone, PartialEq)]
9pub struct MeshReport {
10    pub vertices: usize,
11    pub faces: usize,
12    /// Vertices no face uses.
13    pub unused_vertices: usize,
14    /// Faces with zero area (repeated or collinear corners).
15    pub degenerate_faces: usize,
16    /// Faces with an index past the vertex list; such faces are otherwise
17    /// ignored by this report.
18    pub invalid_faces: usize,
19    /// Distinct edges.
20    pub edges: usize,
21    /// Edges used by exactly one face: the rims of holes.
22    pub boundary_edges: usize,
23    /// Edges used by three or more faces.
24    pub non_manifold_edges: usize,
25    /// Edges used twice in the same direction: neighbouring faces wound
26    /// opposite ways.
27    pub inconsistent_edges: usize,
28    /// Number of edges around each hole (closed loop of boundary edges),
29    /// largest first.
30    pub holes: Vec<usize>,
31    /// Face count of each separate piece, largest first.
32    pub components: Vec<usize>,
33    /// No holes and no non-manifold edges.
34    pub watertight: bool,
35    /// Bounding box corners and size (all zero for an empty mesh).
36    pub min: Point3f,
37    pub max: Point3f,
38    pub size: [f32; 3],
39    /// Total area of all faces.
40    pub surface_area: f64,
41    /// Enclosed volume. Only defined for a watertight, consistently wound
42    /// mesh; `None` otherwise.
43    pub volume: Option<f64>,
44    /// Watertight, manifold, consistently wound and facing outward.
45    pub printable: bool,
46    /// Why the mesh is not printable, in plain words (empty when it is).
47    pub problems: Vec<String>,
48}
49
50/// Inspect `mesh`: topology problems (holes, non-manifold edges, flipped
51/// faces, separate pieces), size, area, volume, and whether it can be 3D
52/// printed as is.
53pub fn analyze_mesh(mesh: &TriangleMesh) -> MeshReport {
54    let n = mesh.vertices.len();
55    let valid: Vec<[usize; 3]> = mesh
56        .faces
57        .iter()
58        .copied()
59        .filter(|f| f.iter().all(|&v| v < n))
60        .collect();
61
62    // Directed uses of every undirected edge: (a, b) with a < b, counted as
63    // forward when the face runs a -> b.
64    let mut edge_uses: HashMap<(usize, usize), (u32, u32)> = HashMap::new();
65    let mut used = vec![false; n];
66    let mut degenerate = 0;
67    let mut area = 0.0f64;
68    let mut signed_volume = 0.0f64;
69    for f in &valid {
70        let [a, b, c] = f.map(|v| mesh.vertices[v].coords.cast::<f64>());
71        let cross = (b - a).cross(&(c - a));
72        let face_area = 0.5 * cross.norm();
73        if face_area <= f64::EPSILON * (b - a).norm().max((c - a).norm()).powi(2) {
74            degenerate += 1;
75        }
76        area += face_area;
77        signed_volume += a.dot(&b.cross(&c)) / 6.0;
78        f.iter().for_each(|&v| used[v] = true);
79        // A face with a repeated corner is not a triangle; keep it out of the
80        // edge topology so it doesn't make real edges look non-manifold.
81        if f[0] == f[1] || f[1] == f[2] || f[0] == f[2] {
82            continue;
83        }
84        for (u, v) in [(f[0], f[1]), (f[1], f[2]), (f[2], f[0])] {
85            let entry = edge_uses.entry((u.min(v), u.max(v))).or_default();
86            if u < v {
87                entry.0 += 1;
88            } else {
89                entry.1 += 1;
90            }
91        }
92    }
93
94    let mut boundary = 0;
95    let mut non_manifold = 0;
96    let mut inconsistent = 0;
97    // Boundary edges in face direction, for tracing holes.
98    let mut next: HashMap<usize, Vec<usize>> = HashMap::new();
99    for (&(a, b), &(forward, backward)) in &edge_uses {
100        match forward + backward {
101            1 => {
102                boundary += 1;
103                let (from, to) = if forward == 1 { (a, b) } else { (b, a) };
104                next.entry(from).or_default().push(to);
105            }
106            2 if forward != 1 => inconsistent += 1,
107            2 => {}
108            _ => non_manifold += 1,
109        }
110    }
111
112    // Walk boundary edges into closed loops, one per hole.
113    let mut holes = Vec::new();
114    let mut starts: Vec<usize> = next.keys().copied().collect();
115    starts.sort_unstable();
116    for start in starts {
117        while next.get(&start).is_some_and(|out| !out.is_empty()) {
118            let mut length = 0;
119            let mut at = start;
120            while let Some(to) = next.get_mut(&at).and_then(Vec::pop) {
121                length += 1;
122                at = to;
123                if at == start {
124                    break;
125                }
126            }
127            holes.push(length);
128        }
129    }
130    holes.sort_unstable_by(|a, b| b.cmp(a));
131
132    let mut components: Vec<usize> = mesh_pieces(&valid).iter().map(Vec::len).collect();
133    components.sort_unstable_by(|a, b| b.cmp(a));
134
135    let (min, max) = bounds(mesh, &used);
136    let size = [max.x - min.x, max.y - min.y, max.z - min.z];
137
138    let watertight = !valid.is_empty() && boundary == 0 && non_manifold == 0;
139    let oriented = inconsistent == 0;
140    let volume = (watertight && oriented).then_some(signed_volume.abs());
141
142    let mut problems = Vec::new();
143    if valid.is_empty() {
144        problems.push("the mesh has no faces".to_string());
145    }
146    if !holes.is_empty() {
147        problems.push(format!(
148            "{} hole(s) in the surface ({} open edges)",
149            holes.len(),
150            boundary
151        ));
152    }
153    if non_manifold > 0 {
154        problems.push(format!(
155            "{non_manifold} edge(s) shared by more than two faces"
156        ));
157    }
158    if !oriented {
159        problems.push(format!(
160            "{inconsistent} edge(s) between faces that face opposite ways"
161        ));
162    } else if watertight && signed_volume < 0.0 {
163        problems.push("all faces point inward (the mesh is inside out)".to_string());
164    }
165    if mesh.faces.len() != valid.len() {
166        problems.push(format!(
167            "{} face(s) use vertex indices past the vertex list",
168            mesh.faces.len() - valid.len()
169        ));
170    }
171
172    MeshReport {
173        vertices: n,
174        faces: mesh.faces.len(),
175        unused_vertices: used.iter().filter(|&&u| !u).count(),
176        degenerate_faces: degenerate,
177        invalid_faces: mesh.faces.len() - valid.len(),
178        edges: edge_uses.len(),
179        boundary_edges: boundary,
180        non_manifold_edges: non_manifold,
181        inconsistent_edges: inconsistent,
182        holes,
183        components,
184        watertight,
185        min,
186        max,
187        size,
188        surface_area: area,
189        volume,
190        printable: problems.is_empty(),
191        problems,
192    }
193}
194
195/// Faces grouped into pieces connected through shared edges, as face indices.
196/// Faces must index real vertices. `analyze_mesh` and `repair_for_print` use
197/// this one definition of a piece, so their counts agree.
198pub fn mesh_pieces(faces: &[[usize; 3]]) -> Vec<Vec<usize>> {
199    let mut by_edge: HashMap<(usize, usize), Vec<usize>> = HashMap::new();
200    for (i, f) in faces.iter().enumerate() {
201        for (a, b) in [(f[0], f[1]), (f[1], f[2]), (f[2], f[0])] {
202            by_edge.entry((a.min(b), a.max(b))).or_default().push(i);
203        }
204    }
205    let mut piece_of = vec![usize::MAX; faces.len()];
206    let mut out: Vec<Vec<usize>> = Vec::new();
207    for start in 0..faces.len() {
208        if piece_of[start] != usize::MAX {
209            continue;
210        }
211        let id = out.len();
212        let mut members = vec![start];
213        piece_of[start] = id;
214        let mut queue = VecDeque::from([start]);
215        while let Some(f) = queue.pop_front() {
216            let face = faces[f];
217            for (a, b) in [(face[0], face[1]), (face[1], face[2]), (face[2], face[0])] {
218                for &g in &by_edge[&(a.min(b), a.max(b))] {
219                    if piece_of[g] == usize::MAX {
220                        piece_of[g] = id;
221                        members.push(g);
222                        queue.push_back(g);
223                    }
224                }
225            }
226        }
227        out.push(members);
228    }
229    out
230}
231
232/// Bounding box of the vertices faces use (all zero when there are none).
233fn bounds(mesh: &TriangleMesh, used: &[bool]) -> (Point3f, Point3f) {
234    let mut points = mesh
235        .vertices
236        .iter()
237        .zip(used)
238        .filter(|(p, &u)| u && p.coords.iter().all(|c| c.is_finite()))
239        .map(|(p, _)| *p);
240    let Some(first) = points.next() else {
241        return (Point3f::origin(), Point3f::origin());
242    };
243    points.fold((first, first), |(lo, hi), p| {
244        (
245            Point3f::new(lo.x.min(p.x), lo.y.min(p.y), lo.z.min(p.z)),
246            Point3f::new(hi.x.max(p.x), hi.y.max(p.y), hi.z.max(p.z)),
247        )
248    })
249}
250
251#[cfg(test)]
252mod tests {
253    use super::*;
254
255    /// Unit cube, 12 triangles, wound so normals point outward.
256    fn cube() -> TriangleMesh {
257        let v = (0..8)
258            .map(|i| Point3f::new((i & 1) as f32, ((i >> 1) & 1) as f32, ((i >> 2) & 1) as f32))
259            .collect();
260        let faces = vec![
261            [0, 2, 1],
262            [1, 2, 3], // z = 0, facing -z
263            [4, 5, 6],
264            [5, 7, 6], // z = 1, facing +z
265            [0, 1, 4],
266            [1, 5, 4], // y = 0
267            [2, 6, 3],
268            [3, 6, 7], // y = 1
269            [0, 4, 2],
270            [2, 4, 6], // x = 0
271            [1, 3, 5],
272            [3, 7, 5], // x = 1
273        ];
274        TriangleMesh::from_vertices_and_faces(v, faces)
275    }
276
277    #[test]
278    fn closed_cube_is_printable_with_exact_measurements() {
279        let r = analyze_mesh(&cube());
280        assert!(r.watertight && r.printable, "{:?}", r.problems);
281        assert_eq!(
282            (r.edges, r.boundary_edges, r.non_manifold_edges),
283            (18, 0, 0)
284        );
285        assert!(r.holes.is_empty());
286        assert_eq!(r.components, vec![12]);
287        assert!((r.surface_area - 6.0).abs() < 1e-9);
288        assert!((r.volume.unwrap() - 1.0).abs() < 1e-9);
289        assert_eq!(r.size, [1.0, 1.0, 1.0]);
290    }
291
292    #[test]
293    fn missing_faces_are_reported_as_one_hole() {
294        let mut mesh = cube();
295        mesh.faces.truncate(10); // drop the x = 1 side: one square hole
296        let r = analyze_mesh(&mesh);
297        assert!(!r.watertight && !r.printable);
298        assert_eq!(r.holes, vec![4]);
299        assert_eq!(r.volume, None);
300        assert!(r.problems[0].contains("1 hole"), "{:?}", r.problems);
301    }
302
303    #[test]
304    fn inside_out_and_flipped_faces_are_caught() {
305        let mut inside_out = cube();
306        for f in inside_out.faces.iter_mut() {
307            f.swap(1, 2);
308        }
309        let r = analyze_mesh(&inside_out);
310        assert!(r.watertight && !r.printable);
311        assert!(
312            (r.volume.unwrap() - 1.0).abs() < 1e-9,
313            "volume is still the size"
314        );
315        assert!(r.problems.iter().any(|p| p.contains("inside out")));
316
317        let mut one_flipped = cube();
318        one_flipped.faces[0].swap(1, 2);
319        let r = analyze_mesh(&one_flipped);
320        assert_eq!(r.inconsistent_edges, 3);
321        assert_eq!(r.volume, None);
322        assert!(!r.printable);
323    }
324
325    #[test]
326    fn non_manifold_pieces_degenerate_and_bad_indices_are_counted() {
327        let mut mesh = cube();
328        // A fin on an existing edge (0-1), a separate floating triangle, a
329        // zero-area face and a face pointing past the vertex list.
330        mesh.vertices.extend([
331            Point3f::new(0.5, -1.0, 0.0),
332            Point3f::new(5.0, 5.0, 5.0),
333            Point3f::new(6.0, 5.0, 5.0),
334            Point3f::new(5.0, 6.0, 5.0),
335            Point3f::new(9.0, 9.0, 9.0), // unused
336        ]);
337        mesh.faces
338            .extend([[0, 1, 8], [9, 10, 11], [9, 9, 10], [0, 1, 99]]);
339        let r = analyze_mesh(&mesh);
340        assert_eq!(r.non_manifold_edges, 1);
341        assert_eq!(r.components, vec![13, 2]);
342        assert_eq!(r.degenerate_faces, 1);
343        assert_eq!(r.invalid_faces, 1);
344        assert_eq!(r.unused_vertices, 1);
345        assert!(!r.watertight && !r.printable);
346    }
347
348    #[test]
349    fn empty_mesh_is_not_printable() {
350        let r = analyze_mesh(&TriangleMesh::new());
351        assert!(!r.printable && !r.watertight);
352        assert_eq!(r.volume, None);
353        assert_eq!(r.size, [0.0, 0.0, 0.0]);
354    }
355
356    #[test]
357    fn faces_touching_at_one_corner_are_separate_pieces() {
358        // Two triangles share only vertex 0: two pieces, the same as repair sees.
359        let v = vec![
360            Point3f::new(0.0, 0.0, 0.0),
361            Point3f::new(1.0, 0.0, 0.0),
362            Point3f::new(0.0, 1.0, 0.0),
363            Point3f::new(-1.0, 0.0, 0.0),
364            Point3f::new(0.0, -1.0, 0.0),
365        ];
366        let mesh = TriangleMesh::from_vertices_and_faces(v, vec![[0, 1, 2], [0, 3, 4]]);
367        assert_eq!(analyze_mesh(&mesh).components, vec![1, 1]);
368        assert_eq!(mesh_pieces(&mesh.faces), vec![vec![0], vec![1]]);
369    }
370}
threecrate_core/mesh_analysis.rs

threecrate_core/
mesh_analysis.rs
