Struct Bvh 

pub struct Bvh { /* private fields */ }

Bounding volume hierarchy over the alive triangles of one Mesh, in mesh-local coordinates. Keep it current with Bvh::update.

Implementations

impl Bvh

pub fn root(&self) -> Option<NodeId>

The root node, or None for an empty tree.

pub fn node(&self, id: NodeId) -> NodeView<'_>

The bounds and contents of id. id must come from this BVH and not predate its last modification; otherwise this may panic or return unrelated data.

pub fn parent(&self, id: NodeId) -> Option<NodeId>

The parent of id, or None for the root.

pub fn traverse(&self, visit: impl FnMut(NodeId, &NodeView<'_>) -> bool)

Visits the tree in depth-first pre-order (left child first), without a stack. visit returns whether to descend into the node’s children (ignored for leaves).

pub fn traverse_ordered( &self, first_is_left: impl Fn(&Aabb, &Aabb) -> bool, visit: impl FnMut(NodeId, &NodeView<'_>) -> bool, )

Like Bvh::traverse, but at each inner node first_is_left gets the left and right child bounds and says whether the left child is visited first. It must be pure: it may be called more than once per node, and an impure predicate (one that gives different answers for the same bounds) can make the traversal skip subtrees or loop forever. It is still memory-safe.

pub fn traverse_by_key<K: Copy + PartialOrd>( &self, key: impl FnMut(&Aabb) -> Option<K>, visit: impl FnMut(NodeId, &NodeView<'_>, K) -> bool, )

Visits the tree depth-first, nearest first: of two children, the one with the smaller key is visited first (the left one on equal keys, or when the keys do not compare).

key maps a node’s bounds to its key; a child whose key is None is skipped together with its subtree, and so is the root. visit gets the node, its view and its key, and returns whether to descend into its children (ignored for leaves).

key is evaluated once per node, when its parent is expanded (the root first). The traversal never allocates on the heap and never fails: it keeps up to [TRAVERSE_STACK] pending nodes in a fixed array, and a subtree that does not fit is finished at once by a parent-link walk, in the same order, where key may be evaluated more than once per node. So key should be pure; an impure one there can skip subtrees or loop forever, though it stays memory-safe.

pub fn traverse_from( &self, root: NodeId, visit: impl FnMut(NodeId, &NodeView<'_>) -> bool, )

Visits the subtree rooted at root in depth-first pre-order (left child first), without a stack. visit returns whether to descend into the node’s children (ignored for leaves). root must come from this BVH and not predate its last modification; otherwise this may panic or visit unrelated nodes.

pub fn node_slots(&self) -> usize

Number of node slots in storage, garbage included: every NodeId::index is below it.

pub fn generation(&self) -> u64

Counter that changes whenever nodes, boxes, refs or layout change (build, update, refit, rebuild, compaction), so per-node data keyed by NodeId::index can detect that it went stale. Values are unique across all BVHs in this process, so a replacement tree never shares one with an earlier tree.

pub fn mesh_uid(&self) -> u64

The uid of the mesh this BVH was built for (see Mesh::uid).

impl Bvh

pub fn build(mesh: &Mesh, options: &BuildOptions) -> Result<Bvh>

Builds a BVH over the alive triangles of mesh.

pub fn set_policy(&mut self, policy: UpdatePolicy) -> Result<()>

Replaces the update policy (see Bvh::update).

pub fn options(&self) -> &BuildOptions

pub fn policy(&self) -> &UpdatePolicy

pub fn revision(&self) -> u64

The mesh revision this BVH matches (see Mesh::revision). Manual Bvh::refit and Bvh::rebuild_region calls do not change it.

pub fn is_current(&self, mesh: &Mesh) -> bool

True when the BVH matches the mesh’s current revision (and the mesh has not been compacted since).

pub fn subtree_triangles(&self, id: NodeId) -> usize

The triangles in the subtree of id: exact, kept up to date by builds, updates and compactions (refits change none). Lets a caller bound the work of a subtree on any tree, balanced or not.

As for Bvh::node, id must come from this BVH and not predate its last modification.

Panics

When id is past the BVH’s nodes (an id from another BVH, or from before a compaction); an id that is in range but stale gives an unrelated count.

pub fn query_aabb( &self, mesh: &Mesh, min: [f32; 3], max: [f32; 3], out: &mut Vec<TriangleId>, )

Appends every alive triangle whose bounding box overlaps the box [min, max] (touching counts), in no particular order.

The BVH must be current for mesh (Bvh::is_current); a stale tree may return wrong results or panic.

pub fn node_count(&self) -> usize

Reachable nodes.

pub fn treelet_count(&self) -> usize

pub fn root_bounds(&self) -> Option<Aabb>

Bounds of all triangles, or None for an empty tree.

pub fn depth(&self) -> usize

Longest root-to-leaf path, counting nodes (0 for an empty tree).

pub fn byte_size(&self) -> usize

Heap memory held by the BVH, garbage included.

pub fn validate(&self, mesh: &Mesh) -> Result<(), String>

Checks every structural invariant against mesh. Meant for tests and debugging; returns a description of the first violation.

impl Bvh

pub fn update( &mut self, mesh: &mut Mesh, changes: &ChangeSet, ) -> Result<UpdateReport>

Brings the BVH up to date with mesh, given the ChangeSets of every commit, undo and redo since the BVH last matched (merge them when there are several). Builds the mesh’s incidence index when vertices moved.

Chooses the cheapest correct strategy: refit for moves, treelet rebuilds for local topology changes, a full rebuild when more than UpdatePolicy::full_rebuild_fraction of the triangles are dirty. On error the BVH is unchanged.

When the BVH already matches the mesh’s revision, changes is ignored and the result is Strategy::Unchanged, so applying a change set twice is harmless. When the mesh was compacted since the last full build (Mesh::epoch changed), every slot id is stale and the tree is rebuilt from scratch (Strategy::Full) whatever changes says.

pub fn refit(&mut self, mesh: &Mesh, triangles: &[TriangleId]) -> Result<()>

Recomputes the boxes of the leaves holding triangles and their ancestors.

If the mesh was compacted since the last full build (Mesh::epoch changed), slot ids are stale, so this rebuilds the whole tree instead (like Bvh::rebuild, which also records the mesh revision). On error the BVH is unchanged.

pub fn rebuild_region( &mut self, mesh: &Mesh, triangles: &[TriangleId], ) -> Result<()>

Rebuilds the treelets containing triangles from their current contents (triangles that died since are dropped).

If the mesh was compacted since the last full build (Mesh::epoch changed), slot ids are stale, so this rebuilds the whole tree instead (like Bvh::rebuild, which also records the mesh revision). Memory for every affected treelet is reserved before the first one is rebuilt, so on error the BVH is unchanged.

pub fn rebuild(&mut self, mesh: &Mesh) -> Result<()>

Rebuilds the whole tree from mesh. On error the BVH is unchanged.

Trait Implementations

impl Debug for Bvh

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

Formats the value using the given formatter.