我想知道处理大量移动对象(球体、三角形、盒子、点等)的最佳数据结构是什么?我试图回答两个问题,最近邻和碰撞检测。
我确实意识到,传统上,像 R 树这样的数据结构用于最近邻查询,Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。
我只是希望还有其他更好的东西。
我感谢所有的帮助。
您可以将场景划分为八叉树并利用场景一致性。您正在测试的移动对象将在树的特定节点中持续特定数量的帧,具体取决于其速度。这意味着您可以假设它将在节点中,因此可以快速删除许多不在节点中的对象。当然,棘手的一点是当您的对象靠近分区边缘时,您必须确保更新对象所在的节点。
运动的物体有方向和速度。您可以通过使用对象移动方向的垂直划分轻松地将场景分为两部分。不需要检查位于该划分错误一侧的任何对象。当然要补偿其他物体的速度。因此,如果另一个对象相当慢,您可以轻松地将其从进一步检查中删除。
始终使用轴对齐边界框之类的东西来简化您正在测试的任何形状。初始碰撞测试
您可以计算物体与另一个移动物体之间的距离加上速度。如果另一个移动物体以更快的速度沿相同的方向移动,您可以将其从检查中消除。
根据对象的形状,还有许多其他优化。圆形、正方形或更复杂的形状都可以在移动时进行特定的优化。
假设某些对象确实停止或可以停止移动,您可以跟踪停止的对象。这些对象可以像静态对象一样对待,因此检查速度更快,并且您可以对它们应用所有静态优化技术。
我知道更多,但一时想不起来。有一段时间没做这个了。
当然,这取决于您如何进行碰撞检测。您是否根据速度增量更新对象的位置并检查它是否是静态的。或者您是否通过挤压形状并计算出初始碰撞点来补偿速度。前者对于快速移动的物体需要一小步。后者更复杂且成本更高,但效果更好。另外,如果你要旋转物体,那么事情就会变得更加棘手。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)