3个版本
| 0.1.2 | 2020年4月4日 |
|---|---|
| 0.1.1 | 2020年3月15日 |
| 0.1.0 | 2020年3月15日 |
#987 in 算法
4.5MB
1.5K SLoC
broadphase-rs 
概述
broadphase-rs 是一个名为独特的 Rust 广相碰撞检测库。它将对象边界转换为轻量级空间索引表示，一个单独的整数。这样的索引向量可以直接排序，得到拓扑排序的 Morton 顺序，之后可以通过对排序列表的单次遍历来完成整个系统的碰撞检测，只需一个最小的辅助堆栈来维护状态。索引之间的碰撞测试通过简单的位移动、掩码和异或操作完成。
这种方法可以支持不同尺寸的对象（与均匀网格不同），同时在内存中具有简单、非层次化的结构（与四叉树或八叉树不同），因为整个表示都存在于一个索引/对象对的单个向量中。
broadphase-rs 能够以交互式速度支持数以千计的对象。虽然它尚未与替代方案进行基准测试，但示例的碰撞检测例程在 10,000 个动态对象上大约需要 6 毫秒（stable-x86_64-pc-windows-msvc，rustc 1.32.0，Intel Core i5 6600K，发布模式，使用 par_scan()）
特性
- 支持2D和3D系统
- 使用
Layer::scan进行完整的系统碰撞检查 - 使用
Layer::scan_filtered进行用户定义的碰撞过滤器 - 层可以预先计算并合并（使用
Layer::merge），以避免静态数据的重新计算 - 可选的多线程操作使用Rayon（
Layer::par_sort和Layer::par_scan） - 针对盒子（
Layer::test_box）、射线（Layer::test_ray）或用户自定义测试（Layer::test）的单独查询 - 沿着射线选择第一个元素（
Layer::pick_ray）或用户指定的选择器（Layer::pick）
用法
- 实例化一个
Layer<Index, ID>Index必须是SpatialIndex的一个实例；可以是Index32_2D、Index64_2D或Index64_3D之一ID可以是任何满足ObjectID特质的用户自定义类型（泛型实现；包括原始整数类型）
- 如果需要，使用
Layer::clear清除旧数据 - 使用
Layer::extend追加对象边界-ID对 - 使用
Layer::scan检索潜在的碰撞
示例
从包含的示例程序
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...
}));
开发
生成测试数据
在utils/目录中包含了一个名为gen_test_data的程序，用于生成和可视化测试数据。包含两个脚本来自动化测试生成过程（tests/gen_test_scenes.py和tests/gen_validation_data.py）
可视化测试数据
要显示测试数据，从utils/子目录中执行cargo run show -<test_data_path> --gui。使用W/A/S/D + 鼠标（按住LMB）移动，使用左右方括号键（[/]）切换对象。或者，使用--select-id作为命令行参数指定特定的ID。可以通过传递--select-all命令行参数或按空格键在应用运行时同时选择所有对象。