Struct Bvh

pub struct Bvh { /* private fields */ }

A Bounding Volume Hierarchy (BVH) for spatial queries and collision detection.

A BVH is a tree structure where each node contains an Axis-Aligned Bounding Box (AABB) that encloses all geometry in its subtree. Leaf nodes represent individual objects, while internal nodes partition space hierarchically. This enables efficient spatial queries by allowing entire subtrees to be culled during traversal.

What is a BVH and Why Use It?

A Bounding Volume Hierarchy organizes geometric objects (represented by their AABBs) into a binary tree. Each internal node’s AABB bounds the union of its two children’s AABBs. This hierarchical structure enables:

• Fast spatial queries: Ray casting, point queries, and AABB intersection tests
• Broad-phase collision detection: Quickly find potentially colliding pairs
• Efficient culling: Skip entire branches that don’t intersect query regions

Performance Benefits

Without a BVH, testing N objects against M queries requires O(N × M) tests. With a BVH, this reduces to approximately O(M × log N) for most queries, providing dramatic speedups for scenes with many objects:

• 1,000 objects: ~10x faster for ray casting
• 10,000 objects: ~100x faster for ray casting
• Critical for: Real-time applications (games, physics engines, robotics)

Structure

The BVH is a binary tree where:

• Leaf nodes: Contain references to actual geometry (via user-provided indices)
• Internal nodes: Contain two children and an AABB encompassing both
• Root: The top-level node encompassing the entire scene

Basic Usage - Static Scenes

For scenes where objects don’t move, build the BVH once and query repeatedly:

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

// Create AABBs for your objects
let objects = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)),
    Aabb::new(Point3::new(10.0, 0.0, 0.0), Point3::new(11.0, 1.0, 1.0)),
];

// Build the BVH - the index of each AABB becomes its leaf ID
let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &objects);

// Query which objects intersect a region
let query_region = Aabb::new(
    Point3::new(-1.0, -1.0, -1.0),
    Point3::new(2.0, 2.0, 2.0)
);

for leaf_id in bvh.intersect_aabb(&query_region) {
    println!("Object {} intersects the query region", leaf_id);
    // leaf_id corresponds to the index in the original 'objects' vec
}

Dynamic Scenes - Adding and Updating Objects

The BVH supports dynamic scenes where objects move or are added/removed:

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Add objects dynamically with custom IDs
bvh.insert(Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)), 100);
bvh.insert(Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)), 200);

// Update an object's position (by re-inserting with same ID)
bvh.insert(Aabb::new(Point3::new(0.5, 0.5, 0.0), Point3::new(1.5, 1.5, 1.0)), 100);

// Refit the tree after updates for optimal query performance
bvh.refit(&mut workspace);

// Remove an object
bvh.remove(200);

Ray Casting Example

Find the closest object hit by a ray:

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use parry3d::query::{Ray, RayCast};
use nalgebra::{Point3, Vector3};

let objects = vec![
    Aabb::new(Point3::new(0.0, 0.0, 5.0), Point3::new(1.0, 1.0, 6.0)),
    Aabb::new(Point3::new(0.0, 0.0, 10.0), Point3::new(1.0, 1.0, 11.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &objects);

// Cast a ray forward along the Z axis
let ray = Ray::new(Point3::new(0.5, 0.5, 0.0), Vector3::new(0.0, 0.0, 1.0));
let max_distance = 100.0;

// The BVH finds potentially intersecting leaves, then you test actual geometry
if let Some((leaf_id, hit_time)) = bvh.cast_ray(&ray, max_distance, |leaf_id, best_hit| {
    // Test ray against the actual geometry for this leaf
    // For this example, we test against the AABB itself
    let aabb = &objects[leaf_id as usize];
    aabb.cast_local_ray(&ray, best_hit, true)
}) {
    println!("Ray hit object {} at distance {}", leaf_id, hit_time);
    let hit_point = ray.point_at(hit_time);
    println!("Hit point: {:?}", hit_point);
}

Construction Strategies

Different build strategies offer trade-offs between build time and query performance:

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)),
];

// Binned strategy: Fast construction, good quality (recommended default)
let bvh_binned = Bvh::from_leaves(BvhBuildStrategy::Binned, &aabbs);

// PLOC strategy: Slower construction, best quality for ray-casting
// Use this for static scenes with heavy query workloads
let bvh_ploc = Bvh::from_leaves(BvhBuildStrategy::Ploc, &aabbs);

Maintenance for Dynamic Scenes

The BVH provides operations to maintain good performance as scenes change:

Refitting

After objects move, update the tree’s AABBs efficiently:

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Insert initial objects
bvh.insert(Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)), 0);
bvh.insert(Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)), 1);

// Simulate object movement every frame
for frame in 0..100 {
    let offset = frame as f32 * 0.1;
    bvh.insert(Aabb::new(
        Point3::new(offset, 0.0, 0.0),
        Point3::new(1.0 + offset, 1.0, 1.0)
    ), 0);

    // Refit updates internal AABBs - very fast operation
    bvh.refit(&mut workspace);

    // Now you can query the BVH with updated positions
}

Incremental Optimization

For scenes with continuous movement, incrementally improve tree quality:

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Build initial tree
for i in 0..1000 {
    let aabb = Aabb::new(
        Point3::new(i as f32, 0.0, 0.0),
        Point3::new(i as f32 + 1.0, 1.0, 1.0)
    );
    bvh.insert(aabb, i);
}

// In your update loop:
for frame in 0..100 {
    // Update object positions...

    bvh.refit(&mut workspace);

    // Incrementally optimize tree quality (rebuilds small parts of tree)
    // Call this every few frames, not every frame
    if frame % 5 == 0 {
        bvh.optimize_incremental(&mut workspace);
    }
}

Typical Workflows

Static Scene (Build Once, Query Many Times)

1. Create AABBs for all objects
2. Build BVH with from_leaves
3. Query repeatedly (ray casting, intersection tests, etc.)

Dynamic Scene (Objects Move)

1. Build initial BVH or start empty
2. Each frame:
   • Update positions with insert
   • Call refit to update tree AABBs
   • Perform queries
3. Occasionally call optimize_incremental (every 5-10 frames)

Fully Dynamic (Objects Added/Removed)

1. Start with empty BVH
2. Add objects with insert as they’re created
3. Remove objects with remove as they’re destroyed
4. Call refit after batch updates
5. Call optimize_incremental periodically

Performance Tips

• Reuse BvhWorkspace: Pass the same workspace to multiple operations to avoid allocations
• Batch updates: Update many leaves, then call refit once instead of refitting after each update
• Optimize periodically: Call optimize_incremental every few frames for highly dynamic scenes, not every frame
• Choose right strategy: Use Binned for most cases, PLOC for static scenes with heavy ray-casting
• Use insert_or_update_partially: For bulk updates followed by a single refit

Complexity

• Construction: O(n log n) where n is the number of leaves
• Query (average): O(log n) for well-balanced trees
• Insert: O(log n) average
• Remove: O(log n) average
• Refit: O(n) but very fast (just updates AABBs)
• Memory: ~64 bytes per pair of children (3D f32 SIMD), O(n) total

See Also

• BvhBuildStrategy - Choose construction algorithm (Binned vs PLOC)
• BvhWorkspace - Reusable workspace to avoid allocations
• BvhNode - Individual tree nodes with AABBs

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 new leaf into the BVH or updates an existing one.

If a leaf with the given leaf_index already exists in the tree, its AABB is updated to the new value and the tree’s internal nodes are adjusted to maintain correctness. If the leaf doesn’t exist, it’s inserted into an optimal position based on the Surface Area Heuristic (SAH).

This operation automatically propagates AABB changes up the tree to maintain the invariant that each internal node’s AABB encloses all its descendants. For better performance when updating many leaves, consider using insert_or_update_partially followed by a single refit call.

Arguments

• aabb - The Axis-Aligned Bounding Box for this leaf
• leaf_index - A unique identifier for this leaf (typically an object ID)

Performance

• Insert new leaf: O(log n) average, O(n) worst case
• Update existing leaf: O(log n) for propagation up the tree

Examples

Adding new objects

use parry3d::partitioning::Bvh;
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();

// Insert objects with custom IDs
bvh.insert(Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)), 100);
bvh.insert(Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)), 200);
bvh.insert(Aabb::new(Point3::new(10.0, 0.0, 0.0), Point3::new(11.0, 1.0, 1.0)), 300);

assert_eq!(bvh.leaf_count(), 3);

Updating object positions

use parry3d::partitioning::Bvh;
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();

// Insert an object
bvh.insert(Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)), 42);

// Simulate the object moving - just insert with the same ID
bvh.insert(Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)), 42);

// The BVH still has only 1 leaf, but at the new position
assert_eq!(bvh.leaf_count(), 1);

Bulk updates with better performance

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Add initial objects
for i in 0..100 {
    let aabb = Aabb::new(
        Point3::new(i as f32, 0.0, 0.0),
        Point3::new(i as f32 + 1.0, 1.0, 1.0)
    );
    bvh.insert(aabb, i);
}

// For better performance on bulk updates, use insert_or_update_partially
// then refit once at the end
for i in 0..100 {
    let aabb = Aabb::new(
        Point3::new(i as f32 + 0.1, 0.0, 0.0),
        Point3::new(i as f32 + 1.1, 1.0, 1.0)
    );
    bvh.insert_or_update_partially(aabb, i, 0.0);
}
bvh.refit(&mut workspace); // Update tree in one pass

Notes

• Leaf indices can be any u32 value - they don’t need to be contiguous
• The same leaf index can only exist once in the tree
• For dynamic scenes, call this every frame for moving objects
• Consider calling refit or optimize_incremental periodically for best query performance

See Also

• insert_with_change_detection - Insert with margin for motion prediction
• insert_or_update_partially - Insert without propagation (faster for bulk updates)
• remove - Remove a leaf from the tree
• refit - Update tree after bulk modifications

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)

Incrementally improves tree quality after dynamic updates.

This method performs one step of tree optimization by rebuilding small portions of the BVH to maintain good query performance. As objects move around, the tree’s structure can become suboptimal even after refitting. This method gradually fixes these issues without the cost of rebuilding the entire tree.

What It Does

Each call optimizes:

• A small percentage of the tree (typically ~5% of leaves)
• The root region (periodically)
• Subtrees that have degraded the most

The optimization is incremental - it’s designed to be called repeatedly (e.g., every few frames) to continuously maintain tree quality without large frame-time spikes.

When to Use

Call optimize_incremental:

• Every 5-10 frames for highly dynamic scenes
• After many insert and remove operations
• When query performance degrades over time
• In physics engines, once per simulation step

Don’t call this:

• Every frame (too frequent - diminishing returns)
• For static scenes (not needed)
• Immediately after from_leaves (tree is already optimal)

Arguments

• workspace - A reusable workspace to avoid allocations. The same workspace can be shared across multiple BVH operations.

Performance

• Time: O(k log k) where k is the number of leaves optimized (~5% of total)
• Target: <1ms for trees with 10,000 leaves (on modern hardware)
• Spreads optimization cost over many frames
• Much cheaper than full rebuild (O(n log n))

Examples

In a game loop

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Add initial objects
for i in 0..1000 {
    let aabb = Aabb::new(
        Point3::new(i as f32, 0.0, 0.0),
        Point3::new(i as f32 + 1.0, 1.0, 1.0)
    );
    bvh.insert(aabb, i);
}

// Game loop
for frame in 0..1000 {
    // Update object positions every frame
    for i in 0..1000 {
        let time = frame as f32 * 0.016;
        let offset = (time * (i as f32 + 1.0)).sin() * 5.0;
        let aabb = Aabb::new(
            Point3::new(i as f32 + offset, 0.0, 0.0),
            Point3::new(i as f32 + offset + 1.0, 1.0, 1.0)
        );
        bvh.insert_or_update_partially(aabb, i, 0.0);
    }

    // Update AABBs every frame (fast)
    bvh.refit(&mut workspace);

    // Optimize tree quality every 5 frames (slower but important)
    if frame % 5 == 0 {
        bvh.optimize_incremental(&mut workspace);
    }

    // Perform queries (ray casts, collision detection, etc.)
}

Physics engine broad-phase

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Simulation loop
for step in 0..100 {
    // Physics update: integrate velocities, forces, etc.
    // Update BVH with new rigid body positions
    for body_id in 0..100 {
        let aabb = get_body_aabb(body_id);
        bvh.insert_or_update_partially(aabb, body_id, 0.0);
    }

    // Refit tree for new positions
    bvh.refit(&mut workspace);

    // Optimize tree quality once per step
    bvh.optimize_incremental(&mut workspace);

    // Broad-phase collision detection
    // let pairs = find_overlapping_pairs(&bvh);
    // ...
}

After many insertions/removals

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Dynamically add many objects over time
for i in 0..1000 {
    let aabb = Aabb::new(
        Point3::new(i as f32, 0.0, 0.0),
        Point3::new(i as f32 + 1.0, 1.0, 1.0)
    );
    bvh.insert(aabb, i);

    // Periodically optimize while building
    if i % 100 == 0 && i > 0 {
        bvh.optimize_incremental(&mut workspace);
    }
}

// Tree is now well-optimized despite incremental construction

How It Works

The method uses a sophisticated strategy:

1. Subtree Selection: Identifies small subtrees that would benefit most from rebuilding
2. Local Rebuild: Rebuilds selected subtrees using the binned construction algorithm
3. Root Optimization: Periodically optimizes the top levels of the tree
4. Rotation: Tracks changes and rotates subtrees incrementally

The optimization rotates through different parts of the tree on successive calls, ensuring the entire tree is eventually optimized.

Comparison with Full Rebuild

Operation	Time	When to Use
optimize_incremental	O(k log k), k ≈ 5% of n	Every few frames in dynamic scenes
from_leaves (rebuild)	O(n log n)	When tree is very poor or scene is static

Notes

• State persists across calls - each call continues from where the last left off
• Call frequency can be adjusted based on performance budget
• Complementary to refit - use both for best results
• The workspace stores optimization state between calls

See Also

• refit - Update AABBs after leaf movements (call more frequently)
• from_leaves - Full rebuild (for major scene changes)
• BvhWorkspace - Reusable workspace for operations

impl Bvh

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

Returns an iterator over all leaves whose AABBs intersect the given AABB.

This efficiently finds all objects in the scene that potentially overlap with a query region. It’s commonly used for:

• Finding objects in a specific area
• Broad-phase collision detection (find candidate pairs)
• Spatial queries (what’s near this position?)
• Frustum culling (what’s in the camera’s view?)

The iterator returns leaf indices corresponding to objects that were added to the BVH.

Arguments

• aabb - The axis-aligned bounding box to test for intersections

Returns

An iterator yielding u32 leaf indices for all leaves whose AABBs intersect the query AABB. The iteration order is depth-first through the tree.

Performance

• Time: O(log n) average case with good spatial locality
• Worst case: O(n) if the query AABB is very large
• Efficiently prunes entire subtrees that don’t intersect
• Zero allocations

Examples

Find objects in a region

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

// Create a scene with objects
let objects = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)),
    Aabb::new(Point3::new(10.0, 0.0, 0.0), Point3::new(11.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &objects);

// Query: which objects are near the origin?
let query_region = Aabb::new(
    Point3::new(-1.0, -1.0, -1.0),
    Point3::new(2.0, 2.0, 2.0)
);

for leaf_id in bvh.intersect_aabb(&query_region) {
    println!("Object {} is in the query region", leaf_id);
    // You can now test the actual geometry of objects[leaf_id]
}

Broad-phase collision detection

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let objects = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(0.5, 0.0, 0.0), Point3::new(1.5, 1.0, 1.0)),  // Overlaps first
    Aabb::new(Point3::new(10.0, 0.0, 0.0), Point3::new(11.0, 1.0, 1.0)), // Far away
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &objects);

// Find potential collision pairs
let mut collision_pairs = Vec::new();

for (i, aabb) in objects.iter().enumerate() {
    for leaf_id in bvh.intersect_aabb(aabb) {
        if leaf_id as usize > i {  // Avoid duplicate pairs
            collision_pairs.push((i as u32, leaf_id));
        }
    }
}

// collision_pairs now contains potential collision pairs
// Next step: narrow-phase test actual geometry

Frustum culling for rendering

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let scene_objects = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)),
    Aabb::new(Point3::new(100.0, 0.0, 0.0), Point3::new(101.0, 1.0, 1.0)), // Far away
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &scene_objects);

// Camera frustum as an AABB (simplified - real frustums are more complex)
let camera_frustum = Aabb::new(
    Point3::new(-10.0, -10.0, -10.0),
    Point3::new(10.0, 10.0, 10.0)
);

let mut visible_objects = Vec::new();
for leaf_id in bvh.intersect_aabb(&camera_frustum) {
    visible_objects.push(leaf_id);
}

// Only render visible_objects - massive performance win!
assert_eq!(visible_objects.len(), 2); // Far object culled

Finding neighbors for an object

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::{Aabb, BoundingVolume};
use nalgebra::Point3;

let objects = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(1.5, 0.0, 0.0), Point3::new(2.5, 1.0, 1.0)),
    Aabb::new(Point3::new(100.0, 0.0, 0.0), Point3::new(101.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &objects);

// Expand an object's AABB to find nearby objects
let search_radius = 2.0;
let expanded = objects[0].loosened(search_radius);

let mut neighbors = Vec::new();
for leaf_id in bvh.intersect_aabb(&expanded) {
    if leaf_id != 0 {  // Don't include the object itself
        neighbors.push(leaf_id);
    }
}

// neighbors contains objects within search_radius of object 0

Notes

• This only tests AABB-AABB intersection, which is conservative (may have false positives)
• For exact collision detection, test actual geometry after getting candidates
• The iterator is lazy - work is only done as you consume items
• Empty queries (no intersections) are very fast due to early pruning

See Also

• cast_ray - Ray casting queries
• project_point - Find closest point
• traverse - Custom traversal logic
• leaves - General leaf iteration with predicate

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 project_point_and_get_feature( &self, point: &Point<f32>, max_distance: f32, primitive_check: impl Fn(u32, f32) -> Option<(PointProjection, FeatureId)>, ) -> Option<(u32, (f32, (PointProjection, FeatureId)))>

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

Also returns the feature the point was projected on.

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)

Updates the BVH’s internal node AABBs after leaf changes.

Refitting ensures that every internal node’s AABB tightly encloses the AABBs of its children. This operation is essential after updating leaf positions with insert_or_update_partially and is much faster than rebuilding the entire tree.

In addition to updating AABBs, this method:

• Reorders nodes in depth-first order for better cache locality during queries
• Ensures leaf counts on each node are correct
• Propagates change flags from leaves to ancestors (for change detection)

When to Use

Call refit after:

• Bulk updates with insert_or_update_partially
• Any operation that modifies leaf AABBs without updating ancestor nodes
• When you want to optimize tree layout for better query performance

Don’t call refit after:

• Regular insert calls (they already update ancestors)
• remove calls (they already maintain tree validity)

Arguments

• workspace - A reusable workspace to avoid allocations. Can be shared across multiple BVH operations for better performance.

Performance

• Time: O(n) where n is the number of nodes
• Space: O(n) temporary storage in workspace
• Much faster than rebuilding the tree from scratch
• Essential for maintaining good query performance in dynamic scenes

Examples

After bulk updates

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Insert initial objects
for i in 0..100 {
    let aabb = Aabb::new(
        Point3::new(i as f32, 0.0, 0.0),
        Point3::new(i as f32 + 1.0, 1.0, 1.0)
    );
    bvh.insert(aabb, i);
}

// Update all objects without tree propagation (faster)
for i in 0..100 {
    let offset = 0.1;
    let aabb = Aabb::new(
        Point3::new(i as f32 + offset, 0.0, 0.0),
        Point3::new(i as f32 + 1.0 + offset, 1.0, 1.0)
    );
    bvh.insert_or_update_partially(aabb, i, 0.0);
}

// Now update the tree in one efficient pass
bvh.refit(&mut workspace);

In a game loop

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Game initialization - add objects
for i in 0..1000 {
    let aabb = Aabb::new(
        Point3::new(i as f32, 0.0, 0.0),
        Point3::new(i as f32 + 1.0, 1.0, 1.0)
    );
    bvh.insert(aabb, i);
}

// Game loop - update objects each frame
for frame in 0..100 {
    // Update physics, AI, etc.
    for i in 0..1000 {
        let time = frame as f32 * 0.016; // ~60 FPS
        let pos = time.sin() * 10.0;
        let aabb = Aabb::new(
            Point3::new(i as f32 + pos, 0.0, 0.0),
            Point3::new(i as f32 + pos + 1.0, 1.0, 1.0)
        );
        bvh.insert_or_update_partially(aabb, i, 0.0);
    }

    // Refit once per frame for all updates
    bvh.refit(&mut workspace);

    // Now perform collision detection queries...
}

With change detection margin

use parry3d::partitioning::{Bvh, BvhWorkspace};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let mut bvh = Bvh::new();
let mut workspace = BvhWorkspace::default();

// Add an object
let aabb = Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0));
bvh.insert(aabb, 0);

// Update with a margin - tree won't update if movement is small
let margin = 0.5;
let new_aabb = Aabb::new(Point3::new(0.1, 0.0, 0.0), Point3::new(1.1, 1.0, 1.0));
bvh.insert_or_update_partially(new_aabb, 0, margin);

// Refit propagates the change detection flags
bvh.refit(&mut workspace);

Comparison with refit_without_opt

This method reorganizes the tree in memory for better cache performance. If you only need to update AABBs without reordering, use refit_without_opt which is faster but doesn’t improve memory layout.

Notes

• Reuses the provided workspace to avoid allocations
• Safe to call even if no leaves were modified (just reorganizes tree)
• Does not change the tree’s topology, only AABBs and layout
• Call this before optimize_incremental for best results

See Also

• insert_or_update_partially - Update leaves without propagation
• refit_without_opt - Faster refit without memory reorganization
• optimize_incremental - Improve tree quality
• BvhWorkspace - Reusable workspace for operations

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)

Traverses the BVH in depth-first order with full control over traversal.

This method provides low-level control over tree traversal. For each node visited, it calls your closure which can decide whether to continue traversing, prune that subtree, or exit early.

Arguments

• check_node - A mutable closure called for each node. It receives a BvhNode and returns a TraversalAction to control the traversal:
  • Continue: Visit this node’s children (if not a leaf)
  • Prune: Skip this node’s subtree entirely
  • EarlyExit: Stop traversal immediately

Traversal Order

The tree is traversed in depth-first order:

1. Check current node with check_node
2. If Continue, descend into left child first
3. Then descend into right child
4. Backtrack when both subtrees are processed

This order is cache-friendly and matches the tree’s memory layout.

When to Use

Use traverse when you need:

• Mutable state during traversal
• Early exit conditions
• Full control over pruning decisions
• Custom query logic that doesn’t fit standard patterns

For simpler cases, consider:

• leaves - Iterator over leaves matching a predicate
• intersect_aabb - Find leaves intersecting an AABB
• cast_ray - Ray casting queries

Performance

• Best case: O(log n) when pruning effectively
• Worst case: O(n) when visiting all nodes
• Cache-friendly due to depth-first order
• No allocations beyond a small stack (~32 entries)

Examples

Count leaves in a region

use parry3d::partitioning::{Bvh, BvhBuildStrategy, TraversalAction};
use parry3d::bounding_volume::{Aabb, BoundingVolume};
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)),
    Aabb::new(Point3::new(10.0, 0.0, 0.0), Point3::new(11.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

let query_region = Aabb::new(
    Point3::new(-1.0, -1.0, -1.0),
    Point3::new(7.0, 2.0, 2.0)
);

let mut count = 0;
bvh.traverse(|node| {
    if !node.aabb().intersects(&query_region) {
        // Prune: this entire subtree is outside the region
        return TraversalAction::Prune;
    }

    if node.is_leaf() {
        count += 1;
    }

    TraversalAction::Continue
});

assert_eq!(count, 2); // First two objects intersect the region

Find first leaf matching a condition

use parry3d::partitioning::{Bvh, BvhBuildStrategy, TraversalAction};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)),
    Aabb::new(Point3::new(10.0, 0.0, 0.0), Point3::new(11.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

let target_point = Point3::new(5.5, 0.5, 0.5);
let mut found_leaf = None;

bvh.traverse(|node| {
    if !node.aabb().contains_local_point(&target_point) {
        return TraversalAction::Prune;
    }

    if let Some(leaf_id) = node.leaf_data() {
        found_leaf = Some(leaf_id);
        return TraversalAction::EarlyExit; // Found it, stop searching
    }

    TraversalAction::Continue
});

assert_eq!(found_leaf, Some(1));

Collect statistics with mutable state

use parry3d::partitioning::{Bvh, BvhBuildStrategy, TraversalAction};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)),
    Aabb::new(Point3::new(4.0, 0.0, 0.0), Point3::new(5.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

let mut stats = (0, 0); // (num_internal_nodes, num_leaves)

bvh.traverse(|node| {
    if node.is_leaf() {
        stats.1 += 1;
    } else {
        stats.0 += 1;
    }
    TraversalAction::Continue
});

assert_eq!(stats.1, 3); // 3 leaves

Notes

• The closure is called for every visited node (internal and leaf)
• Pruning a node skips all its descendants
• Use node.is_leaf() to distinguish leaves from internal nodes
• Use node.leaf_data() to get the leaf’s index (returns None for internal nodes)
• The traversal uses a small fixed-size stack internally

See Also

• leaves - Simpler iterator interface for leaf traversal
• intersect_aabb - Specialized AABB intersection query
• cast_ray - Ray casting with best-first traversal
• TraversalAction - Controls traversal flow

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

Creates an empty BVH with no leaves.

This is equivalent to Bvh::default() but more explicit. Use this when you plan to incrementally build the tree using insert, or when you need an empty placeholder BVH.

Example

use parry3d::partitioning::Bvh;

let bvh = Bvh::new();
assert!(bvh.is_empty());
assert_eq!(bvh.leaf_count(), 0);

See Also

• from_leaves - Build from AABBs
• from_iter - Build from an iterator

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

Creates a new BVH from a slice of AABBs.

Each AABB in the slice becomes a leaf in the BVH. The leaf at index i in the slice will have leaf data i, which can be used to identify which object a query result refers to.

Arguments

• strategy - The construction algorithm to use (see BvhBuildStrategy)
• leaves - Slice of AABBs, one for each object in the scene

Returns

A new Bvh containing all the leaves organized in a tree structure.

Performance

• Time: O(n log n) where n is the number of leaves
• Space: O(n) additional memory during construction

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)),
    Aabb::new(Point3::new(4.0, 0.0, 0.0), Point3::new(5.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::Binned, &aabbs);

assert_eq!(bvh.leaf_count(), 3);
// Leaf 0 corresponds to aabbs[0], leaf 1 to aabbs[1], etc.

See Also

• from_iter - Build from an iterator with custom indices
• BvhBuildStrategy - Choose construction algorithm

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

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

Creates a new BVH from an iterator of (index, AABB) pairs.

This is more flexible than from_leaves as it allows you to provide custom leaf indices. This is useful when your objects don’t have contiguous indices, or when you want to use sparse IDs.

Arguments

• strategy - The construction algorithm to use (see BvhBuildStrategy)
• leaves - Iterator yielding (index, aabb) pairs

Returns

A new Bvh containing all the leaves organized in a tree structure.

Notes

• Indices are stored internally as u32, but the iterator accepts usize for convenience
• You can use .enumerate() directly on an AABB iterator
• Indices larger than u32::MAX will overflow

Performance

• Time: O(n log n) where n is the number of leaves
• Space: O(n) additional memory during construction

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

// Create a BVH with custom indices
let leaves = vec![
    (10, Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0))),
    (20, Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0))),
    (30, Aabb::new(Point3::new(4.0, 0.0, 0.0), Point3::new(5.0, 1.0, 1.0))),
];

let bvh = Bvh::from_iter(BvhBuildStrategy::Binned, leaves.into_iter());

assert_eq!(bvh.leaf_count(), 3);
// Leaf data will be 10, 20, 30 instead of 0, 1, 2

See Also

• from_leaves - Simpler version with automatic indices
• BvhBuildStrategy - Choose construction algorithm

pub fn root_aabb(&self) -> Aabb

Returns the AABB that bounds all geometry in this BVH.

This is the AABB of the root node, which encompasses all leaves in the tree. For an empty BVH, returns an invalid AABB (with mins > maxs).

Returns

An Aabb that contains all objects in the BVH.

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::{Aabb, BoundingVolume};
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(5.0, 0.0, 0.0), Point3::new(6.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);
let root_aabb = bvh.root_aabb();

// Root AABB contains both leaves
assert!(root_aabb.contains(&aabbs[0]));
assert!(root_aabb.contains(&aabbs[1]));

See Also

• is_empty - Check if BVH has no leaves

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

Scales all AABBs in the tree by the given factors.

This multiplies all AABB coordinates (mins and maxs) by the corresponding components of the scale vector. This is useful when scaling an entire scene or changing coordinate systems.

Arguments

• scale - Per-axis scale factors (must all be positive)

Panics

This function has undefined behavior if any scale component is negative or zero. Always use positive scale values.

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::{Point3, Vector3};

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
];

let mut bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

// Scale by 2x on all axes
bvh.scale(&Vector3::new(2.0, 2.0, 2.0));

let root = bvh.root_aabb();
assert_eq!(root.maxs, Point3::new(2.0, 2.0, 2.0));

See Also

• BvhNode::scale - Scale a single node

pub fn is_empty(&self) -> bool

Returns true if this BVH contains no leaves.

An empty BVH has no geometry and cannot be queried meaningfully.

Returns

true if the BVH is empty, false otherwise.

Example

use parry3d::partitioning::Bvh;

let empty_bvh = Bvh::new();
assert!(empty_bvh.is_empty());

See Also

• leaf_count - Get the number of leaves

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

Returns a reference to the leaf node with the given index.

The leaf_key is the index that was provided when constructing the BVH (either the position in the slice for from_leaves, or the custom index for from_iter).

Arguments

• leaf_key - The leaf index to look up

Returns

• Some(&BvhNode) if a leaf with that index exists
• None if no leaf with that index exists

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

// Leaf 0 exists (from aabbs[0])
assert!(bvh.leaf_node(0).is_some());

// Leaf 1 doesn't exist
assert!(bvh.leaf_node(1).is_none());

See Also

• remove - Remove a leaf by index

pub fn total_memory_size(&self) -> usize

Estimates the total memory usage of this BVH in bytes.

This includes both the stack size of the Bvh struct itself and all heap-allocated memory (node arrays, parent indices, leaf index maps).

Returns

Approximate memory usage in bytes.

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs: Vec<_> = (0..100)
    .map(|i| {
        let f = i as f32;
        Aabb::new(Point3::new(f, 0.0, 0.0), Point3::new(f + 1.0, 1.0, 1.0))
    })
    .collect();

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

println!("BVH memory usage: {} bytes", bvh.total_memory_size());

See Also

• heap_memory_size - Only heap-allocated memory

pub fn heap_memory_size(&self) -> usize

Estimates the heap-allocated memory usage of this BVH in bytes.

This only counts dynamically allocated memory (nodes, indices, etc.) and excludes the stack size of the Bvh struct itself.

Returns

Approximate heap memory usage in bytes.

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs: Vec<_> = (0..100)
    .map(|i| {
        let f = i as f32;
        Aabb::new(Point3::new(f, 0.0, 0.0), Point3::new(f + 1.0, 1.0, 1.0))
    })
    .collect();

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

println!("BVH heap memory: {} bytes", bvh.heap_memory_size());

See Also

• total_memory_size - Total memory including stack

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

Computes the depth of the subtree rooted at the specified node.

The depth is the number of levels from the root to the deepest leaf. A single node has depth 1, a node with two leaf children has depth 2, etc.

Arguments

• node_id - The index of the root node of the subtree (use 0 for the entire tree)

Returns

The depth of the subtree, or 0 for an empty tree.

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs: Vec<_> = (0..4)
    .map(|i| {
        let f = i as f32;
        Aabb::new(Point3::new(f, 0.0, 0.0), Point3::new(f + 1.0, 1.0, 1.0))
    })
    .collect();

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);

// Get depth of entire tree
let depth = bvh.subtree_depth(0);
assert!(depth >= 2); // At least 2 levels with 4 leaves

See Also

• leaf_count - Number of leaves in the tree

pub fn leaf_count(&self) -> u32

Returns the number of leaves in this BVH.

Each leaf represents one geometric object that was provided during construction or added via insert.

Returns

The total number of leaves in the tree.

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)),
    Aabb::new(Point3::new(4.0, 0.0, 0.0), Point3::new(5.0, 1.0, 1.0)),
];

let bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);
assert_eq!(bvh.leaf_count(), 3);

See Also

• is_empty - Check if the tree has no leaves

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

Removes a leaf from the BVH.

This removes the leaf with the specified index and updates the tree structure accordingly. The sibling of the removed leaf moves up to take its parent’s place, and all ancestor AABBs and leaf counts are updated.

Arguments

• leaf_index - The index of the leaf to remove (the same index used when constructing)

Performance

• Time: O(h) where h is the tree height (typically O(log n))
• Updates AABBs and leaf counts for all ancestors of the removed leaf
• For heavily unbalanced trees, consider rebuilding or rebalancing after many removals

Notes

• If the leaf doesn’t exist, this is a no-op
• Removing the last leaf results in an empty BVH
• The tree structure remains valid after removal

Example

use parry3d::partitioning::{Bvh, BvhBuildStrategy};
use parry3d::bounding_volume::Aabb;
use nalgebra::Point3;

let aabbs = vec![
    Aabb::new(Point3::origin(), Point3::new(1.0, 1.0, 1.0)),
    Aabb::new(Point3::new(2.0, 0.0, 0.0), Point3::new(3.0, 1.0, 1.0)),
    Aabb::new(Point3::new(4.0, 0.0, 0.0), Point3::new(5.0, 1.0, 1.0)),
];

let mut bvh = Bvh::from_leaves(BvhBuildStrategy::default(), &aabbs);
assert_eq!(bvh.leaf_count(), 3);

// Remove the middle leaf
bvh.remove(1);
assert_eq!(bvh.leaf_count(), 2);

// Leaf 1 no longer exists
assert!(bvh.leaf_node(1).is_none());

See Also

• insert - Add a new leaf to the BVH
• refit - Update AABBs after leaf movements
• optimize_incremental - Improve tree quality

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.