bvh_arena/lib.rs
1#![deny(future_incompatible)]
2#![warn(nonstandard_style, rust_2018_idioms, missing_docs, clippy::pedantic)]
3#![deny(unsafe_code)]
4#![no_std]
5
6//! A bounding-volume hierarchy for in-game broad-phase collision detection
7//!
8//! The core type is [`Bvh`]. It supports insertion and removal as well as iterating over all overlaping pairs.
9//!
10//! The [`Bvh`] type is generic over the type of bounding volume,
11//! so you may choose one in [`volumes`] or implement yourself the [`BoundingVolume`] trait.
12//!
13//! # Usage example
14//!
15//! ```
16//! use bvh_arena::{Bvh, volumes::Aabb};
17//!
18//! // The built-in `Aabb` type can be created from anything that implement `Into<[f32; D]>`
19//! // So we can use glam's vector types. But you may use anything else you like.
20//! use glam::Vec2;
21//!
22//! // Create a bounding volume hierarchy.
23//! let mut bvh: Bvh<u8, Aabb<2>> = Bvh::default();
24//!
25//! // Insert bounding volumes
26//! bvh.insert(1, Aabb::from_min_max(Vec2::ZERO, Vec2::new(1.0, 1.0)));
27//! bvh.insert(2, Aabb::from_min_max(Vec2::new(0.5, 0.5), Vec2::new(2.0, 2.0)));
28//! bvh.insert(3, Aabb::from_min_max(Vec2::new(3.0, 2.0), Vec2::new(4.0, 4.0)));
29//!
30//! // Insertion returns an Id that can be used to remove the bounding volume
31//! let id = bvh.insert(4, Aabb::from_min_max(Vec2::new(3.0, 2.0), Vec2::new(4.0, 4.0)));
32//! bvh.remove(id);
33//!
34//! let mut pairs: Vec<(u8, u8)> = Vec::new();
35//!
36//! // Iteration over overlaping pairs
37//! bvh.for_each_overlaping_pair(|data1, data2| pairs.push((*data1, *data2)));
38//!
39//! assert_eq!(pairs, vec![(1, 2)]);
40//! ```
41pub use self::bvh::{Bvh, VolumeHandle};
42
43mod bvh;
44
45pub mod volumes;
46
47/// A type that represent a bounding volume, useful for broad collision detection
48pub trait BoundingVolume: Copy {
49 /// Merge the two bounding volumes into a single one that encompass both of them
50 #[must_use]
51 fn merge(self, other: Self) -> Self;
52
53 /// Return a scalar value that represent "how big" the volume is.
54 #[must_use]
55 fn area(&self) -> f32;
56
57 /// Returns true if this overlaps with the other volume
58 #[must_use]
59 fn overlaps(&self, other: &Self) -> bool;
60}