Sign in to follow this  
personalnadir

Rigid Body Collision Resolution Problem [Solved]

Recommended Posts

personalnadir    122
I've spent a while working on a rigid body physics sim, based variously on Chris Hecker's articles and Gaffer's. The simulation is 2 dimensional and allows the player to chuck cubes around and have them bounce off other objects. My problem only turned up a couple of days ago, once I'd thought everything was done and dusted. I noticed that in the collision resolution code I was calculating the impulse (as in Hecker's third article) and rather than adding it to momentum, I was setting momentum to be the impulse. As strange as this sounds, it actually worked fine. There were some wierd side effects: for instance box A is travelling left to right at some speed and B, travelling in the same direction, but going faster, hits the back of A. The result in this simulation was that A would be slowed by the collision, as if some one had put some gum at the collision point. It being only two lines of code I corrected the problem and ran the simulation. Lo and behold! What had worked fine with incorrect physics, broke down in a smouldering heap with the correction. This left me puzzled. Now I appriciate that the above is vague as to the nature of the problem. The simulation breaks down when objects collide (particularily if this involves a stack of objects being formed). It doesn't always break down, and infact will usually run serveral collisions until some magical senario is reached which it can't handle. As said this usually occurs when several objects are touching. As for implementation details, you who have made it this far will be blessed with them: I use an AABBTree to return all objects whose node overlaps with the objects of interest. The tree is built using the updated coordinates for the objects. The simulation covers angular and linear velocities. I'm using a RK4 integrator. If two objects are penetrating I revert their state to the last frame, subdivide the time step and update them until they complete their time step. Non colliding objects are updated with the original time step. Err.. What else? It seems wierd to me that something would break down just because I fix it... It's spiteful. [Edited by - personalnadir on October 11, 2005 11:59:21 AM]

Share this post


Link to post
Share on other sites
personalnadir    122
Hmm, I'm actually wrong (happens more than I like). The simulation doesn't grind to a halt, it just grinds. It drops from a happy 100 fps down to about 1fpy and only as I mentioned for some collisions.

I've double and tripple checked my impulse forces (peeking at source where available), so I'm about as confident that they're correct as I can be. What I'm not too confident about is the order in which I update and revert object.

I basically use a system along the lines of:

Put everything in vector toDo
Update all objects in toDo by dt
Revert and store any interpenetrating objects in vector collided
Remove all objects from toDo which are in collided
Save the state on all objects left in toDo
Remove all objects in toDo which have completed their time step
If toDo is empty shift the contents of collided into toDo
dt *= 0.5
update all objects in toDo etc.

What I'm not happy about is that I'm saving the state on objects in toDo before all objects have completed their time step, yet if I don't do this the simulation breaks down. Any suggestions?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
It sounds like the problem may be that in the case of collisions, you are going back in time to find the time of the collision, repeatedly. So you might be going into very fine timesteps, which will make the update for a single timestep take a long time, since it gets subdivided into very fine timesteps.

Share this post


Link to post
Share on other sites
personalnadir    122
I was reading earlier (it was a link in this forum's FAQ) about collisions between spheres. The article described a way of working out the distance a sphere could travel along a vector before it collides with another sphere (assuming there will be a collision).

I was curious as to whether I could use this in my simulation, and so work out the time of collision and not need to subdivide the time step. The only problem is that spinning polygons are a bit more complex than two spheres. Is there a solution to this or any viable alternatives?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
For spinning polygons, finding the time of the collision is very difficult. Even if you could find the times, you'd still have cases where two objects can collide with each other several times during a single timestep. For an interactive simulation, you just have to forget about simulating the objects perfectly and use some tricks to just get it to where it looks right. This can involve dealing with penetrating objects by just moving them apart so they don't penetrate, or allowing objects to penetrate each other and applying a small force to try to gradually push them apart.

Share this post


Link to post
Share on other sites
personalnadir    122
hmm, would this force then be seperate to the impulse? So if I get this right (which according to recent performance is unlikely), rather than reverting to a previous safe state and subdividing the time step, interpentrating objects are pushed apart by a force, until impulse propels them away as should be...

Or do I just apply impulse once I've found them to be interpentrating?

Share this post


Link to post
Share on other sites
oliii    2196
This is called penalty forces. Your objects are in an invalid configuration (they intersect), you try to compensate the intersection with a force. Problem are, it's not accurate, in particularly in case of stacking.

as an example,

denom = -(1+Cor)[Vel.norm + (depth * depth_penalty_amount)]
numer = [1/Ma + 1/Mb] + [Ia' * (ra x norm)²] + [Ib' * (rb x norm)²]
impulse = denom / numer;

as simple as that. All you have to do in case of an intersection is to be able to calculate the amount of intersection.

but this as many shortcomings.

Share this post


Link to post
Share on other sites
personalnadir    122
Oh yeah, I've read a few papers, and generally they didn't recommend it. I'd rather figure out how to fix this subdivision technique I'm currently using than try a brand new approach with 99% of the code complete. I have noticed that more impulse reduces the chances of the program grinding to a halt, but that's presumably because objects are being fired away from each other.

I tried doubling the impulse, and while it was amusing, eventually the crash came, but far far later into the program.

Maybe I'm having problems with objects hitting each other several times in the time step, I can see how that would take an age to sort out using subdivision. I've played around with it a bit (as much as one cares to play around with a program that constantly needs killing), but I can't yet really see any particular scenario which triggers the problem. Most collisions it solves normally, with little bother, but there's always one which pulls the rug from under it.

Share this post


Link to post
Share on other sites
oliii    2196
when objects becomes in resting or sliding contacts, you'll do lots of back and forth tests t find an infinitesimal time of collision, and the program will stop, or even fail to find a solution due to numerical innacuracies.

So you'll have to solve it differently for contacts than for collisions, if you want to use a non-penalty method.

Look for David Baraff's papers if you haven't yet, Dave Eberly also has some stuff (and book about game physics), and these bunch of docs

http://graphics.stanford.edu/papers/rigid_bodies-sig03/
http://www.cg.tuwien.ac.at/studentwork/CESCG/CESCG-2000/PSovis/
http://citeseer.ist.psu.edu/mirtich95impulsebased.html
http://www.cs.unc.edu/~ehmann/RigidTutorial/
http://www.cs.unc.edu/~dm/UNC/PHYSICS/Papers/baraff94.ps.gz
http://www.cs.unc.edu/~dm/UNC/PHYSICS/Papers/baraff93.ps.gz
http://graphics.stanford.edu/courses/cs468-03-winter/Papers/hybridImpulse.pdf
http://citeseer.ist.psu.edu/redon02fast.html

as you can see, not an easy problem. :)

Share this post


Link to post
Share on other sites
personalnadir    122
Arrgh! I've certainly come across micro collisions before, but I think the maths was a bit too complicated for me (I need nice friendly introductions). I'll try to make some head or tail of it on monday.

Share this post


Link to post
Share on other sites
personalnadir    122
I can't see how I can translate the information in the Mirtich paper into something I can use. As I'm only using a 2D simulation, and my maths or understanding of entirely what is mentioned, is good enough to translate the 3D down one dimension (and also because it would require a lot of recoding) I'll give Baraff's work a go.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
The penalty force method can be a good approach. It is elegant, and easy to implement (apart from that pesky finding the penetration depth thing). And it can run faster than the impulse-momentum approach, in the case that you intend to totally, 100% disallow interpenetration.

The difficulty is that you must essentially use implicit integration to make it stable in general. And implicit integration is the wrench in the works---not always easy to implement.

Share this post


Link to post
Share on other sites
personalnadir    122
I have to admit, that despite all the helpful posts, I'm not entirely sure what the root of my woes are. Today, because I've been too tired to grasp the the complexities of the papers suggested, I tried to limit the number of subdivisions that are being made.

Objects which have collided are now added to a list in pairs with the size of the unsucceful time step. Once the time step gets too small, there's a kind of "shut up" function, which pretends that the objects are as close as I'd like and applies impulse to drive them appart. This has had not effect. I had thought it would lead to some inaccruacies, but that the program would run. Instead nothing has changed. When the program grinds to a halt, it's not that it doesn't try to seperate objects by applying impulse, it just fails to do so.

The problem even arises when just two blocks collide, which shouldn't be a problem for subdivision, particualarily given that I am asking for a very low accruacy (objects are 2 units across and only need to be with in 0.3 units of each other and closing to be dealt with). That said the limit is definately reached. So, most times it works, but often it doesn't. Curse my impotent impulses :P

Share this post


Link to post
Share on other sites
personalnadir    122
Hahaha ha... ha... *sob*

I finally found the problem! After months of looking for it, I came across it by pure accident! It was the collision normal. The code that found it looked at each object in the collision, finding the contact point and the edge (for the normal) involved. Some time ago, in a bout of optimisation, I replaced several calls to the vector magnitude function with a magnitude squared function.

I missed one.

ARRRGH!!

Two months after the change, a bug fix (the impulse) causes the code to have an impact (excuse the pun) and it's taken several weeks to track it down. Once again thanks to every one for the help. I'm going to cry :'(

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