parry3d/partitioning/bvh/
bvh_binned_build.rs

1use super::bvh_tree::{BvhBuildStrategy, BvhNodeIndex, BvhNodeWide};
2use super::{Bvh, BvhNode, BvhWorkspace};
3use crate::bounding_volume::{Aabb, BoundingVolume};
4use crate::math::Real;
5
6impl Bvh {
7    /// Fully rebuilds this BVH using the given strategy.
8    ///
9    /// This rebuilds a BVH with the same leaves, but different intermediate nodes and depth using
10    /// the specified building strategy.
11    pub fn rebuild(&mut self, workspace: &mut BvhWorkspace, strategy: BvhBuildStrategy) {
12        if self.nodes.len() < 2 {
13            // Nothing to rebuild if the tree is empty or only contains the root.
14            // This takes care of the case where we have a partial root too.
15            return;
16        }
17
18        workspace.rebuild_leaves.clear();
19        for node in self.nodes.iter() {
20            if node.left.is_leaf() {
21                workspace.rebuild_leaves.push(node.left);
22            }
23            if node.right.is_leaf() {
24                workspace.rebuild_leaves.push(node.right);
25            }
26        }
27
28        self.nodes.clear();
29        self.parents.clear();
30        self.nodes.push(BvhNodeWide::zeros());
31        self.parents.push(BvhNodeIndex::default());
32
33        match strategy {
34            BvhBuildStrategy::Binned => self.rebuild_range_binned(0, &mut workspace.rebuild_leaves),
35            BvhBuildStrategy::Ploc => self.rebuild_range_ploc(0, &mut workspace.rebuild_leaves),
36        }
37    }
38
39    pub(crate) fn rebuild_range_binned(&mut self, target_node_id: u32, leaves: &mut [BvhNode]) {
40        // PERF: calculate an optimal bin count dynamically based on the number of leaves to split?
41        //       The paper suggests (4 + 2 * sqrt(num_leaves).floor()).min(16)
42        const NUM_BINS: usize = 8;
43        const BIN_EPSILON: Real = 1.0e-5;
44
45        let mut bins = [BvhBin::default(); NUM_BINS];
46
47        assert!(leaves.len() > 1);
48
49        let centroid_aabb = Aabb::from_points(leaves.iter().map(|node| node.center()));
50        let bins_axis = centroid_aabb.extents().imax();
51        let bins_range = [centroid_aabb.mins[bins_axis], centroid_aabb.maxs[bins_axis]];
52
53        // Compute bins characteristics.
54        let k1 = NUM_BINS as Real * (1.0 - BIN_EPSILON) / (bins_range[1] - bins_range[0]);
55        let k0 = bins_range[0];
56        for leaf in &*leaves {
57            let bin_id = (k1 * (leaf.center()[bins_axis] - k0)) as usize;
58            let bin = &mut bins[bin_id];
59            bin.aabb.merge(&leaf.aabb());
60            bin.leaf_count += 1;
61        }
62
63        // Select the best splitting plane (there are NUM_BINS - 1 splitting planes) based on SAH.
64        let mut right_merges = bins;
65        let mut right_acc = bins[NUM_BINS - 1];
66
67        for i in 1..NUM_BINS - 1 {
68            right_acc.aabb.merge(&right_merges[NUM_BINS - 1 - i].aabb);
69            right_acc.leaf_count += &right_merges[NUM_BINS - 1 - i].leaf_count;
70            right_merges[NUM_BINS - 1 - i] = right_acc;
71        }
72
73        let mut best_cost = Real::MAX;
74        let mut best_plane = 0;
75        let mut left_merge = bins[0];
76        let mut best_leaf_count = bins[0].leaf_count;
77
78        for i in 0..NUM_BINS - 1 {
79            let right = &right_merges[i + 1];
80
81            let cost = left_merge.aabb.volume() * left_merge.leaf_count as Real
82                + right.aabb.volume() * right.leaf_count as Real;
83            if cost < best_cost {
84                best_cost = cost;
85                best_plane = i;
86                best_leaf_count = left_merge.leaf_count;
87            }
88
89            left_merge.aabb.merge(&bins[i + 1].aabb);
90            left_merge.leaf_count += bins[i + 1].leaf_count;
91        }
92
93        // With the splitting plane selected, sort & split the leaves in place.
94        let mut mid = best_leaf_count as usize;
95
96        // In degenerate cases where all the node end up on the same bin,
97        // just split the range in two.
98        if mid == 0 || mid == leaves.len() {
99            mid = leaves.len() / 2;
100        } else {
101            // Sort in-place.
102            // TODO PERF: try with using teh leaves_tmp instead of in-place sorting.
103            let bin = |leaves: &mut [BvhNode], id: usize| {
104                let node = &leaves[id];
105                (k1 * (node.center()[bins_axis] - k0)) as usize
106            };
107
108            let mut left_id = 0;
109            let mut right_id = mid;
110
111            'outer: while left_id != mid && right_id != leaves.len() {
112                while bin(leaves, left_id) <= best_plane {
113                    left_id += 1;
114
115                    if left_id == mid {
116                        break 'outer;
117                    }
118                }
119
120                while bin(leaves, right_id) > best_plane {
121                    right_id += 1;
122
123                    if right_id == leaves.len() {
124                        break 'outer;
125                    }
126                }
127
128                leaves.swap(left_id, right_id);
129                left_id += 1;
130                right_id += 1;
131            }
132        }
133
134        // Recurse.
135        let (left_leaves, right_leaves) = leaves.split_at_mut(mid);
136
137        assert!(!left_leaves.is_empty() && !right_leaves.is_empty());
138
139        // Recurse.
140        if left_leaves.len() == 1 {
141            let target = &mut self.nodes[target_node_id as usize];
142            target.left = left_leaves[0];
143
144            if target.left.is_leaf() {
145                self.leaf_node_indices[target.left.children as usize] =
146                    BvhNodeIndex::left(target_node_id);
147            } else {
148                self.parents[target.left.children as usize] = BvhNodeIndex::left(target_node_id);
149            }
150        } else {
151            let left_id = self.nodes.len() as u32;
152            self.nodes.push(BvhNodeWide::zeros());
153            self.parents.push(BvhNodeIndex::left(target_node_id));
154            self.rebuild_range_binned(left_id, left_leaves);
155            self.nodes[target_node_id as usize].left = self.nodes[left_id as usize].merged(left_id);
156        }
157
158        if right_leaves.len() == 1 {
159            let target = &mut self.nodes[target_node_id as usize];
160            target.right = right_leaves[0];
161
162            if target.right.is_leaf() {
163                self.leaf_node_indices[target.right.children as usize] =
164                    BvhNodeIndex::right(target_node_id);
165            } else {
166                self.parents[target.right.children as usize] = BvhNodeIndex::right(target_node_id);
167            }
168        } else {
169            let right_id = self.nodes.len() as u32;
170            self.nodes.push(BvhNodeWide::zeros());
171            self.parents.push(BvhNodeIndex::right(target_node_id));
172            self.rebuild_range_binned(right_id, right_leaves);
173            self.nodes[target_node_id as usize].right =
174                self.nodes[right_id as usize].merged(right_id);
175        }
176    }
177}
178
179#[derive(Copy, Clone, Debug)]
180struct BvhBin {
181    aabb: Aabb,
182    leaf_count: u32,
183}
184
185impl Default for BvhBin {
186    fn default() -> Self {
187        Self {
188            aabb: Aabb::new_invalid(),
189            leaf_count: 0,
190        }
191    }
192}
parry3d/partitioning/bvh/bvh_binned_build.rs

parry3d/partitioning/bvh/
bvh_binned_build.rs
