3
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Your question is slightly confusing, can you clarify, are the black and red arrows all happening in one single step, or is each one happening in a different frame, and so you're seeing jitter/zig-zag from side to side while it proceeds over time? \$\endgroup\$ Apr 24, 2020 at 0:47
  • \$\begingroup\$ I modified the color for each frame, I hope it's clearer what's going on now. \$\endgroup\$ Apr 24, 2020 at 11:28
  • \$\begingroup\$ Watching this question now for a while, I'll try to help you out if you are still looking for a solution. However, I have a question: Which is the "good path" you are looking for? Along the corner of the surfaces A and B? \$\endgroup\$
    – wychmaster
    Apr 26, 2020 at 11:24
  • \$\begingroup\$ Yes, along the intersection line of both planes A and B. \$\endgroup\$ Apr 26, 2020 at 11:53
  • \$\begingroup\$ I think the main problem is, that you need to treat an already corrected vector differently than an unmodified one. After the first collision of the vector, you need to pass this information to every subsequent collision check. During the handling of the second collision, you have to check if the vector is still in contact with the first object it collided with. If so, the new vector must be calculated with a different approach. However, this depends on the type of contact. A convex corner will be treated different than a concave one. \$\endgroup\$
    – wychmaster
    Apr 26, 2020 at 17:53

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .