• Create Account

# Moving from collision detection to simple interactions with an environment

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1pondwater  Members   -  Reputation: 191

Like
0Likes
Like

Posted 06 August 2011 - 06:59 PM

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?

### #2japro  Members   -  Reputation: 887

Like
1Likes
Like

Posted 07 August 2011 - 10:47 AM

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.

### #3pondwater  Members   -  Reputation: 191

Like
0Likes
Like

Posted 07 August 2011 - 01:40 PM

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.

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?

### #4maxgpgpu  Crossbones+   -  Reputation: 197

Like
1Likes
Like

Posted 07 August 2011 - 02:55 PM

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!

### #5japro  Members   -  Reputation: 887

Like
1Likes
Like

Posted 07 August 2011 - 03:00 PM

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?

Both approaches are somewhat unphysical, but i think the minimum penetration generally is the one you should try first and only start "fixing" it when actual problems arise. I imagine that calculating penetration along the movement direction would result in actors instantly getting stuck as soon as they hit something. This could be especially problematic when there is gravity. With gravity a moving actor will pickup a slight down movement every time step which should then be corrected by the collision. Now if he is in a valid position "touching" the ground at the beginning of the step the simulation with gravity will make him move diagonally downwards, so if you resolve the collision by backtracking along the movement direction he ends in the latest valid position which is the same one he was in at the beginning of the step...
Correcting along minimum penetration will automatically give you most of the expected behavior, like actors that hit a wall at an angle will slide along the wall instead of just being stuck on it.
In your example the penetration is very large in comparison to the object sizes which is the main cause why it ends up looking weird. A way to reduce/fix this would be to detect if the penetration is big in comparison to the object size and if necessary to perform "substeps" in the movement. Also the objects that are affected by this kind of glitch are usually fast moving so the glitch wont be as visible anyway.

### #6pondwater  Members   -  Reputation: 191

Like
0Likes
Like

Posted 08 August 2011 - 01:18 AM

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?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS