Calculating collisions in realtime - dealing with

问题:

Suppose:

• you're coding a program in which 3 (or a lot more) circles (or other geometry) move around on the screen in realtime, 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 eachother will 'bounce off' by using physics-calculations

• Suppose that during the time between frame x and frame x+1, three circles will collide with eachother. 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 https://physics.stackexchange.com/questions/18515/calculating-collisions-in-realtime-dealing-with-a-delay-in-time before you vote for closure

回答1:

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...

回答2:

The idea of things only being evaluated in "frames" is probably not right.

One of the oldest OO patterns is "Model-View-Controller" - which encourages the decoupling of what is being viewed (the Model) with how it is viewed (the View).

A physics engine operates on model objects, and so would be tracking interactions between them all the time - so when the View comes along and asks for the position and direction of each circle in your "Frame x+1" scenario, it can easily answer, based on how much real time has passed since the last View request.

回答3:

I know your question states that the physics can only be evaluated at each frame, but I don't understand when this would be the case. It would be straightforward to incrementally update the physics in sufficiently small steps to avoid objects completely bypassing each other, once for each step.

However, sticking to an explicit update scheme (velocity times time step) only works for low velocities. As can be seen in many physics based games, upping the velocities can often lead to penetrating objects. Most simple physics engines opt to just allow for these bugs, because robust collision detection is notourisly difficult and costly.

If one limits the applicability to just circular shapes there are things that can be done. Writing the distance of the objects, as a function of time (over the time step)

x_a = x0_a + v_a*t
x_b = x0_b + v_b*t
d_ab = norm(x_a-x_b) = norm(x0_b-x0_a + (v_b-v_a)*t) = norm(dx + dv*t)

if the distance function d_ab equals the sum of the radii r_a+r_b for any t during the time step, then you have collision. So checking which objects collide (if any) first, then continuing from that point and redoing the analysis until the end of the time step has been reached. Quite complicated, and still only applies to circles/spheres.

回答4:

The keywords of collision-detection here are "continuous" or "not continuous".

Just like some of the other answers write, most modern collision-libraries go with the non-continuous version because it is costly to analyze the exact collision-time for many collision-shapes. This means you let the objects interpenetrate, detect this, then adjust their velocities to counter the interpenetration. And just like has been noted, this allows fast-moving objects to pass each other. This is solved by increasing the frequency you run the physics, essentially you need to decouple it from the rendering (run it using a much faster timer). The actual way you solve for the resolution of the interpenetration etc. is in scope for a different question.

However, for circles, the fact that you can analytically solve for the exact collision-time for any pair of circles with constant (or accelerating) velocity gives you a possibility to do continuous collision-detection in this particular case. It would be a nice project, but I'm not sure if it is the right way since you might suddenly want to include other shapes and then you're stuck. The formulas you have to solve was already posted as an answer.

What I wanted to add here apart from summarizing the two methods, because you seem very concerned about the processing speed of a "modern computing system", is that computers now are blazingly fast doing any of these calculations even in the naive way of checking all pairs of circles, if you optimize the inner code somewhat. You probably have no problem at all upping the speed of the physics compared to the rendering also, for solving the non-continuous case of high velocities.

What a non-continuous engine adds to avoid pair-checking all objects is to use some kind of data structure to keep track of objects and their general position and occupancy in space to detect potential overlaps without having to check every object against every object. This is called a broadphase in shop-talk. You definitely need to implement something like this eventually if you start increasing the number of objects. You don't state what a "large" number of circles are or the CPU you are targeting, so hopefully you can skip this and do it the simple way as a start but it is difficult to say unless you post your use-case.

Bottomline: I would go for the tried and tested non-continuous engine type, at a sufficient physics frequency to avoid the high-velocity-skipping case, and don't worry about performance. If you are actually interested in coding this for a game, and don't want to take care of the details, you could simply use some of the existing 2D physics libraries like Chipmunk or Box2D. I'm not familiar with their implementations but I'm sure they are good ways to learn the subject too if you study the code.