Skip to main content

meshoptimizer_rs/
lod_quality.rs

1//! Sampled LOD surface quality, an extension not in C++ meshoptimizer.
2use crate::{
3    budget::Budget, workspace::Work, Error, LodChain, LodChainGeneric, Positions, Workspace,
4};
5use alloc::vec::Vec;
6
7type V = [f64; 3];
8
9/// A borrowed triangle surface. Only referenced vertices are measured/validated.
10#[derive(Clone, Copy, Debug)]
11#[non_exhaustive]
12pub struct LodQualityMeshGeneric<'a, I: crate::Index = u32> {
13    /// Triangle-list indices; at least one triangle is required.
14    pub indices: &'a [I],
15    /// Positions in the same world units as the reported distances.
16    pub positions: Positions<'a>,
17    /// Optional per-vertex normals, normalized before interpolation.
18    pub normals: Option<&'a [[f32; 3]]>,
19}
20impl<'a, I: crate::Index> LodQualityMeshGeneric<'a, I> {
21    /// Borrow a surface without normals. Set `normals` to compare shading normals.
22    pub fn new_generic(indices: &'a [I], positions: Positions<'a>) -> Self {
23        Self {
24            indices,
25            positions,
26            normals: None,
27        }
28    }
29}
30
31/// Deterministic sampling settings (not in C++ meshoptimizer).
32#[derive(Clone, Copy, Debug)]
33#[non_exhaustive]
34pub struct LodQualityOptions {
35    /// Interior samples per square world unit, default 1. Must be finite and
36    /// nonnegative. Each triangle gets `ceil(area * density)` samples, plus its
37    /// three corners (shared corners are repeated). Zero disables interiors.
38    /// Degenerate triangles have corners only. More than `u32::MAX` interior
39    /// samples on one triangle returns `SizeOverflow`; work limits apply first
40    /// to every visit that is actually attempted.
41    pub samples_per_unit_area: f64,
42}
43impl Default for LodQualityOptions {
44    fn default() -> Self {
45        Self {
46            samples_per_unit_area: 1.0,
47        }
48    }
49}
50
51/// Sampled distance statistics in world units.
52#[derive(Clone, Copy, Debug, Default, PartialEq)]
53#[non_exhaustive]
54pub struct LodDistance {
55    /// Largest sampled nearest-surface distance, a lower estimate of Hausdorff distance.
56    pub max: f64,
57    /// Root mean square over samples, with equal weight per sample.
58    pub rms: f64,
59    /// Number of samples, including repeated triangle corners.
60    pub samples: u64,
61}
62/// Shading-normal angular deviation in radians.
63#[derive(Clone, Copy, Debug, Default, PartialEq)]
64#[non_exhaustive]
65pub struct LodNormalDeviation {
66    /// Largest angle, in `[0, pi]`.
67    pub max: f64,
68    /// Arithmetic mean angle over samples in both directions.
69    pub mean: f64,
70}
71/// Quality of a level relative to the source; not in C++ meshoptimizer.
72#[derive(Clone, Copy, Debug, PartialEq)]
73#[non_exhaustive]
74pub struct LodQuality {
75    /// One-sided source-to-level measurements.
76    pub source_to_level: LodDistance,
77    /// One-sided level-to-source measurements.
78    pub level_to_source: LodDistance,
79    /// Maximum and pooled RMS across both directions.
80    pub symmetric: LodDistance,
81    /// Pooled normal angles, present when both surfaces supply normals.
82    pub normals: Option<LodNormalDeviation>,
83}
84
85/// Pinhole camera used to turn world-space deviation into switch distance.
86#[derive(Clone, Copy, Debug)]
87#[non_exhaustive]
88pub struct LodCamera {
89    /// Vertical field of view in radians, strictly between zero and pi.
90    /// All positive finite values below pi are valid, including subnormals.
91    pub vertical_fov: f64,
92    /// Positive viewport height in pixels.
93    pub viewport_height: f64,
94    /// Positive allowed projected deviation in pixels.
95    pub pixel_tolerance: f64,
96}
97impl LodCamera {
98    /// Construct and validate a camera.
99    /// # Errors
100    /// `InvalidParameter` for non-finite or out-of-domain parameters.
101    pub fn new(
102        vertical_fov: f64,
103        viewport_height: f64,
104        pixel_tolerance: f64,
105    ) -> Result<Self, Error> {
106        let camera = Self {
107            vertical_fov,
108            viewport_height,
109            pixel_tolerance,
110        };
111        camera.switch_distance(0.0)?;
112        Ok(camera)
113    }
114    /// Minimum camera-space depth in the pinhole model:
115    /// `deviation * viewport_height / (2 * tan(vertical_fov/2) * pixel_tolerance)`.
116    /// This is a depth threshold for a transverse displacement, not a raster
117    /// error guarantee. Use nearest mesh depth (or add a bounding radius when
118    /// measuring camera-to-center distance). Sampled error can miss extrema.
119    /// # Errors
120    /// `InvalidParameter` for invalid camera or negative/non-finite deviation;
121    /// `NumericalFailure` if the result overflows or a positive threshold
122    /// underflows to zero. A zero deviation always returns zero.
123    pub fn switch_distance(&self, deviation: f64) -> Result<f64, Error> {
124        if !self.vertical_fov.is_finite()
125            || self.vertical_fov <= 0.0
126            || self.vertical_fov >= core::f64::consts::PI
127            || !self.viewport_height.is_finite()
128            || self.viewport_height <= 0.0
129            || !self.pixel_tolerance.is_finite()
130            || self.pixel_tolerance <= 0.0
131            || !deviation.is_finite()
132            || deviation < 0.0
133        {
134            return Err(Error::InvalidParameter);
135        }
136        if deviation == 0.0 {
137            return Ok(0.0);
138        }
139        // Logs avoid overflow/underflow in intermediate products of valid inputs.
140        // For tiny angles, 2*tan(fov/2) rounds to fov; avoid halving a
141        // subnormal before taking its logarithm. The relative approximation
142        // error below this cutoff is smaller than f64 precision.
143        let log_scale = if self.vertical_fov < 1e-8 {
144            libm::log(self.vertical_fov)
145        } else {
146            libm::log(2.0) + libm::log(libm::tan(self.vertical_fov / 2.0))
147        };
148        let log = libm::log(deviation) + libm::log(self.viewport_height)
149            - log_scale
150            - libm::log(self.pixel_tolerance);
151        let distance = libm::exp(log);
152        if !distance.is_finite() || distance == 0.0 {
153            return Err(Error::NumericalFailure);
154        }
155        Ok(distance)
156    }
157}
158/// One chain level's quality and optional camera threshold.
159#[derive(Clone, Copy, Debug, PartialEq)]
160#[non_exhaustive]
161pub struct LodQualityLevel {
162    /// Measured directly against the source, never against the previous level.
163    pub quality: LodQuality,
164    /// Minimum depth for this level's sampled symmetric maximum.
165    pub switch_distance: Option<f64>,
166}
167
168/// Measure a source and a simplified surface, with a balanced triangle BVH.
169/// This extension is not in C++ meshoptimizer and does not change simplification.
170///
171/// Each triangle contributes its corners in index order, then area-scaled
172/// interiors. For interior ordinal `j` of `n`, let `r=sqrt((j+0.5)/n)` and
173/// `t=(reverse_bits(j)+0.5)/2^32`; barycentric weights are `(1-r, r*(1-t), r*t)`.
174/// Samples are streamed without allocating a sample array. Degenerate triangles
175/// use segment/point distances. Normals are normalized per vertex, interpolated
176/// at the sample and closest point, then normalized again. Nearest-point ties
177/// choose the lowest original target triangle ordinal. Both or neither surface
178/// must supply normals. Opposite normals give pi (no absolute dot product).
179///
180/// Maxima are sampled lower estimates, not certified continuous Hausdorff
181/// bounds. RMS/mean weight repeated corners and interiors equally, not area
182/// integrals. Higher density improves coverage but does not certify accuracy.
183/// Deterministic for identical inputs on the same build/target.
184///
185/// Work counts validation corners/triangles, BVH bounding/partition visits,
186/// samples and visited BVH nodes. Bounds and distances use `f64` arithmetic.
187/// Typical query cost is samples × log(triangles); overlapping/adversarial
188/// surfaces can visit more nodes, always bounded by `Limits::max_work`.
189/// Heap storage is fallible, charged before allocation, and released on return;
190/// existing workspace scratch is accounted for and may be evicted under pressure.
191/// # Errors
192/// `InvalidTopology`, `IndexOutOfBounds`, `InvalidParameter` (empty surface,
193/// density, normal length or zero normals), `NumericalFailure` (non-finite
194/// positions/normals or zero interpolated normal), or resource/size errors.
195pub fn measure_lod_quality_generic<I: crate::Index>(
196    source: LodQualityMeshGeneric<'_, I>,
197    level: LodQualityMeshGeneric<'_, I>,
198    options: &LodQualityOptions,
199    workspace: &mut Workspace,
200) -> Result<LodQuality, Error> {
201    let mut work = workspace.begin();
202    let result = measure(
203        source,
204        level,
205        options,
206        &mut Budget::new(workspace),
207        &mut work,
208    );
209    workspace.finish(&work);
210    result
211}
212
213/// Measure every `build_lod_chain` level directly against `source` using its
214/// unchanged vertex/normal buffers. Limits cover the entire call, including
215/// the returned metadata. An empty chain returns an empty vector.
216/// Not in C++ meshoptimizer. Thresholds follow measured errors and are not
217/// forced to increase: independent simplifications can have nonmonotone error.
218/// # Errors
219/// The errors of [`measure_lod_quality`] or [`LodCamera::switch_distance`].
220pub fn measure_lod_chain_quality_generic<I: crate::Index>(
221    source: LodQualityMeshGeneric<'_, I>,
222    chain: &LodChainGeneric<I>,
223    options: &LodQualityOptions,
224    camera: Option<LodCamera>,
225    workspace: &mut Workspace,
226) -> Result<Vec<LodQualityLevel>, Error> {
227    let mut work = workspace.begin();
228    let result = (|| {
229        validate_options(options)?;
230        if let Some(camera) = camera {
231            camera.switch_distance(0.0)?;
232        }
233        work.add(chain.levels.len())?;
234        let mut budget = Budget::new(workspace);
235        let mut out = budget.reserved(chain.levels.len())?;
236        for level in &chain.levels {
237            let mesh = LodQualityMeshGeneric {
238                indices: &level.indices,
239                ..source
240            };
241            let quality = measure(source, mesh, options, &mut budget, &mut work)?;
242            out.push(LodQualityLevel {
243                quality,
244                switch_distance: camera
245                    .map(|c| c.switch_distance(quality.symmetric.max))
246                    .transpose()?,
247            });
248        }
249        Ok(out)
250    })();
251    workspace.finish(&work);
252    result
253}
254
255fn validate_options(options: &LodQualityOptions) -> Result<(), Error> {
256    if !options.samples_per_unit_area.is_finite() || options.samples_per_unit_area < 0.0 {
257        return Err(Error::InvalidParameter);
258    }
259    Ok(())
260}
261fn position<I: crate::Index>(mesh: LodQualityMeshGeneric<'_, I>, index: I) -> Result<V, Error> {
262    let i = usize::try_from(index.to_u32()).map_err(|_| Error::SizeOverflow)?;
263    let p = mesh
264        .positions
265        .get(i)
266        .ok_or(Error::IndexOutOfBounds)?
267        .map(f64::from);
268    if !p.iter().all(|v| v.is_finite()) {
269        return Err(Error::NumericalFailure);
270    }
271    Ok(p)
272}
273fn unit(v: V) -> Result<V, Error> {
274    let d = libm::sqrt(dot(v, v));
275    if !d.is_finite() {
276        return Err(Error::NumericalFailure);
277    }
278    if d == 0.0 {
279        return Err(Error::InvalidParameter);
280    }
281    Ok(v.map(|x| x / d))
282}
283fn normal<I: crate::Index>(mesh: LodQualityMeshGeneric<'_, I>, index: I) -> Result<V, Error> {
284    match mesh.normals {
285        Some(normals) => unit(
286            normals[usize::try_from(index.to_u32()).map_err(|_| Error::SizeOverflow)?]
287                .map(f64::from),
288        ),
289        None => Ok([0.0; 3]),
290    }
291}
292fn validate<I: crate::Index>(
293    mesh: LodQualityMeshGeneric<'_, I>,
294    work: &mut Work,
295) -> Result<(), Error> {
296    if !mesh.indices.len().is_multiple_of(3) {
297        return Err(Error::InvalidTopology);
298    }
299    if mesh.indices.is_empty()
300        || mesh
301            .normals
302            .is_some_and(|n| n.len() != mesh.positions.len())
303    {
304        return Err(Error::InvalidParameter);
305    }
306    for &i in mesh.indices {
307        work.add(1)?;
308        position(mesh, i)?;
309        normal(mesh, i)?;
310    }
311    Ok(())
312}
313fn measure<I: crate::Index>(
314    source: LodQualityMeshGeneric<'_, I>,
315    level: LodQualityMeshGeneric<'_, I>,
316    options: &LodQualityOptions,
317    budget: &mut Budget<'_>,
318    work: &mut Work,
319) -> Result<LodQuality, Error> {
320    validate_options(options)?;
321    if source.normals.is_some() != level.normals.is_some() {
322        return Err(Error::InvalidParameter);
323    }
324    validate(source, work)?;
325    validate(level, work)?;
326    let a = direction::<I, false, 3, false>(source, level, options, budget, work, 0.0)?;
327    let b = direction::<I, false, 3, false>(level, source, options, budget, work, 0.0)?;
328    let samples = a.count.checked_add(b.count).ok_or(Error::SizeOverflow)?;
329    Ok(LodQuality {
330        source_to_level: a.distance(),
331        level_to_source: b.distance(),
332        symmetric: LodDistance {
333            max: libm::sqrt(a.max.max(b.max)),
334            rms: libm::sqrt((a.sum + b.sum) / samples as f64),
335            samples,
336        },
337        normals: source.normals.map(|_| LodNormalDeviation {
338            max: a.angle_max.max(b.angle_max),
339            mean: (a.angle_sum + b.angle_sum) / samples as f64,
340        }),
341    })
342}
343// The builder consumes only the symmetric maximum. Keep the public statistics
344// path exact, including nearest-triangle ties, RMS and shading normals.
345// The private floor is already retained by the builder: return the greater of
346// that floor and the sampled maximum without querying irrelevant distances.
347#[cfg(feature = "clusterlod")]
348pub(crate) fn measure_max(
349    source: LodQualityMesh<'_>,
350    level: LodQualityMesh<'_>,
351    options: &LodQualityOptions,
352    floor: f32,
353    workspace: &mut Workspace,
354) -> Result<f64, Error> {
355    let mut work = workspace.begin();
356    let result = (|| {
357        validate_options(options)?;
358        if !floor.is_finite() || floor < 0.0 {
359            return Err(Error::InvalidParameter);
360        }
361        // The caller already retains this floor. Its square is exact in f64
362        // for every finite f32, so queries need only find samples above it.
363        let floor = if floor == 0.0 { 0.0 } else { f64::from(floor) };
364        let cutoff = floor * floor;
365        let source: LodQualityMeshGeneric<'_, u32> = source.into();
366        let level: LodQualityMeshGeneric<'_, u32> = level.into();
367        validate(source, &mut work)?;
368        validate(level, &mut work)?;
369        let mut budget = Budget::new(workspace);
370        let a = direction::<u32, true, 0, false>(
371            source,
372            level,
373            options,
374            &mut budget,
375            &mut work,
376            cutoff,
377        )?;
378        let b = direction::<u32, true, 0, false>(
379            level,
380            source,
381            options,
382            &mut budget,
383            &mut work,
384            a.max,
385        )?;
386        // Avoid a sqrt round trip when no sample exceeds the existing floor.
387        Ok(if b.max == cutoff {
388            floor
389        } else {
390            libm::sqrt(b.max)
391        })
392    })();
393    workspace.finish(&work);
394    result
395}
396
397// Both maxima use the same original sample stream and exact nearest queries.
398// Unlike the public statistics path, undefined interpolated normals contribute
399// the maximum chord (two) rather than failing a valid geometric build.
400// Returns geometric distance and unit-normal chord maxima. Chords are exactly
401// 2*sin(angle/2); compare their squares without per-sample trigonometry.
402#[cfg(feature = "clusterlod")]
403pub(crate) fn measure_normal_max(
404    source: LodQualityMesh<'_>,
405    level: LodQualityMesh<'_>,
406    options: &LodQualityOptions,
407    workspace: &mut Workspace,
408) -> Result<(f64, f64), Error> {
409    let mut work = workspace.begin();
410    let result = (|| {
411        validate_options(options)?;
412        if source.normals.is_none() || level.normals.is_none() {
413            return Err(Error::InvalidParameter);
414        }
415        let source: LodQualityMeshGeneric<'_, u32> = source.into();
416        let level: LodQualityMeshGeneric<'_, u32> = level.into();
417        validate(source, &mut work)?;
418        validate(level, &mut work)?;
419        let mut budget = Budget::new(workspace);
420        let a =
421            direction::<u32, false, 3, true>(source, level, options, &mut budget, &mut work, 0.0)?;
422        let b =
423            direction::<u32, false, 3, true>(level, source, options, &mut budget, &mut work, 0.0)?;
424        Ok((
425            libm::sqrt(a.max.max(b.max)),
426            libm::sqrt(a.normal_chord_squared_max.max(b.normal_chord_squared_max)),
427        ))
428    })();
429    workspace.finish(&work);
430    result
431}
432
433fn sub(a: V, b: V) -> V {
434    core::array::from_fn(|k| a[k] - b[k])
435}
436fn dot(a: V, b: V) -> f64 {
437    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
438}
439fn cross(a: V, b: V) -> V {
440    [
441        a[1] * b[2] - a[2] * b[1],
442        a[2] * b[0] - a[0] * b[2],
443        a[0] * b[1] - a[1] * b[0],
444    ]
445}
446fn blend(p: [V; 3], w: V) -> V {
447    core::array::from_fn(|k| p[0][k] * w[0] + p[1][k] * w[1] + p[2][k] * w[2])
448}
449#[derive(Clone, Copy)]
450// Distance-only records omit unused normals; full statistics retain all three.
451struct Triangle<const NORMALS: usize = 3> {
452    p: [V; 3],
453    n: [V; NORMALS],
454    id: usize,
455}
456impl<const NORMALS: usize> Triangle<NORMALS> {
457    fn read<I: crate::Index>(mesh: LodQualityMeshGeneric<'_, I>, i: usize) -> Result<Self, Error> {
458        let ix = &mesh.indices[i * 3..i * 3 + 3];
459        let mut triangle = Self {
460            p: [
461                position(mesh, ix[0])?,
462                position(mesh, ix[1])?,
463                position(mesh, ix[2])?,
464            ],
465            n: [[0.0; 3]; NORMALS],
466            id: i,
467        };
468        for (value, &index) in triangle.n.iter_mut().zip(ix) {
469            *value = normal(mesh, index)?;
470        }
471        Ok(triangle)
472    }
473    fn normals(&self) -> [V; 3] {
474        let mut normals = [[0.0; 3]; 3];
475        for (to, &from) in normals.iter_mut().zip(&self.n) {
476            *to = from;
477        }
478        normals
479    }
480    fn center(&self, axis: usize) -> f64 {
481        self.p[0][axis] + self.p[1][axis] + self.p[2][axis]
482    }
483}
484#[derive(Clone, Copy)]
485struct Node {
486    lo: V,
487    hi: V,
488    left: usize,
489    right: usize,
490}
491struct Tree<const NORMALS: usize = 3> {
492    triangles: Vec<Triangle<NORMALS>>,
493    nodes: Vec<Node>,
494}
495impl<const NORMALS: usize> Tree<NORMALS> {
496    fn build<I: crate::Index>(
497        mesh: LodQualityMeshGeneric<'_, I>,
498        budget: &mut Budget<'_>,
499        work: &mut Work,
500    ) -> Result<Self, Error> {
501        let n = mesh.indices.len() / 3;
502        work.add(n)?; // initialization is charged before reserving/reading records
503        let mut triangles = budget.reserved(n)?;
504        for i in 0..n {
505            triangles.push(Triangle::<NORMALS>::read(mesh, i)?);
506        }
507        let count = n
508            .checked_mul(2)
509            .and_then(|n| n.checked_sub(1))
510            .ok_or(Error::SizeOverflow)?;
511        work.add(count)?;
512        let nodes = budget.reserved(count)?;
513        let mut tree = Self { triangles, nodes };
514        tree.build_range(0, n, work)?;
515        Ok(tree)
516    }
517    fn build_range(&mut self, start: usize, end: usize, work: &mut Work) -> Result<usize, Error> {
518        let mut lo = [f64::INFINITY; 3];
519        let mut hi = [f64::NEG_INFINITY; 3];
520        for t in &self.triangles[start..end] {
521            work.add(1)?;
522            for p in t.p {
523                for k in 0..3 {
524                    lo[k] = lo[k].min(p[k]);
525                    hi[k] = hi[k].max(p[k]);
526                }
527            }
528        }
529        let id = self.nodes.len();
530        self.nodes.push(Node {
531            lo,
532            hi,
533            left: start,
534            right: usize::MAX,
535        });
536        if end - start > 1 {
537            let axis = (0..3)
538                .max_by(|&a, &b| (hi[a] - lo[a]).total_cmp(&(hi[b] - lo[b])))
539                .unwrap_or(0);
540            let mid = start + (end - start) / 2;
541            select(&mut self.triangles[start..end], mid - start, axis, work)?;
542            let left = self.build_range(start, mid, work)?;
543            let right = self.build_range(mid, end, work)?;
544            self.nodes[id].left = left;
545            self.nodes[id].right = right;
546        }
547        Ok(id)
548    }
549    fn query<const MAX_ONLY: bool>(
550        &self,
551        id: usize,
552        p: V,
553        best: &mut Hit,
554        work: &mut Work,
555        cutoff: f64,
556    ) -> Result<(), Error> {
557        // A witnessed distance below the running maximum cannot raise it.
558        // Otherwise finish the exact nearest query with the original arithmetic.
559        if MAX_ONLY && best.distance <= cutoff {
560            return Ok(());
561        }
562        work.add(1)?;
563        let n = self.nodes[id];
564        if box_distance(n, p) > best.distance {
565            return Ok(());
566        }
567        if n.right == usize::MAX {
568            let t = self.triangles[n.left];
569            let (distance, weights) = closest(t.p, p);
570            if distance < best.distance || (distance == best.distance && t.id < best.id) {
571                *best = Hit {
572                    distance,
573                    weights,
574                    id: t.id,
575                    normals: t.normals(),
576                    triangle: n.left,
577                };
578            }
579        } else {
580            let (a, b) =
581                if box_distance(self.nodes[n.left], p) <= box_distance(self.nodes[n.right], p) {
582                    (n.left, n.right)
583                } else {
584                    (n.right, n.left)
585                };
586            self.query::<MAX_ONLY>(a, p, best, work, cutoff)?;
587            self.query::<MAX_ONLY>(b, p, best, work, cutoff)?;
588        }
589        Ok(())
590    }
591}
592// Metered median partition. A bounded number of quickselect passes falls back
593// to heapsort, preventing adversarial quadratic build work. No hidden sort scans.
594fn select<const NORMALS: usize>(
595    a: &mut [Triangle<NORMALS>],
596    mid: usize,
597    axis: usize,
598    work: &mut Work,
599) -> Result<(), Error> {
600    let key = |t: Triangle<NORMALS>| (t.center(axis), t.id);
601    let cmp = |a: Triangle<NORMALS>, b: Triangle<NORMALS>| {
602        key(a).0.total_cmp(&key(b).0).then(a.id.cmp(&b.id))
603    };
604    let mut lo = 0;
605    let mut hi = a.len();
606    let mut passes = 2 * (usize::BITS - a.len().leading_zeros());
607    while hi - lo > 1 {
608        if passes == 0 {
609            heap_sort(&mut a[lo..hi], cmp, work)?;
610            break;
611        }
612        passes -= 1;
613        let pivot = a[lo + (hi - lo) / 2];
614        let mut store = lo;
615        a.swap(lo + (hi - lo) / 2, hi - 1);
616        for i in lo..hi - 1 {
617            work.add(1)?;
618            if cmp(a[i], pivot).is_lt() {
619                a.swap(i, store);
620                store += 1;
621            }
622        }
623        a.swap(store, hi - 1);
624        if store == mid {
625            break;
626        }
627        if store < mid {
628            lo = store + 1;
629        } else {
630            hi = store;
631        }
632    }
633    Ok(())
634}
635fn heap_sort<const NORMALS: usize>(
636    a: &mut [Triangle<NORMALS>],
637    cmp: impl Fn(Triangle<NORMALS>, Triangle<NORMALS>) -> core::cmp::Ordering + Copy,
638    work: &mut Work,
639) -> Result<(), Error> {
640    fn sift<const INNER_NORMALS: usize>(
641        a: &mut [Triangle<INNER_NORMALS>],
642        mut root: usize,
643        end: usize,
644        cmp: impl Fn(Triangle<INNER_NORMALS>, Triangle<INNER_NORMALS>) -> core::cmp::Ordering + Copy,
645        work: &mut Work,
646    ) -> Result<(), Error> {
647        while root < end / 2 {
648            let mut child = root * 2 + 1;
649            work.add(1)?;
650            if child + 1 < end && cmp(a[child], a[child + 1]).is_lt() {
651                child += 1;
652            }
653            if !cmp(a[root], a[child]).is_lt() {
654                break;
655            }
656            a.swap(root, child);
657            root = child;
658        }
659        Ok(())
660    }
661    for root in (0..a.len() / 2).rev() {
662        sift(a, root, a.len(), cmp, work)?;
663    }
664    for end in (1..a.len()).rev() {
665        a.swap(0, end);
666        sift(a, 0, end, cmp, work)?;
667    }
668    Ok(())
669}
670fn box_distance(n: Node, p: V) -> f64 {
671    (0..3)
672        .map(|k| (n.lo[k] - p[k]).max(0.0).max(p[k] - n.hi[k]))
673        .map(|d| d * d)
674        .sum()
675}
676struct Hit {
677    triangle: usize,
678    distance: f64,
679    weights: V,
680    id: usize,
681    normals: [V; 3],
682}
683// The minimum is on an edge or the orthogonal projection onto the face.
684// Edge fallback also handles collinear and point triangles without division by zero.
685fn closest(t: [V; 3], p: V) -> (f64, V) {
686    let mut best = (f64::INFINITY, [1.0, 0.0, 0.0]);
687    for (a, b) in [(0, 1), (1, 2), (2, 0)] {
688        let edge = sub(t[b], t[a]);
689        let len = dot(edge, edge);
690        let s = if len > 0.0 {
691            (dot(sub(p, t[a]), edge) / len).clamp(0.0, 1.0)
692        } else {
693            0.0
694        };
695        let mut w = [0.0; 3];
696        w[a] = 1.0 - s;
697        w[b] = s;
698        // Measure the residual directly, rather than reconstructing a world
699        // point from rounded weights (which can erase small offsets on long
700        // segments). Endpoints use their direct distance; interiors use the
701        // perpendicular distance to the line, relative to the nearer endpoint.
702        let d = if s == 0.0 {
703            let delta = sub(p, t[a]);
704            dot(delta, delta)
705        } else if s == 1.0 {
706            let delta = sub(p, t[b]);
707            dot(delta, delta)
708        } else {
709            let offset = sub(p, if s <= 0.5 { t[a] } else { t[b] });
710            let perpendicular = cross(offset, edge);
711            dot(perpendicular, perpendicular) / len
712        };
713        if d < best.0 {
714            best = (d, w);
715        }
716    }
717    let ab = sub(t[1], t[0]);
718    let ac = sub(t[2], t[0]);
719    let n = cross(ab, ac);
720    let nn = dot(n, n);
721    if nn > 0.0 {
722        let ap = sub(p, t[0]);
723        let v = dot(cross(ap, ac), n) / nn;
724        let w = dot(cross(ab, ap), n) / nn;
725        if v >= 0.0 && w >= 0.0 && v + w <= 1.0 {
726            let h = dot(ap, n);
727            let d = h * h / nn;
728            if d < best.0 {
729                best = (d, [1.0 - v - w, v, w]);
730            }
731        }
732    }
733    best
734}
735// The face candidate is also tested by `closest`. A successful candidate is
736// sufficient to bound this sample below the running maximum; a failed witness
737// leaves the exact tree query unchanged. Degenerate/outside faces use edges.
738fn witness(t: [V; 3], p: V, cutoff: f64) -> Option<(f64, V)> {
739    let ab = sub(t[1], t[0]);
740    let ac = sub(t[2], t[0]);
741    let n = cross(ab, ac);
742    let nn = dot(n, n);
743    if nn > 0.0 {
744        let ap = sub(p, t[0]);
745        let v = dot(cross(ap, ac), n) / nn;
746        let w = dot(cross(ab, ap), n) / nn;
747        if v >= 0.0 && w >= 0.0 && v + w <= 1.0 {
748            let h = dot(ap, n);
749            let d = h * h / nn;
750            return if d <= cutoff {
751                Some((d, [1.0 - v - w, v, w]))
752            } else {
753                None
754            };
755        }
756    }
757    let (d, weights) = closest(t, p);
758    if d <= cutoff {
759        Some((d, weights))
760    } else {
761        None
762    }
763}
764#[derive(Default)]
765struct Stats {
766    witness: Option<usize>,
767    count: u64,
768    max: f64,
769    sum: f64,
770    angle_max: f64,
771    normal_chord_squared_max: f64,
772    angle_sum: f64,
773}
774impl Stats {
775    fn distance(&self) -> LodDistance {
776        LodDistance {
777            max: libm::sqrt(self.max),
778            rms: libm::sqrt(self.sum / self.count as f64),
779            samples: self.count,
780        }
781    }
782    fn sample<const MAX_ONLY: bool, const NORMALS: usize, const NORMAL_MAX: bool>(
783        &mut self,
784        t: Triangle<NORMALS>,
785        weights: V,
786        tree: &Tree<NORMALS>,
787        normals: bool,
788        work: &mut Work,
789    ) -> Result<(), Error> {
790        work.add(1)?;
791        let p = blend(t.p, weights);
792        let mut hit = Hit {
793            triangle: usize::MAX,
794            distance: f64::INFINITY,
795            weights: [0.0; 3],
796            id: usize::MAX,
797            normals: [[0.0; 3]; 3],
798        };
799        // Nearby samples often share a useful target triangle. Its distance is
800        // an upper bound, so a successful witness needs no BVH traversal.
801        if MAX_ONLY {
802            if let Some(i) = self.witness {
803                work.add(1)?;
804                let t = tree.triangles[i];
805                if let Some((distance, weights)) = witness(t.p, p, self.max) {
806                    hit = Hit {
807                        triangle: i,
808                        distance,
809                        weights,
810                        id: t.id,
811                        normals: t.normals(),
812                    };
813                }
814            }
815        }
816        tree.query::<MAX_ONLY>(0, p, &mut hit, work, self.max)?;
817        if MAX_ONLY && hit.triangle != usize::MAX {
818            self.witness = Some(hit.triangle);
819        }
820        self.count = self.count.checked_add(1).ok_or(Error::SizeOverflow)?;
821        self.max = self.max.max(hit.distance);
822        if !MAX_ONLY && !NORMAL_MAX {
823            self.sum += hit.distance;
824        }
825        if !MAX_ONLY && normals {
826            let a = unit(blend(t.normals(), weights));
827            let b = unit(blend(hit.normals, hit.weights));
828            if NORMAL_MAX {
829                let squared = match (a, b) {
830                    (Ok(a), Ok(b)) => {
831                        let delta = sub(a, b);
832                        dot(delta, delta).clamp(0.0, 4.0)
833                    }
834                    // Undefined interpolants mean the largest unit-normal chord.
835                    _ => 4.0,
836                };
837                self.normal_chord_squared_max = self.normal_chord_squared_max.max(squared);
838            } else {
839                let (a, b) = (
840                    a.map_err(|_| Error::NumericalFailure)?,
841                    b.map_err(|_| Error::NumericalFailure)?,
842                );
843                let angle = libm::atan2(
844                    libm::sqrt(dot(cross(a, b), cross(a, b))),
845                    dot(a, b).clamp(-1.0, 1.0),
846                );
847                self.angle_max = self.angle_max.max(angle);
848                self.angle_sum += angle;
849            }
850        }
851        Ok(())
852    }
853}
854fn direction<
855    I: crate::Index,
856    const MAX_ONLY: bool,
857    const NORMALS: usize,
858    const NORMAL_MAX: bool,
859>(
860    source: LodQualityMeshGeneric<'_, I>,
861    target: LodQualityMeshGeneric<'_, I>,
862    options: &LodQualityOptions,
863    budget: &mut Budget<'_>,
864    work: &mut Work,
865    initial_max: f64,
866) -> Result<Stats, Error> {
867    let tree = Tree::<NORMALS>::build(target, budget, work)?;
868    // Always release local storage accounting, including after a failed query.
869    let mut corners = Vec::<u64>::new();
870    let result = (|| {
871        if MAX_ONLY || NORMAL_MAX {
872            let words = source.positions.len().div_ceil(64);
873            work.add(words)?;
874            corners = budget.reserved(words)?;
875            corners.resize(words, 0);
876        }
877        let mut stats = Stats {
878            max: initial_max,
879            ..Stats::default()
880        };
881        for i in 0..source.indices.len() / 3 {
882            work.add(1)?;
883            let t = Triangle::<NORMALS>::read(source, i)?;
884            let n = cross(sub(t.p[1], t.p[0]), sub(t.p[2], t.p[0]));
885            let count = libm::ceil(0.5 * libm::sqrt(dot(n, n)) * options.samples_per_unit_area);
886            if !count.is_finite() || count > f64::from(u32::MAX) {
887                return Err(Error::SizeOverflow);
888            }
889            // Finite, nonnegative and checked <= u32::MAX: conversion cannot wrap.
890            let count = count as u32;
891            for (corner, w) in [[1., 0., 0.], [0., 1., 0.], [0., 0., 1.]]
892                .into_iter()
893                .enumerate()
894            {
895                let vertex = source.indices[i * 3 + corner].to_u32() as usize;
896                let mask = 1u64 << (vertex % 64);
897                if (MAX_ONLY || NORMAL_MAX) && corners[vertex / 64] & mask != 0 {
898                    // This corner is already bounded by an earlier maximum.
899                    // Keep the sample visit/count; its distance cannot raise max.
900                    work.add(1)?;
901                    stats.count = stats.count.checked_add(1).ok_or(Error::SizeOverflow)?;
902                } else {
903                    stats.sample::<MAX_ONLY, NORMALS, NORMAL_MAX>(
904                        t,
905                        w,
906                        &tree,
907                        source.normals.is_some(),
908                        work,
909                    )?;
910                    if MAX_ONLY || NORMAL_MAX {
911                        corners[vertex / 64] |= mask;
912                    }
913                }
914            }
915            for j in 0..count {
916                let r = libm::sqrt((f64::from(j) + 0.5) / f64::from(count));
917                let t2 = (f64::from(j.reverse_bits()) + 0.5) / 4294967296.0;
918                stats.sample::<MAX_ONLY, NORMALS, NORMAL_MAX>(
919                    t,
920                    [1.0 - r, r * (1.0 - t2), r * t2],
921                    &tree,
922                    source.normals.is_some(),
923                    work,
924                )?;
925            }
926        }
927        Ok(stats)
928    })();
929    if MAX_ONLY || NORMAL_MAX {
930        budget.release(corners);
931    }
932    budget.release(tree.nodes);
933    budget.release(tree.triangles);
934    result
935}
936
937/// The source-compatible u32 entry point; see [`measure_lod_quality_generic`] for selectable index widths.
938#[inline]
939pub fn measure_lod_quality(
940    source: LodQualityMesh<'_>,
941    level: LodQualityMesh<'_>,
942    options: &LodQualityOptions,
943    workspace: &mut Workspace,
944) -> Result<LodQuality, Error> {
945    measure_lod_quality_generic::<u32>(source.into(), level.into(), options, workspace)
946}
947
948/// The source-compatible u32 entry point; see [`measure_lod_chain_quality_generic`] for selectable index widths.
949#[inline]
950pub fn measure_lod_chain_quality(
951    source: LodQualityMesh<'_>,
952    chain: &LodChain,
953    options: &LodQualityOptions,
954    camera: Option<LodCamera>,
955    workspace: &mut Workspace,
956) -> Result<Vec<LodQualityLevel>, Error> {
957    let source: LodQualityMeshGeneric<'_, u32> = source.into();
958    let mut work = workspace.begin();
959    let result = (|| {
960        validate_options(options)?;
961        if let Some(camera) = camera {
962            camera.switch_distance(0.0)?;
963        }
964        work.add(chain.levels.len())?;
965        let mut budget = Budget::new(workspace);
966        let mut out = budget.reserved(chain.levels.len())?;
967        for level in &chain.levels {
968            let mesh = LodQualityMeshGeneric {
969                indices: &level.indices,
970                ..source
971            };
972            let quality = measure(source, mesh, options, &mut budget, &mut work)?;
973            out.push(LodQualityLevel {
974                quality,
975                switch_distance: camera
976                    .map(|c| c.switch_distance(quality.symmetric.max))
977                    .transpose()?,
978            });
979        }
980        Ok(out)
981    })();
982    workspace.finish(&work);
983    result
984}
985
986impl<'a> LodQualityMesh<'a> {
987    /// Source-compatible u32 operation.
988    #[inline]
989    pub fn new(indices: &'a [u32], positions: Positions<'a>) -> Self {
990        LodQualityMeshGeneric::new_generic(indices, positions).into()
991    }
992}
993
994/// The source-compatible u32 form of [`LodQualityMeshGeneric`].
995/// A borrowed triangle surface. Only referenced vertices are measured/validated.
996#[derive(Clone, Copy, Debug)]
997#[non_exhaustive]
998pub struct LodQualityMesh<'a> {
999    /// Triangle-list indices; at least one triangle is required.
1000    pub indices: &'a [u32],
1001    /// Positions in the same world units as the reported distances.
1002    pub positions: Positions<'a>,
1003    /// Optional per-vertex normals, normalized before interpolation.
1004    pub normals: Option<&'a [[f32; 3]]>,
1005}
1006impl<'a> From<LodQualityMeshGeneric<'a, u32>> for LodQualityMesh<'a> {
1007    #[inline]
1008    fn from(value: LodQualityMeshGeneric<'a, u32>) -> Self {
1009        Self {
1010            indices: value.indices,
1011            positions: value.positions,
1012            normals: value.normals,
1013        }
1014    }
1015}
1016
1017impl<'a> From<LodQualityMesh<'a>> for LodQualityMeshGeneric<'a, u32> {
1018    #[inline]
1019    fn from(value: LodQualityMesh<'a>) -> Self {
1020        Self {
1021            indices: value.indices,
1022            positions: value.positions,
1023            normals: value.normals,
1024        }
1025    }
1026}
1027
1028#[cfg(all(test, feature = "clusterlod"))]
1029mod maximum_tests {
1030    use super::*;
1031
1032    #[test]
1033    fn maximum_only_matches_uneven_surfaces() {
1034        let mut state = 17u32;
1035        let mut random = || {
1036            state = state.wrapping_mul(1664525).wrapping_add(1013904223);
1037            (state >> 8) as f32 / 16777216.0
1038        };
1039        for count in [1, 3, 4, 5, 8, 9, 17] {
1040            let indices: Vec<u32> = (0..count * 3).collect();
1041            for scale in [1e-10, 1., 1e10] {
1042                for _ in 0..16 {
1043                    let source: Vec<[f32; 3]> = (0..count * 3)
1044                        .map(|_| core::array::from_fn(|_| random() * scale))
1045                        .collect();
1046                    let target: Vec<[f32; 3]> = source
1047                        .iter()
1048                        .map(|p| core::array::from_fn(|k| p[k] + (random() - 0.5) * scale))
1049                        .collect();
1050                    let options = LodQualityOptions {
1051                        samples_per_unit_area: 4. / f64::from(scale).powi(2),
1052                    };
1053                    let a = LodQualityMesh::new(&indices, Positions::from_packed(&source));
1054                    let b = LodQualityMesh::new(&indices, Positions::from_packed(&target));
1055                    let full = measure_lod_quality(a, b, &options, &mut Workspace::default())
1056                        .expect("full measurement");
1057                    let rounded = full.symmetric.max as f32;
1058                    for floor in [
1059                        0.0,
1060                        f32::from_bits(rounded.to_bits().saturating_sub(1)),
1061                        rounded,
1062                        f32::from_bits(rounded.to_bits() + 1),
1063                    ] {
1064                        let maximum = measure_max(a, b, &options, floor, &mut Workspace::default())
1065                            .expect("maximum measurement");
1066                        assert_eq!(
1067                            maximum.to_bits(),
1068                            full.symmetric.max.max(f64::from(floor)).to_bits()
1069                        );
1070                    }
1071                }
1072            }
1073        }
1074    }
1075
1076    #[test]
1077    fn maximum_only_matches_full_queries() {
1078        // Overlapping faces, repeated corners and degenerate segments exercise
1079        // witness exits and exact queries that must raise the running maximum.
1080        let indices = [0, 1, 2, 2, 1, 0, 0, 0, 3, 3, 4, 5];
1081        let source = [
1082            [0., 0., 0.],
1083            [1., 0., 0.],
1084            [0., 1., 0.],
1085            [0., 0., 2.],
1086            [1., 0., 2.],
1087            [0., 1., 2.],
1088        ];
1089        for offset in [0., 1e-12, 0.125, 4.] {
1090            let target = source.map(|p| [p[0], p[1], p[2] + offset]);
1091            for density in [0., 1., 100.] {
1092                let options = LodQualityOptions {
1093                    samples_per_unit_area: density,
1094                };
1095                let a = LodQualityMesh::new(&indices, Positions::from_packed(&source));
1096                let b = LodQualityMesh::new(&indices, Positions::from_packed(&target));
1097                let full = measure_lod_quality(a, b, &options, &mut Workspace::default())
1098                    .expect("full measurement");
1099                for floor in [0.0, f32::MIN_POSITIVE, 0.03125, 1.0, f32::MAX] {
1100                    let maximum = measure_max(a, b, &options, floor, &mut Workspace::default())
1101                        .expect("maximum measurement");
1102                    assert_eq!(
1103                        maximum.to_bits(),
1104                        full.symmetric.max.max(f64::from(floor)).to_bits()
1105                    );
1106                }
1107            }
1108        }
1109    }
1110}