ploc-bvh

A Bounding Volume Hierarchy based on PLOC. Inspired by a series of articles by Arsène Pérard-Gayot

This crate uses the BoundingVolume and IntersectsVolume traits from bevy_math for most of its functionality. Since bevy_math does not depend on the rest of the bevy engine, it can be used in non-bevy projects too.

A BVH can be constructed using any type that implements bevy_math's BoundingVolumes and this crate's BvhVolume, some type aliases are provided for bevy_math's built-in types, these can be found in the prelude or the dim2/dim3 modules. The BVH can be traversed using any type that implements bevy_math's IntersectsVolume, some types for this are provided by bevy_math, including for overlap between built-in volumes, ray casting, and casting volumes.

Getting started

Creating and traversing the BVH can be entirely done using Iterators.

In this example we create AABBs for a few boxes, and use their index as the key, then travese the BVH:

# use ploc_bvh::prelude::*;
use bevy_math::{bounding::{Aabb3d, RayCast3d}, prelude::{Direction3d, Vec3}};

// We have some list of axis-aligned bounding boxes
let boxes = [
    Aabb3d::new(Vec3::ONE, Vec3::ONE),
    Aabb3d::new(Vec3::NEG_Y, Vec3::splat(2.)),
];

// We build a 3D BVH using the number of boxes, and an iterator of (T, Aabb3d).
// T can be whatever type we need, but it most likely includes some identifier,
// and maybe some information to filter results quickly.
let bvh = BvhAabb3d::new(
    boxes.len(),
    // We use the index of the box as our T here, so we can find it later
    boxes.iter().enumerate().map(|(i, aabb)| (i, *aabb)),
);

// Next we want to traverse the BVH, to do this we need a stack and an intersection test.

// We can create a stack, this type can be reused to save some allocs if necessary.
let mut stack = bvh.create_stack();

// We construct a bounding volume intersection test, a raycast in this case
let origin = Vec3::ZERO;
let direction = Direction3d::Y;
let max_time_of_impact = 1.;
let ray_cast = RayCast3d::new(origin, direction, max_time_of_impact);

// Now we can iterate over the BVH using the `traverse` method
for &index in bvh.traverse(&mut stack, ray_cast) {
    // The value returned from `traverse` matches the T used when constructing the BVH
    println!("We hit box {}: {:?}", index, boxes[index]);
}

Future work

• Actually support the parallelization

Licensing

All code in this repository is dual-licensed under either:

• MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)
• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)

at your option.