collision-detection - 扫除和修剪 : where does temporal coherence come in?

Question

我正在研究各种碰撞检测算法，其中之一是扫描和修剪。我想我对它的工作原理有很好的了解；您为每个轴存储一个排序的端点列表，并且在每次更新期间我必须保持列表排序。以下是我发现的帮助我理解此算法的网页之一的链接:

http://jitter-physics.com/wordpress/?tag=sweep-and-prune

但是，我不太清楚代码中是如何实现时间一致性的。我知道它利用了对象在连续时间范围内移动很少的事实，但我不太清楚它是如何实现的。

有人可以对这种情况有所了解吗？

Answer 1

+1 的问题，但您的回答可能是错误的；在排序(扫描)阶段，在一个模拟步骤到下一个模拟步骤之间利用时间相干性。这是维基百科的摘录Sweep and Prune :

Sweep and prune exploits temporal coherence as it is likely that solids do not move significantly between two simulation steps. Because of that, at each step, the sorted lists of bounding volume starts and ends can be updated with relatively few computational operations. Sorting algorithms which are fast at sorting almost-sorted lists, such as insertion sort, are particularly good for this purpose.

假设我们有 n 个对象，在时间步长 1，t = 1，对于扫描阶段，我们已经对所有对象的 start.x 进行了排序和 end.x并且根据结果，我们也执行了狭窄阶段以找到实际的碰撞对象。现在，对于 t = 2，除非您的模拟具有可以传送(消失并重新出现在其他地方)的对象，否则这些对象将在 t = 2 时从它们的 t = 1 位置略微移动。在 t = 1 和 2 之间，如果 X不是很多(时间一致性)，那么我们为 t = 1 创建的排序列表通常会为到达 t = 2 的排序列表提供一个良好的开端，因为对于 t = 2 旧列表非常接近完美 -排序状态。现在，通过使用诸如 insertion sort 之类的东西，这对于一般情况可能会很昂贵，但在这种几乎排序的情况下会很好地工作，可以快速获得 t = 2 的完美排序列表。