Struct Bvh

pub struct Bvh { /* private fields */ }

A Bounding Volume Hierarchy designed for spatial queries and physics engine broad-phases.

Implementations

impl Bvh

pub fn rebuild( &mut self, workspace: &mut BvhWorkspace, strategy: BvhBuildStrategy, )

Fully rebuilds this BVH using the given strategy.

This rebuilds a BVH with the same leaves, but different intermediate nodes and depth using the specified building strategy.

impl Bvh

pub fn insert(&mut self, aabb: Aabb, leaf_index: u32)

Inserts a leaf into this BVH, or updates it if already exists.

pub fn insert_with_change_detection( &mut self, aabb: Aabb, leaf_index: u32, change_detection_margin: f32, )

Inserts a leaf into this BVH, or updates it if already exists.

If the aabb is already contained by the existing leaf node AABB, nothing is modified. Otherwise, the aabb being effectively inserted is equal to aabb enlarged by the change_detection_margin.

pub fn insert_or_update_partially( &mut self, aabb: Aabb, leaf_index: u32, change_detection_margin: f32, )

Either inserts a node on this tree, or, if it already exists, updates its associated bounding but doesn’t update its ascendant nodes.

This method is primarily designed to be called for inserting new nodes or updating existing ones, and then running a Bvh::refit. Until Bvh::refit or Bvh::refit_without_opt is called, the BVH will effectively be left in an invalid state where some internal nodes might no longer enclose their children.

For an alternative that inserts a node while also making sure all its ascendants are up to date, see Bvh::insert.

impl Bvh

pub fn optimize_incremental(&mut self, workspace: &mut BvhWorkspace)

Performs one step of incremental optimization of the tree.

Incremental optimization of the tree ensures that after modification of the tree’s geometry (after changes of its leaves AABBs) doesn’t lead to a poorly shaped tree, or tree with poor spatial culling capabilities.

This optimization is incremental because it only optimizes a subset of the tree in order to reduce its computational cost. It is indented to be called multiple times across multiple frames.

For example, if the BVH is used for a physics engine’s broad-phase, this method would typically be called once by simulation step.

impl Bvh

pub fn intersect_aabb<'a>( &'a self, aabb: &'a Aabb, ) -> impl Iterator<Item = u32> + 'a

Iterates through all the leaves with an AABB intersecting the given aabb.

pub fn project_point( &self, point: &Point<f32>, max_distance: f32, primitive_check: impl Fn(u32, f32) -> Option<PointProjection>, ) -> Option<(u32, (f32, PointProjection))>

Projects a point on this BVH using the provided leaf projection function.

The primitive_check delegates the point-projection task to an external function that is assumed to map a leaf index to an actual geometry to project on. The Real argument given to that closure is the distance to the closest point found so far (or is equal to max_distance if no projection was found so far).

pub fn cast_ray( &self, ray: &Ray, max_time_of_impact: f32, primitive_check: impl Fn(u32, f32) -> Option<f32>, ) -> Option<(u32, f32)>

Casts a ray on this BVH using the provided leaf ray-cast function.

The primitive_check delegates the ray-casting task to an external function that is assumed to map a leaf index to an actual geometry to cast a ray on. The Real argument given to that closure is the distance to the closest ray hit found so far (or is equal to max_time_of_impact if no projection was found so far).

impl Bvh

pub fn refit(&mut self, workspace: &mut BvhWorkspace)

Performs a tree refitting with internal storage cache optimizations.

Refitting is the action of ensuring that every node’s AABB encloses the AABBs of its children. In addition, this method will:

• Ensure that nodes are stored internally in depth-first order for better cache locality on depth-first searches.
• Ensure that the leaf count on each node is correct.
• Propagate the BvhNode::is_changed flag changes detected by Self::insert_or_update_partially (if change_detection_margin was nonzero) from leaves to its ascendants.

pub fn refit_without_opt(&mut self)

Similar to Self::refit but without any optimization of the internal node storage layout.

This can be faster than Self::refit but doesn’t reorder node to be more cache-efficient on tree traversals.

impl Bvh

pub fn leaves<F: Fn(&BvhNode) -> bool>(&self, check_node: F) -> Leaves<'_, F>

Iterates through the leaves, in depth-first order.

The check_node closure is called on every traversed node. If it returns false then the node and all its descendants won’t be iterated on. This is useful for pruning whole sub-trees based on a geometric predicate on the node’s AABB.

See also the Bvh::traverse function which is slightly less convenient since it doesn’t rely on the iterator system, but takes a closure that implements FnMut instead of Fn.

impl Bvh

pub fn traverse(&self, check_node: impl FnMut(&BvhNode) -> TraversalAction)

Traverse the tree in depth-first order.

The check_node closure is called on every traversed node. The returned TraversalAction controls whether a given node (and all its subtree) needs to be traversed, skipped, or if the traversal needs to exit immediately (for example if you were looking for only one particular node).

See also the Bvh::leaves iterator which is a more convenient way of traversing the tree, but is slightly limited in terms of node checking. In particular the closure given to Bvh::traverse is mutable can hold any state so its check can depend on previous execution of itself during the traversal.

pub fn find_best<L: BvhLeafCost>( &self, max_cost: f32, aabb_cost: impl Fn(&BvhNode, f32) -> f32, leaf_cost: impl Fn(u32, f32) -> Option<L>, ) -> Option<(u32, L)>

Find the leaf that minimizes their associated cost.

impl Bvh

pub fn traverse_bvtt_single_tree<const CHANGE_DETECTION: bool>( &self, workspace: &mut BvhWorkspace, f: &mut impl FnMut(u32, u32), )

Traverses the Bounding Volume Test Tree of a tree against itself.

The closure f will be called on each pair of leaf that passed the AABB intersection checks. If CHANGE_DETECTION is true, then only pairs of leaves where at least one was detected as changed during Self::insert_or_update_partially will be traversed.

pub fn leaf_pairs<'a, F: Fn(&BvhNode, &BvhNode) -> bool>( &'a self, other: &'a Self, check: F, ) -> LeafPairs<'a, F>

Performs a simultaneous traversal of the BVHs self and other, and yields the pairs of leaves it reached.

Any node pairs failing the given check will be excluded from the traversal.

impl Bvh

pub fn new() -> Self

An empty BVH.

pub fn from_leaves(strategy: BvhBuildStrategy, leaves: &[Aabb]) -> Self

Creates a new BVH with a slice of AABBs.

Each leaf will be associated an index equal to its position into the slice. For example, the AABB leaves[42] is associated to the leaf with index 42.

pub fn from_iter<It>(strategy: BvhBuildStrategy, leaves: It) -> Self

where It: IntoIterator<Item = (usize, Aabb)>,

Creates a new BVH with leaves given by an iterator.

The iterator yields leaf index and aabbs. The leaf indices will then be read back by various methods like tree traversals or leaf iterations.

Note that the indices are stored internally as u32. The iterator expects usize for convenience (so that iterators built with .enumerate() can be used directly without an additional cast of the usize index to u32).

pub fn root_aabb(&self) -> Aabb

The AABB bounding everything contained by this BVH.

pub fn scale(&mut self, scale: &Vector<f32>)

Scales this tree’s geometry by the given factor.

This is only valid if all elements of scale are positive.

pub fn is_empty(&self) -> bool

Does this tree not contain any leaf?

pub fn leaf_node(&self, leaf_key: u32) -> Option<&BvhNode>

Reference to the leaf associated to the given index at construction time.

pub fn total_memory_size(&self) -> usize

An approximation of the memory usage (in bytes) for this struct plus the memory it allocates dynamically.

pub fn heap_memory_size(&self) -> usize

An approximation of the memory dynamically-allocated by this struct.

pub fn subtree_depth(&self, node_id: u32) -> u32

The depth of the sub-tree rooted at the node with index node_id.

Set node_id to 0 to get the depth of the whole tree.

pub fn leaf_count(&self) -> u32

The number of leaves of this tree.

pub fn remove(&mut self, leaf_index: u32)

Deletes the leaf at the given index.

The operation is O(h) where h is the tree height (which, if optimized should be close to n log(n) where n is the leaf count). It will update the leaf counts and AABBs of all ancestors of the removed leaf.

impl Bvh

pub fn reachable_leaf_count(&self, id: u32) -> u32

Counts the number of leaves that can be reached from the node at index id.

This is mostly a utility for debugging.

pub fn changed_leaf_count(&self, id: u32) -> u32

Counts the number of leaves of self, starting with the subtree indexed at id, that are marked as changed.

This mostly a utility for debugging.

pub fn assert_well_formed(&self)

Panics if the tree isn’t well-formed.

The tree is well-formed if it is topologically correct (internal indices are all valid) and geometrically correct (node metadata of a parent bound the ones of the children).

Returns the calculated leaf count.

pub fn assert_well_formed_topology_only(&self)

Similar to Self::assert_well_formed but doesn’t check the geometry (i.e. it won’t check that parent AABBs enclose child AABBs).

This can be useful for checking intermediate states of the tree after topological changes but before refitting.

pub fn assert_is_depth_first(&self)

Panics if the nodes of self are not stored in depth-first order on its internal storage.

Depth-first ordering of self’s internals are guaranteed by Self::refit.

Trait Implementations

impl Clone for Bvh

fn clone(&self) -> Bvh

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Bvh

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Bvh

fn default() -> Bvh

Returns the “default value” for a type.