对象之间有效碰撞检测的最佳算法

Question

我糊涂了.好吧不要混淆,不要想做6个测试程序,看看哪个算法最好.所以我想我会问我在这里的专家朋友给我带来他们经验的好处.

该场景是一个3d场景,与其内部对象的大小相比,可能面积相当大.场景中可能存在数千个对象.物体的大小从十分之一到大约10个单位不等,但不大(或更小).对象倾向于聚集在一起,但这些聚类可能会出现在场景中的任何位置.所有物体都是动态的,动人的.集群倾向于一起移动,但是当它们发生时,它们的速度可能不会一直相同.还需要考虑静态几何.虽然有大量的动态对象,但场景中也有一些静态对象(静态对象往往比动态对象大一到两个数量级).

现在,我想要的是一个空间数据结构,用于有效地对场景中的所有项目执行碰撞检测.如果算法也支持可见性查询,那么对于渲染管道来说会很棒.为简单起见,假设此处的碰撞检测是宽相的(即所有动态对象都是完美的球体).

所以,在我的研究中,我可以使用以下方法之一:

(1)八叉树(2)松散八叉树(3)线性八叉树(+松散)(4)KD树(5)BSP树(6)哈希

到目前为止(6)是我尝试过的唯一一个.它实际上是在速度方面完全高超(8192项碰撞下1ms的检查我的系统上),如果场景中的对象是平均均匀地分布.如果所有物体都被卷入一个较小的区域,这不是一个好的算法,我想这是可能的.

有没有人对使用哪一个有所了解,或者我可以用来加快速度的任何技巧？我想无论发生什么,我都可以使用单独的BSP树作为静态几何体.我想动态的"领域"是我最关心的问题.注意:没有CUDA,这只是CPU:p.

谢谢

编辑:好的,多亏了Floris,我发现了更多关于AABB Trees的信息.这里有关于GameDev的旧讨论:http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/ .看起来是一个很好的妥协.

最终编辑:决定不重新发明轮子.子弹物理库可能会为我做所有这些(它有AABB树,也可能非常优化).

Answer 1

好问题.

你基本上有一个复杂的权衡:

1. 完整碰撞检测阶段的速度
2. 当对象移动时更新/维护数据结构的开销

坏消息是因为这个没有"完美"的答案 - 它将真正依赖于你的情况所特有的许多不同因素.例如,当BSP用大量静态平面几何体预先计算时,BSP的速度非常快,这就解释了为什么它们在早期FPS游戏中如此普遍.

我个人的猜测是,在你的情况下,每个底层边界框中具有合理数量的对象(5-10？)的松散AABB(轴对齐边界框)树可能效果最佳.原因:

• 你有一个很大/稀疏的空间与对象簇.AABB树往往对此有好处,因为你可以减少许多你需要的水平.
• 你正在假设完美的领域.球体碰撞测试非常便宜,因此您可以轻松地为每个底层节点进行10-45次测试.基本上N ^ 2适用于N的小值:-)
• 轴对齐使得更新树更加简单,并且交叉点测试比大多数替代方案便宜得多.由于你假设大致是球形物体,我认为你不会从定向边界框中获得太多收益(如果你有很多长/薄形状的滑稽角度,这只会给你一个优势).
• 通过允许边界框松散并包含合理数量的对象,可以减少任何单个对象的运动将其带到AABB边界之外的可能性.除非发生这种情况,否则您无需更新树.这将为您节省大量的树更新时间.当它确实发生时,用一点边距扩展边界,这样你就不必立即重新延长下一帧 - 记住大多数动作往往会在相同的方向上继续几帧!

对不起有点毛茸茸的答案,但我希望这给你一些有用的想法/事情要考虑!

Answer 2

许多物理引擎使用AABBTree(轴对齐的边界框树),它将对象细分为越来越小的部分.使用此算法可以获得非常好的碰撞检测.这棵树看起来有点像八叉树.

OOBBTree(定向边界框)将是更好的对手部分.