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 Iterator
s.
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:
- 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.
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