Struct DynamicBvh 

pub struct DynamicBvh { /* private fields */ }

Dynamic AABB Tree (DBVT) for broadphase collision detection.

Supports incremental insert, remove, and update operations. Uses the surface-area heuristic (SAH) to choose the best sibling when inserting a new leaf.

Implementations

impl DynamicBvh

pub fn new() -> Self

Create a new, empty dynamic BVH.

pub fn insert(&mut self, aabb: BvhAabb, data: u32) -> usize

Insert a leaf AABB with associated data. Returns the leaf node index.

The leaf is stored with a fat AABB (expanded by FAT_MARGIN) to reduce the frequency of re-insertions when the object moves slightly.

pub fn remove(&mut self, leaf: usize)

Remove a leaf node by its index.

Panics

Panics if leaf is not a leaf node.

pub fn update(&mut self, leaf: usize, new_aabb: BvhAabb) -> bool

Update an existing leaf’s AABB.

If new_aabb still fits within the leaf’s current fat AABB, the tree is unchanged and false is returned. Otherwise the leaf is removed and reinserted with a fresh fat AABB, and true is returned.

pub fn query_overlapping_pairs(&self) -> Vec<(u32, u32)>

Return all leaf-data pairs (a, b) where a < b and the leaves overlap. Uses a stack-based traversal.

pub fn query_aabb(&self, aabb: &BvhAabb) -> Vec<u32>

Return the data of all leaves whose fat AABB overlaps aabb.

pub fn query_point(&self, point: Vec3) -> Vec<u32>

Return the data of all leaves whose fat AABB contains point.

pub fn n_leaves(&self) -> usize

Number of leaf nodes currently in the tree.

pub fn n_nodes(&self) -> usize

Total number of nodes (leaves + internal) currently in the tree.

pub fn height(&self) -> i32

Height of the tree (0 for empty, 0 for a single leaf).

pub fn validate(&self) -> bool

Validate tree invariants. Returns true if the tree is consistent.

Checks:

• root has no parent
• all parent/child pointers are consistent
• internal node AABBs contain both children’s AABBs

impl DynamicBvh

pub fn stats(&self) -> DbvtStats

Collect tree statistics.

pub fn refit_all(&mut self)

Refit all internal-node AABBs from leaves upward (full refit pass).

Useful after bulk updates.

pub fn ray_cast( &self, origin: Vec3, dir: Vec3, t_min: f64, t_max: f64, ) -> Vec<(u32, f64)>

Ray cast against all leaves; returns data of all leaves hit.

origin + dir * t for t ∈ [t_min, t_max].

pub fn query_aabb_filtered( &self, aabb: &BvhAabb, filter: impl Fn(u32) -> bool, ) -> Vec<u32>

Overlap query: return data of all leaves that overlap query_aabb and whose data value satisfies filter.

This is an enhanced version of query_aabb that supports a predicate.

pub fn insert_bulk(&mut self, items: &[(BvhAabb, u32)]) -> Vec<usize>

Bulk insert many (aabb, data) pairs and return their leaf indices.

pub fn clear(&mut self)

Remove all leaves and reset the tree to empty.

pub fn all_leaf_data(&self) -> Vec<u32>

Collect all leaf data values in the tree (arbitrary order).

pub fn query_pairs_with_stats(&self) -> (Vec<(u32, u32)>, DbvtStats)

Count overlapping pairs and return both the pairs and stats.

impl DynamicBvh

pub fn quality_metrics(&self) -> Option<BvhQuality>

Compute BVH quality metrics via a single DFS traversal.

Returns None if the tree is empty.

pub fn quality_degraded(&self, threshold: f64) -> bool

Return true if the SAH cost is above threshold (tree quality degraded).

Useful as a trigger to rebuild the tree from scratch.

impl DynamicBvh

pub fn frustum_query(&self, frustum: &BvhFrustum) -> Vec<u32>

Return the data of all leaves potentially visible inside frustum.

Uses a stack-based traversal that prunes subtrees whose AABB is fully outside any frustum plane.

impl DynamicBvh

pub fn k_nearest(&self, point: Vec3, k: usize) -> Vec<NearestLeaf>

Return the k closest leaves (by AABB-center distance) to point.

Result is sorted nearest-first.

impl DynamicBvh

pub fn serialize(&self) -> Vec<f64>

Serialize the entire tree into a flat Vecf64`.

Format per node (14 values): \[min_x, min_y, min_z, max_x, max_y, max_z, parent_or_neg1, left_or_neg1, right_or_neg1, data_or_neg1, height, is_leaf, is_on_free_list, PADDING]

The first element of the buffer is the total number of nodes (as f64).

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

Return the root node index, or None if the tree is empty.

impl DynamicBvh

pub fn move_proxy( &mut self, leaf: usize, new_aabb: BvhAabb, velocity: Vec3, dt: f64, ) -> bool

Update leaf leaf using a new tight AABB expanded in the direction of velocity * dt (speculative / predicted motion).

The resulting fat AABB covers both the current and predicted positions. Returns true if the tree was modified (re-insertion occurred).

impl DynamicBvh

pub fn try_rotate(&mut self, idx: usize) -> bool

Attempt one SAH-improving rotation at node idx.

Tries swapping each grandchild with its uncle; keeps the swap only if it strictly reduces the total surface area of the two affected internal nodes.

Returns true if a rotation was performed.

pub fn optimize_rotations(&mut self)

Perform one bottom-up pass of SAH-improving rotations across the tree.

Visits every non-leaf node from leaves upward and attempts try_rotate.

impl DynamicBvh

pub fn refit_leaf_ancestors(&mut self, leaf: usize)

Refit only the ancestors of a specific leaf node.

More efficient than refit_all when only one leaf changed.

pub fn update_leaf_inplace(&mut self, leaf: usize, new_aabb: BvhAabb)

Update a leaf’s AABB in place without re-inserting it, then refit its ancestor chain.

Only use this when new_aabb is contained within the current fat AABB; otherwise the tree’s AABBs may become incorrect. For unconstrained moves use DynamicBvh::update or DynamicBvh::move_proxy.

pub fn sah_cost(&self) -> f64

Compute the total SAH cost of the tree as a single scalar.

Defined as sum(SA(internal_node)) / SA(root). Lower is better; returns 0.0 for trees with 0 or 1 nodes.

impl DynamicBvh

pub fn compute_sah_cost(&self) -> f64

Compute the Surface Area Heuristic (SAH) cost of the entire tree.

This is an alias for DynamicBvh::sah_cost provided under the name requested by the algorithm expansion spec so that callers can use either name without changing existing code.

Returns 0.0 for an empty or degenerate tree.

pub fn balance_rotation(&mut self) -> usize

Apply one round of balance-improving rotations to the entire tree.

Walks every internal node in bottom-up order and attempts a single SAH-improving swap (see try_rotate). Nodes are visited from shallowest to deepest so that parent improvements propagate before children are processed.

Returns the number of rotations that were accepted.

pub fn traverse_frustum(&self, frustum: &BvhFrustum) -> Vec<u32>

Frustum-culling traversal: return data of all leaves whose fat AABB is potentially inside frustum.

This is a named alias for frustum_query following the algorithm expansion spec. Uses a stack-based traversal that prunes fully-outside subtrees for O(k + log n) complexity where k is the number of hits.

impl DynamicBvh

pub fn node_depth(&self, idx: usize) -> Option<usize>

Return the depth of a given node in the tree (root = 0).

Returns None if idx is on the free list.

pub fn find_leaf(&self, target: u32) -> Option<usize>

Return the leaf node index whose data matches target, or None.

pub fn leaf_data_preorder(&self) -> Vec<u32>

Collect all leaf data in DFS pre-order (left-first).

pub fn root_aabb(&self) -> Option<BvhAabb>

Return the AABB of the root node, or None if the tree is empty.

pub fn max_depth(&self) -> usize

Compute the maximum tree depth by traversal.

pub fn n_internal(&self) -> usize

Return the number of internal nodes (non-leaf, non-free).

impl DynamicBvh

pub fn query_sphere(&self, center: Vec3, radius: f64) -> Vec<u32>

Return data of all leaves whose fat AABB overlaps a sphere defined by center and radius.

Uses the AABB-vs-sphere test: the sphere overlaps an AABB iff the squared distance from center to the nearest point on the AABB is ≤ radius².

pub fn any_in_sphere(&self, center: Vec3, radius: f64) -> bool

Return true if any leaf’s fat AABB overlaps the given sphere.

impl DynamicBvh

pub fn query_capsule(&self, capsule: BvhCapsule) -> Vec<u32>

Return data of all leaves whose fat AABB is hit by a capsule query.

Implemented as AABB-vs-segment-distance test: an AABB intersects the capsule iff the minimum distance from the AABB to the line segment is ≤ capsule.radius.

impl DynamicBvh

pub fn rebuild(&mut self)

Rebuild the tree from scratch using the current fat AABBs of all leaves.

Removes all nodes, collects leaf data and AABBs, then re-inserts them. This is a full O(n log n) rebuild; use only when the tree is severely degraded (e.g. after many updates without rotations).

pub fn leaf_snapshot(&self) -> Vec<(u32, BvhAabb)>

Return a snapshot of all leaf (data, fat_aabb) pairs without modifying the tree.

pub fn leaf_aabb(&self, idx: usize) -> Option<BvhAabb>

Return the fat AABB for a given leaf idx, or None if it is not a valid leaf.

pub fn remove_where(&mut self, pred: impl Fn(u32) -> bool) -> usize

Remove all leaves whose data value satisfies pred.

Returns the number of leaves removed.

pub fn relabel_leaf(&mut self, leaf: usize, new_data: u32) -> bool

Replace the data value of a leaf without changing its AABB.

Returns true if the leaf was found and updated.

impl DynamicBvh

pub fn subtree_leaf_count(&self, idx: usize) -> usize

Return the number of leaves in the subtree rooted at idx.

pub fn validate_heights(&self) -> bool

Return true if the heights stored in nodes are consistent with the actual tree structure.

Trait Implementations

impl Default for DynamicBvh

fn default() -> Self

Returns the “default value” for a type.