Skip to main content
gamedev.net
🔒 Locked

Collision Response Problem

Started by Dtag 13 replies 2.4k views
Original Post
Dtag
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: 

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
Zakwayda
Zakwayda
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.
pTymN
pTymN
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
 
Dtag
Dtag
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 ;)
pTymN
pTymN
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.
 
Dtag
Dtag
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.
pTymN
pTymN
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.
 
Dtag
Dtag
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?
pTymN
pTymN
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.
 
Dtag
Dtag
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?
Zakwayda
Zakwayda
Looks like (maybe?) you already got it sorted, but I thought I'd mention that in my static intersection resolution step, I resolve the intersection along the direction of the penetration vector, not by moving the object back along the velocity vector. Although you still need the swept test for objects that move fast enough to tunnel, this method of resolving static intersection actually produces natural sliding collision response all by itself. Anyway, the point is that a properly implemented static resolution step shouldn't cause your object to get stuck or move unnaturally.
memon
memon
I was tackling with similar problem recently. Below is the code I used for the collision handling part. Note, I used verlet integration for the movement (hence the m_pos, and m_oldpos)

	int	iter = 15;	Vec3	prev(m_oldpos);	Vec3	pos(m_pos);	while(iter)	{		Vec3	delta(pos - prev);		float	len = delta.Length();		// Stop if moving just a little bit.		if(len < 0.0001f)			break;		// Check fo collisions, if no hits allow full movement.		if(!phys->CollideSweptSphere(prev, delta, m_rad, hitRes))			break;		// Check if the initial state is colliding.		if(hitRes.t < 0.00001f)		{			Vec3	d = hitRes.pos - prev			// Convert to ellipse space.			// Could report this back from the CollideSweptSphere too.			d.x /= m_rad.x;			d.y /= m_rad.y;			d.z /= m_rad.z;			d.Normalize();			d *= 1.01f;			d.x *= m_rad.x;			d.y *= m_rad.y;			d.z *= m_rad.z;			prev = hitRes.pos - d;			continue;		}		Vec3	coll = prev + delta * hitRes.t + hitRes.norm * 0.0001f;		Vec3	D = pos - coll;		Vec3	Dn = (D.Dot(hitRes.norm)) * hitRes.norm;		Vec3	Dt = D - Dn;		static float friction = 0.01f;		static float restitution = 0.5f;		pos = coll + (Dn * -restitution + Dt * (1.0f - friction));		prev = coll;		--iter;	}	// Update the position.	m_pos = pos;


The hit result structure contains the time of collision, the normal of the collision and point on surface of the collision.

I also do "backface culling in the collision test code", that is only report the collision if moving towards the polygon. Unless I did that the ellipsoid got stuck once it was initially intersecting with the geometry (t always almost zero).

I believed long and hard that it would be possible that the last position is always safe. But for some reason the ellipsoid just sometimes slipped inside geometry. There is obvious flaw in the above code in the check if the ellipsoid is moving just a little bit, which basically allows the penetration to happen. But I think the almost parallel movement is root of the cause. The floating point accuracy just is not enough.

Later I moved to use more simpler method. Just move the object, check for collisions and push away. The verlet integration takes care of details of sliding along a surface. That works much better in my case since I also wanted to collide with capsules and objects composited from multiple primitives too. And it was so simple to implement too :)
Dtag
Dtag
Assuming that 'hitRes.pos' in memons code refers to the actual collision point where the sphere intersected with the tri, you both appear to be pushing back along the sliding plane normal. I just tried it and it indeed _appears_ to work well ;)... What Iam asking myself is: Not moving on the velocity vector means "unchecked movement" meaning that the amount pushed away from from the plane is never checked for intersections with other tris. So having moving into a sharp corner could make one of the planes push the sphere through the other tri... couldnt it? I tried to reproduce the case, and it was indeed the case that in these corner situations my equivalent of memons code piece

// Check if the initial state is colliding.
if(hitRes.t < 0.00001f)
{
...

Catched these cases and brought the sphere back into the world, resulting in a slight jitter of the camera in these cases ( not a really bad one tough ). All in all Iam not sure whether this is going to work in ALL cases?


jyk: It worked alot better with the stepping, but thats obviously a hack because not all physical objects should have stepping :/
Zakwayda
Zakwayda
One more comment: the static resolution step should be recursive as well, that is, if an intersection is detected you should resolve it and then run the test again. This should handle most cases like the one you describe, where resolving one intersection causes another.

There are cases where the object can get stuck between two surfaces, and be 'bounced' back and forth. I'm not sure what the best way to handle these cases is, but in my implementation I just bailed back to the start position after a certain number of iterations (this didn't happen often, and given the proper restrictions on geometry or object size, you should be able to avoid it entirely).
Dtag
Dtag
Ok thanks everyone ;) After a bit more tweaking it appears to work perfectly now. Didnt have a getting stuck or anything after 20 min of intensive trying to break it, so Im considering that part as working ;)

Just one more thing: Does anyone know any resources in whats the best way to make it look physically more correct? I added gravity etc, ( with euler integration which appears to be enough for this ), and some basic factors to fade out velocity due to friction etc, but it looks somewhat unrealistic when things are falling ( either theyre too slow or too fast :/ ).
Additionally I didnt find a clean way to make the sphere not slide off hills due to gravity ( my way was to prevent sliding of flat tris when the movement is gravitational and, but it didnt seem like a physically correct idea ;) )

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.