molgfx_math/bounds/
bvh_query.rs

1//! Allocation-reusing spatial queries over a finished hierarchy.
2
3use super::Bvh;
4use crate::{Aabb, Vec3};
5
6impl Bvh {
7    /// Root bounds, or the empty bound for an empty hierarchy.
8    #[must_use]
9    #[inline]
10    pub fn bounds(&self) -> Aabb {
11        self.nodes.first().map_or(Aabb::EMPTY, |node| node.bounds())
12    }
13
14    /// Appends source indices whose bounds overlap a ray. Both vectors are
15    /// cleared and reused; results follow deterministic hierarchy order.
16    pub fn ray_candidates(
17        &self,
18        origin: Vec3,
19        direction: Vec3,
20        traversal: &mut Vec<u32>,
21        output: &mut Vec<u32>,
22    ) {
23        traversal.clear();
24        output.clear();
25        if self.nodes.is_empty() || !origin.is_finite() || !direction.is_finite() {
26            return;
27        }
28        traversal.push(0);
29        let inverse_direction = direction.recip();
30        while let Some(index) = traversal.pop() {
31            let Some(node) = self.nodes.get(index as usize).copied() else {
32                continue;
33            };
34            if node
35                .bounds()
36                .ray_intersect(origin, inverse_direction)
37                .is_none()
38            {
39                continue;
40            }
41            self.append_node_candidates(node, traversal, output);
42        }
43    }
44
45    /// Appends source indices whose primitive bounds overlap a query sphere.
46    /// Both caller vectors retain their allocations for reuse.
47    pub fn sphere_candidates(
48        &self,
49        center: Vec3,
50        radius: f32,
51        traversal: &mut Vec<u32>,
52        output: &mut Vec<u32>,
53    ) {
54        traversal.clear();
55        output.clear();
56        if self.nodes.is_empty() || !center.is_finite() || !radius.is_finite() || radius < 0.0 {
57            return;
58        }
59        traversal.push(0);
60        let radius_sq = radius * radius;
61        while let Some(index) = traversal.pop() {
62            let Some(node) = self.nodes.get(index as usize).copied() else {
63                continue;
64            };
65            if point_box_distance_squared(center, node.bounds()) > radius_sq {
66                continue;
67            }
68            self.append_node_candidates(node, traversal, output);
69        }
70    }
71
72    /// Appends source indices whose primitive bounds overlap an axis-aligned
73    /// query box. Both caller vectors retain their storage.
74    pub fn aabb_candidates(&self, query: Aabb, traversal: &mut Vec<u32>, output: &mut Vec<u32>) {
75        traversal.clear();
76        output.clear();
77        if self.nodes.is_empty()
78            || query.is_empty()
79            || !query.min.is_finite()
80            || !query.max.is_finite()
81        {
82            return;
83        }
84        traversal.push(0);
85        while let Some(index) = traversal.pop() {
86            let Some(node) = self.nodes.get(index as usize).copied() else {
87                continue;
88            };
89            if !node.bounds().overlaps(&query) {
90                continue;
91            }
92            self.append_node_candidates(node, traversal, output);
93        }
94    }
95
96    #[inline]
97    fn append_node_candidates(
98        &self,
99        node: super::BvhNode,
100        traversal: &mut Vec<u32>,
101        output: &mut Vec<u32>,
102    ) {
103        if let Some(range) = node.primitive_range() {
104            let start = range.start as usize;
105            let end = range.end as usize;
106            if let Some(indices) = self.primitive_indices.get(start..end) {
107                output.extend_from_slice(indices);
108            }
109        } else if let Some((left, right)) = node.children() {
110            traversal.push(right);
111            traversal.push(left);
112        }
113    }
114}
115
116#[inline]
117pub(super) fn point_box_distance_squared(point: Vec3, bound: Aabb) -> f32 {
118    let outside = (bound.min - point).max(Vec3::ZERO) + (point - bound.max).max(Vec3::ZERO);
119    outside.length_squared()
120}
molgfx_math/bounds/bvh_query.rs

molgfx_math/bounds/
bvh_query.rs
