obvhs/ploc/
rebuild.rs

1use std::borrow::Borrow;
2
3use crate::{
4    bvh2::Bvh2,
5    fast_stack,
6    faststack::FastStack,
7    ploc::{PlocBuilder, PlocSearchDistance, SortPrecision},
8};
9
10/// Provide a set of leaves that need to be rebuilt. After calling, flags will be true for any node index up the tree
11/// that needs to be included in the partial rebuild.
12pub fn compute_rebuild_path_flags<I, L>(bvh: &Bvh2, leaves: I, flags: &mut Vec<bool>)
13where
14    I: IntoIterator<Item = L>,
15    L: Borrow<u32>,
16{
17    if bvh.nodes.len() < 2 {
18        return;
19    }
20    if bvh.parents.is_empty() {
21        panic!(
22            "Parents must be init before running compute_rebuild_path_flags. Call `bvh.init_parents_if_uninit()` first."
23        )
24    }
25
26    flags.clear();
27    flags.resize(bvh.nodes.len(), false);
28    // Bottom up traverse flagging nodes as being parents of leaves that need to be rebuilt.
29    for leaf_id in leaves {
30        let mut index = *leaf_id.borrow() as usize;
31        debug_assert!(bvh.nodes[index].is_leaf());
32        flags[index] = true;
33        while index > 0 {
34            index = bvh.parents[index] as usize;
35            if flags[index] {
36                // If already flagged don't need to continue up further, above this has already been traversed.
37                break;
38            }
39            flags[index] = true;
40        }
41    }
42}
43
44impl PlocBuilder {
45    /// Fully rebuild the bvh from its current leaves.
46    ///
47    /// # Arguments
48    /// * `bvh` - An existing bvh with valid leaves. Inner nodes are ignored.
49    /// * `search_distance` - Which search distance should be used when building the ploc.
50    /// * `sort_precision` - Bits used for ploc radix sort. More bits results in a more accurate but slower sort.
51    /// * `search_depth_threshold` - Below this depth a search distance of 1 will be used. Set to 0 to bypass and
52    ///   just use search_distance.
53    pub fn full_rebuild(
54        &mut self,
55        bvh: &mut Bvh2,
56        search_distance: PlocSearchDistance,
57        sort_precision: SortPrecision,
58        search_depth_threshold: usize,
59    ) {
60        if bvh.nodes.len() < 2 {
61            return;
62        }
63
64        self.current_nodes.clear();
65
66        // Collect all leaves
67        for node in &bvh.nodes {
68            if node.is_leaf() {
69                self.current_nodes.push(*node);
70            }
71        }
72
73        self.rebuild_from_leaves::<false>(
74            bvh,
75            search_distance,
76            sort_precision,
77            search_depth_threshold,
78        );
79    }
80
81    /// Partially rebuild the bvh. The given set of leaves and the subtrees that do not include any of the given leaves
82    /// will be built into a new bvh. If the set of leaves is a small enough proportion of the total this can be faster
83    /// since there may be large portions of the BVH that don't need to be updated. If the proportion is very high it
84    /// can be faster to build from scratch instead, avoiding the overhead of doing a partial rebuild. If only a few
85    /// nodes need to be updated it might be faster and produce a better BVH to selectively reinsert them.
86    ///
87    /// # Arguments
88    /// * `bvh` - An existing bvh with valid layout (AABBs in the tree above nodes that are to be rebuilt does not need
89    ///   to be correct)
90    /// * `should_remove()` - should return true for any node that should be include in the rebuild. This includes the
91    ///   entire chain up from any leaves that need to be updated. Use PlocBuilder::compute_rebuild_path_flags() or
92    ///   similar to compute. The leaves should have their new AABB before calling partial_rebuild() but the BVH does
93    ///   not need to be refit to accommodate them.
94    /// * `search_distance` - Which search distance should be used when building the ploc.
95    /// * `sort_precision` - Bits used for ploc radix sort. More bits results in a more accurate but slower sort.
96    /// * `search_depth_threshold` - Below this depth a search distance of 1 will be used. Set to 0 to bypass and
97    ///   just use search_distance.
98    pub fn partial_rebuild(
99        &mut self,
100        bvh: &mut Bvh2,
101        should_remove: impl Fn(usize) -> bool,
102        search_distance: PlocSearchDistance,
103        sort_precision: SortPrecision,
104        search_depth_threshold: usize,
105    ) {
106        if bvh.nodes.len() < 2 {
107            return;
108        }
109
110        self.current_nodes.clear();
111
112        // Top down traverse to collect leaves and unflagged subtrees
113        fast_stack!(u32, (96, 192), bvh.max_depth, stack, {
114            stack.push(bvh.nodes[0].first_index);
115            while let Some(left_node_index) = stack.pop() {
116                for node_index in [left_node_index as usize, left_node_index as usize + 1] {
117                    let node = &mut bvh.nodes[node_index];
118                    if !should_remove(node_index) || node.is_leaf() {
119                        self.current_nodes.push(*node);
120                    } else {
121                        stack.push(node.first_index);
122                    }
123                    node.set_invalid();
124                }
125            }
126        });
127
128        self.rebuild_from_leaves::<true>(
129            bvh,
130            search_distance,
131            sort_precision,
132            search_depth_threshold,
133        );
134    }
135
136    fn rebuild_from_leaves<const PARTIAL: bool>(
137        &mut self,
138        bvh: &mut Bvh2,
139        search_distance: PlocSearchDistance,
140        sort_precision: SortPrecision,
141        search_depth_threshold: usize,
142    ) {
143        if bvh.nodes.len() < 2 {
144            return;
145        }
146
147        let had_parents = !bvh.parents.is_empty();
148        let had_primitives_to_nodes = !bvh.primitives_to_nodes.is_empty();
149
150        self.next_nodes.clear();
151        self.mortons.clear();
152
153        // Rebuild BVH from leaves
154        let total_aabb = *bvh.nodes[0].aabb();
155        let sdt = search_depth_threshold;
156        match search_distance {
157            PlocSearchDistance::Minimum => {
158                self.build_ploc_from_leaves::<1, PARTIAL>(bvh, total_aabb, sort_precision, sdt)
159            }
160            PlocSearchDistance::VeryLow => {
161                self.build_ploc_from_leaves::<2, PARTIAL>(bvh, total_aabb, sort_precision, sdt)
162            }
163            PlocSearchDistance::Low => {
164                self.build_ploc_from_leaves::<6, PARTIAL>(bvh, total_aabb, sort_precision, sdt)
165            }
166            PlocSearchDistance::Medium => {
167                self.build_ploc_from_leaves::<14, PARTIAL>(bvh, total_aabb, sort_precision, sdt)
168            }
169            PlocSearchDistance::High => {
170                self.build_ploc_from_leaves::<24, PARTIAL>(bvh, total_aabb, sort_precision, sdt)
171            }
172            PlocSearchDistance::VeryHigh => {
173                self.build_ploc_from_leaves::<32, PARTIAL>(bvh, total_aabb, sort_precision, sdt)
174            }
175        }
176
177        if had_parents {
178            bvh.update_parents();
179        }
180        if had_primitives_to_nodes {
181            bvh.update_primitives_to_nodes();
182        }
183    }
184}
185
186#[cfg(test)]
187mod tests {
188
189    use glam::UVec2;
190
191    use super::*;
192    use crate::{
193        INVALID,
194        test_util::{geometry::demoscene, sampling::hash_noise},
195    };
196
197    #[test]
198    fn test_full_rebuild() {
199        let sm = demoscene(5, 0);
200        for tris in [&demoscene(31, 0), &sm, &sm[..1], &sm[..2], &sm[..3], &[]] {
201            let mut builder = PlocBuilder::with_capacity(tris.len());
202
203            let mut bvh = builder.build(
204                PlocSearchDistance::Minimum,
205                tris,
206                (0..tris.len() as u32).collect::<Vec<_>>(),
207                SortPrecision::U64,
208                1,
209            );
210
211            bvh.validate(tris, false, true);
212
213            builder.full_rebuild(&mut bvh, PlocSearchDistance::Minimum, SortPrecision::U64, 1);
214
215            bvh.validate(tris, false, true);
216        }
217    }
218
219    #[test]
220    fn test_full_rebuild_with_free_indices() {
221        let tris = demoscene(32, 0);
222
223        let mut builder = PlocBuilder::with_capacity(tris.len());
224
225        let mut bvh = builder.build(
226            PlocSearchDistance::Minimum,
227            &tris,
228            (0..tris.len() as u32).collect::<Vec<_>>(),
229            SortPrecision::U64,
230            1,
231        );
232
233        bvh.validate(&tris, false, true);
234
235        // Remove some primitives to create free indices
236        bvh.remove_primitive(6);
237        bvh.remove_primitive(9);
238        bvh.remove_primitive(10);
239        assert_eq!(bvh.primitive_indices_freelist.len(), 3);
240        assert!(bvh.primitive_indices.contains(&INVALID));
241
242        // Now do a full rebuild
243        builder.full_rebuild(&mut bvh, PlocSearchDistance::Minimum, SortPrecision::U64, 1);
244
245        bvh.validate(&tris, false, true);
246    }
247
248    #[test]
249    fn test_partial_rebuild_with_all_leaves() {
250        let sm = demoscene(5, 0);
251        for tris in [&demoscene(31, 0), &sm, &sm[..1], &sm[..2], &sm[..3], &[]] {
252            let mut builder = PlocBuilder::with_capacity(tris.len());
253
254            let mut bvh = builder.build(
255                PlocSearchDistance::Minimum,
256                tris,
257                (0..tris.len() as u32).collect::<Vec<_>>(),
258                SortPrecision::U64,
259                1,
260            );
261
262            bvh.validate(tris, false, true);
263
264            bvh.init_parents_if_uninit();
265            let mut flags = Vec::new();
266            compute_rebuild_path_flags(
267                &bvh,
268                bvh.nodes
269                    .iter()
270                    .enumerate()
271                    .filter(|(_i, n)| n.is_leaf())
272                    .map(|(i, _n)| i as u32),
273                &mut flags,
274            );
275
276            builder.partial_rebuild(
277                &mut bvh,
278                |node_id| flags[node_id],
279                PlocSearchDistance::Minimum,
280                SortPrecision::U64,
281                1,
282            );
283
284            bvh.validate(tris, false, true);
285        }
286    }
287
288    #[test]
289    fn test_partial_rebuild_with_one_leaf() {
290        let tris = demoscene(8, 0);
291
292        let mut builder = PlocBuilder::with_capacity(tris.len());
293
294        let mut bvh = builder.build(
295            PlocSearchDistance::Minimum,
296            &tris,
297            (0..tris.len() as u32).collect::<Vec<_>>(),
298            SortPrecision::U64,
299            0,
300        );
301
302        bvh.validate(&tris, false, true);
303
304        bvh.init_parents_if_uninit();
305        let mut flags = Vec::new();
306        compute_rebuild_path_flags(
307            &bvh,
308            bvh.nodes
309                .iter()
310                .enumerate()
311                .filter(|(_i, n)| n.is_leaf())
312                .map(|(i, _n)| i as u32)
313                .take(1),
314            &mut flags,
315        );
316
317        builder.partial_rebuild(
318            &mut bvh,
319            |node_id| flags[node_id],
320            PlocSearchDistance::Minimum,
321            SortPrecision::U64,
322            0,
323        );
324
325        bvh.validate(&tris, false, true);
326    }
327
328    #[test]
329    fn test_partial_rebuild_with_random_leaves() {
330        let sm = demoscene(5, 0);
331        for tris in [&demoscene(31, 0), &sm, &sm[..1], &sm[..2], &sm[..3], &[]] {
332            let mut builder = PlocBuilder::with_capacity(tris.len());
333
334            let mut bvh = builder.build(
335                PlocSearchDistance::Minimum,
336                tris,
337                (0..tris.len() as u32).collect::<Vec<_>>(),
338                SortPrecision::U64,
339                1,
340            );
341
342            bvh.validate(tris, false, true);
343
344            bvh.init_parents_if_uninit();
345            let mut flags = Vec::new();
346            compute_rebuild_path_flags(
347                &bvh,
348                bvh.nodes
349                    .iter()
350                    .enumerate()
351                    .filter(|(i, n)| n.is_leaf() && hash_noise(UVec2::ZERO, *i as u32) > 0.5)
352                    .map(|(i, _n)| i as u32)
353                    .take(1),
354                &mut flags,
355            );
356
357            builder.partial_rebuild(
358                &mut bvh,
359                |node_id| flags[node_id],
360                PlocSearchDistance::Minimum,
361                SortPrecision::U64,
362                0,
363            );
364
365            bvh.validate(tris, false, true);
366        }
367    }
368}
obvhs/ploc/rebuild.rs

obvhs/ploc/
rebuild.rs
