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
116
117
118
119
120
121
122
123
124
125
126

//! Balls, including circles and spheres.

use nalgebra::Point;

use crate::{
    aabb::{Aabb, IntersectsAabb},
    bounding_hierarchy::BHValue,
};

/// A circle, which can be used for traversing 2D BVHs.
pub type Circle<T> = Ball<T, 2>;

/// A sphere, which can be used for traversing 3D BVHs.
pub type Sphere<T> = Ball<T, 3>;

/// In 2D, a circle. In 3D, a sphere. This can be used for traversing BVHs.
#[derive(Debug, Clone, Copy)]
pub struct Ball<T: BHValue, const D: usize> {
    /// The center of the ball.
    pub center: Point<T, D>,
    /// The radius of the ball.
    pub radius: T,
}

impl<T: BHValue, const D: usize> Ball<T, D> {
    /// Creates a [`Ball`] with the given `center` and `radius`.
    ///
    /// # Panics
    /// Panics, in debug mode, if the radius is negative.
    ///
    /// # Examples
    /// ```
    /// use bvh::ball::Ball;
    /// use nalgebra::Point3;
    ///
    /// let ball = Ball::new(Point3::new(1.0, 1.0, 1.0), 1.0);
    /// assert_eq!(ball.center, Point3::new(1.0, 1.0, 1.0));
    /// assert_eq!(ball.radius, 1.0)
    /// ```
    ///
    /// [`Ball`]: struct.Ball.html
    pub fn new(center: Point<T, D>, radius: T) -> Self {
        debug_assert!(radius >= T::from_f32(0.0).unwrap());
        Self { center, radius }
    }

    /// Returns true if this [`Ball`] contains the [`Point`].
    ///
    /// # Examples
    /// ```
    /// use bvh::ball::Ball;
    /// use nalgebra::Point3;
    ///
    /// let ball = Ball::new(Point3::new(1.0, 1.0, 1.0), 1.0);
    /// let point = Point3::new(1.25, 1.25, 1.25);
    ///
    /// assert!(ball.contains(&point));
    /// ```
    ///
    /// [`Ball`]: struct.Ball.html
    pub fn contains(&self, point: &Point<T, D>) -> bool {
        let mut distance_squared = T::zero();
        for i in 0..D {
            distance_squared += (point[i] - self.center[i]).powi(2);
        }
        // Squaring the RHS is faster than computing the square root of the LHS.
        distance_squared <= self.radius.powi(2)
    }

    /// Returns true if this [`Ball`] intersects the [`Aabb`].
    ///
    /// # Examples
    /// ```
    /// use bvh::{aabb::Aabb, ball::Ball};
    /// use nalgebra::Point3;
    ///
    /// let ball = Ball::new(Point3::new(1.0, 1.0, 1.0), 1.0);
    /// let aabb = Aabb::with_bounds(Point3::new(1.25, 1.25, 1.25), Point3::new(3.0, 3.0, 3.0));
    ///
    /// assert!(ball.intersects_aabb(&aabb));
    /// ```
    ///
    /// [`Aabb`]: struct.Aabb.html
    /// [`Ball`]: struct.Ball.html
    pub fn intersects_aabb(&self, aabb: &Aabb<T, D>) -> bool {
        // https://gamemath.com/book/geomtests.html#intersection_sphere_aabb
        // Finding the point in/on the AABB that is closest to the ball's center or,
        // more specifically, find the squared distance between that point and the
        // ball's center.
        let mut distance_squared = T::zero();
        for i in 0..D {
            let closest_on_aabb = self.center[i].clamp(aabb.min[i], aabb.max[i]);
            distance_squared += (closest_on_aabb - self.center[i]).powi(2);
        }

        // Then test if that point is in/on the ball. Squaring the RHS is faster than computing
        // the square root of the LHS.
        distance_squared <= self.radius.powi(2)
    }
}

impl<T: BHValue, const D: usize> IntersectsAabb<T, D> for Ball<T, D> {
    fn intersects_aabb(&self, aabb: &Aabb<T, D>) -> bool {
        self.intersects_aabb(aabb)
    }
}

#[cfg(test)]
mod tests {
    use super::Ball;
    use crate::testbase::TPoint3;

    #[test]
    fn ball_contains() {
        let ball = Ball::new(TPoint3::new(3.0, 4.0, 5.0), 1.5);

        // Ball should contain its own center.
        assert!(ball.contains(&ball.center));

        // Test some manually-selected points.
        let just_inside = TPoint3::new(3.04605, 3.23758, 3.81607);
        let just_outside = TPoint3::new(3.06066, 3.15813, 3.70917);
        assert!(ball.contains(&just_inside));
        assert!(!ball.contains(&just_outside));
    }
}