broadphase-rs
Overview
broadphase-rs is a, creatively named, broadphase collision detection library in Rust. It transforms object bounds into a lightweight spatial index representation, a single integer. A vector of such indices is sorted directly to yield a result which is a topologically-sorted Morton order, after which full-system collision detection can be accomplished by a single pass over the sorted list with only a minimal auxiliary stack necessary to maintain state. Collision tests between indices are accomplished with simple bitwise shifts, masks, and XORs.
This method is capable of supporting objects of varying scale (unlike uniform grids), while having a straightforward, non-hierarchical structure in memory (unlike quad- or oct-trees), as the entire representation exists in a single vector of index/object pairs.
broadphase-rs is capable of supporting many thousands of objects at interactive speeds. While it has not (yet) been
benchmarked against alternatives, the example's collision detection routine takes roughly ~6ms for 10,000 dynamic
objects (stable-x86_64-pc-windows-msvc, rustc 1.32.0, Intel Core i5 6600K, release mode, using par_scan()
)
Features
- Support for both 2D and 3D systems
- Full-system collision checking with
Layer::scan
- User-defined collision filters with
Layer::scan_filtered
- Layers can be pre-computed and merged (using
Layer::merge
) to avoid recalculation of static data - Optional multi-threaded operations using Rayon (
Layer::par_sort
andLayer::par_scan
) - Individual queries for boxes (
Layer::test_box
), rays (Layer::test_ray
), or user-specified tests (Layer::test
) - Picking first element along a ray (
Layer::pick_ray
) or user-specified picker (Layer::pick
)
Usage
- Instantiate a
Layer<Index, ID>
Index
must be an instance ofSpatialIndex
; one ofIndex32_2D
,Index64_2D
, orIndex64_3D
ID
may be any user-specified type which satisfies theObjectID
trait (blanket implementation; includes primitive integral types)
- Clear old data, if necessary, using
Layer::clear
- Append object bounds-ID pairs using
Layer::extend
- Retrieve potential collisions using
Layer::scan
Example
From the included sample program:
struct Collisions {
system: broadphase::Layer<broadphase::Index32_2D, specs::world::Index>,
collisions: Vec<(specs::Entity, specs::Entity, f32, Vector2<f32>)>,
}
// ...
self.system.clear();
self.system.extend(collision_config.bounds,
(&entities, &positions, &radii).join()
.map(|(ent, &pos, &Radius(r))| {
let bounds = Bounds{
min: Point2::new(pos.1.x - r, pos.1.y - r),
max: Point2::new(pos.1.x + r, pos.1.y + r)};
(bounds, ent.id())}));
// ...
self.collisions.clear();
self.collisions.extend(self.system.par_scan()
.iter()
.filter_map(|&(id0, id1)| {
// ...narrow-phase...
}));
Development
Generating Test Data
A program, gen_test_data
, is included in the utils/
directory to generate and visualize test data. Two scripts are included to automate the test generation process (tests/gen_test_scenes.py
and tests/gen_validation_data.py
)
Visualizing Test Data
To show test data, execute cargo run show -i <test_data_path> --gui
from the utils/
subdirectory. Move with W/A/S/D + Mouse (holding LMB) and cycle through objects left/right square bracket keys ([/]). Alternatively, specify a particular ID as a command-line parameter using --select-id
. All objects can be selected simultaneously by passing the --select-all
command-line parameter or pressing the spacebar while the application is running.