Struct Bvh2 

pub struct Bvh2 {
    pub nodes: Vec<Bvh2Node>,
    pub primitive_indices: Vec<u32>,
    pub primitive_indices_freelist: Vec<u32>,
    pub primitives_to_nodes: Vec<u32>,
    pub parents: Vec<u32>,
    pub children_are_ordered_after_parents: bool,
    pub max_depth: usize,
    pub uses_spatial_splits: bool,
}

A binary BVH

Fields

nodes: Vec<Bvh2Node>

List of nodes contained in this bvh. first_index in Bvh2Node for inner nodes indexes into this list. This list fully represents the BVH tree. The other fields in this struct provide additional information that allow the BVH to be manipulated more efficiently, but are not actually part of the BVH itself. The only other critical field is primitive_indices, assuming the BVH is not using a direct mapping.

primitive_indices: Vec<u32>

Mapping from bvh primitive indices to original input indices The reason for this mapping is that if multiple primitives are contained in a node, they need to have their indices laid out contiguously. To avoid this indirection we have two options:

1. Layout the primitives in the order of the primitive_indices mapping so that this can index directly into the primitive list.
2. Only allow one primitive per node and write back the original mapping to the bvh node list.

primitive_indices_freelist: Vec<u32>

A freelist for use when removing primitives from the bvh. These represent slots in Bvh2::primitive_indices that are available if a primitive is added to the bvh. Only currently used by Bvh2::remove_primitive() and Bvh2::insert_primitive() which are not part of the typical initial bvh generation.

primitives_to_nodes: Vec<u32>

An optional mapping from primitives back to nodes. Ex. let node_id = primitives_to_nodes[primitive_id]; Where primitive_id is the original index of the primitive used when making the BVH and node_id is the index into Bvh2::nodes for the node of that primitive. Always use with the direct primitive id, not the one in the bvh node. See: Bvh2::init_primitives_to_nodes(). If primitives_to_nodes is empty it’s expected that it has not been initialized yet or has been invalidated. If primitives_to_nodes is not empty, it is expected that functions that modify the BVH will keep the mapping valid.

parents: Vec<u32>

An optional mapping from a given node index to that node’s parent for each node in the bvh. See: Bvh2::init_parents_if_uninit(). If parents is empty it’s expected that it has not been initialized yet or has been invalidated. If parents is not empty it’s expected that functions that modify the BVH will keep the mapping valid.

children_are_ordered_after_parents: bool

This is set by operations that ensure that parents have higher indices than children and unset by operations that might disturb that order. Some operations require this ordering and will reorder if this is not true.

max_depth: usize

Stack defaults to 96 or the max depth found during initial ploc building, whichever is larger. This may be larger than needed depending on what post processing steps (like collapse, reinsertion, etc…), but the cost of recalculating it may not be worth it so it is not done automatically.

uses_spatial_splits: bool

Indicates that this BVH is using spatial splits. Large triangles are split into multiple smaller Aabbs, so primitives will extend outside the leaf in some cases. If the bvh uses splits, a primitive can show up in multiple leaf nodes so there wont be a 1 to 1 correlation between the total number of primitives in leaf nodes and in Bvh2::primitive_indices, vs the input triangles. If spatial splits are used, some validation steps have to be skipped and some features are unavailable: Bvh2::add_leaf(), Bvh2::remove_leaf(), Bvh2::add_primitive(), Bvh2::remove_primitive() as these would require a mapping from one primitive to multiple nodes in Bvh2::primitives_to_nodes

Implementations

impl Bvh2

pub fn remove_leaf(&mut self, node_id: usize) -> Bvh2Node

Removes and returns the leaf specified by node_id. Puts node_id sibling in its parents place then moves the last two nodes into the now empty slots at node_id and its sibling.

Doesn’t update the primitive_indices mapping. If this node is just going to be re-inserted again, nothing needs to be done with primitive_indices, the mapping will still be valid. If this primitive needs to be removed permanently see Bvh2::remove_primitive().

Arguments

• node_id - The index into self.nodes of the node that is to be removed

pub fn insert_leaf( &mut self, new_node: Bvh2Node, stack: &mut HeapStack<SiblingInsertionCandidate>, ) -> usize

Searches the tree recursively to find the best sibling for the node being inserted. The best sibling is classified as the sibling that if chosen it would increase the surface area of the BVH the least. When the best sibling is found, a parent of both the sibling and the new node is put in the location of the sibling and both the sibling and new node are added to the end of the bvh.nodes. See “Branch and Bound” https://box2d.org/files/ErinCatto_DynamicBVH_Full.pdf Jiˇrí Bittner et al. 2012 Fast Insertion-Based Optimization of Bounding Volume Hierarchies

Returns

The index of the newly added node (always bvh.nodes.len() - 1 since the node it put at the end).

Arguments

• new_node - This node must be a leaf and already have a valid first_index into primitive_indices
• stack - Used for the traversal stack. Needs to be large enough to initially accommodate traversal to the deepest leaf of the BVH. insert_leaf() will resize this stack after traversal to be at least 2x the required size. This ends up being quite a bit faster than using a Vec and works well when inserting multiple nodes. But does require the user to provide a good initial guess. SiblingInsertionCandidate is tiny so be generous. Something like: stack.reserve(bvh.depth(0) * 2).max(1000); If you are inserting a lot of leaves don’t call bvh.depth(0) with each leaf just let insert_leaf() resize the stack as needed.

pub fn remove_primitive(&mut self, primitive_id: u32)

Removes the leaf that contains the given primitive. Should be correct for nodes with multiple primitives per leaf but faster for nodes with only one primitive per leaf, and will leave node aabb oversized. Updates Bvh2::primitive_indices and Bvh2::primitive_indices_freelist.

Arguments

• primitive_id - The index of the primitive being removed.

pub fn insert_primitive( &mut self, aabb: Aabb, primitive_id: u32, stack: &mut HeapStack<SiblingInsertionCandidate>, ) -> usize

Searches the tree recursively to find the best sibling for the primitive being inserted (see Bvh2::insert_leaf()). Updates Bvh2::primitive_indices and Bvh2::primitive_indices_freelist.

Returns

The index of the newly added node.

Arguments

• bvh - The Bvh2 the new node is being added to
• primitive_id - The index of the primitive being inserted.
• stack - Used for the traversal stack. Needs to be large enough to initially accommodate traversal to the deepest leaf of the BVH. insert_leaf() will resize this stack after traversal to be at least 2x the required size. This ends up being quite a bit faster than using a Vec and works well when inserting multiple nodes. But does require the user to provide a good initial guess. SiblingInsertionCandidate is tiny so be generous. Something like: stack.reserve(bvh.depth(0) * 2).max(1000); If you are inserting a lot of leaves don’t call bvh.depth(0) with each leaf just let insert_leaf() resize the stack as needed.

impl Bvh2

pub fn reset_for_reuse(&mut self, prim_count: usize, indices: Option<Vec<u32>>)

Reset BVH while keeping allocations for rebuild. Note: results in an invalid bvh until rebuilt.

pub fn zeroed(prim_count: usize) -> Self

pub fn ray_traverse<F: FnMut(&Ray, usize) -> f32>( &self, ray: Ray, hit: &mut RayHit, intersection_fn: F, ) -> bool

Traverse the bvh for a given Ray. Returns the closest intersected primitive.

Arguments

• ray - The ray to be tested for intersection.
• hit - As traverse_dynamic intersects primitives, it will update hit with the closest.
• intersection_fn - should take the given ray and primitive index and return the distance to the intersection, if any.

Note the primitive index should index first into Bvh2::primitive_indices then that will be index of original primitive. Various parts of the BVH building process might reorder the primitives. To avoid this indirection, reorder your original primitives per primitive_indices.

pub fn ray_traverse_miss<F: FnMut(&Ray, usize) -> f32>( &self, ray: Ray, intersection_fn: F, ) -> bool

Traverse the bvh for a given Ray. Returns true if the ray missed all primitives.

Arguments

• ray - The ray to be tested for intersection.
• hit - As traverse_dynamic intersects primitives, it will update hit with the closest.
• intersection_fn - should take the given ray and primitive index and return the distance to the intersection, if any.

Note the primitive index should index first into Bvh2::primitive_indices then that will be index of original primitive. Various parts of the BVH building process might reorder the primitives. To avoid this indirection, reorder your original primitives per primitive_indices.

pub fn ray_traverse_anyhit<F: FnMut(&Ray, usize)>( &self, ray: Ray, intersection_fn: F, )

Traverse the bvh for a given Ray. Intersects all primitives along ray (for things like evaluating transparency) intersection_fn is called for all intersections. Ray is not updated to allow for evaluating at every hit.

Arguments

• ray - The ray to be tested for intersection.
• intersection_fn - takes the given ray and primitive index.

Note the primitive index should index first into Bvh2::primitive_indices then that will be index of original primitive. Various parts of the BVH building process might reorder the primitives. To avoid this indirection, reorder your original primitives per primitive_indices.

pub fn ray_traverse_dynamic<F: FnMut(&Bvh2Node, &mut Ray, &mut RayHit) -> bool, Stack: FastStack<u32>>( &self, stack: &mut Stack, ray: Ray, hit: &mut RayHit, intersection_fn: F, )

Traverse the BVH Returns false when no hit is found. Consider using or referencing: Bvh2::ray_traverse(), Bvh2::ray_traverse_miss(), or Bvh2::ray_traverse_anyhit().

Arguments

• state - Holds the current traversal state. Allows traverse_dynamic to yield.
• hit - As traverse_dynamic intersects primitives, it will update hit with the closest.
• intersection_fn - should test the primitives in the given node, update the ray.tmax, and hit info. Return false to halt traversal. For basic miss test return false on first hit to halt traversal. For closest hit run until it returns false and check hit.t < ray.tmax to see if it hit something For transparency, you want to hit every primitive in the ray’s path, keeping track of the closest opaque hit. and then manually setting ray.tmax to that closest opaque hit at each iteration.

Note the primitive index should index first into Bvh2::primitive_indices then that will be index of original primitive. Various parts of the BVH building process might reorder the primitives. To avoid this indirection, reorder your original primitives per primitive_indices.

pub fn ray_traverse_recursive( &self, ray: &Ray, node_index: usize, leaf_indices: &mut Vec<usize>, )

Recursively traverse the bvh for a given Ray. On completion, leaf_indices will contain a list of the intersected leaf node indices. This method is slower than stack traversal and only exists as a reference. This method does not check if the primitive was intersected, only the leaf node.

pub fn aabb_traverse<F: FnMut(&Self, u32) -> bool>(&self, aabb: Aabb, eval: F)

Traverse the BVH with an Aabb. fn eval is called for nodes that intersect aabb The bvh (self) and the current node index is passed into fn eval Note each node may have multiple primitives. node.first_index is the index of the first primitive. node.prim_count is the quantity of primitives contained in the given node. Return false from eval to halt traversal

pub fn point_traverse<F: FnMut(&Self, u32) -> bool>( &self, point: Vec3A, eval: F, )

Traverse the BVH with a point. fn eval is called for nodes that intersect point The bvh (self) and the current node index is passed into fn eval Note each node may have multiple primitives. node.first_index is the index of the first primitive. node.prim_count is the quantity of primitives contained in the given node. Return false from eval to halt traversal

pub fn reorder_in_stack_traversal_order(&mut self)

Order node array in stack traversal order. Ensures parents are always at lower indices than children. Fairly slow, can take around 1/3 of the time of building the same BVH from scratch from with the fastest_build preset. Doesn’t seem to speed up traversal much for a new BVH created from PLOC, but if it has had many removals/insertions it can help.

pub fn refit_all(&mut self)

Refits the whole BVH from the leaves up. If the leaves have moved very much the BVH can quickly become degenerate causing significantly higher traversal times. Consider rebuilding the BVH from scratch or running a bit of reinsertion after refit. Usage:

   use glam::*;
   use obvhs::*;
   use obvhs::{ploc::*, test_util::geometry::demoscene, bvh2::builder::build_bvh2_from_tris};
   use std::time::Duration;

   let mut tris = demoscene(32, 0);
   let mut bvh = build_bvh2_from_tris(&tris, BvhBuildParams::fastest_build(), &mut Duration::default());

   bvh.init_primitives_to_nodes_if_uninit(); // Generate mapping from primitives to nodes
   tris.transform(&Mat4::from_scale_rotation_translation(
       Vec3::splat(1.3),
       Quat::from_rotation_y(0.1),
       vec3(0.33, 0.3, 0.37),
   ));
   for (prim_id, tri) in tris.iter().enumerate() {
       bvh.nodes[bvh.primitives_to_nodes[prim_id] as usize].set_aabb(tri.aabb()); // Update aabbs
   }
   bvh.refit_all(); // Refit aabbs
   bvh.validate(&tris, false, true); // Validate that aabbs are now fitting tightly

pub fn init_parents_if_uninit(&mut self)

Compute parents and update cache only if they have not already been computed

pub fn update_parents(&mut self)

Compute the mapping from a given node index to that node’s parent for each node in the bvh and update local cache.

pub fn compute_parents(nodes: &[Bvh2Node], parents: &mut Vec<u32>)

Compute the mapping from a given node index to that node’s parent for each node in the bvh, takes a Vec to allow reusing the allocation.

pub fn init_primitives_to_nodes_if_uninit(&mut self)

Compute compute_primitives_to_nodes and update cache only if they have not already been computed. Not supported if using spatial splits as it would require a mapping from one primitive to multiple nodes.

pub fn update_primitives_to_nodes(&mut self)

Compute the mapping from primitive index to node index and update local cache. Not supported if using spatial splits as it would require a mapping from one primitive to multiple nodes.

pub fn compute_primitives_to_nodes( nodes: &[Bvh2Node], primitive_indices: &[u32], primitives_to_nodes: &mut Vec<u32>, )

Compute the mapping from primitive index to node index. Takes a Vec to allow reusing the allocation.

pub fn validate_parents(&self)

pub fn validate_primitives_to_nodes(&self)

pub fn refit_from(&mut self, index: usize)

Refit the BVH working up the tree from this node, ignoring leaves. (TODO add a version that checks leaves) This recomputes the Aabbs for all the parents of the given node index. This can only be used to refit when a single node has changed or moved.

pub fn refit_from_fast(&mut self, index: usize)

Refit the BVH working up the tree from this node, ignoring leaves. This recomputes the Aabbs for the parents of the given node index. Halts if the parents are the same size. Panics in debug if some parents still needed to be resized. This can only be used to refit when a single node has changed or moved.

pub fn resize_node(&mut self, node_id: usize, aabb: Aabb)

Update node aabb and refit the BVH working up the tree from this node.

pub fn reinsert_node(&mut self, node_id: usize)

Find if there might be a better spot in the BVH for this node and move it there. The id of the reinserted node does not changed.

pub fn active_primitive_indices_count(&self) -> usize

Get the count of active primitive indices. when primitives are removed they are added to the primitive_indices_freelist so the self.primitive_indices.len() may not represent the actual number of valid, active primitive_indices.

pub fn validate<T: Boundable>( &self, primitives: &[T], direct_layout: bool, tight_fit: bool, ) -> Bvh2ValidationResult

direct_layout: The primitives are already laid out in bvh.primitive_indices order. tight_fit: Requires that children nodes and primitives fit tightly in parents. This is ignored for primitives if the bvh uses spatial splits (tight_fit can still be set to true). This was added for validating refit_all().

pub fn validate_impl<T: Boundable>( &self, primitives: &[T], result: &mut Bvh2ValidationResult, node_index: u32, parent_index: u32, current_depth: u32, )

pub fn print_bvh(&self, node_index: usize, depth: usize)

Basic debug print illustrating the bvh layout

pub fn depth(&self, node_index: usize) -> usize

Get the maximum depth of the BVH from the given node

Trait Implementations

impl Clone for Bvh2

fn clone(&self) -> Bvh2

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Default for Bvh2

fn default() -> Self

Returns the “default value” for a type.