标签: broad-phase

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

• 检查所有内容(O(n ^ 2)复杂度)
• 扫描和修剪(排序和扫描)
• 关于二进制空间分区的一些事情(不知道如何做到这一点)

但肯定还有更多选择吗？这些是什么？并且可以提供每个的基本描述或链接到描述吗？

我已经看到了这个,但我要求提供一系列可用的算法,而不是最符合我需求的算法.

在这种情况下,"广泛相位碰撞检测"是物理引擎用来确定模拟中哪些物体足够接近以保证进一步调查和可能的碰撞解决的方法.

从一开始,碰撞检测感觉就像是O(n ^ 2)问题.

你有一堆对象,你需要检查每个对象是否与任何其他对象发生碰撞.但是,我知道将每个对象与所有其他对象进行对比检查是非常无效的.为什么两个球之间的相对昂贵的碰撞检查,如果它们彼此不相近？

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

如果你有1000个球,那么如果你进行了天真的碰撞检测,你将获得1000 ^ 2次收集检查(一百万)!这种冲突检查很快成为我的应用程序的瓶颈.我需要实施一些广泛的阶段修剪.

在处理2d - 圆形物体时,应该使用哪些技术来修剪碰撞检查？我已经阅读过关于QuadTrees,BSP,空间散列等的内容,但很难理解哪种方法最适合这个用例.

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