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

问题描述

我很困惑好不容易混淆，不想做6个测试程序来看哪个算法是最好的。所以我以为我会在这里问我的专家的朋友给我的经验的好处。

该场景是一个3d场景，与其中的对象的大小相比，潜在的面积可能相当大。场景中可能有数千个物体。物体的大小从单位的十分之一变化到大约十个单位，但没有更大（或更小）。这些对象往往被聚集在一起，但是这些集合可以潜在地出现在场景的任何地方。所有物体都是动态和动态的。集群往往一起移动，但是当他们的速度可能不一样的时候。还有静态几何要考虑。虽然有大量的动态对象，但场景中还有一些静态对象（静态对象往往比动态对象大一个或两个数量级）。

现在，我想要的是一个空间数据结构，用于有效执行场景中所有项目的碰撞检测。如果算法也支持可见性查询，对于渲染管道，这将是很好的。为了简单起见，假设这里的碰撞检测是广泛的（即所有动态对象都是完美的球体）。

所以，在我的研究中，我可以使用一个（1）Octree
（2）松散Octree
（3）线性八叉树（+松散）
（4） KD树
（5）BSP树
（6）哈希

到目前为止（6）是我尝试过的唯一一个。实际上，在场景中的对象平均均匀分布的情况下，速度方面实际上是非常好的（8192项目的碰撞检查在我的系统的1ms以下）。如果所有的对象都被放大到较小的区域，那么这不是一个好的算法。我想这是可能的。

有没有人有一些洞察力来使用哪一个，或者我可以用来加快事情的任何技巧？我想，无论发生什么，我可以使用一个单独的BSP树作为静态几何。我认为动态的球体在这里是我最关心的。注意：没有CUDA，这只是CPU：p。

谢谢

编辑：好的，谢谢Floris ，我找到了有关AABB树的更多信息。有一个关于GameDev的旧讨论：。看起来像一个很好的妥协。

最终编辑：决定不重塑轮子。可能的是，子弹物理库将为我做所有这一切（它有一个AABB树，可能很好地优化）。

解决方案

您基本上有一个复杂的权衡：

1. 完成碰撞检测阶段的速度


2. 将数据结构作为对象更新/维护的开销

坏消息是，由于这个原因，没有完美的答案 - 它将真正取决于您的情况独特的许多不同因素。例如，当BSP被预先计算出很多静态平面几何图形时，BSP就会变得非常快，这就解释了为什么他们在早期的FPS游戏中很流行。

我个人的猜测是，在每个底层边界框中，具有合理数量的对象（5-10？）的松散的AABB（轴对齐边界框）树可能在您的情况下最有效。原因：

• 您有相当大的/稀疏的空间与对象集群。 AABB树往往对此很有好处，因为您可以切出很多您需要的水平。


• 您正在假设完美的领域。球体碰撞测试非常便宜，所以您可以轻松地为每个底层节点进行10-45次测试。基本上N ^ 2适用于N的小值： - ）


• 轴对齐使得树更新更简单，交叉测试比大多数替代方案便宜得多。因为你假设大致是球形的对象，我不认为你会从面向边界的框中获得很多收益（只有在有趣的角度你有很多长/薄的形状才有真正的优势）。


• 通过允许边界框松动并包含合理数量的对象，您可以减少任何单个对象的运动将其超出AABB边界的机会。除非发生这种情况，否则不需要更新树。这将为您节省很多树更新时间。当发生这种情况时，用一些边距扩展边界，以便您不需要立即重新再次延伸下一帧 - 请记住，大多数运动往往以相同的方向继续进行几帧！

对于轻微的羊毛答案，对不起，但我希望这给你一些有用的想法/事情要考虑！

I'm confused. Well not confused, so much as not wanting to do 6 test programs to see which algorithm is the best. So I thought I'd ask my expert friends here at SO to give me the benefit of their experience.

The scenario is a 3d scene with potentially quite a large area compared to the sizes of the objects inside it. There are potentially thousands of objects in the scene. Objects vary in size from tenths of a unit to up to around 10 units, but no bigger (or smaller). The objects tend to be clustered together, but those clusters can potentially appear anywhere in the scene. All objects are dynamic and moving. Clusters tend to move together, but when they do their velocities might not be the same all the time. There's also static geometry to consider. Although there are large numbers of dynamic objects, there's also some static objects in the scene (the static objects tend to be one or two orders of magnitude larger than the dynamic objects).

Now, what I want is a spatial data structure for efficiently performing collision detection for all items in the scene. It would be great if the algorithm also supported visibility query too, for the rendering pipeline. For the sake of simplicity, assume that collision detection here is broad-phase (i.e. all dynamic objects are just perfect spheres).

So, in my research I can use one of:

(1) Octree(2) Loose Octree(3) Linear Octree (+ loose)(4) KD Tree(5) BSP Tree(6) Hashing

So far (6) is the only one I've tried. It's actually totally superb in terms of speed (8192 items collision checked in under 1ms on my system) if objects in the scene are on average evenly spread out. It's not such a good algorithm if all objects get couped up into a smaller area, which I suppose is possible.

Does anyone have some insight as to which one to use, or any tricks I can employ to speed things up? I'm thinking that whatever happens I can just use a separate BSP tree for the static geometry. I suppose the dynamic "spheres" are what concern me most here. Note: no CUDA, this is CPU only :p.

Thanks

EDIT: Ok, thanks to Floris, I found more information about AABB Trees. There's an old discussion on GameDev here: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Looks like a good compromise.

Final EDIT: Decided not to reinvent the wheel. It's possible the bullet physics library will do all of this for me (it has AABB tree in it, probably very well optimised too).

解决方案

Great question.

You basically have a complex trade-off between:

1. Speed of a complete collision detection phase
2. Overhead of updating / maintaining the data structure as objects move around

The bad news is that there is no "perfect" answer because of this - it will genuinely depend on lots of different factors unique to your situation. BSPs for example are blisteringly fast for 1. when they are pre-computed with a lot of static planar geometry, which explains why they were so prevalent in early FPS games.

My personal guess is that a loose AABB (Axis Aligned Bounding Box) tree with a reasonable number of objects (5-10?) in each bottom level bounding box will probably work best in your case. Reasons:

• You have quite a large / sparse space with clusters of objects. AABB trees tend to be good for this, as you can cut out a lot of levels that you would otherwise need.
• You are assuming perfect spheres. Sphere to sphere collision tests are very cheap so you can easily afford to do 10-45 tests for each bottom level-node. Basically N^2 is fine for small values of N :-)
• Axis alignment makes updating the tree much simpler and intersection tests much cheaper than most alternatives. Since you are assuming roughly spherical objects, I don't think you would gain much from oriented bounding boxes (which only really give you an advantage if you have lots of long/thin shapes at funny angles).
• By allowing the bounding boxes to be loose and contain a reasonable number of objects, you reduce the chance that the motion of any individual object will take it outside the AABB bounds. Unless this happens, you don't need to update the tree. This will save you a lot of tree-updating time. When it does happen, extend the bound with a bit of margin so that you don't immediately have to re-extend again next frame - remember that most motion tends to continue in the same direction for a few frames!

Sorry for the slightly woolly answer but I hope this gives you some useful ideas / things to consider!

这篇关于对象之间高效碰撞检测的最佳算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！