我正在研究各种碰撞检测算法，其中之一是扫描和修剪。我想我对它的工作原理有很好的理解；您为每个轴存储一个排序的端点列表，并且在每次更新期间我必须保持列表排序。下面是我发现的一个网页的链接，它帮助我理解了这个算法：
http://jitter-physics.com/wordpress/?tag=sweep-and-prune
但是，我不太清楚代码中的时间一致性是如何实现的。我知道它利用了对象在连续时间范围内几乎没有移动的事实，但我不太明白它是如何实现的。
有人可以对这种情况有所了解吗？
问问题
2416 次
2 回答
3
+1 的问题，但你的答案可能是错误的；在排序（扫描）阶段，在一个模拟步骤到下一个模拟步骤之间利用时间相干性。这是维基百科的Sweep and Prune的摘录：
扫描和修剪利用了时间相干性，因为固体很可能在两个模拟步骤之间没有显着移动。正因为如此，在每一步，包围体开始和结束的排序列表可以用相对较少的计算操作进行更新。对几乎已排序的列表进行快速排序的排序算法，例如插入排序，特别适合此目的。
假设我们有n 个对象，在时间步 1，t = 1，对于扫描阶段，我们已经对所有对象进行了排序start.x，end.x并且根据结果，我们也执行了窄阶段以找到实际的碰撞对象。现在，对于t = 2 ，除非您的模拟具有可以传送（在其他地方消失并重新出现）的对象，否则对象将在t = 2处从其t = 1位置略微移动。在t = 1和2之间，如果变化不大（时间连贯性），那么我们为t = 1创建的排序列表通常会为到达t = 2的排序列表提供一个良好的开端X因为对于t = 2，旧列表非常接近完美排序状态。现在，通过使用诸如插入排序之类的排序，这对于一般情况来说可能代价高昂，但在这种几乎排序的情况下会很好地工作，人们可以快速获得t = 2的完美排序列表。
于 2014-11-05T11:18:54.497 回答
2
我想我可能已经找到了自己问题的答案。时间相干性仅仅减少了窄相位碰撞检测的工作量。我正在检查以下链接中的代码。
http://www.koders.com/java/fidB3D3D9D154CE69A671A799D52E7C44C104DF9537.aspx?s=wa
我认为这就是时间相干性发挥作用的地方：当考虑到对象对发生碰撞并进入窄相碰撞时，将对端点数组进行排序。在端点需要再次排序之前，不需要寻找对象对来考虑窄相冲突，因为第 76 行的 if 语句永远不会为真。如果是这样，那么代码遵循时间一致性原则：在小时间步长内，对象配置的变化很小，以至于无法保证数组排序；数组中不会重新排列任何内容。因此窄相碰撞的数量将减少。
于 2012-05-05T04:51:49.350 回答