实时计算碰撞-处理时间延迟 [英] Calculating collisions in real time - dealing with a delay in time

问题描述

假设:

• 您正在编写一个程序，其中3个(或更多个)圆(或其他几何形状)在屏幕上实时移动，但都以不同的速度移动，由于某些原因，该速度可能在某些时间发生变化物理计算.

• 只能在每一帧上计算

在每个帧中，您必须确保在该帧与最后一个帧之间的时间段内碰撞"/碰撞"的圆圈.彼此之间将通过物理计算反弹"

• 假设在第x帧和第x + 1帧之间的时间里，三个圆圈将相互碰撞.但是，在第x帧期间，没有一个圆圈彼此接触.在第x + 1帧中，同样的情况适用(没有碰撞)我将尝试用图像更好地说明这一点:

问题:

有什么好的方法来跟踪碰撞，以免由于两帧之间的一些(意外的)大的延迟而不会跳过碰撞?

这个问题在我脑海中徘徊了太久了...

对于所有认为该帖子很重要的人:请参阅解决方案

正确执行此操作:

• 计算您的圈子的确切碰撞时间，而不是舍入到下一帧:
  • 如果您的对象以一维以上的速度移动，则需要进行寻根.
• 按顺序解决冲突，如下所示:
  • 在上述确切碰撞时间停止模拟.
  • 在第一次碰撞中解决圆的物理问题.
  • 重新计算以确定由于新轨迹而引起的任何碰撞.
  • 重新开始仿真.
  • 重复直到直到帧尾而没有碰撞为止.
• 物理上任何其他计划外的变化也将要求更新即将发生的碰撞.

您可能会注意到，这有可能进行大量计算.如果您的球失去动能并最终彼此搁置，这可能会特别令人讨厌-如果您的物理学使这种可能性成为可能，则您需要为静止接触"添加某种阈值(不幸的是，这可能会使情况更加复杂)你的物理学极大).

---

更新，以回应评论:我想明确地指出，我的回答忽略了您的一种假设-如果您假装帧边界之间没有任何时间，就无法准确地处理碰撞.碰撞不会发生在帧边界处；通常，冲突将发生在帧边界之间 ，因此您的计算需要反映出来.

如果假设帧之间的所有运动都是线性的(即，模拟对帧边界进行了所有加速)，则实际上确定是否，何时何地发生碰撞非常简单.它将帧间仿真"几乎减少为零-即使仿真是2D或3D，也可以以封闭形式求解方程式:

  posAB = posA-posB [圆A和B之间的相对矢量]velAB = velA-velB [圆A和B之间的相对速度]posAB(t)= posAB(0)+ t * velAB [相对矢量与时间的关系]rAB = rA + rB [两个圆的半径之和]当distance(t)= abs(posAB(t))== rAB时发生碰撞->rAB ^ 2 = |posAB(t)| ^ 2 = |posAB(0)+ t * velAB | ^ 2->t^2 * |velAB|^2 + t * 2*posAB(0).velAB + |posAB(0)|^2 - rAB^2 == 0求解t的二次方程:-如果判别为负，则不存在冲突.-如果碰撞时间在当前时间步之外，则没有当前碰撞.-否则，最小的t应该是正确的碰撞时间.-提防2个圆圈撞出碰撞的情况... 

最后，听起来您正在尝试进行过早的优化.更好地使事情正常运行，然后使其快速运行；您必须先运行代码，才能知道实际的瓶颈.实际上，我还认为您低估了现代计算机的功能.当然，您总是可以添加足够多的对象来关闭计算机，但是我想您会惊讶地发现它花了多少钱...

Suppose:

• you're coding a program in which 3 (or a lot more) circles (or other geometry) move around on the screen in real time, all with a different velocity, that can change at certain times due to physics-calculations.

• the calculations can only be calculated on every frame

• each frame, you have to make sure the circles who "collide"/"have collided during the time between this frame and the last" with each other will 'bounce off' by using physics-calculations

• Suppose that during the time between frame x and frame x+1, three circles will collide with each other. However, during frame x none of the circles touches the other. In frame x+1, the same thing applies (none collides) I will try to better illustrate this with an image:

The question:

What are good ways to keep track of collision like this, so that a collision wouldn't get skipped due to some (unexpected) large delay in time between two frames?

This question has been spooking around in my head for way too long...

EDIT:

To everyone thinking this post is OT: see this before you vote for closure.

解决方案

To do this properly:

• calculate exact collision times for your circles instead of rounding to the next frame:
  • if your objects are moving in more than 1D, this requires root-finding.
• resolve collisions in order, as follows:
  • stop the simulation at the aforementioned exact collision time.
  • resolve the physics of the circles in this first collision.
  • recalculate to determine any collisions due to the new trajectories.
  • restart the simulation.
  • repeat until you reach end-of-frame without a collision.
• any other unscheduled change in physics will also require updating upcoming collisions.

You may notice that this has the potential for lots of computation. It can be particularly nasty in cases where your balls lose kinetic energy and end up resting on each other -- if your physics makes this likely, you will need to add some sort of threshold for "resting contact" (which, unfortunately, can complicate your physics enormously).

---

Update, in response to comments: I want to make clear that my answer ignores one of your assumptions -- you can't handle collisions accurately if you pretend that there isn't any time between frame boundaries. The collisions don't happen at the frame boundaries; in general, the collisions will happen between the frame boundaries, so your computations need to reflect that.

If you assume that all motion between frames is linear (i.e., your simulation does all acceleration on the frame boundaries), then determining whether, where, and when there is a collision is actually pretty simple. It reduces your interframe "simulation" to practically nothing -- you can solve your equations in closed form, even if your simulation is 2D or 3D:

posAB = posA - posB                [relative vector between circles A and B]
velAB = velA - velB                [relative velocity between circles A and B]
posAB(t) = posAB(0) + t * velAB    [relative vector as a function of time]
rAB = rA + rB                      [sum of radii of the two circles]
collision happens when distance(t) = abs(posAB(t)) == rAB
-> rAB^2 = | posAB(t) |^2 = | posAB(0) + t * velAB |^2
-> t^2 * |velAB|^2 + t * 2*posAB(0).velAB + |posAB(0)|^2 - rAB^2 == 0
solve quadratic equation for t:
   - if discriminant is negative, there is no collision.
   - if collision times are outside current timestep, there is no current collision.
   - otherwise, smallest t should be the correct collision time.
   - watch out for cases like 2 circles coming *out* of collision...

Finally, it sounds like you're trying to do premature optimization. Better to make things work right, then make them fast; you won't know your actual bottlenecks until you have running code. I also think you are, in fact, underestimating the power of modern computers. Of course, you can always add enough objects to bog down your computer, but I think you will be surprised how many it takes...

这篇关于实时计算碰撞-处理时间延迟的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！