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