Skip to main content

meshoptimizer_rs/
meshlet_util.rs

1// Port of meshoptimizer 1.3 meshletutils.cpp (MIT, Arseny Kapoulkine).
2use crate::math::{sqrt8, LANES};
3use crate::processing::{cross, dot, finite, point, sub, Context};
4use crate::{Attributes, Error, Positions, Workspace};
5use alloc::vec::Vec;
6
7/// A borrowed positions view whose bounds-validation scan is cached once.
8///
9/// Construction scans all positions in O(n) time without allocating. The scan
10/// result, including a failure, is retained: bounds calls report it at their
11/// original validation point, after topology checks and work-limit checks.
12/// This preserves error precedence even for malformed topology combined with
13/// non-finite positions. Repeated calls do no full-view scan, but charge the
14/// original logical position visits to preserve [`Workspace`] limits and usage.
15#[derive(Clone, Copy, Debug)]
16pub struct BoundsPositions<'a> {
17    positions: Positions<'a>,
18    validation: Result<bool, Error>,
19}
20impl<'a> BoundsPositions<'a> {
21    /// Scan and cache the size, finiteness and arithmetic-range checks for `positions`.
22    ///
23    /// Errors are deferred to the bounds operation to preserve its precedence.
24    pub fn new(positions: Positions<'a>) -> Self {
25        Self {
26            positions,
27            validation: crate::processing::validate_positions(positions),
28        }
29    }
30    fn apply(self, ctx: &mut Context<'_>) -> Result<bool, Error> {
31        if self.positions.len() > u32::MAX as usize {
32            return Err(Error::SizeOverflow);
33        }
34        ctx.tick(self.positions.len())?;
35        self.validation
36    }
37}
38
39/// Meaningful fields of `meshopt_Bounds`, without native padding.
40#[derive(Clone, Copy, Debug, Default, PartialEq)]
41pub struct Bounds {
42    /// Sphere center.
43    pub center: [f32; 3],
44    /// Sphere radius.
45    pub radius: f32,
46    /// Perspective normal-cone apex.
47    pub cone_apex: [f32; 3],
48    /// Unit normal-cone axis.
49    pub cone_axis: [f32; 3],
50    /// Cone culling cutoff.
51    pub cone_cutoff: f32,
52    /// Conservative signed-normalized axis.
53    pub cone_axis_s8: [i8; 3],
54    /// Conservative signed-normalized cutoff.
55    pub cone_cutoff_s8: i8,
56}
57/// Meshlet-local topology with first-visit vertex references.
58#[derive(Debug, Default, PartialEq, Eq)]
59pub struct LocalMeshlet {
60    /// References to the original vertex buffer.
61    pub vertices: Vec<u32>,
62    /// Three local byte indices per triangle.
63    pub triangles: Vec<u8>,
64}
65
66// The bounded fast path has finite intermediates by construction. Its largest
67// product is a squared cross product of differences at most 2e8 (below 1e35).
68// Larger finite inputs retain every original intermediate check.
69#[inline(always)]
70fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
71    if CHECK {
72        finite(value)
73    } else {
74        Ok(value)
75    }
76}
77trait SphereSource {
78    fn sample(&self, index: usize) -> ([f32; 3], f32);
79}
80// Select a packed layout once before repeated point reads. The view fallback
81// retains checked access for strided, byte-ordered and mapped positions.
82trait BoundsSource: Copy {
83    fn point(self, index: u32) -> [f32; 3];
84}
85impl BoundsSource for Positions<'_> {
86    #[inline(always)]
87    fn point(self, index: u32) -> [f32; 3] {
88        point(self, index)
89    }
90}
91impl BoundsSource for &[[f32; 3]] {
92    #[inline(always)]
93    fn point(self, index: u32) -> [f32; 3] {
94        self[index as usize]
95    }
96}
97struct PointSource<'a, P = Positions<'a>> {
98    p: P,
99    indices: Option<&'a [u32]>,
100    radii: Option<Attributes<'a>>,
101}
102impl<P: BoundsSource> SphereSource for PointSource<'_, P> {
103    #[inline(always)]
104    fn sample(&self, index: usize) -> ([f32; 3], f32) {
105        let v = self.indices.map_or(index as u32, |i| i[index]);
106        (
107            self.p.point(v),
108            self.radii
109                .map_or(0., |r| r.get(v as usize, 0).expect("validated radius")),
110        )
111    }
112}
113struct NormalSource<'a>(&'a [[f32; 4]]);
114impl SphereSource for NormalSource<'_> {
115    #[inline(always)]
116    fn sample(&self, index: usize) -> ([f32; 3], f32) {
117        let p = self.0[index];
118        ([p[0], p[1], p[2]], 0.)
119    }
120}
121// The scalar fallback in sqrt8 computes every lane, including unused 1.0
122// padding. For one-triangle bounds, omit those unused fallback calls while
123// keeping the used operands, backend and evaluation order identical.
124#[inline(always)]
125fn bounds_roots(values: [f32; LANES], used: usize) -> [f32; LANES] {
126    if used < LANES
127        && values[..used]
128            .iter()
129            .any(|v| v.to_bits().wrapping_sub(0x0080_0000) >= 0x7f00_0000)
130    {
131        let mut result = [1.; LANES];
132        for i in 0..used {
133            result[i] = crate::math::sqrt(values[i]);
134        }
135        result
136    } else {
137        sqrt8(values)
138    }
139}
140#[inline(always)]
141fn sphere<const A: usize, const CHECK: bool>(
142    count: usize,
143    get: impl SphereSource,
144    skip_padding: bool,
145    ctx: &mut Context<'_>,
146) -> Result<([f32; 3], f32), Error> {
147    if count == 0 {
148        return Ok(([0.0; 3], 0.0));
149    }
150    let axes = [
151        [1., 0., 0.],
152        [0., 1., 0.],
153        [0., 0., 1.],
154        [0.57735026; 3],
155        [-0.57735026, 0.57735026, 0.57735026],
156        [0.57735026, -0.57735026, 0.57735026],
157        [0.57735026, 0.57735026, -0.57735026],
158    ];
159    let mut pmin = [0u32; 7];
160    let mut pmax = [0u32; 7];
161    let mut tmin = [f32::MAX; 7];
162    let mut tmax = [-f32::MAX; 7];
163    ctx.tick(count * 2)?;
164    for i in 0..count {
165        let (p, r) = get.sample(i);
166        for k in 0..A {
167            let tp = number::<CHECK>(dot(axes[k], p))?;
168            let lo = number::<CHECK>(tp - r)?;
169            let hi = number::<CHECK>(tp + r)?;
170            let lower = lo < tmin[k];
171            let upper = hi > tmax[k];
172            pmin[k] = if lower { i as u32 } else { pmin[k] };
173            pmax[k] = if upper { i as u32 } else { pmax[k] };
174            tmin[k] = if lower { lo } else { tmin[k] };
175            tmax[k] = if upper { hi } else { tmax[k] };
176        }
177    }
178    // The axis extents are independent: take their roots together. Failures
179    // are all NumericalFailure, so the grouped check order is unobservable.
180    let mut squares = [1f32; LANES];
181    for k in 0..A {
182        let (a, _) = get.sample(pmin[k] as usize);
183        let (b, _) = get.sample(pmax[k] as usize);
184        let d = sub(b, a);
185        squares[k] = number::<CHECK>(dot(d, d))?;
186    }
187    let lengths = if skip_padding {
188        bounds_roots(squares, A)
189    } else {
190        sqrt8(squares)
191    };
192    let mut axis = 0;
193    let mut dr = 0.;
194    for k in 0..A {
195        let (_, ar) = get.sample(pmin[k] as usize);
196        let (_, br) = get.sample(pmax[k] as usize);
197        let v = number::<CHECK>(lengths[k] + ar + br)?;
198        if v > dr {
199            dr = v;
200            axis = k;
201        }
202    }
203    let (a, ar) = get.sample(pmin[axis] as usize);
204    let (b, br) = get.sample(pmax[axis] as usize);
205    let delta = sub(b, a);
206    // The same difference as the selected axis extent: reuse its root.
207    let d = lengths[axis];
208    let k = if d > 0. { (d + br - ar) / (2. * d) } else { 0. };
209    let mut center = [
210        a[0] + delta[0] * k,
211        a[1] + delta[1] * k,
212        a[2] + delta[2] * k,
213    ];
214    let mut radius = dr / 2.;
215    for i in 0..count {
216        let (p, r) = get.sample(i);
217        let dp = sub(p, center);
218        let d2 = number::<CHECK>(dot(dp, dp))?;
219        // sqrt(round(x*x)) rounds to x when x*x is normal. Lower the
220        // rounded radius-r by one representable value, so adding r cannot
221        // exceed radius. This only avoids a sqrt whose update would be false.
222        let limit = radius - r;
223        if limit >= 1.0e-18 {
224            let lower = f32::from_bits(limit.to_bits() - 1);
225            if d2 <= lower * lower {
226                continue;
227            }
228        }
229        let d = ctx.sqrt(d2);
230        if d + r > radius {
231            let k = if d > 0. {
232                (d + r - radius) / (2. * d)
233            } else {
234                0.
235            };
236            for j in 0..3 {
237                center[j] += k * (p[j] - center[j]);
238            }
239            radius = (radius + d + r) / 2.;
240        }
241    }
242    for v in center {
243        number::<CHECK>(v)?;
244    }
245    number::<CHECK>(radius)?;
246    Ok((center, radius))
247}
248fn bounds<const CHECK: bool, const N: usize>(
249    indices: &[u32],
250    corners: &[u32],
251    p: impl BoundsSource,
252    ctx: &mut Context<'_>,
253) -> Result<Bounds, Error> {
254    let mut normals = [[0f32; 4]; N];
255    let mut n = 0;
256    ctx.tick(indices.len() / 3)?;
257    // Triangle areas are independent: take their roots eight at a time. Every
258    // failure is the same NumericalFailure and work is charged above, so the
259    // grouped check order is unobservable.
260    for group in indices.as_chunks::<3>().0.chunks(LANES) {
261        let mut corners = [[0f32; 3]; LANES];
262        let mut normals_raw = [[0f32; 3]; LANES];
263        let mut squares = [1f32; LANES];
264        for (k, t) in group.iter().enumerate() {
265            let a = p.point(t[0]);
266            let normal = cross(sub(p.point(t[1]), a), sub(p.point(t[2]), a));
267            squares[k] = number::<CHECK>(dot(normal, normal))?;
268            corners[k] = a;
269            normals_raw[k] = normal;
270        }
271        let areas = if N == 1 && group.len() == 1 {
272            bounds_roots(squares, 1)
273        } else {
274            sqrt8(squares)
275        };
276        for k in 0..group.len() {
277            let area = areas[k];
278            if area == 0. {
279                continue;
280            }
281            let mut normal = normals_raw[k];
282            for v in &mut normal {
283                *v /= area;
284            }
285            normals[n] = [
286                normal[0],
287                normal[1],
288                normal[2],
289                -number::<CHECK>(dot(normal, corners[k]))?,
290            ];
291            n += 1;
292        }
293    }
294    let mut b = Bounds::default();
295    if n == 0 {
296        return Ok(b);
297    }
298    let (center, radius) = sphere::<7, CHECK>(
299        corners.len(),
300        PointSource {
301            p,
302            indices: Some(corners),
303            radii: None,
304        },
305        N == 1,
306        ctx,
307    )?;
308    b.center = center;
309    b.radius = radius;
310    let (mut axis, _) = sphere::<3, CHECK>(n, NormalSource(&normals[..n]), N == 1, ctx)?;
311    let len = ctx.sqrt(number::<CHECK>(dot(axis, axis))?);
312    let inv = if len == 0. { 0. } else { 1. / len };
313    for a in &mut axis {
314        *a *= inv;
315    }
316    let mut mindp = 1.;
317    ctx.tick(n * 2)?;
318    for normal in &normals[..n] {
319        let dp = dot([normal[0], normal[1], normal[2]], axis);
320        if dp < mindp {
321            mindp = dp;
322        }
323    }
324    if mindp <= 0.1 {
325        b.cone_cutoff = 1.;
326        b.cone_cutoff_s8 = 127;
327        return Ok(b);
328    }
329    let mut maxt = 0.;
330    for normal in &normals[..n] {
331        let nn = [normal[0], normal[1], normal[2]];
332        let dc = dot(center, nn) + normal[3];
333        let dn = dot(axis, nn);
334        let t = number::<CHECK>(dc / dn)?;
335        if t > maxt {
336            maxt = t;
337        }
338    }
339    for j in 0..3 {
340        b.cone_apex[j] = number::<CHECK>(center[j] - axis[j] * maxt)?;
341        b.cone_axis[j] = axis[j];
342        let v = axis[j].clamp(-1., 1.);
343        b.cone_axis_s8[j] = (v * 127. + if v >= 0. { 0.5 } else { -0.5 }) as i8;
344    }
345    b.cone_cutoff = ctx.sqrt(number::<CHECK>(1. - mindp * mindp)?);
346    let e0 = (b.cone_axis_s8[0] as f32 / 127. - axis[0]).abs();
347    let e1 = (b.cone_axis_s8[1] as f32 / 127. - axis[1]).abs();
348    let e2 = (b.cone_axis_s8[2] as f32 / 127. - axis[2]).abs();
349    b.cone_cutoff_s8 = ((127. * (b.cone_cutoff + e0 + e1 + e2) + 1.) as i32).min(127) as i8;
350    Ok(b)
351}
352/// `meshopt_computeClusterBounds`: sphere and conservative normal cone.
353///
354/// Scans all positions in O(n) time per call. For repeated bounds queries use
355/// [`BoundsPositions`] with [`compute_cluster_bounds_with_positions`].
356///
357/// # Errors
358/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
359/// `InvalidParameter` for too many indices; `NumericalFailure` for non-finite geometry or calculations.
360/// `SizeOverflow` for size overflow or `LimitExceeded` for exhausted limits.
361pub fn compute_cluster_bounds(
362    indices: &[u32],
363    p: Positions<'_>,
364    workspace: &mut Workspace,
365) -> Result<Bounds, Error> {
366    let mut ctx = Context::new(workspace)?;
367    if indices.len() > 1536 {
368        return Err(Error::InvalidParameter);
369    }
370    if indices.len() <= 96 {
371        cluster_bounds::<96, 32>(indices, p, &mut ctx, None)
372    } else if indices.len() <= 384 {
373        cluster_bounds::<384, 128>(indices, p, &mut ctx, None)
374    } else {
375        cluster_bounds::<1536, 512>(indices, p, &mut ctx, None)
376    }
377}
378/// Compute cluster bounds using a cached positions-validation scan.
379///
380/// Output bits, errors, error precedence and logical workspace usage match
381/// [`compute_cluster_bounds`]. Per-call work is O(indices.len()), without a
382/// full positions scan; constructing [`BoundsPositions`] costs O(n) once.
383///
384/// # Errors
385/// Same errors as [`compute_cluster_bounds`].
386pub fn compute_cluster_bounds_with_positions(
387    indices: &[u32],
388    p: BoundsPositions<'_>,
389    workspace: &mut Workspace,
390) -> Result<Bounds, Error> {
391    let mut ctx = Context::new(workspace)?;
392    if indices.len() > 1536 {
393        return Err(Error::InvalidParameter);
394    }
395    if indices.len() <= 96 {
396        cluster_bounds_cached::<96, 32>(indices, p, &mut ctx)
397    } else if indices.len() <= 384 {
398        cluster_bounds_cached::<384, 128>(indices, p, &mut ctx)
399    } else {
400        cluster_bounds_cached::<1536, 512>(indices, p, &mut ctx)
401    }
402}
403fn cluster_bounds_cached<const M: usize, const N: usize>(
404    indices: &[u32],
405    p: BoundsPositions<'_>,
406    ctx: &mut Context<'_>,
407) -> Result<Bounds, Error> {
408    ctx.topology(indices, p.positions.len())?;
409    ctx.moderate = p.apply(ctx)?;
410    cluster_bounds_body::<M, N>(indices, p.positions, ctx)
411}
412fn cluster_bounds_body<const M: usize, const N: usize>(
413    indices: &[u32],
414    p: Positions<'_>,
415    ctx: &mut Context<'_>,
416) -> Result<Bounds, Error> {
417    let mut cache = [u32::MAX; 512];
418    let mut corners = [0u32; M];
419    let mut n = 0;
420    ctx.tick(indices.len())?;
421    for &v in indices {
422        let c = &mut cache[v as usize & 511];
423        if *c != v {
424            corners[n] = v;
425            n += 1;
426        }
427        *c = v;
428    }
429    if ctx.moderate {
430        bounds::<false, N>(indices, &corners[..n], p, ctx)
431    } else {
432        bounds::<true, N>(indices, &corners[..n], p, ctx)
433    }
434}
435#[cfg(feature = "clusterlod")]
436pub(crate) fn compute_cluster_bounds_validated(
437    indices: &[u32],
438    p: Positions<'_>,
439    moderate: bool,
440    workspace: &mut Workspace,
441) -> Result<Bounds, Error> {
442    let mut ctx = Context::new(workspace)?;
443    if indices.len() > 1536 {
444        return Err(Error::InvalidParameter);
445    }
446    if indices.len() <= 96 {
447        cluster_bounds::<96, 32>(indices, p, &mut ctx, Some(moderate))
448    } else if indices.len() <= 384 {
449        cluster_bounds::<384, 128>(indices, p, &mut ctx, Some(moderate))
450    } else {
451        cluster_bounds::<1536, 512>(indices, p, &mut ctx, Some(moderate))
452    }
453}
454fn cluster_bounds<const M: usize, const N: usize>(
455    indices: &[u32],
456    p: Positions<'_>,
457    ctx: &mut Context<'_>,
458    trusted_moderate: Option<bool>,
459) -> Result<Bounds, Error> {
460    ctx.topology(indices, p.len())?;
461    if let Some(moderate) = trusted_moderate {
462        ctx.moderate = moderate;
463    } else {
464        ctx.positions(p)?;
465    }
466    let mut cache = [u32::MAX; 512];
467    let mut corners = [0u32; M];
468    let mut n = 0;
469    ctx.tick(indices.len())?;
470    for &v in indices {
471        let c = &mut cache[v as usize & 511];
472        if *c != v {
473            corners[n] = v;
474            n += 1;
475        }
476        *c = v;
477    }
478    if ctx.moderate {
479        bounds::<false, N>(indices, &corners[..n], p, ctx)
480    } else {
481        bounds::<true, N>(indices, &corners[..n], p, ctx)
482    }
483}
484/// `meshopt_computeMeshletBounds`: bounds of byte-local triangles.
485///
486/// Scans all positions in O(n) time per call. For repeated bounds queries use
487/// [`BoundsPositions`] with [`compute_meshlet_bounds_with_positions`].
488///
489/// # Errors
490/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
491/// `InvalidParameter` for unsupported meshlet counts; `NumericalFailure` for non-finite geometry or calculations.
492/// `SizeOverflow` for size overflow or `LimitExceeded` for exhausted limits.
493pub fn compute_meshlet_bounds(
494    vertices: &[u32],
495    triangles: &[u8],
496    p: Positions<'_>,
497    workspace: &mut Workspace,
498) -> Result<Bounds, Error> {
499    let mut ctx = Context::new(workspace)?;
500    validate_local(vertices, triangles)?;
501    if triangles.len() <= 96 {
502        meshlet_bounds::<96, 32>(vertices, triangles, p, &mut ctx)
503    } else if triangles.len() <= 384 {
504        meshlet_bounds::<384, 128>(vertices, triangles, p, &mut ctx)
505    } else {
506        meshlet_bounds::<1536, 512>(vertices, triangles, p, &mut ctx)
507    }
508}
509/// Compute meshlet bounds using a cached positions-validation scan.
510///
511/// Output bits, errors, error precedence and logical workspace usage match
512/// [`compute_meshlet_bounds`]. Per-call work is O(vertices.len() + triangles.len()),
513/// without a full positions scan; constructing [`BoundsPositions`] costs O(n) once.
514///
515/// # Errors
516/// Same errors as [`compute_meshlet_bounds`].
517pub fn compute_meshlet_bounds_with_positions(
518    vertices: &[u32],
519    triangles: &[u8],
520    p: BoundsPositions<'_>,
521    workspace: &mut Workspace,
522) -> Result<Bounds, Error> {
523    let mut ctx = Context::new(workspace)?;
524    validate_local(vertices, triangles)?;
525    ctx.moderate = p.apply(&mut ctx)?;
526    if triangles.len() <= 3 {
527        meshlet_bounds_body::<3, 1>(vertices, triangles, p.positions, &mut ctx)
528    } else if triangles.len() <= 96 {
529        meshlet_bounds_body::<96, 32>(vertices, triangles, p.positions, &mut ctx)
530    } else if triangles.len() <= 384 {
531        meshlet_bounds_body::<384, 128>(vertices, triangles, p.positions, &mut ctx)
532    } else {
533        meshlet_bounds_body::<1536, 512>(vertices, triangles, p.positions, &mut ctx)
534    }
535}
536fn meshlet_bounds<const M: usize, const N: usize>(
537    vertices: &[u32],
538    triangles: &[u8],
539    p: Positions<'_>,
540    ctx: &mut Context<'_>,
541) -> Result<Bounds, Error> {
542    ctx.positions(p)?;
543    ctx.tick(vertices.len() + triangles.len())?;
544    if vertices.iter().any(|&v| v as usize >= p.len()) {
545        return Err(Error::IndexOutOfBounds);
546    }
547    let mut indices = [0u32; M];
548    let mut n = 0;
549    for (i, &v) in triangles.iter().enumerate() {
550        indices[i] = vertices[v as usize];
551        n = n.max(v as usize + 1);
552    }
553    if ctx.moderate {
554        bounds::<false, N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
555    } else {
556        bounds::<true, N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
557    }
558}
559fn meshlet_bounds_body<const M: usize, const N: usize>(
560    vertices: &[u32],
561    triangles: &[u8],
562    p: Positions<'_>,
563    ctx: &mut Context<'_>,
564) -> Result<Bounds, Error> {
565    ctx.tick(vertices.len() + triangles.len())?;
566    if vertices
567        .iter()
568        .copied()
569        .max()
570        .is_some_and(|v| v as usize >= p.len())
571    {
572        return Err(Error::IndexOutOfBounds);
573    }
574    if N == 1 {
575        let Some(triangle) = triangles.first_chunk::<3>() else {
576            return Ok(Bounds::default());
577        };
578        let indices = triangle.map(|v| vertices[v as usize]);
579        let n = triangle.iter().copied().max().unwrap() as usize + 1;
580        return meshlet_bounds_result::<N>(&indices, &vertices[..n], p, ctx);
581    }
582    let mut indices = [0u32; M];
583    let mut n = 0;
584    for (i, &v) in triangles.iter().enumerate() {
585        indices[i] = vertices[v as usize];
586        n = n.max(v as usize + 1);
587    }
588    meshlet_bounds_result::<N>(&indices[..triangles.len()], &vertices[..n], p, ctx)
589}
590#[inline(always)]
591fn meshlet_bounds_result<const N: usize>(
592    indices: &[u32],
593    corners: &[u32],
594    p: Positions<'_>,
595    ctx: &mut Context<'_>,
596) -> Result<Bounds, Error> {
597    if let Some(packed) = p.packed_values() {
598        if ctx.moderate {
599            bounds::<false, N>(indices, corners, packed, ctx)
600        } else {
601            bounds::<true, N>(indices, corners, packed, ctx)
602        }
603    } else if ctx.moderate {
604        bounds::<false, N>(indices, corners, p, ctx)
605    } else {
606        bounds::<true, N>(indices, corners, p, ctx)
607    }
608}
609/// `meshopt_computeSphereBounds`. Optional radii use a checked one-component view.
610///
611/// # Errors
612/// `InvalidLayout` for mismatched radii; `InvalidParameter` for negative or non-finite radii;
613/// `NumericalFailure` for non-finite geometry or calculations.
614/// `SizeOverflow` for size overflow or `LimitExceeded` for exhausted limits.
615pub fn compute_sphere_bounds(
616    p: Positions<'_>,
617    radii: Option<Attributes<'_>>,
618    workspace: &mut Workspace,
619) -> Result<Bounds, Error> {
620    let mut ctx = Context::new(workspace)?;
621    ctx.positions(p)?;
622    if let Some(r) = radii {
623        if r.len() != p.len() || r.components() != 1 {
624            return Err(Error::InvalidLayout);
625        }
626        ctx.tick(r.len())?;
627        for i in 0..r.len() {
628            let v = r.get(i, 0).ok_or(Error::InvalidLayout)?;
629            ctx.moderate &= v <= 1.0e8;
630            if !v.is_finite() || v < 0. {
631                return Err(Error::InvalidParameter);
632            }
633        }
634    }
635    let get = PointSource {
636        p,
637        indices: None,
638        radii,
639    };
640    let (center, radius) = if ctx.moderate {
641        sphere::<7, false>(p.len(), get, false, &mut ctx)?
642    } else {
643        sphere::<7, true>(p.len(), get, false, &mut ctx)?
644    };
645    Ok(Bounds {
646        center,
647        radius,
648        ..Bounds::default()
649    })
650}
651fn validate_local(v: &[u32], t: &[u8]) -> Result<(), Error> {
652    if !t.len().is_multiple_of(3) {
653        return Err(Error::InvalidTopology);
654    }
655    if v.len() > 256 || t.len() > 1536 {
656        return Err(Error::InvalidParameter);
657    }
658    if t.iter().any(|&i| i as usize >= v.len()) {
659        return Err(Error::IndexOutOfBounds);
660    }
661    Ok(())
662}
663fn extract<const V: usize, const T: usize>(
664    indices: &[u32],
665    vertices: &mut [u32; V],
666    triangles: &mut [u8; T],
667    ctx: &mut Context<'_>,
668) -> Result<usize, Error> {
669    if !indices.len().is_multiple_of(3) {
670        return Err(Error::InvalidTopology);
671    }
672    if indices.len() > 1536 {
673        return Err(Error::InvalidParameter);
674    }
675    let mut n = 0;
676    let mut cache = [-1i16; 1024];
677    ctx.tick(indices.len())?;
678    for (i, &v) in indices.iter().enumerate() {
679        let key = v as usize & 1023;
680        let c = cache[key];
681        if c >= 0 && vertices[c as u8 as usize] == v {
682            triangles[i] = c as u8;
683            continue;
684        }
685        let pos = if c < 0 {
686            n
687        } else {
688            ctx.tick(n)?;
689            vertices[..n].iter().position(|&x| x == v).unwrap_or(n)
690        };
691        if pos == n {
692            if n == 256 {
693                return Err(Error::InvalidParameter);
694            }
695            vertices[n] = v;
696            n += 1;
697        }
698        cache[key] = pos as i16;
699        triangles[i] = pos as u8;
700    }
701    Ok(n)
702}
703/// `meshopt_extractMeshletIndices`: preserve first-visit vertex order.
704///
705/// # Errors
706/// `InvalidTopology` for incomplete triangles; `InvalidParameter` for unsupported meshlet counts;
707/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
708pub fn extract_meshlet_indices(
709    indices: &[u32],
710    workspace: &mut Workspace,
711) -> Result<LocalMeshlet, Error> {
712    let mut ctx = Context::new(workspace)?;
713    extracted(indices, &mut ctx, |v, t, ctx| {
714        Ok(LocalMeshlet {
715            vertices: ctx.copy(v)?,
716            triangles: ctx.copy(t)?,
717        })
718    })
719}
720// Run `extract` with stack scratch sized to the input (no larger than the
721// 256-vertex and 1536-index limits), so small meshlets do not clear the
722// full-size arrays. Validation order and results are unchanged.
723#[inline(always)]
724fn extracted<R>(
725    indices: &[u32],
726    ctx: &mut Context<'_>,
727    finish: impl FnOnce(&[u32], &[u8], &mut Context<'_>) -> Result<R, Error>,
728) -> Result<R, Error> {
729    if indices.len() <= 96 {
730        let (mut v, mut t) = ([0; 96], [0; 96]);
731        let n = extract(indices, &mut v, &mut t, ctx)?;
732        finish(&v[..n], &t[..indices.len()], ctx)
733    } else if indices.len() <= 384 {
734        let (mut v, mut t) = ([0; 256], [0; 384]);
735        let n = extract(indices, &mut v, &mut t, ctx)?;
736        finish(&v[..n], &t[..indices.len()], ctx)
737    } else {
738        let (mut v, mut t) = ([0; 256], [0; 1536]);
739        let n = extract(indices, &mut v, &mut t, ctx)?;
740        finish(&v[..n], &t[..indices.len()], ctx)
741    }
742}
743/// Caller-buffer extraction. Errors leave both destinations unchanged; tails are preserved.
744///
745/// # Errors
746/// Same errors as [`extract_meshlet_indices`]. `BufferTooSmall` if either output is too short; no output allocation is needed.
747pub fn extract_meshlet_indices_into(
748    vertices: &mut [u32],
749    triangles: &mut [u8],
750    indices: &[u32],
751    workspace: &mut Workspace,
752) -> Result<usize, Error> {
753    let mut ctx = Context::new(workspace)?;
754    if triangles.len() < indices.len() {
755        return Err(Error::BufferTooSmall);
756    }
757    extracted(indices, &mut ctx, |v, t, _| {
758        if vertices.len() < v.len() {
759            return Err(Error::BufferTooSmall);
760        }
761        vertices[..v.len()].copy_from_slice(v);
762        triangles[..t.len()].copy_from_slice(t);
763        Ok(v.len())
764    })
765}
766// All entry points validate sizes and local references before copying/mutation.
767fn optimize(v: &mut [u32], t: &mut [u8], level: u8, ctx: &mut Context<'_>) -> Result<(), Error> {
768    if level > 9 {
769        return Err(Error::InvalidParameter);
770    }
771    if level == 0 {
772        optimize_body::<false>(v, t, level, ctx)
773    } else {
774        optimize_body::<true>(v, t, level, ctx)
775    }
776}
777fn optimize_body<const ADVANCED: bool>(
778    v: &mut [u32],
779    t: &mut [u8],
780    level: u8,
781    ctx: &mut Context<'_>,
782) -> Result<(), Error> {
783    let n = t.len() / 3;
784    // A single triangle cannot change order or rotation at any level. Keep the
785    // exact work-charge sequence, including short-budget failure points.
786    if n <= 1 {
787        ctx.tick(t.len())?;
788        if n == 1 {
789            ctx.tick(1)?;
790            ctx.tick(1)?;
791            if ADVANCED {
792                ctx.tick(1)?;
793            }
794        }
795        ctx.tick(t.len())?;
796        let mut source = [0u8; 3];
797        let mut order = [0u32; 3];
798        let mut count = 0;
799        for x in t {
800            let local = match source[..count].iter().position(|&i| i == *x) {
801                Some(local) => local,
802                None => {
803                    source[count] = *x;
804                    order[count] = v[*x as usize];
805                    count += 1;
806                    count - 1
807                }
808            };
809            *x = local as u8;
810        }
811        v[..count].copy_from_slice(&order[..count]);
812        return Ok(());
813    }
814    let mut cache = [0u8; 256];
815    let mut last = 128u8;
816    let mut valence = [0u8; 256];
817    ctx.tick(t.len())?;
818    for &i in t.iter() {
819        valence[i as usize] = valence[i as usize].wrapping_add(1);
820    }
821    for i in 0..n {
822        let mut next = i;
823        let mut best = -1;
824        let mut edges = 0;
825        ctx.search(
826            t.as_chunks::<3>().0[i..].iter().enumerate(),
827            |(offset, tri)| {
828                let (a, b, c) = (tri[0] as usize, tri[1] as usize, tri[2] as usize);
829                let (ad, bd, cd) = (
830                    last.wrapping_sub(cache[a]),
831                    last.wrapping_sub(cache[b]),
832                    last.wrapping_sub(cache[c]),
833                );
834                let matches = i32::from(ad < 3) + i32::from(bd < 3) + i32::from(cd < 3);
835                let score = if ADVANCED {
836                    (matches * 1024 + (1023 - ad as i32 - bd as i32 - cd as i32)) * 256
837                        + (255 - valence[a].min(valence[b]).min(valence[c]) as i32)
838                } else {
839                    matches
840                };
841                if score > best {
842                    best = score;
843                    next = i + offset;
844                }
845                if matches >= 2 {
846                    edges += 1;
847                    if !ADVANCED || edges >= level {
848                        return true;
849                    }
850                }
851                false
852            },
853        )?;
854        ctx.tick(next - i + 1)?;
855        let tri = [t[next * 3], t[next * 3 + 1], t[next * 3 + 2]];
856        t.copy_within(i * 3..next * 3, (i + 1) * 3);
857        t[i * 3..i * 3 + 3].copy_from_slice(&tri);
858        last = last.wrapping_add(1);
859        for x in tri {
860            cache[x as usize] = last;
861            valence[x as usize] = valence[x as usize].wrapping_sub(1);
862        }
863    }
864    if ADVANCED {
865        cache.fill(0);
866        for i in 0..n {
867            ctx.tick(1)?;
868            let mut tri = [t[i * 3], t[i * 3 + 1], t[i * 3 + 2]];
869            let [a, b, c] = tri;
870            if cache[a as usize] == 0 && cache[b as usize] != 0 && cache[c as usize] == 0 {
871                tri.rotate_left(1);
872            } else if cache[a as usize] == 0 && cache[b as usize] == 0 && cache[c as usize] == 0 {
873                let (mut ab, mut bc, mut ca) = (false, false, false);
874                for j in i + 1..n.min(i + 4) {
875                    ctx.tick(1)?;
876                    let [oa, ob, oc] = [t[j * 3], t[j * 3 + 1], t[j * 3 + 2]];
877                    ab |= (oa == b && ob == a) || (ob == b && oc == a) || (oc == b && oa == a);
878                    bc |= (oa == c && ob == b) || (ob == c && oc == b) || (oc == c && oa == b);
879                    ca |= (oa == a && ob == c) || (ob == a && oc == c) || (oc == a && oa == c);
880                }
881                if ab && !bc {
882                    tri.rotate_left(1);
883                } else if (ab && !ca) || (!ab && bc && !ca) {
884                    tri.rotate_right(1);
885                }
886            }
887            t[i * 3..i * 3 + 3].copy_from_slice(&tri);
888            for x in tri {
889                cache[x as usize] = 1;
890            }
891        }
892    }
893    let mut remap = [-1i16; 256];
894    let mut order = [0u32; 256];
895    let mut count = 0;
896    ctx.tick(t.len())?;
897    for x in t {
898        let r = &mut remap[*x as usize];
899        if *r < 0 {
900            *r = count as i16;
901            order[count] = v[*x as usize];
902            count += 1;
903        }
904        *x = *r as u8;
905    }
906    v[..count].copy_from_slice(&order[..count]);
907    Ok(())
908}
909/// `meshopt_optimizeMeshletLevel`: atomic destructive variant, levels 0 through 9.
910///
911/// # Errors
912/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
913/// `InvalidParameter` for unsupported meshlet counts or level; `SizeOverflow` for size overflow or `LimitExceeded` for exhausted limits.
914pub fn optimize_meshlet_level_in_place(
915    vertices: &mut [u32],
916    triangles: &mut [u8],
917    level: u8,
918    workspace: &mut Workspace,
919) -> Result<(), Error> {
920    let mut ctx = Context::new(workspace)?;
921    validate_local(vertices, triangles)?;
922    let mut v = [0; 256];
923    let mut t = [0; 1536];
924    v[..vertices.len()].copy_from_slice(vertices);
925    t[..triangles.len()].copy_from_slice(triangles);
926    optimize(
927        &mut v[..vertices.len()],
928        &mut t[..triangles.len()],
929        level,
930        &mut ctx,
931    )?;
932    vertices.copy_from_slice(&v[..vertices.len()]);
933    triangles.copy_from_slice(&t[..triangles.len()]);
934    Ok(())
935}
936/// Atomic destructive `meshopt_optimizeMeshlet` (level zero).
937///
938/// # Errors
939/// Same errors as [`optimize_meshlet_level_in_place`].
940pub fn optimize_meshlet_in_place(
941    vertices: &mut [u32],
942    triangles: &mut [u8],
943    workspace: &mut Workspace,
944) -> Result<(), Error> {
945    optimize_meshlet_level_in_place(vertices, triangles, 0, workspace)
946}
947/// Allocating `meshopt_optimizeMeshletLevel`; unused vertex suffix stays unchanged.
948///
949/// # Errors
950/// Same errors as [`optimize_meshlet_level_in_place`]. `AllocationFailed` if output reservation fails.
951pub fn optimize_meshlet_level(
952    vertices: &[u32],
953    triangles: &[u8],
954    level: u8,
955    workspace: &mut Workspace,
956) -> Result<LocalMeshlet, Error> {
957    let mut ctx = Context::new(workspace)?;
958    validate_local(vertices, triangles)?;
959    let mut v = ctx.copy(vertices)?;
960    let mut t = ctx.copy(triangles)?;
961    optimize(&mut v, &mut t, level, &mut ctx)?;
962    Ok(LocalMeshlet {
963        vertices: v,
964        triangles: t,
965    })
966}
967/// Allocating `meshopt_optimizeMeshlet` (level zero).
968///
969/// # Errors
970/// Same errors as [`optimize_meshlet_level_in_place`]. `AllocationFailed` if output reservation fails.
971pub fn optimize_meshlet(
972    vertices: &[u32],
973    triangles: &[u8],
974    workspace: &mut Workspace,
975) -> Result<LocalMeshlet, Error> {
976    optimize_meshlet_level(vertices, triangles, 0, workspace)
977}
978
979/// Caller-buffer meshlet optimization. Errors leave destinations unchanged;
980/// suffixes beyond the supplied vertex and triangle lengths are preserved.
981///
982/// # Errors
983/// Same errors as [`optimize_meshlet_level_in_place`]. `BufferTooSmall` if either destination is too short.
984pub fn optimize_meshlet_level_into(
985    out_vertices: &mut [u32],
986    out_triangles: &mut [u8],
987    vertices: &[u32],
988    triangles: &[u8],
989    level: u8,
990    workspace: &mut Workspace,
991) -> Result<(), Error> {
992    let mut ctx = Context::new(workspace)?;
993    if out_vertices.len() < vertices.len() || out_triangles.len() < triangles.len() {
994        return Err(Error::BufferTooSmall);
995    }
996    validate_local(vertices, triangles)?;
997    let mut v = [0; 256];
998    let mut t = [0; 1536];
999    v[..vertices.len()].copy_from_slice(vertices);
1000    t[..triangles.len()].copy_from_slice(triangles);
1001    optimize(
1002        &mut v[..vertices.len()],
1003        &mut t[..triangles.len()],
1004        level,
1005        &mut ctx,
1006    )?;
1007    out_vertices[..vertices.len()].copy_from_slice(&v[..vertices.len()]);
1008    out_triangles[..triangles.len()].copy_from_slice(&t[..triangles.len()]);
1009    Ok(())
1010}
1011/// Caller-buffer level-zero meshlet optimization, preserving unused tails.
1012///
1013/// # Errors
1014/// Same errors as [`optimize_meshlet_level_in_place`]. `BufferTooSmall` if either destination is too short.
1015pub fn optimize_meshlet_into(
1016    out_vertices: &mut [u32],
1017    out_triangles: &mut [u8],
1018    vertices: &[u32],
1019    triangles: &[u8],
1020    workspace: &mut Workspace,
1021) -> Result<(), Error> {
1022    optimize_meshlet_level_into(
1023        out_vertices,
1024        out_triangles,
1025        vertices,
1026        triangles,
1027        0,
1028        workspace,
1029    )
1030}
1031
1032#[cfg(test)]
1033mod bounds_root_tests {
1034    use super::{bounds_roots, sqrt8, LANES};
1035
1036    #[test]
1037    fn used_roots_match_full_lanes_bit_for_bit() {
1038        let mut state = 0x1357_2468u32;
1039        let special = [
1040            0,
1041            1,
1042            0x007f_ffff,
1043            0x0080_0000,
1044            0x3f80_0000,
1045            0x7f7f_ffff,
1046            0x8000_0000,
1047            0xbf80_0000,
1048            0x7f80_0000,
1049            0x7fc0_1234,
1050        ];
1051        for sample in 0..512 {
1052            for used in 1..=LANES {
1053                let mut values = [1.; LANES];
1054                for value in &mut values[..used] {
1055                    state = state.wrapping_mul(1664525).wrapping_add(1013904223);
1056                    let bits = if sample < special.len() {
1057                        special[sample]
1058                    } else if sample.is_multiple_of(2) {
1059                        0x0080_0000 + state % 0x7f00_0000
1060                    } else {
1061                        state
1062                    };
1063                    *value = f32::from_bits(bits);
1064                }
1065                assert_eq!(
1066                    bounds_roots(values, used).map(f32::to_bits),
1067                    sqrt8(values).map(f32::to_bits)
1068                );
1069            }
1070        }
1071    }
1072}