Skip to main content

meshoptimizer_rs/
simplify.rs

1//! Scalar edge-collapse simplification translated from upstream simplifier.cpp.
2use crate::workspace::{checked_bytes, topology, Work};
3use crate::{validate_vertex_flags, Attributes, Error, Positions, VertexFlags, Workspace};
4use alloc::vec::Vec;
5#[path = "simplify_extra.rs"]
6mod extra;
7pub(crate) use extra::SloppyScratch;
8pub use extra::{
9    simplify_points, simplify_points_generic, simplify_points_into, simplify_points_into_generic,
10    simplify_prune, simplify_prune_generic, simplify_prune_into, simplify_prune_into_generic,
11    simplify_sloppy, simplify_sloppy_generic, simplify_sloppy_into, simplify_sloppy_into_generic,
12    simplify_with_update, simplify_with_update_generic,
13};
14
15// Keep the native backend local to simplify; other families retain their
16// qualified portable backend. Special values use that backend too, preserving
17// its NaN payload/sign behavior rather than relying on hardware NaN selection.
18#[inline(always)]
19fn sqrt(value: f32) -> f32 {
20    #[cfg(feature = "std")]
21    if value.to_bits() < 0x7f80_0000 {
22        return value.sqrt();
23    }
24    crate::math::sqrt(value)
25}
26
27/// Whether every packed coordinate is finite. `x - x` is +0 for finite `x`
28/// and NaN otherwise; NaN persists through the lane sums, and a sum of +0
29/// values is +0, so the total is zero exactly when all values are finite.
30#[inline]
31#[allow(clippy::eq_op)] // `x - x` is the finiteness probe, not a zero.
32fn packed_finite(values: &[[f32; 3]]) -> bool {
33    let (chunks, tail) = values.as_flattened().as_chunks::<8>();
34    let mut lanes = [0.0f32; 8];
35    for chunk in chunks {
36        for (lane, &x) in lanes.iter_mut().zip(chunk) {
37            *lane += x - x;
38        }
39    }
40    let mut sum = tail.iter().fold(0.0f32, |sum, &x| sum + (x - x));
41    for lane in lanes {
42        sum += lane;
43    }
44    sum == 0.0
45}
46
47#[cfg(not(feature = "std"))]
48type SqrtCache = crate::math::SqrtCache;
49
50// A native scalar root is cheaper than hashing and traversing the software-root
51// memo. Keep the same call sites and arithmetic order on both backends.
52#[cfg(feature = "std")]
53struct SqrtCache;
54#[cfg(feature = "std")]
55impl SqrtCache {
56    const fn new() -> Self {
57        Self
58    }
59    #[inline(always)]
60    fn sqrt(&mut self, value: f32) -> f32 {
61        sqrt(value)
62    }
63}
64
65// Counted work for one simplifier phase. `Work` checks every visit against the
66// remaining budget. `Prepaid` is used only after `metered!` has established that
67// the remaining budget covers an upper bound of the phase's visits: no visit can
68// then exhaust the budget, so the phase counts locally and charges its exact
69// total (or, on an error, the visited prefix) once. Errors, consumed work and
70// partial side effects are identical to visit-by-visit checking.
71trait Meter {
72    /// Whether `add` cannot fail: the enclosing phase's bound was prepaid.
73    const PREPAID: bool;
74    fn add(&mut self, count: usize) -> Result<(), Error>;
75    fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error>;
76    fn scan<T>(
77        &mut self,
78        values: impl ExactSizeIterator<Item = T>,
79        visit: impl FnMut(T) -> Result<(), Error>,
80    ) -> Result<(), Error>;
81}
82impl Meter for Work {
83    const PREPAID: bool = false;
84    #[inline(always)]
85    fn add(&mut self, count: usize) -> Result<(), Error> {
86        Work::add(self, count)
87    }
88    #[inline(always)]
89    fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
90        Work::precharge(self, count, units)
91    }
92    #[inline(always)]
93    fn scan<T>(
94        &mut self,
95        values: impl ExactSizeIterator<Item = T>,
96        visit: impl FnMut(T) -> Result<(), Error>,
97    ) -> Result<(), Error> {
98        Work::scan(self, values, visit)
99    }
100}
101struct Prepaid(usize);
102impl Meter for Prepaid {
103    const PREPAID: bool = true;
104    #[inline(always)]
105    fn add(&mut self, count: usize) -> Result<(), Error> {
106        self.0 += count;
107        Ok(())
108    }
109    #[inline(always)]
110    fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
111        self.0 += count.checked_mul(units).ok_or(Error::SizeOverflow)?;
112        Ok(true)
113    }
114    #[inline(always)]
115    fn scan<T>(
116        &mut self,
117        values: impl ExactSizeIterator<Item = T>,
118        mut visit: impl FnMut(T) -> Result<(), Error>,
119    ) -> Result<(), Error> {
120        let count = values.len();
121        for (i, value) in values.enumerate() {
122            if let Err(error) = visit(value) {
123                self.0 += i + 1;
124                return Err(error);
125            }
126        }
127        self.0 += count;
128        Ok(())
129    }
130}
131// Evaluate `$body` with `$m` bound to a meter. `$bound` is an upper bound of the
132// visits `$body` counts, or `None` when no cheap bound exists.
133macro_rules! metered {
134    ($work:expr, $bound:expr, |$m:ident| $body:expr) => {{
135        let work: &mut Work = $work;
136        match $bound {
137            Some(bound) if work.covers(bound)? => {
138                let mut tally = Prepaid(0);
139                let result = {
140                    let $m = &mut tally;
141                    $body
142                };
143                debug_assert!(tally.0 <= bound);
144                work.add(tally.0)?;
145                result
146            }
147            _ => {
148                let $m = work;
149                $body
150            }
151        }
152    }};
153}
154
155/// Stable simplification options supported by this port.
156#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
157pub struct SimplifyOptions(u32);
158impl SimplifyOptions {
159    /// Default topology and relative-error behavior.
160    pub const EMPTY: Self = Self(0);
161    /// Prevent movement of geometric border vertices.
162    pub const LOCK_BORDER: Self = Self(1);
163    /// Use first-referenced vertices and subset extents for simplification.
164    pub const SPARSE: Self = Self(2);
165    /// Interpret the error limit and result in position units.
166    pub const ERROR_ABSOLUTE: Self = Self(4);
167    /// Remove disconnected components incrementally within the error budget.
168    pub const PRUNE: Self = Self(8);
169    /// Apply stronger positional regularization.
170    pub const REGULARIZE: Self = Self(16);
171    /// Allow collapses across unprotected attribute discontinuities.
172    pub const PERMISSIVE: Self = Self(32);
173    /// Apply light positional regularization.
174    pub const REGULARIZE_LIGHT: Self = Self(64);
175    /// Preserve geometric folds using additional edge quadrics.
176    #[cfg(feature = "experimental")]
177    pub const PRESERVE_FOLDS: Self = Self(128);
178    /// Clamp each attribute quadric error to its accumulated area.
179    #[cfg(feature = "experimental")]
180    pub const ERROR_CLAMPED: Self = Self(256);
181    /// Validate a raw option mask; unsupported options are rejected.
182    ///
183    /// # Errors
184    /// `UnknownFlags` if any option bit is unknown or unavailable with the enabled features.
185    pub const fn from_bits(bits: u32) -> Result<Self, Error> {
186        let mask = if cfg!(feature = "experimental") {
187            511
188        } else {
189            127
190        };
191        if bits & !mask != 0 {
192            Err(Error::UnknownFlags)
193        } else {
194            Ok(Self(bits))
195        }
196    }
197    /// Return the upstream option mask.
198    pub const fn bits(self) -> u32 {
199        self.0
200    }
201    /// Whether all bits in `other` are present.
202    pub const fn contains(self, other: Self) -> bool {
203        self.0 & other.0 == other.0
204    }
205}
206impl core::ops::BitOr for SimplifyOptions {
207    type Output = Self;
208    fn bitor(self, rhs: Self) -> Self {
209        Self(self.0 | rhs.0)
210    }
211}
212impl core::ops::BitOrAssign for SimplifyOptions {
213    fn bitor_assign(&mut self, rhs: Self) {
214        self.0 |= rhs.0;
215    }
216}
217/// Parameters for edge-collapse simplification.
218#[derive(Clone, Copy, Debug)]
219pub struct SimplifySettings {
220    /// Requested index count, at most the input count; need not be divisible by three.
221    pub target_index_count: usize,
222    /// Nonnegative finite linear error limit; relative to the mesh extent by default.
223    pub target_error: f32,
224    /// Topology, regularization and error-unit options.
225    pub options: SimplifyOptions,
226}
227/// Simplified topology referencing the original vertex array.
228#[derive(Debug)]
229pub struct SimplifiedMeshGeneric<I: crate::Index = u32> {
230    /// Remaining triangles, in upstream order. The requested target may not be reached.
231    pub indices: Vec<I>,
232    /// Linear error in the units selected by the settings.
233    pub error: f32,
234}
235/// Caller-buffer simplification result.
236#[derive(Clone, Copy, Debug)]
237pub struct SimplifyResult {
238    /// Number of initialized result indices in the destination prefix.
239    pub index_count: usize,
240    /// Linear error in the units selected by the settings.
241    pub error: f32,
242}
243/// Return meshopt_simplifyScale's maximum axis extent, without an epsilon clamp.
244/// Empty and coincident positions return zero; non-finite inputs and overflowing
245/// extents return an error. This operation allocates no memory.
246///
247/// Packed `[f32; 3]` positions are fastest. Little-endian byte views with a
248/// 64-byte stride also take a fast path; other layouts use a slower general reader.
249///
250/// # Errors
251/// `InvalidParameter` for non-finite positions; `NumericalFailure` for an overflowing extent.
252pub fn simplify_scale(positions: Positions<'_>) -> Result<f32, Error> {
253    let Some(values) = positions.packed_values() else {
254        return scale_view(positions);
255    };
256    // Separating the finite reduction from the bounds loop lets each scan
257    // run without a per-coordinate early exit. No output/work is observable
258    // before this API returns, and validation still precedes extent overflow.
259    let finite = values
260        .as_flattened()
261        .iter()
262        .fold(true, |finite, v| finite & v.is_finite());
263    if !finite {
264        return Err(Error::InvalidParameter);
265    }
266    let mut lo = [f32::MAX; 3];
267    let mut hi = [-f32::MAX; 3];
268    for v in values {
269        for j in 0..3 {
270            if lo[j] > v[j] {
271                lo[j] = v[j];
272            }
273            if hi[j] < v[j] {
274                hi[j] = v[j];
275            }
276        }
277    }
278    if values.is_empty() {
279        return Ok(0.0);
280    }
281    let mut extent = 0.0;
282    for j in 0..3 {
283        let d = hi[j] - lo[j];
284        if d >= extent {
285            extent = d;
286        }
287    }
288    if !extent.is_finite() {
289        return Err(Error::NumericalFailure);
290    }
291    Ok(extent)
292}
293// Keep the byte reader and its scan state out of the packed fast path.
294#[inline(never)]
295fn scale_view(positions: Positions<'_>) -> Result<f32, Error> {
296    if let Some(records) = positions.scale_full_records() {
297        return scale_records(records, positions.is_empty());
298    }
299    if let Some(records) = positions.scale_records() {
300        return scale_records(records, positions.is_empty());
301    }
302    Ok(bounds(positions)?.1)
303}
304fn scale_records(
305    values: impl Iterator<Item = [f32; 3]> + Clone,
306    empty: bool,
307) -> Result<f32, Error> {
308    // Validate every XYZ before computing extents, retaining InvalidParameter
309    // precedence over NumericalFailure even when an earlier extent overflows.
310    let finite = values.clone().fold(true, |finite, v| {
311        finite & v[0].is_finite() & v[1].is_finite() & v[2].is_finite()
312    });
313    if !finite {
314        return Err(Error::InvalidParameter);
315    }
316    let mut lo = [f32::MAX; 3];
317    let mut hi = [-f32::MAX; 3];
318    for v in values {
319        for j in 0..3 {
320            if lo[j] > v[j] {
321                lo[j] = v[j];
322            }
323            if hi[j] < v[j] {
324                hi[j] = v[j];
325            }
326        }
327    }
328    if empty {
329        return Ok(0.0);
330    }
331    let mut extent = 0.0;
332    for j in 0..3 {
333        let d = hi[j] - lo[j];
334        if d >= extent {
335            extent = d;
336        }
337    }
338    if !extent.is_finite() {
339        return Err(Error::NumericalFailure);
340    }
341    Ok(extent)
342}
343fn bounds_impl<const VALIDATED: bool>(p: Positions<'_>) -> Result<([f32; 3], f32), Error> {
344    let mut lo = [f32::MAX; 3];
345    let mut hi = [-f32::MAX; 3];
346    p.for_each(|v| {
347        for j in 0..3 {
348            if !VALIDATED && !v[j].is_finite() {
349                return Err(Error::InvalidParameter);
350            }
351            if lo[j] > v[j] {
352                lo[j] = v[j];
353            }
354            if hi[j] < v[j] {
355                hi[j] = v[j];
356            }
357        }
358        Ok(())
359    })?;
360    if p.is_empty() {
361        return Ok((lo, 0.0));
362    }
363    let mut extent = 0.0;
364    for j in 0..3 {
365        let d = hi[j] - lo[j];
366        if d >= extent {
367            extent = d;
368        }
369    }
370    if !extent.is_finite() {
371        return Err(Error::NumericalFailure);
372    }
373    Ok((lo, extent))
374}
375// The scale API has no prior finite-input validation.
376fn bounds(p: Positions<'_>) -> Result<([f32; 3], f32), Error> {
377    bounds_impl::<false>(p)
378}
379/// Allocate meshopt_simplify's result, preserving upstream ordering and error bits.
380/// No welding, fetch compaction or cache optimization is applied to the result.
381///
382/// # Errors
383/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
384/// `InvalidParameter` for invalid settings or non-finite inputs; `NumericalFailure` for non-finite geometry or calculations.
385/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
386#[inline]
387pub fn simplify_generic<I: crate::Index>(
388    indices: &[I],
389    positions: Positions<'_>,
390    settings: SimplifySettings,
391    workspace: &mut Workspace,
392) -> Result<SimplifiedMeshGeneric<I>, Error> {
393    I::with_input(indices, workspace, |indices, workspace| {
394        simplify_u32(indices, positions, settings, workspace)
395            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
396    })
397}
398
399fn simplify_u32(
400    indices: &[u32],
401    positions: Positions<'_>,
402    settings: SimplifySettings,
403    workspace: &mut Workspace,
404) -> Result<SimplifiedMeshGeneric, Error> {
405    allocating(indices, positions, None, &[], None, settings, workspace)
406}
407/// Allocate meshopt_simplifyWithAttributes's result. All three vertex flags are
408/// supported; weights must be finite and nonnegative, with one per component.
409/// Zero-weight components do not contribute to error. All supplied values must
410/// be finite, including unused vertices and zero-weight components.
411///
412/// # Errors
413/// Same errors as [`simplify`]. `InvalidLayout` for mismatched attributes, weights or flags.
414#[inline]
415pub fn simplify_with_attributes_generic<I: crate::Index>(
416    indices: &[I],
417    positions: Positions<'_>,
418    attributes: Attributes<'_>,
419    weights: &[f32],
420    vertex_flags: Option<&[VertexFlags]>,
421    settings: SimplifySettings,
422    workspace: &mut Workspace,
423) -> Result<SimplifiedMeshGeneric<I>, Error> {
424    I::with_input(indices, workspace, |indices, workspace| {
425        simplify_with_attributes_u32(
426            indices,
427            positions,
428            attributes,
429            weights,
430            vertex_flags,
431            settings,
432            workspace,
433        )
434        .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
435    })
436}
437
438fn simplify_with_attributes_u32(
439    indices: &[u32],
440    positions: Positions<'_>,
441    attributes: Attributes<'_>,
442    weights: &[f32],
443    vertex_flags: Option<&[VertexFlags]>,
444    settings: SimplifySettings,
445    workspace: &mut Workspace,
446) -> Result<SimplifiedMeshGeneric, Error> {
447    allocating(
448        indices,
449        positions,
450        Some(attributes),
451        weights,
452        vertex_flags,
453        settings,
454        workspace,
455    )
456}
457/// Allocating simplification with per-vertex flags and no attributes.
458pub(crate) fn simplify_flagged(
459    indices: &[u32],
460    positions: Positions<'_>,
461    flags: &[VertexFlags],
462    settings: SimplifySettings,
463    workspace: &mut Workspace,
464) -> Result<SimplifiedMeshGeneric, Error> {
465    allocating(
466        indices,
467        positions,
468        None,
469        &[],
470        Some(flags),
471        settings,
472        workspace,
473    )
474}
475fn allocating(
476    indices: &[u32],
477    positions: Positions<'_>,
478    attributes: Option<Attributes<'_>>,
479    weights: &[f32],
480    flags: Option<&[VertexFlags]>,
481    settings: SimplifySettings,
482    ws: &mut Workspace,
483) -> Result<SimplifiedMeshGeneric, Error> {
484    ws.lod_error_limited = false;
485    let mut work = ws.begin();
486    let result = (|| {
487        validate(
488            indices, positions, attributes, weights, flags, settings, &mut work,
489        )?;
490        ws.acquire(crate::workspace::ScratchFamily::Simplify);
491        ws.prepare([0; 4], checked_bytes(indices.len(), 4)?)?;
492        let mut out = crate::workspace::output(indices.len())?;
493        let output_bytes = checked_bytes(out.capacity(), 4)?;
494        let r = run(
495            &mut out,
496            indices,
497            positions,
498            attributes,
499            weights,
500            flags,
501            settings,
502            ws,
503            &mut work,
504            output_bytes,
505        )?;
506        out.truncate(r.index_count);
507        Ok(SimplifiedMeshGeneric {
508            indices: out,
509            error: r.error,
510        })
511    })();
512    ws.finish(&work);
513    result
514}
515/// Write meshopt_simplify's result into a caller buffer of at least input length.
516/// The tail after the input length is preserved. A late resource or numerical
517/// error may modify the input-length prefix; use the allocating API for atomicity.
518///
519/// # Errors
520/// Same errors as [`simplify`]. `BufferTooSmall` if the destination cannot hold the required prefix.
521#[inline]
522pub fn simplify_into_generic<I: crate::Index>(
523    destination: &mut [I],
524    indices: &[I],
525    positions: Positions<'_>,
526    settings: SimplifySettings,
527    workspace: &mut Workspace,
528) -> Result<SimplifyResult, Error> {
529    I::with_input(indices, workspace, |indices, workspace| {
530        I::with_mut(destination, workspace, |destination, workspace| {
531            simplify_into_u32(destination, indices, positions, settings, workspace)
532        })
533    })
534}
535
536fn simplify_into_u32(
537    destination: &mut [u32],
538    indices: &[u32],
539    positions: Positions<'_>,
540    settings: SimplifySettings,
541    workspace: &mut Workspace,
542) -> Result<SimplifyResult, Error> {
543    into(
544        destination,
545        indices,
546        positions,
547        None,
548        &[],
549        None,
550        settings,
551        workspace,
552    )
553}
554/// Caller-buffer attribute simplification, with the same contracts as
555/// [`simplify_with_attributes`] and the mutation guarantee of [`simplify_into`].
556///
557/// # Errors
558/// Same errors as [`simplify_with_attributes`]. `BufferTooSmall` if the destination cannot hold the required prefix.
559#[allow(clippy::too_many_arguments)]
560#[inline]
561pub fn simplify_with_attributes_into_generic<I: crate::Index>(
562    destination: &mut [I],
563    indices: &[I],
564    positions: Positions<'_>,
565    attributes: Attributes<'_>,
566    weights: &[f32],
567    vertex_flags: Option<&[VertexFlags]>,
568    settings: SimplifySettings,
569    workspace: &mut Workspace,
570) -> Result<SimplifyResult, Error> {
571    I::with_input(indices, workspace, |indices, workspace| {
572        I::with_mut(destination, workspace, |destination, workspace| {
573            simplify_with_attributes_into_u32(
574                destination,
575                indices,
576                positions,
577                attributes,
578                weights,
579                vertex_flags,
580                settings,
581                workspace,
582            )
583        })
584    })
585}
586
587#[allow(clippy::too_many_arguments)]
588fn simplify_with_attributes_into_u32(
589    destination: &mut [u32],
590    indices: &[u32],
591    positions: Positions<'_>,
592    attributes: Attributes<'_>,
593    weights: &[f32],
594    vertex_flags: Option<&[VertexFlags]>,
595    settings: SimplifySettings,
596    workspace: &mut Workspace,
597) -> Result<SimplifyResult, Error> {
598    into(
599        destination,
600        indices,
601        positions,
602        Some(attributes),
603        weights,
604        vertex_flags,
605        settings,
606        workspace,
607    )
608}
609#[allow(clippy::too_many_arguments)]
610fn into(
611    out: &mut [u32],
612    indices: &[u32],
613    p: Positions<'_>,
614    a: Option<Attributes<'_>>,
615    weights: &[f32],
616    flags: Option<&[VertexFlags]>,
617    settings: SimplifySettings,
618    ws: &mut Workspace,
619) -> Result<SimplifyResult, Error> {
620    let mut work = ws.begin();
621    let result = (|| {
622        if out.len() < indices.len() {
623            return Err(Error::BufferTooSmall);
624        }
625        validate(indices, p, a, weights, flags, settings, &mut work)?;
626        ws.acquire(crate::workspace::ScratchFamily::Simplify);
627        run(
628            out, indices, p, a, weights, flags, settings, ws, &mut work, 0,
629        )
630    })();
631    ws.finish(&work);
632    result
633}
634#[allow(clippy::too_many_arguments)]
635fn validate(
636    indices: &[u32],
637    p: Positions<'_>,
638    a: Option<Attributes<'_>>,
639    weights: &[f32],
640    flags: Option<&[VertexFlags]>,
641    s: SimplifySettings,
642    work: &mut Work,
643) -> Result<(), Error> {
644    topology(indices, p.len(), work)?;
645    if s.target_index_count > indices.len() || !s.target_error.is_finite() || s.target_error < 0.0 {
646        return Err(Error::InvalidParameter);
647    }
648    validate_vertex_flags(flags, p.len())?;
649    if let Some(a) = a {
650        if a.len() != p.len() || a.components() != weights.len() {
651            return Err(Error::InvalidLayout);
652        }
653    }
654    work.scan(weights.iter().copied(), |w| {
655        if !w.is_finite() || w < 0.0 {
656            return Err(Error::InvalidParameter);
657        }
658        Ok(())
659    })?;
660    if a.is_none() {
661        if let Some(records) = p.scale_full_records() {
662            return work.scan(records, |v| {
663                if v.iter().fold(true, |finite, x| finite & x.is_finite()) {
664                    Ok(())
665                } else {
666                    Err(Error::InvalidParameter)
667                }
668            });
669        }
670        // Packed positions that are all finite and fit the budget charge the
671        // scan's one visit per vertex at once. Otherwise the counted scan
672        // reports the first non-finite vertex at its original charge.
673        if let Some(values) = p.packed_values() {
674            if work.covers(values.len())? && packed_finite(values) {
675                return work.add(values.len());
676            }
677        }
678        return p.for_each_counted(work, |v| {
679            if !v.iter().fold(true, |finite, x| finite & x.is_finite()) {
680                Err(Error::InvalidParameter)
681            } else {
682                Ok(())
683            }
684        });
685    }
686    // Each loop iteration below charges one visit and then one per component,
687    // and its only side effect is that charge. For packed positions and
688    // contiguous float attributes, find the first vertex the loop would
689    // reject without charging; if the budget covers every iteration, charge
690    // the accepted prefix at once and let the loop rerun only from there.
691    // Errors, their order and the charged work are those of the full loop
692    // (parity/0217-optimesh/PROOFS.md, "Validation prefix").
693    let mut start = 0;
694    if let (Some(values), Some((records, width))) = (
695        p.packed_values(),
696        a.and_then(|a| Some((a.contiguous_floats()?, a.components()))),
697    ) {
698        let visits = width
699            .checked_add(1)
700            .and_then(|v| v.checked_mul(values.len()));
701        if visits.is_some_and(|v| matches!(work.covers(v), Ok(true))) {
702            start = first_nonfinite_vertex(values, records, width);
703            work.add_covered(start * (width + 1));
704        }
705    }
706    for i in start..p.len() {
707        work.add(1)?;
708        if !p
709            .at(i)?
710            .iter()
711            .fold(true, |finite, x| finite & x.is_finite())
712        {
713            return Err(Error::InvalidParameter);
714        }
715        if let Some(a) = a {
716            if let Some(values) = a.float_record(i) {
717                work.scan(values.iter().copied(), |value| {
718                    if value.is_finite() {
719                        Ok(())
720                    } else {
721                        Err(Error::InvalidParameter)
722                    }
723                })?;
724            } else {
725                work.scan(0..a.components(), |k| {
726                    if !a.get(i, k).ok_or(Error::InvalidLayout)?.is_finite() {
727                        return Err(Error::InvalidParameter);
728                    }
729                    Ok(())
730                })?;
731            }
732        }
733    }
734    Ok(())
735}
736#[derive(Clone, Copy, Default, Debug)]
737struct V {
738    x: f32,
739    y: f32,
740    z: f32,
741}
742impl From<[f32; 3]> for V {
743    fn from(v: [f32; 3]) -> Self {
744        Self {
745            x: v[0],
746            y: v[1],
747            z: v[2],
748        }
749    }
750}
751impl V {
752    #[inline(always)]
753    fn sub(self, b: Self) -> Self {
754        Self {
755            x: self.x - b.x,
756            y: self.y - b.y,
757            z: self.z - b.z,
758        }
759    }
760    #[inline(always)]
761    fn dot(self, b: Self) -> f32 {
762        self.x * b.x + self.y * b.y + self.z * b.z
763    }
764    #[inline(always)]
765    fn cross(self, b: Self) -> Self {
766        Self {
767            x: self.y * b.z - self.z * b.y,
768            y: self.z * b.x - self.x * b.z,
769            z: self.x * b.y - self.y * b.x,
770        }
771    }
772    #[inline(always)]
773    fn normalize(&mut self, cache: &mut SqrtCache) -> f32 {
774        let l = cache.sqrt(self.dot(*self));
775        if l > 0.0 {
776            self.x /= l;
777            self.y /= l;
778            self.z /= l;
779        }
780        l
781    }
782}
783#[derive(Clone, Copy, Default)]
784struct Q {
785    a00: f32,
786    a11: f32,
787    a22: f32,
788    a10: f32,
789    a20: f32,
790    a21: f32,
791    b0: f32,
792    b1: f32,
793    b2: f32,
794    c: f32,
795    w: f32,
796    // Used only by positional quadrics after their accumulation phase.
797    inverse_weight: f32,
798}
799impl Q {
800    #[inline(always)]
801    fn add(&mut self, r: Self) {
802        self.a00 += r.a00;
803        self.a11 += r.a11;
804        self.a22 += r.a22;
805        self.a10 += r.a10;
806        self.a20 += r.a20;
807        self.a21 += r.a21;
808        self.b0 += r.b0;
809        self.b1 += r.b1;
810        self.b2 += r.b2;
811        self.c += r.c;
812        self.w += r.w;
813    }
814    #[inline(always)]
815    fn eval(self, v: V) -> f32 {
816        let mut rx = (self.b0 + self.a10 * v.y) * 2.0;
817        let mut ry = (self.b1 + self.a21 * v.z) * 2.0;
818        let mut rz = (self.b2 + self.a20 * v.x) * 2.0;
819        rx += self.a00 * v.x;
820        ry += self.a11 * v.y;
821        rz += self.a22 * v.z;
822        self.c + rx * v.x + ry * v.y + rz * v.z
823    }
824    #[inline(always)]
825    fn error(self, v: V) -> f32 {
826        self.eval(v).abs() * self.inverse_weight
827    }
828    fn cache_inverse_weight(&mut self) {
829        self.inverse_weight = if self.w == 0.0 { 0.0 } else { 1.0 / self.w };
830    }
831    #[inline(always)]
832    fn plane(n: V, d: f32, w: f32) -> Self {
833        let aw = n.x * w;
834        let bw = n.y * w;
835        let cw = n.z * w;
836        let dw = d * w;
837        Self {
838            a00: n.x * aw,
839            a11: n.y * bw,
840            a22: n.z * cw,
841            a10: n.x * bw,
842            a20: n.x * cw,
843            a21: n.y * cw,
844            b0: n.x * dw,
845            b1: n.y * dw,
846            b2: n.z * dw,
847            c: d * dw,
848            w,
849            inverse_weight: 0.0,
850        }
851    }
852    #[inline(always)]
853    fn point(p: V, w: f32) -> Self {
854        Self {
855            a00: w,
856            a11: w,
857            a22: w,
858            b0: -p.x * w,
859            b1: -p.y * w,
860            b2: -p.z * w,
861            c: p.dot(p) * w,
862            w,
863            ..Self::default()
864        }
865    }
866    #[inline(always)]
867    fn triangle(a: V, b: V, c: V, w: f32, cache: &mut SqrtCache) -> Self {
868        let mut n = b.sub(a).cross(c.sub(a));
869        let area = n.normalize(cache);
870        Self::plane(n, -n.dot(a), cache.sqrt(area) * w)
871    }
872    #[inline(always)]
873    fn edge(a: V, b: V, c: V, w: f32, cache: &mut SqrtCache) -> Self {
874        let p10 = b.sub(a);
875        let ls = p10.dot(p10);
876        let p20 = c.sub(a);
877        let proj = p20.dot(p10);
878        let mut perp = V {
879            x: p20.x * ls - p10.x * proj,
880            y: p20.y * ls - p10.y * proj,
881            z: p20.z * ls - p10.z * proj,
882        };
883        perp.normalize(cache);
884        Self::plane(perp, -perp.dot(a), cache.sqrt(ls) * w)
885    }
886    /// The eleven accumulated fields; `inverse_weight` is derived.
887    #[inline(always)]
888    fn fields(self) -> [f32; 11] {
889        [
890            self.a00, self.a11, self.a22, self.a10, self.a20, self.a21, self.b0, self.b1, self.b2,
891            self.c, self.w,
892        ]
893    }
894    #[inline(always)]
895    fn finite(self) -> bool {
896        // For either sign, finite IEEE-754 values have absolute bit patterns
897        // below infinity. The maximum tests all eleven fields without changing
898        // arithmetic or the position of the caller's numerical-error guard.
899        self.fields()
900            .into_iter()
901            .map(|x| x.to_bits() & 0x7fff_ffff)
902            .max()
903            .unwrap_or(0)
904            < 0x7f80_0000
905    }
906}
907#[derive(Clone, Copy, Default)]
908struct G {
909    x: f32,
910    y: f32,
911    z: f32,
912    w: f32,
913}
914impl G {
915    fn add(&mut self, r: Self) {
916        self.x += r.x;
917        self.y += r.y;
918        self.z += r.z;
919        self.w += r.w;
920    }
921}
922#[derive(Clone, Copy, Default)]
923struct Edge {
924    next: u32,
925    prev: u32,
926}
927#[derive(Clone, Copy, Default)]
928struct Collapse {
929    a: u32,
930    b: u32,
931    error: f32,
932}
933const NONE: usize = u32::MAX as usize;
934const MAN: u8 = 0;
935const BORDER: u8 = 1;
936const SEAM: u8 = 2;
937const COMPLEX: u8 = 3;
938const FRINGE: u8 = 4;
939const LOCKED: u8 = 5;
940const CAN: [[u8; 6]; 6] = [
941    [1, 1, 1, 1, 1, 1],
942    [0, 1, 0, 0, 1, 1],
943    [0, 0, 1, 0, 0, 1],
944    [0, 0, 0, 1, 1, 1],
945    [0, 0, 0, 0, 1, 0],
946    [0; 6],
947];
948const OPP: [[u8; 6]; 6] = [
949    [1; 6],
950    [1, 0, 1, 0, 0, 0],
951    [1, 1, 1, 0, 0, 1],
952    [1, 0, 0, 0, 0, 0],
953    [1, 0, 0, 0, 0, 0],
954    [1, 0, 1, 0, 0, 0],
955];
956// Collapse-candidate rules for an ordered kind pair, precomputed from CAN/OPP.
957const PICK_ANY: u8 = 1;
958const PICK_BOTH: u8 = 2;
959const PICK_FORWARD: u8 = 4;
960const PICK_OPPOSITE: u8 = 8;
961const PICK_CHECK_FORWARD: u8 = 16;
962const PICK_CHECK_BACK: u8 = 32;
963const PICK: [u8; 64] = {
964    let mut table = [0; 64];
965    let mut k0 = 0;
966    while k0 < 6 {
967        let mut k1 = 0;
968        while k1 < 6 {
969            let forward = CAN[k0][k1] != 0;
970            let reverse = CAN[k1][k0] != 0;
971            let mut rule = 0;
972            if forward || reverse {
973                rule |= PICK_ANY;
974            }
975            if forward && reverse {
976                rule |= PICK_BOTH;
977            }
978            if forward {
979                rule |= PICK_FORWARD;
980            }
981            if OPP[k0][k1] != 0 {
982                rule |= PICK_OPPOSITE;
983            }
984            let loop0 = k0 == BORDER as usize || k0 == SEAM as usize;
985            let loop1 = k1 == BORDER as usize || k1 == SEAM as usize;
986            if loop0 && k1 != MAN as usize {
987                rule |= PICK_CHECK_FORWARD;
988            }
989            if loop1 && k0 != MAN as usize {
990                rule |= PICK_CHECK_BACK;
991            }
992            table[k0 * 8 + k1] = rule;
993            k1 += 1;
994        }
995        k0 += 1;
996    }
997    table
998};
999// Kinds are always below six, so masking never changes a valid table index.
1000#[inline(always)]
1001fn pair(k0: u8, k1: u8) -> usize {
1002    ((k0 as usize) << 3 | k1 as usize) & 63
1003}
1004// Topology validation bounds every stored index by u32::MAX. Conversions
1005// occur at slice access boundaries, keeping heap records identical in width to C++.
1006struct Indices(Vec<u32>);
1007impl Indices {
1008    #[inline]
1009    fn get(&self, i: usize) -> usize {
1010        self.0[i] as usize
1011    }
1012    #[inline]
1013    fn set(&mut self, i: usize, value: usize) {
1014        self.0[i] = value as u32;
1015    }
1016    fn fill(&mut self, value: usize) {
1017        self.0.fill(value as u32);
1018    }
1019    fn len(&self) -> usize {
1020        self.0.len()
1021    }
1022}
1023// Original-space bounds from the same ordered scan used for normalization.
1024// Update finalization reuses them before it mutates caller positions.
1025struct PositionBounds {
1026    lo: [f32; 3],
1027    hi: [f32; 3],
1028}
1029pub(crate) struct State {
1030    vertex_count: usize,
1031    sqrt_cache: SqrtCache,
1032    offsets: Indices,
1033    edges: Vec<Edge>,
1034    remap: Indices,
1035    wedge: Indices,
1036    kind: Vec<u8>,
1037    forward: Indices,
1038    back: Indices,
1039    p: Vec<V>,
1040    a: Vec<f32>,
1041    q: Vec<Q>,
1042    aq: Vec<Q>,
1043    g: Vec<G>,
1044    vg: Vec<G>,
1045    sparse: Vec<u32>,
1046    original: Vec<u32>,
1047    clamped: bool,
1048    collapses: Vec<Collapse>,
1049    order: Indices,
1050    cr: Indices,
1051    locked: Vec<bool>,
1052    table: Indices,
1053    // Largest per-vertex edge count in the current adjacency.
1054    max_degree: usize,
1055    ac: usize,
1056    bytes: usize,
1057}
1058// Keep the update snapshot owned and reachable during every preparation phase,
1059// including sparse remapping. Its capacity is included in the external budget.
1060struct Input<'a> {
1061    indices: &'a [u32],
1062    original: Vec<u32>,
1063    update: bool,
1064}
1065impl<'a> Input<'a> {
1066    fn borrowed(indices: &'a [u32]) -> Self {
1067        Self {
1068            indices,
1069            original: Vec::new(),
1070            update: false,
1071        }
1072    }
1073    fn as_slice(&self) -> &[u32] {
1074        if self.update {
1075            &self.original
1076        } else {
1077            self.indices
1078        }
1079    }
1080}
1081struct Budget<'a> {
1082    ws: &'a mut Workspace,
1083    bytes: usize,
1084    charged: bool,
1085}
1086impl<'a> Budget<'a> {
1087    fn new(ws: &'a mut Workspace, bytes: usize) -> Self {
1088        Self {
1089            ws,
1090            bytes,
1091            charged: false,
1092        }
1093    }
1094    fn reclaim_input(
1095        &mut self,
1096        original: &mut Vec<u32>,
1097        added: Result<usize, Error>,
1098    ) -> Result<(), Error> {
1099        let requested =
1100            added.and_then(|added| self.bytes.checked_add(added).ok_or(Error::SizeOverflow));
1101        if requested.is_ok_and(|bytes| bytes > self.ws.limits().max_bytes) {
1102            let before = checked_bytes(original.capacity(), 4)?;
1103            crate::workspace::shrink(original, true)?;
1104            self.bytes -= before - checked_bytes(original.capacity(), 4)?;
1105            self.charged = false;
1106        }
1107        Ok(())
1108    }
1109    fn charge_current(&mut self) -> Result<(), Error> {
1110        if !self.charged {
1111            self.ws.charge_owned(self.bytes)?;
1112            self.charged = true;
1113        }
1114        Ok(())
1115    }
1116    fn reuse_capacity<T>(&mut self, v: &mut Vec<T>, n: usize) -> Result<(), Error> {
1117        let size = core::mem::size_of::<T>();
1118        let old = checked_bytes(v.capacity(), size)?;
1119        if self.bytes < old {
1120            return Err(Error::SizeOverflow);
1121        }
1122        if n <= v.capacity() {
1123            self.charge_current()?;
1124            return Ok(());
1125        }
1126        let minimum = n;
1127        let base = self.bytes.checked_sub(old).ok_or(Error::SizeOverflow)?;
1128        let requested = checked_bytes(minimum, size)?;
1129        self.ws
1130            .charge_owned(base.checked_add(requested).ok_or(Error::SizeOverflow)?)?;
1131        if n > v.capacity() {
1132            v.try_reserve_exact(n.saturating_sub(v.len()))
1133                .map_err(|_| Error::AllocationFailed)?;
1134        }
1135        self.bytes = base
1136            .checked_add(checked_bytes(v.capacity(), size)?)
1137            .ok_or(Error::SizeOverflow)?;
1138        if v.capacity() != minimum {
1139            self.ws.charge_owned(self.bytes)?;
1140        }
1141        self.charged = true;
1142        Ok(())
1143    }
1144    fn reuse<T: Default + Clone>(&mut self, v: &mut Vec<T>, n: usize) -> Result<(), Error> {
1145        self.reuse_capacity(v, n)?;
1146        v.resize(n, T::default());
1147        Ok(())
1148    }
1149    fn vec<T: Default + Clone>(&mut self, n: usize) -> Result<Vec<T>, Error> {
1150        self.filled(n, T::default())
1151    }
1152    fn filled<T: Clone>(&mut self, n: usize, value: T) -> Result<Vec<T>, Error> {
1153        let mut v = self.reserve(n)?;
1154        v.resize(n, value);
1155        Ok(v)
1156    }
1157    fn release<T>(&mut self, value: Vec<T>) {
1158        self.bytes -= value.capacity() * core::mem::size_of::<T>();
1159        drop(value);
1160    }
1161    fn reserve<T>(&mut self, n: usize) -> Result<Vec<T>, Error> {
1162        let b = checked_bytes(n, core::mem::size_of::<T>())?;
1163        self.ws
1164            .charge_owned(self.bytes.checked_add(b).ok_or(Error::SizeOverflow)?)?;
1165        let mut v = Vec::new();
1166        v.try_reserve_exact(n)
1167            .map_err(|_| Error::AllocationFailed)?;
1168        self.bytes = self
1169            .bytes
1170            .checked_add(checked_bytes(v.capacity(), core::mem::size_of::<T>())?)
1171            .ok_or(Error::SizeOverflow)?;
1172        if v.capacity() != n {
1173            self.ws.charge_owned(self.bytes)?;
1174        }
1175        self.charged = true;
1176        Ok(v)
1177    }
1178}
1179impl core::fmt::Debug for State {
1180    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1181        f.debug_struct("SimplifyScratch")
1182            .field("vertices", &self.vertex_count)
1183            .field("heap_bytes", &self.capacity_bytes())
1184            .finish()
1185    }
1186}
1187impl State {
1188    pub(crate) fn capacity_bytes(&self) -> Result<usize, Error> {
1189        let fields = [
1190            (self.offsets.0.capacity(), 4),
1191            (self.edges.capacity(), core::mem::size_of::<Edge>()),
1192            (self.remap.0.capacity(), 4),
1193            (self.wedge.0.capacity(), 4),
1194            (self.kind.capacity(), 1),
1195            (self.forward.0.capacity(), 4),
1196            (self.back.0.capacity(), 4),
1197            (self.p.capacity(), core::mem::size_of::<V>()),
1198            (self.a.capacity(), 4),
1199            (self.q.capacity(), core::mem::size_of::<Q>()),
1200            (self.aq.capacity(), core::mem::size_of::<Q>()),
1201            (self.g.capacity(), core::mem::size_of::<G>()),
1202            (self.vg.capacity(), core::mem::size_of::<G>()),
1203            (self.sparse.capacity(), 4),
1204            (self.original.capacity(), 4),
1205            (self.collapses.capacity(), core::mem::size_of::<Collapse>()),
1206            (self.order.0.capacity(), 4),
1207            (self.cr.0.capacity(), 4),
1208            (self.locked.capacity(), 1),
1209            (self.table.0.capacity(), 4),
1210        ];
1211        fields.into_iter().try_fold(0usize, |sum, (n, size)| {
1212            sum.checked_add(checked_bytes(n, size)?)
1213                .ok_or(Error::SizeOverflow)
1214        })
1215    }
1216    fn reclaim_for(
1217        &mut self,
1218        ws: &Workspace,
1219        requested: Result<usize, Error>,
1220        original: &mut Vec<u32>,
1221    ) -> Result<(), Error> {
1222        if !requested.is_ok_and(|bytes| bytes > ws.limits().max_bytes) {
1223            return Ok(());
1224        }
1225        let before = self.capacity_bytes()? + checked_bytes(original.capacity(), 4)?;
1226        // remap, wedge and positions are filled by pushes after initial allocation.
1227        // Their reserved prefixes are live even before their lengths reach n.
1228        self.remap.0.shrink_to(self.vertex_count);
1229        self.wedge.0.shrink_to(self.vertex_count);
1230        self.p.shrink_to(self.vertex_count);
1231        macro_rules! shrink {
1232            ($($v:expr),* $(,)?) => { $(crate::workspace::shrink(&mut $v, true)?;)* };
1233        }
1234        shrink!(
1235            self.offsets.0,
1236            self.edges,
1237            self.kind,
1238            self.forward.0,
1239            self.back.0,
1240            self.a,
1241            self.q,
1242            self.aq,
1243            self.g,
1244            self.vg,
1245            self.sparse,
1246            self.original,
1247            self.collapses,
1248            self.order.0,
1249            self.cr.0,
1250            self.locked,
1251            self.table.0,
1252            *original
1253        );
1254        let after = self.capacity_bytes()? + checked_bytes(original.capacity(), 4)?;
1255        self.bytes -= before - after;
1256        Ok(())
1257    }
1258    fn retain(mut self, ws: &mut Workspace) {
1259        // Position quadrics are fully rewritten on every call and dominate
1260        // resident scratch during caller-side pruning. Keep the other typed
1261        // buffers reusable, but release these pages before returning.
1262        if ws.retention() == crate::Retention::Lean {
1263            self.q = Vec::new();
1264        }
1265        if let Some(mut unused) = ws.simplify.take() {
1266            if self.a.capacity() == 0 {
1267                self.a = core::mem::take(&mut unused.a);
1268            }
1269            if self.aq.capacity() == 0 {
1270                self.aq = core::mem::take(&mut unused.aq);
1271            }
1272            if self.g.capacity() == 0 {
1273                self.g = core::mem::take(&mut unused.g);
1274            }
1275            if self.vg.capacity() == 0 {
1276                self.vg = core::mem::take(&mut unused.vg);
1277            }
1278            if self.sparse.capacity() == 0 {
1279                self.sparse = core::mem::take(&mut unused.sparse);
1280            }
1281            if self.original.capacity() == 0 {
1282                self.original = core::mem::take(&mut unused.original);
1283            }
1284        }
1285        ws.has_retained = true;
1286        ws.simplify = Some(self);
1287    }
1288    fn empty() -> Self {
1289        Self {
1290            vertex_count: 0,
1291            sqrt_cache: SqrtCache::new(),
1292            offsets: Indices(Vec::new()),
1293            edges: Vec::new(),
1294            remap: Indices(Vec::new()),
1295            wedge: Indices(Vec::new()),
1296            kind: Vec::new(),
1297            forward: Indices(Vec::new()),
1298            back: Indices(Vec::new()),
1299            p: Vec::new(),
1300            a: Vec::new(),
1301            q: Vec::new(),
1302            aq: Vec::new(),
1303            g: Vec::new(),
1304            vg: Vec::new(),
1305            sparse: Vec::new(),
1306            original: Vec::new(),
1307            clamped: false,
1308            collapses: Vec::new(),
1309            order: Indices(Vec::new()),
1310            cr: Indices(Vec::new()),
1311            locked: Vec::new(),
1312            table: Indices(Vec::new()),
1313            max_degree: 0,
1314            ac: 0,
1315            bytes: 0,
1316        }
1317    }
1318    fn new(
1319        n: usize,
1320        m: usize,
1321        ac: usize,
1322        ws: &mut Workspace,
1323        mut output: usize,
1324        solve: bool,
1325        original: &mut Vec<u32>,
1326    ) -> Result<Self, Error> {
1327        let na = n.checked_mul(ac).ok_or(Error::SizeOverflow)?;
1328        let buckets = n
1329            .checked_add(n / 4)
1330            .ok_or(Error::SizeOverflow)?
1331            .checked_next_power_of_two()
1332            .ok_or(Error::SizeOverflow)?;
1333        let mut state = ws.simplify.take().unwrap_or_else(Self::empty);
1334        // Keep dormant fields in the workspace, outside the live local state.
1335        // Any later reservation can evict them, including prune/solve phases.
1336        let mut unused = Self::empty();
1337        if na == 0 {
1338            unused.a = core::mem::take(&mut state.a);
1339            unused.g = core::mem::take(&mut state.g);
1340        }
1341        if ac == 0 {
1342            unused.aq = core::mem::take(&mut state.aq);
1343        }
1344        if !solve || ac == 0 {
1345            unused.vg = core::mem::take(&mut state.vg);
1346        }
1347        unused.sparse = core::mem::take(&mut state.sparse);
1348        unused.original = core::mem::take(&mut state.original);
1349        if unused.capacity_bytes()? != 0 {
1350            ws.has_retained = true;
1351            ws.simplify = Some(unused);
1352        }
1353        // Old capacity has no live contents yet. Before reserving, discard an
1354        // oversized previous problem (including attributes/collapse buffers).
1355        // Only the reservations made below enter this preflight.
1356        // Same-size calls keep their allocations whenever the peak fits.
1357        // An estimate must not preempt the first real reservation's error.
1358        let projected = (|| {
1359            let mut projected = output
1360                .checked_add(state.capacity_bytes()?)
1361                .ok_or(Error::SizeOverflow)?;
1362            for (capacity, needed, size) in [
1363                (state.offsets.0.capacity(), n + 1, 4),
1364                (state.edges.capacity(), m, core::mem::size_of::<Edge>()),
1365                (state.remap.0.capacity(), n, 4),
1366                (state.wedge.0.capacity(), n, 4),
1367                (state.kind.capacity(), n, 1),
1368                (state.forward.0.capacity(), n, 4),
1369                (state.back.0.capacity(), n, 4),
1370                (state.p.capacity(), n, core::mem::size_of::<V>()),
1371                (state.a.capacity(), na, 4),
1372                (state.q.capacity(), n, core::mem::size_of::<Q>()),
1373                (
1374                    state.aq.capacity(),
1375                    if ac > 0 { n } else { 0 },
1376                    core::mem::size_of::<Q>(),
1377                ),
1378                (state.g.capacity(), na, core::mem::size_of::<G>()),
1379                (state.cr.0.capacity(), n, 4),
1380                (state.locked.capacity(), n, 1),
1381                (state.table.0.capacity(), buckets, 4),
1382            ] {
1383                projected = projected
1384                    .checked_add(checked_bytes(needed.saturating_sub(capacity), size)?)
1385                    .ok_or(Error::SizeOverflow)?;
1386            }
1387            Ok::<_, Error>(projected)
1388        })();
1389        if projected.is_ok_and(|bytes| bytes > ws.limits().max_bytes) {
1390            let old = checked_bytes(original.capacity(), 4)?;
1391            crate::workspace::shrink(original, true)?;
1392            let released = old - checked_bytes(original.capacity(), 4)?;
1393            output -= released;
1394            if projected.is_ok_and(|bytes| bytes - released > ws.limits().max_bytes) {
1395                state = Self::empty();
1396            }
1397        }
1398        let bytes = output
1399            .checked_add(state.capacity_bytes()?)
1400            .ok_or(Error::SizeOverflow)?;
1401        let lean = ws.retention() == crate::Retention::Lean;
1402        let mut b = Budget::new(ws, bytes);
1403        b.reuse(&mut state.offsets.0, n + 1)?;
1404        b.reuse(&mut state.edges, m)?;
1405        state.remap.0.clear();
1406        b.reuse_capacity(&mut state.remap.0, n)?;
1407        state.wedge.0.clear();
1408        b.reuse_capacity(&mut state.wedge.0, n)?;
1409        b.reuse(&mut state.kind, n)?;
1410        state.kind.fill(MAN);
1411        b.reuse(&mut state.forward.0, n)?;
1412        state.forward.fill(NONE);
1413        b.reuse(&mut state.back.0, n)?;
1414        state.back.fill(NONE);
1415        state.p.clear();
1416        b.reuse_capacity(&mut state.p, n)?;
1417        b.reuse(&mut state.a, na)?;
1418        if lean {
1419            // Initialize once for both fresh and reused allocations.
1420            state.q.clear();
1421            b.reuse(&mut state.q, n)?;
1422        } else {
1423            b.reuse(&mut state.q, n)?;
1424            state.q.fill(Q::default());
1425        }
1426        b.reuse(&mut state.aq, if ac > 0 { n } else { 0 })?;
1427        state.aq.fill(Q::default());
1428        b.reuse(&mut state.g, na)?;
1429        state.g.fill(G::default());
1430        state.vg.clear();
1431        state.sparse.clear();
1432        state.original.clear();
1433        state.collapses.clear();
1434        state.order.0.clear();
1435        b.reuse(&mut state.cr.0, n)?;
1436        b.reuse(&mut state.locked, n)?;
1437        state.locked.fill(false);
1438        b.reuse(&mut state.table.0, buckets)?;
1439        state.table.fill(NONE);
1440        state.ac = ac;
1441        state.vertex_count = n;
1442        state.clamped = false;
1443        state.max_degree = 0;
1444        state.bytes = b.bytes;
1445        Ok(state)
1446    }
1447    fn adjacency<const WELD: bool>(
1448        &mut self,
1449        indices: &[u32],
1450        work: &mut impl Meter,
1451    ) -> Result<(), Error> {
1452        work.add(self.vertex_count)?;
1453        self.offsets.fill(0);
1454        let n = self.vertex_count;
1455        let counters = &mut self.offsets.0[1..][..n];
1456        let remap = &self.remap.0[..if WELD { n } else { 0 }];
1457        let edges = &mut self.edges[..indices.len()];
1458        work.scan(indices.iter().copied(), |i| {
1459            let v = if WELD {
1460                remap[i as usize] as usize
1461            } else {
1462                i as usize
1463            };
1464            counters[v] += 1;
1465            Ok(())
1466        })?;
1467        let mut offset = 0;
1468        let mut max_degree = 0;
1469        for v in counters.iter_mut() {
1470            let count = *v;
1471            *v = offset;
1472            offset += count;
1473            max_degree = max_degree.max(count);
1474        }
1475        self.max_degree = max_degree as usize;
1476        let triangles = indices.as_chunks::<3>().0;
1477        let charged = work.precharge(triangles.len(), 3)?;
1478        for t in triangles {
1479            if !charged {
1480                work.add(3)?;
1481            }
1482            let mut v = [t[0] as usize, t[1] as usize, t[2] as usize];
1483            if WELD {
1484                for x in &mut v {
1485                    *x = remap[*x] as usize;
1486                }
1487            }
1488            for e in 0..3 {
1489                let a = v[e];
1490                let offset = &mut counters[a];
1491                edges[*offset as usize] = Edge {
1492                    next: v[(e + 1) % 3] as u32,
1493                    prev: v[(e + 2) % 3] as u32,
1494                };
1495                *offset += 1;
1496            }
1497        }
1498        Ok(())
1499    }
1500    fn has_edge<const WELD: bool, M: Meter>(
1501        &self,
1502        a: usize,
1503        b: usize,
1504        work: &mut M,
1505    ) -> Result<bool, Error> {
1506        let mut v = a;
1507        loop {
1508            for e in &self.edges[self.offsets.get(v)..self.offsets.get(v + 1)] {
1509                work.add(1)?;
1510                if if WELD {
1511                    self.remap.get(e.next as usize) == self.remap.get(b)
1512                } else {
1513                    e.next as usize == b
1514                } {
1515                    return Ok(true);
1516                }
1517            }
1518            if !WELD {
1519                break;
1520            }
1521            v = self.wedge.get(v);
1522            if v == a {
1523                break;
1524            }
1525        }
1526        Ok(false)
1527    }
1528    fn position_remap(
1529        &mut self,
1530        p: Positions<'_>,
1531        work: &mut Work,
1532    ) -> Result<([f32; 3], [f32; 3]), Error> {
1533        if let Some((values, mapping)) = p.packed_source() {
1534            if let Some(mapping) = mapping {
1535                self.position_remap_kernel::<false>(
1536                    mapping.len(),
1537                    |i| Ok(values[mapping[i] as usize]),
1538                    work,
1539                )
1540            } else {
1541                self.position_remap_kernel::<false>(values.len(), |i| Ok(values[i]), work)
1542            }
1543        } else if let Some(mut records) = p.scale_full_records() {
1544            self.position_remap_kernel::<true>(
1545                p.len(),
1546                |_| Ok(records.next().expect("validated position count")),
1547                work,
1548            )
1549        } else {
1550            self.position_remap_kernel::<true>(p.len(), |i| p.at(i), work)
1551        }
1552    }
1553    fn position_remap_kernel<const CACHE_POSITIONS: bool>(
1554        &mut self,
1555        count: usize,
1556        mut read: impl FnMut(usize) -> Result<[f32; 3], Error>,
1557        work: &mut Work,
1558    ) -> Result<([f32; 3], [f32; 3]), Error> {
1559        let mask = self.table.len() - 1;
1560        // All three prefixes already have fallibly reserved capacity. Their
1561        // scratch writes are unobservable on failure: run_state drops the local
1562        // State. Fixed lengths remove growth checks from every vertex/probe.
1563        self.remap.0.resize(count, 0);
1564        self.wedge.0.resize(count, 0);
1565        if CACHE_POSITIONS {
1566            self.p.resize(count, V::default());
1567        }
1568        let remap = &mut self.remap.0[..count];
1569        let wedge = &mut self.wedge.0[..count];
1570        let positions = &mut self.p[..if CACHE_POSITIONS { count } else { 0 }];
1571        let table = &mut self.table.0[..];
1572        let mut lo = [f32::MAX; 3];
1573        let mut hi = [-f32::MAX; 3];
1574        // At most table.len() probes plus the initial read per vertex.
1575        // Batches keep the conservative bound useful for large real meshes.
1576        for start in (0..count).step_by(64) {
1577            let end = count.min(start.saturating_add(64));
1578            let bound = (end - start).checked_mul(mask + 2);
1579            metered!(work, bound, |work| (|| {
1580                for i in start..end {
1581                    work.add(1)?;
1582                    let v = read(i)?;
1583                    // The original bounds pass reads these same validated
1584                    // coordinates in this order. Only the reduction is fused;
1585                    // its charge and extent-error check remain after classify.
1586                    for j in 0..3 {
1587                        if lo[j] > v[j] {
1588                            lo[j] = v[j];
1589                        }
1590                        if hi[j] < v[j] {
1591                            hi[j] = v[j];
1592                        }
1593                    }
1594                    // The normalized-position allocation is already reserved. Until
1595                    // normalization, keep original coordinates here so hash probes do
1596                    // not repeatedly decode strided records. Every occupied entry was
1597                    // inserted by this or an earlier iteration; hash/probe order and
1598                    // counted visits are unchanged. Packed sources need no copy.
1599                    if CACHE_POSITIONS {
1600                        positions[i] = V::from(v);
1601                    }
1602                    let mut bits = v.map(|v| match v.to_bits() {
1603                        0x8000_0000 => 0,
1604                        bits => bits,
1605                    });
1606                    for x in &mut bits {
1607                        *x ^= *x >> 17;
1608                    }
1609                    let hash = bits[0].wrapping_mul(73856093)
1610                        ^ bits[1].wrapping_mul(19349663)
1611                        ^ bits[2].wrapping_mul(83492791);
1612                    let mut bucket = hash as usize & mask;
1613                    for probe in 0..=mask {
1614                        work.add(1)?;
1615                        let j = table[bucket] as usize;
1616                        if j == NONE {
1617                            table[bucket] = i as u32;
1618                            break;
1619                        }
1620                        let candidate = if CACHE_POSITIONS {
1621                            let p = positions[j];
1622                            [p.x, p.y, p.z]
1623                        } else {
1624                            read(j)?
1625                        };
1626                        if candidate == v {
1627                            break;
1628                        }
1629                        bucket = (bucket + probe + 1) & mask;
1630                    }
1631                    remap[i] = table[bucket];
1632                    wedge[i] = i as u32;
1633                }
1634                Ok(())
1635            })())?;
1636        }
1637        self.bytes -= self.table.0.capacity() * core::mem::size_of::<u32>();
1638        self.table.0 = Vec::new();
1639        let wedge = &mut self.wedge.0[..count];
1640        work.scan(self.remap.0[..count].iter().enumerate(), |(i, &r)| {
1641            let r = r as usize;
1642            if r != i {
1643                wedge[i] = wedge[r];
1644                wedge[r] = i as u32;
1645            }
1646            Ok(())
1647        })?;
1648        Ok((lo, hi))
1649    }
1650    // Visits without PERMISSIVE: each vertex and unwelded edge, an unwelded edge
1651    // search of at most max_degree per edge, and at most four further vertex
1652    // passes. PERMISSIVE welded searches have no cheap bound.
1653    fn classify_work(&self, edges: usize, options: SimplifyOptions) -> Option<usize> {
1654        if options.contains(SimplifyOptions::PERMISSIVE) {
1655            return None;
1656        }
1657        edges
1658            .checked_mul(self.max_degree.checked_add(1)?)?
1659            .checked_add(self.vertex_count.checked_mul(5)?)
1660    }
1661    fn classify<M: Meter>(
1662        &mut self,
1663        flags: Option<&[VertexFlags]>,
1664        options: SimplifyOptions,
1665        work: &mut M,
1666    ) -> Result<(), Error> {
1667        let n = self.vertex_count;
1668        // The initial adjacency is unwelded. Borrow its disjoint tables once,
1669        // and walk checked edge slices instead of reloading State for searches.
1670        let offsets = &self.offsets.0[..n + 1];
1671        let edges = &self.edges[..];
1672        let forward = &mut self.forward.0[..n];
1673        let back = &mut self.back.0[..n];
1674        for (i, range) in offsets.windows(2).enumerate() {
1675            work.add(1)?;
1676            for edge in &edges[range[0] as usize..range[1] as usize] {
1677                work.add(1)?;
1678                let t = edge.next as usize;
1679                if t == i {
1680                    forward[i] = i as u32;
1681                    back[i] = i as u32;
1682                } else {
1683                    let mut opposite = false;
1684                    for edge in &edges[offsets[t] as usize..offsets[t + 1] as usize] {
1685                        work.add(1)?;
1686                        if edge.next as usize == i {
1687                            opposite = true;
1688                            break;
1689                        }
1690                    }
1691                    if !opposite {
1692                        back[t] = if back[t] as usize == NONE { i } else { t } as u32;
1693                        forward[i] = if forward[i] as usize == NONE { t } else { i } as u32;
1694                    }
1695                }
1696            }
1697        }
1698        let remap = &self.remap.0[..n];
1699        let wedge = &self.wedge.0[..n];
1700        let kind = &mut self.kind[..n];
1701        for i in 0..n {
1702            work.add(1)?;
1703            kind[i] = if remap[i] as usize != i {
1704                kind[remap[i] as usize]
1705            } else if wedge[i] as usize == i {
1706                let a = back[i] as usize;
1707                let b = forward[i] as usize;
1708                if a == NONE && b == NONE {
1709                    MAN
1710                } else if a != NONE && b != NONE && remap[a] == remap[b] && a != i {
1711                    SEAM
1712                } else if a != i && b != i {
1713                    BORDER
1714                } else {
1715                    LOCKED
1716                }
1717            } else if wedge[wedge[i] as usize] as usize == i {
1718                let w = wedge[i] as usize;
1719                let a = back[i] as usize;
1720                let b = forward[i] as usize;
1721                let c = back[w] as usize;
1722                let d = forward[w] as usize;
1723                if a != NONE
1724                    && a != i
1725                    && b != NONE
1726                    && b != i
1727                    && c != NONE
1728                    && c != w
1729                    && d != NONE
1730                    && d != w
1731                    && remap[a] == remap[d]
1732                    && remap[b] == remap[c]
1733                    && remap[a] != remap[b]
1734                {
1735                    SEAM
1736                } else {
1737                    LOCKED
1738                }
1739            } else {
1740                LOCKED
1741            };
1742        }
1743        if options.contains(SimplifyOptions::PERMISSIVE) {
1744            for i in 0..n {
1745                work.add(1)?;
1746                if self.kind[i] != SEAM && self.kind[i] != LOCKED {
1747                    continue;
1748                }
1749                if self.remap.get(i) != i {
1750                    self.kind[i] = self.kind[self.remap.get(i)];
1751                    continue;
1752                }
1753                let mut protect = false;
1754                let mut border = false;
1755                let mut v = i;
1756                loop {
1757                    work.add(1)?;
1758                    protect |= flag(flags, v, VertexFlags::PROTECT);
1759                    for j in self.offsets.get(v)..self.offsets.get(v + 1) {
1760                        work.add(1)?;
1761                        border |=
1762                            !self.has_edge::<true, M>(self.edges[j].next as usize, v, work)?;
1763                    }
1764                    v = self.wedge.get(v);
1765                    if v == i {
1766                        break;
1767                    }
1768                }
1769                if !protect {
1770                    self.kind[i] = if border { FRINGE } else { COMPLEX };
1771                }
1772            }
1773        }
1774        if let Some(flags) = flags {
1775            for (i, &f) in flags.iter().enumerate() {
1776                work.add(1)?;
1777                if f.contains(VertexFlags::LOCK) {
1778                    self.kind[self.remap.get(i)] = LOCKED;
1779                }
1780            }
1781            for i in 0..n {
1782                work.add(1)?;
1783                if self.kind[self.remap.get(i)] == LOCKED {
1784                    self.kind[i] = LOCKED;
1785                }
1786            }
1787        }
1788        if options.contains(SimplifyOptions::LOCK_BORDER) {
1789            for k in &mut self.kind {
1790                work.add(1)?;
1791                if *k == BORDER || *k == FRINGE {
1792                    *k = LOCKED;
1793                }
1794            }
1795        }
1796        Ok(())
1797    }
1798}
1799fn flag(flags: Option<&[VertexFlags]>, i: usize, f: VertexFlags) -> bool {
1800    flags.is_some_and(|flags| flags[i].contains(f))
1801}
1802#[inline(always)]
1803fn attribute_gradient(q: &mut Q, values: [f32; 3], p0: V, basis: [V; 2], w: f32) -> G {
1804    let [a0, a1, a2] = values;
1805    let gx = basis[0].x * (a1 - a0) + basis[1].x * (a2 - a0);
1806    let gy = basis[0].y * (a1 - a0) + basis[1].y * (a2 - a0);
1807    let gz = basis[0].z * (a1 - a0) + basis[1].z * (a2 - a0);
1808    let gw = a0 - p0.x * gx - p0.y * gy - p0.z * gz;
1809    q.a00 += w * (gx * gx);
1810    q.a11 += w * (gy * gy);
1811    q.a22 += w * (gz * gz);
1812    q.a10 += w * (gy * gx);
1813    q.a20 += w * (gz * gx);
1814    q.a21 += w * (gz * gy);
1815    q.b0 += w * (gx * gw);
1816    q.b1 += w * (gy * gw);
1817    q.b2 += w * (gz * gw);
1818    q.c += w * (gw * gw);
1819    G {
1820        x: w * gx,
1821        y: w * gy,
1822        z: w * gz,
1823        w: w * gw,
1824    }
1825}
1826fn record_triplet<T>(
1827    records: &mut [T],
1828    width: usize,
1829    indices: [usize; 3],
1830) -> Option<[&mut [T]; 3]> {
1831    let [a, b, c] = indices;
1832    if a == b || a == c || b == c {
1833        return None;
1834    }
1835    records
1836        .get_disjoint_mut([
1837            a * width..(a + 1) * width,
1838            b * width..(b + 1) * width,
1839            c * width..(c + 1) * width,
1840        ])
1841        .ok()
1842}
1843impl State {
1844    fn attribute_quadric(&mut self, t: [usize; 3]) -> Q {
1845        let [i0, i1, i2] = t;
1846        let p0 = self.p[i0];
1847        let v0 = self.p[i1].sub(p0);
1848        let v1 = self.p[i2].sub(p0);
1849        let normal = v0.cross(v1);
1850        let w = self.sqrt_cache.sqrt(normal.dot(normal)) * 0.5;
1851        let d00 = v0.dot(v0);
1852        let d01 = v0.dot(v1);
1853        let d11 = v1.dot(v1);
1854        let denom = d00 * d11 - d01 * d01;
1855        let dr = if denom == 0.0 { 0.0 } else { 1.0 / denom };
1856        let gx1 = (d11 * v0.x - d01 * v1.x) * dr;
1857        let gx2 = (d00 * v1.x - d01 * v0.x) * dr;
1858        let gy1 = (d11 * v0.y - d01 * v1.y) * dr;
1859        let gy2 = (d00 * v1.y - d01 * v0.y) * dr;
1860        let gz1 = (d11 * v0.z - d01 * v1.z) * dr;
1861        let gz2 = (d00 * v1.z - d01 * v0.z) * dr;
1862        let mut q = Q { w, ..Q::default() };
1863        let attributes0 = &self.a[i0 * self.ac..][..self.ac];
1864        let attributes1 = &self.a[i1 * self.ac..][..self.ac];
1865        let attributes2 = &self.a[i2 * self.ac..][..self.ac];
1866        let basis = [
1867            V {
1868                x: gx1,
1869                y: gy1,
1870                z: gz1,
1871            },
1872            V {
1873                x: gx2,
1874                y: gy2,
1875                z: gz2,
1876            },
1877        ];
1878        if let Some([g0, g1, g2]) = record_triplet(&mut self.g, self.ac, t) {
1879            for (((&a0, &a1), &a2), ((g0, g1), g2)) in attributes0
1880                .iter()
1881                .zip(attributes1)
1882                .zip(attributes2)
1883                .zip(g0.iter_mut().zip(g1).zip(g2))
1884            {
1885                let g = attribute_gradient(&mut q, [a0, a1, a2], p0, basis, w);
1886                g0.add(g);
1887                g1.add(g);
1888                g2.add(g);
1889            }
1890        } else {
1891            for (k, ((&a0, &a1), &a2)) in attributes0
1892                .iter()
1893                .zip(attributes1)
1894                .zip(attributes2)
1895                .enumerate()
1896            {
1897                let g = attribute_gradient(&mut q, [a0, a1, a2], p0, basis, w);
1898                for i in t {
1899                    self.g[i * self.ac + k].add(g);
1900                }
1901            }
1902        }
1903        q
1904    }
1905    fn quadrics<M: Meter>(
1906        &mut self,
1907        indices: &[u32],
1908        flags: Option<&[VertexFlags]>,
1909        options: SimplifyOptions,
1910        work: &mut M,
1911    ) -> Result<(), Error> {
1912        let n = self.p.len();
1913        let p = &self.p[..n];
1914        let remap = &self.remap.0[..n];
1915        let qv = &mut self.q[..n];
1916        let kind = &self.kind[..n];
1917        let forward = &self.forward.0[..n];
1918        let back = &self.back.0[..n];
1919        let triangles = indices.as_chunks::<3>().0;
1920        let charged = work.precharge(triangles.len(), 3)?;
1921        for t in triangles {
1922            if !charged {
1923                work.add(3)?;
1924            }
1925            let [a, b, c] = [t[0] as usize, t[1] as usize, t[2] as usize];
1926            let mut normal = p[b].sub(p[a]).cross(p[c].sub(p[a]));
1927            let area = normal.normalize(&mut self.sqrt_cache);
1928            let q = Q::plane(normal, -normal.dot(p[a]), self.sqrt_cache.sqrt(area) * 1.0);
1929            for i in [a, b, c] {
1930                qv[remap[i] as usize].add(q);
1931            }
1932            if !self.vg.is_empty() {
1933                // The volume gradient uses the same normalized triangle plane.
1934                let area = area * 0.5;
1935                let g = G {
1936                    x: normal.x * area,
1937                    y: normal.y * area,
1938                    z: normal.z * area,
1939                    w: (-p[a].x * normal.x - p[a].y * normal.y - p[a].z * normal.z) * area,
1940                };
1941                for i in [a, b, c] {
1942                    self.vg[remap[i] as usize].add(g);
1943                }
1944            }
1945        }
1946        let factor = if options.contains(SimplifyOptions::REGULARIZE_LIGHT) {
1947            1e-2
1948        } else if options.contains(SimplifyOptions::REGULARIZE) {
1949            1e-1
1950        } else {
1951            1e-7
1952        };
1953        work.scan(
1954            qv.iter_mut().zip(p).zip(remap).enumerate(),
1955            |(i, ((q, &position), &r))| {
1956                if r as usize == i {
1957                    let w = q.w
1958                        * if flag(flags, i, VertexFlags::PRIORITY) {
1959                            1.0
1960                        } else {
1961                            factor
1962                        };
1963                    q.add(Q::point(position, w));
1964                }
1965                Ok(())
1966            },
1967        )?;
1968        let charged_edges = work.precharge(indices.len(), 1)?;
1969        for t in indices.as_chunks::<3>().0 {
1970            for e in 0..3 {
1971                if !charged_edges {
1972                    work.add(1)?;
1973                }
1974                let a = t[e] as usize;
1975                let b = t[(e + 1) % 3] as usize;
1976                let c = t[(e + 2) % 3] as usize;
1977                let k0 = kind[a];
1978                let k1 = kind[b];
1979                if k0 == MAN || k1 == MAN {
1980                    continue;
1981                }
1982                // A pattern test; slice `contains` on bytes calls the memchr scan.
1983                if !matches!(k0, BORDER | SEAM | FRINGE) && !matches!(k1, BORDER | SEAM | FRINGE) {
1984                    continue;
1985                }
1986                if (k0 == BORDER || k0 == SEAM) && forward[a] as usize != b {
1987                    continue;
1988                }
1989                if (k1 == BORDER || k1 == SEAM) && back[b] as usize != a {
1990                    continue;
1991                }
1992                if (k0 == FRINGE || k1 == FRINGE) && (k0 == COMPLEX || k1 == COMPLEX) {
1993                    continue;
1994                }
1995                let w = if k0 == SEAM || k1 == SEAM { 0.5 } else { 10.0 };
1996                let mut q = Q::edge(p[a], p[b], p[c], w, &mut self.sqrt_cache);
1997                let mut qt = Q::triangle(p[a], p[b], p[c], w, &mut self.sqrt_cache);
1998                qt.w = 0.0;
1999                q.add(qt);
2000                qv[remap[a] as usize].add(q);
2001                qv[remap[b] as usize].add(q);
2002            }
2003        }
2004        if self.ac > 0 {
2005            let units = 3 + self.ac * 3;
2006            let charged = work.precharge(triangles.len(), units)?;
2007            for t in triangles {
2008                if !charged {
2009                    work.add(units)?;
2010                }
2011                let t = [t[0] as usize, t[1] as usize, t[2] as usize];
2012                let q = self.attribute_quadric(t);
2013                for i in t {
2014                    self.aq[i].add(q);
2015                }
2016            }
2017        }
2018        if options.bits() & 128 != 0 {
2019            extra::fold_quadrics(self, work)?;
2020        }
2021        // Normalization bounds positional quadric accumulation (see
2022        // parity/0215-contract-simplify/PROOFS.md). Attribute and gradient checks remain before any use.
2023        // Reciprocal overflow is still checked only when its error is ranked.
2024        for q in &mut self.q {
2025            q.cache_inverse_weight();
2026        }
2027        // The same predicate as testing each quadric and gradient: no field
2028        // of either table is non-finite. Field-wise maxima have no early
2029        // exit, so the scans vectorize; neither has side effects.
2030        // Each lane sums `x * 0.0`: exactly a signed zero for finite `x` and
2031        // NaN for infinite or NaN `x`, and NaN persists through the sum, so a
2032        // lane ends NaN exactly when one of its values is non-finite. Lane 11
2033        // adds the constant 0, never `inverse_weight`. Lanes of one record
2034        // are independent, so each record's update is a few vector ops.
2035        let aq = self.aq.iter().fold([0.0f32; 12], |mut m, q| {
2036            let f = q.fields();
2037            let f = [
2038                f[0], f[1], f[2], f[3], f[4], f[5], f[6], f[7], f[8], f[9], f[10], 0.0,
2039            ];
2040            for (m, x) in m.iter_mut().zip(f) {
2041                *m += x * 0.0;
2042            }
2043            m
2044        });
2045        let g = self.g.iter().fold([0.0f32; 4], |mut m, g| {
2046            for (m, x) in m.iter_mut().zip([g.x, g.y, g.z, g.w]) {
2047                *m += x * 0.0;
2048            }
2049            m
2050        });
2051        if aq.into_iter().chain(g).any(|lane| lane.is_nan()) {
2052            return Err(Error::NumericalFailure);
2053        }
2054        Ok(())
2055    }
2056    // Visits at most one per index.
2057    fn pick<M: Meter>(
2058        &mut self,
2059        indices: &[u32],
2060        capacity: usize,
2061        work: &mut M,
2062    ) -> Result<usize, Error> {
2063        let mut count = 0;
2064        // Disjoint borrows keep table bases in registers across pushes.
2065        // State::new initializes all four tables to the active vertex count.
2066        // Sharing the slice length lets one corner check cover every table.
2067        let n = self.vertex_count;
2068        let remap = &self.remap.0[..n];
2069        let kind = &self.kind[..n];
2070        let forward = &self.forward.0[..n];
2071        let back = &self.back.0[..n];
2072        let collapses = &mut self.collapses;
2073        collapses.clear();
2074        // A prepaid meter cannot fail, and every entered triangle visits all
2075        // three corners: count triangles and charge three visits each once.
2076        let mut entered = 0;
2077        for t in indices.as_chunks::<3>().0 {
2078            if count + 3 > capacity {
2079                break;
2080            }
2081            entered += 1;
2082            for e in 0..3 {
2083                if !M::PREPAID {
2084                    work.add(1)?;
2085                }
2086                let a = t[e] as usize;
2087                let b = t[(e + 1) % 3] as usize;
2088                let ra = remap[a];
2089                let rb = remap[b];
2090                if ra == rb {
2091                    continue;
2092                }
2093                let rule = PICK[pair(kind[a], kind[b])];
2094                if rule & PICK_ANY == 0 {
2095                    continue;
2096                }
2097                if rule & PICK_OPPOSITE != 0 && rb > ra {
2098                    continue;
2099                }
2100                if rule & PICK_CHECK_FORWARD != 0 && forward[a] as usize != b {
2101                    continue;
2102                }
2103                if rule & PICK_CHECK_BACK != 0 && back[b] as usize != a {
2104                    continue;
2105                }
2106                collapses.push(if rule & PICK_BOTH != 0 {
2107                    Collapse {
2108                        a: a as u32,
2109                        b: b as u32,
2110                        error: f32::from_bits(1),
2111                    }
2112                } else if rule & PICK_FORWARD != 0 {
2113                    Collapse {
2114                        a: a as u32,
2115                        b: b as u32,
2116                        ..Collapse::default()
2117                    }
2118                } else {
2119                    Collapse {
2120                        a: b as u32,
2121                        b: a as u32,
2122                        ..Collapse::default()
2123                    }
2124                });
2125                count += 1;
2126            }
2127        }
2128        if M::PREPAID {
2129            work.add(entered * 3)?;
2130        }
2131        Ok(count)
2132    }
2133    fn complex_target(&self, v: usize, t: usize) -> usize {
2134        let r = self.remap.get(t);
2135        if self.forward.get(v) != NONE && self.remap.get(self.forward.get(v)) == r {
2136            self.forward.get(v)
2137        } else if self.back.get(v) != NONE && self.remap.get(self.back.get(v)) == r {
2138            self.back.get(v)
2139        } else {
2140            t
2141        }
2142    }
2143    fn seam_target(&self, a: usize, b: usize) -> (usize, usize) {
2144        let s0 = self.wedge.get(a);
2145        let s1 = if self.forward.get(a) == b {
2146            self.back.get(s0)
2147        } else {
2148            self.forward.get(s0)
2149        };
2150        (s0, if s1 != NONE { s1 } else { self.wedge.get(b) })
2151    }
2152    fn rank(&mut self, count: usize, work: &mut Work) -> Result<(), Error> {
2153        if self.ac == 0 {
2154            // All three vertex tables have the same length. Re-borrow that
2155            // common prefix once, and iterate the initialized candidate slice.
2156            let n = self.p.len();
2157            let p = &self.p[..n];
2158            let q = &self.q[..n];
2159            let remap = &self.remap.0[..n];
2160            #[inline(always)]
2161            fn rank_one(c: &mut Collapse, p: &[V], q: &[Q], remap: &[u32]) -> Result<(), Error> {
2162                let a = c.a as usize;
2163                let b = c.b as usize;
2164                let bidirectional = c.error.to_bits() != 0;
2165                let ei = q[remap[a] as usize].error(p[b]);
2166                let ej = if bidirectional {
2167                    q[remap[b] as usize].error(p[a])
2168                } else {
2169                    f32::MAX
2170                };
2171                if !(ei.is_finite() & ej.is_finite()) {
2172                    return Err(Error::NumericalFailure);
2173                }
2174                if bidirectional && ej < ei {
2175                    core::mem::swap(&mut c.a, &mut c.b);
2176                }
2177                c.error = if ej < ei { ej } else { ei };
2178                Ok(())
2179            }
2180            let values = &mut self.collapses[..count];
2181            return if work.covers(count)? {
2182                for (i, c) in values.iter_mut().enumerate() {
2183                    if let Err(error) = rank_one(c, p, q, remap) {
2184                        work.add(i + 1)?;
2185                        return Err(error);
2186                    }
2187                }
2188                work.add(count)
2189            } else {
2190                for c in values {
2191                    work.add(1)?;
2192                    rank_one(c, p, q, remap)?;
2193                }
2194                Ok(())
2195            };
2196        }
2197        // One candidate visit, 2ac base visits and at most two n-entry
2198        // wedge traversals (the seam branch uses only 2ac additional visits).
2199        let per_candidate = self
2200            .vertex_count
2201            .checked_add(1)
2202            .and_then(|n| self.ac.checked_mul(2)?.checked_mul(n))
2203            .and_then(|n| n.checked_add(1));
2204        for start in (0..count).step_by(64) {
2205            let end = count.min(start.saturating_add(64));
2206            let bound = per_candidate.and_then(|n| n.checked_mul(end - start));
2207            metered!(work, bound, |w| self.rank_attributes(start..end, w))?;
2208        }
2209        Ok(())
2210    }
2211    fn rank_attributes<M: Meter>(
2212        &mut self,
2213        range: core::ops::Range<usize>,
2214        work: &mut M,
2215    ) -> Result<(), Error> {
2216        for i in range {
2217            work.add(1)?;
2218            let c = self.collapses[i];
2219            let a = c.a as usize;
2220            let b = c.b as usize;
2221            let mut ei = self.q[self.remap.get(a)].error(self.p[b]);
2222            let mut ej = if c.error.to_bits() != 0 {
2223                self.q[self.remap.get(b)].error(self.p[a])
2224            } else {
2225                f32::MAX
2226            };
2227            if self.ac > 0 {
2228                work.add(self.ac * 2)?;
2229                ei += self.attribute_error(a, b);
2230                ej += if c.error.to_bits() != 0 {
2231                    self.attribute_error(b, a)
2232                } else {
2233                    0.0
2234                };
2235                if self.kind[a] == SEAM {
2236                    work.add(self.ac * 2)?;
2237                    let (s0, s1) = self.seam_target(a, b);
2238                    ei += self.attribute_error(s0, s1);
2239                    ej += if c.error.to_bits() != 0 {
2240                        self.attribute_error(s1, s0)
2241                    } else {
2242                        0.0
2243                    };
2244                } else {
2245                    if self.kind[a] == COMPLEX || self.kind[a] == FRINGE {
2246                        let mut v = self.wedge.get(a);
2247                        while v != a {
2248                            work.add(self.ac)?;
2249                            ei += self.attribute_error(v, self.complex_target(v, b));
2250                            v = self.wedge.get(v);
2251                        }
2252                    }
2253                    if (self.kind[b] == COMPLEX || self.kind[b] == FRINGE)
2254                        && (c.error.to_bits() != 0)
2255                    {
2256                        let mut v = self.wedge.get(b);
2257                        while v != b {
2258                            work.add(self.ac)?;
2259                            ej += self.attribute_error(v, self.complex_target(v, a));
2260                            v = self.wedge.get(v);
2261                        }
2262                    }
2263                }
2264            }
2265            if !(ei.is_finite() & ej.is_finite()) {
2266                return Err(Error::NumericalFailure);
2267            }
2268            let rev = (c.error.to_bits() != 0) && ej < ei;
2269            self.collapses[i] = Collapse {
2270                a: (if rev { b } else { a }) as u32,
2271                b: (if rev { a } else { b }) as u32,
2272                error: if ej < ei { ej } else { ei },
2273            };
2274        }
2275        Ok(())
2276    }
2277    #[inline(always)]
2278    fn attribute_error(&self, source: usize, target: usize) -> f32 {
2279        let v = self.p[target];
2280        let q = self.aq[source];
2281        let mut r = q.eval(v);
2282        let attributes = &self.a[target * self.ac..][..self.ac];
2283        let gradients = &self.g[source * self.ac..][..self.ac];
2284        let term = |a: f32, g: G| {
2285            let g = v.x * g.x + v.y * g.y + v.z * g.z + g.w;
2286            a * (a * q.w - 2.0 * g)
2287        };
2288        let (a4, at) = attributes.as_chunks::<4>();
2289        let (g4, gt) = gradients.as_chunks::<4>();
2290        for (a, g) in a4.iter().zip(g4) {
2291            // Independent terms can vectorize; accumulation remains in the
2292            // exact upstream component order, with no horizontal reduction.
2293            let terms = [
2294                term(a[0], g[0]),
2295                term(a[1], g[1]),
2296                term(a[2], g[2]),
2297                term(a[3], g[3]),
2298            ];
2299            for t in terms {
2300                r += t;
2301            }
2302        }
2303        for (&a, &g) in at.iter().zip(gt) {
2304            r += term(a, g);
2305        }
2306        let e = r.abs();
2307        if self.clamped && e >= q.w {
2308            q.w
2309        } else {
2310            e
2311        }
2312    }
2313    fn sort(&mut self, count: usize, work: &mut Work) -> Result<(), Error> {
2314        // pick emits at most one candidate per input index; topology already
2315        // bounds that count by u32::MAX. Match upstream's bucket storage width.
2316        let mut h = [0u32; 2560];
2317        let collapses = &self.collapses[..count];
2318        work.scan(collapses.iter(), |c| {
2319            h[sort_key(c.error)] += 1;
2320            Ok(())
2321        })?;
2322        let mut sum = 0;
2323        for v in &mut h {
2324            let n = *v;
2325            *v = sum as u32;
2326            sum += n as usize;
2327        }
2328        let order = &mut self.order.0[..count];
2329        work.scan(collapses.iter().enumerate(), |(i, c)| {
2330            let k = sort_key(c.error);
2331            order[h[k] as usize] = i as u32;
2332            h[k] += 1;
2333            Ok(())
2334        })?;
2335        Ok(())
2336    }
2337    fn flips<M: Meter>(&mut self, a: usize, b: usize, work: &mut M) -> Result<bool, Error> {
2338        for e in &self.edges[self.offsets.get(a)..self.offsets.get(a + 1)] {
2339            work.add(1)?;
2340            let x = self.cr.get(e.next as usize);
2341            let y = self.cr.get(e.prev as usize);
2342            if x == b || y == b || x == y {
2343                continue;
2344            }
2345            let pa = self.p[x];
2346            let eb = self.p[y].sub(pa);
2347            let ec = self.p[a].sub(pa);
2348            let ed = self.p[b].sub(pa);
2349            let nbc = eb.cross(ec);
2350            let nbd = eb.cross(ed);
2351            if nbc.dot(nbd) <= 0.25 * self.sqrt_cache.sqrt(nbc.dot(nbc) * nbd.dot(nbd)) {
2352                return Ok(true);
2353            }
2354        }
2355        Ok(false)
2356    }
2357    // Visits: the vertex reset, then per candidate one visit and a flip check
2358    // of at most max_degree edges. PERMISSIVE wedge walks are not bounded here.
2359    fn perform_work(&self, count: usize, options: SimplifyOptions) -> Option<usize> {
2360        if options.contains(SimplifyOptions::PERMISSIVE) {
2361            return None;
2362        }
2363        count
2364            .checked_mul(self.max_degree.checked_add(1)?)?
2365            .checked_add(self.p.len())
2366    }
2367    fn perform<M: Meter>(
2368        &mut self,
2369        count: usize,
2370        goal: usize,
2371        limit: f32,
2372        error: &mut f32,
2373        work: &mut M,
2374    ) -> Result<(usize, bool), Error> {
2375        let n = self.p.len();
2376        let mut error_limited = false;
2377        work.scan(
2378            self.cr.0[..n]
2379                .iter_mut()
2380                .zip(&mut self.locked[..n])
2381                .enumerate(),
2382            |(i, (remap, locked))| {
2383                *remap = i as u32;
2384                *locked = false;
2385                Ok(())
2386            },
2387        )?;
2388        let mut edges = 0;
2389        let mut triangles = 0;
2390        let mut edge_goal = goal / 2;
2391        for i in 0..count {
2392            work.add(1)?;
2393            let c = self.collapses[self.order.get(i)];
2394            if c.error > limit || triangles >= goal {
2395                error_limited = c.error > limit && triangles < goal;
2396                break;
2397            }
2398            let error_goal = if edge_goal < count {
2399                1.5 * self.collapses[self.order.get(edge_goal)].error
2400            } else {
2401                f32::MAX
2402            };
2403            if c.error > error_goal && c.error > *error && triangles > goal / 6 {
2404                break;
2405            }
2406            let a = c.a as usize;
2407            let b = c.b as usize;
2408            let r0 = self.remap.get(a);
2409            let r1 = self.remap.get(b);
2410            let kind = self.kind[a];
2411            if self.locked[r0] || self.locked[r1] {
2412                continue;
2413            }
2414            if self.flips(r0, r1, work)? {
2415                edge_goal += 1;
2416                continue;
2417            }
2418            self.cr.set(a, b);
2419            if kind == COMPLEX || kind == FRINGE {
2420                let mut v = self.wedge.get(a);
2421                while v != a {
2422                    work.add(1)?;
2423                    self.cr.set(v, self.complex_target(v, b));
2424                    v = self.wedge.get(v);
2425                }
2426            } else if kind == SEAM {
2427                let (s0, s1) = self.seam_target(a, b);
2428                self.cr.set(s0, s1);
2429            }
2430            self.locked[r0] = true;
2431            self.locked[r1] = true;
2432            triangles += if kind == BORDER { 1 } else { 2 };
2433            edges += 1;
2434            if *error < c.error {
2435                *error = c.error;
2436            }
2437        }
2438        Ok((edges, error_limited))
2439    }
2440    fn update<M: Meter>(&mut self, vertex_error: &mut f32, work: &mut M) -> Result<(), Error> {
2441        let n = self.p.len();
2442        let cr = &self.cr.0[..n];
2443        let remap = &self.remap.0[..n];
2444        if self.ac == 0 && self.vg.is_empty() {
2445            // Positional updates need no attribute/volume tables. A shared
2446            // vertex prefix keeps their bounds and bases outside the loop.
2447            let quadrics = &mut self.q[..n];
2448            // One visit per vertex. A prepaid meter cannot fail: it is charged
2449            // the visited prefix once, on error or after the pass.
2450            for (i, &target) in cr.iter().enumerate() {
2451                if !M::PREPAID {
2452                    work.add(1)?;
2453                }
2454                let t = target as usize;
2455                if t == i {
2456                    continue;
2457                }
2458                let r0 = remap[i] as usize;
2459                let r1 = remap[t] as usize;
2460                if i == r0 {
2461                    let q = quadrics[r0];
2462                    let destination = &mut quadrics[r1];
2463                    destination.add(q);
2464                    if !destination.finite() {
2465                        if M::PREPAID {
2466                            work.add(i + 1)?;
2467                        }
2468                        return Err(Error::NumericalFailure);
2469                    }
2470                    destination.cache_inverse_weight();
2471                }
2472            }
2473            if M::PREPAID {
2474                work.add(n)?;
2475            }
2476        } else {
2477            for i in 0..self.p.len() {
2478                work.add(1)?;
2479                let t = self.cr.get(i);
2480                if t == i {
2481                    continue;
2482                }
2483                let r0 = self.remap.get(i);
2484                let r1 = self.remap.get(t);
2485                if i == r0 {
2486                    let q = self.q[r0];
2487                    self.q[r1].add(q);
2488                    if !self.q[r1].finite() {
2489                        return Err(Error::NumericalFailure);
2490                    }
2491                    self.q[r1].cache_inverse_weight();
2492                    if !self.vg.is_empty() {
2493                        let g = self.vg[r0];
2494                        self.vg[r1].add(g);
2495                    }
2496                }
2497                if self.ac > 0 {
2498                    if i == r0 {
2499                        let e = self.q[r0].error(self.p[r1]);
2500                        if *vertex_error < e {
2501                            *vertex_error = e;
2502                        }
2503                    }
2504                    work.add(self.ac)?;
2505                    let q = self.aq[i];
2506                    self.aq[t].add(q);
2507                    if !self.aq[t].finite() {
2508                        return Err(Error::NumericalFailure);
2509                    }
2510                    for k in 0..self.ac {
2511                        let g = self.g[i * self.ac + k];
2512                        self.g[t * self.ac + k].add(g);
2513                    }
2514                }
2515            }
2516        }
2517        // Two infallible passes of one visit per vertex.
2518        if M::PREPAID {
2519            work.add(n * 2)?;
2520        }
2521        for loops in [&mut self.forward.0[..n], &mut self.back.0[..n]] {
2522            for i in 0..n {
2523                if !M::PREPAID {
2524                    work.add(1)?;
2525                }
2526                let l = loops[i] as usize;
2527                if l != NONE {
2528                    let r = cr[l] as usize;
2529                    loops[i] = if i == r {
2530                        let next = loops[l] as usize;
2531                        if next != NONE {
2532                            cr[next]
2533                        } else {
2534                            NONE as u32
2535                        }
2536                    } else {
2537                        r as u32
2538                    };
2539                }
2540            }
2541        }
2542        Ok(())
2543    }
2544}
2545fn sort_key(error: f32) -> usize {
2546    ((error.to_bits() << 1) >> 20).min(2559) as usize
2547}
2548#[allow(clippy::too_many_arguments)]
2549fn run(
2550    out: &mut [u32],
2551    indices: &[u32],
2552    positions: Positions<'_>,
2553    attributes: Option<Attributes<'_>>,
2554    weights: &[f32],
2555    flags: Option<&[VertexFlags]>,
2556    settings: SimplifySettings,
2557    ws: &mut Workspace,
2558    work: &mut Work,
2559    output: usize,
2560) -> Result<SimplifyResult, Error> {
2561    let (result, state, _) = run_state(
2562        out,
2563        Input::borrowed(indices),
2564        positions,
2565        attributes,
2566        weights,
2567        flags,
2568        settings,
2569        ws,
2570        work,
2571        output,
2572        false,
2573    )?;
2574    state.retain(ws);
2575    Ok(result)
2576}
2577/// One exactly when `x` is infinite or NaN (all exponent bits set), the
2578/// `!x.is_finite()` predicate as an integer that SSE2 can compare and OR.
2579#[inline(always)]
2580fn nonfinite(x: f32) -> u32 {
2581    u32::from(x.to_bits() & 0x7f80_0000 == 0x7f80_0000)
2582}
2583/// Whether any value is non-finite; no early exit, so the scan vectorizes.
2584#[inline(always)]
2585fn any_nonfinite(values: &[f32]) -> bool {
2586    values.iter().fold(0, |a, &x| a | nonfinite(x)) != 0
2587}
2588/// Index of the first vertex with a non-finite position or attribute
2589/// component, or the vertex count. `records` holds `width` components per
2590/// vertex for every vertex of `positions`.
2591fn first_nonfinite_vertex(positions: &[[f32; 3]], records: &[f32], width: usize) -> usize {
2592    if !any_nonfinite(positions.as_flattened()) && !any_nonfinite(records) {
2593        return positions.len();
2594    }
2595    (0..positions.len())
2596        .find(|&i| any_nonfinite(&positions[i]) || any_nonfinite(&records[i * width..][..width]))
2597        .unwrap_or(positions.len())
2598}
2599#[inline(always)]
2600fn prepaid<M: Meter>(_: &M) -> bool {
2601    M::PREPAID
2602}
2603/// Normalize leading vertices exactly as the checked loop in `run_state`
2604/// does, stopping before the first vertex that loop rejects; returns the
2605/// number written. `source` is `None` when `positions` already holds the
2606/// coordinates; `records` holds `weights.len()` components per vertex, and
2607/// every weight is positive, so row `i` of `attributes` is the products.
2608#[allow(clippy::too_many_arguments)]
2609fn normalize_prefix(
2610    positions: &mut [V],
2611    attributes: &mut [f32],
2612    source: Option<&[[f32; 3]]>,
2613    records: &[f32],
2614    weights: &[f32],
2615    lo: [f32; 3],
2616    scale: f32,
2617    finite_scale: bool,
2618) -> usize {
2619    // Fixed widths unroll each row; every instance computes the same values.
2620    macro_rules! fixed {
2621        ($($w:literal)*) => {
2622            match weights.len() {
2623                $($w => {
2624                    return normalize_rows::<$w>(
2625                        positions, attributes, source, records, weights, lo, scale, finite_scale,
2626                    )
2627                })*
2628                _ => {}
2629            }
2630        };
2631    }
2632    fixed!(1 2 3 4 5 6 7 8);
2633    let width = weights.len();
2634    for (i, destination) in positions.iter_mut().enumerate() {
2635        let normalized = normalized_position(source, i, destination, lo, scale);
2636        if !finite_scale && any_nonfinite(&[normalized.x, normalized.y, normalized.z]) {
2637            return i;
2638        }
2639        let values = &records[i * width..][..width];
2640        let bad = values
2641            .iter()
2642            .zip(weights)
2643            .fold(0, |bad, (&value, &weight)| bad | nonfinite(value * weight));
2644        if bad != 0 {
2645            return i;
2646        }
2647        *destination = normalized;
2648        let row = &mut attributes[i * width..][..width];
2649        for ((d, &value), &weight) in row.iter_mut().zip(values).zip(weights) {
2650            *d = value * weight;
2651        }
2652    }
2653    positions.len()
2654}
2655#[inline(always)]
2656fn normalized_position(
2657    source: Option<&[[f32; 3]]>,
2658    i: usize,
2659    cached: &V,
2660    lo: [f32; 3],
2661    scale: f32,
2662) -> V {
2663    let p = match source {
2664        Some(source) => source[i],
2665        None => [cached.x, cached.y, cached.z],
2666    };
2667    V {
2668        x: (p[0] - lo[0]) * scale,
2669        y: (p[1] - lo[1]) * scale,
2670        z: (p[2] - lo[2]) * scale,
2671    }
2672}
2673/// `normalize_prefix` for `W == weights.len()` components per vertex.
2674#[allow(clippy::too_many_arguments)]
2675fn normalize_rows<const W: usize>(
2676    positions: &mut [V],
2677    attributes: &mut [f32],
2678    source: Option<&[[f32; 3]]>,
2679    records: &[f32],
2680    weights: &[f32],
2681    lo: [f32; 3],
2682    scale: f32,
2683    finite_scale: bool,
2684) -> usize {
2685    let (Some(weights), (records, _), (rows, _)) = (
2686        weights.first_chunk::<W>(),
2687        records.as_chunks::<W>(),
2688        attributes.as_chunks_mut::<W>(),
2689    ) else {
2690        return 0;
2691    };
2692    for (i, destination) in positions.iter_mut().enumerate() {
2693        let normalized = normalized_position(source, i, destination, lo, scale);
2694        if !finite_scale && any_nonfinite(&[normalized.x, normalized.y, normalized.z]) {
2695            return i;
2696        }
2697        let values = records[i];
2698        let products: [f32; W] = core::array::from_fn(|k| values[k] * weights[k]);
2699        if any_nonfinite(&products) {
2700            return i;
2701        }
2702        *destination = normalized;
2703        rows[i] = products;
2704    }
2705    positions.len()
2706}
2707#[inline(always)]
2708fn normalize_attribute_row<M: Meter>(
2709    destination: &mut [f32],
2710    source: Attributes<'_>,
2711    vertex: usize,
2712    weights: &[f32],
2713    work: &mut M,
2714) -> Result<(), Error> {
2715    let mut write_generic = 0;
2716    if let Some(values) = source.float_record(vertex) {
2717        work.scan(values.iter().zip(weights), |(&value, &weight)| {
2718            if weight > 0.0 {
2719                let value = value * weight;
2720                if !value.is_finite() {
2721                    return Err(Error::NumericalFailure);
2722                }
2723                destination[write_generic] = value;
2724                write_generic += 1;
2725            }
2726            Ok(())
2727        })?;
2728    } else {
2729        for (component, &weight) in weights.iter().enumerate() {
2730            work.add(1)?;
2731            if weight > 0.0 {
2732                let value = source.get(vertex, component).ok_or(Error::InvalidLayout)? * weight;
2733                if !value.is_finite() {
2734                    return Err(Error::NumericalFailure);
2735                }
2736                destination[write_generic] = value;
2737                write_generic += 1;
2738            }
2739        }
2740    }
2741    Ok(())
2742}
2743
2744#[allow(clippy::too_many_arguments)]
2745fn run_state(
2746    out: &mut [u32],
2747    mut input: Input<'_>,
2748    positions: Positions<'_>,
2749    attributes: Option<Attributes<'_>>,
2750    weights: &[f32],
2751    flags: Option<&[VertexFlags]>,
2752    settings: SimplifySettings,
2753    ws: &mut Workspace,
2754    work: &mut Work,
2755    output: usize,
2756    solve: bool,
2757) -> Result<(SimplifyResult, State, PositionBounds), Error> {
2758    if settings.options.contains(SimplifyOptions::SPARSE) {
2759        return extra::sparse_run(
2760            out, input, positions, attributes, weights, flags, settings, ws, work, output, solve,
2761        );
2762    }
2763    let n = positions.len();
2764    let m = input.as_slice().len();
2765    let ac = weights.iter().filter(|&&w| w > 0.0).count();
2766    let dense = ac == weights.len();
2767    let mut s = State::new(n, m, ac, ws, output, solve, &mut input.original)?;
2768    s.clamped = settings.options.bits() & 256 != 0;
2769    if solve && ac > 0 {
2770        let requested = checked_bytes(n.saturating_sub(s.vg.capacity()), core::mem::size_of::<G>())
2771            .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2772        s.reclaim_for(ws, requested, &mut input.original)?;
2773        let mut b = Budget::new(ws, s.bytes);
2774        b.reuse(&mut s.vg, n)?;
2775        s.vg.fill(G::default());
2776        s.bytes = b.bytes;
2777    }
2778    // One vertex reset, one index count and one edge write per corner.
2779    metered!(work, m.checked_mul(2).and_then(|v| v.checked_add(n)), |w| s
2780        .adjacency::<false>(input.as_slice(), w))?;
2781    let (lo, hi) = s.position_remap(positions, work)?;
2782    metered!(work, s.classify_work(m, settings.options), |w| s.classify(
2783        flags,
2784        settings.options,
2785        w
2786    ))?;
2787    work.add(n)?;
2788    // Welding reduced the same validated coordinates in their original order.
2789    // Keep the old bounds charge and overflow check here, after classification.
2790    let mut extent = 0.0;
2791    if n != 0 {
2792        for j in 0..3 {
2793            let d = hi[j] - lo[j];
2794            if d >= extent {
2795                extent = d;
2796            }
2797        }
2798    }
2799    if !extent.is_finite() {
2800        return Err(Error::NumericalFailure);
2801    }
2802    let scale = if extent == 0.0 { 0.0 } else { 1.0 / extent };
2803    // bounds checked finite extent; validate checked finite coordinates.
2804    // Each difference is in [0, extent]. If the rounded reciprocal is finite,
2805    // extent*scale < 2, so every normalized coordinate is finite. A reciprocal
2806    // overflow still takes the original per-vertex guard after its write.
2807    let finite_scale = scale.is_finite();
2808    let cached_positions = s.p.len() == n;
2809    if !cached_positions {
2810        s.p.resize(n, V::default());
2811    }
2812    // Each vertex charges once, then each supplied attribute weight once.
2813    let normalize_work = weights.len().checked_add(1).and_then(|v| n.checked_mul(v));
2814    metered!(work, normalize_work, |work| (|| {
2815        // Packed positions without attributes under a finite scale have no
2816        // fallible step: reads are in bounds and the finite guard cannot fire.
2817        // When their n visits fit, charge them once and normalize in one pass
2818        // with the same arithmetic; otherwise keep the per-vertex loop.
2819        if let (false, true, None, Some(values)) = (
2820            cached_positions,
2821            finite_scale,
2822            attributes,
2823            positions.packed_values(),
2824        ) {
2825            if work.precharge(values.len(), 1)? {
2826                for (destination, p) in s.p.iter_mut().zip(values) {
2827                    *destination = V {
2828                        x: (p[0] - lo[0]) * scale,
2829                        y: (p[1] - lo[1]) * scale,
2830                        z: (p[2] - lo[2]) * scale,
2831                    };
2832                }
2833                return Ok(());
2834            }
2835        }
2836        // Under a prepaid meter, each iteration's charge cannot fail and
2837        // only its total matters. With packed or cached positions, contiguous
2838        // float attributes and every weight positive, normalize the prefix of
2839        // vertices the loop accepts, charge it at once and resume the loop at
2840        // the first vertex it would reject (parity/0217-optimesh/PROOFS.md,
2841        // "Normalization prefix").
2842        let mut start = 0;
2843        if prepaid(work) && dense {
2844            let source = positions.packed_values();
2845            if let Some(records) = attributes.and_then(|a| a.contiguous_floats()) {
2846                if cached_positions || source.is_some() {
2847                    start = normalize_prefix(
2848                        &mut s.p,
2849                        &mut s.a,
2850                        if cached_positions { None } else { source },
2851                        records,
2852                        weights,
2853                        lo,
2854                        scale,
2855                        finite_scale,
2856                    );
2857                    work.add(start * (weights.len() + 1))?;
2858                }
2859            }
2860        }
2861        for (i, destination) in s.p.iter_mut().enumerate().skip(start) {
2862            work.add(1)?;
2863            let p = if cached_positions {
2864                let p = *destination;
2865                [p.x, p.y, p.z]
2866            } else {
2867                positions.at(i)?
2868            };
2869            let normalized = V {
2870                x: (p[0] - lo[0]) * scale,
2871                y: (p[1] - lo[1]) * scale,
2872                z: (p[2] - lo[2]) * scale,
2873            };
2874            *destination = normalized;
2875            if !finite_scale
2876                && ![destination.x, destination.y, destination.z]
2877                    .iter()
2878                    .fold(true, |finite, x| finite & x.is_finite())
2879            {
2880                return Err(Error::NumericalFailure);
2881            }
2882            if let Some(a) = attributes {
2883                normalize_attribute_row(&mut s.a[i * ac..(i + 1) * ac], a, i, weights, work)?;
2884            }
2885        }
2886        Ok(())
2887    })())?;
2888    let (components, component_errors) = if settings.options.contains(SimplifyOptions::PRUNE) {
2889        let requested = checked_bytes(n, 4)
2890            .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2891        s.reclaim_for(ws, requested, &mut input.original)?;
2892        let mut b = crate::budget::Budget::with_bytes(ws, s.bytes);
2893        let (c, nc) = extra::component_ids(&s.remap.0, input.as_slice(), &mut b, work)?;
2894        s.bytes = b.bytes();
2895        let requested = checked_bytes(nc, 16)
2896            .and_then(|added| s.bytes.checked_add(added).ok_or(Error::SizeOverflow));
2897        s.reclaim_for(ws, requested, &mut input.original)?;
2898        let mut b = crate::budget::Budget::with_bytes(ws, s.bytes);
2899        let errors = extra::component_errors(&s.p, &c, nc, &mut b, work)?;
2900        s.bytes = b.bytes();
2901        (c, errors)
2902    } else {
2903        (Vec::new(), Vec::new())
2904    };
2905    // Triangles: m visits; regularization: n; edges: m; attributes:
2906    // (m/3)*(3+3*ac). Folding has additional visits and keeps its checked path.
2907    let quadric_work = if settings.options.bits() & 128 != 0 {
2908        None
2909    } else {
2910        m.checked_mul(2)
2911            .and_then(|v| v.checked_add(n))
2912            .and_then(|v| {
2913                if ac == 0 {
2914                    Some(v)
2915                } else {
2916                    ac.checked_add(1)
2917                        .and_then(|a| m.checked_mul(a))
2918                        .and_then(|a| v.checked_add(a))
2919                }
2920            })
2921    };
2922    metered!(work, quadric_work, |w| s.quadrics(
2923        input.as_slice(),
2924        flags,
2925        settings.options,
2926        w
2927    ))?;
2928    let mut dual = 0;
2929    work.scan(s.kind.iter().zip(s.offsets.0.windows(2)), |(&k, o)| {
2930        if k == MAN || k == SEAM {
2931            dual += o[1] as usize - o[0] as usize;
2932        }
2933        Ok(())
2934    })?;
2935    let capacity = m - dual / 2 + 3;
2936    let requested = (|| {
2937        let order_growth = checked_bytes(capacity.saturating_sub(s.order.0.capacity()), 4)?;
2938        let requested = s
2939            .bytes
2940            .checked_add(checked_bytes(
2941                capacity.saturating_sub(s.collapses.capacity()),
2942                core::mem::size_of::<Collapse>(),
2943            )?)
2944            .and_then(|n| n.checked_add(order_growth))
2945            .ok_or(Error::SizeOverflow)?;
2946        Ok::<_, Error>(requested)
2947    })();
2948    s.reclaim_for(ws, requested, &mut input.original)?;
2949    let lean = ws.retention() == crate::Retention::Lean;
2950    let mut budget = Budget::new(ws, s.bytes);
2951    budget.reuse_capacity(&mut s.collapses, capacity)?;
2952    if lean {
2953        // Reserve the same fallible upper bound without touching unused pages.
2954        budget.reuse_capacity(&mut s.order.0, capacity)?;
2955    } else {
2956        budget.reuse(&mut s.order.0, capacity)?;
2957    }
2958    let mut count = m;
2959    let mut error = 0.0;
2960    let mut vertex_error = 0.0;
2961    let mut component_next = 0.0;
2962    let error_scale = if settings.options.contains(SimplifyOptions::ERROR_ABSOLUTE) {
2963        extent
2964    } else {
2965        1.0
2966    };
2967    let limit = (settings.target_error * settings.target_error) / (error_scale * error_scale);
2968    work.add(m)?;
2969    out[..m].copy_from_slice(input.as_slice());
2970    while count > settings.target_index_count {
2971        metered!(
2972            work,
2973            count.checked_mul(2).and_then(|v| v.checked_add(n)),
2974            |w| s.adjacency::<true>(&out[..count], w)
2975        )?;
2976        // pick visits each corner at most once, including triangles that
2977        // produce no collapses. The capacity stop can only reduce that count.
2978        // It has no fallible arithmetic/reader callbacks; an insufficient
2979        // budget takes the original checked path with identical partial pushes.
2980        let nc = metered!(work, Some(count), |w| s.pick(&out[..count], capacity, w))?;
2981        if nc == 0 {
2982            break;
2983        }
2984        // pick is bounded by capacity; resize cannot allocate here. Sorting
2985        // writes every used entry, and no ordering entries exist when nc == 0.
2986        if lean {
2987            s.order.0.resize(nc, 0);
2988        }
2989        s.rank(nc, work)?;
2990        s.sort(nc, work)?;
2991        let goal = (count - settings.target_index_count) / 3;
2992        let (edges, error_limited) = metered!(work, s.perform_work(nc, settings.options), |w| s
2993            .perform(nc, goal, limit, &mut error, w))?;
2994        if edges == 0 {
2995            ws.lod_error_limited = error_limited;
2996            break;
2997        }
2998        if ac == 0 {
2999            vertex_error = error;
3000        }
3001        // n vertex visits, at most n*ac gradient visits, two n loop passes.
3002        let update_work = ac.checked_add(3).and_then(|v| n.checked_mul(v));
3003        metered!(work, update_work, |w| s.update(&mut vertex_error, w))?;
3004        let cr = &s.cr.0[..n];
3005        let remap = &s.remap.0[..n];
3006        let write_generic = metered!(work, Some(count), |w| (|| {
3007            let out = &mut out[..count];
3008            let mut write_generic = 0;
3009            // Only the charge can fail in this pass: when all its triangles
3010            // fit, charge them before the first write, as the loop would.
3011            let charged = w.precharge(count / 3, 3)?;
3012            for i in 0..count / 3 {
3013                if !charged {
3014                    w.add(3)?;
3015                }
3016                // Copy one checked triangle before writing the compacted
3017                // prefix. write<=i, so no unread triangle is overwritten.
3018                let [a, b, c] = out.as_chunks::<3>().0[i];
3019                let a = cr[a as usize] as usize;
3020                let b = cr[b as usize] as usize;
3021                let c = cr[c as usize] as usize;
3022                let r0 = remap[a];
3023                let r1 = remap[b];
3024                let r2 = remap[c];
3025                if r0 != r1 && r0 != r2 && r1 != r2 {
3026                    out.as_chunks_mut::<3>().0[write_generic] = [a as u32, b as u32, c as u32];
3027                    write_generic += 1;
3028                }
3029            }
3030            Ok(write_generic)
3031        })())?;
3032        count = write_generic * 3;
3033        if settings.options.contains(SimplifyOptions::PRUNE)
3034            && count > settings.target_index_count
3035            && component_next <= vertex_error
3036        {
3037            (count, component_next) = extra::prune(
3038                out,
3039                count,
3040                &components,
3041                &component_errors,
3042                vertex_error,
3043                work,
3044            )?;
3045        }
3046    }
3047    let mut stale = true;
3048    while settings.options.contains(SimplifyOptions::PRUNE)
3049        && count > settings.target_index_count
3050        && component_next <= limit
3051    {
3052        let cutoff = if component_next * 1.5 < limit {
3053            component_next * 1.5
3054        } else {
3055            limit
3056        };
3057        let mut max_error = 0.0;
3058        for &e in &component_errors {
3059            work.add(1)?;
3060            if e > max_error && e <= cutoff {
3061                max_error = e;
3062            }
3063        }
3064        let (new_count, next) =
3065            extra::prune(out, count, &components, &component_errors, cutoff, work)?;
3066        component_next = next;
3067        if new_count == count && !stale {
3068            break;
3069        }
3070        stale = false;
3071        count = new_count;
3072        if error < max_error {
3073            error = max_error;
3074        }
3075    }
3076    if settings.options.contains(SimplifyOptions::PRUNE)
3077        && count > settings.target_index_count
3078        && component_next > limit
3079    {
3080        ws.lod_error_limited = true;
3081    }
3082    if solve {
3083        extra::solve_state(&mut s, &out[..count], work)?;
3084    }
3085    let error = sqrt(error) * error_scale;
3086    if !error.is_finite() {
3087        return Err(Error::NumericalFailure);
3088    }
3089    s.original = input.original;
3090    Ok((
3091        SimplifyResult {
3092            index_count: count,
3093            error,
3094        },
3095        s,
3096        PositionBounds { lo, hi },
3097    ))
3098}
3099
3100/// The source-compatible u32 entry point; see [`simplify_generic`] for selectable index widths.
3101#[inline]
3102pub fn simplify(
3103    indices: &[u32],
3104    positions: Positions<'_>,
3105    settings: SimplifySettings,
3106    workspace: &mut Workspace,
3107) -> Result<SimplifiedMesh, Error> {
3108    simplify_generic::<u32>(indices, positions, settings, workspace).map(Into::into)
3109}
3110
3111/// The source-compatible u32 entry point; see [`simplify_with_attributes_generic`] for selectable index widths.
3112#[inline]
3113pub fn simplify_with_attributes(
3114    indices: &[u32],
3115    positions: Positions<'_>,
3116    attributes: Attributes<'_>,
3117    weights: &[f32],
3118    vertex_flags: Option<&[VertexFlags]>,
3119    settings: SimplifySettings,
3120    workspace: &mut Workspace,
3121) -> Result<SimplifiedMesh, Error> {
3122    simplify_with_attributes_generic::<u32>(
3123        indices,
3124        positions,
3125        attributes,
3126        weights,
3127        vertex_flags,
3128        settings,
3129        workspace,
3130    )
3131    .map(Into::into)
3132}
3133
3134/// The source-compatible u32 entry point; see [`simplify_into_generic`] for selectable index widths.
3135#[inline]
3136pub fn simplify_into(
3137    destination: &mut [u32],
3138    indices: &[u32],
3139    positions: Positions<'_>,
3140    settings: SimplifySettings,
3141    workspace: &mut Workspace,
3142) -> Result<SimplifyResult, Error> {
3143    simplify_into_generic::<u32>(destination, indices, positions, settings, workspace)
3144}
3145
3146/// The source-compatible u32 entry point; see [`simplify_with_attributes_into_generic`] for selectable index widths.
3147#[inline]
3148#[allow(clippy::too_many_arguments)]
3149pub fn simplify_with_attributes_into(
3150    destination: &mut [u32],
3151    indices: &[u32],
3152    positions: Positions<'_>,
3153    attributes: Attributes<'_>,
3154    weights: &[f32],
3155    vertex_flags: Option<&[VertexFlags]>,
3156    settings: SimplifySettings,
3157    workspace: &mut Workspace,
3158) -> Result<SimplifyResult, Error> {
3159    simplify_with_attributes_into_generic::<u32>(
3160        destination,
3161        indices,
3162        positions,
3163        attributes,
3164        weights,
3165        vertex_flags,
3166        settings,
3167        workspace,
3168    )
3169}
3170
3171/// The source-compatible u32 form of [`SimplifiedMeshGeneric`].
3172/// Simplified topology referencing the original vertex array.
3173#[derive(Debug)]
3174pub struct SimplifiedMesh {
3175    /// Remaining triangles, in upstream order. The requested target may not be reached.
3176    pub indices: Vec<u32>,
3177    /// Linear error in the units selected by the settings.
3178    pub error: f32,
3179}
3180impl From<SimplifiedMeshGeneric<u32>> for SimplifiedMesh {
3181    #[inline]
3182    fn from(value: SimplifiedMeshGeneric<u32>) -> Self {
3183        Self {
3184            indices: value.indices,
3185            error: value.error,
3186        }
3187    }
3188}
3189
3190impl From<SimplifiedMesh> for SimplifiedMeshGeneric<u32> {
3191    #[inline]
3192    fn from(value: SimplifiedMesh) -> Self {
3193        Self {
3194            indices: value.indices,
3195            error: value.error,
3196        }
3197    }
3198}
3199
3200#[cfg(test)]
3201mod tests {
3202    use super::*;
3203    use crate::Limits;
3204
3205    #[test]
3206    fn update_bounds_preserve_original_sparse_order_and_zero_signs() {
3207        let p = [
3208            [100.0; 3], // Unreferenced; dense bounds must still include it.
3209            [0.0, -0.0, 0.0],
3210            [1.0, 0.0, 0.0],
3211            [-0.0, 1.0, 0.0],
3212            [0.0, 0.0, 1.0],
3213        ];
3214        let indices = [3, 2, 1, 1, 2, 4];
3215        for (options, expected_lo, expected_hi) in [
3216            (SimplifyOptions::EMPTY, [0.0f32, -0.0, 0.0], [100.0f32; 3]),
3217            (SimplifyOptions::SPARSE, [-0.0f32, 0.0, 0.0], [1.0f32; 3]),
3218        ] {
3219            let mut out = [0; 6];
3220            let mut ws = Workspace::default();
3221            let mut work = ws.begin();
3222            let (_, _, bounds) = run_state(
3223                &mut out,
3224                Input::borrowed(&indices),
3225                Positions::from_packed(&p),
3226                None,
3227                &[],
3228                None,
3229                SimplifySettings {
3230                    target_index_count: indices.len(),
3231                    target_error: 1.0,
3232                    options,
3233                },
3234                &mut ws,
3235                &mut work,
3236                0,
3237                true,
3238            )
3239            .unwrap();
3240            assert_eq!(bounds.lo.map(f32::to_bits), expected_lo.map(f32::to_bits));
3241            assert_eq!(bounds.hi.map(f32::to_bits), expected_hi.map(f32::to_bits));
3242        }
3243    }
3244
3245    #[test]
3246    fn preflight_preserves_the_first_reservations_limit_error() {
3247        // On 32-bit this vertex count fits the public index width. The quadric
3248        // estimate overflows isize, but the first offset reservation exceeds
3249        // this zero-byte limit before any allocation or later size check.
3250        let vertices = isize::MAX as usize / core::mem::size_of::<Q>() + 1;
3251        let mut ws = Workspace::new(Limits {
3252            max_bytes: 0,
3253            ..Limits::default()
3254        });
3255        assert!(matches!(
3256            State::new(vertices, 0, 0, &mut ws, 0, false, &mut Vec::new()),
3257            Err(Error::LimitExceeded)
3258        ));
3259    }
3260
3261    // Run explicitly in release mode under <job-runner>. Compare all bit patterns,
3262    // including signed zero, subnormals, infinities and every NaN payload.
3263    #[test]
3264    #[ignore = "exhaustive 2^32-pattern backend identity gate"]
3265    fn simplify_sqrt_exhaustive_identity() {
3266        for bits in 0..=u32::MAX {
3267            let value = core::hint::black_box(f32::from_bits(bits));
3268            assert_eq!(
3269                sqrt(value).to_bits(),
3270                crate::math::sqrt(value).to_bits(),
3271                "sqrt operand {bits:08x}"
3272            );
3273        }
3274    }
3275
3276    #[test]
3277    fn repeated_simplify_reuses_arrays_but_releases_the_remapping_hash() {
3278        let p = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
3279        let settings = SimplifySettings {
3280            target_index_count: 0,
3281            target_error: 0.5,
3282            options: SimplifyOptions::EMPTY,
3283        };
3284        let mut ws = Workspace::default();
3285        let expected = simplify(&[0, 1, 2], Positions::from_packed(&p), settings, &mut ws).unwrap();
3286        let state = ws.simplify.as_ref().unwrap();
3287        assert_eq!(state.table.0.capacity(), 0);
3288        let before = (
3289            state.edges.as_ptr(),
3290            state.q.as_ptr(),
3291            state.collapses.as_ptr(),
3292            state.order.0.as_ptr(),
3293        );
3294        let actual = simplify(&[0, 1, 2], Positions::from_packed(&p), settings, &mut ws).unwrap();
3295        assert_eq!(expected.indices, actual.indices);
3296        assert_eq!(expected.error.to_bits(), actual.error.to_bits());
3297        let state = ws.simplify.as_ref().unwrap();
3298        assert_eq!(state.table.0.capacity(), 0);
3299        assert_eq!(
3300            before,
3301            (
3302                state.edges.as_ptr(),
3303                state.q.as_ptr(),
3304                state.collapses.as_ptr(),
3305                state.order.0.as_ptr()
3306            )
3307        );
3308    }
3309
3310    #[test]
3311    fn prepaid_picker_preserves_every_budget_prefix_and_capacity_stop() {
3312        type PickObservation = (Result<usize, Error>, u64, Vec<(u32, u32, u32)>);
3313        fn run(limit: u64, capacity: usize, prepaid: bool, welded: bool) -> PickObservation {
3314            let indices = [0, 1, 2, 2, 1, 0, 0, 2, 3, 3, 2, 0];
3315            let mut ws = Workspace::new(Limits {
3316                max_bytes: 1 << 20,
3317                max_work: limit,
3318            });
3319            let mut state = State::new(4, 12, 0, &mut ws, 0, false, &mut Vec::new()).unwrap();
3320            state
3321                .remap
3322                .0
3323                .extend(if welded { [0; 4] } else { [0, 1, 2, 3] });
3324            state.collapses.reserve_exact(12);
3325            let mut work = ws.begin();
3326            let result = if prepaid {
3327                (|| {
3328                    metered!(&mut work, Some(indices.len()), |w| state
3329                        .pick(&indices, capacity, w))
3330                })()
3331            } else {
3332                state.pick(&indices, capacity, &mut work)
3333            };
3334            ws.finish(&work);
3335            let collapses = state
3336                .collapses
3337                .iter()
3338                .map(|c| (c.a, c.b, c.error.to_bits()))
3339                .collect();
3340            (result, ws.usage().work, collapses)
3341        }
3342        for limit in 0..=13 {
3343            for capacity in [0, 2, 3, 6, 12] {
3344                for welded in [false, true] {
3345                    assert_eq!(
3346                        run(limit, capacity, true, welded),
3347                        run(limit, capacity, false, welded)
3348                    );
3349                }
3350            }
3351        }
3352    }
3353
3354    #[test]
3355    fn prepaid_phases_match_checked_visits() {
3356        // Five visits of one record each, then a two-record scan; a numerical
3357        // failure may occur at any visit. Bounds: exact, loose, or absent.
3358        fn phase<M: Meter>(
3359            fail_at: usize,
3360            seen: &mut Vec<usize>,
3361            work: &mut M,
3362        ) -> Result<(), Error> {
3363            for i in 0..5 {
3364                work.add(1)?;
3365                seen.push(i);
3366                if i == fail_at {
3367                    return Err(Error::NumericalFailure);
3368                }
3369            }
3370            work.scan(5..7, |i| {
3371                seen.push(i);
3372                if i == fail_at {
3373                    return Err(Error::NumericalFailure);
3374                }
3375                Ok(())
3376            })
3377        }
3378        fn run_phase(
3379            limit: u64,
3380            fail_at: usize,
3381            bound: Option<usize>,
3382        ) -> (Result<(), Error>, u64, Vec<usize>) {
3383            let mut ws = Workspace::new(Limits {
3384                max_bytes: 0,
3385                max_work: limit,
3386            });
3387            let mut work = ws.begin();
3388            let mut seen = Vec::new();
3389            let result = (|| metered!(&mut work, bound, |w| phase(fail_at, &mut seen, w)))();
3390            ws.finish(&work);
3391            (result, ws.usage().work, seen)
3392        }
3393        for limit in 0..=9 {
3394            for fail_at in 0..=7 {
3395                let checked = run_phase(limit, fail_at, None);
3396                assert_eq!(run_phase(limit, fail_at, Some(7)), checked);
3397                assert_eq!(run_phase(limit, fail_at, Some(9)), checked);
3398            }
3399        }
3400    }
3401
3402    #[test]
3403    fn ranking_preserves_numerical_failure_and_budget_prefix() {
3404        for limit in 0..=6 {
3405            for fail_at in 0..=5 {
3406                let mut ws = Workspace::new(Limits {
3407                    max_bytes: 1 << 20,
3408                    max_work: limit,
3409                });
3410                let mut state = State::new(2, 0, 0, &mut ws, 0, false, &mut Vec::new()).unwrap();
3411                state.p.extend([V::default(); 2]);
3412                state.remap.0.extend([0, 1]);
3413                state.q[0] = Q {
3414                    c: f32::MAX,
3415                    w: 0.5,
3416                    inverse_weight: 2.0,
3417                    ..Q::default()
3418                };
3419                state.q[1] = Q {
3420                    w: 1.0,
3421                    inverse_weight: 1.0,
3422                    ..Q::default()
3423                };
3424                for i in 0..5 {
3425                    state.collapses.push(Collapse {
3426                        a: if i == fail_at { 0 } else { 1 },
3427                        b: 1,
3428                        error: f32::from_bits(1),
3429                    });
3430                }
3431                let mut work = ws.begin();
3432                let result = state.rank(5, &mut work);
3433                let (expected, visited, changed) = if limit <= fail_at as u64 && limit < 5 {
3434                    (Err(Error::LimitExceeded), limit, limit as usize)
3435                } else if fail_at < 5 {
3436                    (Err(Error::NumericalFailure), fail_at as u64 + 1, fail_at)
3437                } else {
3438                    (Ok(()), 5, 5)
3439                };
3440                assert_eq!(result, expected);
3441                ws.finish(&work);
3442                assert_eq!(ws.usage().work, visited);
3443                for (i, c) in state.collapses.iter().enumerate() {
3444                    assert_eq!(c.error.to_bits(), if i < changed { 0 } else { 1 });
3445                }
3446            }
3447        }
3448    }
3449}
3450
3451#[cfg(test)]
3452mod retention_tests {
3453    use alloc::vec::Vec;
3454
3455    use crate::{
3456        optimize_overdraw, optimize_vertex_cache, simplify, Positions, SimplifyOptions,
3457        SimplifySettings,
3458    };
3459    use crate::{Error, Limits, Retention, Workspace};
3460
3461    #[test]
3462    fn cache_update_cache_releases_scratch_and_preserves_results() {
3463        let positions = [
3464            [0.0, 0.0, 0.0],
3465            [1.0, 0.0, 0.0],
3466            [0.0, 1.0, 0.0],
3467            [1.0, 1.0, 0.1],
3468        ];
3469        let indices = [0, 1, 2, 2, 1, 3];
3470        let mut outcomes = Vec::new();
3471        for retention in [Retention::Lean, Retention::Reuse] {
3472            let mut ws = Workspace::default();
3473            ws.set_retention(retention);
3474            let cached = optimize_vertex_cache(&indices, positions.len(), &mut ws).unwrap();
3475            let cache_work = ws.usage().work;
3476            let mut updated_indices = indices;
3477            let mut updated_positions = positions;
3478            let result = crate::simplify_with_update(
3479                &mut updated_indices,
3480                &mut crate::PositionsMut::from_packed(&mut updated_positions),
3481                None,
3482                &[],
3483                None,
3484                SimplifySettings {
3485                    target_index_count: indices.len(),
3486                    target_error: 0.5,
3487                    options: SimplifyOptions::EMPTY,
3488                },
3489                &mut ws,
3490            )
3491            .unwrap();
3492            let update_work = ws.usage().work;
3493            if retention == Retention::Lean {
3494                assert_eq!(ws.integers.capacity(), 0);
3495                assert_eq!(ws.floats.capacity(), 0);
3496                assert_eq!(ws.flags.capacity(), 0);
3497                assert_eq!(ws.keys.capacity(), 0);
3498                assert_eq!(ws.vertices.capacity(), 0);
3499            }
3500            assert!(ws.simplify.is_some());
3501            let cached_again =
3502                optimize_vertex_cache(&updated_indices, positions.len(), &mut ws).unwrap();
3503            if retention == Retention::Lean {
3504                assert!(ws.simplify.is_none());
3505            }
3506            outcomes.push((
3507                cached,
3508                result.index_count,
3509                result.error.to_bits(),
3510                updated_indices,
3511                updated_positions.map(|p| p.map(f32::to_bits)),
3512                cached_again,
3513                [cache_work, update_work, ws.usage().work],
3514            ));
3515        }
3516        assert_eq!(outcomes[0], outcomes[1]);
3517    }
3518
3519    #[test]
3520    fn switching_chain_family_releases_scratch_and_preserves_results() {
3521        let p = [
3522            [0.0, 0.0, 0.0],
3523            [1.0, 0.0, 0.0],
3524            [0.0, 1.0, 0.0],
3525            [1.0, 1.0, 0.1],
3526        ];
3527        let i = [0, 1, 2, 2, 1, 3];
3528        let settings = SimplifySettings {
3529            target_index_count: 3,
3530            target_error: 0.5,
3531            options: SimplifyOptions::EMPTY,
3532        };
3533        let mut ws = Workspace::default();
3534        ws.set_retention(Retention::Lean);
3535        let simplified = simplify(&i, Positions::from_packed(&p), settings, &mut ws).unwrap();
3536        assert!(ws.simplify.as_ref().unwrap().capacity_bytes().unwrap() > 0);
3537        assert_eq!(ws.simplify.as_ref().unwrap().q.capacity(), 0);
3538        let mut reuse = Workspace::default();
3539        assert_eq!(reuse.retention(), Retention::Reuse);
3540        let expected = simplify(&i, Positions::from_packed(&p), settings, &mut reuse).unwrap();
3541        assert_eq!(expected.indices, simplified.indices);
3542        assert_eq!(expected.error.to_bits(), simplified.error.to_bits());
3543        assert!(reuse.simplify.as_ref().unwrap().q.capacity() > 0);
3544        let expected_cache = optimize_vertex_cache(&i, p.len(), &mut reuse).unwrap();
3545        assert!(reuse.simplify.is_some());
3546        let expected_overdraw = optimize_overdraw(
3547            &expected_cache,
3548            Positions::from_packed(&p),
3549            1.05,
3550            &mut reuse,
3551        )
3552        .unwrap();
3553        assert!(reuse.simplify.is_some());
3554        assert!(reuse.vertices.capacity() > 0);
3555        let cached = optimize_vertex_cache(&i, p.len(), &mut ws).unwrap();
3556        assert!(ws.simplify.is_none());
3557        assert!(ws.vertices.capacity() > 0);
3558        assert_eq!(
3559            cached,
3560            optimize_vertex_cache(&i, p.len(), &mut Workspace::default()).unwrap()
3561        );
3562        let vertex_ptr = ws.vertices.as_ptr();
3563        let integer_ptr = ws.integers.as_ptr();
3564        assert_eq!(cached, optimize_vertex_cache(&i, p.len(), &mut ws).unwrap());
3565        assert_eq!(vertex_ptr, ws.vertices.as_ptr());
3566        assert_eq!(integer_ptr, ws.integers.as_ptr());
3567        let overdraw =
3568            optimize_overdraw(&cached, Positions::from_packed(&p), 1.05, &mut ws).unwrap();
3569        assert_eq!(overdraw, expected_overdraw);
3570        assert_eq!(ws.vertices.capacity(), 0);
3571        assert_eq!(ws.flags.capacity(), 0);
3572        assert_eq!(
3573            overdraw,
3574            optimize_overdraw(
3575                &cached,
3576                Positions::from_packed(&p),
3577                1.05,
3578                &mut Workspace::default()
3579            )
3580            .unwrap()
3581        );
3582        let integer_ptr = ws.integers.as_ptr();
3583        let float_ptr = ws.floats.as_ptr();
3584        assert_eq!(
3585            overdraw,
3586            optimize_overdraw(&cached, Positions::from_packed(&p), 1.05, &mut ws).unwrap()
3587        );
3588        assert_eq!(integer_ptr, ws.integers.as_ptr());
3589        assert_eq!(float_ptr, ws.floats.as_ptr());
3590        let again = simplify(&i, Positions::from_packed(&p), settings, &mut ws).unwrap();
3591        assert_eq!(again.indices, simplified.indices);
3592        assert_eq!(again.error.to_bits(), simplified.error.to_bits());
3593        assert_eq!(ws.integers.capacity(), 0);
3594        assert_eq!(ws.floats.capacity(), 0);
3595        assert_eq!(ws.keys.capacity(), 0);
3596        assert_eq!(ws.simplify.as_ref().unwrap().q.capacity(), 0);
3597        let state_bytes = ws.simplify.as_ref().unwrap().capacity_bytes().unwrap();
3598        assert_eq!(ws.retained_bytes().unwrap(), state_bytes);
3599        assert_eq!(ws.limits(), Limits::default());
3600        assert!(ws.usage().bytes >= state_bytes);
3601        assert!(ws.usage().work > 0);
3602        // Validation failures do not acquire scratch or alter the error.
3603        assert_eq!(
3604            optimize_vertex_cache(&[4, 0, 1], p.len(), &mut ws),
3605            Err(Error::IndexOutOfBounds)
3606        );
3607        assert!(ws.simplify.is_some());
3608        assert_eq!(
3609            optimize_vertex_cache(&[4, 0, 1], p.len(), &mut reuse),
3610            Err(Error::IndexOutOfBounds)
3611        );
3612        assert_eq!(ws.retained_bytes().unwrap(), state_bytes);
3613        let fifo = crate::optimize_vertex_cache_fifo(&i, p.len(), 16, &mut ws).unwrap();
3614        assert!(ws.simplify.is_none());
3615        assert_eq!(
3616            fifo,
3617            crate::optimize_vertex_cache_fifo(&i, p.len(), 16, &mut Workspace::default()).unwrap()
3618        );
3619        let usage = ws.usage();
3620        ws.set_retention(Retention::Lean);
3621        assert_eq!(ws.usage(), usage);
3622        ws.clear();
3623        assert_eq!(ws.retention(), Retention::Lean);
3624        ws.set_limits(Limits::default());
3625        assert_eq!(ws.retention(), Retention::Lean);
3626        ws.set_retention(Retention::Reuse);
3627        assert_eq!(ws.retained_bytes().unwrap(), 0);
3628        assert_eq!(ws.usage(), crate::Usage::default());
3629    }
3630}