fast_mesh_ops/
analyze.rs

1//! A read-only report of what is wrong with a mesh.
2
3use std::fmt;
4
5use fast_mesh_bvh::Bvh;
6use fast_mesh_store::{Mesh, TriangleId, VertexId, par};
7
8use fast_mesh_query::self_intersects;
9
10use crate::topology::{
11    BoundaryLoop, Component, EdgeMap, components, loops_with, pinch_vertices, point, triangle_area,
12};
13use crate::weld::{check_tolerance, weld_roots};
14use crate::{Result, filled, push, reserve};
15
16/// Options for [`analyze`].
17#[derive(Clone, Copy)]
18pub struct AnalyzeOptions<'a> {
19    /// Vertices at most this far apart (local units) count as coincident.
20    /// 0, the default, counts exact duplicates only.
21    pub weld_tolerance: f32,
22    /// A BVH of the mesh, to check for self-intersection; `None`, the
23    /// default, skips the check.
24    pub self_intersection: Option<&'a Bvh>,
25    /// The most entries kept in each list that has a count beside it; the
26    /// counts are always exact. Default 1000.
27    pub max_listed: usize,
28}
29
30impl Default for AnalyzeOptions<'_> {
31    fn default() -> Self {
32        AnalyzeOptions {
33            weld_tolerance: 0.0,
34            self_intersection: None,
35            max_listed: 1000,
36        }
37    }
38}
39
40impl fmt::Debug for AnalyzeOptions<'_> {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        f.debug_struct("AnalyzeOptions")
43            .field("weld_tolerance", &self.weld_tolerance)
44            .field("self_intersection", &self.self_intersection.map(|_| "Bvh"))
45            .field("max_listed", &self.max_listed)
46            .finish()
47    }
48}
49
50impl<'a> AnalyzeOptions<'a> {
51    /// A builder for [`AnalyzeOptions`]: every option unset, as [`Default`],
52    /// until set.
53    pub fn builder() -> AnalyzeOptionsBuilder<'a> {
54        AnalyzeOptionsBuilder::default()
55    }
56}
57
58/// A builder for [`AnalyzeOptions`], see [`AnalyzeOptions::builder`].
59#[derive(Debug, Clone, Default)]
60pub struct AnalyzeOptionsBuilder<'a> {
61    options: AnalyzeOptions<'a>,
62}
63
64impl<'a> AnalyzeOptionsBuilder<'a> {
65    /// Vertices at most this far apart count as coincident.
66    pub fn weld_tolerance(mut self, weld_tolerance: f32) -> Self {
67        self.options.weld_tolerance = weld_tolerance;
68        self
69    }
70
71    /// Check for self-intersection with this BVH of the mesh.
72    pub fn self_intersection(mut self, self_intersection: &'a Bvh) -> Self {
73        self.options.self_intersection = Some(self_intersection);
74        self
75    }
76
77    /// The most entries kept in each list that has a count beside it.
78    pub fn max_listed(mut self, max_listed: usize) -> Self {
79        self.options.max_listed = max_listed;
80        self
81    }
82
83    /// The options as set.
84    pub fn build(self) -> AnalyzeOptions<'a> {
85        self.options
86    }
87}
88
89/// What [`analyze`] found.
90#[derive(Debug, Clone, PartialEq)]
91pub struct Analysis {
92    /// The boundary loops, as [`boundary_loops`](crate::boundary_loops)
93    /// returns them.
94    pub loops: Vec<BoundaryLoop>,
95    /// How many groups of two or more coincident vertices there are.
96    pub coincident_groups: usize,
97    /// The groups, by smallest id, each ascending.
98    pub coincident: Vec<Vec<VertexId>>,
99    /// How many triangles are degenerate.
100    pub degenerate: usize,
101    /// The degenerate triangles, ascending.
102    pub degenerate_list: Vec<TriangleId>,
103    /// How many triangles repeat the vertex set of a triangle with a smaller id.
104    pub duplicate: usize,
105    /// Those triangles, ascending.
106    pub duplicate_list: Vec<TriangleId>,
107    /// How many edges have three or more triangles.
108    pub non_manifold_edges: usize,
109    /// Those edges as `(min, max)`, ascending.
110    pub non_manifold_edge_list: Vec<(VertexId, VertexId)>,
111    /// The vertices on non-manifold edges, ascending.
112    pub non_manifold_vertices: Vec<VertexId>,
113    /// The vertices whose triangle fan splits into several pieces, ascending.
114    pub pinch_vertices: Vec<VertexId>,
115    /// The connected components, by smallest triangle id.
116    pub components: Vec<Component>,
117    /// How many interior edges are used in the same direction by both their
118    /// triangles.
119    pub orientation_conflicts: usize,
120    /// Whether two triangles that share no vertex intersect; `None` when no
121    /// BVH was given.
122    pub self_intersects: Option<bool>,
123}
124
125/// A triangle is degenerate by area when its area is at most this times its
126/// longest edge squared (the default of `remove_degenerate`).
127pub(crate) const AREA_EPSILON: f64 = 1e-12;
128
129/// [`analyze`] runs its passes side by side from this many triangles, with
130/// the `parallel` feature.
131///
132/// Measured on the i5-13600K on terrains (no defects, no BVH): at 512
133/// triangles parallel is 1.1 to 1.2 times slower, at 1,152 1.1 to 1.3 times
134/// faster, and from 4k on steadily 1.25 times (the edge map's sort, which
135/// the other passes wait for, stays sequential).
136pub(crate) const PAR_MIN_ANALYZE_TRIS: usize = 2048;
137
138/// Reports the defects of `mesh` without changing it.
139///
140/// - Loops, components, edge kinds, pinch vertices and orientation conflicts
141///   are computed from the triangles with three distinct vertex ids; the
142///   others are skipped there, as everywhere in this crate.
143/// - Coincident vertices: groups of alive vertices linked through pairs at
144///   most `weld_tolerance` apart, as a weld would merge them.
145/// - Degenerate triangles: a repeated vertex id, or an area of at most
146///   `1e-12` times the longest edge squared.
147/// - Duplicate triangles: every alive triangle but the smallest id of each
148///   set of triangles on the same three vertex ids, in any order or winding.
149/// - Non-manifold vertices are the ends of non-manifold edges. Pinch
150///   vertices, whose fan splits into pieces (the corner where two holes
151///   touch), are listed apart.
152/// - Orientation conflicts: interior edges whose two triangles both run
153///   along them in the same direction.
154/// - Self-intersection ([`self_intersects`](fast_mesh_query::self_intersects)):
155///   two alive triangles that share no vertex id, neither degenerate,
156///   intersect or touch. Pairs sharing a vertex are not tested.
157///
158/// The lists with a count beside them (`coincident`, `degenerate_list`,
159/// `duplicate_list` and `non_manifold_edge_list`) keep their first
160/// `options.max_listed` entries; the counts and the other lists are complete.
161///
162/// # Errors
163/// [`OpsError::InvalidInput`] when `weld_tolerance` is negative, NaN or
164/// infinite; [`OpsError::Query`] when the BVH does not match the mesh; and
165/// [`OpsError::Store`] with [`StoreError::OutOfMemory`] when a temporary
166/// cannot grow.
167///
168/// [`StoreError::OutOfMemory`]: fast_mesh_store::StoreError::OutOfMemory
169/// [`OpsError::InvalidInput`]: crate::OpsError::InvalidInput
170/// [`OpsError::Query`]: crate::OpsError::Query
171/// [`OpsError::Store`]: crate::OpsError::Store
172pub fn analyze(mesh: &Mesh, options: &AnalyzeOptions) -> Result<Analysis> {
173    let max = options.max_listed;
174    // Checked first, so a bad tolerance fails before any pass runs.
175    check_tolerance(options.weld_tolerance)?;
176    // The four passes read the mesh only; on large meshes they run side by
177    // side. Their errors are returned in pass order, so the first error is
178    // the same however they ran.
179    let parallel = mesh.triangle_count() >= PAR_MIN_ANALYZE_TRIS;
180    let ((coincident, topology), (scans, self_intersects)) = par::join(
181        parallel,
182        || {
183            par::join(
184                parallel,
185                || groups(&weld_roots(mesh, options.weld_tolerance)?, max),
186                || topology_pass(mesh, max, parallel),
187            )
188        },
189        || {
190            par::join(
191                parallel,
192                || scan_pass(mesh, max),
193                || self_intersection_pass(mesh, options.self_intersection),
194            )
195        },
196    );
197    let (coincident_groups, coincident) = coincident?;
198    let topology = topology?;
199    let (degenerate, degenerate_list, duplicate, duplicate_list) = scans?;
200    let self_intersects = self_intersects?;
201
202    Ok(Analysis {
203        loops: topology.loops,
204        coincident_groups,
205        coincident,
206        degenerate,
207        degenerate_list,
208        duplicate,
209        duplicate_list,
210        non_manifold_edges: topology.non_manifold_edges,
211        non_manifold_edge_list: topology.non_manifold_edge_list,
212        non_manifold_vertices: topology.non_manifold_vertices,
213        pinch_vertices: topology.pinch_vertices,
214        components: topology.components,
215        orientation_conflicts: topology.orientation_conflicts,
216        self_intersects,
217    })
218}
219
220/// What [`analyze`] reads from the edge map.
221struct Topology {
222    loops: Vec<BoundaryLoop>,
223    non_manifold_edges: usize,
224    non_manifold_edge_list: Vec<(VertexId, VertexId)>,
225    non_manifold_vertices: Vec<VertexId>,
226    pinch_vertices: Vec<VertexId>,
227    components: Vec<Component>,
228    orientation_conflicts: usize,
229}
230
231/// The edge map and everything [`analyze`] reads from it: the loops, the
232/// components and the rest side by side when `parallel`, errors in that
233/// order.
234fn topology_pass(mesh: &Mesh, max: usize, parallel: bool) -> Result<Topology> {
235    let edges = EdgeMap::build(mesh)?;
236    let (loops, (components, rest)) = par::join(
237        parallel,
238        || loops_with(mesh, &edges),
239        || {
240            par::join(
241                parallel,
242                || components(mesh, &edges),
243                || edge_kinds(mesh, &edges, max),
244            )
245        },
246    );
247    let (loops, components) = (loops?, components?);
248    let (pinch_vertices, non_manifold, orientation_conflicts) = rest?;
249    let (non_manifold_edges, non_manifold_edge_list, non_manifold_vertices) = non_manifold;
250    Ok(Topology {
251        loops,
252        non_manifold_edges,
253        non_manifold_edge_list,
254        non_manifold_vertices,
255        pinch_vertices,
256        components,
257        orientation_conflicts,
258    })
259}
260
261/// The non-manifold edge count, edge list and vertices.
262type NonManifold = (usize, Vec<(VertexId, VertexId)>, Vec<VertexId>);
263
264/// The pinch vertices, the non-manifold edges and vertices, and the
265/// orientation conflicts.
266fn edge_kinds(
267    mesh: &Mesh,
268    edges: &EdgeMap,
269    max: usize,
270) -> Result<(Vec<VertexId>, NonManifold, usize)> {
271    let pinch_vertices = pinch_vertices(mesh, edges)?;
272    let mut non_manifold_edges = 0;
273    let mut non_manifold_edge_list = Vec::new();
274    let mut on_non_manifold = filled(mesh.vertex_slots(), false)?;
275    let mut orientation_conflicts = 0;
276    for ((a, b), tris) in edges.edges() {
277        match *tris {
278            [_] => {}
279            [s, t] => {
280                if runs_forward(mesh, s, a, b) == runs_forward(mesh, t, a, b) {
281                    orientation_conflicts += 1;
282                }
283            }
284            _ => {
285                non_manifold_edges += 1;
286                if non_manifold_edge_list.len() < max {
287                    push(&mut non_manifold_edge_list, (a, b))?;
288                }
289                on_non_manifold[a as usize] = true;
290                on_non_manifold[b as usize] = true;
291            }
292        }
293    }
294    let mut non_manifold_vertices = Vec::new();
295    for (v, &on) in on_non_manifold.iter().enumerate() {
296        if on {
297            push(&mut non_manifold_vertices, v as VertexId)?;
298        }
299    }
300    let non_manifold = (
301        non_manifold_edges,
302        non_manifold_edge_list,
303        non_manifold_vertices,
304    );
305    Ok((pinch_vertices, non_manifold, orientation_conflicts))
306}
307
308/// The degenerate count and list, then the duplicate count and list.
309type Scans = (usize, Vec<TriangleId>, usize, Vec<TriangleId>);
310
311/// The degenerate and duplicate triangle scans of [`analyze`].
312fn scan_pass(mesh: &Mesh, max: usize) -> Result<Scans> {
313    let mut degenerate = 0;
314    let mut degenerate_list = Vec::new();
315    for t in 0..mesh.triangle_slots() as TriangleId {
316        let Some(tri) = mesh.triangle(t) else {
317            continue;
318        };
319        if is_degenerate(mesh, tri, AREA_EPSILON) {
320            degenerate += 1;
321            if degenerate_list.len() < max {
322                push(&mut degenerate_list, t)?;
323            }
324        }
325    }
326    let mut duplicate_list = duplicate_triangles(mesh)?;
327    let duplicate = duplicate_list.len();
328    duplicate_list.truncate(max);
329    Ok((degenerate, degenerate_list, duplicate, duplicate_list))
330}
331
332/// Whether two triangles of `mesh` intersect, given a BVH.
333fn self_intersection_pass(mesh: &Mesh, bvh: Option<&Bvh>) -> Result<Option<bool>> {
334    let Some(bvh) = bvh else {
335        return Ok(None);
336    };
337    Ok(Some(self_intersects(mesh, bvh)?))
338}
339
340/// The alive triangles that repeat the vertex set of a triangle with a smaller
341/// id, ascending.
342pub(crate) fn duplicate_triangles(mesh: &Mesh) -> Result<Vec<TriangleId>> {
343    // Each alive triangle's sorted vertex ids, then its id: sorting brings
344    // each set together, smallest id first.
345    let mut sets: Vec<([VertexId; 3], TriangleId)> = Vec::new();
346    reserve(&mut sets, mesh.triangle_count())?;
347    for t in 0..mesh.triangle_slots() as TriangleId {
348        if let Some(mut key) = mesh.triangle(t) {
349            key.sort_unstable();
350            push(&mut sets, (key, t))?;
351        }
352    }
353    sets.sort_unstable();
354    let mut out = Vec::new();
355    for w in sets.windows(2) {
356        if w[0].0 == w[1].0 {
357            push(&mut out, w[1].1)?;
358        }
359    }
360    out.sort_unstable();
361    Ok(out)
362}
363
364/// Whether triangle `t` runs along its edge `a`-`b` from `a` to `b`.
365fn runs_forward(mesh: &Mesh, t: TriangleId, a: VertexId, b: VertexId) -> bool {
366    let [x, y, z] = mesh.triangles()[t as usize];
367    (x, y) == (a, b) || (y, z) == (a, b) || (z, x) == (a, b)
368}
369
370/// A repeated vertex id, or an area of at most `area_epsilon` times the
371/// longest edge squared.
372pub(crate) fn is_degenerate(mesh: &Mesh, [a, b, c]: [VertexId; 3], area_epsilon: f64) -> bool {
373    if a == b || b == c || a == c {
374        return true;
375    }
376    let [p, q, r] = [a, b, c].map(|v| point(mesh, v));
377    let d2 = |u: [f64; 3], v: [f64; 3]| (0..3).map(|k| (u[k] - v[k]).powi(2)).sum::<f64>();
378    let longest = d2(p, q).max(d2(q, r)).max(d2(r, p));
379    triangle_area(mesh, [a, b, c]) <= area_epsilon * longest
380}
381
382/// Marks a vertex whose group is not numbered yet, in [`groups`].
383const UNNUMBERED: usize = usize::MAX;
384
385/// The number of weld groups of two or more vertices, and the first `max` of
386/// them by smallest id, each ascending. `roots[v]` is the smallest id of
387/// `v`'s group.
388fn groups(roots: &[VertexId], max: usize) -> Result<(usize, Vec<Vec<VertexId>>)> {
389    // A group's root is its smallest member, so visiting ids in order meets
390    // each group at its second-smallest member first, after its root.
391    let mut index = filled(roots.len(), UNNUMBERED)?;
392    let mut count = 0;
393    let mut out: Vec<Vec<VertexId>> = Vec::new();
394    for (v, &r) in roots.iter().enumerate() {
395        let r = r as usize;
396        if r == v {
397            continue;
398        }
399        if index[r] == UNNUMBERED {
400            index[r] = count;
401            count += 1;
402            if out.len() < max {
403                let mut group = Vec::new();
404                push(&mut group, r as VertexId)?;
405                push(&mut out, group)?;
406            }
407        }
408        if let Some(group) = out.get_mut(index[r]) {
409            push(group, v as VertexId)?;
410        }
411    }
412    Ok((count, out))
413}
414
415#[cfg(test)]
416mod tests {
417    use fast_mesh_bvh::BuildOptions;
418    use fast_mesh_store::StoreError;
419
420    use super::*;
421    use crate::test_util::*;
422    use crate::{OpsError, fail_allocations_after};
423
424    fn run(mesh: &Mesh) -> Analysis {
425        analyze(mesh, &AnalyzeOptions::default()).unwrap()
426    }
427
428    #[test]
429    fn builder_matches_literal() {
430        let mesh = uv_sphere(8, 12, 1.0);
431        let bvh = Bvh::build(&mesh, &BuildOptions::default()).unwrap();
432        let got = AnalyzeOptions::builder()
433            .weld_tolerance(0.5)
434            .self_intersection(&bvh)
435            .max_listed(10)
436            .build();
437        assert_eq!(got.weld_tolerance, 0.5);
438        assert!(got.self_intersection.is_some());
439        assert_eq!(got.max_listed, 10);
440        let default = AnalyzeOptions::builder().build();
441        assert_eq!(default.weld_tolerance, 0.0);
442        assert!(default.self_intersection.is_none());
443        assert_eq!(default.max_listed, 1000);
444    }
445
446    #[test]
447    fn analyze_counts_on_damaged_fixture() {
448        let mesh = damaged_sphere();
449        assert_eq!(mesh.triangle_count(), 170);
450        assert_eq!(mesh.vertex_count(), 94);
451        let a = run(&mesh);
452
453        // 3 holes, 4 slits and the square's border.
454        let mut lens: Vec<usize> = a.loops.iter().map(|l| l.vertices.len()).collect();
455        lens.sort_unstable();
456        assert_eq!(lens, [3, 3, 3, 4, 4, 4, 4, 4]);
457        assert!(a.loops.iter().all(|l| l.clean && l.closed));
458        let seqs: Vec<&[VertexId]> = a.loops.iter().map(|l| l.vertices.as_slice()).collect();
459        // The hole of quad (1, 0), triangle [1, 13, 14], walked against it.
460        assert!(seqs.contains(&&[1, 14, 13][..]));
461        // The slit at vertex 10: triangle [10, 22, 23] now uses copy 86.
462        assert!(seqs.contains(&&[10, 23, 86, 22][..]));
463        assert!(seqs.contains(&&[90, 91, 92, 93][..]));
464
465        assert_eq!(a.coincident_groups, 4);
466        assert_eq!(a.coincident, [[10, 86], [25, 87], [31, 88], [52, 89]]);
467        assert_eq!(a.degenerate, 2);
468        assert_eq!(a.degenerate_list, [166, 167]);
469        assert_eq!(a.duplicate, 1);
470        assert_eq!(a.duplicate_list, [165]);
471        assert_eq!(a.non_manifold_edges, 3);
472        assert_eq!(a.non_manifold_edge_list, [(77, 78), (77, 85), (78, 85)]);
473        assert_eq!(a.non_manifold_vertices, [77, 78, 85]);
474        assert!(a.pinch_vertices.is_empty());
475        // The sphere with the copy (165 triangles plus one), and the square.
476        assert_eq!(a.components.len(), 2);
477        assert_eq!(a.components[0].triangles, (0..166).collect::<Vec<_>>());
478        assert_eq!(a.components[1].triangles, [168, 169]);
479        assert!(a.components.iter().all(|c| !c.closed));
480        assert!((a.components[1].area - 1.0).abs() < 1e-12);
481        // 5 flips, each against its 3 neighbours.
482        assert_eq!(a.orientation_conflicts, 15);
483        assert_eq!(a.self_intersects, None);
484    }
485
486    #[test]
487    fn analyze_clean_sphere_reports_nothing() {
488        let a = run(&uv_sphere(8, 12, 1.0));
489        assert!(a.loops.is_empty());
490        assert_eq!((a.coincident_groups, a.degenerate, a.duplicate), (0, 0, 0));
491        assert_eq!((a.non_manifold_edges, a.orientation_conflicts), (0, 0));
492        assert!(a.non_manifold_vertices.is_empty() && a.pinch_vertices.is_empty());
493        assert_eq!(a.components.len(), 1);
494        assert!(a.components[0].closed);
495    }
496
497    #[test]
498    fn analyze_bowtie_reports_pinch_and_two_clean_holes() {
499        let a = run(&bowtie_holes());
500        assert_eq!(a.pinch_vertices, [12]);
501        assert!(a.non_manifold_vertices.is_empty());
502        assert_eq!(a.non_manifold_edges, 0);
503        let seqs: Vec<&[VertexId]> = a.loops.iter().map(|l| l.vertices.as_slice()).collect();
504        assert_eq!(seqs.len(), 3);
505        assert_eq!(&seqs[1..], [&[6, 11, 12, 7][..], &[12, 17, 18, 13][..]]);
506        assert!(a.loops.iter().all(|l| l.clean && l.closed));
507        assert_eq!(a.components.len(), 1);
508        assert_eq!(a.orientation_conflicts, 0);
509    }
510
511    #[test]
512    fn analyze_fin_reports_non_manifold_vertices_not_pinches() {
513        let a = run(&fin());
514        assert_eq!(a.non_manifold_edges, 1);
515        assert_eq!(a.non_manifold_edge_list, [(0, 1)]);
516        assert_eq!(a.non_manifold_vertices, [0, 1]);
517        assert!(a.pinch_vertices.is_empty());
518        assert!(a.loops.iter().all(|l| !l.clean));
519    }
520
521    #[test]
522    fn analyze_does_not_modify() {
523        let mesh = damaged_sphere();
524        let bvh = Bvh::build(&mesh, &BuildOptions::default()).unwrap();
525        let (revision, before) = (mesh.revision(), parts(&mesh));
526        let options = AnalyzeOptions {
527            self_intersection: Some(&bvh),
528            ..Default::default()
529        };
530        let first = analyze(&mesh, &options).unwrap();
531        assert_eq!(mesh.revision(), revision);
532        assert_eq!(parts(&mesh), before);
533        assert_eq!(analyze(&mesh, &options).unwrap(), first);
534    }
535
536    #[test]
537    fn analyze_self_intersection_flag() {
538        let boxes = crossed_boxes();
539        let sphere = uv_sphere(8, 12, 1.0);
540        for (mesh, want) in [(&boxes, true), (&sphere, false)] {
541            let bvh = Bvh::build(mesh, &BuildOptions::default()).unwrap();
542            let options = AnalyzeOptions {
543                self_intersection: Some(&bvh),
544                ..Default::default()
545            };
546            assert_eq!(analyze(mesh, &options).unwrap().self_intersects, Some(want));
547            assert_eq!(run(mesh).self_intersects, None);
548        }
549        // A BVH of another mesh is the query's error.
550        let bvh = Bvh::build(&sphere, &BuildOptions::default()).unwrap();
551        let options = AnalyzeOptions {
552            self_intersection: Some(&bvh),
553            ..Default::default()
554        };
555        assert_eq!(
556            analyze(&boxes, &options),
557            Err(OpsError::Query(fast_mesh_query::QueryError::MeshMismatch))
558        );
559    }
560
561    #[test]
562    fn analyze_degenerate_by_area_and_duplicates_in_any_order() {
563        // The unit square's triangle [0, 1, 2], its reversed copy, a sliver
564        // through the midpoint 4 of edge 0-1 (exact in f32), a needle far
565        // below the area threshold, and a repeated id.
566        let positions = [
567            0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.5, 0.0, 0.0, 0.5, 1e-7,
568            0.0,
569        ];
570        let tris = [
571            [0, 1, 2],
572            [0, 2, 3],
573            [2, 1, 0], // duplicate of 0, reversed
574            [0, 4, 1], // collinear
575            [0, 5, 1], // area 5e-8 against L^2 = 1: kept
576            [3, 3, 2], // repeated id
577            [1, 2, 0], // duplicate of 0, rotated
578        ];
579        let indices: Vec<u32> = tris.iter().flatten().copied().collect();
580        let mesh = Mesh::from_buffers(&positions, &indices).unwrap();
581        let a = run(&mesh);
582        assert_eq!(a.degenerate_list, [3, 5]);
583        assert_eq!(a.duplicate_list, [2, 6]);
584        assert_eq!((a.degenerate, a.duplicate), (2, 2));
585    }
586
587    #[test]
588    fn analyze_coincident_with_tolerance() {
589        // Vertices 0 to 3 on the x axis at 0, 0.1, 0.2 and 0.5; 4 at 0 too.
590        let positions = [
591            0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.2, 0.0, 0.0, 0.5, 0.0, 0.0, -0.0, 0.0, 0.0, 0.0, 1.0,
592            0.0,
593        ];
594        let indices = [0, 1, 5, 1, 2, 5, 2, 3, 5, 3, 4, 5];
595        let mesh = Mesh::from_buffers(&positions, &indices).unwrap();
596        let with = |weld_tolerance| {
597            let options = AnalyzeOptions {
598                weld_tolerance,
599                ..Default::default()
600            };
601            analyze(&mesh, &options).unwrap().coincident
602        };
603        assert_eq!(with(0.0), [vec![0, 4]]);
604        // Chained: 0-1 and 1-2 are within 0.15, 0-2 is not.
605        assert_eq!(with(0.15), [vec![0, 1, 2, 4]]);
606        assert_eq!(with(0.05), [vec![0, 4]]);
607        assert_eq!(with(1.5), [vec![0, 1, 2, 3, 4, 5]]);
608        for bad in [-1.0, f32::NAN, f32::INFINITY] {
609            let options = AnalyzeOptions {
610                weld_tolerance: bad,
611                ..Default::default()
612            };
613            assert!(matches!(
614                analyze(&mesh, &options),
615                Err(OpsError::InvalidInput(_))
616            ));
617        }
618    }
619
620    #[test]
621    fn analyze_truncates_lists_but_not_counts() {
622        let mesh = damaged_sphere();
623        let options = AnalyzeOptions {
624            max_listed: 1,
625            ..Default::default()
626        };
627        let a = analyze(&mesh, &options).unwrap();
628        assert_eq!((a.coincident_groups, a.coincident), (4, vec![vec![10, 86]]));
629        assert_eq!((a.degenerate, a.degenerate_list), (2, vec![166]));
630        assert_eq!((a.duplicate, a.duplicate_list), (1, vec![165]));
631        assert_eq!(
632            (a.non_manifold_edges, a.non_manifold_edge_list),
633            (3, vec![(77, 78)])
634        );
635        assert_eq!(a.non_manifold_vertices.len(), 3);
636        assert_eq!(a.loops.len(), 8);
637        let none = AnalyzeOptions {
638            max_listed: 0,
639            ..Default::default()
640        };
641        let a = analyze(&mesh, &none).unwrap();
642        assert_eq!((a.degenerate, a.degenerate_list.len()), (2, 0));
643    }
644
645    /// A damaged mesh of over [`PAR_MIN_ANALYZE_TRIS`] triangles: a sphere
646    /// with holes, flipped triangles, a duplicate, a repeated id and a slit
647    /// (vertex 500 copied, with one triangle moved onto the copy), beside two
648    /// crossed boxes.
649    fn large_damaged() -> Mesh {
650        let sphere = uv_sphere(96, 192, 1.0);
651        let holed = punch_holes(&sphere, &[[1.0, 0.0, 0.0], [0.0, -1.0, 0.0]], 0.2);
652        let every_97th: Vec<TriangleId> = (0..holed.triangle_count() as u32).step_by(97).collect();
653        let (mut positions, mut triangles) =
654            parts(&combine(&[&flip(&holed, &every_97th), &crossed_boxes()]));
655        let copy = (positions.len() / 3) as VertexId;
656        positions.extend_from_within(1500..1503);
657        let t = triangles.iter().position(|t| t.contains(&500)).unwrap();
658        triangles[t] = triangles[t].map(|v| if v == 500 { copy } else { v });
659        triangles.extend([triangles[10], [5, 5, 6]]);
660        mesh_of(&positions, &triangles)
661    }
662
663    #[test]
664    fn analyze_bit_identical() {
665        let mesh = large_damaged();
666        assert!(mesh.triangle_count() >= PAR_MIN_ANALYZE_TRIS);
667        let bvh = Bvh::build(&mesh, &BuildOptions::default()).unwrap();
668        for weld_tolerance in [0.0, 0.02] {
669            let options = AnalyzeOptions {
670                weld_tolerance,
671                self_intersection: Some(&bvh),
672                ..Default::default()
673            };
674            let a = assert_parallel_identical("analyze", || analyze(&mesh, &options).unwrap());
675            assert_eq!(a.self_intersects, Some(true));
676            assert!(a.loops.len() >= 2 && a.orientation_conflicts > 0);
677            assert_eq!((a.duplicate, a.degenerate), (1, 1));
678            assert!(a.coincident_groups > 0);
679        }
680        // A pass's error is the same however the passes ran.
681        let other = Bvh::build(&uv_sphere(8, 12, 1.0), &BuildOptions::default()).unwrap();
682        let mut bad = AnalyzeOptions {
683            self_intersection: Some(&other),
684            ..Default::default()
685        };
686        let e = assert_parallel_identical("analyze error", || analyze(&mesh, &bad));
687        assert!(matches!(e, Err(OpsError::Query(_))));
688        // A bad tolerance fails before any pass runs.
689        bad.weld_tolerance = -1.0;
690        let before = par::parallel_entries();
691        assert!(matches!(
692            analyze(&mesh, &bad),
693            Err(OpsError::InvalidInput(_))
694        ));
695        assert_eq!(par::parallel_entries(), before);
696    }
697
698    #[test]
699    fn analyze_oom_is_clean() {
700        let mesh = damaged_sphere();
701        let bvh = Bvh::build(&mesh, &BuildOptions::default()).unwrap();
702        let options = AnalyzeOptions {
703            self_intersection: Some(&bvh),
704            ..Default::default()
705        };
706        let expected = analyze(&mesh, &options).unwrap();
707        let mut n = 0;
708        loop {
709            fail_allocations_after(Some(n));
710            let got = analyze(&mesh, &options);
711            fail_allocations_after(None);
712            match got {
713                Ok(a) => {
714                    assert_eq!(a, expected);
715                    break;
716                }
717                Err(e) => assert_eq!(e, OpsError::Store(StoreError::OutOfMemory)),
718            }
719            n += 1;
720        }
721        assert!(n > 10, "only {n} fallible reservations");
722    }
723}
fast_mesh_ops/analyze.rs

fast_mesh_ops/
analyze.rs
