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>(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#[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)]
385struct 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)?; 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 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}
527fn 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}
618fn 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 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}
670fn 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 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 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 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 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 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#[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#[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 #[inline]
903 pub fn new(indices: &'a [u32], positions: Positions<'a>) -> Self {
904 LodQualityMeshGeneric::new_generic(indices, positions).into()
905 }
906}
907
908#[derive(Clone, Copy, Debug)]
911#[non_exhaustive]
912pub struct LodQualityMesh<'a> {
913 pub indices: &'a [u32],
915 pub positions: Positions<'a>,
917 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 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}