Interpolate and collisions

Lets take the simple example of a ball bouncing off a wall. The physics is separated from the display. The physics is set to run at say 20 frames per second and the display is running faster than this (usually something like 60 fps).

In order to have smooth rendering, the render function gets a parameter called alpha that is a percentage (float/double value between 0 and 1) of time elapsed for frame (ie. alpha = accumulator / time_per_physics_frame). And we interpolate using this value:

position = currentPosition * alpha + previousPosition * (1 - alpha)

This works well when moving from one position to the next. For example, if x = 2 and we moving at dx = 4 at high fps the ball gets rendered at x from 2 to 6.

Now say the ball has x = 2, dx = -4 and there is a wall at x = 0. The physics simulator updates the ball to x = 2, dx = 4 (Collision retains all energy and no elastic properties). So using the above interpolate there is no rendering of the ball hitting the wall.

How can the interpolate function handle things like wall collisions?

• Run the physics at a higher framerate. Jul 26 '12 at 23:15
• Exactly, why just 20FPS? That seems too inprecise. Jul 27 '12 at 0:07
• Well network games (ie. Quake 3) use a low frame per second for the updates. Anyway, even if I increase it, if the physics updates are less often then the display rate this problem still happens. So my question remains.
– grom
Jul 27 '12 at 4:16
• After more thought on this matter, I do need a much higher framerate for the physics. So then interpolate is basically only there to handle the exception where the CPU can't keep up. Or if an object is very fast moving.
– grom
Jul 27 '12 at 6:22

I had a similar problem regarding visual interpolation. In my case, I visually predicted physical movement inbetween the current and the next frame using object speeds. The problem was that objects were allowed to visually pass through solid obstacles before the physical simulation got there. There was a simple solution. Instead of trying to predict physical movement, I let my display actually FOLLOW physical simulation. In my case, it was as simple as this:

visualPos = actualPos - speed * (1.0 - alpha)

While this was my previous interpolation method

visualPos = actualPos + speed * alpha

That way, collisions were displayed properly.

However, this doesn't seem to provide a solution to your problem. I guess what I'm trying to say is: As long as you're interpolating, your results will never be perfect. In your specific case, I'd suggest increaing physics FPS - 20 seems really low.

Since your physics system presumably generates velocities for objects in addition to positions, you could use a Hermite spline for interpolation rather than just using linear interpolation. The Hermite spline accepts tangent vectors for the beginning and end of the spline, where you can put in the object's velocity.

This should help your example because when the ball goes from x = 2, dx = -4 to x = 2, dx = 4, the cubic spline will have it moving toward the wall then reversing velocity and returning to its original position. It won't quite look like a collision because it will smoothly reverse velocity over the duration of the timestep, kinda like a spaceship firing its thrusters to veer away from the wall, rather than hitting the wall and bouncing off - which is a pretty much discontinuous change in velocity. However, it's probably still better than the ball just staying in place.

This question still comes up on Google and I came up with a neat way to solve interpolating the location during a collision, so I am posting here in hopes it will help someone else stumbling here.

This is based on a physics system as explained in the Gaffer on games blogs, where you have an accumulator and interpolate positions between the steps.

Essentially what you need to do is interpolate either

A) Between the point before the collision and the point of the collision B) Between the point of the collision and the reflected location.

Whichever you choose is based on if the accumulator is behind or ahead of the collision time.

Here is the complete interpolation code

float alpha = physicsSpace.Accumulator / PHYSICS_HZ;
body& body = physicsSpace.Bodies[i];
v3 interpolateFrom = body.PreviousState.Position;
v3 interpolateTo = body.State.Position;
if (body.CollisionCount > 0) {
collision firstCollision = body.Collisions;

if (alpha <= firstCollision.Time) {
// Time is the from 0.0f to 1.0f over the hz
float remainder = firstCollision.Time;
alpha /= remainder;
interpolateTo = firstCollision.Point;
} else {
float remainder = 1.0f - firstCollision.Time;
alpha = (alpha - firstCollision.Time) / remainder;
body.PreviousState.Position = firstCollision.Point;
body.PreviousState.Velocity = body.State.Velocity;
interpolateFrom = firstCollision.Point;
}
}
body.InterpolatedPosition = ((1.0f - alpha) * interpolateFrom) +
((alpha) * interpolateTo);

What you're experiencing is a very, very common problem with physics engines. Basically, your object is falling between the cracks that your framerate provides. First it's approaching the wall and then it's inside of the wall, without registering a collision!

There are two solutions to this problem:

• Ducktape it - Use a smaller timestep, which is effectively a higher framerate. If you up the framerate to 60 fps, there are now 6 frames between "before the wall" and "inside the wall". Why is this a ducktape solution? Because your framerate might still not be high enough and you can't up it forever.

• Fix it properly - Don't base your physics on just the current position.

I'm not going to bother explaining the first solution, it's simple enough. If that works for you, great! Many games have shipped with that solution in place.

However, I really want to explain the second solution.

Let's say we have the following situation: Here, the red ball wants to bounce off the wall. We can see its direction denoted by the blue line. However, this isn't its direction, but its velocity, which is direction * speed. So, what we have here is the ball's current position and the ball's future position, which would be position + (direction * speed).

Now we can deflect our ball using the wall's surface normal: The important thing to note here: the ball hasn't moved yet. As far as the ball is concerned, it is still in front of a wall.

The code should now look this:

• Ball updates its direction and speed, if necessary.
• Ball calculates its velocity from direction and speed.
• Ball calculates its future position from position and velocity.
• Scene uses Ball's position and future position to determine that Ball will collide with Wall.
• Wall reflects Ball's velocity over its surface normal to create a new future position, a new direction and a new speed for Ball.
• Ball sets its position to future position and updates its direction and speed.

Now your Ball can never fall through the cracks. Even better: multiple objects can collide with Ball and it will hopefully all resolve to 1 future position. However, this will require multiple passes of collision resolving by the Scene.

For further reading, look for "sweep test".

• As far as I can see, this is a (good) answer to a different question. You're talking about swept collision detection while the topic is about visual interpolation regarding physics.