1use crate::{
3 budget::Budget, workspace::Work, Error, LodChain, LodChainGeneric, Positions, Workspace,
4};
5use alloc::vec::Vec;
6
7type V = [f64; 3];
8
9#[derive(Clone, Copy, Debug)]
11#[non_exhaustive]
12pub struct LodQualityMeshGeneric<'a, I: crate::Index = u32> {
13 pub indices: &'a [I],
15 pub positions: Positions<'a>,
17 pub normals: Option<&'a [[f32; 3]]>,
19}
20impl<'a, I: crate::Index> LodQualityMeshGeneric<'a, I> {
21 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#[derive(Clone, Copy, Debug)]
33#[non_exhaustive]
34pub struct LodQualityOptions {
35 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#[derive(Clone, Copy, Debug, Default, PartialEq)]
53#[non_exhaustive]
54pub struct LodDistance {
55 pub max: f64,
57 pub rms: f64,
59 pub samples: u64,
61}
62#[derive(Clone, Copy, Debug, Default, PartialEq)]
64#[non_exhaustive]
65pub struct LodNormalDeviation {
66 pub max: f64,
68 pub mean: f64,
70}
71#[derive(Clone, Copy, Debug, PartialEq)]
73#[non_exhaustive]
74pub struct LodQuality {
75 pub source_to_level: LodDistance,
77 pub level_to_source: LodDistance,
79 pub symmetric: LodDistance,
81 pub normals: Option<LodNormalDeviation>,
83}
84
85#[derive(Clone, Copy, Debug)]
87#[non_exhaustive]
88pub struct LodCamera {
89 pub vertical_fov: f64,
92 pub viewport_height: f64,
94 pub pixel_tolerance: f64,
96}
97impl LodCamera {
98 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 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 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#[derive(Clone, Copy, Debug, PartialEq)]
160#[non_exhaustive]
161pub struct LodQualityLevel {
162 pub quality: LodQuality,
164 pub switch_distance: Option<f64>,
166}
167
168pub 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
213pub 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#[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 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 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#[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)]
450struct 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)?; 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 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}
592fn 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}
683fn 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 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}
735fn 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 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 _ => 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 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 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 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#[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#[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 #[inline]
989 pub fn new(indices: &'a [u32], positions: Positions<'a>) -> Self {
990 LodQualityMeshGeneric::new_generic(indices, positions).into()
991 }
992}
993
994#[derive(Clone, Copy, Debug)]
997#[non_exhaustive]
998pub struct LodQualityMesh<'a> {
999 pub indices: &'a [u32],
1001 pub positions: Positions<'a>,
1003 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 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}