ploc_bvh/
traverse.rs

1//! A module with generic logic for traversing the BVH
2
3use crate::{Bvh, BvhNode, BvhVolume};
4
5use std::collections::VecDeque;
6
7use bevy_math::bounding::IntersectsVolume;
8
9/// A stack used when traversing the BVH, you can reuse this to save on an alloc
10#[derive(Default)]
11pub struct Stack(VecDeque<u32>);
12
13impl std::ops::Deref for Stack {
14    type Target = VecDeque<u32>;
15
16    fn deref(&self) -> &Self::Target {
17        &self.0
18    }
19}
20
21impl std::ops::DerefMut for Stack {
22    fn deref_mut(&mut self) -> &mut Self::Target {
23        &mut self.0
24    }
25}
26
27impl<Volume: BvhVolume, T: Copy> Bvh<Volume, T> {
28    /// Create a stack with the right size for the BVH
29    pub fn create_stack(&self) -> Stack {
30        // TODO: Make sure we use the correct value here
31        Stack(VecDeque::with_capacity(
32            (self.items.len() as f32).log2().ceil() as usize + 10,
33        ))
34    }
35
36    /// Traverse the BVH with the provided [`IntersectsVolume`] test
37    pub fn traverse<'a, Test: IntersectsVolume<Volume>>(
38        &'a self,
39        stack: &'a mut Stack,
40        tester: Test,
41    ) -> Traverser<'a, Volume, T, Test> {
42        stack.clear();
43        stack.reserve_exact((self.items.len() as f32).log2().ceil() as usize + 10);
44        stack.push_back(0);
45
46        Traverser {
47            bvh: self,
48            tester,
49            stack,
50            current_node: None,
51            offset: 0,
52        }
53    }
54}
55
56/// An iterator that traverse the BVH using the provided [`IntersectsVolume`] test
57pub struct Traverser<'a, Volume: BvhVolume, T: Copy, Test: IntersectsVolume<Volume>> {
58    bvh: &'a Bvh<Volume, T>,
59    /// The test used in the traverser
60    pub tester: Test,
61    stack: &'a mut Stack,
62    current_node: Option<u32>,
63    offset: u32,
64}
65
66impl<'a, Volume: BvhVolume, T: Copy, Test: IntersectsVolume<Volume>> Iterator
67    for Traverser<'a, Volume, T, Test>
68{
69    type Item = &'a T;
70
71    fn next(&mut self) -> Option<Self::Item> {
72        if self.bvh.items.is_empty() {
73            return None;
74        }
75
76        if let Some(current_node) = self.current_node {
77            let node = &self.bvh.nodes[current_node as usize];
78            match self.next_item(node) {
79                None => {}
80                v => return v,
81            };
82        }
83
84        while let Some(index) = self.stack.pop_front() {
85            let node = &self.bvh.nodes[index as usize];
86
87            if !self.tester.intersects(&node.volume) {
88                continue;
89            }
90
91            if node.count > 0 {
92                self.current_node = Some(index);
93                self.offset = 0;
94
95                match self.next_item(node) {
96                    None => {}
97                    v => return v,
98                };
99            } else {
100                self.stack.push_back(node.start_index);
101                self.stack.push_back(node.start_index + 1);
102            }
103        }
104
105        None
106    }
107}
108
109impl<'a, Volume: BvhVolume, T: Copy, Test: IntersectsVolume<Volume>>
110    Traverser<'a, Volume, T, Test>
111{
112    #[inline(always)]
113    fn next_item(&mut self, node: &'_ BvhNode<Volume>) -> Option<&'a T> {
114        while self.current_node.is_some() {
115            let item = &self.bvh.items[(node.start_index + self.offset) as usize];
116            self.offset += 1;
117            if self.offset == node.count {
118                self.current_node = None;
119            }
120            if self.tester.intersects(&item.volume) {
121                return Some(&item.t);
122            }
123        }
124        None
125    }
126}
ploc_bvh/traverse.rs

ploc_bvh/
traverse.rs
