Skip to main content

meshoptimizer_rs/
meshlet.rs

1#![allow(clippy::too_many_arguments)]
2// Port of meshoptimizer 1.3 clusterizer.cpp (MIT, Arseny Kapoulkine).
3use crate::math::{root_at_least, RootEstimate, LANES};
4use crate::processing::{cross, dot, finite, point, sub, Context};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8// Every builder root goes through this memo. With std, an operand whose bit
9// pattern is at most f32::MAX is finite and nonnegative (including +0 and
10// subnormals); the native root is bit-identical to the pinned backend there
11// (0.2.10 exhaustive comparison; IEEE 754 correct rounding). Every other bit
12// pattern, and every operand in no_std, keeps the pinned memoized backend.
13struct SqrtCache(crate::math::SqrtCache);
14impl SqrtCache {
15    const fn new() -> Self {
16        Self(crate::math::SqrtCache::new())
17    }
18    #[inline(always)]
19    fn sqrt(&mut self, value: f32) -> f32 {
20        #[cfg(feature = "std")]
21        if value.to_bits() <= f32::MAX.to_bits() {
22            return value.sqrt();
23        }
24        self.0.sqrt(value)
25    }
26}
27// Eight roots under the same guard: all lanes finite and nonnegative use the
28// native root; otherwise the pinned eight-lane backend.
29#[inline(always)]
30fn sqrt8(values: [f32; LANES]) -> [f32; LANES] {
31    #[cfg(feature = "std")]
32    if values.iter().all(|v| v.to_bits() <= f32::MAX.to_bits()) {
33        return values.map(f32::sqrt);
34    }
35    crate::math::sqrt8(values)
36}
37
38/// Current 1.3 descriptor: triangle offsets are consecutive byte offsets, without padding.
39#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
40pub struct Meshlet {
41    /// Offset in the vertex-reference array.
42    pub vertex_offset: u32,
43    /// Offset in the byte triangle array.
44    pub triangle_offset: u32,
45    /// Number of referenced vertices.
46    pub vertex_count: u32,
47    /// Number of triangles (three bytes each).
48    pub triangle_count: u32,
49}
50/// Complete tightly packed meshlet output.
51#[derive(Debug, Default, PartialEq, Eq)]
52pub struct MeshletsGeneric<I: crate::Index = u32> {
53    /// Meshlet descriptors in construction order.
54    pub meshlets: Vec<Meshlet>,
55    /// Original vertex references.
56    pub vertices: Vec<I>,
57    /// Local triangle bytes, without per-meshlet padding.
58    pub triangles: Vec<u8>,
59}
60/// Limits used by all meshlet builders.
61#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub struct MeshletSettings {
63    /// Maximum vertices, 3 through 256.
64    pub max_vertices: usize,
65    /// Maximum triangles, 1 through 512.
66    pub max_triangles: usize,
67}
68impl Default for MeshletSettings {
69    fn default() -> Self {
70        Self {
71            max_vertices: 64,
72            max_triangles: 124,
73        }
74    }
75}
76/// Used prefixes after caller-buffer meshlet construction.
77#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
78pub struct MeshletSizes {
79    /// Number of descriptors.
80    pub meshlets: usize,
81    /// Number of vertex references.
82    pub vertices: usize,
83    /// Number of triangle bytes.
84    pub triangles: usize,
85}
86/// `meshopt_buildMeshletsBound`: conservative descriptor capacity, with checked arithmetic.
87///
88/// # Errors
89/// `InvalidTopology` for incomplete triangles; `InvalidParameter` for unsupported meshlet limits;
90/// `SizeOverflow` if the bound cannot be represented.
91#[inline(always)]
92pub fn build_meshlets_bound(
93    index_count: usize,
94    max_vertices: usize,
95    max_triangles: usize,
96) -> Result<usize, Error> {
97    if !index_count.is_multiple_of(3) {
98        return Err(Error::InvalidTopology);
99    }
100    if !(3..=256).contains(&max_vertices) || !(1..=512).contains(&max_triangles) {
101        return Err(Error::InvalidParameter);
102    }
103    let v = max_vertices - 2;
104    let a = small_divide(
105        index_count.checked_add(v - 1).ok_or(Error::SizeOverflow)?,
106        v,
107    );
108    let b = small_divide(
109        (index_count / 3)
110            .checked_add(max_triangles - 1)
111            .ok_or(Error::SizeOverflow)?,
112        max_triangles,
113    );
114    Ok(a.max(b))
115}
116// ceil(2^32 / d) for every divisor 1..=512 (D78).
117static RECIPROCALS: [u64; 513] = {
118    let mut table = [0u64; 513];
119    let mut d = 1;
120    while d < 513 {
121        table[d] = (1u64 << 32).div_ceil(d as u64);
122        d += 1;
123    }
124    table
125};
126// x / d for 1 <= d <= 512. Below 2^22 a 64-bit multiply by ceil(2^32 / d)
127// is exact: it exceeds x / d by less than 2^22 / 2^32 = 2^-10, while the
128// fractional part of x / d is at most 1 - 1/512 = 1 - 2^-9.
129#[inline(always)]
130fn small_divide(x: usize, d: usize) -> usize {
131    match RECIPROCALS.get(d) {
132        Some(&m) if d != 0 && x < 1 << 22 => ((x as u64 * m) >> 32) as usize,
133        _ => x / d,
134    }
135}
136pub(crate) struct Output<'a> {
137    pub(crate) descriptors: &'a mut [Meshlet],
138    pub(crate) vertices: &'a mut [u32],
139    pub(crate) triangles: &'a mut [u8],
140    pub(crate) current: Meshlet,
141    pub(crate) count: usize,
142}
143pub(crate) trait UsedVertices {
144    fn local(&self, vertex: usize) -> i16;
145    fn set_local(&mut self, vertex: usize, local: i16);
146}
147impl UsedVertices for [i16] {
148    #[inline(always)]
149    fn local(&self, vertex: usize) -> i16 {
150        self[vertex]
151    }
152    #[inline(always)]
153    fn set_local(&mut self, vertex: usize, local: i16) {
154        self[vertex] = local;
155    }
156}
157impl<T> UsedVertices for Vec<T>
158where
159    [T]: UsedVertices,
160{
161    #[inline(always)]
162    fn local(&self, vertex: usize) -> i16 {
163        self.as_slice().local(vertex)
164    }
165    #[inline(always)]
166    fn set_local(&mut self, vertex: usize, local: i16) {
167        self.as_mut_slice().set_local(vertex, local);
168    }
169}
170impl Output<'_> {
171    #[inline(always)]
172    pub(crate) fn append<U: UsedVertices + ?Sized>(
173        &mut self,
174        t: &[u32; 3],
175        used: &mut U,
176        s: MeshletSettings,
177        split: bool,
178        ctx: &mut Context<'_>,
179    ) -> Result<bool, Error> {
180        ctx.tick(1)?;
181        // Work on a local copy of the open descriptor: the output slices could
182        // otherwise alias it for the optimizer, forcing a reload per access.
183        let mut m = self.current;
184        let [a, b, c] = t.map(|v| v as usize);
185        let mut local = [used.local(a), used.local(b), used.local(c)];
186        // Count missing corners before deduplicating, as upstream does. Keep
187        // the original conservative flush decision on degenerate triangles.
188        let extra = local.iter().filter(|&&v| v < 0).count();
189        let mut flush = false;
190        if m.vertex_count as usize + extra > s.max_vertices
191            || m.triangle_count as usize >= s.max_triangles
192            || split
193        {
194            self.descriptors[self.count] = m;
195            self.count += 1;
196            ctx.tick(m.vertex_count as usize)?;
197            for &v in &self.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
198                used.set_local(v as usize, -1);
199            }
200            m.vertex_offset += m.vertex_count;
201            m.triangle_offset += m.triangle_count * 3;
202            m.vertex_count = 0;
203            m.triangle_count = 0;
204            local = [-1; 3];
205            flush = true;
206        }
207        let off = m.triangle_offset as usize + m.triangle_count as usize * 3;
208        let triangle = &mut self.triangles[off..off + 3];
209        for k in 0..3 {
210            if local[k] < 0 {
211                // A preceding missing corner may have inserted this vertex.
212                // The usual distinct-corner case needs no second table load.
213                if k > 0 && t[k] == t[0] {
214                    local[k] = local[0];
215                } else if k == 2 && t[k] == t[1] {
216                    local[k] = local[1];
217                } else {
218                    local[k] = m.vertex_count as i16;
219                    used.set_local(t[k] as usize, local[k]);
220                    self.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
221                    m.vertex_count += 1;
222                }
223            }
224            triangle[k] = local[k] as u8;
225        }
226        m.triangle_count += 1;
227        self.current = m;
228        Ok(flush)
229    }
230    fn finish(&mut self) -> MeshletSizes {
231        if self.current.triangle_count != 0 {
232            self.descriptors[self.count] = self.current;
233            self.count += 1;
234        }
235        MeshletSizes {
236            meshlets: self.count,
237            vertices: (self.current.vertex_offset + self.current.vertex_count) as usize,
238            triangles: (self.current.triangle_offset + self.current.triangle_count * 3) as usize,
239        }
240    }
241}
242fn validate(s: MeshletSettings, min: usize, weight: f32, split: f32) -> Result<(), Error> {
243    build_meshlets_bound(0, s.max_vertices, s.max_triangles)?;
244    if min == 0
245        || min > s.max_triangles
246        || !weight.is_finite()
247        || !(0.0..=1.0).contains(&weight)
248        || !split.is_finite()
249        || split < 0.
250    {
251        return Err(Error::InvalidParameter);
252    }
253    Ok(())
254}
255#[derive(Clone, Copy, Default)]
256struct Cone {
257    p: [f32; 3],
258    n: [f32; 3],
259}
260// `getMeshletCone` position: the accumulated centroid over the count.
261#[inline(always)]
262fn cone_position(acc: Cone, count: u32) -> [f32; 3] {
263    let scale = if count == 0 { 0. } else { 1. / count as f32 };
264    acc.p.map(|v| v * scale)
265}
266// `getMeshletCone` normal: acc * (1 / sqrt(|acc|^2)), or zero for |acc| = 0.
267struct MeshletNormal {
268    low: [f32; 3],
269    high: [f32; 3],
270    exact: Option<[f32; 3]>,
271}
272impl MeshletNormal {
273    fn exact(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
274        let l = dot(acc, acc);
275        let scale = if l == 0. { 0. } else { 1. / roots.sqrt(l) };
276        let n = acc.map(|v| v * scale);
277        Self {
278            low: n,
279            high: n,
280            exact: Some(n),
281        }
282    }
283    // Bounds of each rounded component: the table bounds the rounded scale
284    // fl(1 / fl(sqrt(l))) without a division (D79), and acc_k * scale is
285    // monotone in scale with the sign of acc_k.
286    #[inline(always)]
287    fn bounds(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
288        let l = dot(acc, acc);
289        let Some(root) = RootEstimate::new(l) else {
290            return Self::exact(acc, roots);
291        };
292        let (scale_low, scale_high) = root.inverse_table();
293        let mut low = [0f32; 3];
294        let mut high = [0f32; 3];
295        for k in 0..3 {
296            let (a, b) = (acc[k] * scale_low, acc[k] * scale_high);
297            (low[k], high[k]) = if acc[k] >= 0. { (a, b) } else { (b, a) };
298        }
299        Self {
300            low,
301            high,
302            exact: None,
303        }
304    }
305}
306// Adjacency offset, live triangle count and meshlet-local index of one vertex,
307// packed so that a meshlet-vertex visit touches one record.
308#[derive(Clone, Copy)]
309struct VertexState {
310    offset: u32,
311    live: u32,
312    local: i16,
313}
314impl Default for VertexState {
315    fn default() -> Self {
316        Self {
317            offset: 0,
318            live: 0,
319            local: -1,
320        }
321    }
322}
323impl UsedVertices for [VertexState] {
324    #[inline(always)]
325    fn local(&self, vertex: usize) -> i16 {
326        self[vertex].local
327    }
328    #[inline(always)]
329    fn set_local(&mut self, vertex: usize, local: i16) {
330        self[vertex].local = local;
331    }
332}
333struct Adjacency {
334    vertices: Vec<VertexState>,
335    data: Vec<u32>,
336}
337fn adjacency(indices: &[u32], n: usize, ctx: &mut Context<'_>) -> Result<Adjacency, Error> {
338    let mut vertices = ctx.alloc::<VertexState>(n)?;
339    let mut data = ctx.alloc::<u32>(indices.len())?;
340    ctx.tick(n + indices.len() * 2)?;
341    for &v in indices {
342        vertices[v as usize].live += 1;
343    }
344    let mut offset = 0;
345    for vertex in vertices.iter_mut() {
346        vertex.offset = offset;
347        offset += vertex.live;
348    }
349    for (i, t) in indices.as_chunks::<3>().0.iter().enumerate() {
350        for &v in t {
351            let o = &mut vertices[v as usize].offset;
352            data[*o as usize] = i as u32;
353            *o += 1;
354        }
355    }
356    for vertex in vertices.iter_mut() {
357        vertex.offset -= vertex.live;
358    }
359    Ok(Adjacency { vertices, data })
360}
361// Preserve the upstream packed eight-byte KD node.
362#[derive(Clone, Copy, Default)]
363struct Node {
364    data: u32,
365    meta: u32,
366}
367impl Node {
368    fn axis(self) -> usize {
369        (self.meta & 3) as usize
370    }
371    fn children(self) -> usize {
372        (self.meta >> 2) as usize
373    }
374    fn set(&mut self, axis: usize, children: usize) -> Result<(), Error> {
375        if children > 0x3fffffff {
376            return Err(Error::SizeOverflow);
377        }
378        self.meta = (children as u32) << 2 | axis as u32;
379        Ok(())
380    }
381}
382
383// Split statistics of one kd range: Welford mean and variance per axis.
384#[derive(Clone, Copy, Default)]
385struct KdSplit {
386    mean: [f32; 3],
387    axis: usize,
388}
389impl KdSplit {
390    #[inline(always)]
391    fn finish(mean: [f32; 3], vars: [f32; 3]) -> Self {
392        let axis = if vars[0] >= vars[1] && vars[0] >= vars[2] {
393            0
394        } else if vars[1] >= vars[2] {
395            1
396        } else {
397            2
398        };
399        Self { mean, axis }
400    }
401}
402#[inline(always)]
403fn welford(p: [f32; 3], mean: &mut [f32; 3], vars: &mut [f32; 3], runs: f32) {
404    for k in 0..3 {
405        let delta = p[k] - mean[k];
406        mean[k] += delta * runs;
407        vars[k] += delta * (p[k] - mean[k]);
408    }
409}
410fn kd_stats(order: &[u32], cones: &[Cone]) -> KdSplit {
411    let (mut mean, mut vars) = ([0.; 3], [0.; 3]);
412    let (mut runc, mut runs) = (1f32, 1f32);
413    for &v in order {
414        welford(cones[v as usize].p, &mut mean, &mut vars, runs);
415        runc += 1.;
416        runs = 1. / runc;
417    }
418    KdSplit::finish(mean, vars)
419}
420// Statistics of two sibling ranges in one loop: the two Welford chains are
421// independent, and both use the same running weight at the same position.
422fn kd_stats2(a: &[u32], b: &[u32], cones: &[Cone]) -> (KdSplit, KdSplit) {
423    let (mut am, mut av, mut bm, mut bv) = ([0.; 3], [0.; 3], [0.; 3], [0.; 3]);
424    let (mut runc, mut runs) = (1f32, 1f32);
425    let common = a.len().min(b.len());
426    for (&x, &y) in a[..common].iter().zip(&b[..common]) {
427        welford(cones[x as usize].p, &mut am, &mut av, runs);
428        welford(cones[y as usize].p, &mut bm, &mut bv, runs);
429        runc += 1.;
430        runs = 1. / runc;
431    }
432    let (rest, mean, vars) = if a.len() > common {
433        (&a[common..], &mut am, &mut av)
434    } else {
435        (&b[common..], &mut bm, &mut bv)
436    };
437    for &v in rest {
438        welford(cones[v as usize].p, mean, vars, runs);
439        runc += 1.;
440        runs = 1. / runc;
441    }
442    (KdSplit::finish(am, av), KdSplit::finish(bm, bv))
443}
444// `kdtreeBuild`. A split node computes its children's statistics together
445// (they depend only on the partition, which later recursion does not touch);
446// each child still charges its work and checks its mean when it is built,
447// so budget failures and errors occur exactly where the recursion did.
448fn kd_build(
449    nodes: &mut [Node],
450    offset: usize,
451    order: &mut [u32],
452    cones: &[Cone],
453    depth: usize,
454    split: Option<KdSplit>,
455    ctx: &mut Context<'_>,
456) -> Result<usize, Error> {
457    let n = order.len();
458    let mut middle = 0;
459    let mut stats = KdSplit::default();
460    if n > 8 {
461        ctx.tick(n * 2)?;
462        stats = split.unwrap_or_else(|| kd_stats(order, cones));
463        let (mean, axis) = (stats.mean, stats.axis);
464        finite(mean[axis])?;
465        for i in 0..n {
466            let v = cones[order[i] as usize].p[axis];
467            order.swap(middle, i);
468            middle += usize::from(v < mean[axis]);
469        }
470    }
471    if n <= 8 || middle <= 4 || middle >= n - 4 || depth >= 50 {
472        if n > 0x3fffffff {
473            return Err(Error::SizeOverflow);
474        }
475        ctx.tick(n)?;
476        for (i, &v) in order.iter().enumerate() {
477            nodes[offset + i] = Node {
478                data: v,
479                meta: 3 | ((if i == 0 { n as u32 } else { 0x3fffffff }) << 2),
480            };
481        }
482        return Ok(offset + n);
483    }
484    nodes[offset].data = stats.mean[stats.axis].to_bits();
485    let (left, right) = order.split_at_mut(middle);
486    let (left_split, right_split) = match (left.len() > 8, right.len() > 8) {
487        (true, true) => {
488            let (l, r) = kd_stats2(left, right, cones);
489            (Some(l), Some(r))
490        }
491        (true, false) => (Some(kd_stats(left, cones)), None),
492        (false, true) => (None, Some(kd_stats(right, cones))),
493        (false, false) => (None, None),
494    };
495    let next = kd_build(nodes, offset + 1, left, cones, depth + 1, left_split, ctx)?;
496    nodes[offset].set(stats.axis, next - offset - 1)?;
497    kd_build(nodes, next, right, cones, depth + 1, right_split, ctx)
498}
499fn nearest<const CHECK: bool>(
500    nodes: &mut [Node],
501    root: usize,
502    cones: &[Cone],
503    emitted: &[u8],
504    p: [f32; 3],
505    result: &mut u32,
506    limit: &mut f32,
507    roots: &mut SqrtCache,
508    ctx: &mut Context<'_>,
509) -> Result<(), Error> {
510    let covered = nodes
511        .len()
512        .checked_mul(2)
513        .is_some_and(|bound| ctx.work.covers(bound).unwrap_or(false));
514    if covered && !CHECK {
515        let mut search = Covered {
516            nodes,
517            cones,
518            emitted,
519            p,
520            result: *result,
521            limit: *limit,
522            visits: 0,
523            roots,
524        };
525        let status = search.nearest(root);
526        // The same visits nearest_inner::<false, true> charges one by one,
527        // charged once on every exit (the covered budget cannot exhaust).
528        ctx.work.add_covered(search.visits);
529        *result = search.result;
530        *limit = search.limit;
531        status
532    } else if covered {
533        nearest_inner::<CHECK, true>(nodes, root, cones, emitted, p, result, limit, roots, ctx)
534    } else {
535        nearest_inner::<CHECK, false>(nodes, root, cones, emitted, p, result, limit, roots, ctx)
536    }
537}
538
539// The moderate (!CHECK) search when the budget covers every visit: the
540// statements and order of nearest_inner::<false, true>, with the invariant
541// arguments in one record (the recursion passes two arguments, not nine) and
542// the visits tallied locally instead of charged per node.
543struct Covered<'a> {
544    nodes: &'a mut [Node],
545    cones: &'a [Cone],
546    emitted: &'a [u8],
547    p: [f32; 3],
548    result: u32,
549    limit: f32,
550    visits: usize,
551    roots: &'a mut SqrtCache,
552}
553impl Covered<'_> {
554    fn nearest(&mut self, root: usize) -> Result<(), Error> {
555        self.visits += 1;
556        let node = self.nodes[root];
557        if node.children() == 0 {
558            return Ok(());
559        }
560        if node.axis() == 3 {
561            let count = node.children();
562            // One bound for both per-vertex tables: a single index check
563            // per item (kd-tree items index both).
564            let n = self.cones.len().min(self.emitted.len());
565            let (cones, emitted) = (&self.cones[..n], &self.emitted[..n]);
566            let mut inactive = true;
567            for item in &self.nodes[root..root + count] {
568                let v = item.data as usize;
569                if emitted[v] == EMITTED {
570                    continue;
571                }
572                inactive = false;
573                let d = sub(cones[v].p, self.p);
574                let square = dot(d, d);
575                if PRUNE && (lower_distance(d) >= self.limit || root_at_least(square, self.limit)) {
576                    continue;
577                }
578                let distance = moderate_root(square, self.roots);
579                if distance < self.limit {
580                    self.result = v as u32;
581                    self.limit = distance;
582                }
583            }
584            self.visits += count;
585            if inactive {
586                self.nodes[root].set(3, 0)?;
587            }
588        } else {
589            let delta = self.p[node.axis()] - f32::from_bits(node.data);
590            let first = if delta <= 0. { 0 } else { node.children() };
591            let second = first ^ node.children();
592            if self.nodes[root + 1 + first].children() | self.nodes[root + 1 + second].children()
593                == 0
594            {
595                self.nodes[root].set(node.axis(), 0)?;
596            }
597            self.nearest(root + 1 + first)?;
598            if delta.abs() <= self.limit {
599                self.nearest(root + 1 + second)?;
600            }
601        }
602        Ok(())
603    }
604}
605
606fn nearest_inner<const CHECK: bool, const COVERED: bool>(
607    nodes: &mut [Node],
608    root: usize,
609    cones: &[Cone],
610    emitted: &[u8],
611    p: [f32; 3],
612    result: &mut u32,
613    limit: &mut f32,
614    roots: &mut SqrtCache,
615    ctx: &mut Context<'_>,
616) -> Result<(), Error> {
617    if COVERED {
618        ctx.work.add_covered(1);
619    } else {
620        ctx.tick(1)?;
621    }
622    let node = nodes[root];
623    if node.children() == 0 {
624        return Ok(());
625    }
626    if node.axis() == 3 && !CHECK && (COVERED || ctx.work.covers(node.children())?) {
627        // Moderate leaves cannot fail: one inline loop, charged once.
628        let count = node.children();
629        let mut inactive = true;
630        for item in &nodes[root..root + count] {
631            let v = item.data as usize;
632            if emitted[v] == EMITTED {
633                continue;
634            }
635            inactive = false;
636            let d = sub(cones[v].p, p);
637            let square = dot(d, d);
638            if PRUNE && (lower_distance(d) >= *limit || root_at_least(square, *limit)) {
639                continue;
640            }
641            let distance = moderate_root(square, roots);
642            if distance < *limit {
643                *result = v as u32;
644                *limit = distance;
645            }
646        }
647        if COVERED {
648            ctx.work.add_covered(count);
649        } else {
650            ctx.tick(count)?;
651        }
652        if inactive {
653            nodes[root].set(3, 0)?;
654        }
655    } else if node.axis() == 3 {
656        let mut inactive = true;
657        ctx.scan(0..node.children(), |_ctx, i| {
658            let v = nodes[root + i].data as usize;
659            if emitted[v] == EMITTED {
660                return Ok(());
661            }
662            inactive = false;
663            let d = sub(cones[v].p, p);
664            if !CHECK && PRUNE && (lower_distance(d) >= *limit || root_at_least(dot(d, d), *limit))
665            {
666                return Ok(());
667            }
668            let distance = roots.sqrt(number::<CHECK>(dot(d, d))?);
669            if distance < *limit {
670                *result = v as u32;
671                *limit = distance;
672            }
673            Ok(())
674        })?;
675        if inactive {
676            nodes[root].set(3, 0)?;
677        }
678    } else {
679        let delta = p[node.axis()] - f32::from_bits(node.data);
680        let first = if delta <= 0. { 0 } else { node.children() };
681        let second = first ^ node.children();
682        if nodes[root + 1 + first].children() | nodes[root + 1 + second].children() == 0 {
683            nodes[root].set(node.axis(), 0)?;
684        }
685        nearest_inner::<CHECK, COVERED>(
686            nodes,
687            root + 1 + first,
688            cones,
689            emitted,
690            p,
691            result,
692            limit,
693            roots,
694            ctx,
695        )?;
696        if delta.abs() <= *limit {
697            nearest_inner::<CHECK, COVERED>(
698                nodes,
699                root + 1 + second,
700                cones,
701                emitted,
702                p,
703                result,
704                limit,
705                roots,
706                ctx,
707            )?;
708        }
709    }
710    Ok(())
711}
712// Root-bracket pruning of moderate candidates. A pruned candidate's rounded
713// root is at least the current limit, so it never changes a strict-less
714// selection; the tests only avoid computing that root. With std the root is
715// the native one (a single instruction), cheaper than the tests, so the
716// candidates are evaluated exactly instead. no_std keeps the pinned backend
717// and the pruning.
718const PRUNE: bool = cfg!(not(feature = "std"));
719// The moderate meshlet envelope proves this squared distance finite and nonnegative.
720#[inline(always)]
721fn moderate_root(value: f32, roots: &mut SqrtCache) -> f32 {
722    #[cfg(feature = "std")]
723    {
724        let _ = roots;
725        value.sqrt()
726    }
727    #[cfg(not(feature = "std"))]
728    {
729        roots.sqrt(value)
730    }
731}
732// Each absolute component is a conservative lower bound on the correctly
733// rounded Euclidean distance. Use only after the finite-coordinate envelope.
734#[inline(always)]
735fn lower_distance(d: [f32; 3]) -> f32 {
736    // Plain comparisons: moderate inputs are finite, so NaN-aware max is unneeded.
737    let (x, y, z) = (d[0].abs(), d[1].abs(), d[2].abs());
738    let m = if x > y { x } else { y };
739    let m = if m > z { m } else { z };
740    // Below this envelope a rounded square can be subnormal or zero.
741    if m >= 1.0e-18 {
742        m
743    } else {
744        0.0
745    }
746}
747#[inline(always)]
748fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
749    if CHECK {
750        finite(value)
751    } else {
752        Ok(value)
753    }
754}
755#[inline(always)]
756fn distance<const CHECK: bool>(
757    a: [f32; 3],
758    b: [f32; 3],
759    roots: &mut SqrtCache,
760) -> Result<f32, Error> {
761    let d = sub(a, b);
762    Ok(roots.sqrt(number::<CHECK>(dot(d, d))?))
763}
764// The selected candidate's score is kept as a bracket [lo, hi] around the
765// exact upstream score. `known` means lo == hi == the exact score. The exact
766// root is computed only when a comparison cannot be decided from brackets.
767struct Selection {
768    triangle: u32,
769    priority: i32,
770    lo: f32,
771    hi: f32,
772    known: bool,
773    square: f32,
774}
775impl Selection {
776    fn new() -> Self {
777        Self {
778            triangle: u32::MAX,
779            priority: 5,
780            lo: f32::MAX,
781            hi: f32::MAX,
782            known: true,
783            square: 0.,
784        }
785    }
786}
787struct CandidateInput<'a> {
788    triangles: &'a [[u32; 3]],
789    vertices: &'a [VertexState],
790    cones: &'a [Cone],
791    meshlet: Cone,
792    weight: f32,
793    radius: f32,
794    // Reciprocal bounds around 1 / radius; `bounded` when both are finite
795    // and the radius is a positive normal value.
796    inverse_low: f32,
797    inverse_high: f32,
798    bounded: bool,
799    // Bounded mode: bounds of the normalized meshlet normal, from root bounds
800    // of its squared length; the exact normal is computed only on demand.
801    accumulated: [f32; 3],
802    normal_low: [f32; 3],
803    normal_high: [f32; 3],
804}
805// Mutable state of one neighbor search: the root memo and the exact meshlet
806// normal once computed. Kept out of CandidateInput so `&CandidateInput`
807// stays freeze-only and its fields can be held in registers.
808struct Search<'r> {
809    roots: &'r mut SqrtCache,
810    normal: Option<[f32; 3]>,
811    // Candidates come from the meshlet's candidate list rather than in visit
812    // order: exact ties are then broken by the upstream visit order.
813    listed: bool,
814    data: &'r [u32],
815}
816impl CandidateInput<'_> {
817    #[inline(always)]
818    fn one<const CHECK: bool>(
819        &self,
820        tri: u32,
821        local: u16,
822        selected: &mut Selection,
823        search: &mut Search<'_>,
824    ) -> Result<(), Error> {
825        let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
826        let (av, bv, cv) = (self.vertices[a], self.vertices[b], self.vertices[c]);
827        // A live triangle is listed under each of its meshlet vertices. When one
828        // of them precedes the vertex being scanned, this visit repeats an
829        // earlier one with identical priority and score; under the strict
830        // lexicographic selection (including NaN scores) it cannot change it.
831        if (av.local as u16).min(bv.local as u16).min(cv.local as u16) < local {
832            return Ok(());
833        }
834        self.evaluate::<CHECK>(tri, [av, bv, cv], selected, search)
835    }
836    #[inline(always)]
837    fn evaluate<const CHECK: bool>(
838        &self,
839        tri: u32,
840        [av, bv, cv]: [VertexState; 3],
841        selected: &mut Selection,
842        search: &mut Search<'_>,
843    ) -> Result<(), Error> {
844        let extra = i32::from(av.local < 0) + i32::from(bv.local < 0) + i32::from(cv.local < 0);
845        let (al, bl, cl) = (av.live, bv.live, cv.live);
846        let priority = if extra == 0 {
847            0
848        } else if al == 1 || bl == 1 || cl == 1 {
849            1
850        } else if i32::from(al == 2) + i32::from(bl == 2) + i32::from(cl == 2) >= 2 {
851            1 + extra
852        } else {
853            2 + extra
854        };
855        if priority > selected.priority {
856            return Ok(());
857        }
858        let cone = self.cones[tri as usize];
859        let dp = sub(cone.p, self.meshlet.p);
860        let square = dot(dp, dp);
861        let square = if CHECK { finite(square)? } else { square };
862        if !CHECK && self.bounded {
863            if PRUNE {
864                self.bracketed(tri, priority, cone.n, square, selected, search);
865            } else {
866                self.exact_bounded(tri, priority, cone.n, square, selected, search);
867            }
868            return Ok(());
869        }
870        let clamped = self.clamped(dot(cone.n, self.meshlet.n));
871        let distance = search.roots.sqrt(square);
872        let score = self.score(distance, clamped);
873        // Zero-area geometry retains the upstream NaN score/tie behavior.
874        if priority < selected.priority || score < selected.hi {
875            *selected = Selection {
876                triangle: tri,
877                priority,
878                lo: score,
879                hi: score,
880                known: true,
881                square,
882            };
883        }
884        Ok(())
885    }
886    #[inline(always)]
887    fn clamped(&self, spread: f32) -> f32 {
888        let cc = 1. - spread * self.weight;
889        if cc < 1e-3 {
890            1e-3
891        } else {
892            cc
893        }
894    }
895    #[inline(always)]
896    fn score(&self, distance: f32, clamped: f32) -> f32 {
897        (1. + distance / self.radius * (1. - self.weight)) * clamped
898    }
899    // Bounded mode (moderate inputs, positive normal radius with finite
900    // reciprocal bounds): every operand is finite, the radius and cone factor
901    // are positive and 0 <= weight <= 1. Each rounded operation of the score
902    // is then monotone in each input: nondecreasing in the distance and in
903    // the cone factor, the cone factor nonincreasing in the spread, and each
904    // rounded product of the spread nondecreasing (cone component >= 0) or
905    // nonincreasing (< 0) in the meshlet normal component. Scores from the
906    // bounding inputs therefore bound the exact upstream score, and a
907    // comparison decided by disjoint bounds equals the exact comparison.
908    // Multiplying by a reciprocal rounded away from 1/radius by more than
909    // its own rounding keeps the quotient on one side of the real d / radius.
910    #[inline(always)]
911    fn score_low(&self, distance: f32, clamped: f32) -> f32 {
912        (1. + distance * self.inverse_low * (1. - self.weight)) * clamped
913    }
914    #[inline(always)]
915    fn score_high(&self, distance: f32, clamped: f32) -> f32 {
916        (1. + distance * self.inverse_high * (1. - self.weight)) * clamped
917    }
918    // Bounds of the cone factor from the meshlet normal bounds.
919    #[inline(always)]
920    fn clamped_bounds(&self, n: [f32; 3], low: bool) -> f32 {
921        // Bounded-mode normals are finite. With zero cone weight the factor
922        // is exactly one, independently of the normal interval.
923        if self.weight == 0. {
924            return 1.;
925        }
926        // Each exact term n_k * normal_k lies between the products with the
927        // normal bounds, so their larger (smaller) values bound the spread.
928        let (lo, hi) = (self.normal_low, self.normal_high);
929        let term = |k: usize| {
930            let (a, b) = (n[k] * lo[k], n[k] * hi[k]);
931            if (a > b) == low {
932                a
933            } else {
934                b
935            }
936        };
937        // The cone factor decreases with the spread.
938        self.clamped(term(0) + term(1) + term(2))
939    }
940    // The exact meshlet normal, computed at most once per neighbor search.
941    #[cold]
942    #[inline(never)]
943    fn exact_normal(&self, search: &mut Search<'_>) -> [f32; 3] {
944        if self.weight == 0. {
945            return [0.; 3];
946        }
947        if let Some(n) = search.normal {
948            return n;
949        }
950        let l = dot(self.accumulated, self.accumulated);
951        let scale = if l == 0. {
952            0.
953        } else {
954            1. / search.roots.sqrt(l)
955        };
956        let n = self.accumulated.map(|v| v * scale);
957        search.normal = Some(n);
958        n
959    }
960    #[inline(always)]
961    fn bracketed(
962        &self,
963        tri: u32,
964        priority: i32,
965        normal: [f32; 3],
966        square: f32,
967        selected: &mut Selection,
968        search: &mut Search<'_>,
969    ) {
970        let clamped_low = self.clamped_bounds(normal, true);
971        let (lo, hi) = match RootEstimate::new(square) {
972            Some(root) => {
973                // Division-free table bounds reject most losers (listed
974                // candidates only on a strict loss: they may win a tie).
975                let low = self.score_low(root.table().0, clamped_low);
976                if priority == selected.priority
977                    && (low > selected.hi || (low == selected.hi && !search.listed))
978                {
979                    return;
980                }
981                let (dlo, dhi) = root.bounds();
982                (
983                    self.score_low(dlo, clamped_low),
984                    self.score_high(dhi, self.clamped_bounds(normal, false)),
985                )
986            }
987            None => {
988                let d = search.roots.sqrt(square);
989                (
990                    self.score_low(d, clamped_low),
991                    self.score_high(d, self.clamped_bounds(normal, false)),
992                )
993            }
994        };
995        if priority == selected.priority {
996            // Listed candidates may tie with an earlier-visited selection.
997            if lo > selected.hi || (lo == selected.hi && !search.listed) {
998                return;
999            }
1000            if hi >= selected.lo {
1001                self.resolve(tri, priority, square, selected, search);
1002                return;
1003            }
1004        }
1005        *selected = Selection {
1006            triangle: tri,
1007            priority,
1008            lo,
1009            hi,
1010            known: false,
1011            square,
1012        };
1013    }
1014    // Bounded mode with std (see PRUNE): the exact score with the native root
1015    // of the moderate square, as `resolve` computes it. No bracket is ever
1016    // stored, so every selection is exact; listed candidates break exact ties
1017    // by the upstream visit order, as in `resolve`.
1018    #[inline(always)]
1019    fn exact_bounded(
1020        &self,
1021        tri: u32,
1022        priority: i32,
1023        normal: [f32; 3],
1024        square: f32,
1025        selected: &mut Selection,
1026        search: &mut Search<'_>,
1027    ) {
1028        // exact_normal is zero for zero weight; skip its out-of-line call.
1029        let n = if self.weight == 0. {
1030            [0.; 3]
1031        } else {
1032            self.exact_normal(search)
1033        };
1034        let distance = moderate_root(square, search.roots);
1035        let score = self.score(distance, self.clamped(dot(normal, n)));
1036        if priority < selected.priority
1037            || score < selected.hi
1038            || (search.listed
1039                && score == selected.hi
1040                && self.visit(tri, search.data) < self.visit(selected.triangle, search.data))
1041        {
1042            *selected = Selection {
1043                triangle: tri,
1044                priority,
1045                lo: score,
1046                hi: score,
1047                known: true,
1048                square,
1049            };
1050        }
1051    }
1052    // Upstream visit order of a candidate: its earliest meshlet vertex (by
1053    // local index), then its position in that vertex's live adjacency list.
1054    fn visit(&self, tri: u32, data: &[u32]) -> (u16, usize) {
1055        let mut first = (u16::MAX, 0usize);
1056        for &v in &self.triangles[tri as usize] {
1057            let state = self.vertices[v as usize];
1058            if (state.local as u16) < first.0 {
1059                first = (state.local as u16, v as usize);
1060            }
1061        }
1062        let state = self.vertices[first.1];
1063        let list = &data[state.offset as usize..][..state.live as usize];
1064        (
1065            first.0,
1066            list.iter().position(|&t| t == tri).unwrap_or(list.len()),
1067        )
1068    }
1069    // Undecided equal-priority comparison: compute both exact scores.
1070    #[cold]
1071    #[inline(never)]
1072    fn resolve(
1073        &self,
1074        tri: u32,
1075        priority: i32,
1076        square: f32,
1077        selected: &mut Selection,
1078        search: &mut Search<'_>,
1079    ) {
1080        let n = self.exact_normal(search);
1081        let mut exact = |tri: u32, square: f32| {
1082            let clamped = self.clamped(dot(self.cones[tri as usize].n, n));
1083            self.score(search.roots.sqrt(square), clamped)
1084        };
1085        if !selected.known {
1086            let score = exact(selected.triangle, selected.square);
1087            selected.lo = score;
1088            selected.hi = score;
1089            selected.known = true;
1090        }
1091        let score = exact(tri, square);
1092        if score < selected.hi
1093            || (search.listed
1094                && score == selected.hi
1095                && self.visit(tri, search.data) < self.visit(selected.triangle, search.data))
1096        {
1097            *selected = Selection {
1098                triangle: tri,
1099                priority,
1100                lo: score,
1101                hi: score,
1102                known: true,
1103                square,
1104            };
1105        }
1106    }
1107    // `getNeighborTriangle`: scan the live adjacency of every meshlet vertex.
1108    // Visits are charged once at the end while the budget covers the visited
1109    // prefix plus the next vertex's list (the per-vertex scans' condition);
1110    // a failing visit charges the visited prefix. Once a list is not covered,
1111    // the remaining visits keep the per-visit exhaustion point.
1112    //
1113    // In bounded mode the meshlet's candidate list (each live adjacent
1114    // triangle once) replaces the per-vertex scan: the same visits are
1115    // charged, and the selection is order-independent because scores are
1116    // finite and exact ties are broken by the upstream visit order.
1117    #[inline(always)]
1118    fn neighbors<const CHECK: bool>(
1119        &self,
1120        active: &mut Active,
1121        data: &[u32],
1122        roots: &mut SqrtCache,
1123        normal: Option<[f32; 3]>,
1124        listed: Option<&mut Candidates>,
1125        emitted: &[u8],
1126        ctx: &mut Context<'_>,
1127    ) -> Result<u32, Error> {
1128        if let Some(listed) = listed.filter(|listed| !CHECK && !listed.overflow) {
1129            let mut total = 0usize;
1130            let mut kept = 0;
1131            for k in 0..active.len {
1132                let v = active.list[k];
1133                let live = self.vertices[v as usize].live as usize;
1134                if live != 0 {
1135                    active.list[kept] = v;
1136                    kept += 1;
1137                    total += live;
1138                }
1139            }
1140            active.len = kept;
1141            if ctx.work.covers(total)? {
1142                let mut search = Search {
1143                    roots,
1144                    normal,
1145                    listed: true,
1146                    data,
1147                };
1148                let mut selected = Selection::new();
1149                let mut i = 0;
1150                while i < listed.len {
1151                    let tri = listed.list[i];
1152                    if emitted[tri as usize] == EMITTED {
1153                        listed.len -= 1;
1154                        listed.list[i] = listed.list[listed.len];
1155                        continue;
1156                    }
1157                    let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
1158                    let states = [self.vertices[a], self.vertices[b], self.vertices[c]];
1159                    self.evaluate::<CHECK>(tri, states, &mut selected, &mut search)?;
1160                    i += 1;
1161                }
1162                ctx.tick(total)?;
1163                return Ok(selected.triangle);
1164            }
1165        }
1166        let mut search = Search {
1167            roots,
1168            normal,
1169            listed: false,
1170            data,
1171        };
1172        let mut selected = Selection::new();
1173        let mut visited = 0usize;
1174        let mut kept = 0;
1175        for k in 0..active.len {
1176            let v = active.list[k];
1177            let state = self.vertices[v as usize];
1178            let live = state.live as usize;
1179            // Lists only shrink: drop exhausted vertices. An empty list is
1180            // always covered, since visited never exceeds the budget.
1181            if live == 0 {
1182                continue;
1183            }
1184            active.list[kept] = v;
1185            kept += 1;
1186            let local = state.local as u16;
1187            if !ctx.work.covers(visited + live)? {
1188                ctx.tick(visited)?;
1189                for &v in &active.list[k..active.len] {
1190                    let state = self.vertices[v as usize];
1191                    let off = state.offset as usize;
1192                    for &tri in &data[off..off + state.live as usize] {
1193                        ctx.tick(1)?;
1194                        self.one::<CHECK>(tri, state.local as u16, &mut selected, &mut search)?;
1195                    }
1196                }
1197                return Ok(selected.triangle);
1198            }
1199            let off = state.offset as usize;
1200            for &tri in &data[off..off + live] {
1201                visited += 1;
1202                if let Err(error) = self.one::<CHECK>(tri, local, &mut selected, &mut search) {
1203                    ctx.tick(visited)?;
1204                    return Err(error);
1205                }
1206            }
1207        }
1208        active.len = kept;
1209        ctx.tick(visited)?;
1210        Ok(selected.triangle)
1211    }
1212}
1213// `emitted` states: free, emitted, or listed as a candidate of the meshlet.
1214const EMITTED: u8 = 1;
1215const LISTED: u8 = 2;
1216// Live triangles adjacent to the current meshlet, each once (bounded mode).
1217// A meshlet whose candidates exceed the fixed capacity uses the scan.
1218struct Candidates {
1219    list: [u32; 1024],
1220    len: usize,
1221    overflow: bool,
1222}
1223impl Candidates {
1224    fn new() -> Self {
1225        Self {
1226            list: [0; 1024],
1227            len: 0,
1228            overflow: false,
1229        }
1230    }
1231    fn clear(&mut self, emitted: &mut [u8]) {
1232        for &t in &self.list[..self.len] {
1233            if emitted[t as usize] == LISTED {
1234                emitted[t as usize] = 0;
1235            }
1236        }
1237        self.len = 0;
1238        self.overflow = false;
1239    }
1240    fn add(&mut self, live: &[u32], emitted: &mut [u8]) {
1241        for &t in live {
1242            if emitted[t as usize] == 0 {
1243                if self.len == self.list.len() {
1244                    self.overflow = true;
1245                    return;
1246                }
1247                emitted[t as usize] = LISTED;
1248                self.list[self.len] = t;
1249                self.len += 1;
1250            }
1251        }
1252    }
1253}
1254// Current-meshlet vertices whose live adjacency may be nonempty, in meshlet
1255// (local index) order. Vertices are appended as the meshlet grows and dropped
1256// once their lists are exhausted; live counts never increase again.
1257struct Active {
1258    list: [u32; 256],
1259    len: usize,
1260    offset: u32,
1261    synced: usize,
1262}
1263impl Active {
1264    fn new() -> Self {
1265        Self {
1266            list: [0; 256],
1267            len: 0,
1268            offset: 0,
1269            synced: 0,
1270        }
1271    }
1272    #[inline(always)]
1273    fn sync(
1274        &mut self,
1275        out: &Output<'_>,
1276        adj: &Adjacency,
1277        listed: Option<(&mut Candidates, &mut [u8])>,
1278    ) {
1279        let count = out.current.vertex_count as usize;
1280        let reset = out.current.vertex_offset != self.offset || count < self.synced;
1281        if reset {
1282            self.offset = out.current.vertex_offset;
1283            self.len = 0;
1284            self.synced = 0;
1285        }
1286        let added = &out.vertices[self.offset as usize..][self.synced..count];
1287        if let Some((candidates, emitted)) = listed {
1288            if reset {
1289                candidates.clear(emitted);
1290            }
1291            for &v in added {
1292                let state = adj.vertices[v as usize];
1293                if !candidates.overflow {
1294                    let off = state.offset as usize;
1295                    candidates.add(&adj.data[off..off + state.live as usize], emitted);
1296                }
1297            }
1298        }
1299        for &v in added {
1300            self.list[self.len] = v;
1301            self.len += 1;
1302        }
1303        self.synced = count;
1304    }
1305}
1306// Dispatch position storage once, outside the triangle loop. This keeps
1307// packed inputs as direct checked slice accesses without per-corner view tests.
1308fn fill_cones<const CHECK: bool>(
1309    triangles: &[[u32; 3]],
1310    cones: &mut [Cone],
1311    read: impl Fn(u32) -> [f32; 3],
1312) -> Result<f32, Error> {
1313    let mut mesh_area = 0.;
1314    for (group, out_cones) in triangles.chunks(LANES).zip(cones.chunks_mut(LANES)) {
1315        let mut normals = [[0f32; 3]; LANES];
1316        let mut squares = [1f32; LANES];
1317        for (k, (t, cone)) in group.iter().zip(out_cones.iter_mut()).enumerate() {
1318            let a = read(t[0]);
1319            let b = read(t[1]);
1320            let c = read(t[2]);
1321            let normal = cross(sub(b, a), sub(c, a));
1322            squares[k] = number::<CHECK>(dot(normal, normal))?;
1323            normals[k] = normal;
1324            for j in 0..3 {
1325                cone.p[j] = number::<CHECK>((a[j] + b[j] + c[j]) / 3.)?;
1326            }
1327        }
1328        let areas = sqrt8(squares);
1329        for (k, cone) in out_cones.iter_mut().enumerate() {
1330            let area = areas[k];
1331            let inv = if area == 0. { 0. } else { 1. / area };
1332            for (n, &v) in cone.n.iter_mut().zip(&normals[k]) {
1333                *n = number::<CHECK>(v * inv)?;
1334            }
1335            mesh_area = number::<CHECK>(mesh_area + area)?;
1336        }
1337    }
1338    Ok(mesh_area)
1339}
1340fn flex<const CHECK: bool, const ZERO_WEIGHT: bool>(
1341    out: &mut Output<'_>,
1342    indices: &[u32],
1343    p: Positions<'_>,
1344    s: MeshletSettings,
1345    min: usize,
1346    weight: f32,
1347    split_factor: f32,
1348    ctx: &mut Context<'_>,
1349) -> Result<(), Error> {
1350    // A separate monomorphization lets the bounded search fold its cone
1351    // factor and score multipliers, rather than testing a runtime zero at
1352    // every candidate. The checked/degenerate path retains its old arithmetic.
1353    let weight = if ZERO_WEIGHT { 0. } else { weight };
1354    if indices.is_empty() {
1355        return Ok(());
1356    }
1357    let n = indices.len() / 3;
1358    let node_count = n.checked_mul(2).ok_or(Error::SizeOverflow)?;
1359    // One exact per-call memo with a fixed table: no per-lookup dispatch.
1360    let mut roots = SqrtCache::new();
1361    let mut adj = adjacency(indices, p.len(), ctx)?;
1362    let mut emitted = ctx.alloc::<u8>(n)?;
1363    let mut cones = ctx.alloc::<Cone>(n)?;
1364    ctx.tick(n)?;
1365    let triangles = indices.as_chunks::<3>().0;
1366    let mesh_area = if let Some(values) = p.packed_values() {
1367        fill_cones::<CHECK>(triangles, &mut cones, |i| values[i as usize])?
1368    } else {
1369        fill_cones::<CHECK>(triangles, &mut cones, |i| point(p, i))?
1370    };
1371    let radius = roots.sqrt(number::<CHECK>(
1372        mesh_area / n as f32 * 0.5 * s.max_triangles as f32,
1373    )?) * 0.5;
1374    let mut order = ctx.alloc(n)?;
1375    for (i, v) in order.iter_mut().enumerate() {
1376        *v = i as u32;
1377    }
1378    let mut nodes = ctx.alloc(node_count)?;
1379    kd_build(&mut nodes, 0, &mut order, &cones, 0, None, ctx)?;
1380    ctx.tick(n.checked_mul(2).ok_or(Error::SizeOverflow)?)?;
1381    let mut corner = [f32::MAX; 3];
1382    for c in &cones {
1383        for (k, v) in corner.iter_mut().enumerate() {
1384            if *v > c.p[k] {
1385                *v = c.p[k];
1386            }
1387        }
1388    }
1389    let mut initial = u32::MAX;
1390    let mut score = f32::MAX;
1391    for (i, c) in cones.iter().enumerate() {
1392        if !CHECK && PRUNE && initial != u32::MAX && {
1393            let d = sub(c.p, corner);
1394            lower_distance(d) >= score || root_at_least(dot(d, d), score)
1395        } {
1396            continue;
1397        }
1398        let d = distance::<CHECK>(c.p, corner, &mut roots)?;
1399        if initial == u32::MAX || d < score {
1400            initial = i as u32;
1401            score = d;
1402        }
1403    }
1404    let mut seeds = [0u32; 256];
1405    let mut seed_count = 0;
1406    let mut acc = Cone::default();
1407    let mut active = Active::new();
1408    // 1 / radius rounds by at most 2^-24; scaling by 1 -+ 2^-21 (rounding by
1409    // another 2^-24) moves each bound strictly past the real reciprocal.
1410    let inverse = 1. / radius;
1411    let inverse_low = inverse * 0.999_999_5;
1412    let inverse_high = inverse * 1.000_000_5;
1413    let bounded = !CHECK
1414        && radius.is_normal()
1415        && radius > 0.
1416        && inverse_low.is_normal()
1417        && inverse_high.is_finite();
1418    // Bounded mode lists candidates on meshes large enough to repay the list
1419    // upkeep.
1420    // (Not constructed otherwise: the list is 4 KiB of stack to clear.)
1421    let mut candidates = (bounded && n >= 256).then(Candidates::new);
1422    loop {
1423        ctx.tick(1)?;
1424        let mc_position = cone_position(acc, out.current.triangle_count);
1425        let mut best;
1426        if out.count == 0 && out.current.triangle_count == 0 {
1427            best = initial;
1428        } else {
1429            // In bounded mode the meshlet normal is only bounded here (its root
1430            // is taken on demand); otherwise it is exact, as upstream. The
1431            // initial seed does not search neighbors and needs no normal.
1432            let normal = if bounded && weight == 0. {
1433                MeshletNormal {
1434                    exact: Some([0.; 3]),
1435                    low: [0.; 3],
1436                    high: [0.; 3],
1437                }
1438            } else if bounded {
1439                MeshletNormal::bounds(acc.n, &mut roots)
1440            } else {
1441                MeshletNormal::exact(acc.n, &mut roots)
1442            };
1443            let input = CandidateInput {
1444                triangles: indices.as_chunks::<3>().0,
1445                vertices: &adj.vertices,
1446                cones: &cones,
1447                meshlet: Cone {
1448                    p: mc_position,
1449                    n: normal.exact.unwrap_or_default(),
1450                },
1451                weight,
1452                radius,
1453                inverse_low,
1454                inverse_high,
1455                bounded,
1456                accumulated: acc.n,
1457                normal_low: normal.low,
1458                normal_high: normal.high,
1459            };
1460            active.sync(
1461                out,
1462                &adj,
1463                candidates
1464                    .as_mut()
1465                    .map(|candidates| (candidates, emitted.as_mut_slice())),
1466            );
1467            best = input.neighbors::<CHECK>(
1468                &mut active,
1469                &adj.data,
1470                &mut roots,
1471                normal.exact,
1472                candidates.as_mut(),
1473                &emitted,
1474                ctx,
1475            )?;
1476        }
1477        let mut split = false;
1478        if best == u32::MAX {
1479            let mut d = f32::MAX;
1480            nearest::<CHECK>(
1481                &mut nodes,
1482                0,
1483                &cones,
1484                &emitted,
1485                mc_position,
1486                &mut best,
1487                &mut d,
1488                &mut roots,
1489                ctx,
1490            )?;
1491            split = out.current.triangle_count as usize >= min
1492                && split_factor > 0.
1493                && d > radius * split_factor;
1494        }
1495        if best == u32::MAX {
1496            break;
1497        }
1498        let extra = indices[best as usize * 3..][..3]
1499            .iter()
1500            .filter(|&&v| adj.vertices[v as usize].local < 0)
1501            .count();
1502        if split
1503            || out.current.vertex_count as usize + extra > s.max_vertices
1504            || out.current.triangle_count as usize >= s.max_triangles
1505        {
1506            let mut keep = 0;
1507            for i in 0..seed_count {
1508                if emitted[seeds[i] as usize] != EMITTED {
1509                    seeds[keep] = seeds[i];
1510                    keep += 1;
1511                }
1512            }
1513            seed_count = keep.min(252);
1514            let mut candidates = [u32::MAX; 4];
1515            let mut lives = [u32::MAX; 4];
1516            let mut scores = [f32::MAX; 4];
1517            for &v in &out.vertices[out.current.vertex_offset as usize..]
1518                [..out.current.vertex_count as usize]
1519            {
1520                let off = adj.vertices[v as usize].offset as usize;
1521                let mut neighbor = u32::MAX;
1522                let mut live = u32::MAX;
1523                ctx.scan(
1524                    adj.data[off..off + adj.vertices[v as usize].live as usize]
1525                        .iter()
1526                        .copied(),
1527                    |_ctx, tri| {
1528                        let t = &indices[tri as usize * 3..][..3];
1529                        let l = adj.vertices[t[0] as usize].live
1530                            + adj.vertices[t[1] as usize].live
1531                            + adj.vertices[t[2] as usize].live;
1532                        if l < live {
1533                            neighbor = tri;
1534                            live = l;
1535                        }
1536                        Ok(())
1537                    },
1538                )?;
1539                if neighbor == u32::MAX {
1540                    continue;
1541                }
1542                let d = distance::<CHECK>(cones[neighbor as usize].p, corner, &mut roots)?;
1543                for j in 0..4 {
1544                    if live < lives[j] || (live == lives[j] && d <= scores[j]) {
1545                        candidates[j] = neighbor;
1546                        lives[j] = live;
1547                        scores[j] = d;
1548                        break;
1549                    }
1550                }
1551            }
1552            for tri in candidates {
1553                if tri != u32::MAX {
1554                    seeds[seed_count] = tri;
1555                    seed_count += 1;
1556                }
1557            }
1558            let mut seed = u32::MAX;
1559            let mut live = u32::MAX;
1560            let mut score = f32::MAX;
1561            ctx.scan(seeds[..seed_count].iter().copied(), |_ctx, tri| {
1562                let t = &indices[tri as usize * 3..][..3];
1563                let l = adj.vertices[t[0] as usize].live
1564                    + adj.vertices[t[1] as usize].live
1565                    + adj.vertices[t[2] as usize].live;
1566                if !CHECK
1567                    && (l > live
1568                        || (PRUNE && l == live && {
1569                            let d = sub(cones[tri as usize].p, corner);
1570                            lower_distance(d) >= score || root_at_least(dot(d, d), score)
1571                        }))
1572                {
1573                    return Ok(());
1574                }
1575                let d = distance::<CHECK>(cones[tri as usize].p, corner, &mut roots)?;
1576                if l < live || (l == live && d < score) {
1577                    seed = tri;
1578                    live = l;
1579                    score = d;
1580                }
1581                Ok(())
1582            })?;
1583            if seed != u32::MAX {
1584                best = seed;
1585            }
1586        }
1587        let t = &indices.as_chunks::<3>().0[best as usize];
1588        if out.append(t, &mut adj.vertices, s, split, ctx)? {
1589            acc = Cone::default();
1590        }
1591        for &v in t {
1592            let state = &mut adj.vertices[v as usize];
1593            let list = &mut adj.data[state.offset as usize..][..state.live as usize];
1594            // Charge the visited prefix of the search (the whole list when
1595            // absent); a short budget keeps the per-visit exhaustion point.
1596            let found = if ctx.work.covers(list.len())? {
1597                let found = list.iter().position(|&tri| tri == best);
1598                ctx.tick(found.map_or(list.len(), |i| i + 1))?;
1599                found
1600            } else {
1601                let mut found = None;
1602                for (i, &tri) in list.iter().enumerate() {
1603                    ctx.tick(1)?;
1604                    if tri == best {
1605                        found = Some(i);
1606                        break;
1607                    }
1608                }
1609                found
1610            };
1611            if let Some(i) = found {
1612                list[i] = list[list.len() - 1];
1613                state.live -= 1;
1614            }
1615        }
1616        for k in 0..3 {
1617            acc.p[k] = number::<CHECK>(acc.p[k] + cones[best as usize].p[k])?;
1618            acc.n[k] = number::<CHECK>(acc.n[k] + cones[best as usize].n[k])?;
1619        }
1620        emitted[best as usize] = EMITTED;
1621    }
1622    Ok(())
1623}
1624// The scan's output triangles are sequential and unpadded. A zipped output
1625// iterator proves all three destination slots once, and the descriptor stays
1626// local for the entire covered-budget loop instead of being published per face.
1627fn scan_covered(
1628    out: &mut Output<'_>,
1629    triangles: &[[u32; 3]],
1630    used: &mut [i16],
1631    s: MeshletSettings,
1632) -> usize {
1633    let mut m = out.current;
1634    let mut count = out.count;
1635    let mut visits = triangles.len();
1636    for (t, triangle) in triangles
1637        .iter()
1638        .zip(out.triangles[..triangles.len() * 3].as_chunks_mut::<3>().0)
1639    {
1640        let mut local = t.map(|v| used[v as usize]);
1641        let extra = local.iter().filter(|&&v| v < 0).count();
1642        if m.vertex_count as usize + extra > s.max_vertices
1643            || m.triangle_count as usize >= s.max_triangles
1644        {
1645            out.descriptors[count] = m;
1646            count += 1;
1647            visits += m.vertex_count as usize;
1648            for &v in &out.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
1649                used[v as usize] = -1;
1650            }
1651            m.vertex_offset += m.vertex_count;
1652            m.triangle_offset += m.triangle_count * 3;
1653            m.vertex_count = 0;
1654            m.triangle_count = 0;
1655            local = [-1; 3];
1656        }
1657        for k in 0..3 {
1658            if local[k] < 0 {
1659                if k > 0 && t[k] == t[0] {
1660                    local[k] = local[0];
1661                } else if k == 2 && t[k] == t[1] {
1662                    local[k] = local[1];
1663                } else {
1664                    local[k] = m.vertex_count as i16;
1665                    used[t[k] as usize] = local[k];
1666                    out.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
1667                    m.vertex_count += 1;
1668                }
1669            }
1670            triangle[k] = local[k] as u8;
1671        }
1672        m.triangle_count += 1;
1673    }
1674    out.current = m;
1675    out.count = count;
1676    visits
1677}
1678fn scan(
1679    out: &mut Output<'_>,
1680    indices: &[u32],
1681    n: usize,
1682    s: MeshletSettings,
1683    ctx: &mut Context<'_>,
1684) -> Result<(), Error> {
1685    let mut used = ctx.alloc::<i16>(n)?;
1686    used.fill(-1);
1687    let triangles = indices.as_chunks::<3>().0;
1688    // Each triangle costs one visit, and every flushed vertex was inserted by
1689    // a preceding corner. A covered upper bound lets the hot loop keep its
1690    // exact charge locally; short budgets retain every original failure point.
1691    if indices
1692        .len()
1693        .checked_add(triangles.len())
1694        .is_some_and(|bound| ctx.work.covers(bound).unwrap_or(false))
1695    {
1696        let visits = scan_covered(out, triangles, &mut used, s);
1697        ctx.tick(visits)?;
1698    } else {
1699        for t in triangles {
1700            out.append(t, &mut used, s, false, ctx)?;
1701        }
1702    }
1703    Ok(())
1704}
1705#[derive(Clone, Copy)]
1706pub(crate) enum Builder {
1707    Scan,
1708    Flex {
1709        min: usize,
1710        weight: f32,
1711        split: f32,
1712    },
1713    /// `parallel` selects the Rayon front end; it needs the `parallel` feature.
1714    Spatial {
1715        min: usize,
1716        fill: f32,
1717        parallel: bool,
1718    },
1719}
1720fn min_triangles(b: Builder, s: MeshletSettings) -> usize {
1721    match b {
1722        Builder::Scan => s.max_triangles,
1723        Builder::Flex { min, .. } | Builder::Spatial { min, .. } => min,
1724    }
1725}
1726fn execute(
1727    out: &mut Output<'_>,
1728    indices: &[u32],
1729    n: usize,
1730    p: Option<Positions<'_>>,
1731    s: MeshletSettings,
1732    b: Builder,
1733    ctx: &mut Context<'_>,
1734) -> Result<MeshletSizes, Error> {
1735    match b {
1736        Builder::Scan => scan(out, indices, n, s, ctx)?,
1737        Builder::Flex { min, weight, split } => {
1738            let p = p.expect("positions builder");
1739            if ctx.moderate {
1740                if weight == 0. {
1741                    flex::<false, true>(out, indices, p, s, min, weight, split, ctx)?;
1742                } else {
1743                    flex::<false, false>(out, indices, p, s, min, weight, split, ctx)?;
1744                }
1745            } else {
1746                flex::<true, false>(out, indices, p, s, min, weight, split, ctx)?;
1747            }
1748        }
1749        Builder::Spatial {
1750            min,
1751            fill,
1752            parallel,
1753        } => crate::meshlet_spatial::spatial(
1754            out,
1755            indices,
1756            p.expect("positions builder"),
1757            s,
1758            min,
1759            fill,
1760            parallel,
1761            ctx,
1762        )?,
1763    }
1764    Ok(out.finish())
1765}
1766fn check(s: MeshletSettings, b: Builder) -> Result<(), Error> {
1767    match b {
1768        Builder::Scan => validate(s, s.max_triangles, 0., 0.),
1769        Builder::Flex { min, weight, split } => validate(s, min, weight, split),
1770        Builder::Spatial { min, fill, .. } => {
1771            validate(s, min, 0., 0.)?;
1772            if !fill.is_finite() || fill < 0. {
1773                return Err(Error::InvalidParameter);
1774            }
1775            Ok(())
1776        }
1777    }
1778}
1779fn build(
1780    indices: &[u32],
1781    n: usize,
1782    p: Option<Positions<'_>>,
1783    s: MeshletSettings,
1784    b: Builder,
1785    workspace: &mut Workspace,
1786    trusted_moderate: Option<bool>,
1787) -> Result<MeshletsGeneric, Error> {
1788    let mut ctx = Context::new(workspace)?;
1789    check(s, b)?;
1790    ctx.topology(indices, n)?;
1791    if let Some(p) = p {
1792        if let Some(moderate) = trusted_moderate {
1793            ctx.moderate = moderate;
1794        } else {
1795            ctx.positions(p)?;
1796        }
1797    }
1798    let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1799    let mut result = MeshletsGeneric {
1800        meshlets: ctx.alloc(bound)?,
1801        vertices: ctx.alloc(indices.len())?,
1802        triangles: ctx.alloc(indices.len())?,
1803    };
1804    let sizes = execute(
1805        &mut Output {
1806            descriptors: &mut result.meshlets,
1807            vertices: &mut result.vertices,
1808            triangles: &mut result.triangles,
1809            current: Meshlet::default(),
1810            count: 0,
1811        },
1812        indices,
1813        n,
1814        p,
1815        s,
1816        b,
1817        &mut ctx,
1818    )?;
1819    result.meshlets.truncate(sizes.meshlets);
1820    result.vertices.truncate(sizes.vertices);
1821    result.triangles.truncate(sizes.triangles);
1822    Ok(result)
1823}
1824fn build_into(
1825    descriptors: &mut [Meshlet],
1826    vertices: &mut [u32],
1827    triangles: &mut [u8],
1828    indices: &[u32],
1829    n: usize,
1830    p: Option<Positions<'_>>,
1831    s: MeshletSettings,
1832    b: Builder,
1833    workspace: &mut Workspace,
1834) -> Result<MeshletSizes, Error> {
1835    let mut ctx = Context::new(workspace)?;
1836    check(s, b)?;
1837    let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1838    if descriptors.len() < bound
1839        || vertices.len() < indices.len()
1840        || triangles.len() < indices.len()
1841    {
1842        return Err(Error::BufferTooSmall);
1843    }
1844    ctx.topology(indices, n)?;
1845    if let Some(p) = p {
1846        ctx.positions(p)?;
1847    }
1848    execute(
1849        &mut Output {
1850            descriptors,
1851            vertices,
1852            triangles,
1853            current: Meshlet::default(),
1854            count: 0,
1855        },
1856        indices,
1857        n,
1858        p,
1859        s,
1860        b,
1861        &mut ctx,
1862    )
1863}
1864/// `meshopt_buildMeshletsScan`: consume triangles in input order.
1865///
1866/// # Errors
1867/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1868/// `InvalidParameter` for unsupported meshlet limits; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1869#[inline]
1870pub fn build_meshlets_scan_generic<I: crate::Index>(
1871    indices: &[I],
1872    vertex_count: usize,
1873    s: MeshletSettings,
1874    workspace: &mut Workspace,
1875) -> Result<MeshletsGeneric<I>, Error> {
1876    I::with_input(indices, workspace, |indices, workspace| {
1877        build_meshlets_scan_u32(indices, vertex_count, s, workspace)
1878            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1879    })
1880}
1881
1882fn build_meshlets_scan_u32(
1883    indices: &[u32],
1884    vertex_count: usize,
1885    s: MeshletSettings,
1886    workspace: &mut Workspace,
1887) -> Result<MeshletsGeneric, Error> {
1888    build(
1889        indices,
1890        vertex_count,
1891        None,
1892        s,
1893        Builder::Scan,
1894        workspace,
1895        None,
1896    )
1897}
1898/// `meshopt_buildMeshlets`: connectivity and cone-aware meshlets.
1899///
1900/// # Errors
1901/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1902/// `InvalidParameter` for unsupported builder settings; `NumericalFailure` for non-finite geometry or calculations.
1903/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1904#[inline]
1905pub fn build_meshlets_generic<I: crate::Index>(
1906    indices: &[I],
1907    p: Positions<'_>,
1908    s: MeshletSettings,
1909    cone_weight: f32,
1910    workspace: &mut Workspace,
1911) -> Result<MeshletsGeneric<I>, Error> {
1912    I::with_input(indices, workspace, |indices, workspace| {
1913        build_meshlets_u32(indices, p, s, cone_weight, workspace)
1914            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1915    })
1916}
1917
1918fn build_meshlets_u32(
1919    indices: &[u32],
1920    p: Positions<'_>,
1921    s: MeshletSettings,
1922    cone_weight: f32,
1923    workspace: &mut Workspace,
1924) -> Result<MeshletsGeneric, Error> {
1925    build_meshlets_flex_generic(indices, p, s, s.max_triangles, cone_weight, 0., workspace)
1926}
1927/// `meshopt_buildMeshletsFlex`: variable triangle counts and optional spatial splits.
1928///
1929/// # Errors
1930/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1931/// `InvalidParameter` for unsupported builder settings; `NumericalFailure` for non-finite geometry or calculations.
1932/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1933#[inline]
1934pub fn build_meshlets_flex_generic<I: crate::Index>(
1935    indices: &[I],
1936    p: Positions<'_>,
1937    s: MeshletSettings,
1938    min_triangles: usize,
1939    cone_weight: f32,
1940    split_factor: f32,
1941    workspace: &mut Workspace,
1942) -> Result<MeshletsGeneric<I>, Error> {
1943    I::with_input(indices, workspace, |indices, workspace| {
1944        build_meshlets_flex_u32(
1945            indices,
1946            p,
1947            s,
1948            min_triangles,
1949            cone_weight,
1950            split_factor,
1951            workspace,
1952        )
1953        .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
1954    })
1955}
1956
1957fn build_meshlets_flex_u32(
1958    indices: &[u32],
1959    p: Positions<'_>,
1960    s: MeshletSettings,
1961    min_triangles: usize,
1962    cone_weight: f32,
1963    split_factor: f32,
1964    workspace: &mut Workspace,
1965) -> Result<MeshletsGeneric, Error> {
1966    build(
1967        indices,
1968        p.len(),
1969        Some(p),
1970        s,
1971        Builder::Flex {
1972            min: min_triangles,
1973            weight: cone_weight,
1974            split: split_factor,
1975        },
1976        workspace,
1977        None,
1978    )
1979}
1980#[cfg(feature = "clusterlod")]
1981pub(crate) fn build_meshlets_flex_validated(
1982    indices: &[u32],
1983    p: Positions<'_>,
1984    s: MeshletSettings,
1985    min_triangles: usize,
1986    cone_weight: f32,
1987    split_factor: f32,
1988    moderate: bool,
1989    workspace: &mut Workspace,
1990) -> Result<MeshletsGeneric, Error> {
1991    build(
1992        indices,
1993        p.len(),
1994        Some(p),
1995        s,
1996        Builder::Flex {
1997            min: min_triangles,
1998            weight: cone_weight,
1999            split: split_factor,
2000        },
2001        workspace,
2002        Some(moderate),
2003    )
2004}
2005/// `meshopt_buildMeshletsSpatial`: surface-area heuristic meshlets for ray tracing.
2006///
2007/// # Errors
2008/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
2009/// `InvalidParameter` for unsupported builder settings; `NumericalFailure` for non-finite geometry or calculations.
2010/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
2011#[inline]
2012pub fn build_meshlets_spatial_generic<I: crate::Index>(
2013    indices: &[I],
2014    p: Positions<'_>,
2015    s: MeshletSettings,
2016    min_triangles: usize,
2017    fill_weight: f32,
2018    workspace: &mut Workspace,
2019) -> Result<MeshletsGeneric<I>, Error> {
2020    I::with_input(indices, workspace, |indices, workspace| {
2021        build_meshlets_spatial_u32(indices, p, s, min_triangles, fill_weight, workspace)
2022            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
2023    })
2024}
2025
2026fn build_meshlets_spatial_u32(
2027    indices: &[u32],
2028    p: Positions<'_>,
2029    s: MeshletSettings,
2030    min_triangles: usize,
2031    fill_weight: f32,
2032    workspace: &mut Workspace,
2033) -> Result<MeshletsGeneric, Error> {
2034    build(
2035        indices,
2036        p.len(),
2037        Some(p),
2038        s,
2039        Builder::Spatial {
2040            min: min_triangles,
2041            fill: fill_weight,
2042            parallel: false,
2043        },
2044        workspace,
2045        None,
2046    )
2047}
2048/// `build_meshlets_spatial_generic` on the current Rayon pool, with the same
2049/// result. Only a workspace with unlimited bytes and work uses the parallel
2050/// front end (scratch per worker is not accounted), as in cluster LOD; any
2051/// other workspace, or a one-worker pool, builds serially.
2052#[cfg(feature = "parallel")]
2053pub(crate) fn build_meshlets_spatial_parallel_generic<I: crate::Index>(
2054    indices: &[I],
2055    p: Positions<'_>,
2056    s: MeshletSettings,
2057    min_triangles: usize,
2058    fill_weight: f32,
2059    workspace: &mut Workspace,
2060) -> Result<MeshletsGeneric<I>, Error> {
2061    let limits = workspace.limits();
2062    let parallel = limits.max_bytes == usize::MAX
2063        && limits.max_work == u64::MAX
2064        && rayon::current_num_threads() > 1;
2065    I::with_input(indices, workspace, |indices, workspace| {
2066        build(
2067            indices,
2068            p.len(),
2069            Some(p),
2070            s,
2071            Builder::Spatial {
2072                min: min_triangles,
2073                fill: fill_weight,
2074                parallel,
2075            },
2076            workspace,
2077            None,
2078        )
2079        .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
2080    })
2081}
2082#[cfg(feature = "clusterlod")]
2083pub(crate) fn build_meshlets_spatial_validated(
2084    indices: &[u32],
2085    p: Positions<'_>,
2086    s: MeshletSettings,
2087    min_triangles: usize,
2088    fill_weight: f32,
2089    moderate: bool,
2090    workspace: &mut Workspace,
2091) -> Result<MeshletsGeneric, Error> {
2092    build(
2093        indices,
2094        p.len(),
2095        Some(p),
2096        s,
2097        Builder::Spatial {
2098            min: min_triangles,
2099            fill: fill_weight,
2100            parallel: false,
2101        },
2102        workspace,
2103        Some(moderate),
2104    )
2105}
2106/// Caller-buffer scan builder; a late work-limit failure may modify output prefixes.
2107///
2108/// # Errors
2109/// Same errors as [`build_meshlets_scan`]. `BufferTooSmall` if any output buffer lacks capacity.
2110#[inline]
2111pub fn build_meshlets_scan_into_generic<I: crate::Index>(
2112    descriptors: &mut [Meshlet],
2113    vertices: &mut [I],
2114    triangles: &mut [u8],
2115    indices: &[I],
2116    vertex_count: usize,
2117    s: MeshletSettings,
2118    workspace: &mut Workspace,
2119) -> Result<MeshletSizes, Error> {
2120    I::with_input(indices, workspace, |indices, workspace| {
2121        I::with_mut(vertices, workspace, |vertices, workspace| {
2122            build_meshlets_scan_into_u32(
2123                descriptors,
2124                vertices,
2125                triangles,
2126                indices,
2127                vertex_count,
2128                s,
2129                workspace,
2130            )
2131        })
2132    })
2133}
2134
2135fn build_meshlets_scan_into_u32(
2136    descriptors: &mut [Meshlet],
2137    vertices: &mut [u32],
2138    triangles: &mut [u8],
2139    indices: &[u32],
2140    vertex_count: usize,
2141    s: MeshletSettings,
2142    workspace: &mut Workspace,
2143) -> Result<MeshletSizes, Error> {
2144    build_into(
2145        descriptors,
2146        vertices,
2147        triangles,
2148        indices,
2149        vertex_count,
2150        None,
2151        s,
2152        Builder::Scan,
2153        workspace,
2154    )
2155}
2156/// Caller-buffer standard builder; a late failure may modify output prefixes.
2157///
2158/// # Errors
2159/// Same errors as [`build_meshlets`]. `BufferTooSmall` if any output buffer lacks capacity.
2160#[inline]
2161pub fn build_meshlets_into_generic<I: crate::Index>(
2162    descriptors: &mut [Meshlet],
2163    vertices: &mut [I],
2164    triangles: &mut [u8],
2165    indices: &[I],
2166    p: Positions<'_>,
2167    s: MeshletSettings,
2168    cone_weight: f32,
2169    workspace: &mut Workspace,
2170) -> Result<MeshletSizes, Error> {
2171    I::with_input(indices, workspace, |indices, workspace| {
2172        I::with_mut(vertices, workspace, |vertices, workspace| {
2173            build_meshlets_into_u32(
2174                descriptors,
2175                vertices,
2176                triangles,
2177                indices,
2178                p,
2179                s,
2180                cone_weight,
2181                workspace,
2182            )
2183        })
2184    })
2185}
2186
2187#[allow(clippy::too_many_arguments)]
2188fn build_meshlets_into_u32(
2189    descriptors: &mut [Meshlet],
2190    vertices: &mut [u32],
2191    triangles: &mut [u8],
2192    indices: &[u32],
2193    p: Positions<'_>,
2194    s: MeshletSettings,
2195    cone_weight: f32,
2196    workspace: &mut Workspace,
2197) -> Result<MeshletSizes, Error> {
2198    build_meshlets_flex_into_generic(
2199        descriptors,
2200        vertices,
2201        triangles,
2202        indices,
2203        p,
2204        s,
2205        s.max_triangles,
2206        cone_weight,
2207        0.,
2208        workspace,
2209    )
2210}
2211/// Caller-buffer flexible builder; a late failure may modify output prefixes.
2212///
2213/// # Errors
2214/// Same errors as [`build_meshlets_flex`]. `BufferTooSmall` if any output buffer lacks capacity.
2215#[inline]
2216pub fn build_meshlets_flex_into_generic<I: crate::Index>(
2217    descriptors: &mut [Meshlet],
2218    vertices: &mut [I],
2219    triangles: &mut [u8],
2220    indices: &[I],
2221    p: Positions<'_>,
2222    s: MeshletSettings,
2223    min_triangles: usize,
2224    cone_weight: f32,
2225    split_factor: f32,
2226    workspace: &mut Workspace,
2227) -> Result<MeshletSizes, Error> {
2228    I::with_input(indices, workspace, |indices, workspace| {
2229        I::with_mut(vertices, workspace, |vertices, workspace| {
2230            build_meshlets_flex_into_u32(
2231                descriptors,
2232                vertices,
2233                triangles,
2234                indices,
2235                p,
2236                s,
2237                min_triangles,
2238                cone_weight,
2239                split_factor,
2240                workspace,
2241            )
2242        })
2243    })
2244}
2245
2246#[allow(clippy::too_many_arguments)]
2247fn build_meshlets_flex_into_u32(
2248    descriptors: &mut [Meshlet],
2249    vertices: &mut [u32],
2250    triangles: &mut [u8],
2251    indices: &[u32],
2252    p: Positions<'_>,
2253    s: MeshletSettings,
2254    min_triangles: usize,
2255    cone_weight: f32,
2256    split_factor: f32,
2257    workspace: &mut Workspace,
2258) -> Result<MeshletSizes, Error> {
2259    build_into(
2260        descriptors,
2261        vertices,
2262        triangles,
2263        indices,
2264        p.len(),
2265        Some(p),
2266        s,
2267        Builder::Flex {
2268            min: min_triangles,
2269            weight: cone_weight,
2270            split: split_factor,
2271        },
2272        workspace,
2273    )
2274}
2275/// Caller-buffer spatial builder; a late failure may modify output prefixes.
2276///
2277/// # Errors
2278/// Same errors as [`build_meshlets_spatial`]. `BufferTooSmall` if any output buffer lacks capacity.
2279#[inline]
2280pub fn build_meshlets_spatial_into_generic<I: crate::Index>(
2281    descriptors: &mut [Meshlet],
2282    vertices: &mut [I],
2283    triangles: &mut [u8],
2284    indices: &[I],
2285    p: Positions<'_>,
2286    s: MeshletSettings,
2287    min_triangles: usize,
2288    fill_weight: f32,
2289    workspace: &mut Workspace,
2290) -> Result<MeshletSizes, Error> {
2291    I::with_input(indices, workspace, |indices, workspace| {
2292        I::with_mut(vertices, workspace, |vertices, workspace| {
2293            build_meshlets_spatial_into_u32(
2294                descriptors,
2295                vertices,
2296                triangles,
2297                indices,
2298                p,
2299                s,
2300                min_triangles,
2301                fill_weight,
2302                workspace,
2303            )
2304        })
2305    })
2306}
2307
2308#[allow(clippy::too_many_arguments)]
2309fn build_meshlets_spatial_into_u32(
2310    descriptors: &mut [Meshlet],
2311    vertices: &mut [u32],
2312    triangles: &mut [u8],
2313    indices: &[u32],
2314    p: Positions<'_>,
2315    s: MeshletSettings,
2316    min_triangles: usize,
2317    fill_weight: f32,
2318    workspace: &mut Workspace,
2319) -> Result<MeshletSizes, Error> {
2320    build_into(
2321        descriptors,
2322        vertices,
2323        triangles,
2324        indices,
2325        p.len(),
2326        Some(p),
2327        s,
2328        Builder::Spatial {
2329            min: min_triangles,
2330            fill: fill_weight,
2331            parallel: false,
2332        },
2333        workspace,
2334    )
2335}
2336
2337/// The source-compatible u32 entry point; see [`build_meshlets_scan_generic`] for selectable index widths.
2338#[inline]
2339pub fn build_meshlets_scan(
2340    indices: &[u32],
2341    vertex_count: usize,
2342    s: MeshletSettings,
2343    workspace: &mut Workspace,
2344) -> Result<Meshlets, Error> {
2345    build_meshlets_scan_generic::<u32>(indices, vertex_count, s, workspace).map(Into::into)
2346}
2347
2348/// The source-compatible u32 entry point; see [`build_meshlets_generic`] for selectable index widths.
2349#[inline]
2350pub fn build_meshlets(
2351    indices: &[u32],
2352    p: Positions<'_>,
2353    s: MeshletSettings,
2354    cone_weight: f32,
2355    workspace: &mut Workspace,
2356) -> Result<Meshlets, Error> {
2357    build_meshlets_generic::<u32>(indices, p, s, cone_weight, workspace).map(Into::into)
2358}
2359
2360/// The source-compatible u32 entry point; see [`build_meshlets_flex_generic`] for selectable index widths.
2361#[inline]
2362pub fn build_meshlets_flex(
2363    indices: &[u32],
2364    p: Positions<'_>,
2365    s: MeshletSettings,
2366    min_triangles: usize,
2367    cone_weight: f32,
2368    split_factor: f32,
2369    workspace: &mut Workspace,
2370) -> Result<Meshlets, Error> {
2371    build_meshlets_flex_generic::<u32>(
2372        indices,
2373        p,
2374        s,
2375        min_triangles,
2376        cone_weight,
2377        split_factor,
2378        workspace,
2379    )
2380    .map(Into::into)
2381}
2382
2383/// The source-compatible u32 entry point; see [`build_meshlets_spatial_generic`] for selectable index widths.
2384#[inline]
2385pub fn build_meshlets_spatial(
2386    indices: &[u32],
2387    p: Positions<'_>,
2388    s: MeshletSettings,
2389    min_triangles: usize,
2390    fill_weight: f32,
2391    workspace: &mut Workspace,
2392) -> Result<Meshlets, Error> {
2393    build_meshlets_spatial_generic::<u32>(indices, p, s, min_triangles, fill_weight, workspace)
2394        .map(Into::into)
2395}
2396
2397/// The source-compatible u32 entry point; see [`build_meshlets_scan_into_generic`] for selectable index widths.
2398#[inline]
2399pub fn build_meshlets_scan_into(
2400    descriptors: &mut [Meshlet],
2401    vertices: &mut [u32],
2402    triangles: &mut [u8],
2403    indices: &[u32],
2404    vertex_count: usize,
2405    s: MeshletSettings,
2406    workspace: &mut Workspace,
2407) -> Result<MeshletSizes, Error> {
2408    build_meshlets_scan_into_generic::<u32>(
2409        descriptors,
2410        vertices,
2411        triangles,
2412        indices,
2413        vertex_count,
2414        s,
2415        workspace,
2416    )
2417}
2418
2419/// The source-compatible u32 entry point; see [`build_meshlets_into_generic`] for selectable index widths.
2420#[inline]
2421pub fn build_meshlets_into(
2422    descriptors: &mut [Meshlet],
2423    vertices: &mut [u32],
2424    triangles: &mut [u8],
2425    indices: &[u32],
2426    p: Positions<'_>,
2427    s: MeshletSettings,
2428    cone_weight: f32,
2429    workspace: &mut Workspace,
2430) -> Result<MeshletSizes, Error> {
2431    build_meshlets_into_generic::<u32>(
2432        descriptors,
2433        vertices,
2434        triangles,
2435        indices,
2436        p,
2437        s,
2438        cone_weight,
2439        workspace,
2440    )
2441}
2442
2443/// The source-compatible u32 entry point; see [`build_meshlets_flex_into_generic`] for selectable index widths.
2444#[inline]
2445pub fn build_meshlets_flex_into(
2446    descriptors: &mut [Meshlet],
2447    vertices: &mut [u32],
2448    triangles: &mut [u8],
2449    indices: &[u32],
2450    p: Positions<'_>,
2451    s: MeshletSettings,
2452    min_triangles: usize,
2453    cone_weight: f32,
2454    split_factor: f32,
2455    workspace: &mut Workspace,
2456) -> Result<MeshletSizes, Error> {
2457    build_meshlets_flex_into_generic::<u32>(
2458        descriptors,
2459        vertices,
2460        triangles,
2461        indices,
2462        p,
2463        s,
2464        min_triangles,
2465        cone_weight,
2466        split_factor,
2467        workspace,
2468    )
2469}
2470
2471/// The source-compatible u32 entry point; see [`build_meshlets_spatial_into_generic`] for selectable index widths.
2472#[inline]
2473pub fn build_meshlets_spatial_into(
2474    descriptors: &mut [Meshlet],
2475    vertices: &mut [u32],
2476    triangles: &mut [u8],
2477    indices: &[u32],
2478    p: Positions<'_>,
2479    s: MeshletSettings,
2480    min_triangles: usize,
2481    fill_weight: f32,
2482    workspace: &mut Workspace,
2483) -> Result<MeshletSizes, Error> {
2484    build_meshlets_spatial_into_generic::<u32>(
2485        descriptors,
2486        vertices,
2487        triangles,
2488        indices,
2489        p,
2490        s,
2491        min_triangles,
2492        fill_weight,
2493        workspace,
2494    )
2495}
2496
2497/// The source-compatible u32 form of [`MeshletsGeneric`].
2498/// Complete tightly packed meshlet output.
2499#[derive(Debug, Default, PartialEq, Eq)]
2500pub struct Meshlets {
2501    /// Meshlet descriptors in construction order.
2502    pub meshlets: Vec<Meshlet>,
2503    /// Original vertex references.
2504    pub vertices: Vec<u32>,
2505    /// Local triangle bytes, without per-meshlet padding.
2506    pub triangles: Vec<u8>,
2507}
2508impl From<MeshletsGeneric<u32>> for Meshlets {
2509    #[inline]
2510    fn from(value: MeshletsGeneric<u32>) -> Self {
2511        Self {
2512            meshlets: value.meshlets,
2513            vertices: value.vertices,
2514            triangles: value.triangles,
2515        }
2516    }
2517}
2518
2519impl From<Meshlets> for MeshletsGeneric<u32> {
2520    #[inline]
2521    fn from(value: Meshlets) -> Self {
2522        Self {
2523            meshlets: value.meshlets,
2524            vertices: value.vertices,
2525            triangles: value.triangles,
2526        }
2527    }
2528}
2529
2530#[cfg(test)]
2531mod packed_tests {
2532    use super::*;
2533    #[test]
2534    fn packed_children_check_actual_metadata_without_truncation() {
2535        let mut node = Node::default();
2536        node.set(3, 0x3fffffff).unwrap();
2537        assert_eq!(node.meta, u32::MAX);
2538        assert_eq!(node.axis(), 3);
2539        assert_eq!(node.children(), 0x3fffffff);
2540        assert_eq!(node.set(0, 0x40000000), Err(Error::SizeOverflow));
2541        assert_eq!(node.meta, u32::MAX);
2542    }
2543    #[test]
2544    fn small_divide_matches_integer_division() {
2545        let mut x = 0x9e37_79b9u32;
2546        for d in 1..=512usize {
2547            for edge in [
2548                0,
2549                1,
2550                d - 1,
2551                d,
2552                d + 1,
2553                (1 << 22) - 1,
2554                1 << 22,
2555                u32::MAX as usize,
2556            ] {
2557                assert_eq!(small_divide(edge, d), edge / d);
2558            }
2559            for _ in 0..512 {
2560                x = x.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
2561                assert_eq!(small_divide(x as usize, d), x as usize / d);
2562                let small = (x >> 10) as usize;
2563                assert_eq!(small_divide(small, d), small / d);
2564            }
2565        }
2566        assert_eq!(small_divide(usize::MAX, 7), usize::MAX / 7);
2567    }
2568}