esi*_*gel 17 geometry collision-detection spatial neighbours data-structures
我想知道处理大量移动物体(球体,三角形,盒子,点等)的最佳数据结构是什么？我正在尝试回答两个问题,即最近邻和Collsion检测.
我确实意识到传统上,像R树这样的数据结构用于最近邻居查询,而Oct/Kd/BSP用于处理静态对象或极少数移动对象的碰撞检测问题.
我只是希望那里有更好的东西.
我感谢所有的帮助.
您可以在八叉树中划分场景并利用场景一致性。您要测试的移动对象将根据其速度在树的特定节点中放置特定数量的帧。这意味着您可以假定它会在节点中，因此可以迅速切出很多不在节点中的对象。当然，棘手的一点是，当对象靠近分区边缘时，必须确保更新对象所在的节点。
运动物体具有方向和速度。通过从对象的运动方向垂直划分，可以轻松地将场景划分为两个部分。不需要检查此划分错误一侧的任何对象。当然可以补偿另一个物体的速度。因此，如果另一个对象比较慢，则可以轻松地将其从进一步的检查中剔除。
始终使用轴对齐的边界框等来简化要测试的任何形状。初始碰撞测试
您可以获取物体与另一个运动物体之间的距离以及速度。如果另一个移动物体以相同的大致方向以更快的速度移动，则可以从检查中消除它。
根据对象的形状还有许多其他优化。圆形，正方形或更复杂的形状都具有移动时可以进行的特定优化。
假设某些对象确实停止或可以停止移动，则可以跟踪停止的对象。这些对象可以像静态对象一样对待，因此检查速度更快，您可以将所有静态优化技术应用于它们。
我知道更多，但是想不起来。一段时间没有这样做。
现在，这当然取决于您如何进行碰撞检测。您是否基于速度逐步更新对象的位置并检查它是否是静态的。或者，您是通过拉伸形状并找出初始碰撞点来补偿速度。前者需要快速移动物体的一小步。后者更复杂且成本更高，但效果更好。同样，如果您将要旋转物体，那么事情会变得有些棘手。
边界球可能会帮助您处理许多移动物体；您计算对象的半径平方，并从其中心跟踪它。如果两个物体中心之间的平方距离小于两个物体半径的平方和，那么就有可能发生碰撞。一切都以平方距离完成；没有平方根。
您可以根据对象之间的最小平方距离对最近的邻居进行排序。当然，碰撞检测可能会变得复杂，对于非球形物体，边界球不一定会为您提供碰撞信息，但它可以很好地修剪需要比较碰撞的物体树。
当然，您需要跟踪对象的中心；理想情况下，您希望每个对象都是刚性的，以避免必须重新计算边界球体大小（尽管重新计算并不是特别困难，特别是如果您使用刚性对象树，每个对象都有自己的边界球体是非刚性的；但它变得复杂）。
基本上，为了回答有关数据结构的问题，您可以将所有对象保存在主数组中；我有一组“区域”数组，其中包含对主数组中对象的引用，您可以根据对象的笛卡尔坐标将对象快速排序；“区域”数组的重叠定义应至少为主对象数组中最大对象半径的 2 倍（如果可行；显然会出现对象边界球缩放与对象数量的问题）。
一旦掌握了这一点，您就可以通过比较区域内所有对象彼此的距离来进行快速碰撞测试；同样，这就是区域定义变得重要的地方，因为您正在区域数量和比较数量之间进行重大权衡。然而，它更简单一些，因为您的距离比较可以归结为简单的减法（当然还有 abs() 运算）。
当然，然后您必须在非球形物体之间进行实际的碰撞检测，这可能并不简单，但此时您已经极大地减少了潜在比较的数量。
基本上，它是一个两层系统；第一个是区域数组，您可以通过它对场景进行粗略排序。其次，进行区域内距离比较；其中您将对已碰撞的对象进行基本的碰撞检测和碰撞标记。
这种算法可能有空间在动态区域确定中使用树来平衡您的区域大小，以确保您的区域大小不会因“拥挤”区域而增长得太快；不过，这类事情并不简单，因为对于不同大小的物体，你对密度的排序变得……至少可以说是复杂的。