bvh 0.12.0

A fast BVH using SAH
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

//! Utilities module.

use crate::bounding_hierarchy::{BHShape, BHValue};
use crate::bvh::ShapeIndex;
use crate::{aabb::Aabb, bvh::Shapes};

use nalgebra::Scalar;
use num_traits::Float;

/// Fast floating point minimum.  This function matches the semantics of
///
/// ```no_compile
/// if x < y { x } else { y }
/// ```
///
/// which has efficient instruction sequences on many platforms (1 instruction on x86).  For most
/// values, it matches the semantics of `x.min(y)`; the special cases are:
///
/// ```text
/// min(-0.0, +0.0); +0.0
/// min(+0.0, -0.0): -0.0
/// min( NaN,  1.0):  1.0
/// min( 1.0,  NaN):  NaN
/// ```
///
/// Note: This exists because [`std::cmp::min`] requires Ord which floating point types do not satisfy
#[inline(always)]
#[allow(dead_code)]
pub fn fast_min<T: Scalar + Copy + PartialOrd>(x: T, y: T) -> T {
    if x < y { x } else { y }
}

/// Fast floating point maximum.  This function matches the semantics of
///
/// ```no_compile
/// if x > y { x } else { y }
/// ```
///
/// which has efficient instruction sequences on many platforms (1 instruction on x86).  For most
/// values, it matches the semantics of `x.max(y)`; the special cases are:
///
/// ```text
/// max(-0.0, +0.0); +0.0
/// max(+0.0, -0.0): -0.0
/// max( NaN,  1.0):  1.0
/// max( 1.0,  NaN):  NaN
/// ```
///
/// Note: This exists because [`std::cmp::max`] requires Ord which floating point types do not satisfy
#[inline(always)]
#[allow(dead_code)]
pub fn fast_max<T: Scalar + Copy + PartialOrd>(x: T, y: T) -> T {
    if x > y { x } else { y }
}

/// Defines a Bucket utility object. Used to store the properties of shape-partitions
/// in the [`Bvh`] build procedure using SAH.
#[derive(Clone, Copy)]
pub struct Bucket<T: BHValue, const D: usize> {
    /// The number of shapes in this [`Bucket`].
    pub size: usize,

    /// The joint [`Aabb`] of the shapes in this [`Bucket`].
    pub aabb: Aabb<T, D>,

    /// The [`Aabb`] of the centers of the shapes in this [`Bucket`]
    pub centroid: Aabb<T, D>,
}

impl<T: BHValue, const D: usize> Bucket<T, D> {
    /// Returns an empty bucket.
    pub fn empty() -> Bucket<T, D> {
        Bucket {
            size: 0,
            aabb: Aabb::empty(),
            centroid: Aabb::empty(),
        }
    }

    /// Extend this [`Bucket`] by a shape with the given [`Aabb`].
    pub fn add_aabb(&mut self, aabb: &Aabb<T, D>) {
        self.size += 1;
        self.aabb = self.aabb.join(aabb);
        self.centroid.grow_mut(&aabb.center());
    }

    /// Join the contents of two [`Bucket`]'s.
    pub fn join_bucket(a: Bucket<T, D>, b: &Bucket<T, D>) -> Bucket<T, D> {
        Bucket {
            size: a.size + b.size,
            aabb: a.aabb.join(&b.aabb),
            centroid: a.centroid.join(&b.centroid),
        }
    }
}

pub(crate) fn joint_aabb_of_shapes<T: BHValue, const D: usize, Shape: BHShape<T, D>>(
    indices: &[ShapeIndex],
    shapes: &Shapes<Shape>,
) -> (Aabb<T, D>, Aabb<T, D>) {
    let mut aabb = Aabb::empty();
    let mut centroid = Aabb::empty();
    for index in indices {
        let shape = shapes.get(*index);
        aabb.join_mut(&shape.aabb());
        centroid.grow_mut(&shape.aabb().center());
    }
    (aabb, centroid)
}

/// Returns `true` if and only if any of the floats returned by `iter` are NaN.
#[inline(always)]
pub(crate) fn has_nan<'a, T: Float + 'a>(iter: impl IntoIterator<Item = &'a T>) -> bool {
    iter.into_iter().any(|f| f.is_nan())
}