# Rigid Body Collision Resolution Problem [Solved]

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

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633385
• Total Posts
3011605
• ### Who's Online (See full list)

There are no registered users currently online

×