data-structures - 移动物体的空间数据结构？

Question

我想知道处理大量移动对象(球体、三角形、框、点等)的最佳数据结构是什么？我试图回答两个问题，最近邻和碰撞检测。

我确实意识到，传统上，像 R 树这样的数据结构用于最近邻查询，而 Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。

我只是希望那里有其他更好的东西。

我感谢所有的帮助。

Answer 1

您可以将场景划分为八叉树并利用场景一致性。您正在测试的移动对象将在树的特定节点中针对特定数量的帧，具体取决于其速度。这意味着您可以假设它将在节点中，因此可以快速删除许多不在节点中的对象。当然，棘手的一点是当您的对象靠近分区边缘时，您必须确保更新对象所在的节点。

运动的物体有方向和速度。您可以使用对象移动方向的垂直分割轻松地将场景分成两部分。该分区错误一侧的任何对象都不需要检查。当然要补偿其他物体的速度。因此，如果另一个对象相当慢，您可以轻松地将其从进一步的检查中删除。

始终使用轴对齐的边界框之类的东西来简化您正在测试的任何形状。初始碰撞测试

您可以计算对象与另一个移动对象之间的距离以及速度。如果另一个移动物体以更快的速度沿相同的大致方向移动，您可以将其从检查中排除。

根据对象的形状，还有许多其他优化。圆形或正方形或更复杂的形状都具有您可以在移动时进行的特定优化。

假设某些对象确实停止或可以停止移动，您可以跟踪停止的对象。这些对象可以被视为静态对象，因此检查速度更快，您可以将所有静态优化技术应用于它们。

我知道更多，但我想不出来。好久没做这个了。

当然，这取决于您如何进行碰撞检测。您是否根据速度逐步更新对象的位置并检查它是否是静态的。或者您是否通过挤压形状并找出初始碰撞点来补偿速度。前者对于快速移动的物体需要一小步。后者更复杂，成本更高，但效果更好。此外，如果您要旋转物体，那么事情会变得更加棘手。