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, sqrt8, RootEstimate, SqrtCache, LANES};
4use crate::processing::{cross, dot, finite, point, sub, Context};
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8/// Current 1.3 descriptor: triangle offsets are consecutive byte offsets, without padding.
9#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
10pub struct Meshlet {
11    /// Offset in the vertex-reference array.
12    pub vertex_offset: u32,
13    /// Offset in the byte triangle array.
14    pub triangle_offset: u32,
15    /// Number of referenced vertices.
16    pub vertex_count: u32,
17    /// Number of triangles (three bytes each).
18    pub triangle_count: u32,
19}
20/// Complete tightly packed meshlet output.
21#[derive(Debug, Default, PartialEq, Eq)]
22pub struct Meshlets {
23    /// Meshlet descriptors in construction order.
24    pub meshlets: Vec<Meshlet>,
25    /// Original vertex references.
26    pub vertices: Vec<u32>,
27    /// Local triangle bytes, without per-meshlet padding.
28    pub triangles: Vec<u8>,
29}
30/// Limits used by all meshlet builders.
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub struct MeshletSettings {
33    /// Maximum vertices, 3 through 256.
34    pub max_vertices: usize,
35    /// Maximum triangles, 1 through 512.
36    pub max_triangles: usize,
37}
38impl Default for MeshletSettings {
39    fn default() -> Self {
40        Self {
41            max_vertices: 64,
42            max_triangles: 124,
43        }
44    }
45}
46/// Used prefixes after caller-buffer meshlet construction.
47#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
48pub struct MeshletSizes {
49    /// Number of descriptors.
50    pub meshlets: usize,
51    /// Number of vertex references.
52    pub vertices: usize,
53    /// Number of triangle bytes.
54    pub triangles: usize,
55}
56/// `meshopt_buildMeshletsBound`: conservative descriptor capacity, with checked arithmetic.
57///
58/// # Errors
59/// `InvalidTopology` for incomplete triangles; `InvalidParameter` for unsupported meshlet limits;
60/// `SizeOverflow` if the bound cannot be represented.
61#[inline(always)]
62pub fn build_meshlets_bound(
63    index_count: usize,
64    max_vertices: usize,
65    max_triangles: usize,
66) -> Result<usize, Error> {
67    if !index_count.is_multiple_of(3) {
68        return Err(Error::InvalidTopology);
69    }
70    if !(3..=256).contains(&max_vertices) || !(1..=512).contains(&max_triangles) {
71        return Err(Error::InvalidParameter);
72    }
73    let v = max_vertices - 2;
74    let a = small_divide(
75        index_count.checked_add(v - 1).ok_or(Error::SizeOverflow)?,
76        v,
77    );
78    let b = small_divide(
79        (index_count / 3)
80            .checked_add(max_triangles - 1)
81            .ok_or(Error::SizeOverflow)?,
82        max_triangles,
83    );
84    Ok(a.max(b))
85}
86// ceil(2^32 / d) for every divisor 1..=512 (D78).
87static RECIPROCALS: [u64; 513] = {
88    let mut table = [0u64; 513];
89    let mut d = 1;
90    while d < 513 {
91        table[d] = (1u64 << 32).div_ceil(d as u64);
92        d += 1;
93    }
94    table
95};
96// x / d for 1 <= d <= 512. Below 2^22 a 64-bit multiply by ceil(2^32 / d)
97// is exact: it exceeds x / d by less than 2^22 / 2^32 = 2^-10, while the
98// fractional part of x / d is at most 1 - 1/512 = 1 - 2^-9.
99#[inline(always)]
100fn small_divide(x: usize, d: usize) -> usize {
101    match RECIPROCALS.get(d) {
102        Some(&m) if d != 0 && x < 1 << 22 => ((x as u64 * m) >> 32) as usize,
103        _ => x / d,
104    }
105}
106pub(crate) struct Output<'a> {
107    pub(crate) descriptors: &'a mut [Meshlet],
108    pub(crate) vertices: &'a mut [u32],
109    pub(crate) triangles: &'a mut [u8],
110    pub(crate) current: Meshlet,
111    pub(crate) count: usize,
112}
113pub(crate) trait UsedVertices {
114    fn local(&self, vertex: usize) -> i16;
115    fn set_local(&mut self, vertex: usize, local: i16);
116}
117impl UsedVertices for [i16] {
118    #[inline(always)]
119    fn local(&self, vertex: usize) -> i16 {
120        self[vertex]
121    }
122    #[inline(always)]
123    fn set_local(&mut self, vertex: usize, local: i16) {
124        self[vertex] = local;
125    }
126}
127impl<T> UsedVertices for Vec<T>
128where
129    [T]: UsedVertices,
130{
131    #[inline(always)]
132    fn local(&self, vertex: usize) -> i16 {
133        self.as_slice().local(vertex)
134    }
135    #[inline(always)]
136    fn set_local(&mut self, vertex: usize, local: i16) {
137        self.as_mut_slice().set_local(vertex, local);
138    }
139}
140impl Output<'_> {
141    #[inline(always)]
142    pub(crate) fn append<U: UsedVertices + ?Sized>(
143        &mut self,
144        t: &[u32; 3],
145        used: &mut U,
146        s: MeshletSettings,
147        split: bool,
148        ctx: &mut Context<'_>,
149    ) -> Result<bool, Error> {
150        ctx.tick(1)?;
151        // Work on a local copy of the open descriptor: the output slices could
152        // otherwise alias it for the optimizer, forcing a reload per access.
153        let mut m = self.current;
154        let [a, b, c] = t.map(|v| v as usize);
155        let mut local = [used.local(a), used.local(b), used.local(c)];
156        // Count missing corners before deduplicating, as upstream does. Keep
157        // the original conservative flush decision on degenerate triangles.
158        let extra = local.iter().filter(|&&v| v < 0).count();
159        let mut flush = false;
160        if m.vertex_count as usize + extra > s.max_vertices
161            || m.triangle_count as usize >= s.max_triangles
162            || split
163        {
164            self.descriptors[self.count] = m;
165            self.count += 1;
166            ctx.tick(m.vertex_count as usize)?;
167            for &v in &self.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
168                used.set_local(v as usize, -1);
169            }
170            m.vertex_offset += m.vertex_count;
171            m.triangle_offset += m.triangle_count * 3;
172            m.vertex_count = 0;
173            m.triangle_count = 0;
174            local = [-1; 3];
175            flush = true;
176        }
177        let off = m.triangle_offset as usize + m.triangle_count as usize * 3;
178        let triangle = &mut self.triangles[off..off + 3];
179        for k in 0..3 {
180            if local[k] < 0 {
181                // A preceding missing corner may have inserted this vertex.
182                // The usual distinct-corner case needs no second table load.
183                if k > 0 && t[k] == t[0] {
184                    local[k] = local[0];
185                } else if k == 2 && t[k] == t[1] {
186                    local[k] = local[1];
187                } else {
188                    local[k] = m.vertex_count as i16;
189                    used.set_local(t[k] as usize, local[k]);
190                    self.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
191                    m.vertex_count += 1;
192                }
193            }
194            triangle[k] = local[k] as u8;
195        }
196        m.triangle_count += 1;
197        self.current = m;
198        Ok(flush)
199    }
200    fn finish(&mut self) -> MeshletSizes {
201        if self.current.triangle_count != 0 {
202            self.descriptors[self.count] = self.current;
203            self.count += 1;
204        }
205        MeshletSizes {
206            meshlets: self.count,
207            vertices: (self.current.vertex_offset + self.current.vertex_count) as usize,
208            triangles: (self.current.triangle_offset + self.current.triangle_count * 3) as usize,
209        }
210    }
211}
212fn validate(s: MeshletSettings, min: usize, weight: f32, split: f32) -> Result<(), Error> {
213    build_meshlets_bound(0, s.max_vertices, s.max_triangles)?;
214    if min == 0
215        || min > s.max_triangles
216        || !weight.is_finite()
217        || !(0.0..=1.0).contains(&weight)
218        || !split.is_finite()
219        || split < 0.
220    {
221        return Err(Error::InvalidParameter);
222    }
223    Ok(())
224}
225#[derive(Clone, Copy, Default)]
226struct Cone {
227    p: [f32; 3],
228    n: [f32; 3],
229}
230// `getMeshletCone` position: the accumulated centroid over the count.
231#[inline(always)]
232fn cone_position(acc: Cone, count: u32) -> [f32; 3] {
233    let scale = if count == 0 { 0. } else { 1. / count as f32 };
234    acc.p.map(|v| v * scale)
235}
236// `getMeshletCone` normal: acc * (1 / sqrt(|acc|^2)), or zero for |acc| = 0.
237struct MeshletNormal {
238    low: [f32; 3],
239    high: [f32; 3],
240    exact: Option<[f32; 3]>,
241}
242impl MeshletNormal {
243    fn exact(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
244        let l = dot(acc, acc);
245        let scale = if l == 0. { 0. } else { 1. / roots.sqrt(l) };
246        let n = acc.map(|v| v * scale);
247        Self {
248            low: n,
249            high: n,
250            exact: Some(n),
251        }
252    }
253    // Bounds of each rounded component: the table bounds the rounded scale
254    // fl(1 / fl(sqrt(l))) without a division (D79), and acc_k * scale is
255    // monotone in scale with the sign of acc_k.
256    #[inline(always)]
257    fn bounds(acc: [f32; 3], roots: &mut SqrtCache) -> Self {
258        let l = dot(acc, acc);
259        let Some(root) = RootEstimate::new(l) else {
260            return Self::exact(acc, roots);
261        };
262        let (scale_low, scale_high) = root.inverse_table();
263        let mut low = [0f32; 3];
264        let mut high = [0f32; 3];
265        for k in 0..3 {
266            let (a, b) = (acc[k] * scale_low, acc[k] * scale_high);
267            (low[k], high[k]) = if acc[k] >= 0. { (a, b) } else { (b, a) };
268        }
269        Self {
270            low,
271            high,
272            exact: None,
273        }
274    }
275}
276// Adjacency offset, live triangle count and meshlet-local index of one vertex,
277// packed so that a meshlet-vertex visit touches one record.
278#[derive(Clone, Copy)]
279struct VertexState {
280    offset: u32,
281    live: u32,
282    local: i16,
283}
284impl Default for VertexState {
285    fn default() -> Self {
286        Self {
287            offset: 0,
288            live: 0,
289            local: -1,
290        }
291    }
292}
293impl UsedVertices for [VertexState] {
294    #[inline(always)]
295    fn local(&self, vertex: usize) -> i16 {
296        self[vertex].local
297    }
298    #[inline(always)]
299    fn set_local(&mut self, vertex: usize, local: i16) {
300        self[vertex].local = local;
301    }
302}
303struct Adjacency {
304    vertices: Vec<VertexState>,
305    data: Vec<u32>,
306}
307fn adjacency(indices: &[u32], n: usize, ctx: &mut Context<'_>) -> Result<Adjacency, Error> {
308    let mut vertices = ctx.alloc::<VertexState>(n)?;
309    let mut data = ctx.alloc::<u32>(indices.len())?;
310    ctx.tick(n + indices.len() * 2)?;
311    for &v in indices {
312        vertices[v as usize].live += 1;
313    }
314    let mut offset = 0;
315    for vertex in vertices.iter_mut() {
316        vertex.offset = offset;
317        offset += vertex.live;
318    }
319    for (i, t) in indices.as_chunks::<3>().0.iter().enumerate() {
320        for &v in t {
321            let o = &mut vertices[v as usize].offset;
322            data[*o as usize] = i as u32;
323            *o += 1;
324        }
325    }
326    for vertex in vertices.iter_mut() {
327        vertex.offset -= vertex.live;
328    }
329    Ok(Adjacency { vertices, data })
330}
331// Preserve the upstream packed eight-byte KD node.
332#[derive(Clone, Copy, Default)]
333struct Node {
334    data: u32,
335    meta: u32,
336}
337impl Node {
338    fn axis(self) -> usize {
339        (self.meta & 3) as usize
340    }
341    fn children(self) -> usize {
342        (self.meta >> 2) as usize
343    }
344    fn set(&mut self, axis: usize, children: usize) -> Result<(), Error> {
345        if children > 0x3fffffff {
346            return Err(Error::SizeOverflow);
347        }
348        self.meta = (children as u32) << 2 | axis as u32;
349        Ok(())
350    }
351}
352#[cfg(test)]
353mod packed_tests {
354    use super::*;
355    #[test]
356    fn packed_children_check_actual_metadata_without_truncation() {
357        let mut node = Node::default();
358        node.set(3, 0x3fffffff).unwrap();
359        assert_eq!(node.meta, u32::MAX);
360        assert_eq!(node.axis(), 3);
361        assert_eq!(node.children(), 0x3fffffff);
362        assert_eq!(node.set(0, 0x40000000), Err(Error::SizeOverflow));
363        assert_eq!(node.meta, u32::MAX);
364    }
365    #[test]
366    fn small_divide_matches_integer_division() {
367        let mut x = 0x9e37_79b9u32;
368        for d in 1..=512usize {
369            for edge in [
370                0,
371                1,
372                d - 1,
373                d,
374                d + 1,
375                (1 << 22) - 1,
376                1 << 22,
377                u32::MAX as usize,
378            ] {
379                assert_eq!(small_divide(edge, d), edge / d);
380            }
381            for _ in 0..512 {
382                x = x.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
383                assert_eq!(small_divide(x as usize, d), x as usize / d);
384                let small = (x >> 10) as usize;
385                assert_eq!(small_divide(small, d), small / d);
386            }
387        }
388        assert_eq!(small_divide(usize::MAX, 7), usize::MAX / 7);
389    }
390}
391// Split statistics of one kd range: Welford mean and variance per axis.
392#[derive(Clone, Copy, Default)]
393struct KdSplit {
394    mean: [f32; 3],
395    axis: usize,
396}
397impl KdSplit {
398    #[inline(always)]
399    fn finish(mean: [f32; 3], vars: [f32; 3]) -> Self {
400        let axis = if vars[0] >= vars[1] && vars[0] >= vars[2] {
401            0
402        } else if vars[1] >= vars[2] {
403            1
404        } else {
405            2
406        };
407        Self { mean, axis }
408    }
409}
410#[inline(always)]
411fn welford(p: [f32; 3], mean: &mut [f32; 3], vars: &mut [f32; 3], runs: f32) {
412    for k in 0..3 {
413        let delta = p[k] - mean[k];
414        mean[k] += delta * runs;
415        vars[k] += delta * (p[k] - mean[k]);
416    }
417}
418fn kd_stats(order: &[u32], cones: &[Cone]) -> KdSplit {
419    let (mut mean, mut vars) = ([0.; 3], [0.; 3]);
420    let (mut runc, mut runs) = (1f32, 1f32);
421    for &v in order {
422        welford(cones[v as usize].p, &mut mean, &mut vars, runs);
423        runc += 1.;
424        runs = 1. / runc;
425    }
426    KdSplit::finish(mean, vars)
427}
428// Statistics of two sibling ranges in one loop: the two Welford chains are
429// independent, and both use the same running weight at the same position.
430fn kd_stats2(a: &[u32], b: &[u32], cones: &[Cone]) -> (KdSplit, KdSplit) {
431    let (mut am, mut av, mut bm, mut bv) = ([0.; 3], [0.; 3], [0.; 3], [0.; 3]);
432    let (mut runc, mut runs) = (1f32, 1f32);
433    let common = a.len().min(b.len());
434    for (&x, &y) in a[..common].iter().zip(&b[..common]) {
435        welford(cones[x as usize].p, &mut am, &mut av, runs);
436        welford(cones[y as usize].p, &mut bm, &mut bv, runs);
437        runc += 1.;
438        runs = 1. / runc;
439    }
440    let (rest, mean, vars) = if a.len() > common {
441        (&a[common..], &mut am, &mut av)
442    } else {
443        (&b[common..], &mut bm, &mut bv)
444    };
445    for &v in rest {
446        welford(cones[v as usize].p, mean, vars, runs);
447        runc += 1.;
448        runs = 1. / runc;
449    }
450    (KdSplit::finish(am, av), KdSplit::finish(bm, bv))
451}
452// `kdtreeBuild`. A split node computes its children's statistics together
453// (they depend only on the partition, which later recursion does not touch);
454// each child still charges its work and checks its mean when it is built,
455// so budget failures and errors occur exactly where the recursion did.
456fn kd_build(
457    nodes: &mut [Node],
458    offset: usize,
459    order: &mut [u32],
460    cones: &[Cone],
461    depth: usize,
462    split: Option<KdSplit>,
463    ctx: &mut Context<'_>,
464) -> Result<usize, Error> {
465    let n = order.len();
466    let mut middle = 0;
467    let mut stats = KdSplit::default();
468    if n > 8 {
469        ctx.tick(n * 2)?;
470        stats = split.unwrap_or_else(|| kd_stats(order, cones));
471        let (mean, axis) = (stats.mean, stats.axis);
472        finite(mean[axis])?;
473        for i in 0..n {
474            let v = cones[order[i] as usize].p[axis];
475            order.swap(middle, i);
476            middle += usize::from(v < mean[axis]);
477        }
478    }
479    if n <= 8 || middle <= 4 || middle >= n - 4 || depth >= 50 {
480        if n > 0x3fffffff {
481            return Err(Error::SizeOverflow);
482        }
483        ctx.tick(n)?;
484        for (i, &v) in order.iter().enumerate() {
485            nodes[offset + i] = Node {
486                data: v,
487                meta: 3 | ((if i == 0 { n as u32 } else { 0x3fffffff }) << 2),
488            };
489        }
490        return Ok(offset + n);
491    }
492    nodes[offset].data = stats.mean[stats.axis].to_bits();
493    let (left, right) = order.split_at_mut(middle);
494    let (left_split, right_split) = match (left.len() > 8, right.len() > 8) {
495        (true, true) => {
496            let (l, r) = kd_stats2(left, right, cones);
497            (Some(l), Some(r))
498        }
499        (true, false) => (Some(kd_stats(left, cones)), None),
500        (false, true) => (None, Some(kd_stats(right, cones))),
501        (false, false) => (None, None),
502    };
503    let next = kd_build(nodes, offset + 1, left, cones, depth + 1, left_split, ctx)?;
504    nodes[offset].set(stats.axis, next - offset - 1)?;
505    kd_build(nodes, next, right, cones, depth + 1, right_split, ctx)
506}
507fn nearest<const CHECK: bool>(
508    nodes: &mut [Node],
509    root: usize,
510    cones: &[Cone],
511    emitted: &[u8],
512    p: [f32; 3],
513    result: &mut u32,
514    limit: &mut f32,
515    roots: &mut SqrtCache,
516    ctx: &mut Context<'_>,
517) -> Result<(), Error> {
518    ctx.tick(1)?;
519    let node = nodes[root];
520    if node.children() == 0 {
521        return Ok(());
522    }
523    if node.axis() == 3 && !CHECK && ctx.work.covers(node.children())? {
524        // Moderate leaves cannot fail: one inline loop, charged once.
525        let count = node.children();
526        let mut inactive = true;
527        for item in &nodes[root..root + count] {
528            let v = item.data as usize;
529            if emitted[v] == EMITTED {
530                continue;
531            }
532            inactive = false;
533            let d = sub(cones[v].p, p);
534            let square = dot(d, d);
535            if lower_distance(d) >= *limit || root_at_least(square, *limit) {
536                continue;
537            }
538            let distance = roots.sqrt(square);
539            if distance < *limit {
540                *result = v as u32;
541                *limit = distance;
542            }
543        }
544        ctx.tick(count)?;
545        if inactive {
546            nodes[root].set(3, 0)?;
547        }
548    } else if node.axis() == 3 {
549        let mut inactive = true;
550        ctx.scan(0..node.children(), |_ctx, i| {
551            let v = nodes[root + i].data as usize;
552            if emitted[v] == EMITTED {
553                return Ok(());
554            }
555            inactive = false;
556            let d = sub(cones[v].p, p);
557            if !CHECK && (lower_distance(d) >= *limit || root_at_least(dot(d, d), *limit)) {
558                return Ok(());
559            }
560            let distance = roots.sqrt(number::<CHECK>(dot(d, d))?);
561            if distance < *limit {
562                *result = v as u32;
563                *limit = distance;
564            }
565            Ok(())
566        })?;
567        if inactive {
568            nodes[root].set(3, 0)?;
569        }
570    } else {
571        let delta = p[node.axis()] - f32::from_bits(node.data);
572        let first = if delta <= 0. { 0 } else { node.children() };
573        let second = first ^ node.children();
574        if nodes[root + 1 + first].children() | nodes[root + 1 + second].children() == 0 {
575            nodes[root].set(node.axis(), 0)?;
576        }
577        nearest::<CHECK>(
578            nodes,
579            root + 1 + first,
580            cones,
581            emitted,
582            p,
583            result,
584            limit,
585            roots,
586            ctx,
587        )?;
588        if delta.abs() <= *limit {
589            nearest::<CHECK>(
590                nodes,
591                root + 1 + second,
592                cones,
593                emitted,
594                p,
595                result,
596                limit,
597                roots,
598                ctx,
599            )?;
600        }
601    }
602    Ok(())
603}
604// Each absolute component is a conservative lower bound on the correctly
605// rounded Euclidean distance. Use only after the finite-coordinate envelope.
606#[inline(always)]
607fn lower_distance(d: [f32; 3]) -> f32 {
608    // Plain comparisons: moderate inputs are finite, so NaN-aware max is unneeded.
609    let (x, y, z) = (d[0].abs(), d[1].abs(), d[2].abs());
610    let m = if x > y { x } else { y };
611    let m = if m > z { m } else { z };
612    // Below this envelope a rounded square can be subnormal or zero.
613    if m >= 1.0e-18 {
614        m
615    } else {
616        0.0
617    }
618}
619#[inline(always)]
620fn number<const CHECK: bool>(value: f32) -> Result<f32, Error> {
621    if CHECK {
622        finite(value)
623    } else {
624        Ok(value)
625    }
626}
627#[inline(always)]
628fn distance<const CHECK: bool>(
629    a: [f32; 3],
630    b: [f32; 3],
631    roots: &mut SqrtCache,
632) -> Result<f32, Error> {
633    let d = sub(a, b);
634    Ok(roots.sqrt(number::<CHECK>(dot(d, d))?))
635}
636// The selected candidate's score is kept as a bracket [lo, hi] around the
637// exact upstream score. `known` means lo == hi == the exact score. The exact
638// root is computed only when a comparison cannot be decided from brackets.
639struct Selection {
640    triangle: u32,
641    priority: i32,
642    lo: f32,
643    hi: f32,
644    known: bool,
645    square: f32,
646}
647impl Selection {
648    fn new() -> Self {
649        Self {
650            triangle: u32::MAX,
651            priority: 5,
652            lo: f32::MAX,
653            hi: f32::MAX,
654            known: true,
655            square: 0.,
656        }
657    }
658}
659struct CandidateInput<'a> {
660    triangles: &'a [[u32; 3]],
661    vertices: &'a [VertexState],
662    cones: &'a [Cone],
663    meshlet: Cone,
664    weight: f32,
665    radius: f32,
666    // Reciprocal bounds around 1 / radius; `bounded` when both are finite
667    // and the radius is a positive normal value.
668    inverse_low: f32,
669    inverse_high: f32,
670    bounded: bool,
671    // Bounded mode: bounds of the normalized meshlet normal, from root bounds
672    // of its squared length; the exact normal is computed only on demand.
673    accumulated: [f32; 3],
674    normal_low: [f32; 3],
675    normal_high: [f32; 3],
676}
677// Mutable state of one neighbor search: the root memo and the exact meshlet
678// normal once computed. Kept out of CandidateInput so `&CandidateInput`
679// stays freeze-only and its fields can be held in registers.
680struct Search<'r> {
681    roots: &'r mut SqrtCache,
682    normal: Option<[f32; 3]>,
683    // Candidates come from the meshlet's candidate list rather than in visit
684    // order: exact ties are then broken by the upstream visit order.
685    listed: bool,
686    data: &'r [u32],
687}
688impl CandidateInput<'_> {
689    #[inline(always)]
690    fn one<const CHECK: bool>(
691        &self,
692        tri: u32,
693        local: u16,
694        selected: &mut Selection,
695        search: &mut Search<'_>,
696    ) -> Result<(), Error> {
697        let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
698        let (av, bv, cv) = (self.vertices[a], self.vertices[b], self.vertices[c]);
699        // A live triangle is listed under each of its meshlet vertices. When one
700        // of them precedes the vertex being scanned, this visit repeats an
701        // earlier one with identical priority and score; under the strict
702        // lexicographic selection (including NaN scores) it cannot change it.
703        if (av.local as u16).min(bv.local as u16).min(cv.local as u16) < local {
704            return Ok(());
705        }
706        self.evaluate::<CHECK>(tri, [av, bv, cv], selected, search)
707    }
708    #[inline(always)]
709    fn evaluate<const CHECK: bool>(
710        &self,
711        tri: u32,
712        [av, bv, cv]: [VertexState; 3],
713        selected: &mut Selection,
714        search: &mut Search<'_>,
715    ) -> Result<(), Error> {
716        let extra = i32::from(av.local < 0) + i32::from(bv.local < 0) + i32::from(cv.local < 0);
717        let (al, bl, cl) = (av.live, bv.live, cv.live);
718        let priority = if extra == 0 {
719            0
720        } else if al == 1 || bl == 1 || cl == 1 {
721            1
722        } else if i32::from(al == 2) + i32::from(bl == 2) + i32::from(cl == 2) >= 2 {
723            1 + extra
724        } else {
725            2 + extra
726        };
727        if priority > selected.priority {
728            return Ok(());
729        }
730        let cone = self.cones[tri as usize];
731        let dp = sub(cone.p, self.meshlet.p);
732        let square = dot(dp, dp);
733        let square = if CHECK { finite(square)? } else { square };
734        if !CHECK && self.bounded {
735            self.bracketed(tri, priority, cone.n, square, selected, search);
736            return Ok(());
737        }
738        let clamped = self.clamped(dot(cone.n, self.meshlet.n));
739        let distance = search.roots.sqrt(square);
740        let score = self.score(distance, clamped);
741        // Zero-area geometry retains the upstream NaN score/tie behavior.
742        if priority < selected.priority || score < selected.hi {
743            *selected = Selection {
744                triangle: tri,
745                priority,
746                lo: score,
747                hi: score,
748                known: true,
749                square,
750            };
751        }
752        Ok(())
753    }
754    #[inline(always)]
755    fn clamped(&self, spread: f32) -> f32 {
756        let cc = 1. - spread * self.weight;
757        if cc < 1e-3 {
758            1e-3
759        } else {
760            cc
761        }
762    }
763    #[inline(always)]
764    fn score(&self, distance: f32, clamped: f32) -> f32 {
765        (1. + distance / self.radius * (1. - self.weight)) * clamped
766    }
767    // Bounded mode (moderate inputs, positive normal radius with finite
768    // reciprocal bounds): every operand is finite, the radius and cone factor
769    // are positive and 0 <= weight <= 1. Each rounded operation of the score
770    // is then monotone in each input: nondecreasing in the distance and in
771    // the cone factor, the cone factor nonincreasing in the spread, and each
772    // rounded product of the spread nondecreasing (cone component >= 0) or
773    // nonincreasing (< 0) in the meshlet normal component. Scores from the
774    // bounding inputs therefore bound the exact upstream score, and a
775    // comparison decided by disjoint bounds equals the exact comparison.
776    // Multiplying by a reciprocal rounded away from 1/radius by more than
777    // its own rounding keeps the quotient on one side of the real d / radius.
778    #[inline(always)]
779    fn score_low(&self, distance: f32, clamped: f32) -> f32 {
780        (1. + distance * self.inverse_low * (1. - self.weight)) * clamped
781    }
782    #[inline(always)]
783    fn score_high(&self, distance: f32, clamped: f32) -> f32 {
784        (1. + distance * self.inverse_high * (1. - self.weight)) * clamped
785    }
786    // Bounds of the cone factor from the meshlet normal bounds.
787    #[inline(always)]
788    fn clamped_bounds(&self, n: [f32; 3], low: bool) -> f32 {
789        // Bounded-mode normals are finite. With zero cone weight the factor
790        // is exactly one, independently of the normal interval.
791        if self.weight == 0. {
792            return 1.;
793        }
794        // Each exact term n_k * normal_k lies between the products with the
795        // normal bounds, so their larger (smaller) values bound the spread.
796        let (lo, hi) = (self.normal_low, self.normal_high);
797        let term = |k: usize| {
798            let (a, b) = (n[k] * lo[k], n[k] * hi[k]);
799            if (a > b) == low {
800                a
801            } else {
802                b
803            }
804        };
805        // The cone factor decreases with the spread.
806        self.clamped(term(0) + term(1) + term(2))
807    }
808    // The exact meshlet normal, computed at most once per neighbor search.
809    #[cold]
810    #[inline(never)]
811    fn exact_normal(&self, search: &mut Search<'_>) -> [f32; 3] {
812        if self.weight == 0. {
813            return [0.; 3];
814        }
815        if let Some(n) = search.normal {
816            return n;
817        }
818        let l = dot(self.accumulated, self.accumulated);
819        let scale = if l == 0. {
820            0.
821        } else {
822            1. / search.roots.sqrt(l)
823        };
824        let n = self.accumulated.map(|v| v * scale);
825        search.normal = Some(n);
826        n
827    }
828    #[inline(always)]
829    fn bracketed(
830        &self,
831        tri: u32,
832        priority: i32,
833        normal: [f32; 3],
834        square: f32,
835        selected: &mut Selection,
836        search: &mut Search<'_>,
837    ) {
838        let clamped_low = self.clamped_bounds(normal, true);
839        let (lo, hi) = match RootEstimate::new(square) {
840            Some(root) => {
841                // Division-free table bounds reject most losers (listed
842                // candidates only on a strict loss: they may win a tie).
843                let low = self.score_low(root.table().0, clamped_low);
844                if priority == selected.priority
845                    && (low > selected.hi || (low == selected.hi && !search.listed))
846                {
847                    return;
848                }
849                let (dlo, dhi) = root.bounds();
850                (
851                    self.score_low(dlo, clamped_low),
852                    self.score_high(dhi, self.clamped_bounds(normal, false)),
853                )
854            }
855            None => {
856                let d = search.roots.sqrt(square);
857                (
858                    self.score_low(d, clamped_low),
859                    self.score_high(d, self.clamped_bounds(normal, false)),
860                )
861            }
862        };
863        if priority == selected.priority {
864            // Listed candidates may tie with an earlier-visited selection.
865            if lo > selected.hi || (lo == selected.hi && !search.listed) {
866                return;
867            }
868            if hi >= selected.lo {
869                self.resolve(tri, priority, square, selected, search);
870                return;
871            }
872        }
873        *selected = Selection {
874            triangle: tri,
875            priority,
876            lo,
877            hi,
878            known: false,
879            square,
880        };
881    }
882    // Upstream visit order of a candidate: its earliest meshlet vertex (by
883    // local index), then its position in that vertex's live adjacency list.
884    fn visit(&self, tri: u32, data: &[u32]) -> (u16, usize) {
885        let mut first = (u16::MAX, 0usize);
886        for &v in &self.triangles[tri as usize] {
887            let state = self.vertices[v as usize];
888            if (state.local as u16) < first.0 {
889                first = (state.local as u16, v as usize);
890            }
891        }
892        let state = self.vertices[first.1];
893        let list = &data[state.offset as usize..][..state.live as usize];
894        (
895            first.0,
896            list.iter().position(|&t| t == tri).unwrap_or(list.len()),
897        )
898    }
899    // Undecided equal-priority comparison: compute both exact scores.
900    #[cold]
901    #[inline(never)]
902    fn resolve(
903        &self,
904        tri: u32,
905        priority: i32,
906        square: f32,
907        selected: &mut Selection,
908        search: &mut Search<'_>,
909    ) {
910        let n = self.exact_normal(search);
911        let mut exact = |tri: u32, square: f32| {
912            let clamped = self.clamped(dot(self.cones[tri as usize].n, n));
913            self.score(search.roots.sqrt(square), clamped)
914        };
915        if !selected.known {
916            let score = exact(selected.triangle, selected.square);
917            selected.lo = score;
918            selected.hi = score;
919            selected.known = true;
920        }
921        let score = exact(tri, square);
922        if score < selected.hi
923            || (search.listed
924                && score == selected.hi
925                && self.visit(tri, search.data) < self.visit(selected.triangle, search.data))
926        {
927            *selected = Selection {
928                triangle: tri,
929                priority,
930                lo: score,
931                hi: score,
932                known: true,
933                square,
934            };
935        }
936    }
937    // `getNeighborTriangle`: scan the live adjacency of every meshlet vertex.
938    // Visits are charged once at the end while the budget covers the visited
939    // prefix plus the next vertex's list (the per-vertex scans' condition);
940    // a failing visit charges the visited prefix. Once a list is not covered,
941    // the remaining visits keep the per-visit exhaustion point.
942    //
943    // In bounded mode the meshlet's candidate list (each live adjacent
944    // triangle once) replaces the per-vertex scan: the same visits are
945    // charged, and the selection is order-independent because scores are
946    // finite and exact ties are broken by the upstream visit order.
947    #[inline(always)]
948    fn neighbors<const CHECK: bool>(
949        &self,
950        active: &mut Active,
951        data: &[u32],
952        roots: &mut SqrtCache,
953        normal: Option<[f32; 3]>,
954        listed: Option<&mut Candidates>,
955        emitted: &[u8],
956        ctx: &mut Context<'_>,
957    ) -> Result<u32, Error> {
958        if let Some(listed) = listed.filter(|listed| !CHECK && !listed.overflow) {
959            let mut total = 0usize;
960            let mut kept = 0;
961            for k in 0..active.len {
962                let v = active.list[k];
963                let live = self.vertices[v as usize].live as usize;
964                if live != 0 {
965                    active.list[kept] = v;
966                    kept += 1;
967                    total += live;
968                }
969            }
970            active.len = kept;
971            if ctx.work.covers(total)? {
972                let mut search = Search {
973                    roots,
974                    normal,
975                    listed: true,
976                    data,
977                };
978                let mut selected = Selection::new();
979                let mut i = 0;
980                while i < listed.len {
981                    let tri = listed.list[i];
982                    if emitted[tri as usize] == EMITTED {
983                        listed.len -= 1;
984                        listed.list[i] = listed.list[listed.len];
985                        continue;
986                    }
987                    let [a, b, c] = self.triangles[tri as usize].map(|v| v as usize);
988                    let states = [self.vertices[a], self.vertices[b], self.vertices[c]];
989                    self.evaluate::<CHECK>(tri, states, &mut selected, &mut search)?;
990                    i += 1;
991                }
992                ctx.tick(total)?;
993                return Ok(selected.triangle);
994            }
995        }
996        let mut search = Search {
997            roots,
998            normal,
999            listed: false,
1000            data,
1001        };
1002        let mut selected = Selection::new();
1003        let mut visited = 0usize;
1004        let mut kept = 0;
1005        for k in 0..active.len {
1006            let v = active.list[k];
1007            let state = self.vertices[v as usize];
1008            let live = state.live as usize;
1009            // Lists only shrink: drop exhausted vertices. An empty list is
1010            // always covered, since visited never exceeds the budget.
1011            if live == 0 {
1012                continue;
1013            }
1014            active.list[kept] = v;
1015            kept += 1;
1016            let local = state.local as u16;
1017            if !ctx.work.covers(visited + live)? {
1018                ctx.tick(visited)?;
1019                for &v in &active.list[k..active.len] {
1020                    let state = self.vertices[v as usize];
1021                    let off = state.offset as usize;
1022                    for &tri in &data[off..off + state.live as usize] {
1023                        ctx.tick(1)?;
1024                        self.one::<CHECK>(tri, state.local as u16, &mut selected, &mut search)?;
1025                    }
1026                }
1027                return Ok(selected.triangle);
1028            }
1029            let off = state.offset as usize;
1030            for &tri in &data[off..off + live] {
1031                visited += 1;
1032                if let Err(error) = self.one::<CHECK>(tri, local, &mut selected, &mut search) {
1033                    ctx.tick(visited)?;
1034                    return Err(error);
1035                }
1036            }
1037        }
1038        active.len = kept;
1039        ctx.tick(visited)?;
1040        Ok(selected.triangle)
1041    }
1042}
1043// `emitted` states: free, emitted, or listed as a candidate of the meshlet.
1044const EMITTED: u8 = 1;
1045const LISTED: u8 = 2;
1046// Live triangles adjacent to the current meshlet, each once (bounded mode).
1047// A meshlet whose candidates exceed the fixed capacity uses the scan.
1048struct Candidates {
1049    list: [u32; 1024],
1050    len: usize,
1051    overflow: bool,
1052}
1053impl Candidates {
1054    fn new() -> Self {
1055        Self {
1056            list: [0; 1024],
1057            len: 0,
1058            overflow: false,
1059        }
1060    }
1061    fn clear(&mut self, emitted: &mut [u8]) {
1062        for &t in &self.list[..self.len] {
1063            if emitted[t as usize] == LISTED {
1064                emitted[t as usize] = 0;
1065            }
1066        }
1067        self.len = 0;
1068        self.overflow = false;
1069    }
1070    fn add(&mut self, live: &[u32], emitted: &mut [u8]) {
1071        for &t in live {
1072            if emitted[t as usize] == 0 {
1073                if self.len == self.list.len() {
1074                    self.overflow = true;
1075                    return;
1076                }
1077                emitted[t as usize] = LISTED;
1078                self.list[self.len] = t;
1079                self.len += 1;
1080            }
1081        }
1082    }
1083}
1084// Current-meshlet vertices whose live adjacency may be nonempty, in meshlet
1085// (local index) order. Vertices are appended as the meshlet grows and dropped
1086// once their lists are exhausted; live counts never increase again.
1087struct Active {
1088    list: [u32; 256],
1089    len: usize,
1090    offset: u32,
1091    synced: usize,
1092}
1093impl Active {
1094    fn new() -> Self {
1095        Self {
1096            list: [0; 256],
1097            len: 0,
1098            offset: 0,
1099            synced: 0,
1100        }
1101    }
1102    #[inline(always)]
1103    fn sync(
1104        &mut self,
1105        out: &Output<'_>,
1106        adj: &Adjacency,
1107        listed: Option<(&mut Candidates, &mut [u8])>,
1108    ) {
1109        let count = out.current.vertex_count as usize;
1110        let reset = out.current.vertex_offset != self.offset || count < self.synced;
1111        if reset {
1112            self.offset = out.current.vertex_offset;
1113            self.len = 0;
1114            self.synced = 0;
1115        }
1116        let added = &out.vertices[self.offset as usize..][self.synced..count];
1117        if let Some((candidates, emitted)) = listed {
1118            if reset {
1119                candidates.clear(emitted);
1120            }
1121            for &v in added {
1122                let state = adj.vertices[v as usize];
1123                if !candidates.overflow {
1124                    let off = state.offset as usize;
1125                    candidates.add(&adj.data[off..off + state.live as usize], emitted);
1126                }
1127            }
1128        }
1129        for &v in added {
1130            self.list[self.len] = v;
1131            self.len += 1;
1132        }
1133        self.synced = count;
1134    }
1135}
1136// Dispatch position storage once, outside the triangle loop. This keeps
1137// packed inputs as direct checked slice accesses without per-corner view tests.
1138fn fill_cones<const CHECK: bool>(
1139    triangles: &[[u32; 3]],
1140    cones: &mut [Cone],
1141    read: impl Fn(u32) -> [f32; 3],
1142) -> Result<f32, Error> {
1143    let mut mesh_area = 0.;
1144    for (group, out_cones) in triangles.chunks(LANES).zip(cones.chunks_mut(LANES)) {
1145        let mut normals = [[0f32; 3]; LANES];
1146        let mut squares = [1f32; LANES];
1147        for (k, (t, cone)) in group.iter().zip(out_cones.iter_mut()).enumerate() {
1148            let a = read(t[0]);
1149            let b = read(t[1]);
1150            let c = read(t[2]);
1151            let normal = cross(sub(b, a), sub(c, a));
1152            squares[k] = number::<CHECK>(dot(normal, normal))?;
1153            normals[k] = normal;
1154            for j in 0..3 {
1155                cone.p[j] = number::<CHECK>((a[j] + b[j] + c[j]) / 3.)?;
1156            }
1157        }
1158        let areas = sqrt8(squares);
1159        for (k, cone) in out_cones.iter_mut().enumerate() {
1160            let area = areas[k];
1161            let inv = if area == 0. { 0. } else { 1. / area };
1162            for (n, &v) in cone.n.iter_mut().zip(&normals[k]) {
1163                *n = number::<CHECK>(v * inv)?;
1164            }
1165            mesh_area = number::<CHECK>(mesh_area + area)?;
1166        }
1167    }
1168    Ok(mesh_area)
1169}
1170fn flex<const CHECK: bool, const ZERO_WEIGHT: bool>(
1171    out: &mut Output<'_>,
1172    indices: &[u32],
1173    p: Positions<'_>,
1174    s: MeshletSettings,
1175    min: usize,
1176    weight: f32,
1177    split_factor: f32,
1178    ctx: &mut Context<'_>,
1179) -> Result<(), Error> {
1180    // A separate monomorphization lets the bounded search fold its cone
1181    // factor and score multipliers, rather than testing a runtime zero at
1182    // every candidate. The checked/degenerate path retains its old arithmetic.
1183    let weight = if ZERO_WEIGHT { 0. } else { weight };
1184    if indices.is_empty() {
1185        return Ok(());
1186    }
1187    let n = indices.len() / 3;
1188    let node_count = n.checked_mul(2).ok_or(Error::SizeOverflow)?;
1189    // One exact per-call memo with a fixed table: no per-lookup dispatch.
1190    let mut roots = SqrtCache::new();
1191    let mut adj = adjacency(indices, p.len(), ctx)?;
1192    let mut emitted = ctx.alloc::<u8>(n)?;
1193    let mut cones = ctx.alloc::<Cone>(n)?;
1194    ctx.tick(n)?;
1195    let triangles = indices.as_chunks::<3>().0;
1196    let mesh_area = if let Some(values) = p.packed_values() {
1197        fill_cones::<CHECK>(triangles, &mut cones, |i| values[i as usize])?
1198    } else {
1199        fill_cones::<CHECK>(triangles, &mut cones, |i| point(p, i))?
1200    };
1201    let radius = roots.sqrt(number::<CHECK>(
1202        mesh_area / n as f32 * 0.5 * s.max_triangles as f32,
1203    )?) * 0.5;
1204    let mut order = ctx.alloc(n)?;
1205    for (i, v) in order.iter_mut().enumerate() {
1206        *v = i as u32;
1207    }
1208    let mut nodes = ctx.alloc(node_count)?;
1209    kd_build(&mut nodes, 0, &mut order, &cones, 0, None, ctx)?;
1210    ctx.tick(n.checked_mul(2).ok_or(Error::SizeOverflow)?)?;
1211    let mut corner = [f32::MAX; 3];
1212    for c in &cones {
1213        for (k, v) in corner.iter_mut().enumerate() {
1214            if *v > c.p[k] {
1215                *v = c.p[k];
1216            }
1217        }
1218    }
1219    let mut initial = u32::MAX;
1220    let mut score = f32::MAX;
1221    for (i, c) in cones.iter().enumerate() {
1222        if !CHECK && initial != u32::MAX && {
1223            let d = sub(c.p, corner);
1224            lower_distance(d) >= score || root_at_least(dot(d, d), score)
1225        } {
1226            continue;
1227        }
1228        let d = distance::<CHECK>(c.p, corner, &mut roots)?;
1229        if initial == u32::MAX || d < score {
1230            initial = i as u32;
1231            score = d;
1232        }
1233    }
1234    let mut seeds = [0u32; 256];
1235    let mut seed_count = 0;
1236    let mut acc = Cone::default();
1237    let mut active = Active::new();
1238    // 1 / radius rounds by at most 2^-24; scaling by 1 -+ 2^-21 (rounding by
1239    // another 2^-24) moves each bound strictly past the real reciprocal.
1240    let inverse = 1. / radius;
1241    let inverse_low = inverse * 0.999_999_5;
1242    let inverse_high = inverse * 1.000_000_5;
1243    let bounded = !CHECK
1244        && radius.is_normal()
1245        && radius > 0.
1246        && inverse_low.is_normal()
1247        && inverse_high.is_finite();
1248    // Bounded mode lists candidates on meshes large enough to repay the list
1249    // upkeep.
1250    // (Not constructed otherwise: the list is 4 KiB of stack to clear.)
1251    let mut candidates = (bounded && n >= 256).then(Candidates::new);
1252    loop {
1253        ctx.tick(1)?;
1254        let mc_position = cone_position(acc, out.current.triangle_count);
1255        let mut best;
1256        if out.count == 0 && out.current.triangle_count == 0 {
1257            best = initial;
1258        } else {
1259            // In bounded mode the meshlet normal is only bounded here (its root
1260            // is taken on demand); otherwise it is exact, as upstream. The
1261            // initial seed does not search neighbors and needs no normal.
1262            let normal = if bounded && weight == 0. {
1263                MeshletNormal {
1264                    exact: Some([0.; 3]),
1265                    low: [0.; 3],
1266                    high: [0.; 3],
1267                }
1268            } else if bounded {
1269                MeshletNormal::bounds(acc.n, &mut roots)
1270            } else {
1271                MeshletNormal::exact(acc.n, &mut roots)
1272            };
1273            let input = CandidateInput {
1274                triangles: indices.as_chunks::<3>().0,
1275                vertices: &adj.vertices,
1276                cones: &cones,
1277                meshlet: Cone {
1278                    p: mc_position,
1279                    n: normal.exact.unwrap_or_default(),
1280                },
1281                weight,
1282                radius,
1283                inverse_low,
1284                inverse_high,
1285                bounded,
1286                accumulated: acc.n,
1287                normal_low: normal.low,
1288                normal_high: normal.high,
1289            };
1290            active.sync(
1291                out,
1292                &adj,
1293                candidates
1294                    .as_mut()
1295                    .map(|candidates| (candidates, emitted.as_mut_slice())),
1296            );
1297            best = input.neighbors::<CHECK>(
1298                &mut active,
1299                &adj.data,
1300                &mut roots,
1301                normal.exact,
1302                candidates.as_mut(),
1303                &emitted,
1304                ctx,
1305            )?;
1306        }
1307        let mut split = false;
1308        if best == u32::MAX {
1309            let mut d = f32::MAX;
1310            nearest::<CHECK>(
1311                &mut nodes,
1312                0,
1313                &cones,
1314                &emitted,
1315                mc_position,
1316                &mut best,
1317                &mut d,
1318                &mut roots,
1319                ctx,
1320            )?;
1321            split = out.current.triangle_count as usize >= min
1322                && split_factor > 0.
1323                && d > radius * split_factor;
1324        }
1325        if best == u32::MAX {
1326            break;
1327        }
1328        let extra = indices[best as usize * 3..][..3]
1329            .iter()
1330            .filter(|&&v| adj.vertices[v as usize].local < 0)
1331            .count();
1332        if split
1333            || out.current.vertex_count as usize + extra > s.max_vertices
1334            || out.current.triangle_count as usize >= s.max_triangles
1335        {
1336            let mut keep = 0;
1337            for i in 0..seed_count {
1338                if emitted[seeds[i] as usize] != EMITTED {
1339                    seeds[keep] = seeds[i];
1340                    keep += 1;
1341                }
1342            }
1343            seed_count = keep.min(252);
1344            let mut candidates = [u32::MAX; 4];
1345            let mut lives = [u32::MAX; 4];
1346            let mut scores = [f32::MAX; 4];
1347            for &v in &out.vertices[out.current.vertex_offset as usize..]
1348                [..out.current.vertex_count as usize]
1349            {
1350                let off = adj.vertices[v as usize].offset as usize;
1351                let mut neighbor = u32::MAX;
1352                let mut live = u32::MAX;
1353                ctx.scan(
1354                    adj.data[off..off + adj.vertices[v as usize].live as usize]
1355                        .iter()
1356                        .copied(),
1357                    |_ctx, tri| {
1358                        let t = &indices[tri as usize * 3..][..3];
1359                        let l = adj.vertices[t[0] as usize].live
1360                            + adj.vertices[t[1] as usize].live
1361                            + adj.vertices[t[2] as usize].live;
1362                        if l < live {
1363                            neighbor = tri;
1364                            live = l;
1365                        }
1366                        Ok(())
1367                    },
1368                )?;
1369                if neighbor == u32::MAX {
1370                    continue;
1371                }
1372                let d = distance::<CHECK>(cones[neighbor as usize].p, corner, &mut roots)?;
1373                for j in 0..4 {
1374                    if live < lives[j] || (live == lives[j] && d <= scores[j]) {
1375                        candidates[j] = neighbor;
1376                        lives[j] = live;
1377                        scores[j] = d;
1378                        break;
1379                    }
1380                }
1381            }
1382            for tri in candidates {
1383                if tri != u32::MAX {
1384                    seeds[seed_count] = tri;
1385                    seed_count += 1;
1386                }
1387            }
1388            let mut seed = u32::MAX;
1389            let mut live = u32::MAX;
1390            let mut score = f32::MAX;
1391            ctx.scan(seeds[..seed_count].iter().copied(), |_ctx, tri| {
1392                let t = &indices[tri as usize * 3..][..3];
1393                let l = adj.vertices[t[0] as usize].live
1394                    + adj.vertices[t[1] as usize].live
1395                    + adj.vertices[t[2] as usize].live;
1396                if !CHECK
1397                    && (l > live
1398                        || (l == live && {
1399                            let d = sub(cones[tri as usize].p, corner);
1400                            lower_distance(d) >= score || root_at_least(dot(d, d), score)
1401                        }))
1402                {
1403                    return Ok(());
1404                }
1405                let d = distance::<CHECK>(cones[tri as usize].p, corner, &mut roots)?;
1406                if l < live || (l == live && d < score) {
1407                    seed = tri;
1408                    live = l;
1409                    score = d;
1410                }
1411                Ok(())
1412            })?;
1413            if seed != u32::MAX {
1414                best = seed;
1415            }
1416        }
1417        let t = &indices.as_chunks::<3>().0[best as usize];
1418        if out.append(t, &mut adj.vertices, s, split, ctx)? {
1419            acc = Cone::default();
1420        }
1421        for &v in t {
1422            let state = &mut adj.vertices[v as usize];
1423            let list = &mut adj.data[state.offset as usize..][..state.live as usize];
1424            // Charge the visited prefix of the search (the whole list when
1425            // absent); a short budget keeps the per-visit exhaustion point.
1426            let found = if ctx.work.covers(list.len())? {
1427                let found = list.iter().position(|&tri| tri == best);
1428                ctx.tick(found.map_or(list.len(), |i| i + 1))?;
1429                found
1430            } else {
1431                let mut found = None;
1432                for (i, &tri) in list.iter().enumerate() {
1433                    ctx.tick(1)?;
1434                    if tri == best {
1435                        found = Some(i);
1436                        break;
1437                    }
1438                }
1439                found
1440            };
1441            if let Some(i) = found {
1442                list[i] = list[list.len() - 1];
1443                state.live -= 1;
1444            }
1445        }
1446        for k in 0..3 {
1447            acc.p[k] = number::<CHECK>(acc.p[k] + cones[best as usize].p[k])?;
1448            acc.n[k] = number::<CHECK>(acc.n[k] + cones[best as usize].n[k])?;
1449        }
1450        emitted[best as usize] = EMITTED;
1451    }
1452    Ok(())
1453}
1454// The scan's output triangles are sequential and unpadded. A zipped output
1455// iterator proves all three destination slots once, and the descriptor stays
1456// local for the entire covered-budget loop instead of being published per face.
1457fn scan_covered(
1458    out: &mut Output<'_>,
1459    triangles: &[[u32; 3]],
1460    used: &mut [i16],
1461    s: MeshletSettings,
1462) -> usize {
1463    let mut m = out.current;
1464    let mut count = out.count;
1465    let mut visits = triangles.len();
1466    for (t, triangle) in triangles
1467        .iter()
1468        .zip(out.triangles[..triangles.len() * 3].as_chunks_mut::<3>().0)
1469    {
1470        let mut local = t.map(|v| used[v as usize]);
1471        let extra = local.iter().filter(|&&v| v < 0).count();
1472        if m.vertex_count as usize + extra > s.max_vertices
1473            || m.triangle_count as usize >= s.max_triangles
1474        {
1475            out.descriptors[count] = m;
1476            count += 1;
1477            visits += m.vertex_count as usize;
1478            for &v in &out.vertices[m.vertex_offset as usize..][..m.vertex_count as usize] {
1479                used[v as usize] = -1;
1480            }
1481            m.vertex_offset += m.vertex_count;
1482            m.triangle_offset += m.triangle_count * 3;
1483            m.vertex_count = 0;
1484            m.triangle_count = 0;
1485            local = [-1; 3];
1486        }
1487        for k in 0..3 {
1488            if local[k] < 0 {
1489                if k > 0 && t[k] == t[0] {
1490                    local[k] = local[0];
1491                } else if k == 2 && t[k] == t[1] {
1492                    local[k] = local[1];
1493                } else {
1494                    local[k] = m.vertex_count as i16;
1495                    used[t[k] as usize] = local[k];
1496                    out.vertices[m.vertex_offset as usize + m.vertex_count as usize] = t[k];
1497                    m.vertex_count += 1;
1498                }
1499            }
1500            triangle[k] = local[k] as u8;
1501        }
1502        m.triangle_count += 1;
1503    }
1504    out.current = m;
1505    out.count = count;
1506    visits
1507}
1508fn scan(
1509    out: &mut Output<'_>,
1510    indices: &[u32],
1511    n: usize,
1512    s: MeshletSettings,
1513    ctx: &mut Context<'_>,
1514) -> Result<(), Error> {
1515    let mut used = ctx.alloc::<i16>(n)?;
1516    used.fill(-1);
1517    let triangles = indices.as_chunks::<3>().0;
1518    // Each triangle costs one visit, and every flushed vertex was inserted by
1519    // a preceding corner. A covered upper bound lets the hot loop keep its
1520    // exact charge locally; short budgets retain every original failure point.
1521    if indices
1522        .len()
1523        .checked_add(triangles.len())
1524        .is_some_and(|bound| ctx.work.covers(bound).unwrap_or(false))
1525    {
1526        let visits = scan_covered(out, triangles, &mut used, s);
1527        ctx.tick(visits)?;
1528    } else {
1529        for t in triangles {
1530            out.append(t, &mut used, s, false, ctx)?;
1531        }
1532    }
1533    Ok(())
1534}
1535#[derive(Clone, Copy)]
1536pub(crate) enum Builder {
1537    Scan,
1538    Flex { min: usize, weight: f32, split: f32 },
1539    Spatial { min: usize, fill: f32 },
1540}
1541fn min_triangles(b: Builder, s: MeshletSettings) -> usize {
1542    match b {
1543        Builder::Scan => s.max_triangles,
1544        Builder::Flex { min, .. } | Builder::Spatial { min, .. } => min,
1545    }
1546}
1547fn execute(
1548    out: &mut Output<'_>,
1549    indices: &[u32],
1550    n: usize,
1551    p: Option<Positions<'_>>,
1552    s: MeshletSettings,
1553    b: Builder,
1554    ctx: &mut Context<'_>,
1555) -> Result<MeshletSizes, Error> {
1556    match b {
1557        Builder::Scan => scan(out, indices, n, s, ctx)?,
1558        Builder::Flex { min, weight, split } => {
1559            let p = p.expect("positions builder");
1560            if ctx.moderate {
1561                if weight == 0. {
1562                    flex::<false, true>(out, indices, p, s, min, weight, split, ctx)?;
1563                } else {
1564                    flex::<false, false>(out, indices, p, s, min, weight, split, ctx)?;
1565                }
1566            } else {
1567                flex::<true, false>(out, indices, p, s, min, weight, split, ctx)?;
1568            }
1569        }
1570        Builder::Spatial { min, fill } => crate::meshlet_spatial::spatial(
1571            out,
1572            indices,
1573            p.expect("positions builder"),
1574            s,
1575            min,
1576            fill,
1577            ctx,
1578        )?,
1579    }
1580    Ok(out.finish())
1581}
1582fn check(s: MeshletSettings, b: Builder) -> Result<(), Error> {
1583    match b {
1584        Builder::Scan => validate(s, s.max_triangles, 0., 0.),
1585        Builder::Flex { min, weight, split } => validate(s, min, weight, split),
1586        Builder::Spatial { min, fill } => {
1587            validate(s, min, 0., 0.)?;
1588            if !fill.is_finite() || fill < 0. {
1589                return Err(Error::InvalidParameter);
1590            }
1591            Ok(())
1592        }
1593    }
1594}
1595fn build(
1596    indices: &[u32],
1597    n: usize,
1598    p: Option<Positions<'_>>,
1599    s: MeshletSettings,
1600    b: Builder,
1601    workspace: &mut Workspace,
1602    trusted_moderate: Option<bool>,
1603) -> Result<Meshlets, Error> {
1604    let mut ctx = Context::new(workspace)?;
1605    check(s, b)?;
1606    ctx.topology(indices, n)?;
1607    if let Some(p) = p {
1608        if let Some(moderate) = trusted_moderate {
1609            ctx.moderate = moderate;
1610        } else {
1611            ctx.positions(p)?;
1612        }
1613    }
1614    let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1615    let mut result = Meshlets {
1616        meshlets: ctx.alloc(bound)?,
1617        vertices: ctx.alloc(indices.len())?,
1618        triangles: ctx.alloc(indices.len())?,
1619    };
1620    let sizes = execute(
1621        &mut Output {
1622            descriptors: &mut result.meshlets,
1623            vertices: &mut result.vertices,
1624            triangles: &mut result.triangles,
1625            current: Meshlet::default(),
1626            count: 0,
1627        },
1628        indices,
1629        n,
1630        p,
1631        s,
1632        b,
1633        &mut ctx,
1634    )?;
1635    result.meshlets.truncate(sizes.meshlets);
1636    result.vertices.truncate(sizes.vertices);
1637    result.triangles.truncate(sizes.triangles);
1638    Ok(result)
1639}
1640fn build_into(
1641    descriptors: &mut [Meshlet],
1642    vertices: &mut [u32],
1643    triangles: &mut [u8],
1644    indices: &[u32],
1645    n: usize,
1646    p: Option<Positions<'_>>,
1647    s: MeshletSettings,
1648    b: Builder,
1649    workspace: &mut Workspace,
1650) -> Result<MeshletSizes, Error> {
1651    let mut ctx = Context::new(workspace)?;
1652    check(s, b)?;
1653    let bound = build_meshlets_bound(indices.len(), s.max_vertices, min_triangles(b, s))?;
1654    if descriptors.len() < bound
1655        || vertices.len() < indices.len()
1656        || triangles.len() < indices.len()
1657    {
1658        return Err(Error::BufferTooSmall);
1659    }
1660    ctx.topology(indices, n)?;
1661    if let Some(p) = p {
1662        ctx.positions(p)?;
1663    }
1664    execute(
1665        &mut Output {
1666            descriptors,
1667            vertices,
1668            triangles,
1669            current: Meshlet::default(),
1670            count: 0,
1671        },
1672        indices,
1673        n,
1674        p,
1675        s,
1676        b,
1677        &mut ctx,
1678    )
1679}
1680/// `meshopt_buildMeshletsScan`: consume triangles in input order.
1681///
1682/// # Errors
1683/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1684/// `InvalidParameter` for unsupported meshlet limits; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1685pub fn build_meshlets_scan(
1686    indices: &[u32],
1687    vertex_count: usize,
1688    s: MeshletSettings,
1689    workspace: &mut Workspace,
1690) -> Result<Meshlets, Error> {
1691    build(
1692        indices,
1693        vertex_count,
1694        None,
1695        s,
1696        Builder::Scan,
1697        workspace,
1698        None,
1699    )
1700}
1701/// `meshopt_buildMeshlets`: connectivity and cone-aware meshlets.
1702///
1703/// # Errors
1704/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1705/// `InvalidParameter` for unsupported builder settings; `NumericalFailure` for non-finite geometry or calculations.
1706/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1707pub fn build_meshlets(
1708    indices: &[u32],
1709    p: Positions<'_>,
1710    s: MeshletSettings,
1711    cone_weight: f32,
1712    workspace: &mut Workspace,
1713) -> Result<Meshlets, Error> {
1714    build_meshlets_flex(indices, p, s, s.max_triangles, cone_weight, 0., workspace)
1715}
1716/// `meshopt_buildMeshletsFlex`: variable triangle counts and optional spatial splits.
1717///
1718/// # Errors
1719/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1720/// `InvalidParameter` for unsupported builder settings; `NumericalFailure` for non-finite geometry or calculations.
1721/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1722pub fn build_meshlets_flex(
1723    indices: &[u32],
1724    p: Positions<'_>,
1725    s: MeshletSettings,
1726    min_triangles: usize,
1727    cone_weight: f32,
1728    split_factor: f32,
1729    workspace: &mut Workspace,
1730) -> Result<Meshlets, Error> {
1731    build(
1732        indices,
1733        p.len(),
1734        Some(p),
1735        s,
1736        Builder::Flex {
1737            min: min_triangles,
1738            weight: cone_weight,
1739            split: split_factor,
1740        },
1741        workspace,
1742        None,
1743    )
1744}
1745#[cfg(feature = "clusterlod")]
1746pub(crate) fn build_meshlets_flex_validated(
1747    indices: &[u32],
1748    p: Positions<'_>,
1749    s: MeshletSettings,
1750    min_triangles: usize,
1751    cone_weight: f32,
1752    split_factor: f32,
1753    moderate: bool,
1754    workspace: &mut Workspace,
1755) -> Result<Meshlets, Error> {
1756    build(
1757        indices,
1758        p.len(),
1759        Some(p),
1760        s,
1761        Builder::Flex {
1762            min: min_triangles,
1763            weight: cone_weight,
1764            split: split_factor,
1765        },
1766        workspace,
1767        Some(moderate),
1768    )
1769}
1770/// `meshopt_buildMeshletsSpatial`: surface-area heuristic meshlets for ray tracing.
1771///
1772/// # Errors
1773/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
1774/// `InvalidParameter` for unsupported builder settings; `NumericalFailure` for non-finite geometry or calculations.
1775/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
1776pub fn build_meshlets_spatial(
1777    indices: &[u32],
1778    p: Positions<'_>,
1779    s: MeshletSettings,
1780    min_triangles: usize,
1781    fill_weight: f32,
1782    workspace: &mut Workspace,
1783) -> Result<Meshlets, Error> {
1784    build(
1785        indices,
1786        p.len(),
1787        Some(p),
1788        s,
1789        Builder::Spatial {
1790            min: min_triangles,
1791            fill: fill_weight,
1792        },
1793        workspace,
1794        None,
1795    )
1796}
1797#[cfg(feature = "clusterlod")]
1798pub(crate) fn build_meshlets_spatial_validated(
1799    indices: &[u32],
1800    p: Positions<'_>,
1801    s: MeshletSettings,
1802    min_triangles: usize,
1803    fill_weight: f32,
1804    moderate: bool,
1805    workspace: &mut Workspace,
1806) -> Result<Meshlets, Error> {
1807    build(
1808        indices,
1809        p.len(),
1810        Some(p),
1811        s,
1812        Builder::Spatial {
1813            min: min_triangles,
1814            fill: fill_weight,
1815        },
1816        workspace,
1817        Some(moderate),
1818    )
1819}
1820/// Caller-buffer scan builder; a late work-limit failure may modify output prefixes.
1821///
1822/// # Errors
1823/// Same errors as [`build_meshlets_scan`]. `BufferTooSmall` if any output buffer lacks capacity.
1824pub fn build_meshlets_scan_into(
1825    descriptors: &mut [Meshlet],
1826    vertices: &mut [u32],
1827    triangles: &mut [u8],
1828    indices: &[u32],
1829    vertex_count: usize,
1830    s: MeshletSettings,
1831    workspace: &mut Workspace,
1832) -> Result<MeshletSizes, Error> {
1833    build_into(
1834        descriptors,
1835        vertices,
1836        triangles,
1837        indices,
1838        vertex_count,
1839        None,
1840        s,
1841        Builder::Scan,
1842        workspace,
1843    )
1844}
1845/// Caller-buffer standard builder; a late failure may modify output prefixes.
1846///
1847/// # Errors
1848/// Same errors as [`build_meshlets`]. `BufferTooSmall` if any output buffer lacks capacity.
1849pub fn build_meshlets_into(
1850    descriptors: &mut [Meshlet],
1851    vertices: &mut [u32],
1852    triangles: &mut [u8],
1853    indices: &[u32],
1854    p: Positions<'_>,
1855    s: MeshletSettings,
1856    cone_weight: f32,
1857    workspace: &mut Workspace,
1858) -> Result<MeshletSizes, Error> {
1859    build_meshlets_flex_into(
1860        descriptors,
1861        vertices,
1862        triangles,
1863        indices,
1864        p,
1865        s,
1866        s.max_triangles,
1867        cone_weight,
1868        0.,
1869        workspace,
1870    )
1871}
1872/// Caller-buffer flexible builder; a late failure may modify output prefixes.
1873///
1874/// # Errors
1875/// Same errors as [`build_meshlets_flex`]. `BufferTooSmall` if any output buffer lacks capacity.
1876pub fn build_meshlets_flex_into(
1877    descriptors: &mut [Meshlet],
1878    vertices: &mut [u32],
1879    triangles: &mut [u8],
1880    indices: &[u32],
1881    p: Positions<'_>,
1882    s: MeshletSettings,
1883    min_triangles: usize,
1884    cone_weight: f32,
1885    split_factor: f32,
1886    workspace: &mut Workspace,
1887) -> Result<MeshletSizes, Error> {
1888    build_into(
1889        descriptors,
1890        vertices,
1891        triangles,
1892        indices,
1893        p.len(),
1894        Some(p),
1895        s,
1896        Builder::Flex {
1897            min: min_triangles,
1898            weight: cone_weight,
1899            split: split_factor,
1900        },
1901        workspace,
1902    )
1903}
1904/// Caller-buffer spatial builder; a late failure may modify output prefixes.
1905///
1906/// # Errors
1907/// Same errors as [`build_meshlets_spatial`]. `BufferTooSmall` if any output buffer lacks capacity.
1908pub fn build_meshlets_spatial_into(
1909    descriptors: &mut [Meshlet],
1910    vertices: &mut [u32],
1911    triangles: &mut [u8],
1912    indices: &[u32],
1913    p: Positions<'_>,
1914    s: MeshletSettings,
1915    min_triangles: usize,
1916    fill_weight: f32,
1917    workspace: &mut Workspace,
1918) -> Result<MeshletSizes, Error> {
1919    build_into(
1920        descriptors,
1921        vertices,
1922        triangles,
1923        indices,
1924        p.len(),
1925        Some(p),
1926        s,
1927        Builder::Spatial {
1928            min: min_triangles,
1929            fill: fill_weight,
1930        },
1931        workspace,
1932    )
1933}