我糊涂了。好吧，不要混淆，不要做6个测试程序来看看哪个算法是最好的。所以我想我应该请我在So的专家朋友给我一些他们的经验。
该场景是一个3d场景，与其中物体的大小相比，它的面积可能相当大。场景中可能有成千上万的物体。物体的大小从十分之一到大约10个单位不等，但没有更大(或更小)的。这些对象倾向于聚集在一起，但这些集群可能出现在场景中的任何地方。所有的物体都是动态的和移动的。集群倾向于一起移动，但当它们这样做时，它们的速度可能并不总是相同的。还需要考虑静态几何。虽然场景中有大量的动态对象，但也有一些静态对象(静态对象往往比动态对象大一到两个数量级)。
现在，我想要的是一个空间数据结构，用于有效地执行场景中所有项目的碰撞检测。如果该算法也支持可见性查询，这将是伟大的，为渲染管道。为了简单起见，假设这里的碰撞检测是宽相位的(即所有动态对象都是完美的球体)。
所以，在我的研究中，我可以使用其中一个:
(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树，可能也很好地优化了)。
好问题。
你基本上有一个复杂的权衡:
- 完整碰撞检测阶段的速度
- 对象移动时更新/维护数据结构的开销
坏消息是，没有"完美"的答案，因为这真的取决于你的情况下许多不同的独特因素。例如，bsp对于1来说非常快。当它们预先计算了许多静态平面几何，这就解释了为什么它们在早期的FPS游戏中如此普遍。
我个人的猜测是，一个松散的AABB(轴对齐边界框)树，每个底层边界框中有合理数量的对象(5-10?)可能最适合你的情况。原因:
- 你有一个相当大/稀疏的空间与集群的对象。AABB树往往很适合这一点，因为你可以削减很多你本来需要的水平。
- 你假设完美的球体。球体对球体的碰撞测试非常便宜，所以你可以轻松地为每个底层节点进行10-45次测试。对于较小的N值，N^2就可以了:-)
- 轴对齐使得更新树更简单，交叉测试比大多数替代方法便宜得多。因为你假设的是大致球形的物体，我不认为你会从定向边界框中获得多少好处(只有当你有很多长/细的形状在有趣的角度时，这才真正给你带来优势)。
- 通过允许边界框松散并包含合理数量的对象，您可以减少任何单个对象的运动将其带出AABB边界的机会。除非发生这种情况，否则不需要更新树。这将为您节省大量更新树的时间。当它确实发生时，用一点余量来扩展边界，这样你就不必立即在下一帧中再次扩展——记住，大多数运动倾向于在几个帧中继续朝着同一个方向前进!
很抱歉我的回答有点模糊，但我希望这能给你一些有用的想法/事情来考虑!
许多物理引擎使用AABBTree(轴对齐边界框树)，它将对象细分为越来越小的块。你可以通过使用这个算法得到很好的碰撞检测。这棵树看起来有点像八叉树。
一个OOBBTree(定向边界框)会是更好的对抗部分。