我正在开发一个 3D 游戏引擎作为一个项目。我想对场景中的每个三角形/多边形使用空间分区算法来有效地检测碰撞。我只想知道（在我开始编写细节之前）现代计算机游戏中典型的空间分区算法有多快？我有动态对象，所以我想我可能必须每帧重新分区我的场景。这是否可能并且仍能达到合理的帧速率？如果答案可以包含数据（例如 FPS、多边形数量等），将不胜感激。如果那太麻烦了，请告诉我重新分区每一帧是否合理。
任何帮助，将不胜感激。
问问题
884 次
1 回答
4
我首先建议阅读关于使用 CUDA 进行宽相碰撞检测的章节。它比较了不同的广泛的相位碰撞算法。您的表现取决于几个关键变量。第一个变量是您的算法是否使用 GPU 加速实现。之前引用的文章包含一些关于帧速率与对象数量的基准。至少它应该让您对可以实现的目标有一个很好的了解。
如果您不计划 GPU 加速，则扫描和修剪是最容易实现的方法之一。我不知道确切的数字，但是当对象很少并且您的对象在帧之间变化不大时，它会表现良好。在这种情况下，你有 O(n) 的性能。这是一个很好的基线，因为它很容易实现。
如果你真的很认真，我推荐这本书Real-Time Collision Detection。我在研究碰撞检测方法时使用了这个。这是一个很好的资源。
于 2012-08-15T19:40:54.650 回答