c++ - 处理质量 Spring 系统之间碰撞的好方法

Question

我正在编写一个 C++ 模拟应用程序，其中几个质量 Spring 结构将移动和碰撞，我目前正在努力处理碰撞检测和响应部分。这些结构可能封闭也可能不封闭(它可能是一个“球”或只是一连串的质量和 Spring )所以(我认为)不可能使用我们测试 2 个重叠形状的“经典”方法。

此外，碰撞是该模拟的一个非常重要的部分，我需要它们在检测和响应方面尽可能准确(实时不是这里的限制条件)。我希望能够尽可能了解施加在每个节点(质量)上的力。

目前我正在检测每个时间步长的节点和 Spring 之间的碰撞，检测似乎有效。我可以计算一个节点和 Spring 之间的碰撞时间，从而找到碰撞的确切位置。但是，我不确定这是否是解决此问题的正确方法，并且经过大量研究后我无法找到使事情正常工作的方法，主要是在碰撞的响应方面。

因此，我真的很想听听似乎非常适合此类碰撞问题的任何技术、算法或库，或者您可能需要使这项工作发挥作用的任何想法。真的，我们将不胜感激任何形式的帮助。

Answer 1

如果你能满足以下条件:

 0) All collisions are locally binary - that is to say 
    collisions only occur for pairs of particles, not triples etc, 
 1) you can predict the future time for a collision between 
    objects i and j from knowledge of their dynamics (assuming that no other
    collision occurs first)
 2) you know how to process the physics/dynamicseac of the collision

那么您应该能够执行以下操作:

设 Tpq 是粒子 p 和 q 之间碰撞的预测时间，Vp (Vq) 是一个包含每个粒子 p (q) 局部动力学的结构(即它的速度、位置、 Spring 常数等)

对于n个粒子...

Initialise by calculating all Tpq (p,q in 1..n)
Store the n^2 values of Tpq in a Priority Queue (PQ)
repeat
  extract first Tpq from the PQ
  Advance the time to Tpq
  process the collision (i.e. update Vp and Vq according to your dynamics)
  remove all Tpi, and Tiq (i in 1..n) from the PQ
    // these will be invalid now as the changes in Vp, Vq means the
    // previously calculated collision of p and q with any other particle
    // i might occur sooner, later or not at all
  recalculate new Tpi and Tiq (i in 1..n) and insert in the PQ
until done

初始设置成本为 o(n^2)，但重复循环应为 O(nlogn) - 移除和替换 2n-1 次无效冲突的成本。这对于中等数量的粒子(最多数百个)来说相当有效。它的好处是您只需要在碰撞时处理事物，而不是等间隔的时间步长。这使得事情对于人口稀少的模拟特别有效。