### 3 releases (breaking)

0.2.0 | Jul 8, 2024 |
---|---|

0.1.0 | Mar 6, 2024 |

0.0.1 | Nov 16, 2023 |

#**412** in Game dev

**34** downloads per month

**MIT/Apache**

25KB

535 lines

# 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

and `BoundingVolume`

traits from `IntersectsVolume`

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.`bevy_math`

A BVH can be constructed using any type that implements

's `bevy_math`

and this crate's `BoundingVolumes`

, some type aliases are provided for `BvhVolume`

's built-in types, these can be found in the `bevy_math`

or the `prelude`

/`dim2`

modules.
The BVH can be traversed using any type that implements `dim3`

's `bevy_math`

, some types for this are provided by `IntersectsVolume`

, including for overlap between built-in volumes, ray casting, and casting volumes.`bevy_math`

## Getting started

Creating and traversing the BVH can be entirely done using

s.`Iterator`

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``::``{`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.

#### Dependencies

~5MB

~134K SLoC