obvhs/cwbvh/
traverse_macro.rs

1/// Traverse a CwBvh with custom node and primitive intersections.
2/// I really didn't want to use a macro but it seems like everything else using closures/yielding is slower given
3/// both generic node and primitive traversal.
4///
5/// # Parameters
6/// - `$cwbvh`: `&CwBvh` The CwBvh to be traversed.
7/// - `$node`: `&CwBvhNode` The current node in the BVH that is being traversed.
8/// - `$state`: `Traversal` Mutable traversal state.
9/// - `$node_intersection`: An expression that is executed for each node intersection during traversal.
10///   It should test for intersection against the current `node`, making use of `state.oct_inv4` u32.
11///   It should return a u32 `hitmask` of the node children hitmask corresponding to which nodes were intersected.
12/// - `$primitive_intersection`: A code block that is executed for each primitive intersection.
13///   It should read the current `state.primitive_id` u32. This is the index into the primitive indices for the
14///   current primitive to be tested. Optionally use `break` to halt traversal.
15///
16/// # Example: Closest hit ray traversal
17/// ```
18/// use obvhs::{
19///     cwbvh::{builder::build_cwbvh_from_tris, node::CwBvhNode},
20///     ray::{Ray, RayHit},
21///     test_util::geometry::{icosphere, PLANE},
22///     triangle::Triangle,
23///     BvhBuildParams,
24///     traverse,
25/// };
26/// use glam::*;
27/// use std::time::Duration;
28///
29/// let mut tris: Vec<Triangle> = Vec::new();
30/// tris.extend(icosphere(1));
31/// tris.extend(PLANE);
32///
33/// let ray = Ray::new_inf(vec3a(0.1, 0.1, 4.0), vec3a(0.0, 0.0, -1.0));
34///
35/// let bvh = build_cwbvh_from_tris(&tris, BvhBuildParams::medium_build(), &mut Duration::default());
36/// let mut hit = RayHit::none();
37/// let mut traverse_ray = ray.clone();
38/// let mut state = bvh.new_traversal(ray.direction);
39/// let mut node;
40/// traverse!(bvh, node, state,
41///     // Node intersection:
42///     node.intersect_ray(&traverse_ray, state.oct_inv4),
43///     // Primitive intersection:
44///     {
45///         let t = tris[bvh.primitive_indices[state.primitive_id as usize] as usize].intersect(&traverse_ray);
46///         if t < traverse_ray.tmax {
47///             hit.primitive_id = state.primitive_id;
48///             hit.t = t;
49///             traverse_ray.tmax = t;
50///         }
51///     }
52/// );
53///
54/// let did_hit = hit.t < ray.tmax;
55/// assert!(did_hit);
56/// assert!(bvh.primitive_indices[hit.primitive_id as usize] == 62);
57/// ```
58#[macro_export]
59macro_rules! traverse {
60    ($cwbvh:expr, $node:expr, $state:expr, $node_intersection:expr, $primitive_intersection:expr) => {{
61        use $crate::faststack::FastStack;
62        loop {
63            // While the primitive group is not empty
64            while $state.primitive_group.y != 0 {
65                let local_primitive_index = $crate::cwbvh::firstbithigh($state.primitive_group.y);
66
67                // Remove primitive from current_group
68                $state.primitive_group.y &= !(1u32 << local_primitive_index);
69
70                $state.primitive_id = $state.primitive_group.x + local_primitive_index;
71                $primitive_intersection
72            }
73            $state.primitive_group = UVec2::ZERO;
74
75            // If there's remaining nodes in the current group to check
76            if $state.current_group.y & 0xff000000 != 0 {
77                let hits_imask = $state.current_group.y;
78
79                let child_index_offset = $crate::cwbvh::firstbithigh(hits_imask);
80                let child_index_base = $state.current_group.x;
81
82                // Remove node from current_group
83                $state.current_group.y &= !(1u32 << child_index_offset);
84
85                // If the node group is not yet empty, push it on the stack
86                if $state.current_group.y & 0xff000000 != 0 {
87                    $state.stack.push($state.current_group);
88                }
89
90                let slot_index = (child_index_offset - 24) ^ ($state.oct_inv4 & 0xff);
91                let relative_index = (hits_imask & !(0xffffffffu32 << slot_index)).count_ones();
92
93                let child_node_index = child_index_base + relative_index;
94
95                $node = &$cwbvh.nodes[child_node_index as usize];
96
97                $state.hitmask = $node_intersection;
98
99                $state.current_group.x = $node.child_base_idx;
100                $state.primitive_group.x = $node.primitive_base_idx;
101
102                $state.current_group.y = (&$state.hitmask & 0xff000000u32) | ($node.imask as u32);
103                $state.primitive_group.y = &$state.hitmask & 0x00ffffffu32;
104            } else {
105                // Below is only needed when using triangle postponing, which would only be helpful on the
106                // GPU (it helps reduce thread divergence). Also, this isn't compatible with traversal yielding.
107                // $state.primitive_group = $state.current_group;
108                $state.current_group = UVec2::ZERO;
109            }
110
111            // If there's no remaining nodes in the current group to check, pop it off the stack.
112            if $state.primitive_group.y == 0 && ($state.current_group.y & 0xff000000) == 0 {
113                // If the stack is empty, end traversal.
114                if $state.stack.is_empty() {
115                    #[allow(unused)]
116                    {
117                        $state.current_group.y = 0;
118                    }
119                    break;
120                }
121
122                $state.current_group = $state.stack.pop_fast();
123            }
124        }
125    }};
126}
obvhs/cwbvh/traverse_macro.rs

obvhs/cwbvh/
traverse_macro.rs
