fast_mesh_ops/
auto_repair.rs

1//! The standard cleanup pipeline as one call.
2
3use fast_mesh_store::Transaction;
4
5use crate::{
6    ComponentOptions, DegenerateOptions, DegenerateReport, FillOptions, FillReport, OrientReport,
7    RemoveReport, Result, WeldReport,
8};
9
10/// Options for [`auto_repair()`].
11#[derive(Debug, Clone, Copy, PartialEq)]
12pub struct AutoRepairOptions {
13    /// Vertices at most this far apart are welded, in local units. Default
14    /// `1e-5`.
15    pub weld_tolerance: f32,
16    /// Components with fewer triangles are removed; the largest component
17    /// always stays. Default `500`.
18    pub min_triangles: usize,
19    /// Fill only holes with at most this many edges; `None` fills any size,
20    /// an open mesh's outer boundary included. Default `Some(64)`.
21    pub max_edges: Option<usize>,
22    /// Refine and fair each fill so that it continues the surrounding
23    /// curvature ([`FillOptions::fair`]). Default `true`.
24    pub fair: bool,
25}
26
27impl Default for AutoRepairOptions {
28    fn default() -> Self {
29        Self {
30            weld_tolerance: 1e-5,
31            min_triangles: 500,
32            max_edges: Some(64),
33            fair: true,
34        }
35    }
36}
37
38impl AutoRepairOptions {
39    /// A builder for [`AutoRepairOptions`]: every option unset, as
40    /// [`Default`], until set.
41    pub fn builder() -> AutoRepairOptionsBuilder {
42        AutoRepairOptionsBuilder::default()
43    }
44}
45
46/// A builder for [`AutoRepairOptions`], see [`AutoRepairOptions::builder`].
47#[derive(Debug, Clone, Copy, Default)]
48pub struct AutoRepairOptionsBuilder {
49    options: AutoRepairOptions,
50}
51
52impl AutoRepairOptionsBuilder {
53    /// Vertices at most this far apart are welded, in local units.
54    pub fn weld_tolerance(mut self, weld_tolerance: f32) -> Self {
55        self.options.weld_tolerance = weld_tolerance;
56        self
57    }
58
59    /// Components with fewer triangles are removed.
60    pub fn min_triangles(mut self, min_triangles: usize) -> Self {
61        self.options.min_triangles = min_triangles;
62        self
63    }
64
65    /// Fill only holes with at most this many edges; `None` fills any size.
66    pub fn max_edges(mut self, max_edges: Option<usize>) -> Self {
67        self.options.max_edges = max_edges;
68        self
69    }
70
71    /// Whether to refine and fair each fill.
72    pub fn fair(mut self, fair: bool) -> Self {
73        self.options.fair = fair;
74        self
75    }
76
77    /// The options as set.
78    pub fn build(self) -> AutoRepairOptions {
79        self.options
80    }
81}
82
83/// What [`auto_repair()`] did, stage by stage.
84#[derive(Debug, Clone, Default, PartialEq, Eq)]
85pub struct AutoRepairReport {
86    /// The weld stage.
87    pub weld: WeldReport,
88    /// The remove-degenerate stage.
89    pub degenerate: DegenerateReport,
90    /// The orient stage.
91    pub orient: OrientReport,
92    /// The remove-small-components stage.
93    pub components: RemoveReport,
94    /// The fill-holes stage.
95    pub fill: FillReport,
96}
97
98/// One stage's report in an [`AutoRepairReport`].
99#[derive(Debug, Clone, Copy, PartialEq, Eq)]
100pub enum AutoRepairStage<'a> {
101    /// The weld stage.
102    Weld(&'a WeldReport),
103    /// The remove-degenerate stage.
104    Degenerate(&'a DegenerateReport),
105    /// The orient stage.
106    Orient(&'a OrientReport),
107    /// The remove-small-components stage.
108    Components(&'a RemoveReport),
109    /// The fill-holes stage.
110    Fill(&'a FillReport),
111}
112
113impl AutoRepairReport {
114    /// The stages' reports in the order they ran, for showing them without
115    /// repeating that order.
116    pub fn stages(&self) -> [AutoRepairStage<'_>; 5] {
117        [
118            AutoRepairStage::Weld(&self.weld),
119            AutoRepairStage::Degenerate(&self.degenerate),
120            AutoRepairStage::Orient(&self.orient),
121            AutoRepairStage::Components(&self.components),
122            AutoRepairStage::Fill(&self.fill),
123        ]
124    }
125}
126
127/// Repairs a mesh with the standard cleanup pipeline: [`weld()`](crate::weld)
128/// → [`remove_degenerate()`](crate::remove_degenerate) →
129/// [`orient()`](crate::orient) →
130/// [`remove_small_components()`](crate::remove_small_components) →
131/// [`fill_holes()`](crate::fill_holes), all in `tx`, so committing it makes
132/// one undo step.
133///
134/// The order matters: welding stitches coincident vertices and can leave
135/// duplicate triangles for the next stage, orienting makes hole rims clean
136/// for filling, and small components go before filling so that their holes
137/// are not filled for nothing. Holes past `max_edges` are skipped and holes
138/// that cannot be filled are listed in [`FillReport`]; neither is an error.
139///
140/// On a mesh with UVs a seam stays a seam: the weld keeps its two sides apart,
141/// UV islands of one surface count as one component, and loops with a seam
142/// edge are skipped with [`SkipReason::UvSeam`](crate::SkipReason::UvSeam).
143/// New fill vertices interpolate their rim's UVs.
144///
145/// ```
146/// use fast_mesh_ops::{AutoRepairOptions, auto_repair};
147/// use fast_mesh_store::Mesh;
148///
149/// // Two triangles of a unit square, with the shared corners duplicated.
150/// let positions = [
151///     0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, // first triangle
152///     0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, // second triangle
153/// ];
154/// let mut mesh = Mesh::from_buffers(&positions, &[0, 1, 2, 3, 4, 5]).unwrap();
155///
156/// let mut tx = mesh.begin_edit();
157/// let report = auto_repair(&mut tx, &AutoRepairOptions::default()).unwrap();
158/// tx.commit().unwrap();
159/// assert_eq!(report.weld.merged_vertices, 2);
160/// ```
161///
162/// # Errors
163/// [`OpsError::InvalidInput`](crate::OpsError::InvalidInput) when
164/// `weld_tolerance` is negative, NaN or infinite;
165/// [`OpsError::Store`](crate::OpsError::Store) when memory runs out. Earlier
166/// stages have written to `tx` by then: drop it, which rolls all of them
167/// back, instead of committing.
168pub fn auto_repair(tx: &mut Transaction, options: &AutoRepairOptions) -> Result<AutoRepairReport> {
169    let weld = crate::weld(tx, options.weld_tolerance)?;
170    let degenerate = crate::remove_degenerate(tx, &DegenerateOptions::default())?;
171    let orient = crate::orient(tx)?;
172    let components = crate::remove_small_components(
173        tx,
174        &ComponentOptions {
175            min_triangles: Some(options.min_triangles),
176            ..ComponentOptions::default()
177        },
178    )?;
179    let fill = crate::fill_holes(
180        tx,
181        &FillOptions {
182            // The fill needs a bound: "any size" is one that every loop meets.
183            max_edges: Some(options.max_edges.unwrap_or(usize::MAX)),
184            fair: options.fair,
185            ..FillOptions::default()
186        },
187    )?;
188    Ok(AutoRepairReport {
189        weld,
190        degenerate,
191        orient,
192        components,
193        fill,
194    })
195}
196
197#[cfg(test)]
198mod tests {
199    use super::*;
200    use crate::test_util::{damaged_sphere, edit, grid_without, mesh_of, parts};
201    use crate::{OpsError, fail_allocations_after, weld};
202    use fast_mesh_store::StoreError;
203
204    /// Small enough that the sphere stays and the box floater goes.
205    fn options() -> AutoRepairOptions {
206        AutoRepairOptions {
207            weld_tolerance: 1e-4,
208            min_triangles: 10,
209            ..AutoRepairOptions::default()
210        }
211    }
212
213    #[test]
214    fn defaults_and_builder() {
215        let d = AutoRepairOptions::default();
216        assert_eq!(d.weld_tolerance, 1e-5);
217        assert_eq!(d.min_triangles, 500);
218        assert_eq!(d.max_edges, Some(64));
219        assert!(d.fair);
220        assert_eq!(AutoRepairOptions::builder().build(), d);
221        assert_eq!(
222            AutoRepairOptions::builder()
223                .weld_tolerance(0.5)
224                .min_triangles(3)
225                .max_edges(None)
226                .fair(false)
227                .build(),
228            AutoRepairOptions {
229                weld_tolerance: 0.5,
230                min_triangles: 3,
231                max_edges: None,
232                fair: false,
233            }
234        );
235    }
236
237    #[test]
238    fn matches_the_ops_run_by_hand_in_order() {
239        let o = options();
240        let (mut piped, mut by_hand) = (damaged_sphere(), damaged_sphere());
241        let (r, _) = edit(&mut piped, |tx| auto_repair(tx, &o));
242        let (expected, _) = edit(&mut by_hand, |tx| {
243            Ok(AutoRepairReport {
244                weld: weld(tx, o.weld_tolerance)?,
245                degenerate: crate::remove_degenerate(tx, &DegenerateOptions::default())?,
246                orient: crate::orient(tx)?,
247                components: crate::remove_small_components(
248                    tx,
249                    &ComponentOptions {
250                        min_triangles: Some(o.min_triangles),
251                        keep_largest: true,
252                        min_area: None,
253                    },
254                )?,
255                fill: crate::fill_holes(
256                    tx,
257                    &FillOptions {
258                        max_edges: Some(64),
259                        ..FillOptions::default()
260                    },
261                )?,
262            })
263        });
264        assert_eq!(r, expected);
265        assert_eq!(parts(&piped), parts(&by_hand));
266        // Every stage had work on this mesh.
267        assert!(r.weld.merged_vertices > 0);
268        assert!(r.degenerate.removed_triangles > 0);
269        assert!(r.orient.flipped_triangles > 0);
270        assert_eq!(r.components.removed_components, 1);
271        assert!(!r.fill.filled.is_empty());
272    }
273
274    #[test]
275    fn weld_runs_before_remove_degenerate() {
276        // The same triangle twice on separate vertices: a duplicate only once welded.
277        let corners = [0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0];
278        let positions: Vec<f32> = corners.iter().chain(&corners).copied().collect();
279        let mut mesh = mesh_of(&positions, &[[0, 1, 2], [3, 4, 5]]);
280        let (r, _) = edit(&mut mesh, |tx| auto_repair(tx, &options()));
281        assert_eq!(r.weld.merged_vertices, 3);
282        assert_eq!(r.degenerate.removed_triangles, 1);
283    }
284
285    #[test]
286    fn stages_come_in_run_order() {
287        let r = AutoRepairReport::default();
288        assert_eq!(
289            r.stages(),
290            [
291                AutoRepairStage::Weld(&r.weld),
292                AutoRepairStage::Degenerate(&r.degenerate),
293                AutoRepairStage::Orient(&r.orient),
294                AutoRepairStage::Components(&r.components),
295                AutoRepairStage::Fill(&r.fill),
296            ]
297        );
298    }
299
300    #[test]
301    fn repaired_mesh_needs_nothing_more() {
302        let mut mesh = damaged_sphere();
303        edit(&mut mesh, |tx| auto_repair(tx, &options()));
304        let (again, empty) = edit(&mut mesh, |tx| auto_repair(tx, &options()));
305        assert!(empty);
306        assert_eq!(again.weld, WeldReport::default());
307        assert_eq!(again.degenerate, DegenerateReport::default());
308        assert_eq!(again.orient.flipped_triangles, 0);
309        assert_eq!(again.components, RemoveReport::default());
310        assert_eq!(again.fill, FillReport::default());
311    }
312
313    #[test]
314    fn max_edges_bounds_the_fill_and_none_means_any_size() {
315        // One 4 x 4 hole (16 edges) plus the grid's outer boundary (32 edges).
316        let cells: Vec<(u32, u32)> = (2..6).flat_map(|y| (2..6).map(move |x| (x, y))).collect();
317        let run = |max_edges| {
318            let mut mesh = grid_without(8, &cells);
319            let o = AutoRepairOptions {
320                max_edges,
321                fair: false,
322                ..AutoRepairOptions::default()
323            };
324            edit(&mut mesh, |tx| auto_repair(tx, &o)).0.fill
325        };
326        let (smallest, inner, any) = (run(Some(4)), run(Some(16)), run(None));
327        assert_eq!((smallest.filled.len(), smallest.skipped.len()), (0, 2));
328        assert_eq!((inner.filled.len(), inner.skipped.len()), (1, 1));
329        // None selects the outer boundary too (its collinear rim may not fill).
330        assert!(any.skipped.is_empty());
331        assert_eq!(any.filled.len() + any.failed.len(), 2);
332    }
333
334    #[test]
335    fn min_triangles_keeps_the_largest_component() {
336        // Every component is below the cutoff: the largest still stays.
337        let o = AutoRepairOptions {
338            min_triangles: 1_000_000,
339            ..options()
340        };
341        let mut mesh = damaged_sphere();
342        let (r, _) = edit(&mut mesh, |tx| auto_repair(tx, &o));
343        assert_eq!(r.components.removed_components, 1);
344        assert!(mesh.triangle_count() > 2);
345    }
346
347    #[test]
348    fn invalid_tolerance_writes_nothing() {
349        for bad in [-1.0, f32::NAN, f32::INFINITY] {
350            let mut mesh = damaged_sphere();
351            let before = parts(&mesh);
352            let mut tx = mesh.begin_edit();
353            let o = AutoRepairOptions {
354                weld_tolerance: bad,
355                ..options()
356            };
357            assert!(matches!(
358                auto_repair(&mut tx, &o),
359                Err(OpsError::InvalidInput(_))
360            ));
361            assert!(tx.commit().unwrap().is_empty());
362            assert_eq!(parts(&mesh), before);
363        }
364    }
365
366    #[test]
367    fn a_failure_at_any_stage_rolls_back_when_dropped() {
368        let mut mesh = damaged_sphere();
369        let before = parts(&mesh);
370        let mut n = 0;
371        loop {
372            let mut tx = mesh.begin_edit();
373            fail_allocations_after(Some(n));
374            let r = auto_repair(&mut tx, &options());
375            fail_allocations_after(None);
376            if let Ok(report) = &r {
377                // Past every failure point: the sweep reached the last stage.
378                assert!(report.fill.filled.len() > 1);
379                assert!(n > 5);
380                break;
381            }
382            assert_eq!(r, Err(OpsError::Store(StoreError::OutOfMemory)));
383            drop(tx);
384            assert_eq!(parts(&mesh), before, "failure point {n}");
385            n += 1;
386        }
387    }
388}
fast_mesh_ops/auto_repair.rs

fast_mesh_ops/
auto_repair.rs
