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>(source, level, options, budget, work, 0.0)?;
327    let b = direction::<I, false, 3>(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#[cfg(feature = "clusterlod")]
346pub(crate) fn measure_max(
347    source: LodQualityMesh<'_>,
348    level: LodQualityMesh<'_>,
349    options: &LodQualityOptions,
350    workspace: &mut Workspace,
351) -> Result<f64, Error> {
352    let mut work = workspace.begin();
353    let result = (|| {
354        validate_options(options)?;
355        let source: LodQualityMeshGeneric<'_, u32> = source.into();
356        let level: LodQualityMeshGeneric<'_, u32> = level.into();
357        validate(source, &mut work)?;
358        validate(level, &mut work)?;
359        let mut budget = Budget::new(workspace);
360        let a = direction::<u32, true, 0>(source, level, options, &mut budget, &mut work, 0.0)?;
361        let b = direction::<u32, true, 0>(level, source, options, &mut budget, &mut work, a.max)?;
362        Ok(libm::sqrt(b.max))
363    })();
364    workspace.finish(&work);
365    result
366}
367
368fn sub(a: V, b: V) -> V {
369    core::array::from_fn(|k| a[k] - b[k])
370}
371fn dot(a: V, b: V) -> f64 {
372    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
373}
374fn cross(a: V, b: V) -> V {
375    [
376        a[1] * b[2] - a[2] * b[1],
377        a[2] * b[0] - a[0] * b[2],
378        a[0] * b[1] - a[1] * b[0],
379    ]
380}
381fn blend(p: [V; 3], w: V) -> V {
382    core::array::from_fn(|k| p[0][k] * w[0] + p[1][k] * w[1] + p[2][k] * w[2])
383}
384#[derive(Clone, Copy)]
385// Distance-only records omit unused normals; full statistics retain all three.
386struct Triangle<const NORMALS: usize = 3> {
387    p: [V; 3],
388    n: [V; NORMALS],
389    id: usize,
390}
391impl<const NORMALS: usize> Triangle<NORMALS> {
392    fn read<I: crate::Index>(mesh: LodQualityMeshGeneric<'_, I>, i: usize) -> Result<Self, Error> {
393        let ix = &mesh.indices[i * 3..i * 3 + 3];
394        let mut triangle = Self {
395            p: [
396                position(mesh, ix[0])?,
397                position(mesh, ix[1])?,
398                position(mesh, ix[2])?,
399            ],
400            n: [[0.0; 3]; NORMALS],
401            id: i,
402        };
403        for (value, &index) in triangle.n.iter_mut().zip(ix) {
404            *value = normal(mesh, index)?;
405        }
406        Ok(triangle)
407    }
408    fn normals(&self) -> [V; 3] {
409        let mut normals = [[0.0; 3]; 3];
410        for (to, &from) in normals.iter_mut().zip(&self.n) {
411            *to = from;
412        }
413        normals
414    }
415    fn center(&self, axis: usize) -> f64 {
416        self.p[0][axis] + self.p[1][axis] + self.p[2][axis]
417    }
418}
419#[derive(Clone, Copy)]
420struct Node {
421    lo: V,
422    hi: V,
423    left: usize,
424    right: usize,
425}
426struct Tree<const NORMALS: usize = 3> {
427    triangles: Vec<Triangle<NORMALS>>,
428    nodes: Vec<Node>,
429}
430impl<const NORMALS: usize> Tree<NORMALS> {
431    fn build<I: crate::Index>(
432        mesh: LodQualityMeshGeneric<'_, I>,
433        budget: &mut Budget<'_>,
434        work: &mut Work,
435    ) -> Result<Self, Error> {
436        let n = mesh.indices.len() / 3;
437        work.add(n)?; // initialization is charged before reserving/reading records
438        let mut triangles = budget.reserved(n)?;
439        for i in 0..n {
440            triangles.push(Triangle::<NORMALS>::read(mesh, i)?);
441        }
442        let count = n
443            .checked_mul(2)
444            .and_then(|n| n.checked_sub(1))
445            .ok_or(Error::SizeOverflow)?;
446        work.add(count)?;
447        let nodes = budget.reserved(count)?;
448        let mut tree = Self { triangles, nodes };
449        tree.build_range(0, n, work)?;
450        Ok(tree)
451    }
452    fn build_range(&mut self, start: usize, end: usize, work: &mut Work) -> Result<usize, Error> {
453        let mut lo = [f64::INFINITY; 3];
454        let mut hi = [f64::NEG_INFINITY; 3];
455        for t in &self.triangles[start..end] {
456            work.add(1)?;
457            for p in t.p {
458                for k in 0..3 {
459                    lo[k] = lo[k].min(p[k]);
460                    hi[k] = hi[k].max(p[k]);
461                }
462            }
463        }
464        let id = self.nodes.len();
465        self.nodes.push(Node {
466            lo,
467            hi,
468            left: start,
469            right: usize::MAX,
470        });
471        if end - start > 1 {
472            let axis = (0..3)
473                .max_by(|&a, &b| (hi[a] - lo[a]).total_cmp(&(hi[b] - lo[b])))
474                .unwrap_or(0);
475            let mid = start + (end - start) / 2;
476            select(&mut self.triangles[start..end], mid - start, axis, work)?;
477            let left = self.build_range(start, mid, work)?;
478            let right = self.build_range(mid, end, work)?;
479            self.nodes[id].left = left;
480            self.nodes[id].right = right;
481        }
482        Ok(id)
483    }
484    fn query<const MAX_ONLY: bool>(
485        &self,
486        id: usize,
487        p: V,
488        best: &mut Hit,
489        work: &mut Work,
490        cutoff: f64,
491    ) -> Result<(), Error> {
492        // A witnessed distance below the running maximum cannot raise it.
493        // Otherwise finish the exact nearest query with the original arithmetic.
494        if MAX_ONLY && best.distance <= cutoff {
495            return Ok(());
496        }
497        work.add(1)?;
498        let n = self.nodes[id];
499        if box_distance(n, p) > best.distance {
500            return Ok(());
501        }
502        if n.right == usize::MAX {
503            let t = self.triangles[n.left];
504            let (distance, weights) = closest(t.p, p);
505            if distance < best.distance || (distance == best.distance && t.id < best.id) {
506                *best = Hit {
507                    distance,
508                    weights,
509                    id: t.id,
510                    normals: t.normals(),
511                    triangle: n.left,
512                };
513            }
514        } else {
515            let (a, b) =
516                if box_distance(self.nodes[n.left], p) <= box_distance(self.nodes[n.right], p) {
517                    (n.left, n.right)
518                } else {
519                    (n.right, n.left)
520                };
521            self.query::<MAX_ONLY>(a, p, best, work, cutoff)?;
522            self.query::<MAX_ONLY>(b, p, best, work, cutoff)?;
523        }
524        Ok(())
525    }
526}
527// Metered median partition. A bounded number of quickselect passes falls back
528// to heapsort, preventing adversarial quadratic build work. No hidden sort scans.
529fn select<const NORMALS: usize>(
530    a: &mut [Triangle<NORMALS>],
531    mid: usize,
532    axis: usize,
533    work: &mut Work,
534) -> Result<(), Error> {
535    let key = |t: Triangle<NORMALS>| (t.center(axis), t.id);
536    let cmp = |a: Triangle<NORMALS>, b: Triangle<NORMALS>| {
537        key(a).0.total_cmp(&key(b).0).then(a.id.cmp(&b.id))
538    };
539    let mut lo = 0;
540    let mut hi = a.len();
541    let mut passes = 2 * (usize::BITS - a.len().leading_zeros());
542    while hi - lo > 1 {
543        if passes == 0 {
544            heap_sort(&mut a[lo..hi], cmp, work)?;
545            break;
546        }
547        passes -= 1;
548        let pivot = a[lo + (hi - lo) / 2];
549        let mut store = lo;
550        a.swap(lo + (hi - lo) / 2, hi - 1);
551        for i in lo..hi - 1 {
552            work.add(1)?;
553            if cmp(a[i], pivot).is_lt() {
554                a.swap(i, store);
555                store += 1;
556            }
557        }
558        a.swap(store, hi - 1);
559        if store == mid {
560            break;
561        }
562        if store < mid {
563            lo = store + 1;
564        } else {
565            hi = store;
566        }
567    }
568    Ok(())
569}
570fn heap_sort<const NORMALS: usize>(
571    a: &mut [Triangle<NORMALS>],
572    cmp: impl Fn(Triangle<NORMALS>, Triangle<NORMALS>) -> core::cmp::Ordering + Copy,
573    work: &mut Work,
574) -> Result<(), Error> {
575    fn sift<const INNER_NORMALS: usize>(
576        a: &mut [Triangle<INNER_NORMALS>],
577        mut root: usize,
578        end: usize,
579        cmp: impl Fn(Triangle<INNER_NORMALS>, Triangle<INNER_NORMALS>) -> core::cmp::Ordering + Copy,
580        work: &mut Work,
581    ) -> Result<(), Error> {
582        while root < end / 2 {
583            let mut child = root * 2 + 1;
584            work.add(1)?;
585            if child + 1 < end && cmp(a[child], a[child + 1]).is_lt() {
586                child += 1;
587            }
588            if !cmp(a[root], a[child]).is_lt() {
589                break;
590            }
591            a.swap(root, child);
592            root = child;
593        }
594        Ok(())
595    }
596    for root in (0..a.len() / 2).rev() {
597        sift(a, root, a.len(), cmp, work)?;
598    }
599    for end in (1..a.len()).rev() {
600        a.swap(0, end);
601        sift(a, 0, end, cmp, work)?;
602    }
603    Ok(())
604}
605fn box_distance(n: Node, p: V) -> f64 {
606    (0..3)
607        .map(|k| (n.lo[k] - p[k]).max(0.0).max(p[k] - n.hi[k]))
608        .map(|d| d * d)
609        .sum()
610}
611struct Hit {
612    triangle: usize,
613    distance: f64,
614    weights: V,
615    id: usize,
616    normals: [V; 3],
617}
618// The minimum is on an edge or the orthogonal projection onto the face.
619// Edge fallback also handles collinear and point triangles without division by zero.
620fn closest(t: [V; 3], p: V) -> (f64, V) {
621    let mut best = (f64::INFINITY, [1.0, 0.0, 0.0]);
622    for (a, b) in [(0, 1), (1, 2), (2, 0)] {
623        let edge = sub(t[b], t[a]);
624        let len = dot(edge, edge);
625        let s = if len > 0.0 {
626            (dot(sub(p, t[a]), edge) / len).clamp(0.0, 1.0)
627        } else {
628            0.0
629        };
630        let mut w = [0.0; 3];
631        w[a] = 1.0 - s;
632        w[b] = s;
633        // Measure the residual directly, rather than reconstructing a world
634        // point from rounded weights (which can erase small offsets on long
635        // segments). Endpoints use their direct distance; interiors use the
636        // perpendicular distance to the line, relative to the nearer endpoint.
637        let d = if s == 0.0 {
638            let delta = sub(p, t[a]);
639            dot(delta, delta)
640        } else if s == 1.0 {
641            let delta = sub(p, t[b]);
642            dot(delta, delta)
643        } else {
644            let offset = sub(p, if s <= 0.5 { t[a] } else { t[b] });
645            let perpendicular = cross(offset, edge);
646            dot(perpendicular, perpendicular) / len
647        };
648        if d < best.0 {
649            best = (d, w);
650        }
651    }
652    let ab = sub(t[1], t[0]);
653    let ac = sub(t[2], t[0]);
654    let n = cross(ab, ac);
655    let nn = dot(n, n);
656    if nn > 0.0 {
657        let ap = sub(p, t[0]);
658        let v = dot(cross(ap, ac), n) / nn;
659        let w = dot(cross(ab, ap), n) / nn;
660        if v >= 0.0 && w >= 0.0 && v + w <= 1.0 {
661            let h = dot(ap, n);
662            let d = h * h / nn;
663            if d < best.0 {
664                best = (d, [1.0 - v - w, v, w]);
665            }
666        }
667    }
668    best
669}
670// The face candidate is also tested by `closest`. A successful candidate is
671// sufficient to bound this sample below the running maximum; a failed witness
672// leaves the exact tree query unchanged. Degenerate/outside faces use edges.
673fn witness(t: [V; 3], p: V, cutoff: f64) -> Option<(f64, V)> {
674    let ab = sub(t[1], t[0]);
675    let ac = sub(t[2], t[0]);
676    let n = cross(ab, ac);
677    let nn = dot(n, n);
678    if nn > 0.0 {
679        let ap = sub(p, t[0]);
680        let v = dot(cross(ap, ac), n) / nn;
681        let w = dot(cross(ab, ap), n) / nn;
682        if v >= 0.0 && w >= 0.0 && v + w <= 1.0 {
683            let h = dot(ap, n);
684            let d = h * h / nn;
685            return if d <= cutoff {
686                Some((d, [1.0 - v - w, v, w]))
687            } else {
688                None
689            };
690        }
691    }
692    let (d, weights) = closest(t, p);
693    if d <= cutoff {
694        Some((d, weights))
695    } else {
696        None
697    }
698}
699#[derive(Default)]
700struct Stats {
701    witness: Option<usize>,
702    count: u64,
703    max: f64,
704    sum: f64,
705    angle_max: f64,
706    angle_sum: f64,
707}
708impl Stats {
709    fn distance(&self) -> LodDistance {
710        LodDistance {
711            max: libm::sqrt(self.max),
712            rms: libm::sqrt(self.sum / self.count as f64),
713            samples: self.count,
714        }
715    }
716    fn sample<const MAX_ONLY: bool, const NORMALS: usize>(
717        &mut self,
718        t: Triangle<NORMALS>,
719        weights: V,
720        tree: &Tree<NORMALS>,
721        normals: bool,
722        work: &mut Work,
723    ) -> Result<(), Error> {
724        work.add(1)?;
725        let p = blend(t.p, weights);
726        let mut hit = Hit {
727            triangle: usize::MAX,
728            distance: f64::INFINITY,
729            weights: [0.0; 3],
730            id: usize::MAX,
731            normals: [[0.0; 3]; 3],
732        };
733        // Nearby samples often share a useful target triangle. Its distance is
734        // an upper bound, so a successful witness needs no BVH traversal.
735        if MAX_ONLY {
736            if let Some(i) = self.witness {
737                work.add(1)?;
738                let t = tree.triangles[i];
739                if let Some((distance, weights)) = witness(t.p, p, self.max) {
740                    hit = Hit {
741                        triangle: i,
742                        distance,
743                        weights,
744                        id: t.id,
745                        normals: t.normals(),
746                    };
747                }
748            }
749        }
750        tree.query::<MAX_ONLY>(0, p, &mut hit, work, self.max)?;
751        if MAX_ONLY && hit.triangle != usize::MAX {
752            self.witness = Some(hit.triangle);
753        }
754        self.count = self.count.checked_add(1).ok_or(Error::SizeOverflow)?;
755        self.max = self.max.max(hit.distance);
756        if !MAX_ONLY {
757            self.sum += hit.distance;
758        }
759        if !MAX_ONLY && normals {
760            let a = unit(blend(t.normals(), weights)).map_err(|_| Error::NumericalFailure)?;
761            let b = unit(blend(hit.normals, hit.weights)).map_err(|_| Error::NumericalFailure)?;
762            // atan2 remains accurate near zero and pi, unlike acos(dot).
763            let angle = libm::atan2(
764                libm::sqrt(dot(cross(a, b), cross(a, b))),
765                dot(a, b).clamp(-1.0, 1.0),
766            );
767            self.angle_max = self.angle_max.max(angle);
768            self.angle_sum += angle;
769        }
770        Ok(())
771    }
772}
773fn direction<I: crate::Index, const MAX_ONLY: bool, const NORMALS: usize>(
774    source: LodQualityMeshGeneric<'_, I>,
775    target: LodQualityMeshGeneric<'_, I>,
776    options: &LodQualityOptions,
777    budget: &mut Budget<'_>,
778    work: &mut Work,
779    initial_max: f64,
780) -> Result<Stats, Error> {
781    let tree = Tree::<NORMALS>::build(target, budget, work)?;
782    // Always release local storage accounting, including after a failed query.
783    let mut corners = Vec::<u64>::new();
784    let result = (|| {
785        if MAX_ONLY {
786            let words = source.positions.len().div_ceil(64);
787            work.add(words)?;
788            corners = budget.reserved(words)?;
789            corners.resize(words, 0);
790        }
791        let mut stats = Stats {
792            max: initial_max,
793            ..Stats::default()
794        };
795        for i in 0..source.indices.len() / 3 {
796            work.add(1)?;
797            let t = Triangle::<NORMALS>::read(source, i)?;
798            let n = cross(sub(t.p[1], t.p[0]), sub(t.p[2], t.p[0]));
799            let count = libm::ceil(0.5 * libm::sqrt(dot(n, n)) * options.samples_per_unit_area);
800            if !count.is_finite() || count > f64::from(u32::MAX) {
801                return Err(Error::SizeOverflow);
802            }
803            // Finite, nonnegative and checked <= u32::MAX: conversion cannot wrap.
804            let count = count as u32;
805            for (corner, w) in [[1., 0., 0.], [0., 1., 0.], [0., 0., 1.]]
806                .into_iter()
807                .enumerate()
808            {
809                let vertex = source.indices[i * 3 + corner].to_u32() as usize;
810                let mask = 1u64 << (vertex % 64);
811                if MAX_ONLY && corners[vertex / 64] & mask != 0 {
812                    // This corner is already bounded by an earlier maximum.
813                    // Keep the sample visit/count; its distance cannot raise max.
814                    work.add(1)?;
815                    stats.count = stats.count.checked_add(1).ok_or(Error::SizeOverflow)?;
816                } else {
817                    stats.sample::<MAX_ONLY, NORMALS>(
818                        t,
819                        w,
820                        &tree,
821                        source.normals.is_some(),
822                        work,
823                    )?;
824                    if MAX_ONLY {
825                        corners[vertex / 64] |= mask;
826                    }
827                }
828            }
829            for j in 0..count {
830                let r = libm::sqrt((f64::from(j) + 0.5) / f64::from(count));
831                let t2 = (f64::from(j.reverse_bits()) + 0.5) / 4294967296.0;
832                stats.sample::<MAX_ONLY, NORMALS>(
833                    t,
834                    [1.0 - r, r * (1.0 - t2), r * t2],
835                    &tree,
836                    source.normals.is_some(),
837                    work,
838                )?;
839            }
840        }
841        Ok(stats)
842    })();
843    if MAX_ONLY {
844        budget.release(corners);
845    }
846    budget.release(tree.nodes);
847    budget.release(tree.triangles);
848    result
849}
850
851/// The source-compatible u32 entry point; see [`measure_lod_quality_generic`] for selectable index widths.
852#[inline]
853pub fn measure_lod_quality(
854    source: LodQualityMesh<'_>,
855    level: LodQualityMesh<'_>,
856    options: &LodQualityOptions,
857    workspace: &mut Workspace,
858) -> Result<LodQuality, Error> {
859    measure_lod_quality_generic::<u32>(source.into(), level.into(), options, workspace)
860}
861
862/// The source-compatible u32 entry point; see [`measure_lod_chain_quality_generic`] for selectable index widths.
863#[inline]
864pub fn measure_lod_chain_quality(
865    source: LodQualityMesh<'_>,
866    chain: &LodChain,
867    options: &LodQualityOptions,
868    camera: Option<LodCamera>,
869    workspace: &mut Workspace,
870) -> Result<Vec<LodQualityLevel>, Error> {
871    let source: LodQualityMeshGeneric<'_, u32> = source.into();
872    let mut work = workspace.begin();
873    let result = (|| {
874        validate_options(options)?;
875        if let Some(camera) = camera {
876            camera.switch_distance(0.0)?;
877        }
878        work.add(chain.levels.len())?;
879        let mut budget = Budget::new(workspace);
880        let mut out = budget.reserved(chain.levels.len())?;
881        for level in &chain.levels {
882            let mesh = LodQualityMeshGeneric {
883                indices: &level.indices,
884                ..source
885            };
886            let quality = measure(source, mesh, options, &mut budget, &mut work)?;
887            out.push(LodQualityLevel {
888                quality,
889                switch_distance: camera
890                    .map(|c| c.switch_distance(quality.symmetric.max))
891                    .transpose()?,
892            });
893        }
894        Ok(out)
895    })();
896    workspace.finish(&work);
897    result
898}
899
900impl<'a> LodQualityMesh<'a> {
901    /// Source-compatible u32 operation.
902    #[inline]
903    pub fn new(indices: &'a [u32], positions: Positions<'a>) -> Self {
904        LodQualityMeshGeneric::new_generic(indices, positions).into()
905    }
906}
907
908/// The source-compatible u32 form of [`LodQualityMeshGeneric`].
909/// A borrowed triangle surface. Only referenced vertices are measured/validated.
910#[derive(Clone, Copy, Debug)]
911#[non_exhaustive]
912pub struct LodQualityMesh<'a> {
913    /// Triangle-list indices; at least one triangle is required.
914    pub indices: &'a [u32],
915    /// Positions in the same world units as the reported distances.
916    pub positions: Positions<'a>,
917    /// Optional per-vertex normals, normalized before interpolation.
918    pub normals: Option<&'a [[f32; 3]]>,
919}
920impl<'a> From<LodQualityMeshGeneric<'a, u32>> for LodQualityMesh<'a> {
921    #[inline]
922    fn from(value: LodQualityMeshGeneric<'a, u32>) -> Self {
923        Self {
924            indices: value.indices,
925            positions: value.positions,
926            normals: value.normals,
927        }
928    }
929}
930
931impl<'a> From<LodQualityMesh<'a>> for LodQualityMeshGeneric<'a, u32> {
932    #[inline]
933    fn from(value: LodQualityMesh<'a>) -> Self {
934        Self {
935            indices: value.indices,
936            positions: value.positions,
937            normals: value.normals,
938        }
939    }
940}
941
942#[cfg(all(test, feature = "clusterlod"))]
943mod maximum_tests {
944    use super::*;
945
946    #[test]
947    fn maximum_only_matches_uneven_surfaces() {
948        let mut state = 17u32;
949        let mut random = || {
950            state = state.wrapping_mul(1664525).wrapping_add(1013904223);
951            (state >> 8) as f32 / 16777216.0
952        };
953        let indices: Vec<u32> = (0..36).collect();
954        for scale in [1e-10, 1., 1e10] {
955            for _ in 0..16 {
956                let source: Vec<[f32; 3]> = (0..36)
957                    .map(|_| core::array::from_fn(|_| random() * scale))
958                    .collect();
959                let target: Vec<[f32; 3]> = source
960                    .iter()
961                    .map(|p| core::array::from_fn(|k| p[k] + (random() - 0.5) * scale))
962                    .collect();
963                let options = LodQualityOptions {
964                    samples_per_unit_area: 4. / f64::from(scale).powi(2),
965                };
966                let a = LodQualityMesh::new(&indices, Positions::from_packed(&source));
967                let b = LodQualityMesh::new(&indices, Positions::from_packed(&target));
968                let full = measure_lod_quality(a, b, &options, &mut Workspace::default())
969                    .expect("full measurement");
970                let maximum = measure_max(a, b, &options, &mut Workspace::default())
971                    .expect("maximum measurement");
972                assert_eq!(maximum.to_bits(), full.symmetric.max.to_bits());
973            }
974        }
975    }
976
977    #[test]
978    fn maximum_only_matches_full_queries() {
979        // Overlapping faces, repeated corners and degenerate segments exercise
980        // witness exits and exact queries that must raise the running maximum.
981        let indices = [0, 1, 2, 2, 1, 0, 0, 0, 3, 3, 4, 5];
982        let source = [
983            [0., 0., 0.],
984            [1., 0., 0.],
985            [0., 1., 0.],
986            [0., 0., 2.],
987            [1., 0., 2.],
988            [0., 1., 2.],
989        ];
990        for offset in [0., 1e-12, 0.125, 4.] {
991            let target = source.map(|p| [p[0], p[1], p[2] + offset]);
992            for density in [0., 1., 100.] {
993                let options = LodQualityOptions {
994                    samples_per_unit_area: density,
995                };
996                let a = LodQualityMesh::new(&indices, Positions::from_packed(&source));
997                let b = LodQualityMesh::new(&indices, Positions::from_packed(&target));
998                let full = measure_lod_quality(a, b, &options, &mut Workspace::default())
999                    .expect("full measurement");
1000                let maximum = measure_max(a, b, &options, &mut Workspace::default())
1001                    .expect("maximum measurement");
1002                assert_eq!(maximum.to_bits(), full.symmetric.max.to_bits());
1003            }
1004        }
1005    }
1006}