ifc_lite_geometry/kernel/broadphase/
bounded.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at https://mozilla.org/MPL/2.0/.
4use super::{aabb_contains, seg_hits_aabb, Bvh};
5
6impl Bvh {
7    /// Conservative near-point candidates using this same tree/padding policy,
8    /// charging every visited node to a caller-owned aggregate work budget.
9    /// On exhaustion discard `out`: a partial candidate list is not a result.
10    pub fn point_candidates_bounded(
11        &self,
12        point: [f64; 3],
13        radius: f64,
14        out: &mut Vec<u32>,
15        remaining: &mut usize,
16    ) -> Result<(), &'static str> {
17        if !point.iter().all(|v| v.is_finite()) || !radius.is_finite() || radius < 0. {
18            return Err("BVH query requires a finite point and nonnegative radius");
19        }
20        if self.root == u32::MAX {
21            return Ok(());
22        }
23        let mut pending = [0_u32; 64];
24        pending[0] = self.root;
25        let mut count = 1;
26        while count > 0 {
27            count -= 1;
28            let index = pending[count];
29            *remaining = remaining
30                .checked_sub(1)
31                .ok_or("BVH query work budget exhausted")?;
32            let node = &self.nodes[index as usize];
33            if !aabb_contains(point, &node.aabb, self.pad + radius) {
34                continue;
35            }
36            if node.tri != u32::MAX {
37                out.push(node.tri);
38            } else {
39                if count + 2 > pending.len() {
40                    return Err("BVH query stack budget exceeded");
41                }
42                pending[count] = node.right;
43                pending[count + 1] = node.left;
44                count += 2;
45            }
46        }
47        Ok(())
48    }
49}
50
51impl Bvh {
52    /// Conservative candidates for the segment `p`→`far`, charging every visited
53    /// node to the caller's aggregate work budget like `point_candidates_bounded`.
54    /// On exhaustion discard `out`: a partial candidate list is not a result.
55    pub fn ray_candidates_bounded(
56        &self,
57        p: [f64; 3],
58        far: [f64; 3],
59        out: &mut Vec<u32>,
60        remaining: &mut usize,
61    ) -> Result<(), &'static str> {
62        if !p.iter().chain(&far).all(|v| v.is_finite()) {
63            return Err("BVH query requires finite segment endpoints");
64        }
65        if self.root == u32::MAX {
66            return Ok(());
67        }
68        let mut pending = [0_u32; 64];
69        pending[0] = self.root;
70        let mut count = 1;
71        while count > 0 {
72            count -= 1;
73            let index = pending[count];
74            *remaining = remaining
75                .checked_sub(1)
76                .ok_or("BVH query work budget exhausted")?;
77            let node = &self.nodes[index as usize];
78            if !seg_hits_aabb(p, far, &node.aabb, self.pad) {
79                continue;
80            }
81            if node.tri != u32::MAX {
82                out.push(node.tri);
83            } else {
84                if count + 2 > pending.len() {
85                    return Err("BVH query stack budget exceeded");
86                }
87                pending[count] = node.right;
88                pending[count + 1] = node.left;
89                count += 2;
90            }
91        }
92        Ok(())
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    #[test]
100    fn issue_4381_bounded_ray_query_matches_candidates_and_reports_exhaustion() {
101        let triangles = [
102            [[0., 0., 0.], [1., 0., 0.], [0., 1., 0.]],
103            [[0., 0., 0.004], [1., 0., 0.004], [0., 1., 0.004]],
104            [[5., 5., 0.], [6., 5., 0.], [5., 6., 0.]],
105        ];
106        let tree = Bvh::build(&triangles);
107        let mut old = Vec::new();
108        tree.ray_candidates([0.2, 0.2, -0.001], [0.2, 0.2, 0.01], &mut old);
109        let mut actual = Vec::new();
110        let mut budget = 5;
111        tree.ray_candidates_bounded([0.2, 0.2, -0.001], [0.2, 0.2, 0.01], &mut actual, &mut budget)
112            .unwrap();
113        actual.sort_unstable();
114        old.sort_unstable();
115        assert_eq!(actual, old);
116        assert_eq!(actual, vec![0, 1]);
117        assert!(tree
118            .ray_candidates_bounded([0.2, 0.2, -0.001], [0.2, 0.2, 0.01], &mut Vec::new(), &mut 1)
119            .is_err());
120        assert!(tree
121            .ray_candidates_bounded([f64::NAN, 0., 0.], [0., 0., 1.], &mut Vec::new(), &mut 10)
122            .is_err());
123        let mut none = Vec::new();
124        tree.ray_candidates_bounded([0.2, 0.2, 0.001], [0.2, 0.2, 0.003], &mut none, &mut 10).unwrap();
125        assert!(none.is_empty(), "a segment strictly between the sheets touches neither");
126    }
127    #[test]
128    fn issue_4381_bounded_query_matches_candidates_and_reports_exhaustion() {
129        let triangles = [
130            [[0., 0., 0.], [1., 0., 0.], [0., 1., 0.]],
131            [[0., 0., 0.01], [1., 0., 0.01], [0., 1., 0.01]],
132        ];
133        let tree = Bvh::build(&triangles);
134        let mut old = Vec::new();
135        tree.point_candidates([0.2, 0.2, 0.], 0.02, &mut old);
136        let mut actual = Vec::new();
137        let mut budget = 3;
138        tree.point_candidates_bounded([0.2, 0.2, 0.], 0.02, &mut actual, &mut budget)
139            .unwrap();
140        assert_eq!(actual, old);
141        assert_eq!(actual.len(), 2);
142        assert_eq!(budget, 0);
143        assert!(tree
144            .point_candidates_bounded([0.2, 0.2, 0.], 0.02, &mut Vec::new(), &mut 2)
145            .is_err());
146        assert!(tree
147            .point_candidates_bounded([f64::NAN, 0., 0.], 0.02, &mut Vec::new(), &mut 10)
148            .is_err());
149    }
150}
ifc_lite_geometry/kernel/broadphase/bounded.rs

ifc_lite_geometry/kernel/broadphase/
bounded.rs
