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 and Layer::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

1. Instantiate a Layer<Index, ID>
   • Index must be an instance of SpatialIndex; one of Index32_2D, Index64_2D, or Index64_3D
   • ID may be any user-specified type which satisfies the ObjectID trait (blanket implementation; includes primitive integral types)
2. Clear old data, if necessary, using Layer::clear
3. Append object bounds-ID pairs using Layer::extend
4. 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.