Skip to main content

meshoptimizer_rs/
repair.rs

1//! Opt-in local repair; not in C++ meshoptimizer.
2use crate::budget::Budget;
3use crate::sanitize::{sort_work, steps};
4use crate::workspace::{checked_bytes, Work};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8const NONE: u32 = u32::MAX;
9
10/// Explicit seam policy for welding; not in C++ meshoptimizer.
11#[derive(Clone, Copy)]
12pub enum WeldPolicy<'a> {
13    /// Compare positions alone, potentially destroying attribute seams.
14    PositionsOnly,
15    /// Also require caller attribute equality between representative and vertex.
16    /// The callback must be a deterministic equivalence relation. It is called
17    /// only for geometrically eligible original indices, in deterministic order.
18    AttributeEquality(&'a dyn Fn(u32, u32) -> bool),
19}
20
21/// Counts from welding; not in C++ meshoptimizer.
22#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
23#[non_exhaustive]
24pub struct WeldReport {
25    /// All input vertices, including unreferenced vertices.
26    pub input_vertices: usize,
27    /// Vertices retained as representatives.
28    pub representatives: usize,
29    /// Vertices mapped to an earlier representative.
30    pub merged_vertices: usize,
31}
32
33/// Old-to-original-representative mapping; not in C++ meshoptimizer.
34#[derive(Clone, Debug, Default, PartialEq, Eq)]
35#[non_exhaustive]
36pub struct WeldedVertices {
37    /// One original index per input vertex; this is not a compact numbering.
38    pub remap: Vec<u32>,
39    /// Exact change counts.
40    pub report: WeldReport,
41}
42
43/// Weld positions within a finite nonnegative Euclidean distance tolerance.
44/// This extension is not in C++ meshoptimizer. No vertex is moved.
45///
46/// Visit original indices in ascending order. Choose the lowest original index
47/// among eligible *representatives*, never an already merged vertex. Thus
48/// merging is non-transitive: every member is within tolerance of its own
49/// representative. At zero tolerance numeric equality is used (signed zeros
50/// equal). Apply the remap to indices, then rerun [`crate::sanitize`], because
51/// welding can create repeated corners and duplicate faces.
52///
53/// A sorted spatial grid and fixed neighbor order make selection deterministic.
54/// Grid cells widen for extreme coordinate/tolerance ratios to keep cell keys
55/// representable. Dense cells can cause quadratic candidate visits; every
56/// visit, binary search and sort is charged to `max_work`. All scratch and
57/// output capacity is charged to `max_bytes`; scratch is call-local.
58///
59/// # Errors
60/// `InvalidParameter` for a negative/non-finite tolerance, `NumericalFailure`
61/// for any non-finite input position, and `SizeOverflow`, `LimitExceeded` or
62/// `AllocationFailed` for resource failures. Returns no partial mapping.
63pub fn weld_vertices(
64    positions: Positions<'_>,
65    tolerance: f32,
66    policy: WeldPolicy<'_>,
67    workspace: &mut Workspace,
68) -> Result<WeldedVertices, Error> {
69    let mut work = workspace.begin();
70    let result = weld_plan(
71        positions,
72        tolerance,
73        policy,
74        &mut Budget::new(workspace),
75        &mut work,
76    );
77    workspace.finish(&work);
78    result
79}
80
81/// Mapping length required by [`weld_vertices_into`]; not in C++ meshoptimizer.
82pub const fn weld_vertices_bound(vertex_count: usize) -> usize {
83    vertex_count
84}
85
86/// [`weld_vertices`] into caller storage; not in C++ meshoptimizer.
87/// On success writes `positions.len()` entries and preserves the tail.
88/// Every error leaves the entire destination unchanged. Stages the mapping in
89/// budgeted scratch, so the caller-buffer form still requires heap storage.
90/// # Errors
91/// Same as [`weld_vertices`], plus `BufferTooSmall` after planning the mapping.
92#[inline]
93pub fn weld_vertices_into_generic<I: crate::Index>(
94    destination: &mut [I],
95    positions: Positions<'_>,
96    tolerance: f32,
97    policy: WeldPolicy<'_>,
98    workspace: &mut Workspace,
99) -> Result<WeldReport, Error> {
100    I::with_mut(destination, workspace, |destination, workspace| {
101        weld_vertices_into_u32(destination, positions, tolerance, policy, workspace)
102    })
103}
104
105fn weld_vertices_into_u32(
106    destination: &mut [u32],
107    positions: Positions<'_>,
108    tolerance: f32,
109    policy: WeldPolicy<'_>,
110    workspace: &mut Workspace,
111) -> Result<WeldReport, Error> {
112    let mut work = workspace.begin();
113    let result = (|| {
114        let plan = weld_plan(
115            positions,
116            tolerance,
117            policy,
118            &mut Budget::new(workspace),
119            &mut work,
120        )?;
121        let out = destination
122            .get_mut(..plan.remap.len())
123            .ok_or(Error::BufferTooSmall)?;
124        work.add(out.len())?;
125        out.copy_from_slice(&plan.remap);
126        Ok(plan.report)
127    })();
128    workspace.finish(&work);
129    result
130}
131
132#[derive(Clone, Copy)]
133struct Cell {
134    key: [i64; 3],
135    vertex: u32,
136}
137fn cell(p: [f32; 3], width: f64) -> [i64; 3] {
138    if width == 0.0 {
139        p.map(|v| if v == 0.0 { 0 } else { i64::from(v.to_bits()) })
140    } else {
141        p.map(|v| libm::floor(f64::from(v) / width) as i64)
142    }
143}
144fn weld_plan(
145    positions: Positions<'_>,
146    tolerance: f32,
147    policy: WeldPolicy<'_>,
148    budget: &mut Budget<'_>,
149    work: &mut Work,
150) -> Result<WeldedVertices, Error> {
151    if !tolerance.is_finite() || tolerance < 0.0 {
152        return Err(Error::InvalidParameter);
153    }
154    let n = positions.len();
155    u32::try_from(n).map_err(|_| Error::SizeOverflow)?;
156    budget.ws.charge_retained()?;
157    let mut largest = 0.0f64;
158    for i in 0..n {
159        work.add(1)?;
160        for v in positions.get(i).ok_or(Error::InvalidParameter)? {
161            if !v.is_finite() {
162                return Err(Error::NumericalFailure);
163            }
164            largest = largest.max(f64::from(v).abs());
165        }
166    }
167    // The factor two leaves room for division rounding at cell boundaries;
168    // |key| <= 2^50 bounds that rounding below one quarter of a cell.
169    let width = if tolerance == 0.0 {
170        0.0
171    } else {
172        (2.0 * f64::from(tolerance)).max(largest / ((1u64 << 50) as f64))
173    };
174    work.add(n)?;
175    work.add(sort_work(n)?)?;
176    let mut cells = budget.reserved::<Cell>(n)?;
177    for i in 0..n {
178        cells.push(Cell {
179            // Infallible: the scan above returned for any missing position.
180            key: cell(positions.get(i).ok_or(Error::InvalidParameter)?, width),
181            vertex: i as u32,
182        });
183    }
184    cells.sort_unstable_by_key(|c| (c.key, c.vertex));
185    let mut remap = budget.reserved::<u32>(n)?;
186    let mut merged = 0;
187    let radius = if tolerance == 0.0 { 0 } else { 1 };
188    let squared = f64::from(tolerance) * f64::from(tolerance);
189    for i in 0..n {
190        work.add(1)?;
191        let p = positions.get(i).ok_or(Error::InvalidParameter)?;
192        let key = cell(p, width);
193        let mut representative = i as u32;
194        for x in -radius..=radius {
195            for y in -radius..=radius {
196                for z in -radius..=radius {
197                    let neighbor = [key[0] + x, key[1] + y, key[2] + z];
198                    work.add(steps(n))?;
199                    let start = cells.partition_point(|c| c.key < neighbor);
200                    for c in &cells[start..] {
201                        work.add(1)?;
202                        if c.key != neighbor {
203                            break;
204                        }
205                        let j = c.vertex as usize;
206                        if j >= representative as usize || remap[j] != c.vertex {
207                            continue;
208                        }
209                        let q = positions.get(j).ok_or(Error::InvalidParameter)?;
210                        let d = [0, 1, 2].map(|axis| f64::from(p[axis]) - f64::from(q[axis]));
211                        if d[0] * d[0] + d[1] * d[1] + d[2] * d[2] <= squared
212                            && match policy {
213                                WeldPolicy::PositionsOnly => true,
214                                WeldPolicy::AttributeEquality(eq) => eq(c.vertex, i as u32),
215                            }
216                        {
217                            representative = c.vertex;
218                        }
219                    }
220                }
221            }
222        }
223        merged += usize::from(representative != i as u32);
224        remap.push(representative);
225    }
226    Ok(WeldedVertices {
227        remap,
228        report: WeldReport {
229            input_vertices: n,
230            representatives: n - merged,
231            merged_vertices: merged,
232        },
233    })
234}
235
236/// Orientation changes and residuals; not in C++ meshoptimizer.
237#[derive(Clone, Debug, Default, PartialEq, Eq)]
238#[non_exhaustive]
239pub struct OrientReport {
240    /// Components joined exclusively across two-face edges, including isolated faces.
241    pub components: usize,
242    /// Original face indices flipped, in ascending order.
243    pub flipped_faces: Vec<u32>,
244    /// Two-face edges still inconsistent after propagation, sorted by endpoints.
245    /// These witness contradictory orientation constraints (non-orientability).
246    pub conflicts: Vec<[u32; 2]>,
247    /// Lowest face indices of components touching non-manifold edges or containing
248    /// contradictory constraints, in ascending order.
249    pub ambiguous_components: Vec<u32>,
250}
251/// Oriented indices with original face order; not in C++ meshoptimizer.
252#[derive(Clone, Debug, Default, PartialEq, Eq)]
253#[non_exhaustive]
254pub struct OrientedMeshGeneric<I: crate::Index = u32> {
255    /// Original triangles, with corners 1 and 2 exchanged for reported flips.
256    pub indices: Vec<I>,
257    /// Changes and unresolved components.
258    pub report: OrientReport,
259}
260
261/// Propagate winding across edges with exactly two incident faces.
262/// Not in C++ meshoptimizer. Each component is seeded by its lowest face
263/// index, which stays unflipped. Breadth-first visits use original corner order.
264/// Non-manifold edges never provide adjacency or orientation constraints;
265/// their incident components are reported as ambiguous. A face incident to such
266/// an edge can still flip due to a different, two-face edge. Contradictory
267/// components retain their deterministic spanning-tree assignment and report
268/// the residual conflict edges. No outward orientation is attempted.
269///
270/// # Errors
271/// `InvalidTopology` for incomplete or repeated-index triangles,
272/// `IndexOutOfBounds` for invalid references, or resource errors as in
273/// [`weld_vertices`]. Input topology should first be sanitized. Scratch and
274/// reports are linear in index count; sorted edges cost `O(n log n)` work.
275#[inline]
276pub fn orient_faces_generic<I: crate::Index>(
277    indices: &[I],
278    vertex_count: usize,
279    workspace: &mut Workspace,
280) -> Result<OrientedMeshGeneric<I>, Error> {
281    I::with_input(indices, workspace, |indices, workspace| {
282        orient_faces_u32(indices, vertex_count, workspace)
283            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
284    })
285}
286
287fn orient_faces_u32(
288    indices: &[u32],
289    vertex_count: usize,
290    workspace: &mut Workspace,
291) -> Result<OrientedMeshGeneric, Error> {
292    let mut work = workspace.begin();
293    let result = (|| {
294        let mut budget = Budget::new(workspace);
295        let (flip, report) = orient_plan(indices, vertex_count, &mut budget, &mut work)?;
296        work.add(indices.len())?;
297        let mut out = budget.copied(indices)?;
298        apply_flips(&mut out, &flip);
299        Ok(OrientedMeshGeneric {
300            indices: out,
301            report,
302        })
303    })();
304    workspace.finish(&work);
305    result
306}
307/// Index count required by [`orient_faces_into`]; not in C++ meshoptimizer.
308pub const fn orient_faces_bound(index_count: usize) -> usize {
309    index_count
310}
311/// [`orient_faces`] into caller storage; not in C++ meshoptimizer.
312/// Writes the input index count, preserves the tail, and leaves all destination
313/// entries unchanged on every error. Reports also use budgeted heap storage.
314/// # Errors
315/// Same as [`orient_faces`], plus `BufferTooSmall` after orientation planning.
316#[inline]
317pub fn orient_faces_into_generic<I: crate::Index>(
318    destination: &mut [I],
319    indices: &[I],
320    vertex_count: usize,
321    workspace: &mut Workspace,
322) -> Result<OrientReport, Error> {
323    I::with_input(indices, workspace, |indices, workspace| {
324        I::with_mut(destination, workspace, |destination, workspace| {
325            orient_faces_into_u32(destination, indices, vertex_count, workspace)
326        })
327    })
328}
329
330fn orient_faces_into_u32(
331    destination: &mut [u32],
332    indices: &[u32],
333    vertex_count: usize,
334    workspace: &mut Workspace,
335) -> Result<OrientReport, Error> {
336    let mut work = workspace.begin();
337    let result = (|| {
338        let (flip, report) = orient_plan(
339            indices,
340            vertex_count,
341            &mut Budget::new(workspace),
342            &mut work,
343        )?;
344        let out = destination
345            .get_mut(..indices.len())
346            .ok_or(Error::BufferTooSmall)?;
347        work.add(indices.len())?;
348        out.copy_from_slice(indices);
349        apply_flips(out, &flip);
350        Ok(report)
351    })();
352    workspace.finish(&work);
353    result
354}
355fn apply_flips(out: &mut [u32], flip: &[i8]) {
356    for (t, &f) in out.as_chunks_mut::<3>().0.iter_mut().zip(flip) {
357        if f == 1 {
358            t.swap(1, 2);
359        }
360    }
361}
362
363#[derive(Clone, Copy)]
364struct Edge {
365    key: [u32; 2],
366    face: u32,
367    corner: usize,
368    forward: bool,
369}
370fn edges(
371    indices: &[u32],
372    vertex_count: usize,
373    budget: &mut Budget<'_>,
374    work: &mut Work,
375) -> Result<Vec<Edge>, Error> {
376    if !indices.len().is_multiple_of(3) {
377        return Err(Error::InvalidTopology);
378    }
379    u32::try_from(vertex_count).map_err(|_| Error::SizeOverflow)?;
380    checked_bytes(indices.len(), 4)?;
381    u32::try_from(indices.len() / 3).map_err(|_| Error::SizeOverflow)?;
382    budget.ws.charge_retained()?;
383    for t in indices.as_chunks::<3>().0 {
384        work.add(1)?;
385        if t.iter().any(|&v| v as usize >= vertex_count) {
386            return Err(Error::IndexOutOfBounds);
387        }
388        if t[0] == t[1] || t[1] == t[2] || t[2] == t[0] {
389            return Err(Error::InvalidTopology);
390        }
391    }
392    work.add(indices.len())?;
393    work.add(sort_work(indices.len())?)?;
394    let mut edges = budget.reserved::<Edge>(indices.len())?;
395    for (f, t) in indices.as_chunks::<3>().0.iter().enumerate() {
396        for c in 0..3 {
397            let (a, b) = (t[c], t[(c + 1) % 3]);
398            edges.push(Edge {
399                key: [a.min(b), a.max(b)],
400                face: f as u32,
401                corner: c,
402                forward: a < b,
403            });
404        }
405    }
406    edges.sort_unstable_by_key(|e| (e.key, e.face, e.corner));
407    Ok(edges)
408}
409fn groups(edges: &[Edge]) -> impl Iterator<Item = &[Edge]> {
410    let mut rest = edges;
411    core::iter::from_fn(move || {
412        if rest.is_empty() {
413            return None;
414        }
415        let n = rest.partition_point(|e| e.key == rest[0].key);
416        let (first, tail) = rest.split_at(n);
417        rest = tail;
418        Some(first)
419    })
420}
421#[derive(Clone, Copy)]
422struct Link {
423    face: u32,
424    parity: i8,
425}
426fn orient_plan(
427    indices: &[u32],
428    vertex_count: usize,
429    budget: &mut Budget<'_>,
430    work: &mut Work,
431) -> Result<(Vec<i8>, OrientReport), Error> {
432    let edges = edges(indices, vertex_count, budget, work)?;
433    let n = indices.len() / 3;
434    work.add(sort_work(edges.len())?)?; // group discovery plus all edge visits
435    let mut links = budget.filled(
436        n,
437        [Link {
438            face: NONE,
439            parity: 0,
440        }; 3],
441    )?;
442    let mut blocked = budget.filled(n, false)?;
443    for group in groups(&edges) {
444        if let [a, b] = group {
445            let parity = i8::from(a.forward == b.forward);
446            links[a.face as usize][a.corner] = Link {
447                face: b.face,
448                parity,
449            };
450            links[b.face as usize][b.corner] = Link {
451                face: a.face,
452                parity,
453            };
454        } else if group.len() > 2 {
455            for e in group {
456                blocked[e.face as usize] = true;
457            }
458        }
459    }
460    let mut flip = budget.filled(n, -1i8)?;
461    let mut seeds = budget.filled(n, NONE)?;
462    let mut ambiguous = budget.filled(n, false)?;
463    let mut queue = budget.reserved::<u32>(n)?;
464    let mut report = OrientReport {
465        flipped_faces: budget.reserved(n)?,
466        conflicts: budget.reserved(edges.len() / 2)?,
467        ambiguous_components: budget.reserved(n)?,
468        ..OrientReport::default()
469    };
470    for seed in 0..n {
471        work.add(1)?;
472        if flip[seed] != -1 {
473            continue;
474        }
475        report.components += 1;
476        queue.clear();
477        queue.push(seed as u32);
478        flip[seed] = 0;
479        let mut head = 0;
480        while head < queue.len() {
481            work.add(1)?;
482            let f = queue[head] as usize;
483            head += 1;
484            seeds[f] = seed as u32;
485            ambiguous[seed] |= blocked[f];
486            for link in links[f] {
487                work.add(1)?;
488                if link.face != NONE && flip[link.face as usize] == -1 {
489                    flip[link.face as usize] = flip[f] ^ link.parity;
490                    queue.push(link.face);
491                }
492            }
493        }
494    }
495    work.add(sort_work(edges.len())?)?;
496    for group in groups(&edges) {
497        if let [a, b] = group {
498            if (flip[a.face as usize] ^ flip[b.face as usize]) != i8::from(a.forward == b.forward) {
499                report.conflicts.push(a.key);
500                ambiguous[seeds[a.face as usize] as usize] = true;
501            }
502        }
503    }
504    work.add(n)?;
505    for f in 0..n {
506        if flip[f] == 1 {
507            report.flipped_faces.push(f as u32);
508        }
509        if ambiguous[f] {
510            report.ambiguous_components.push(f as u32);
511        }
512    }
513    Ok((flip, report))
514}
515
516/// One boundary component decision; not in C++ meshoptimizer.
517#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
518#[non_exhaustive]
519pub struct HoleLoop {
520    /// Lowest original vertex index in this boundary component.
521    pub vertex: u32,
522    /// Number of boundary edges in the component.
523    pub edges: usize,
524}
525/// Hole filling changes and refusals; not in C++ meshoptimizer.
526#[derive(Clone, Debug, Default, PartialEq, Eq)]
527#[non_exhaustive]
528pub struct FillHolesReport {
529    /// Original triangle count.
530    pub input_triangles: usize,
531    /// Triangle count after appending fills.
532    pub output_triangles: usize,
533    /// Filled loops, ordered by lowest vertex index.
534    pub filled: Vec<HoleLoop>,
535    /// Components exceeding the caller's maximum edge count.
536    pub too_large: Vec<HoleLoop>,
537    /// Projected loops with intersections, touching edges, coincident corners,
538    /// zero area, or no nondegenerate ear triangulation.
539    pub non_simple: Vec<HoleLoop>,
540    /// Branching/inconsistently directed boundaries, boundaries touching defective
541    /// edges, vertices with disconnected face fans, or loops outside the documented planarity tolerance.
542    pub ambiguous: Vec<HoleLoop>,
543}
544/// Original indices plus filled faces; not in C++ meshoptimizer.
545#[derive(Clone, Debug, Default, PartialEq, Eq)]
546#[non_exhaustive]
547pub struct FilledMeshGeneric<I: crate::Index = u32> {
548    /// Original triangles followed by fills, using original vertices only.
549    pub indices: Vec<I>,
550    /// Exact decisions for each boundary component.
551    pub report: FillHolesReport,
552}
553
554/// Fill small simple boundary loops with existing vertices only.
555/// Not in C++ meshoptimizer. `max_edges` is inclusive; values below three fill
556/// nothing. Original triangles and vertex streams are unchanged.
557///
558/// Components are considered in lowest-vertex order. Refusal precedence is:
559/// too large, ambiguous topology, non-simple projection, nonplanarity. Each
560/// boundary vertex must have one incoming and one outgoing boundary edge and
561/// touch no non-manifold vertex, non-manifold edge, or inconsistent two-face edge. Start at the smallest
562/// index and follow existing winding; append triangles in opposite winding.
563///
564/// Uses independently implemented [ear clipping (Eberly, sections 1–2)](
565/// https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf):
566/// project onto the dominant plane of the loop's area normal, reject touching
567/// or intersecting nonadjacent segments, and remove the first eligible ear in
568/// loop order. Predicates use `f64`, not adaptive exact arithmetic. Distance
569/// from the plane through the first vertex must be at most `1e-6` times the
570/// largest coordinate extent. Nonplanar loops are reported as ambiguous.
571/// Filling does not test intersections with other mesh surfaces, infer intended
572/// openings, or promise watertightness. Orient/sanitize first as appropriate.
573///
574/// Work is bounded by `Limits`, including component searches, intersection
575/// pairs, ear candidates and containment tests (worst case cubic in loop size).
576/// Storage is linear in input indices plus appended indices and reports.
577/// # Errors
578/// Same topology/resource errors as [`orient_faces`], plus `NumericalFailure`
579/// for non-finite referenced positions. Refused loops are successful report
580/// entries; other loops may still be filled. An error returns no partial mesh.
581#[inline]
582pub fn fill_holes_generic<I: crate::Index>(
583    indices: &[I],
584    positions: Positions<'_>,
585    max_edges: usize,
586    workspace: &mut Workspace,
587) -> Result<FilledMeshGeneric<I>, Error> {
588    I::with_input(indices, workspace, |indices, workspace| {
589        fill_holes_u32(indices, positions, max_edges, workspace)
590            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
591    })
592}
593
594fn fill_holes_u32(
595    indices: &[u32],
596    positions: Positions<'_>,
597    max_edges: usize,
598    workspace: &mut Workspace,
599) -> Result<FilledMeshGeneric, Error> {
600    let mut work = workspace.begin();
601    let result = (|| {
602        let mut budget = Budget::new(workspace);
603        let (added, report) = fill_plan(indices, positions, max_edges, &mut budget, &mut work)?;
604        let n = indices
605            .len()
606            .checked_add(added.len())
607            .ok_or(Error::SizeOverflow)?;
608        work.add(n)?;
609        let mut out = budget.reserved(n)?;
610        out.extend_from_slice(indices);
611        out.extend_from_slice(&added);
612        Ok(FilledMeshGeneric {
613            indices: out,
614            report,
615        })
616    })();
617    workspace.finish(&work);
618    result
619}
620/// Conservative output index bound for [`fill_holes_into`]; not in C++ meshoptimizer.
621/// Each boundary edge contributes at most three added indices.
622/// # Errors
623/// `SizeOverflow` if four times the input index count is not representable.
624pub fn fill_holes_bound(index_count: usize) -> Result<usize, Error> {
625    let n = index_count.checked_mul(4).ok_or(Error::SizeOverflow)?;
626    checked_bytes(n, 4)?;
627    Ok(n)
628}
629/// [`fill_holes`] into caller storage; not in C++ meshoptimizer.
630/// Writes `report.output_triangles * 3` indices and preserves the tail. A
631/// destination of [`fill_holes_bound`] entries suffices. All errors, including
632/// insufficient capacity, leave the entire destination unchanged. Added faces
633/// and reports are staged in budgeted heap storage before any write.
634/// # Errors
635/// Same as [`fill_holes`], plus `BufferTooSmall` after planning all loops.
636#[inline]
637pub fn fill_holes_into_generic<I: crate::Index>(
638    destination: &mut [I],
639    indices: &[I],
640    positions: Positions<'_>,
641    max_edges: usize,
642    workspace: &mut Workspace,
643) -> Result<FillHolesReport, Error> {
644    I::with_input(indices, workspace, |indices, workspace| {
645        I::with_mut(destination, workspace, |destination, workspace| {
646            fill_holes_into_u32(destination, indices, positions, max_edges, workspace)
647        })
648    })
649}
650
651fn fill_holes_into_u32(
652    destination: &mut [u32],
653    indices: &[u32],
654    positions: Positions<'_>,
655    max_edges: usize,
656    workspace: &mut Workspace,
657) -> Result<FillHolesReport, Error> {
658    let mut work = workspace.begin();
659    let result = (|| {
660        let (added, report) = fill_plan(
661            indices,
662            positions,
663            max_edges,
664            &mut Budget::new(workspace),
665            &mut work,
666        )?;
667        let n = indices
668            .len()
669            .checked_add(added.len())
670            .ok_or(Error::SizeOverflow)?;
671        let out = destination.get_mut(..n).ok_or(Error::BufferTooSmall)?;
672        work.add(n)?;
673        out[..indices.len()].copy_from_slice(indices);
674        out[indices.len()..].copy_from_slice(&added);
675        Ok(report)
676    })();
677    workspace.finish(&work);
678    result
679}
680
681#[derive(Clone, Copy)]
682struct End {
683    vertex: u32,
684    edge: usize,
685}
686fn end_range(ends: &[End], vertex: u32, work: &mut Work) -> Result<core::ops::Range<usize>, Error> {
687    work.add(
688        steps(ends.len())
689            .checked_mul(2)
690            .ok_or(Error::SizeOverflow)?,
691    )?;
692    Ok(ends.partition_point(|e| e.vertex < vertex)..ends.partition_point(|e| e.vertex <= vertex))
693}
694fn directed(e: &Edge) -> [u32; 2] {
695    if e.forward {
696        e.key
697    } else {
698        [e.key[1], e.key[0]]
699    }
700}
701fn fill_plan(
702    indices: &[u32],
703    positions: Positions<'_>,
704    max_edges: usize,
705    budget: &mut Budget<'_>,
706    work: &mut Work,
707) -> Result<(Vec<u32>, FillHolesReport), Error> {
708    let edges = edges(indices, positions.len(), budget, work)?;
709    for &v in indices {
710        work.add(1)?;
711        // Infallible: `edges` returned `IndexOutOfBounds` for any index >= len.
712        if !positions
713            .get(v as usize)
714            .ok_or(Error::IndexOutOfBounds)?
715            .iter()
716            .all(|x| x.is_finite())
717        {
718            return Err(Error::NumericalFailure);
719        }
720    }
721    work.add(sort_work(edges.len())?)?;
722    let mut boundary = budget.reserved::<Edge>(edges.len())?;
723    let mut bad_vertices =
724        budget.reserved::<u32>(edges.len().checked_mul(2).ok_or(Error::SizeOverflow)?)?;
725    for group in groups(&edges) {
726        match group {
727            [e] => boundary.push(*e),
728            [a, b] if a.forward != b.forward => (),
729            _ => bad_vertices.extend_from_slice(&group[0].key),
730        }
731    }
732    mark_disconnected_fans(&edges, indices, &mut bad_vertices, budget, work)?;
733    work.add(sort_work(bad_vertices.len())?)?;
734    bad_vertices.sort_unstable();
735    let b = boundary.len();
736    let end_count = b.checked_mul(2).ok_or(Error::SizeOverflow)?;
737    work.add(b)?;
738    work.add(sort_work(end_count)?)?;
739    let mut ends = budget.reserved::<End>(end_count)?;
740    for (i, e) in boundary.iter().enumerate() {
741        for vertex in e.key {
742            ends.push(End { vertex, edge: i });
743        }
744    }
745    ends.sort_unstable_by_key(|e| (e.vertex, e.edge));
746    let mut visited = budget.filled(b, false)?;
747    let mut queue = budget.reserved::<usize>(b)?;
748    let mut polygon = budget.reserved::<u32>(b)?;
749    let mut projected = budget.reserved::<[f64; 2]>(b)?;
750    let mut active = budget.reserved::<usize>(b)?;
751    let mut added = budget.reserved::<u32>(b.checked_mul(3).ok_or(Error::SizeOverflow)?)?;
752    let mut report = FillHolesReport {
753        input_triangles: indices.len() / 3,
754        output_triangles: indices.len() / 3,
755        filled: budget.reserved(b)?,
756        too_large: budget.reserved(b)?,
757        non_simple: budget.reserved(b)?,
758        ambiguous: budget.reserved(b)?,
759    };
760    for start in 0..b {
761        work.add(1)?;
762        if visited[start] {
763            continue;
764        }
765        queue.clear();
766        queue.push(start);
767        visited[start] = true;
768        let mut head = 0;
769        let mut ambiguous = false;
770        let mut vertex = u32::MAX;
771        while head < queue.len() {
772            work.add(1)?;
773            let e = boundary[queue[head]];
774            head += 1;
775            for v in e.key {
776                vertex = vertex.min(v);
777                work.add(steps(bad_vertices.len()))?;
778                ambiguous |= bad_vertices.binary_search(&v).is_ok();
779                let range = end_range(&ends, v, work)?;
780                ambiguous |= range.len() != 2;
781                let mut incoming = 0;
782                for end in &ends[range] {
783                    work.add(1)?;
784                    incoming += usize::from(directed(&boundary[end.edge])[1] == v);
785                    if !visited[end.edge] {
786                        visited[end.edge] = true;
787                        queue.push(end.edge);
788                    }
789                }
790                ambiguous |= incoming != 1;
791            }
792        }
793        let decision = HoleLoop {
794            vertex,
795            edges: queue.len(),
796        };
797        if queue.len() > max_edges {
798            report.too_large.push(decision);
799            continue;
800        }
801        if ambiguous || queue.len() < 3 {
802            report.ambiguous.push(decision);
803            continue;
804        }
805        polygon.clear();
806        let mut current = vertex;
807        for _ in 0..queue.len() {
808            work.add(1)?;
809            polygon.push(current);
810            let range = end_range(&ends, current, work)?;
811            let e = ends[range]
812                .iter()
813                .find(|e| directed(&boundary[e.edge])[0] == current)
814                // Infallible: each loop vertex has two ends and one incoming edge.
815                .ok_or(Error::InvalidTopology)?;
816            current = directed(&boundary[e.edge])[1];
817        }
818        let old = added.len();
819        match triangulate(
820            &polygon,
821            positions,
822            &mut projected,
823            &mut active,
824            &mut added,
825            work,
826        )? {
827            LoopResult::Filled => report.filled.push(decision),
828            LoopResult::NonSimple => {
829                added.truncate(old);
830                report.non_simple.push(decision);
831            }
832            LoopResult::Ambiguous => {
833                added.truncate(old);
834                report.ambiguous.push(decision);
835            }
836        }
837    }
838    report.output_triangles += added.len() / 3;
839    Ok((added, report))
840}
841
842// A corner is a node in its vertex's face fan. Union by size and path
843// compression keep adversarial chains bounded; all parent visits are metered.
844fn fan_root(parent: &mut [usize], mut node: usize, work: &mut Work) -> Result<usize, Error> {
845    loop {
846        work.add(1)?;
847        let next = parent[node];
848        if next == node {
849            return Ok(node);
850        }
851        parent[node] = parent[next];
852        node = next;
853    }
854}
855fn mark_disconnected_fans(
856    edges: &[Edge],
857    indices: &[u32],
858    bad: &mut Vec<u32>,
859    budget: &mut Budget<'_>,
860    work: &mut Work,
861) -> Result<(), Error> {
862    let mut parent = budget.reserved::<usize>(indices.len())?;
863    work.add(indices.len())?;
864    parent.extend(0..indices.len());
865    let mut size = budget.filled(indices.len(), 1usize)?;
866    work.add(sort_work(edges.len())?)?;
867    for group in groups(edges) {
868        for pair in group.windows(2) {
869            for vertex in group[0].key {
870                let corner = |e: &Edge| {
871                    e.face as usize * 3
872                        + if directed(e)[0] == vertex {
873                            e.corner
874                        } else {
875                            (e.corner + 1) % 3
876                        }
877                };
878                let mut a = fan_root(&mut parent, corner(&pair[0]), work)?;
879                let mut b = fan_root(&mut parent, corner(&pair[1]), work)?;
880                if a != b {
881                    if size[a] < size[b] {
882                        core::mem::swap(&mut a, &mut b);
883                    }
884                    parent[b] = a;
885                    size[a] += size[b];
886                }
887            }
888        }
889    }
890    let mut corners = budget.reserved::<(u32, usize)>(indices.len())?;
891    for (node, &v) in indices.iter().enumerate() {
892        corners.push((v, fan_root(&mut parent, node, work)?));
893    }
894    work.add(sort_work(corners.len())?)?;
895    corners.sort_unstable();
896    let mut previous = None;
897    let mut flagged = false;
898    for (v, root) in corners.iter().copied() {
899        work.add(1)?;
900        match previous {
901            Some((pv, pr)) if pv == v => {
902                if root != pr && !flagged {
903                    bad.push(v);
904                    flagged = true;
905                }
906            }
907            _ => {
908                previous = Some((v, root));
909                flagged = false;
910            }
911        }
912    }
913    budget.release(parent);
914    budget.release(size);
915    budget.release(corners);
916    Ok(())
917}
918
919enum LoopResult {
920    Filled,
921    NonSimple,
922    Ambiguous,
923}
924fn cross(a: [f64; 2], b: [f64; 2], c: [f64; 2]) -> f64 {
925    (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
926}
927fn on_segment(a: [f64; 2], b: [f64; 2], p: [f64; 2]) -> bool {
928    cross(a, b, p) == 0.0 && (0..2).all(|k| p[k] >= a[k].min(b[k]) && p[k] <= a[k].max(b[k]))
929}
930fn intersects(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> bool {
931    let (x, y, z, w) = (
932        cross(a, b, c),
933        cross(a, b, d),
934        cross(c, d, a),
935        cross(c, d, b),
936    );
937    ((x > 0.0 && y < 0.0 || x < 0.0 && y > 0.0) && (z > 0.0 && w < 0.0 || z < 0.0 && w > 0.0))
938        || on_segment(a, b, c)
939        || on_segment(a, b, d)
940        || on_segment(c, d, a)
941        || on_segment(c, d, b)
942}
943fn triangulate(
944    polygon: &[u32],
945    positions: Positions<'_>,
946    projected: &mut Vec<[f64; 2]>,
947    active: &mut Vec<usize>,
948    added: &mut Vec<u32>,
949    work: &mut Work,
950) -> Result<LoopResult, Error> {
951    // Infallible: polygon vertices are indices that `edges` bounds-checked.
952    let point = |i: usize| {
953        positions
954            .get(polygon[i] as usize)
955            .map(|p| p.map(f64::from))
956            .ok_or(Error::IndexOutOfBounds)
957    };
958    let n = polygon.len();
959    let origin = point(0)?;
960    let mut normal = [0.0; 3];
961    let mut extent = 0.0f64;
962    let mut lo = origin;
963    let mut hi = origin;
964    for i in 0..n {
965        work.add(1)?;
966        let a = point(i)?;
967        let b = point((i + 1) % n)?;
968        let a = [0, 1, 2].map(|k| {
969            lo[k] = lo[k].min(a[k]);
970            hi[k] = hi[k].max(a[k]);
971            a[k] - origin[k]
972        });
973        let b = [0, 1, 2].map(|k| b[k] - origin[k]);
974        normal[0] += a[1] * b[2] - a[2] * b[1];
975        normal[1] += a[2] * b[0] - a[0] * b[2];
976        normal[2] += a[0] * b[1] - a[1] * b[0];
977    }
978    let mut axis = 0;
979    for k in 0..3 {
980        if normal[k].abs() > normal[axis].abs() {
981            axis = k;
982        }
983        extent = extent.max(hi[k] - lo[k]);
984    }
985    if normal[axis] == 0.0 {
986        return Ok(LoopResult::NonSimple);
987    }
988    projected.clear();
989    active.clear();
990    for i in 0..n {
991        work.add(1)?;
992        let p = point(i)?;
993        projected.push([p[(axis + 1) % 3], p[(axis + 2) % 3]]);
994        active.push(i);
995    }
996    for i in 0..n {
997        for j in i + 1..n {
998            work.add(1)?;
999            if projected[i] == projected[j] {
1000                return Ok(LoopResult::NonSimple);
1001            }
1002            if j != i + 1
1003                && !(i == 0 && j == n - 1)
1004                && intersects(
1005                    projected[i],
1006                    projected[(i + 1) % n],
1007                    projected[j],
1008                    projected[(j + 1) % n],
1009                )
1010            {
1011                return Ok(LoopResult::NonSimple);
1012            }
1013        }
1014    }
1015    let length = libm::sqrt(normal.iter().map(|v| v * v).sum());
1016    for i in 0..n {
1017        work.add(1)?;
1018        let p = point(i)?;
1019        let distance = (0..3)
1020            .map(|k| (p[k] - origin[k]) * normal[k])
1021            .sum::<f64>()
1022            .abs()
1023            / length;
1024        if distance > 1e-6 * extent {
1025            return Ok(LoopResult::Ambiguous);
1026        }
1027    }
1028    let sign = if normal[axis] > 0.0 { 1.0 } else { -1.0 };
1029    while active.len() > 2 {
1030        let m = active.len();
1031        let mut ear = None;
1032        for i in 0..m {
1033            work.add(1)?;
1034            let (a, b, c) = (active[(i + m - 1) % m], active[i], active[(i + 1) % m]);
1035            if cross(projected[a], projected[b], projected[c]) * sign <= 0.0 {
1036                continue;
1037            }
1038            let mut contains = false;
1039            for &p in active.iter() {
1040                work.add(1)?;
1041                if p != a
1042                    && p != b
1043                    && p != c
1044                    && cross(projected[a], projected[b], projected[p]) * sign >= 0.0
1045                    && cross(projected[b], projected[c], projected[p]) * sign >= 0.0
1046                    && cross(projected[c], projected[a], projected[p]) * sign >= 0.0
1047                {
1048                    contains = true;
1049                    break;
1050                }
1051            }
1052            if !contains {
1053                ear = Some((i, a, b, c));
1054                break;
1055            }
1056        }
1057        let Some((i, a, b, c)) = ear else {
1058            return Ok(LoopResult::NonSimple);
1059        };
1060        work.add(active.len())?; // removal shifts and triangle emission
1061        added.extend_from_slice(&[polygon[a], polygon[c], polygon[b]]);
1062        active.remove(i);
1063    }
1064    Ok(LoopResult::Filled)
1065}
1066
1067/// The source-compatible u32 entry point; see [`weld_vertices_into_generic`] for selectable index widths.
1068#[inline]
1069pub fn weld_vertices_into(
1070    destination: &mut [u32],
1071    positions: Positions<'_>,
1072    tolerance: f32,
1073    policy: WeldPolicy<'_>,
1074    workspace: &mut Workspace,
1075) -> Result<WeldReport, Error> {
1076    weld_vertices_into_generic::<u32>(destination, positions, tolerance, policy, workspace)
1077}
1078
1079/// The source-compatible u32 entry point; see [`orient_faces_generic`] for selectable index widths.
1080#[inline]
1081pub fn orient_faces(
1082    indices: &[u32],
1083    vertex_count: usize,
1084    workspace: &mut Workspace,
1085) -> Result<OrientedMesh, Error> {
1086    orient_faces_generic::<u32>(indices, vertex_count, workspace).map(Into::into)
1087}
1088
1089/// The source-compatible u32 entry point; see [`orient_faces_into_generic`] for selectable index widths.
1090#[inline]
1091pub fn orient_faces_into(
1092    destination: &mut [u32],
1093    indices: &[u32],
1094    vertex_count: usize,
1095    workspace: &mut Workspace,
1096) -> Result<OrientReport, Error> {
1097    orient_faces_into_generic::<u32>(destination, indices, vertex_count, workspace)
1098}
1099
1100/// The source-compatible u32 entry point; see [`fill_holes_generic`] for selectable index widths.
1101#[inline]
1102pub fn fill_holes(
1103    indices: &[u32],
1104    positions: Positions<'_>,
1105    max_edges: usize,
1106    workspace: &mut Workspace,
1107) -> Result<FilledMesh, Error> {
1108    fill_holes_generic::<u32>(indices, positions, max_edges, workspace).map(Into::into)
1109}
1110
1111/// The source-compatible u32 entry point; see [`fill_holes_into_generic`] for selectable index widths.
1112#[inline]
1113pub fn fill_holes_into(
1114    destination: &mut [u32],
1115    indices: &[u32],
1116    positions: Positions<'_>,
1117    max_edges: usize,
1118    workspace: &mut Workspace,
1119) -> Result<FillHolesReport, Error> {
1120    fill_holes_into_generic::<u32>(destination, indices, positions, max_edges, workspace)
1121}
1122
1123/// The source-compatible u32 form of [`OrientedMeshGeneric`].
1124/// Oriented indices with original face order; not in C++ meshoptimizer.
1125#[derive(Clone, Debug, Default, PartialEq, Eq)]
1126#[non_exhaustive]
1127pub struct OrientedMesh {
1128    /// Original triangles, with corners 1 and 2 exchanged for reported flips.
1129    pub indices: Vec<u32>,
1130    /// Changes and unresolved components.
1131    pub report: OrientReport,
1132}
1133impl From<OrientedMeshGeneric<u32>> for OrientedMesh {
1134    #[inline]
1135    fn from(value: OrientedMeshGeneric<u32>) -> Self {
1136        Self {
1137            indices: value.indices,
1138            report: value.report,
1139        }
1140    }
1141}
1142
1143impl From<OrientedMesh> for OrientedMeshGeneric<u32> {
1144    #[inline]
1145    fn from(value: OrientedMesh) -> Self {
1146        Self {
1147            indices: value.indices,
1148            report: value.report,
1149        }
1150    }
1151}
1152
1153/// The source-compatible u32 form of [`FilledMeshGeneric`].
1154/// Original indices plus filled faces; not in C++ meshoptimizer.
1155#[derive(Clone, Debug, Default, PartialEq, Eq)]
1156#[non_exhaustive]
1157pub struct FilledMesh {
1158    /// Original triangles followed by fills, using original vertices only.
1159    pub indices: Vec<u32>,
1160    /// Exact decisions for each boundary component.
1161    pub report: FillHolesReport,
1162}
1163impl From<FilledMeshGeneric<u32>> for FilledMesh {
1164    #[inline]
1165    fn from(value: FilledMeshGeneric<u32>) -> Self {
1166        Self {
1167            indices: value.indices,
1168            report: value.report,
1169        }
1170    }
1171}
1172
1173impl From<FilledMesh> for FilledMeshGeneric<u32> {
1174    #[inline]
1175    fn from(value: FilledMesh) -> Self {
1176        Self {
1177            indices: value.indices,
1178            report: value.report,
1179        }
1180    }
1181}
1182
1183mod topology;
1184pub use topology::*;