Applying collision impulses
Author
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
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.
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
Its badly thought out pseudo code, im currently cleaning up my code, and I'll repost it once i'm done
float timeLeft = deltaTimewhile timeLeft > 0 float moveTime = timeLeft //find collisions dynamicArray collisionList for i = 0 to objectsNum-1 for j = i+1 to objectNum float collisionTime = objects.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.move(moveTime) end for //collision response (calculate new velocities) dynamicArray newVelocities for i = 0 to collisionList.size() int colObjIndex1 = collisionList[0] newVelocities.add(colObjIndex1, newVelocityCalc1) int colObjIndex2 = collisionList[1] newVelocities.add(colObjIndex2, newVelocityCalc2) end for //update objects' velocities for i = 0 to collisionList.size() objects[newVelocities.index1].velocity+=newVelocities1 objects[newVelocities.index2].velocity+=newVelocities2 end for // timeLeft-=moveTime end while
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.
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.
Author
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!
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!
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.
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.
Author
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.
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.
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
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
heres my source for collisions between multiple spheres, it includes the movement code aswell.
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
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.position - objects[j].position; math::Vector v = objects.linearVelocity - objects[j].linearVelocity; double r = objects.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.position += objects.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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
