Sign in to follow this  
Berion

Applying collision impulses

Recommended Posts

Berion    122
Hello! I am writing my first physics engine with only spheres at the moment. I use NSV and swept sphere - sphere collision test. No broad phase at the moment. I also know how to calculate impulses, but I don't know how to apply them. The correct but slooow way: Calculate all collisions and sort by time. Loop through all collisions and calculate impulses, update velocity and position and check for new collisions and insert them. Are there better ways, which produce good results? I know allowing penetrations is much faster, but how do you avoid tunneling? Are there other/better options? Alexander Meisel

Share this post


Link to post
Share on other sites
Dmytry    1151
Are you sure that "slow way" is really that slow? I imagine the most of your slowness probably anyway comes from doing O(n^2) collision checks, assuming you don't use space partitioning.

Share this post


Link to post
Share on other sites
johnnyBravo    100
im doing the same thing, this is what im doing (only with linear movement so far):

Its badly thought out pseudo code, im currently cleaning up my code, and I'll repost it once i'm done

float timeLeft = deltaTime

while timeLeft > 0
float moveTime = timeLeft

//find collisions
dynamicArray collisionList

for i = 0 to objectsNum-1
for j = i+1 to objectNum
float collisionTime = objects[i].getCollisionTime(objects[j])

if(collisionTime >= 0 AND collisionTime <= moveTime)
if(moveTime > collisionTime)
collisionList.clear()
end if

collisionList.add(i,j)
moveTime = collisionTime
end if
end for
end for

//move objects forward
for i = 0 to objectNum
objects[i].move(moveTime)
end for

//collision response (calculate new velocities)
dynamicArray newVelocities

for i = 0 to collisionList.size()
int colObjIndex1 = collisionList[i][0]
newVelocities.add(colObjIndex1, newVelocityCalc1)
int colObjIndex2 = collisionList[i][1]
newVelocities.add(colObjIndex2, newVelocityCalc2)
end for

//update objects' velocities
for i = 0 to collisionList.size()
objects[newVelocities[i].index1].velocity+=newVelocities[i]1
objects[newVelocities[i].index2].velocity+=newVelocities[i]2
end for

//
timeLeft-=moveTime

end while


Share this post


Link to post
Share on other sites
Milkshake    374
Hi,

I started off writing my physics solver trying to consider velocity in the collision code, and while I had it working beautifully for spheres, as soon as you start trying to handle boxes and capsules as well, the collision code you need it truly horrifying (the static box to box test requires testing 15 separate axes ... I can't even imagine what this looks like with velocities and/or swept volumes included).

So unless you really want some stylised game-specific physics solution - I found trying to do realistic physics is just a huge pain this way.

My current solver uses the standard "allow penetration then try and correct it" approach, and so far, it's pretty good. Just this week I tackled the problem of tunneling (to handle high speed things like bullets), and so far that's holding up pretty well too.

If you look at the last entry in my journal, there's a bit of a discussion of how I did it, and even a video of it in action handling loads of fast moving spherical "bullets". Let me know if you have any questions I might be able to help with.

Share this post


Link to post
Share on other sites
Berion    122
So you make a ray test for objects with high velocitys and a static collisions test for the rest? Good idea! I think I will test it.

So first update velocity.
Then make the ray test for fast objects.
Then the static collision test for the rest.
Then update position.

Some questions about the the ray test:

Do you test against static and slow objects or also other fast moving?
If the ray test finds a collision you move the object to that position an make a static collisions test? What if there is no collision? Another ray test?

Thanks for the help!

Share this post


Link to post
Share on other sites
Milkshake    374
Almost.

Firstly, many simulation engines do this in a slightly different order:
1) Determine the current intersections in the scene
2) Calculate the response forces necessary to respect the system constraints (e.g. collisions/contacts etc)
3) Apply the forces, then apply the resulting velocity

Given the above system is quite complicated and I wanted to avoid putting high-speed objects in a separate code path (because you'd find more and more things which didn't work the same or at all with fast objects), my current solution is to insert a new step 0, which uses a ray cast to look ahead of the object's current trajectory, and if it finds anything, it adjusts the time/position of this object so that the collision that happens mid-way along the current update frame is moved to the start (where the normal static collision detection used in step 1 will see it).

It's not 100% accurate - but for my purposes it's (so far) virtually indistinguishable to the naked eye and is both simple and fast.

The ray cast is currently done at the scene level and does not take velocity into account. So it tests everything, but two fast moving objects which cross over inside a single frame might get missed if they're not colliding head on ... but given this cross-over has to happen in a single frame where the player never sees a precise rendering of the cross-over, I doubt it will ever look obviously wrong, more like a near miss.

If there is no ray cast collision, I just let the standard physics update test as normal, and as long as it's still moving fast, it will get another ray cast on the next physics update. Did I mention the ray cast only searches for intersections as far as the object is moving in the current update? You don't want to try and consider the whole path because a) gravity will make it non-linear, and b) other objects might move over the course of the motion.

It's worth noting that my ray cast collision does support a "volume" parameter - so I can effectively test the swept bounding volume for intersections, not just a single ray. This is less important for small bullets - but very important if you have larger fast moving objects.



Share this post


Link to post
Share on other sites
Berion    122
Thanks again!

I have rewritten my system:

It is 2d and only has spheres/circles at the moment.

1.) Test for collisions.
2.) Apply impulses.
3.) Update velocity and position.

1.) and 3.) are completely clear and work perfect.

But I have problems with 2.):

I first tried to use "Fast and Simple Physics using Sequential Impulses" from Erin Catto GDC 2006, but it didn't worked. I only changed from boxes to spheres and suddenly all collisions where inelastic. I tried to change it, but it didn't work.

Now I just apply one impulse:

float j = -((1.0f + (mA.mCOR + mB.mCOR) / 2.0f) * fVelocity.dot(mNormal)) / (mA.mInverseMass + mB.mInverseMass);
velocity += j * N;

For collisions with only 2 objects it works perfectly, but more objects or stacking are a problem.

Are there any good tutorials or papers out there?

I have found "Nonconvex Rigid Bodies with Stacking" but had not enough time to read and test it.

Share this post


Link to post
Share on other sites
Milkshake    374
So the one term I can't see in your equation is the penetration depth.

Your collision response has two components:

1) you need to apply some combination of convervation of momentum and conversation of energy to work out which direction and velocities the two bodies should exit the collision with. This seems to be what your current response approximates today - but you'll probably need a more complicated model if you want to support elastic vs inelastic collisions (i.e. things bouncing off each other vs things sticking to each other). The fact that you're not getting bouncy collisions suggests you're not including convervation of kinetic energy ( Ke = 0.5 m v^2). From memory, the sum of the kinetic energies of the bodies before and after the collision must be identical for a perfectly elastic collision (where no energy is absorbed deforming the bodies).

2) you need to include a second term to fully or partially correct for the interpenetration. Collision routines typically return several pieces of information: the point of contact, the normal of contact, and the depth of contact. The first two terms are used in step 1, the last two get used here.

Apologies if this stuff is already been taken into account in the equation - but in my sleepy state (I just stayed up all night to get a Wii) I'm not seeing it.

If you're really wanting to develop your solver into a fully featured system - you might want to start looking at the source code for ODE. It's not for the faint of heart though.

Cheers,
G

Share this post


Link to post
Share on other sites
johnnyBravo    100
heres my source for collisions between multiple spheres, it includes the movement code aswell.


double timeLeft = deltaTime;

while(timeLeft > 0) {
double moveTime = timeLeft;
std::vector<int> collisions;

//find earliest collision(s), and time
for(int i=0;i<(int)objects.size()-1;i++) {
for(int j=i+1;j<(int)objects.size();j++) {
math::Vector p = objects[i].position - objects[j].position;
math::Vector v = objects[i].linearVelocity - objects[j].linearVelocity;

double r = objects[i].base->radius + objects[j].base->radius;
double a = v.x*v.x + v.y*v.y + v.z*v.z;
double b = 2*(p.x*v.x + p.y*v.y + p.z*v.z);
double c = p.x*p.x + p.y*p.y + p.z*p.z - r*r;
double determinant = b*b - 4*a*c;

if(determinant >= 0) {
double collisionTime = (-b - sqrt(determinant))/(2*a);

if(collisionTime >= 0 && collisionTime <= moveTime) {
if(collisionTime < moveTime) {
moveTime = collisionTime;
collisions.clear();
}

collisions.push_back(i);
collisions.push_back(j);
}
}
}
}

//move objects forward by move time
for(int i=0;i<int(objects.size());i++) {
objects[i].position += objects[i].linearVelocity*moveTime;
}

//response
std::vector<math::Vector> linearVelocities;

for(int i=0;i<(int)collisions.size()/2;i++) {
int i1 = collisions[i*2];
int i2 = collisions[i*2+1];

math::Vector normal = (objects[i1].position - objects[i2].position).normal();

double m1 = objects[i1].base->mass;
double m2 = objects[i2].base->mass;
double e = 1;

math::Vector V1 = normal * objects[i1].linearVelocity.dot(normal);
math::Vector V2 = normal * objects[i2].linearVelocity.dot(normal);

math::Vector V1f = (V2*((e + 1.0) * m2) + V1 * (m1 - e * m2))/(m1 + m2);
math::Vector V2f = (V1*((e + 1.0) * m1) + V2 * (m2 - e * m1))/(m1 + m2);

linearVelocities.push_back(V1f - V1);
linearVelocities.push_back(V2f - V2);
}

for(int i=0;i<(int)collisions.size()/2;i++) {
objects[collisions[i*2]].linearVelocity += linearVelocities[i*2];
objects[collisions[i*2+1]].linearVelocity += linearVelocities[i*2+1];
}

timeLeft -= moveTime;
}




its basically goes like this

find earliest collisions and time
move all objects forward by this time or deltaTime(if no collision)
calculate collision responses
apply collision responses

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this