# Simple collision response - collide and slide

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

## Recommended Posts

I'm having some problems with my main entity movement algorithm. What tutorials and docs usually describe is collision detection, but I've found documents about how to organize your movement around its results not to be as readily available. I got Paul Nettle's docs and demo for collision detection using ellipsoids, though, and learned quite a few things from it. Anyway, the kind of response I'm aiming for is to slide against entities I collide with. The idea for the algorithm is to find the closest entity my moving object (a sphere, and all the other objects currently use bounding boxes) is going to collide with, to move the object as close to it as possible, and then to project what's remaining of my movement vector on it (the object we're collding with is only defined by its normal vector at the collision point and the distance we have to travel to hit it). This projection becomes my new movement vector, and I continue until the vector's depleted. It's simple enough in theory, but obviously I'm making some error somewhere in the implementation. It works fine as long as I'm colliding with only one entity, but as soon as I'm colliding with several objects at once the moving object may be violently pushed away from its colliders. For example in this situation the object, which should normally fall down and get stuck between the two boxes below, will be pushed upwards rather violently upon contact with both surfaces at the same time. The bounding volumes are displayed in white, by the way. Here's a look at the movement code. Defined outside of this bit are m_position and m_speed, which are attributes of the moving object, fElapsedTime, which is provided by the application, and the code uses D3DX functions for all vector math, but I think the names are explanatory enough. I'm pretty certain the problem doesn't come from the scene's collider detection method, since single-object collisions react exactly as I'd expect them to.
D3DXVECTOR3 movement=m_speed*fElapsedTime;
D3DXVECTOR3 originalPosition=m_position;
c_MoveInfo moveInfo;

bool collisionOccured=true;
unsigned int collisionLoops= MAXCOLLISIONLOOPS;
while (collisionLoops-- && collisionOccured
&& D3DXVec3LengthSq(&movement) > EPSILON)
{
//movement is decomposed into an unit vector for direction and a distance
moveInfo.moveDistance=D3DXVec3Length(&movement);
D3DXVec3Normalize(&moveInfo.moveDirection,&movement);
// the dynamic collision method returns the distance to the nearest collided entity
// and the normal to the collided surface if something is hit during movement.
collisionOccured=m_parentScene->dynamicCollision(this,&moveInfo);
if (collisionOccured){
//move entity right against the collider
m_position+=moveInfo.moveDirection*moveInfo.collisionDistance;
//substract the traveled bit from total intended movement
movement-=moveInfo.moveDirection*moveInfo.collisionDistance;
//project movement on the collided surface
movement=(movement- D3DXVec3Dot(&movement, &moveInfo.collisionNormal)*moveInfo.collisionNormal);
} else {
//no collision, simple movement
m_position+=movement;
}
}
m_speed=(m_position-originalPosition)/fElapsedTime;


If anybody's got some idea as to why it's incorrect, I'm open to suggestions. Possibly it's a rather silly error, but I've been staring at it for too long and can't seem to find it.

##### Share on other sites
The violent collision reaction could be getting caused by a divide by zero. I'd make sure your fElapsedTime is always greater than some epsilon value before doing the division.

Regards,
ViLiO

##### Share on other sites
The intuitive answer to that would be that if fElapsedTime is near zero the movement vector's lenth will be near zero too and the loop won't loop.

Did add a check, to be sure ;) and it doesn't change anything.

I think it may be a consequence to the moving object being embedded in the collider, since it's pretty much the only case where the movement would go backwards, but I don't really get why the reaction would be so violent - the sphere is suddenly moved backwards to a distance apparently greater than the intended movement, which is why it's then catapulted away as a consequence of the way I recompute speed at the end of the movement.

[Edited by - chevluh on October 15, 2006 3:59:39 PM]

##### Share on other sites
So, you are saying you added a check for fElapsedTime that prevents this line:
m_speed=(m_position-originalPosition)/fElapsedTime;

from running?

If that doesn't solve it, assert! Store the magnatude of your movement before and after each phase, and assert that it doesn't go up.

While you are at it, given that the code should NOT add velocity in any direction, make sure that (unit vector in eventual distance you travelled) dot (original velocity) is at least as long as (eventual distance you travelled).

(In addition, store for post-mortem analysis any important variables you change.)

##### Share on other sites
Quote:
 Original post by NotAYakkSo, you are saying you added a check for fElapsedTime that prevents this line:m_speed=(m_position-originalPosition)/fElapsedTime;from running?

precisely. And added a breakpoint to see if that check was ever true. Turns out it isn't, and my catapult seems to be unrelated. Which is kinda unsurprising, since my problem seems to be linked to specific geometric configurations rather than the flow of time.

Excellent suggestion about the asserts, I'll do just that.

##### Share on other sites
note that, if you have angles < 90 degrees, and your object gets funneled, then you can encounter cases where you have intersections if you are not VERY careful with tolerances. And you will have to use tolerances due to the floating point innacuracies.

I can;t tell you exactly what tolerances you should use and where, but what you could do, assert if you detect an intersection.

also assert for potential divisions by zero, obviously.

##### Share on other sites
Shouldnt this be much easier with Verlet integration?
No speed, extremely stable, and I think easier.
Advanced Character Physics by Thomas Jakobsen

##### Share on other sites
Quote:
 Original post by GagyiShouldnt this be much easier with Verlet integration?

It's quite possible, but the very title of the doc and its abstract ensured its storage in my "physics stuff, for later" folder instead of the "basic moving sphere" one :)
I'll have a look at it, but I'd like to finish what I have started with the current algo, since it's doesn't seem that far from finished.

The symptoms match what Oliii mentioned (incorrect behavior for angles <90 degrees, other cases are stable) and tolerences are indeed mostly missing, so I'll go in that direction for now.

##### Share on other sites
It's hard to tell from just a pic, but what might be happening is that each push along a collision normal moves the object into the other collision face, back and forth, several times. Thus when the object is in collision with two collision faces, as here, it can't project the movement onto either of them (because that puts it in collision with the other). The variable movement will be decreased each time until it ends up 'negative' (i.e. pointing in a direction largely opposite to the original object velocity), and the object will 'back up' until it's free of both colliders (which is probably correct as there's not really any other sane answer). The big jump away comes from setting the speed at the end: since you've gone through a lot of collision iterations and potentially 'backed up' a long way, the correct speed is almost certainly zero in this instance.

Thus, I suggest:
if(DotProduct(m_speed, movement) < 0) m_speed = Vector(0,0,0);else m_speed = (m_position-originalPosition)/fElapsedTime;

... i.e., if the object has been turned around by more than 90 degrees, it stops instead of 'bouncing'.

##### Share on other sites
Quote:
 Original post by Bob JanovaThe big jump away comes from setting the speed at the end

Well, yes and no. The violent, physically correct, catapult-like effect comes from setting the speed, but only because the resulting computed movement was not the one expected. The fix you suggest only gets rid of the physical consequences ("catapulting" the object away), not the initial movement backwards. Which essentially translates into mad jittering when you push into an acute angle.

I think said movement comes from sliding parallel to a plane, because of floating point errors (since in case of intersections I'm pushed away along the direction of movement, if the movement's near parallel to the surface the freeing position can be far away). Normally the collision detection routine ignores the last collided plane, because I'm obviously sliding parallel to it, but when bouncing back and forth between two objects it's not enough, so I need to work on those tolerances.

[Edited by - chevluh on October 16, 2006 3:05:33 PM]

##### Share on other sites
What if you don't move the object, but instead simply restrict the object's movement?

You start at X. Your velocity is V.

Prevent Collision:
If (X, X+V) crosses a line L, then...
Define Y(L) be the intersection of (X, X+V) and L. Y)L) is in (X, X+V), and on L.

Repeat the above Y(L) for each line you could intercept L.

Let Y(L_0) be the closest Y(L) to X.

Define X = Y(L_0) and U(L_0) = X+V-Y(L_0).

Define W(L) = DIR(L) * U dot DIR(L) -- the slide effect.

Let V = W(L_0)

Now solve for X and V.

The main difference here is I collided with the earliest line. Your collided with the first line you noticed checked. By moving yourself unilatrally, you could very well have teleported past another line -- not a good thing.

As a completely alternative solution, you could simply find the earliest line -- but DO NOT MOVE THE OBJECT YET.

Calculate Y(L). Calculate W(L).

Now define V` = Y(L)+W(L) - X.

Keep the object at location X, and calculate where the collision with the line wants to move you. Change the Velocity, but not the Position of your object.

This shouldn't collide with your first line anymore (assert this).

Now test against the next line. Restrict your Velocity again.

Each step in the operation should NOT increase the absolute magnatude of your Velocity (assert this).

Repeated collisions should decay your Velocity, until your thingy doesn't want to move much.

##### Share on other sites
Quote:
 Original post by NotAYakkThe main difference here is I collided with the earliest line. Your collided with the first line you noticed checked. By moving yourself unilatrally, you could very well have teleported past another line -- not a good thing.

Actually, you can't assume that, since the snippet of code I posted didn't cover how I choose my collider. And I do choose the one that minimizes movement, through a process quite similar to the one you describe.

Now, as I vaguely indicated in my previous post, the "jump" comes from moving near-parallel to the colliding plane, because a collision register with a plane I'm supposed to slide on and my objects are pushed back along the direction of movement instead of being pushed back along the plane's normal, and when the direction of movement is near-parallel that means they'll be pushed back quite far.

Normally this is taken care of in the collision detection method, by ignoring the last collider, since I'm supposed to be travelling parallel to it, but when bouncing back and forth between colliders it's not enough.

So I added a check for dot(movement, collisionNormal) >Epsilon), which takes care of the bouncing but creates the inverse case where an object can be stuck between two others, so it'll still need some tweaking.

##### Share on other sites
Ah.

So you are nearly on the plane, and moving nearly parallel to it.

Because you are dealing with inprecice floating point numbers, you don't notice that you are 'already' colliding with the object.

So you get a nearly random point along your movement vector/plane as your "point of collision". If you aren't careful, the point on the plane you pick may not be along your vector

You then move there (generating yet more random jitter in your position and the calculations, and adding a random multiplier to your velocity vector), and do the dot product between a vector parallel to a surface and the surface (which returns the size of your vector).

You then find the ray along the surface you should collide with -- and get, randomly, a vector roughly parallel with your velocity vector, but possibly going in the wrong direction.

Ya, that would cause strange things to happen.

Advice: remove the check for "don't check the surface you just collided with". Then make your collision code stable when colliding with a single object. When you collide with something roughly parallel with you, you should just work.

Relying on that check is analagous to relying on a self-check when doing a copy constructor. It is a sign that your algorithm has a flaw.

##### Share on other sites
Dunno. that's one of the thing I lifted from Paul Nettle's code, and so far it's been working much better than tolerances. I only really want to remove that if it's actively preventing the algorithm from working correctly, and it's not. It's not not indicative of a flaw, but of a solution, and a simple, inexpensive one. The only flaw is that this solution happens to be incomplete, which is to be expected from an unfinished algorithm.

Apparently he's using a variant of the same trick to solve the problem of several simultaneous colliders which I'm rather tempted to recycle too.

Anyway, the point I get when colliding a surface I should be parallel to isn't as random as you seem to think: it's always somewhere along the velocity vector (simply because the collision method returns its results in terms of distance to travel, never as a new vector), and always moves the object backwards (because the object's embedded). Only the distance will be random (though it is constrained, because my colliders are convex polygons or polyhedrons, never just planes).

EDIT: hahaha, actually it works now, but the fix is ridiculous: instead of trying to find how far along the normal I should go back to not intersect a collider anymore, I just use a completely arbitrary and very small value. and it works perfectly! That's kinda ridiculous but good enough for me :)

[Edited by - chevluh on October 17, 2006 12:11:37 PM]

##### Share on other sites
So, is there any possibility that the intersection of your velocity with the plane could end up being behind the velocity, as it where? Beyond the end of the velocity?

##### Share on other sites
Quote:
 Original post by NotAYakkSo, is there any possibility that the intersection of your velocity with the plane could end up being behind the velocity, as it where? Beyond the end of the velocity?

well yeah, since it occurs when the moving object's embedded in its collider, and the new distance returned by the collision function's meant to put the object right on the collider's surface. If it wasn't in the other direction it would count as a normal move and my life would be simpler.

The fix still needs some tweaking because I'm pretty sure I must have introduced some fringe effects, I'll have to run through more tests before I'm certain it works.