Wall penetration

Question

I have a terrain with geometry that is fairly ridged. I needed to make sure the player didn't enter the world geometry, so I used sphere-triangle intersections (after narrow down of which tris to test using AABBs on chunks of the terrain).

This works fine, the player smoothly appears to "roll off" the terrain when you walk into it.

What I do is detect the penetration distance of the sphere into the terrain, then just push the player back in the direction of the terrain face. That clears him of the world geometry.

Method 1:

Push the bounding sphere of the player back in the direction of the normal of the wall he hit, until he exits the wall.

However. This has had the awkward side effect of occassionally pushing the player into another face (when the player is near the meeting of 2 faces). The result is this nasty bounce-shake between the two walls and the player gets stuck until he changes direction (turns around).

Initially I tried to solve this problem by:

• "Cancel" previous move by translating player back along his "last move" vector the exact distance he moved if he touches a wall

  • But this causes walls to feel "sticky". You will get "caught" on walls if you use this, if any component of your velocity enters a wall (so you cannot "slide" by running diagonally into the wall).

• Pushing the player back along his "last move" vector only far enough to clear the wall. This looks better at first, but converges to the same sticky walls problem as "fully cancelling the move" if the player is already touching the wall, but is trying to slide along it by running diagonally into it

Method 2:

Cancel or partially cancel the move by pushing the player back along the vector from which he came, until he exits the wall he deepest hit

So it seems I was on the right track with the first approach (push in wall's normal direction). What I'm going to try next is a hybrid:

• Look for wall intersection
  • If one is found, push him back along the normal of the wall, then CHECK FOR A WALL COLLISION AGAIN (apply Method #1)
    • If a 2nd wall collision is found, cancel the move until he exits the wall (apply Method #2)

Am I on the right track here? Is there a better way to solve this?

Answer 1

Here's one quick nice trick implemented in the latest Physics SDK: if you have a ball experiencing multiple collisions, then use impulses to resolve collisions.

1. find the number of contact points (contact point = {pair, position, normal} )
2. divide the ball into n balls with the same center of mass (basically sharing the same position and volume, of course not colliding with each other), but having the initial sphere's mass divided by n
3. now simply compute for each sphere the necessary impulse required to push it out of the wall
4. when all contact points are solved by finding appropriate impulses, just add those impulses together and apply them to your big sphere
5. Inside a frame, to assure convergence, you can perform 4 such iterations to find a solution (relaxation).

Nvidia Physics researchers claim it's even jitter free :).

Answer 2

You could add one invisible wall to prevent players from trying to squeeze into these areas. So instead of bouncing between two walls at an acute angle, they could bounce off three walls with obtuse angles between them. That would avoid your feedback problem without additional collision logic. But to the player, it would appear that they simply can't move any farther into the joint of the two visible walls.

Answer 3

Method #1 does work, but performance is a lot better if you use the interpolated normal of the face (instead of the face normal, as I had been using).

But you can still get sporadic behavior with this. The "weird bounce" behavior occurs mostly when a sphere "chomps" into the side of a triangle (instead of "kissing" the triangle from above)

So I found there were actually 3 cases to handle distinctly to avoid sporadic bouncing behavior:

1. "Kissing" intersections (normal intersections like you'd expect).

For these you push off in the interpolated normal direction (use barycentric coordinates to determine the interpolated normal from the vertex normals -- you have the barycentric coordinates from the sphere-tri test anyway)

2. "Chomping Edge" intersections

3. "Chomping Corner"

For chomping edge and chomping corner, don't use the normal direction, that will push your sphere WAY off in the wrong direction. Instead you need the closest pt on the tri to the sphere center, and to push the sphere OFF the triangle in the direction from the closest pt on the tri to the sphere center.

A couple of other notes:

• I only select one tri to push back on each frame.
• The tri I select (of all the tris intersected) is the tri with the closest tri centroid to the sphere centroid. Choosing the tri with the deepest penetration distance does not seem to be a good choice.

Answer 4

The "canceling" you described earlier should work, just you need to separate the movement between the axes and check both seperatedly. E.g. a collision on the X-axis shouldn't cancel the movement on the Y-axis and vice versa.

This also applies to the bouncing, hitting a wall should just invert the movement on the X-axis and not affect the movement on the Y-axis at all.