Lib.rs

Broccoli

Broccoli是一个2D广相碰撞检测库。

基本数据结构是KD树和Sweep and Prune的混合。

在github 和 crates.io 上查看。文档在 docs.rs。

截图

来自内部 analysis/demo-web 项目的屏幕截图。

示例

use broccoli::rect;
fn main() {
    let mut inner1 = 0;
    let mut inner2 = 0;
    let mut inner3 = 0;

    // Rect is stored directly in tree,
    // but inner is not.
    let mut aabbs = [
        (rect(00, 10, 00, 10), &mut inner1),
        (rect(15, 20, 15, 20), &mut inner2),
        (rect(05, 15, 05, 15), &mut inner3),
    ];

    // Construct tree by doing many swapping of elements
    let mut tree = broccoli::Tree::new(&mut aabbs);

    // Find all colliding aabbs.
    tree.find_colliding_pairs(|a, b| {
        // We aren't given &mut T reference, but instead of AabbPin<&mut T>.
        // We call unpack_inner() to extract the portion that we are allowed to mutate.
        // (We are not allowed to change the bounding box while in the tree)
        **a.unpack_inner() += 1;
        **b.unpack_inner() += 1;
    });

    assert_eq!(inner1, 1);
    assert_eq!(inner2, 1);
    assert_eq!(inner3, 2);
}

缓存键示例

为了更方便，您可以使用cached_key接口

fn main() {
    let mut inner = [0, 4, 8];

    broccoli::from_cached_key!(tree, &mut inner, |&a| broccoli::rect(a, a + 5, 0, 10));

    tree.find_colliding_pairs(|a, b| {
        broccoli::unpack!(a, b);
        *a += 1;
        *b += 1;
    });

    // bboxes 1st and 2nd intersect, as well as 2nd and 3rd.
    assert_eq!(inner, [0 + 1, 4 + 2, 8 + 1]);
}

Tree 中 T 的大小

在构建过程中，树的元素会频繁交换。因此，如果T的大小太大，性能可能会大幅下降！为了解决这个问题，请考虑使用以下列出的半直接或甚至间接布局。间接布局实现了最小的元素大小（只有一个指针），但是可能会因为大问题规模而出现大量的缓存未命中。半直接布局更友好地利用缓存，但可能会使用更多的内存。有关更多信息，请参阅下面的优化部分。在几乎所有情况下，您都希望使用半直接布局。

• (Rect<N>,&mut T) 半直接
• (Rect<N>,T) 直接
• &mut (Rect<N>,T) 间接

我创建了ManySwap标记特征，以帮助提高对此性能退化陷阱的认识。它被实现在了许多保证是小的类型上。如果您了解自己在做什么，可以使用自动实现该特征的ManySwappable包装结构体，或者在自己的类型上自行实现。

您还可以使用半直接或间接的方式构建一个树，然后将其转换为直接方式。（请参阅Tree::from_tree_data()函数。）然而，我不确定这样做是否有性能上的好处。

并行性

警告：异构CPU变得越来越流行，您可能会有一些高性能核心和一些低功耗核心。为了在系统上获得一致的性能，您将不得不设置线程亲和力，使rayon的线程池仅在一种组类型上运行。这使得编写系统无关的代码非常困难。除非您能够调整并行性能，否则请考虑坚持单线程。简单地使用broccoli算法所带来的收益大于并行化所带来的收益，因此，仅使用broccoli而坚持顺序可能就足够了。

在broccoli-rayon存储库中提供了构建和碰撞对查找函数的并行版本。

浮点数

Broccoli仅要求其数字类型实现PartialOrd。对于它不理解的比较，它将只是任意选择一个结果。因此，如果您使用常规的浮点原始类型，并且即使只有一个NaN，树构建和查询也不会崩溃，但结果将是不确定的。如果使用浮点数，用户的责任是不要将NaN值传递到树中。虽然没有静态保护，但如果需要，您可以使用ordered-float存储库。没有强制执行Ord特征，以使用户有选择直接使用原始浮点类型，这可以更容易地处理。

静态保护不变性

已经做了很多工作来禁止用户在构建树之后违反树的不变性，同时仍然允许他们修改树的每个元素的各个部分。用户可以可变地遍历树，但可变引用的返回值被隐藏在禁止修改aabbs的AabbPin<T>类型之后。也就是说，broccoli树有访问/替换其内部数据的功能。因此，用户当然可以创建错误的树。

我必须每次都重建树吗？

是的。我优化了快速查询而不是快速构建。我注意到构建时间是稳定的，而查询时间会根据重叠的数量而大幅变化，并且在一定数量的碰撞之后，查询时间将超过重建时间。我认为许多碰撞系统都有机制来避免重建整个树，但这是以牺牲较慢的查询时间为代价的。例如，它们可能会插入松散的边界框，这将在查询时增加误报的数量。这些系统如果预先知道不会发生那么多碰撞，就非常出色。然而，在其他系统中，您可能无法对此进行限制，因此，broccoli针对的是碰撞数量可能占主导地位的情况进行了优化。为了减少树构建时间，请考虑一次只为一个对象组构建一个树，例如，您可能有一些动态对象和一些静态对象。（您可以在树和列表之间，或者在树和另一个树之间找到碰撞对）。

内存布局

树由节点组成，每个节点指向所有aabbs的一个切片。节点按先序排列。aabbs切片也按先序排列。

缓存结果

由broccoli-ext存储库提供的函数提供了缓存碰撞对的功能。

3D？

不支持，但你可以使用西兰花来分割两个维度，并使用其他东西来处理第三个维度。你可以在回调函数内部检查元素是否在z轴上相交。或者，你可以将z轴分割成平面，并在每个平面上使用西兰花。我认为在许多情况下，问题基本上是“主要二维”的，因为分布主要位于二维平面上，因此使用更侧重于二维的碰撞系统可能实际上更快。

优化

我主要关注的是在有很多重叠aabbs的分布中尽可能快地找到碰撞对。

以下是我所投入的努力的简要概述以及每种算法的一般性能成本估计。

数字是10分制的，只是粗略的估计。对于更深入的分析，请参阅内部 analysis/report-web/plot-gen 的输出： https://tiby312.github.io/broccoli_plots/

请参阅旧报告（我已经有一段时间没有更新了）：analysis/report-legacy，位于： broccoli book。

名称

如果你把“广相碰撞”缩写为“广撞”并快速说，听起来就像西兰花。西兰花基本上是小型树木，西兰花使用树形数据结构。