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(), Bvh2::insert_primitive(), and Bvh2::insert_primitive_precise(), 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 insert_leaf(&mut self, new_node: Bvh2Node) -> usize

Searches the tree with the greedy descent in Bvh2::find_sibling_greedy() to find a sibling for the node being inserted, then attaches it there and refits back up to the root, performing rotations along the way to help prevent the BVH from degenerating.

This is the faster counterpart of Bvh2::insert_leaf_precise(). It doesn’t need a traversal stack and it tries to keep Bvh2::max_depth up to date, at the cost of sometimes picking a slightly worse sibling.

Returns

The index of the newly added node. Note that this is generally not self.nodes.len() - 1, since a rotation on the refit walk can move the node that was just attached.

Arguments

• new_node - This node must be a leaf and already have a valid first_index into primitive_indices.

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_primitive(&mut self, aabb: Aabb, primitive_id: u32) -> usize

Searches the tree with the greedy descent in Bvh2::find_sibling_greedy() to find a sibling for the primitive being inserted, then attaches it there and refits back up to the root, performing rotations along the way to help prevent the BVH from degenerating. Updates Bvh2::primitive_indices and Bvh2::primitive_indices_freelist.

This is the faster counterpart of Bvh2::insert_primitive_precise(). It doesn’t need a traversal stack and it tries to keep Bvh2::max_depth up to date, at the cost of sometimes picking a slightly worse sibling.

Returns

The index of the newly added node.

Arguments

• aabb - The aabb of the primitive being inserted.
• primitive_id - The index of the primitive being inserted.

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 move_leaf(&mut self, node_id: usize, aabb: Aabb) -> usize

Moves the leaf specified by node_id to a new position in the BVH, resizing it to aabb. Refits back up to the root, performing rotations along the way to help prevent the BVH from degenerating.

This is the fused equivalent of Bvh2::remove_leaf() followed by Bvh2::insert_leaf().

Bvh2::nodes.len() is unchanged across the call and Bvh2::primitive_indices is untouched.

Returns

The index of the moved node.

Arguments

• node_id - The index into self.nodes of the leaf being moved.
• aabb - The new aabb of the leaf.

pub fn move_primitive(&mut self, aabb: Aabb, primitive_id: u32) -> usize

Moves the leaf that contains the given primitive to a new position in the BVH, resizing it to aabb. Refits back up to the root, performing rotations along the way to help prevent the BVH from degenerating.

This is the fused equivalent of Bvh2::remove_primitive() followed by Bvh2::insert_primitive(). The whole leaf is moved, so this requires that the leaf contains only this primitive.

Returns

The new index of the node of this primitive.

Arguments

• aabb - The new aabb of the primitive.
• primitive_id - The index of the primitive being moved.

pub fn insert_primitive_precise( &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_precise()). Updates Bvh2::primitive_indices and Bvh2::primitive_indices_freelist. Refits back up to the root, performing rotations along the way to help prevent the BVH from degenerating.

See Bvh2::insert_primitive() for a faster version that descends a single path when choosing the sibling. Unlike this method, Bvh2::insert_primitive() also tries to keep Bvh2::max_depth up to date.

Returns

The index of the newly added node. Note that this is generally not self.nodes.len() - 1, since a rotation on the refit walk can move the node that was just attached.

Arguments

• aabb - The aabb of the primitive being inserted.
• 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_precise() 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_precise() resize the stack as needed.

pub fn insert_leaf_precise( &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 Bvh2::nodes. Refits back up to the root, performing rotations along the way to help prevent the BVH from degenerating.

See “Branch and Bound” https://box2d.org/files/ErinCatto_DynamicBVH_Full.pdf and Jiˇrí Bittner et al. 2012 Fast Insertion-Based Optimization of Bounding Volume Hierarchies

See Bvh2::insert_leaf() for a faster version that descends a single path when choosing the sibling. Unlike this method, Bvh2::insert_leaf() also tries to keep Bvh2::max_depth up to date.

Returns

The index of the newly added node. Note that this is generally not self.nodes.len() - 1, since a rotation on the refit walk can move the node that was just attached.

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_precise() 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_precise() resize the stack as needed.

pub fn find_sibling_greedy(&self, aabb: &Aabb) -> (usize, usize)

Searches the tree for the best sibling for a leaf with the given aabb using a greedy top-down descent. The best sibling is classified as the sibling that if chosen it would increase the surface area of the BVH the least.

Unlike the branch and bound search in Bvh2::insert_leaf_precise(), this only ever descends a single path from the root, always taking the child with the lower bound on what inserting beneath it could cost, and stopping as soon as neither child’s bound can beat the best candidate already found. This is O(depth), needs no traversal stack, and doesn’t blow up the same way as the BVH gets deeper. However, it tends to find a slightly worse sibling than the branch and bound search.

Returns

The index of the best sibling found, and the depth it was found at (the root has a depth of 0).

Arguments

• aabb - The aabb of the leaf that is going to be inserted.

pub fn rotate_node(&mut self, node_id: usize) -> Option<(usize, usize)>

Computes the cost of a potential rotation around the node at node_id, and applies it if it improves the total cost of the two inner nodes below node_id.

This is a local restructuring of the tree that swaps one of the two children of node_id with a child of the other (a grandchild of node_id). Given a tree of the form:

    node
   /    \
  b      c
 / \    / \
d   e  f   g

where node_id refers to node, four rotations are considered: swapping b with f, b with g, c with d, and c with e. The minimum cost of the four is computed, and if it is less than the current cost of b and c, the rotation is applied.

This incrementally recovers the quality of the BVH as leaves are inserted or the tree is refit, and helps avoid degenerating depth.

Returns

The two slots whose contents were swapped, if a rotation was applied. Any node id held by the caller that is one of the two needs to be updated to the other.

Arguments

• node_id - The index into self.nodes of the node to rotate around. Does nothing for leaves, or for nodes whose children are both leaves.

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

Refit the BVH working up the tree from this node, ignoring leaves, performing rotations at each node along the way where beneficial.

Halts once two consecutive levels needed neither a resize nor a rotation. Panics in debug if some parent still needed to be resized.

This can only be used to refit when a single node has changed or moved.

See Bvh2::rotate_node() and Bvh2::refit_from().

pub fn refit_and_rotate_from_tracking_fast( &mut self, index: usize, tracked_node_id: usize, ) -> usize

Same as Bvh2::refit_and_rotate_from_fast(), but follows the node at tracked_node_id through any rotations applied along the way.

Returns

The index that the tracked node ended up at.

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 relink(&mut self, node_id: usize)

Tell the children of the node at node_id, or the primitives it contains if it is a leaf, that it is now at node_id. Needed after moving a node into a different slot in Bvh2::nodes.

If the node is already available, prefer Bvh2::relink_node().

pub fn relink_node(&mut self, node: &Bvh2Node, node_id: usize)

Tell the children of node, or the primitives it contains if it is a leaf, that it is now at node_id. Needed after moving a node into a different slot in Bvh2::nodes.

node must be the node that now occupies the node_id slot of Bvh2::nodes.

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.