问题标签 [broad-phase]

从一开始，碰撞检测就好像是一个 O(n^2) 问题。

您有一堆对象，您需要检查每个对象是否与任何其他对象发生碰撞。但是，我知道将每个对象与所有其他对象进行检查是非常低效的。如果两个球甚至彼此不靠近，为什么要在两个球之间进行相对昂贵的碰撞检查？

这是我正在处理的简单程序的示例：

如果您有 1000 个球，那么如果您使用简单的碰撞检测，您将有 1000^2 次收集检查（一百万）！这种碰撞检查很快成为我的应用程序的瓶颈。我需要实施一些广泛的阶段修剪。

使用 2d 圆形对象时，应该使用哪些技术来修剪碰撞检查？我读过关于 QuadTrees、BSP、空间散列等的信息，但很难找出最适合这个用例的方法。

有没有人知道什么可能最有效？

我正在构建一个 2D 物理引擎，我想添加宽相碰撞检测，尽管我只知道 2 或 3 种类型：

• 检查一切与其他一切（O（n ^ 2）复杂度）
• Sweep and Prune（排序和扫描）
• 关于二进制空间分区的一些事情（不知道如何做到这一点）

但肯定有更多的选择，对吧？这些是什么？是否可以提供每个的基本描述或描述的链接？

我已经看到了这一点，但我要求提供可用算法的列表，而不是最适合我需要的算法。

在这种情况下，“宽相碰撞检测”是物理引擎用来确定其模拟中哪些物体足够接近以保证进一步调查和可能的碰撞解决的方法。

我正在尝试编写一个排序和扫描广泛阶段系统，并且在重叠报告阶段遇到了一些性能问题。

我的配对报告代码是瓶颈所在：

基本思想是为每个轴生成一个重叠对的临时列表，然后对于 X 中的每一对，检查该对是否存在于 Y 和 Z 中。一些额外的检查是在对生成中处理堆叠立方体和包含边缘情况。对生成代码如下：

通过分析发现的瓶颈是在通过 == 运算符比较对时发生的。我怀疑这是由于执行了许多此类检查，而不是检查本身的开销。

对上报代码如下：

我读过的关于排序和扫描/扫描和修剪的材料并没有详细说明一种快速搜索重复对的快速方法，或者实际上是一种以有效方式搜索其他轴以查找等值对的方法。我显然错过了一些东西，所以我将不胜感激任何可以提供的帮助。

首先，嘿，感谢所有查看我问题的人，

我正在为女巫构建一个 3D-Physics 引擎，我需要一个广泛的相位碰撞检测系统。我需要这个的世界非常具体，我比较了一些方法，但我仍然不确定什么是最好的。

现在我想请你就这个话题提供一些意见。

世界的属性： - 非常大（双向量中的位置） - 很少有对象（最多 100 个） - 对象有复杂的碰撞器（图元的组装 - 平均 10 到 50 个） - 对象通常聚集成组（平均 2 - 10 个） -物体不断移动 - 很少有静态物体

我有 2 个重点选项（但对其他选项持开放态度）： - 球体或轴对齐的箱形树 - 局部分区

具有二元结构的球体树（每个节点最多 2 个对象）可能是最好的..

你觉得最快的是什么？有什么方法可以在不尝试每一种可能性的情况下进行说明吗？

我希望你有一些建议。

阳光先生