物体间高效碰撞检测的最佳算法
我很困惑。好吧，不要感到困惑，就像不想做 6 个测试程序来看看哪种算法是最好的一样。所以我想我应该请教我在 SO 的专家朋友，让我从他们的经验中获益。
该场景是一个 3D 场景，与其中对象的大小相比，其区域可能相当大。场景中可能有数千个对象。物体的大小从十分之一到大约十个单位不等，但没有更大（或更小）。这些对象往往聚集在一起，但这些群集可能会出现在场景中的任何位置。所有物体都是动态的、移动的。星团往往会一起移动，但当它们一起移动时，它们的速度可能并不总是相同。还需要考虑静态几何形状。尽管存在大量的动态对象，但场景中也存在一些静态对象（静态对象往往比动态对象大一两个数量级）。
现在，我想要的是一个空间数据结构，可以有效地对场景中的所有项目执行碰撞检测。如果该算法也支持渲染管道的可见性查询，那就太好了。为了简单起见，假设这里的碰撞检测是宽相的（即所有动态物体都是完美的球体）。
因此，在我的研究中，我可以使用以下之一：
（1）八叉树 (2) 松散八叉树 (3) 线性八叉树（+松散） (4)KD树 (5)BSP树 (6) 散列
到目前为止，(6) 是我唯一尝试过的。如果场景中的对象平均均匀分布，那么它的速度实际上非常出色（在我的系统上，8192 个项目碰撞检查不到 1 毫秒）。如果所有对象都被合并到一个较小的区域中，那么这不是一个好的算法，我认为这是可能的。
有谁知道应该使用哪一个，或者我可以采用哪些技巧来加快速度？我认为无论发生什么，我都可以使用单独的 BSP 树来处理静态几何体。我想动态“领域”是我最关心的。注意：没有 CUDA，这只是 CPU :p。
谢谢
编辑：好的，感谢 Floris，我找到了有关 AABB 树的更多信息。这里有一个关于 GameDev 的旧讨论：http://www.gamedev .net/topic/308665-aabb-tree---wheres-the-poly-o_o/。看起来是一个很好的妥协。
最终编辑：决定不重新发明轮子。子弹物理库可能会为我完成所有这些（它有 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).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
许多物理引擎使用 AABBTree（轴对齐边界框树），它将对象细分为越来越小的块。通过使用该算法，您可以获得非常好的碰撞检测。这棵树看起来有点像八叉树。
OOBBTree（定向边界框）将是它更好的对应部分。
Many physics engines use an AABBTree (Axis aligned Bounding Box Tree), It subdivides an object to smaller and smaller pieces. You can get very good collision detection by using this algo. This tree looks somewhat like an Octree.
An OOBBTree (Orientated Bounding Box) would be it's better counter part.
很好的问题。
基本上，您需要在以下方面进行复杂的权衡：
坏消息是，因此没有“完美”的答案 - 它将真正取决于您的具体情况有许多不同的独特因素。例如，当 BSP 使用大量静态平面几何体进行预先计算时，其速度非常快，这解释了为什么它们在早期 FPS 游戏中如此普遍。
我个人的猜测是，每个底层边界框中包含合理数量的对象（5-10？）的松散 AABB（轴对齐边界框）树可能最适合您的情况。原因：
抱歉，这个答案有点模糊，但我希望这能给您一些有用的想法/需要考虑的事情！
Great question.
You basically have a complex trade-off between:
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:
Sorry for the slightly woolly answer but I hope this gives you some useful ideas / things to consider!