parry3d/partitioning/bvh/
bvh_queries.rs

1use super::{Bvh, BvhNode};
2use crate::bounding_volume::{Aabb, BoundingVolume};
3use crate::math::Point;
4use crate::math::Real;
5use crate::query::PointProjection;
6use crate::query::{PointQuery, Ray};
7
8#[cfg(all(feature = "simd-is-enabled", feature = "dim3", feature = "f32"))]
9pub(super) struct SimdInvRay {
10    // TODO: we need to use `glam` here instead of `wide` because `wide` is lacking
11    //       operations for getting the min/max vector element.
12    //       We can switch back to `wide` once it's supported.
13    pub origin: glam::Vec3A,
14    pub inv_dir: glam::Vec3A,
15}
16
17#[cfg(all(feature = "simd-is-enabled", feature = "dim3", feature = "f32"))]
18impl From<Ray> for SimdInvRay {
19    fn from(ray: Ray) -> Self {
20        let inv_dir = ray.dir.map(|r| {
21            if r.abs() < Real::EPSILON {
22                r.signum() / Real::EPSILON
23            } else {
24                1.0 / r
25            }
26        });
27        Self {
28            origin: glam::Vec3A::from([ray.origin.x, ray.origin.y, ray.origin.z]),
29            inv_dir: glam::Vec3A::from([inv_dir.x, inv_dir.y, inv_dir.z]),
30        }
31    }
32}
33
34impl Bvh {
35    /// Iterates through all the leaves with an AABB intersecting the given `aabb`.
36    pub fn intersect_aabb<'a>(&'a self, aabb: &'a Aabb) -> impl Iterator<Item = u32> + 'a {
37        self.leaves(|node: &BvhNode| node.aabb().intersects(aabb))
38    }
39
40    /// Projects a point on this BVH using the provided leaf projection function.
41    ///
42    /// The `primitive_check` delegates the point-projection task to an external function that
43    /// is assumed to map a leaf index to an actual geometry to project on. The `Real` argument
44    /// given to that closure is the distance to the closest point found so far (or is equal to
45    /// `max_distance` if no projection was found so far).
46    pub fn project_point(
47        &self,
48        point: &Point<Real>,
49        max_distance: Real,
50        primitive_check: impl Fn(u32, Real) -> Option<PointProjection>,
51    ) -> Option<(u32, (Real, PointProjection))> {
52        self.find_best(
53            max_distance,
54            |node: &BvhNode, _| node.aabb().distance_to_local_point(point, true),
55            |primitive, _| {
56                let proj = primitive_check(primitive, max_distance)?;
57                Some((na::distance(&proj.point, point), proj))
58            },
59        )
60    }
61
62    /// Casts a ray on this BVH using the provided leaf ray-cast function.
63    ///
64    /// The `primitive_check` delegates the ray-casting task to an external function that
65    /// is assumed to map a leaf index to an actual geometry to cast a ray on. The `Real` argument
66    /// given to that closure is the distance to the closest ray hit found so far (or is equal to
67    /// `max_time_of_impact` if no projection was found so far).
68    #[cfg(not(all(feature = "simd-is-enabled", feature = "dim3", feature = "f32")))]
69    pub fn cast_ray(
70        &self,
71        ray: &Ray,
72        max_time_of_impact: Real,
73        primitive_check: impl Fn(u32, Real) -> Option<Real>,
74    ) -> Option<(u32, Real)> {
75        self.find_best(
76            max_time_of_impact,
77            |node: &BvhNode, best_so_far| node.cast_ray(ray, best_so_far),
78            primitive_check,
79        )
80    }
81
82    /// Casts a ray on this BVH using the provided leaf ray-cast function.
83    ///
84    /// The `primitive_check` delegates the ray-casting task to an external function that
85    /// is assumed to map a leaf index to an actual geometry to cast a ray on. The `Real` argument
86    /// given to that closure is the distance to the closest ray hit found so far (or is equal to
87    /// `max_time_of_impact` if no projection was found so far).
88    #[cfg(all(feature = "simd-is-enabled", feature = "dim3", feature = "f32"))]
89    pub fn cast_ray(
90        &self,
91        ray: &Ray,
92        max_time_of_impact: Real,
93        primitive_check: impl Fn(u32, Real) -> Option<Real>,
94    ) -> Option<(u32, Real)> {
95        // The commented code below relies on depth-first traversal instead of
96        // depth first. Interesting to compare both approaches (the best-first is
97        // expected to be consistently faster though).
98        //
99        // let simd_inv_ray = SimdInvRay::from(*ray);
100        // let mut best_primitive = u32::MAX;
101        // let mut best_toi = Real::MAX;
102        // self.traverse(|node: &BvhNode| {
103        //     if node.cast_inv_ray_simd(&simd_inv_ray) >= best_toi {
104        //         return TraversalAction::Prune;
105        //     }
106        //
107        //     if let Some(primitive) = node.leaf_data() {
108        //         let toi = primitive_check(primitive as u32, best_toi);
109        //         if toi < best_toi {
110        //             best_primitive = primitive as u32;
111        //             best_toi = toi;
112        //         }
113        //     }
114        //
115        //     TraversalAction::Continue
116        // });
117        // (best_primitive, best_toi)
118
119        let simd_inv_ray = SimdInvRay::from(*ray);
120        self.find_best(
121            max_time_of_impact,
122            |node: &BvhNode, _best_so_far| node.cast_inv_ray_simd(&simd_inv_ray),
123            |primitive, best_so_far| primitive_check(primitive, best_so_far),
124        )
125    }
126}
parry3d/partitioning/bvh/bvh_queries.rs

parry3d/partitioning/bvh/
bvh_queries.rs
