valence_spatial/
lib.rs

Help
1#![doc = include_str!("../README.md")]
2
3use vek::{Aabb, Vec3};
4
5pub mod bvh;
6
7pub trait SpatialIndex<N = f64> {
8    type Object: Bounded3D<N>;
9
10    /// Invokes `f` with every object in the spatial index considered
11    /// colliding according to `collides` in an arbitrary order.
12    ///
13    /// `collides` takes an AABB and returns whether or not a collision
14    /// occurred with the given AABB.
15    ///
16    /// `f` is called with every object considered colliding. If `f` returns
17    /// with `Some(x)`, then `query` exits early with `Some(x)`. If `f` never
18    /// returns with `Some`, then query returns `None`.
19    fn query<C, F, T>(&self, collides: C, f: F) -> Option<T>
20    where
21        C: FnMut(Aabb<N>) -> bool,
22        F: FnMut(&Self::Object) -> Option<T>;
23
24    /// Casts a ray defined by `origin` and `direction` through object AABBs
25    /// and returns the closest intersection for which `f` returns `true`.
26    ///
27    /// `f` is a predicate used to filter intersections. For instance, if a ray
28    /// is shot from a player's eye position, you probably don't want the
29    /// ray to intersect with the player's own hitbox.
30    ///
31    /// If no intersections are found or if `f` never returns `true` then `None`
32    /// is returned. Additionally, the given ray direction must be
33    /// normalized.
34    fn raycast<F>(
35        &self,
36        origin: Vec3<f64>,
37        direction: Vec3<f64>,
38        f: F,
39    ) -> Option<RaycastHit<Self::Object, N>>
40    where
41        F: FnMut(RaycastHit<Self::Object, N>) -> bool;
42}
43
44pub trait Bounded3D<N = f64> {
45    fn aabb(&self) -> Aabb<N>;
46}
47
48/// Represents an intersection between a ray and an entity's axis-aligned
49/// bounding box (hitbox).
50#[derive(PartialEq, Eq, Debug)]
51pub struct RaycastHit<'a, O, N = f64> {
52    /// The object that was hit by the ray.
53    pub object: &'a O,
54    /// The distance from the ray origin to the closest intersection point.
55    /// If the origin of the ray is inside the bounding box, then this will be
56    /// zero.
57    pub near: N,
58    /// The distance from the ray origin to the second intersection point. This
59    /// represents the point at which the ray exits the bounding box.
60    pub far: N,
61}
62
63impl<O, N: Clone> Clone for RaycastHit<'_, O, N> {
64    fn clone(&self) -> Self {
65        Self {
66            object: self.object,
67            near: self.near.clone(),
68            far: self.far.clone(),
69        }
70    }
71}
72
73impl<O, N: Copy> Copy for RaycastHit<'_, O, N> {}
74
75impl<N: Clone> Bounded3D<N> for Aabb<N> {
76    fn aabb(&self) -> Aabb<N> {
77        self.clone()
78    }
79}
80
81#[derive(Copy, Clone, PartialEq, Eq, Hash, Default, Debug)]
82pub struct WithAabb<O, N = f64> {
83    pub object: O,
84    pub aabb: Aabb<N>,
85}
86
87impl<O, N> WithAabb<O, N> {
88    pub fn new(object: O, aabb: Aabb<N>) -> Self {
89        Self { object, aabb }
90    }
91}
92
93impl<O, N: Clone> Bounded3D<N> for WithAabb<O, N> {
94    fn aabb(&self) -> Aabb<N> {
95        self.aabb.clone()
96    }
97}
98
99/// Calculates the intersection between an axis-aligned bounding box and a ray
100/// defined by its origin `ro` and direction `rd`.
101///
102/// If an intersection occurs, `Some((near, far))` is returned. `near` and `far`
103/// are the distance from the origin to the closest and furthest intersection
104/// points respectively. If the intersection occurs inside the bounding box,
105/// then `near` is zero.
106pub fn ray_box_intersect(ro: Vec3<f64>, rd: Vec3<f64>, bb: Aabb<f64>) -> Option<(f64, f64)> {
107    let mut near = -f64::INFINITY;
108    let mut far = f64::INFINITY;
109
110    for i in 0..3 {
111        // Rust's definition of min and max properly handle the NaNs that these
112        // computations might produce.
113        let t0 = (bb.min[i] - ro[i]) / rd[i];
114        let t1 = (bb.max[i] - ro[i]) / rd[i];
115
116        near = near.max(t0.min(t1));
117        far = far.min(t0.max(t1));
118    }
119
120    if near <= far && far >= 0.0 {
121        Some((near.max(0.0), far))
122    } else {
123        None
124    }
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130
131    #[test]
132    fn ray_box_edge_cases() {
133        let bb = Aabb {
134            min: Vec3::new(0.0, 0.0, 0.0),
135            max: Vec3::new(1.0, 1.0, 1.0),
136        };
137
138        let ros = [
139            // On a corner
140            Vec3::new(0.0, 0.0, 0.0),
141            // Outside
142            Vec3::new(-0.5, 0.5, -0.5),
143            // In the center
144            Vec3::new(0.5, 0.5, 0.5),
145            // On an edge
146            Vec3::new(0.0, 0.5, 0.0),
147            // On a face
148            Vec3::new(0.0, 0.5, 0.5),
149            // Outside slabs
150            Vec3::new(-2.0, -2.0, -2.0),
151        ];
152
153        let rds = [
154            Vec3::new(1.0, 0.0, 0.0),
155            Vec3::new(-1.0, 0.0, 0.0),
156            Vec3::new(0.0, 1.0, 0.0),
157            Vec3::new(0.0, -1.0, 0.0),
158            Vec3::new(0.0, 0.0, 1.0),
159            Vec3::new(0.0, 0.0, -1.0),
160        ];
161
162        assert!(rds.iter().all(|d| d.is_normalized()));
163
164        for ro in ros {
165            for rd in rds {
166                if let Some((near, far)) = ray_box_intersect(ro, rd, bb) {
167                    assert!(near.is_finite());
168                    assert!(far.is_finite());
169                    assert!(near <= far);
170                    assert!(near >= 0.0);
171                    assert!(far >= 0.0);
172                }
173            }
174        }
175    }
176}
valence_spatial/lib.rs

valence_spatial/
lib.rs
