我想知道处理大量移动对象（球体、三角形、框、点等）的最佳数据结构是什么？我试图回答两个问题，最近邻和碰撞检测。
我确实意识到，传统上，像 R 树这样的数据结构用于最近邻查询，而 Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。
我只是希望那里有其他更好的东西。
我感谢所有的帮助。
Eric
问问题
5173 次
5 回答
6
您可以将场景划分为八叉树并利用场景一致性。您正在测试的移动对象将在树的特定节点中针对特定数量的帧，具体取决于其速度。这意味着您可以假设它将在节点中，因此可以快速删除许多不在节点中的对象。当然，棘手的一点是当您的对象靠近分区边缘时，您必须确保更新对象所在的节点。
运动的物体有方向和速度。您可以使用对象移动方向的垂直分割轻松地将场景分成两部分。该分区错误一侧的任何对象都不需要检查。当然要补偿其他物体的速度。因此，如果另一个对象相当慢，您可以轻松地将其从进一步的检查中删除。
始终使用轴对齐的边界框之类的东西来简化您正在测试的任何形状。初始碰撞测试
您可以计算对象与另一个移动对象之间的距离以及速度。如果另一个移动物体以更快的速度沿相同的大致方向移动，您可以将其从检查中排除。
根据对象的形状，还有许多其他优化。圆形或正方形或更复杂的形状都具有您可以在移动时进行的特定优化。
假设某些对象确实停止或可以停止移动，您可以跟踪停止的对象。这些对象可以被视为静态对象，因此检查速度更快，您可以将所有静态优化技术应用于它们。
我知道更多，但我想不出来。好久没做这个了。
当然，这取决于您如何进行碰撞检测。您是否根据速度逐步更新对象的位置并检查它是否是静态的。或者您是否通过挤压形状并找出初始碰撞点来补偿速度。前者对于快速移动的物体需要一小步。后者更复杂，成本更高，但效果更好。此外，如果您要旋转物体，那么事情会变得更加棘手。
于 2008-10-25T04:22:54.097 回答
2
Bounding Spheres 可能会帮助您处理许多移动物体；您计算对象的半径平方，并从它的中心跟踪它。如果两个对象中心之间的平方距离小于两个对象的平方半径之和，则可能发生碰撞。一切都是用平方距离完成的；没有平方根。
您可以按对象之间的最小平方距离对最近的邻居进行排序。当然，碰撞检测会变得复杂，对于非球形物体，Bounding Spheres 不一定会为您提供碰撞信息，但它可以很好地修剪您需要比较碰撞的对象树。
当然，您需要跟踪对象的 CENTER；理想情况下，您希望每个对象都是刚性的，以避免重新计算边界球体的大小（尽管重新计算并不是特别困难，特别是如果您使用刚性对象树，每个对象都有自己的边界球体是非刚性的；但它变得复杂）。
基本上，要回答有关数据结构的问题，您可以将所有对象保存在主数组中；我有一组“区域”数组，其中包含对主数组中对象的引用，您可以根据它们的笛卡尔坐标快速将对象分类；“区域”数组的重叠定义至少应为主对象数组中最大对象半径的 2 倍（如果可行；显然会出现对象边界球体缩放与对象数量的问题）。
完成后，您可以通过比较一个区域内所有对象的距离来进行快速碰撞测试；同样，这是区域定义变得重要的地方，因为您正在对区域数量与比较数量进行重大权衡。但是，它更简单一点，因为您的距离比较归结为简单的减法（当然还有 abs() 操作）。
当然，您必须在非球形对象之间进行实际的碰撞检测，这可能很重要，但此时您已经大大减少了潜在比较的数量。
基本上，它是一个两层系统；第一个是区域数组，您可以在其中对场景进行粗略排序。其次，你有你的区域内距离比较；您将在其中对发生碰撞的对象进行基本的碰撞检测和碰撞标记。
这种算法可能有空间在动态区域确定中使用树来平衡您的区域大小，以确保您的区域大小不会因“拥挤”区域而增长过快；但是，这类事情并非微不足道，因为对于不同大小的物体，您对密度的排序变得……至少可以说是复杂的。
于 2008-10-25T00:23:55.637 回答
2
进行碰撞检测的一种有趣方法是使用在特殊八叉树结构中组织的轴向对齐边界框 (AABB)。AABB 的帮助是因为它们可以非常快速地进行粗略的碰撞计算，因为您最多只需要执行 6 次比较。
您应该对八叉树结构使用一些技巧：
1）节点占据的边界区域应该是普通八叉树的两倍（八叉树将空间划分为无重叠）。因为每个节点应该重叠其相邻节点的一半区域。由于 AABB 只能属于一个节点，因此这种额外的大小和重叠允许它在一个节点中保留更长的时间。
2) 同样在每个节点中 - 并且可能在层次结构的每个级别中 - 您保持与节点邻居的链接。这将涉及大量额外代码，但它允许您在接近 O(1) 时间而不是 O(2logn) 时间的时间内在节点之间移动元素。
如果八叉树占用太多内存，您可以将其更改为使用稀疏八叉树结构，只保留游戏世界中实际包含实体的部分的树。然而，这意味着当实体在世界中移动时，您必须为每一帧执行更多计算。
您可能想尝试而不是八叉树的其他一些想法是使用 kd-tree（我相信这是正确的名称），或者使用 AABB 从下向上构建结构。
KD 树（来自内存）使用轴向对齐的平面划分空间，因此它们非常适合与 AABB 一起使用。
另一个想法不是从上到下强制八叉树生成（从一个包围整个世界的盒子开始），而是从基础实体构建它并构建更大的 AABB，直到最大的一个包含整个世界。虽然我不确定它如何与许多快速移动的实体一起工作。
（我已经有一段时间没有完成这种空间游戏开发编码了。）
于 2008-10-25T01:16:25.983 回答
0
RDC可能很有用，尤其是当您的对象稀疏（没有很多交叉点）时。
于 2008-10-29T09:14:45.400 回答
-1
sweep and prune broad phase + gjk narrow phase
于 2008-10-25T09:02:36.120 回答