Avoid shaking artifacts in 3D continuous collision detection

Question

I am programming a 3D game physics engine that uses continuous collision detection to avoid my objects from being able to "tunnel" through the geometry.

Here is basically how it works:

1. Execute a swept-object/world collision check
2. Move the object up to the exact point where it collides
3. If no time is remaining, everything is done, just stop
4. Else, update the velocity so that the object "slides" in a direction orthogonal to the collision normal before returning to step 1. This is the formula I use for this sliding (I just remove the component of the motion in the normal direction): velocity = velocity - (velocity dot normal) * normal

My problem occurs in this kind of situation:

(Do not take into account faces other than A and B, their only purpose is the emphasize the 3D aspect of the shape)

In the first frame, the object first follows the black arrow, then collides face A. It slides correctly on face A (first red arrow) and then climbs on face B (second red arrow). The problem with this algorithm is precisely the fact that it can climb on the opposite face: after several consecutive frames (here the other frames are the cyan and green ones), the general motion will follow the good path (the intersection line of planes A and B), but with a local left-right shaking artifact that I would appreciate getting rid of.

Any idea to solve this would be greatly appreciated.

Answer 1

I had the same problem and I found a solution in the paper "Improving the Numerical Robustness of Sphere Swept Collision Detection" by Jeff Linahan, found here: https://arxiv.org/ftp/arxiv/papers/1211/1211.0059.pdf

In short, your collision response loop should have exactly three iterations:

• If you collide in the first iteration you do the sliding response as usual.
• If you collide in the second iteration you calculate the second sliding plane, but you don't project your velocity vector onto it. Instead, you calculate the crease vector, which is equal to the normalized cross product of the normals of the first and second sliding planes. Now project your velocity onto the crease vector-- that's your velocity for the next and final iteration.
• If you collide in the third iteration, there is no sliding response. Just stop at the point of impact.

The above linked paper contains illustrations and explanations of why this works.

Also caveat, the author notes that while this solves the jitteriness, it also increases instances of getting stuck in geometry. He goes on to explain how to mitigate this by tweaking tolerance values in his implementation, but I'm not sure how that would apply to what you're doing.