So for the past few weeks i've been implementing different algorithms for collision detection, and am curious if there are any well known and efficient methods for using the collision and intersection depth data to properly maintain interactions with an actor and its environment. Im not talking full blown ragdoll physics, just simple traversing terrain and what occurs when the actor encounters a wall, downward hill, upward hill, fall, etc. Think of super mario 64 for an example.

For example these are two scenarios im curious about:



In the side view example, moving from left to right the actor would move off a cliff, and continue moving along the ground below until he reachs an edge that is too steep to move up. What kind of algorithm is used to ensure that the character follows the contour of the ground beneath him.

In the top view example, a character is walking into a wall at a slight angle which would result in the actor moving along the wall. I figure for this type of scenario I would calculate per frame the penetration depth in the direction the actor is moving, and instead of moving the character that distance into the wall, he would move that distance along the wall. That seems like the most reasonable approach.

For now i can detect when a collision is occuring, and am working on a system to calculate the penetration depth in a specific direction, which will be the direction of velocity. Most depth algorithms i've looked at find a 'least depth' distance of penetration. Would that be more useful for developing a system seen in the above pictures? Any resources anyone could recommend?

[quote name='pondwater' timestamp='1312678767' post='4845619']Most depth algorithms i've looked at find a 'least depth' distance of penetration. Would that be more useful for developing a system seen in the above pictures? Any resources anyone could recommend?

The minimum penetration depth is useful because it tells you the minimum displacement needed to resolve the collision for convex polygons. So a good point to start with is to just offset the position of your object/player/whatever by that minimum penetration. As long as stuff isn't moving "too far" in a single time step this already produces reasonable results. It can lead to weird problems like objects "tunneling" through each other when the object size is in the range of the movement per time step or be glitchy when objects end up in impossible situations like being squeezed into a space where they don't fit.
[/quote]

Im just worried that using minimum penetration depth instead of penetration depth in the direction of motion could cause strange behavior such as an actor hitting a wall and then being placed beside the wall, heres an example below. Now you say as long as they arent moving to far per single step it produces reasonable results, would it produce better results if it was done in the direction of motion?

[font="Book Antiqua"]You don't say what collision detection technique you adopted.

If your technique is GJK, the closest parts of the objects can be computed at the last step of the algorithm when convex objects are found to not be in collision, because the last set of vertices on both objects when GJK finds "no intersection" are part of the closest features on the objects.

When GJK does find a collision, the distance from the origin (of the minkowski difference) to the shell (of the minkowski difference) is penetration distance, and you can find "minimum penetration distance" via pass through the vertices (and more efficient techniques exist if you start with the last sets of vertices in the GJK search).

For what you're doing (at the moment anyway), the "minimum penetration distance" might be perfectly adequate. Effectively, you'll be taking a foot that has pushed its way below ground level and moving it to the closest place at surface level. As long as your slope doesn't change much on each step, then the error won't be very large. When going uphill, the foot will be pushed further back than would happen in fact, though you could add a "forward fudge factor" roughly equal to the penetration depth to offset that fairly accurately.

Your problem will be opposite when walking downhill --- you won't get a collision at all, and the player will either start walking above the surface, or you'll need to resolve this some other way (simply take the "closest approach" information from GJK and move the foot that distance and direction), perhaps with another fudge factor (you'll find out).

But this raises another point. You should probably not make the player walking horizontally. At each step you should make the player start walking uphill or downhill by whatever angle is necessary to compensate for the "penetration depth" or "closest approach" information on the previous step. That way errors will be minimized (except when reaching the tip top of a sharp pointed hilltop, or the bottom of a V-shape gulley.

Best of all, if you can "look forward" one step distance in the walking direction and see how much higher or lower the terrain is, you can then have the player take a step at the appropriate upward or downward angle. That's how people work (by looking ahead), unless they're blind or walking in the dark.

Anyway, that's my perspective, assuming I understand what you're shooting for.

Oh, one more thing. If you start doing collision detection for other objects or other situations, you need to realize that the direction and distance of the "minimum penetration" will sometimes be radically different than the collision profile. Just visualize the collision profile when one object just grazes another. The moving object may have moved 10 meters or more while in collision (all during the past frame time), but never have penetrated more than 1 meter (or 0.1 meter) into the other object, and may even be penetrating only 0.01 meter (or 0.001 meter) when your code performs the collision computation at the next frame time. In this case your code needs to move the object 10, 100, 1000 or more times the penetration depth it finds and in a direction roughly 90-degrees from the penetration depth direction.

Oh, the joys of collision detection and response!
[/font]

thanks for the input. I've currenty got a GJK-SAT algorithm working (, however im debating between switching to MPR or even SAT at this point for simplicity. Any idea how much more efficient GJK/MPR is vs SAT?