Crate ploc_bvh

source ·
Expand description

§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 bevy_math::{bounding::{Aabb3d, RayCast3d}, prelude::{Dir3, 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 = Dir3::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:

at your option.

Modules§

  • A module with implementations for 2D support
  • A crate implementing 3D support for the BVH
  • The prelude, exporting all the necessary things to get started
  • A module with generic logic for traversing the BVH

Structs§

  • A generic BVH, can support any dimension that gets an implementation.
  • An item in the BHV
  • A node on the BVH

Traits§

  • A generic bounding volume supported by the BVH. Adds a few extra methods on top of bevy’s BoundingVolume trait