Jump to content
  • Advertisement
Sign in to follow this  
Dtag

Collision Response Problem

This topic is 4485 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi Iam working on a Swept Sphere <-> Triangle collision detection/response. The detection part appears to be working well. I pass the Sphere center and the desired movement vector - what I get back is a float ( called t ) telling how much of the movement could be executed without collision in the given direction ( 1.0 for full movement ). Now in order to stay numerically stable, I dont want to move the Sphere ON the surface, but a little in front of the surface. My code to do so is simply as follows:
float mag=Magnitude(info.vVel);
// the min makes sure we are never pushed farther away than where we came from
CVec3 pushback=Normalize(-info.vVel)*min(EPSILON,mag); // 0.085f for me
CVec3 newPos=info.vStart+info.t*info.vVel+pushback;

Tough this kinda seems to work, Iam not entirely happy with the way this is solved, since the amount we are kept away from the collision point depends on the velocity vector. Thus if the velocity vector is chosen accordingly, its still possible to approach further than EPSILON to the collision point, which is not a nice thing. I tried playing around with the EPSILON but I found it quite impossible to find a value that works well for everything: Too large values cause a jittering ( Sphere moves into the tri, gets pushed back, to a distance of EPSILON, then it moves again ( a distance smaller than EPSILON ), and it doesnt get pushed back because no collision is detected, then it moves into the tri again -> pushback -> jittering ), smaller values lead to a problem where the sphere gets occasionally stuck inside the tri, and this problem is still there with large values ( just less frequently ). I tried to derive a formula to compute how much velocity I have to take back in order to get a distance of EPSILON to the collision point, but that didnt really help ( Iam not sure why because its kinda impossible to debug it, but obviously theres too many cases where the camera makes a move smaller than EPSILON towards the surface ) So whats the correct way to keep some safety distance towards the surface? Maybe my timesteps are too small or something? And that leads to the problem of getting stuck sometimes? ( It really occurs only very seldom... I have to try for a few minutes before I got it stuck...but thats still not acceptable ) Thanks alot

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Dtag
Hi
Iam working on a Swept Sphere <-> Triangle collision detection/response. The detection part appears to be working well. I pass the Sphere center and the desired movement vector - what I get back is a float ( called t ) telling how much of the movement could be executed without collision in the given direction ( 1.0 for full movement ).
Now in order to stay numerically stable, I dont want to move the Sphere ON the surface, but a little in front of the surface. My code to do so is simply as follows:

*** Source Snippet Removed ***

Tough this kinda seems to work, Iam not entirely happy with the way this is solved, since the amount we are kept away from the collision point depends on the velocity vector. Thus if the velocity vector is chosen accordingly, its still possible to approach further than EPSILON to the collision point, which is not a nice thing. I tried playing around with the EPSILON but I found it quite impossible to find a value that works well for everything: Too large values cause a jittering ( Sphere moves into the tri, gets pushed back, to a distance of EPSILON, then it moves again ( a distance smaller than EPSILON ), and it doesnt get pushed back because no collision is detected, then it moves into the tri again -> pushback -> jittering ), smaller values lead to a problem where the sphere gets occasionally stuck inside the tri, and this problem is still there with large values ( just less frequently ).

I tried to derive a formula to compute how much velocity I have to take back in order to get a distance of EPSILON to the collision point, but that didnt really help ( Iam not sure why because its kinda impossible to debug it, but obviously theres too many cases where the camera makes a move smaller than EPSILON towards the surface )

So whats the correct way to keep some safety distance towards the surface?

Maybe my timesteps are too small or something? And that leads to the problem of getting stuck sometimes? ( It really occurs only very seldom... I have to try for a few minutes before I got it stuck...but thats still not acceptable )

Thanks alot
I don't have a nice clean answer for you, but I will say that I've implemented swept sphere vs. poly soup coldet, and after much tweaking was able to get results I was happy with (that is, no shaking, jittering, getting stuck, or falling through, even under extreme conditions).

There were a number of things that went into this, but what might be most relevant to your question is that I gave up on any assumptions about whether the sphere would be intersecting geometry at the end of the time step, or how close it would be. Like you I did have an epsilon 'buffer', but even then it's hard to guarantee a particular post-condition. To deal with this, I performed both a swept test and a static intersection test; the static test caught any anomalous post-conditions and put the sphere back in a non-intersecting state. Even then there are weird cases that can occur; in these (rare) cases you can just bail back to the initial position, which presumably is known to be non-intersecting.

I know that's all pretty vague; feel free to ask if you need more info.

Share this post


Link to post
Share on other sites
Hi,

Very interesting, I just dealt with this problem on my 2D physics engine. I have one phase for moving and positioning objects, and then a static movement phase for checking to see which objects are within *epsilon* of other objects. If an object is close to another object, it gets a contact. A contact stores a pointer to the other object, a pointer to the part of each objects' geometry that is touching, and a normal of collision. With the normal of collision, it is very easy to verify that an object is specifying an invalid movement. Also, sliding can be done easily.

When you do your collisions, are all actors moving dynamically, or are you moving and checking collisons one object at a time?

-Tim Kerchmar

Share this post


Link to post
Share on other sites
Hey
I just tried what jyk suggested. It fixed all problems where the sphere was getting INTO the world somewhere, but instead, the sphere just stopped at that point because the sphere couldnt be moved further back.
My implementation is like this:
If a full movement could be done:
Loop:
See if the sphere is intersecting with any geometry. If so push it back a little along the velocity vector ( but not farther then the length of the velocity vector ). Loop until its not intersecting anymore;

If no full movement could be done. Initially perform a small pushback. Then the same loop as above.

The cases where it got stuck were always cases where the sphere could not be pushed back far enough to get enough distance to be not colliding. Tough in all cases where the sphere was pushed back, the movement felt a little weird.

Just to test a little, I also implemented a small stepping algorithm ( First move up by STEPSIZE, then move velocity-STEPSIZE, and finally apply gravity. ) This turned out to fix nearly all of the problems! Iam not sure why it helped so much.
Iam also not sure whether this is a clean solution, any ideas on that?



As for pTymN:
"With the normal of collision, it is very easy to verify that an object is specifying an invalid movement."
Its not only my problem to DETECT invalid movement, but also how to react properly. If its "too late" to push the sphere back, what should I do?

"When you do your collisions, are all actors moving dynamically, or are you moving and checking collisons one object at a time?""
Iam having a sphere ( represented by the camera for testing purposes right now ) and Iam testing that against terrain. I havent implemented dynamic objects<->dynamic objects yet. My plan was to do the tests against the terrain with an ellipsoid, and the tests of objects against each other using AABB<->AABBs. Havent put any more thinking into that yet tough ;)

Share this post


Link to post
Share on other sites
It sounds like you are using static-dynamic, which is a better solution than just moving the object incrementally and seeing if that position intersects geometry. Since you are "gauranteed" that the sphere does not start out intersecting the terrain, can't you just do this:

CVec3 newPos=info.vStart+info.t*info.vVel*0.9;

It seems that your epsilon can get too small for larger numbers, especially since you are using float not double. This line of code would automatically adjust the pushback with the magnitude of the movement.

Beware that it can be confusing to tell between a collision that happens at 1.0 and one that never happened. There is certainly no reason to only move 90% of the distance when there has been no collision.

Share this post


Link to post
Share on other sites
Quote:
Original post by pTymN
Since you are "gauranteed" that the sphere does not start out intersecting the terrain, can't you just do this:

CVec3 newPos=info.vStart+info.t*info.vVel*0.9;


As states above, I have played around alot with the epsilon. Using a too low epsilon like you suggested results in jittering problems.

Share this post


Link to post
Share on other sites
Yeah, but your epsilon doesn't scale the amount of velocity added to the starting point. Your epsilon subtracts a constant amount from the velocity. I had good luck with scaling the velocity in my engine.

Share this post


Link to post
Share on other sites
Hmmm what should that be good for? Why should the algorithm need more safetey distance for a fast moving object than for a small moving object?

Share this post


Link to post
Share on other sites
Could you give it a try? I can't really explain why it works, but I experienced less problems with my physics engine when I switched methods.

Share this post


Link to post
Share on other sites
I just tried what you suggested, its pretty much the same effect as a medium epsilon ( As expected ). Tough since this does not have any advantage, why decrease the velocity procentually?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!