Jump to content
  • Advertisement
Sign in to follow this  
chevluh

Simple collision response - collide and slide

This topic is 4387 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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
So, 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Gagyi
Shouldnt 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Bob Janova
The 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 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!