Hello,

I'm trying to implement character movement so that my character would slide along the wall (plane) instead of getting stuck next to it.

There is quite a lot of information regarding character sliding on the internet. However all that information seems to be covering only basic cases where character slides only on one plane at a time (collides with one plane at a time). I could not find any information about how to solve corner cases with multiple planes for example where character collides simultaneously with two walls and ground.

My current implementation's general idea is to:

1. calculate the movement velocity vector (intended position change) 

2. try to move my character along that vector if vector length is bigger than some epsilon.

    2. a. If there is no collision I update the position and I'm done.

    2. b. If there is a collision, I move character to the TOI (time of impact),

3. then for the remaining velocity vector I calculate new velocity vector depending on collision normal and repeat the process (go back to 2.)

This seems to work in simple cases, when I'm dealing with one plane (ground for instance). It also seems to work if I simultaneously collide with two objects (ground and wall) if two collision normals are perpendicular. However if angle between two simultaneously collision normals are less than 90° (like "V" corners), my new velocity vector (3.) starts bouncing back and forward between these two surfaces and I need quite a few iterations to resolve the final position. The smaller the angle the more iterations I need. If it was 2d I probably could just stop the algorithm and bale out if I find out that I'm "bouncing" between two surfaces, but in 3D every time I "bounce" my velocity vector slowly changes direction away from current collision normals. But as I said it takes quite a few iterations to get the final result, and this causes freezes, I could limit the iteration count however this might cause my character to stick to a wall instead of sliding along it as I would never reach the correct length of sliding vector.

Some engines like "DigitalRune" move character to the final position, then check for collisions and tries to resolve the final position, in that way you get the sliding effect. This could work in my case as well, however I'm using GJK for collision detection, so I could only solve shallow penetrations, not bigger than 2xMargin. Maybe after first collision and finding TOI I should move my character in smaller steps (not bigger than 2xMargin) for the remaining velocity. In that case I could resolve penetrations. This might work, however it seems that again I potentially can get a lot of iterations. Secondly, by resolving penetration my character might get stuck in another object.

I found one quite fresh topic related to mine:

Randy Gaul says that after finding TOI and collision normal "<..>calculating resolution terms is trivial". Sadly, I find it not that trivial ?

I know that all my rambling is confusing and hard to understand, but I hope you'll be able to give me some tips.

Any help will be appreciated thank you.

2 hours ago, Grambuolys said:

If it was 2d I probably could just stop the algorithm and bale out if I find out that I'm "bouncing" between two surfaces, but in 3D every time I "bounce" my velocity vector slowly changes direction away from current collision normals.

You can do this in 3D as well, simply check if the angle between your initial velocity vector and the newly calculated velocity vector is larger than 90 degrees.

Some links to read:

The ping-pong effect for acute angles is a weakness of the iterative seidel solver. Any solution would involve somehow looking at more than one plane at a time to detect this kind of case. Collecting planes in a set, or otherwise, followed by something to "kick" the system out of the locally difficult state.

Quote

Randy Gaul says that after finding TOI and collision normal "<..>calculating resolution terms is trivial". Sadly, I find it not that trivial ?

I don't think that thread is quite what you're looking for -- but I was describing a way to get a makeshift contact normal by calling GJK between a line segment and some other shape. This normal may or may not be useful, and if extra care isn't taken the character can be pressed along this normal into a colliding configuration. I would suggest checking out the other links.

I got this working at one point after some dicking around, at least for a sphere (and therefore an ellipsoid too). First you define a contact sphere which is a bit larger than your collision sphere. You consider all combinatios of pairs of planes that the contact sphere is touching and that your force vector is pushing towards. Then you take the cross product of the normals of each pair and that gives you vectors that you can move along. Then you select the best vector by taking the dot product of each vector and your force vector and look for the one with the smallest angle.

This worked really well for me. You can push your character up steep mountains and it will follow every nook and cranny perfectly.

Edit: I implemented this a few years back and I haven't looked at it in a while. I might be missing a few details, however it did in fact work very well. I'm on vacation at the moment, but I can look up the code when I get back and post the exact algorithm.

After I created this thread I thought about normal pair cross products as a possible solution, but I haven't tried to implement it yet. I guess I'll check the links Randy gave me first and try to play around with cross products afterwords.

I am really grateful for your help. Thank you very much!

I remembered a few more details.....I think I generare both single and double plane possible movement vectors and consider them together when picking the best one. Also before picking, I eliminate any vectors that are opposed by any contacting geometry. If no vectors are left, it means the character is stuck and must change direction.