Skip to main content

meshoptimizer_rs/
mesh_analysis.rs

1//! Read-only mesh topology analysis. This module is an extension: it is not in
2//! C++ meshoptimizer, and no existing function's behaviour depends on it.
3
4use crate::budget::Budget;
5use crate::sanitize::{canonical, screen, sort_work, steps};
6use crate::workspace::{checked_bytes, Work};
7use crate::{Error, Positions, SanitizeOptions, SanitizeReport, Workspace};
8use alloc::vec::Vec;
9
10/// Options for [`analyze_mesh`]. Not in C++ meshoptimizer.
11///
12/// The default, [`Self::EMPTY`], analyzes index topology (two corners are the
13/// same vertex only when they use the same index) and lists nothing.
14#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
15pub struct AnalyzeOptions {
16    weld_positions: bool,
17    list_limit: usize,
18}
19impl AnalyzeOptions {
20    /// Index topology, counts only.
21    pub const EMPTY: Self = Self {
22        weld_positions: false,
23        list_limit: 0,
24    };
25    /// Analyze position-coincident topology instead of index topology:
26    /// vertices with equal positions count as one vertex, using the same
27    /// equality as [`SanitizeOptions::WELD_POSITIONS`] (exact, with `0.0` and
28    /// `-0.0` equal). No tolerance is applied and no index is rewritten.
29    pub const fn with_weld_positions(self, enabled: bool) -> Self {
30        Self {
31            weld_positions: enabled,
32            ..self
33        }
34    }
35    /// List at most `limit` entries of each kind in [`MeshAnalysis::lists`].
36    /// Zero, the default, lists nothing; counts are always complete.
37    pub const fn with_list_limit(self, limit: usize) -> Self {
38        Self {
39            list_limit: limit,
40            ..self
41        }
42    }
43    /// Whether position-coincident topology is analyzed.
44    pub const fn weld_positions(self) -> bool {
45        self.weld_positions
46    }
47    /// Maximum entries listed of each kind.
48    pub const fn list_limit(self) -> usize {
49        self.list_limit
50    }
51}
52
53/// One connected set of boundary edges from [`analyze_mesh`]. Not in C++
54/// meshoptimizer.
55#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
56#[non_exhaustive]
57pub struct BoundaryComponent {
58    /// Smallest vertex index in the component.
59    pub vertex: u32,
60    /// Boundary edges in the component.
61    pub edges: usize,
62}
63
64/// Bounded defect lists from [`analyze_mesh`]. Not in C++ meshoptimizer.
65///
66/// Each list holds at most [`AnalyzeOptions::list_limit`] entries: the first
67/// ones in ascending order of their vertex indices (edges by smaller, then
68/// larger, vertex index). With [`AnalyzeOptions::with_weld_positions`], a
69/// vertex is named by the smallest referenced index among those sharing its
70/// position; unreferenced positions are not scanned.
71#[derive(Clone, Debug, Default, PartialEq, Eq)]
72#[non_exhaustive]
73pub struct AnalysisLists {
74    /// Boundary edges as `[from, to]` in the winding of their one face.
75    pub boundary_edges: Vec<[u32; 2]>,
76    /// Boundary components, ordered by [`BoundaryComponent::vertex`].
77    pub boundary_components: Vec<BoundaryComponent>,
78    /// Edges with more than two faces, as `[smaller, larger]`.
79    pub non_manifold_edges: Vec<[u32; 2]>,
80    /// Vertices whose faces form more than one fan.
81    pub non_manifold_vertices: Vec<u32>,
82    /// Edges with exactly two incident faces using the same direction, as `[smaller, larger]`.
83    pub orientation_conflicts: Vec<[u32; 2]>,
84}
85
86/// Topology report from [`analyze_mesh`]. Not in C++ meshoptimizer.
87///
88/// Triangles are first classified as in [`sanitize`](crate::sanitize).
89/// Triangles with an out-of-range index, a non-finite referenced position or a
90/// repeated index are counted and left out of the topology; so are triangles
91/// with coincident corners when positions are welded, since their corners
92/// then repeat a vertex. The remaining [`Self::triangles`], duplicates
93/// included, form the analyzed topology, so a duplicate face shows up as the
94/// edge defects it causes.
95#[derive(Clone, Debug, Default, PartialEq, Eq)]
96#[non_exhaustive]
97pub struct MeshAnalysis {
98    /// Triangles in the input.
99    pub input_triangles: usize,
100    /// Left out: an index is at or beyond the vertex count.
101    pub out_of_range: usize,
102    /// Left out: a referenced position has a NaN or infinite component.
103    pub non_finite: usize,
104    /// Left out: two corners use the same index.
105    pub repeated_index: usize,
106    /// Triangles with distinct indices and two corners at equal positions
107    /// (signed zeros equal). Left out only with welded positions; otherwise
108    /// counted and analyzed.
109    pub coincident_corners: usize,
110    /// Analyzed triangles with the same corners and winding as an earlier
111    /// analyzed triangle, after a cyclic rotation. The first winding is kept;
112    /// later copies of either winding count here.
113    /// `sanitize` with `IGNORE_ORIENTATION` classifies copies differently.
114    pub duplicate: usize,
115    /// Analyzed triangles that are the first with the opposite winding of an
116    /// earlier analyzed triangle with the same corners. Later copies of that
117    /// winding count as `duplicate`.
118    pub reversed_duplicate: usize,
119    /// Triangles in the analyzed topology.
120    pub triangles: usize,
121    /// Distinct vertices used by analyzed triangles.
122    pub vertices: usize,
123    /// Distinct undirected edges of analyzed triangles.
124    pub edges: usize,
125    /// Edges with exactly one face.
126    pub boundary_edges: usize,
127    /// Connected sets of boundary edges, joined at shared vertices. Equal to
128    /// the number of holes and borders when each boundary vertex has one
129    /// incoming and one outgoing boundary edge; borders that touch at a vertex
130    /// count as one.
131    pub boundary_components: usize,
132    /// Edges with more than two faces.
133    pub non_manifold_edges: usize,
134    /// Vertices whose faces form more than one fan, where two faces around a
135    /// vertex are in one fan when a chain of faces sharing edges at that
136    /// vertex connects them. A bow-tie vertex has two fans.
137    pub non_manifold_vertices: usize,
138    /// Edges with exactly two incident faces using the same direction.
139    pub orientation_conflicts: usize,
140    /// Sets of analyzed triangles connected through shared vertices.
141    pub components: usize,
142    /// Triangles in the largest component, or zero.
143    pub largest_component: usize,
144    /// Triangles in the smallest component, or zero.
145    pub smallest_component: usize,
146    /// Bounded lists of the counted defects.
147    pub lists: AnalysisLists,
148}
149
150/// Report the topology of a triangle list without changing anything.
151/// Not in C++ meshoptimizer.
152///
153/// Counts boundary edges and components, non-manifold edges and vertices,
154/// orientation conflicts, connected components, and the invalid, degenerate
155/// and duplicate triangles; [`MeshAnalysis`] defines each count. With
156/// [`AnalyzeOptions::with_list_limit`], also lists the first defects of each
157/// kind. Index topology is the default; position-coincident topology needs
158/// [`AnalyzeOptions::with_weld_positions`]. A boundary is not necessarily a
159/// defect: open sheets have one by design.
160///
161/// ```
162/// use meshoptimizer_rs::{analyze_mesh, AnalyzeOptions, Positions, Workspace};
163///
164/// // A square from two triangles: five edges, four of them on one border.
165/// let positions = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [1.0, 1.0, 0.0], [0.0, 1.0, 0.0]];
166/// let indices = [0, 1, 2, 0, 2, 3];
167/// let mut workspace = Workspace::default();
168/// let options = AnalyzeOptions::EMPTY.with_list_limit(8);
169/// let analysis = analyze_mesh(&indices, Positions::from_packed(&positions), options, &mut workspace)?;
170/// assert_eq!((analysis.edges, analysis.boundary_edges, analysis.boundary_components), (5, 4, 1));
171/// assert_eq!(analysis.lists.boundary_edges, [[0, 1], [3, 0], [1, 2], [2, 3]]);
172/// assert_eq!((analysis.non_manifold_edges, analysis.components), (0, 1));
173/// # Ok::<(), meshoptimizer_rs::Error>(())
174/// ```
175///
176/// # Errors
177/// `InvalidTopology` if the index count is not a multiple of three.
178/// `SizeOverflow` for size overflow, including more than `u32::MAX` indices,
179/// `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed
180/// reservation. Invalid triangles are counted, never an error.
181///
182/// Work is `O(n log n)` in the number of triangles whatever the input: edges,
183/// duplicates and welded positions are grouped by sorting, not hashing, and
184/// fans, components and boundary components use union-find with union by size. Scratch
185/// storage is proportional to the analyzed triangles, never to the position
186/// count; each list holds at most the list limit.
187#[inline]
188pub fn analyze_mesh_generic<I: crate::Index>(
189    indices: &[I],
190    positions: Positions<'_>,
191    options: AnalyzeOptions,
192    workspace: &mut Workspace,
193) -> Result<MeshAnalysis, Error> {
194    I::with_input(indices, workspace, |indices, workspace| {
195        analyze_mesh_u32(indices, positions, options, workspace)
196    })
197}
198
199fn analyze_mesh_u32(
200    indices: &[u32],
201    positions: Positions<'_>,
202    options: AnalyzeOptions,
203    workspace: &mut Workspace,
204) -> Result<MeshAnalysis, Error> {
205    let mut work = workspace.begin();
206    let result = analyze(
207        indices,
208        positions,
209        options,
210        &mut Budget::new(workspace),
211        &mut work,
212    );
213    workspace.finish(&work);
214    result
215}
216
217fn analyze(
218    indices: &[u32],
219    positions: Positions<'_>,
220    options: AnalyzeOptions,
221    budget: &mut Budget<'_>,
222    work: &mut Work,
223) -> Result<MeshAnalysis, Error> {
224    if !indices.len().is_multiple_of(3) {
225        return Err(Error::InvalidTopology);
226    }
227    checked_bytes(indices.len(), 4)?;
228    // Corners are numbered in u32.
229    u32::try_from(indices.len()).map_err(|_| Error::SizeOverflow)?;
230    let triangles = indices.as_chunks::<3>().0;
231    budget.ws.charge_retained()?;
232    let weld = options.weld_positions;
233    let mut screened = SanitizeReport::default();
234    let policy = if weld {
235        SanitizeOptions::COINCIDENT_CORNERS
236    } else {
237        SanitizeOptions::EMPTY
238    };
239    let mut candidates = 0;
240    for triangle in triangles {
241        let mut keep = [false];
242        candidates += screen(
243            policy,
244            core::slice::from_ref(triangle),
245            &mut keep,
246            &mut screened,
247            work,
248            |i| positions.get(i as usize),
249        )?;
250    }
251    let mut report = MeshAnalysis {
252        input_triangles: triangles.len(),
253        out_of_range: screened.out_of_range,
254        non_finite: screened.non_finite,
255        repeated_index: screened.repeated_index,
256        coincident_corners: screened.coincident_corners,
257        triangles: candidates,
258        ..MeshAnalysis::default()
259    };
260    if candidates == 0 {
261        return Ok(report);
262    }
263    // Collect only screened triangles; the second screening pass is charged too.
264    let mut kept = budget.reserved::<[u32; 3]>(candidates)?;
265    let mut ignored = SanitizeReport::default();
266    for triangle in triangles {
267        let mut keep = [false];
268        screen(
269            policy,
270            core::slice::from_ref(triangle),
271            &mut keep,
272            &mut ignored,
273            work,
274            |i| positions.get(i as usize),
275        )?;
276        if keep[0] {
277            kept.push(*triangle);
278        }
279    }
280    if !weld {
281        work.add(candidates)?;
282        for &[a, b, c] in &kept {
283            let [pa, pb, pc] = [a, b, c].map(|i| positions.get(i as usize));
284            if pa == pb || pa == pc || pb == pc {
285                report.coincident_corners += 1;
286            }
287        }
288    }
289    let (faces, names) = number_vertices(&kept, weld, positions, budget, work)?;
290    budget.release(kept);
291    count_duplicates(&faces, &mut report, budget, work)?;
292    let lists = topology(
293        &faces,
294        &names,
295        options.list_limit,
296        &mut report,
297        budget,
298        work,
299    )?;
300    report.lists = lists;
301    budget.release(faces);
302    budget.release(names);
303    Ok(report)
304}
305
306/// Number the vertices of the analyzed triangles `0..unique` in ascending
307/// index order, and return each triangle's vertex numbers with the input index
308/// of every number. With `weld`, every corner takes the number of the
309/// smallest index sharing its position, so numbers stay in index order.
310fn number_vertices(
311    triangles: &[[u32; 3]],
312    weld: bool,
313    positions: Positions<'_>,
314    budget: &mut Budget<'_>,
315    work: &mut Work,
316) -> Result<(Vec<[u32; 3]>, Vec<u32>), Error> {
317    let candidates = triangles.len();
318    let corner_count = times(candidates, 3)?;
319    work.add(corner_count)?;
320    work.add(sort_work(corner_count)?)?;
321    let mut referenced = budget.reserved::<u32>(corner_count)?;
322    for triangle in triangles {
323        referenced.extend_from_slice(triangle);
324    }
325    referenced.sort_unstable();
326    referenced.dedup();
327    work.add(referenced.len())?;
328    let names = budget.copied(&referenced)?;
329    budget.release(referenced);
330    let welded = if weld {
331        Some(weld_numbers(&names, positions, budget, work)?)
332    } else {
333        None
334    };
335    work.add(times(corner_count, steps(names.len()))?)?;
336    let mut faces = budget.reserved::<[u32; 3]>(candidates)?;
337    for triangle in triangles {
338        let mut face = [0; 3];
339        for (corner, &vertex) in face.iter_mut().zip(triangle) {
340            let id = names
341                .binary_search(&vertex)
342                .map_err(|_| Error::IndexOutOfBounds)?;
343            *corner = welded.as_ref().map_or(id as u32, |w| w[id]);
344        }
345        faces.push(face);
346    }
347    if let Some(welded) = welded {
348        budget.release(welded);
349    }
350    Ok((faces, names))
351}
352
353/// For every vertex number, the smallest number with an equal position.
354/// Positions are grouped by sorting their bit patterns with `-0.0` folded
355/// into `0.0`; they are finite here, so equal patterns are exactly the equal
356/// floats, the equality `sanitize` welds with.
357fn weld_numbers(
358    names: &[u32],
359    positions: Positions<'_>,
360    budget: &mut Budget<'_>,
361    work: &mut Work,
362) -> Result<Vec<u32>, Error> {
363    let unique = names.len();
364    work.add(times(unique, 2)?)?;
365    work.add(sort_work(unique)?)?;
366    let mut keyed = budget.reserved::<([u32; 3], u32)>(unique)?;
367    for (id, &vertex) in names.iter().enumerate() {
368        let p = positions
369            .get(vertex as usize)
370            .ok_or(Error::IndexOutOfBounds)?;
371        let key = p.map(|x| if x == 0.0 { 0 } else { x.to_bits() });
372        keyed.push((key, id as u32));
373    }
374    keyed.sort_unstable();
375    let mut welded = budget.filled(unique, 0u32)?;
376    let mut class: Option<([u32; 3], u32)> = None;
377    for &(key, id) in &keyed {
378        let first = match class {
379            Some((k, first)) if k == key => first,
380            _ => {
381                class = Some((key, id));
382                id
383            }
384        };
385        welded[id as usize] = first;
386    }
387    budget.release(keyed);
388    Ok(welded)
389}
390
391/// Count duplicate and reversed-duplicate faces by sorting canonical corners,
392/// as `sanitize` does with `IGNORE_ORIENTATION`, keeping every face.
393fn count_duplicates(
394    faces: &[[u32; 3]],
395    report: &mut MeshAnalysis,
396    budget: &mut Budget<'_>,
397    work: &mut Work,
398) -> Result<(), Error> {
399    let n = faces.len();
400    work.add(times(n, 2)?)?;
401    work.add(sort_work(n)?)?;
402    let mut keyed = budget.reserved::<([u32; 3], u32, bool)>(n)?;
403    for (index, &face) in faces.iter().enumerate() {
404        let key = canonical(face);
405        let mirror = canonical([face[0], face[2], face[1]]);
406        keyed.push(if mirror < key {
407            (mirror, index as u32, true)
408        } else {
409            (key, index as u32, false)
410        });
411    }
412    // Input index breaks ties, so each class starts with its earliest face.
413    keyed.sort_unstable();
414    let mut current = None;
415    let mut winding = false;
416    let mut reversed_seen = false;
417    for &(class, _, mirrored) in &keyed {
418        if current == Some(class) {
419            if mirrored == winding || reversed_seen {
420                report.duplicate += 1;
421            } else {
422                reversed_seen = true;
423                report.reversed_duplicate += 1;
424            }
425        } else {
426            current = Some(class);
427            winding = mirrored;
428            reversed_seen = false;
429        }
430    }
431    budget.release(keyed);
432    Ok(())
433}
434
435/// One directed edge of a face, keyed by its undirected vertex pair.
436#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
437struct HalfEdge {
438    lo: u32,
439    hi: u32,
440    /// Corner the edge starts at: `3 * face + k`.
441    corner: u32,
442    /// Whether the edge runs from `lo` to `hi`.
443    forward: bool,
444}
445impl HalfEdge {
446    fn same_edge(&self, other: &Self) -> bool {
447        self.lo == other.lo && self.hi == other.hi
448    }
449    /// The face's corners at `lo` and at `hi`.
450    fn ends(self) -> (u32, u32) {
451        let k = self.corner % 3;
452        let next = self.corner - k + (k + 1) % 3;
453        if self.forward {
454            (self.corner, next)
455        } else {
456            (next, self.corner)
457        }
458    }
459    /// Whether this edge has exactly two faces and both use it in the same direction.
460    fn conflict(group: &[Self]) -> bool {
461        group.len() == 2 && group[0].forward == group[1].forward
462    }
463}
464
465/// Disjoint sets with union by size and path halving, so a tree is at most
466/// `log2(len)` deep and every find visits at most `steps(len)` entries.
467struct Sets {
468    parent: Vec<u32>,
469    size: Vec<u32>,
470}
471impl Sets {
472    fn new(len: usize, budget: &mut Budget<'_>, work: &mut Work) -> Result<Self, Error> {
473        work.add(len)?;
474        let mut parent = budget.reserved::<u32>(len)?;
475        parent.extend(0..len as u32);
476        let size = budget.filled(len, 1u32)?;
477        Ok(Self { parent, size })
478    }
479    fn find(&mut self, mut x: u32) -> u32 {
480        loop {
481            let parent = self.parent[x as usize];
482            if parent == x {
483                return x;
484            }
485            let grandparent = self.parent[parent as usize];
486            self.parent[x as usize] = grandparent;
487            x = grandparent;
488        }
489    }
490    fn union(&mut self, a: u32, b: u32) {
491        let (a, b) = (self.find(a), self.find(b));
492        if a == b {
493            return;
494        }
495        let (root, child) = if self.size[a as usize] >= self.size[b as usize] {
496            (a, b)
497        } else {
498            (b, a)
499        };
500        self.parent[child as usize] = root;
501        self.size[root as usize] += self.size[child as usize];
502    }
503    fn release(self, budget: &mut Budget<'_>) {
504        budget.release(self.parent);
505        budget.release(self.size);
506    }
507}
508
509fn times(a: usize, b: usize) -> Result<usize, Error> {
510    a.checked_mul(b).ok_or(Error::SizeOverflow)
511}
512
513/// Edge, fan, component and boundary-component counts, then the bounded lists.
514fn topology(
515    faces: &[[u32; 3]],
516    names: &[u32],
517    limit: usize,
518    report: &mut MeshAnalysis,
519    budget: &mut Budget<'_>,
520    work: &mut Work,
521) -> Result<AnalysisLists, Error> {
522    let corners = times(faces.len(), 3)?;
523    let unique = names.len();
524    let corner_find = steps(corners);
525    let vertex_find = steps(unique);
526    let vertex = |corner: u32| faces[corner as usize / 3][corner as usize % 3];
527
528    work.add(corners)?;
529    work.add(sort_work(corners)?)?;
530    let mut edges = budget.reserved::<HalfEdge>(corners)?;
531    for (f, face) in faces.iter().enumerate() {
532        for k in 0..3 {
533            let (from, to) = (face[k], face[(k + 1) % 3]);
534            edges.push(HalfEdge {
535                lo: from.min(to),
536                hi: from.max(to),
537                corner: (f * 3 + k) as u32,
538                forward: from < to,
539            });
540        }
541    }
542    edges.sort_unstable();
543
544    // Corners around a vertex join one fan when their faces share an edge at
545    // that vertex; each fan is then one root corner.
546    let mut fans = Sets::new(corners, budget, work)?;
547    for group in edges.chunk_by(HalfEdge::same_edge) {
548        let pairs = group.len() - 1;
549        work.add(group.len())?;
550        work.add(times(pairs, times(corner_find, 4)?)?)?;
551        report.edges += 1;
552        if group.len() == 1 {
553            report.boundary_edges += 1;
554        }
555        if group.len() > 2 {
556            report.non_manifold_edges += 1;
557        }
558        if HalfEdge::conflict(group) {
559            report.orientation_conflicts += 1;
560        }
561        for pair in group.windows(2) {
562            let ((a_lo, a_hi), (b_lo, b_hi)) = (pair[0].ends(), pair[1].ends());
563            fans.union(a_lo, b_lo);
564            fans.union(a_hi, b_hi);
565        }
566    }
567    work.add(corners)?;
568    work.add(unique)?;
569    let mut fan_counts = budget.filled(unique, 0u32)?;
570    for (corner, &parent) in fans.parent.iter().enumerate() {
571        if parent == corner as u32 {
572            fan_counts[vertex(parent) as usize] += 1;
573        }
574    }
575    fans.release(budget);
576    report.vertices = fan_counts.iter().filter(|&&n| n > 0).count();
577    report.non_manifold_vertices = fan_counts.iter().filter(|&&n| n > 1).count();
578
579    // Components: vertices joined by faces, sized in faces.
580    let mut parts = Sets::new(unique, budget, work)?;
581    work.add(times(faces.len(), times(vertex_find, 5)?)?)?;
582    work.add(times(unique, 2)?)?;
583    for face in faces {
584        parts.union(face[0], face[1]);
585        parts.union(face[0], face[2]);
586    }
587    parts.size.fill(0);
588    for face in faces {
589        let root = parts.find(face[0]);
590        parts.size[root as usize] += 1;
591    }
592    let mut smallest = usize::MAX;
593    for &n in parts.size.iter().filter(|&&n| n > 0) {
594        report.components += 1;
595        report.largest_component = report.largest_component.max(n as usize);
596        smallest = smallest.min(n as usize);
597    }
598    report.smallest_component = if report.components > 0 { smallest } else { 0 };
599    parts.release(budget);
600
601    // Boundary components: vertices joined by boundary edges, sized in edges.
602    let mut loops = None;
603    if report.boundary_edges > 0 {
604        let mut sets = Sets::new(unique, budget, work)?;
605        work.add(times(corners, 2)?)?;
606        work.add(times(report.boundary_edges, times(vertex_find, 3)?)?)?;
607        work.add(times(unique, 2)?)?;
608        let boundary = || {
609            edges
610                .chunk_by(HalfEdge::same_edge)
611                .filter_map(|group| match group {
612                    [edge] => Some(*edge),
613                    _ => None,
614                })
615        };
616        for edge in boundary() {
617            sets.union(edge.lo, edge.hi);
618        }
619        sets.size.fill(0);
620        for edge in boundary() {
621            let root = sets.find(edge.lo);
622            sets.size[root as usize] += 1;
623        }
624        report.boundary_components = sets.size.iter().filter(|&&n| n > 0).count();
625        loops = Some(sets);
626    }
627
628    let mut lists = AnalysisLists::default();
629    if limit > 0 {
630        lists = list(
631            &edges,
632            names,
633            &fan_counts,
634            loops.as_mut(),
635            limit,
636            report,
637            budget,
638            work,
639        )?;
640    }
641    if let Some(sets) = loops {
642        sets.release(budget);
643    }
644    budget.release(fan_counts);
645    budget.release(edges);
646    Ok(lists)
647}
648
649/// The first `limit` defects of each kind, in ascending vertex order.
650#[allow(clippy::too_many_arguments)]
651fn list(
652    edges: &[HalfEdge],
653    names: &[u32],
654    fan_counts: &[u32],
655    loops: Option<&mut Sets>,
656    limit: usize,
657    report: &MeshAnalysis,
658    budget: &mut Budget<'_>,
659    work: &mut Work,
660) -> Result<AnalysisLists, Error> {
661    let name = |v: u32| names[v as usize];
662    let caps = [
663        report.boundary_edges,
664        report.non_manifold_edges,
665        report.orientation_conflicts,
666        report.non_manifold_vertices,
667        report.boundary_components,
668    ]
669    .map(|n| n.min(limit));
670    let mut lists = AnalysisLists {
671        boundary_edges: budget.reserved(caps[0])?,
672        non_manifold_edges: budget.reserved(caps[1])?,
673        orientation_conflicts: budget.reserved(caps[2])?,
674        non_manifold_vertices: budget.reserved(caps[3])?,
675        boundary_components: budget.reserved(caps[4])?,
676    };
677    if caps[..3].iter().any(|&n| n > 0) {
678        work.add(edges.len())?;
679        for group in edges.chunk_by(HalfEdge::same_edge) {
680            let Some(&edge) = group.first() else {
681                continue;
682            };
683            let pair = [name(edge.lo), name(edge.hi)];
684            if group.len() == 1 && lists.boundary_edges.len() < caps[0] {
685                let [lo, hi] = pair;
686                lists
687                    .boundary_edges
688                    .push(if edge.forward { [lo, hi] } else { [hi, lo] });
689            }
690            if group.len() > 2 && lists.non_manifold_edges.len() < caps[1] {
691                lists.non_manifold_edges.push(pair);
692            }
693            if lists.orientation_conflicts.len() < caps[2] && HalfEdge::conflict(group) {
694                lists.orientation_conflicts.push(pair);
695            }
696        }
697    }
698    if caps[3] > 0 {
699        work.add(fan_counts.len())?;
700        for (v, &n) in fan_counts.iter().enumerate() {
701            if n > 1 && lists.non_manifold_vertices.len() < caps[3] {
702                lists.non_manifold_vertices.push(name(v as u32));
703            }
704        }
705    }
706    if let (Some(sets), true) = (loops, caps[4] > 0) {
707        // The first vertex met of each component is its smallest; zeroing the
708        // component's count skips its other vertices.
709        work.add(times(names.len(), steps(names.len()))?)?;
710        for v in 0..names.len() as u32 {
711            if lists.boundary_components.len() == caps[4] {
712                break;
713            }
714            let root = sets.find(v);
715            let edges = sets.size[root as usize];
716            if edges > 0 {
717                lists.boundary_components.push(BoundaryComponent {
718                    vertex: name(v),
719                    edges: edges as usize,
720                });
721                sets.size[root as usize] = 0;
722            }
723        }
724    }
725    Ok(lists)
726}
727
728/// The source-compatible u32 entry point; see [`analyze_mesh_generic`] for selectable index widths.
729#[inline]
730pub fn analyze_mesh(
731    indices: &[u32],
732    positions: Positions<'_>,
733    options: AnalyzeOptions,
734    workspace: &mut Workspace,
735) -> Result<MeshAnalysis, Error> {
736    analyze_mesh_generic::<u32>(indices, positions, options, workspace)
737}