A question about penetration handling

[aokman]

Er...Thanks for all kind people above.
I have considered the question for a long time, but I am
still confused. Maybe I didn't describe my question clearly.
So, here I'd like to describe my question again.

I have understood the basics of constraint based dynamic
simulation. During the simulation, when bodies happens to
contact each other, it can be formed as a LCP problem,
and then after the LCP was solved, contact force between
each pair of contact bodies can be obtained. So next, we
can use Newton-Euler motion equation to determine motion
of these bodies.

Most papers describe almost same thing as I mentioned above.
But these papers seems that they just consider the problem
at the instant when bodies are just coming into contact.
And there isn't any penetration having occurred.

However, in real-world dynamic simulation, collision detection
should be used to find whether bodies are in contact.
Considered the manner that collision detection works, it can
usually determine two bodies are in contact when the two
bodies overlay, which means penetration already occur.

So, if we just geometrically correct position of bodies to
avoid/reduce penetration then I think this may introduce
inaccuracy into physical motion.

In practice, should I compute collision impulse directly after
collision detection found penetration between bodies and then
correct position? Or should I correct position of bodies first,
and then adjust motion state of bodies at new position as
collision hasn't occurred, and finally compute the motion state
after collision using computed impulse?

Thanks.

[Dirk Gregorius]

The first thing you need to do is to distinguish between discrete and contiuous physics. For discrete physics where you step the simulation with a (hopefully) fixed timestep you will indeed see penetrations. But also for contiuous physics it is not unlikely that penetrations occure. So either way you must be able to handle them.

The problem can be solved in many ways and each of you mentioned methods might work. The most common ways are Baumgarte stabilization and post-projection (or split-impulses). Of course you could use a different integrator and project position first and the project velocities. E.g. Jan Bender's stepper takes such an approach.


Cheers,
-Dirk

[ngbinh]

Er...Thanks for all kind people above.
I have considered the question for a long time, but I am
still confused. Maybe I didn't describe my question clearly.
So, here I'd like to describe my question again.

I have understood the basics of constraint based dynamic
simulation. During the simulation, when bodies happens to
contact each other, it can be formed as a LCP problem,
and then after the LCP was solved, contact force between
each pair of contact bodies can be obtained. So next, we
can use Newton-Euler motion equation to determine motion
of these bodies.

Most papers describe almost same thing as I mentioned above.
But these papers seems that they just consider the problem
at the instant when bodies are just coming into contact.
And there isn't any penetration having occurred.

However, in real-world dynamic simulation, collision detection
should be used to find whether bodies are in contact.
Considered the manner that collision detection works, it can
usually determine two bodies are in contact when the two
bodies overlay, which means penetration already occur.

So, if we just geometrically correct position of bodies to
avoid/reduce penetration then I think this may introduce
inaccuracy into physical motion.

In practice, should I compute collision impulse directly after
collision detection found penetration between bodies and then
correct position? Or should I correct position of bodies first,
and then adjust motion state of bodies at new position as
collision hasn't occurred, and finally compute the motion state
after collision using computed impulse?

Thanks.

That's a very simple but interesting question. I had the same years ago before I went into grad school.

I can say there are three main types of methods to deal with rigid body contact:

1) Event detection + traditional mechanics. You will need to somehow find the exact time of impact, stop the simulation, add that contact into the system, then proceed. The good thing about this method is that during a time step, the states of your system is the same so you can use many classical mechanics methods to find solutions. You also dont have to linearized your system, which means you can use fully Coulomb friction (quadratic) or nonlinear restitution rules if you wish. The problem is that it's almost impossible to find the exact time of impact. Historically, people ' ve been trying to reduce time step until no penetration occur. This method is suitable for system that have very few contact changes. For the scene with alot of contacts, the method may suffer from very small time step (to capture time of impact) and also exponential switches. Most current mechanical simulation still using this type of method (SimMechanics, Adams, etc..)

2) Penetration correction : This method rooted from Mihai Anitescu and Florian Potra paper in 1997. The main idea is to detect if there are any penetrations, if yes, form complementarity problems on the velocity projection along the normals to stop deeper penetrations. Then correct them in some ways ( projections, Baumgarte ). This is the method used by most current game physics engine.

3) Penetration prevention: rooted from Stewart,Trinkle paper in 1996. The main idea of this method is that it actively looking for potential penetrating contacts and add those to the complementarity problems (slightly different from the on in 2). Then those contacts will be handled correctly. There will still be penetrations but only due to linearization or numerical errors. Normally, this type of method result in much less penetrations than 2, but it requires more contacts to be added to the LCP, so it could be slower than 2 with the same scenario.

For 2 and 3, once penetrations occur, you can either project them out (Jakobsen) or add a correction term proportions to the penetration depth (Baumgarte).

Hope that answer your question.

[fishboy82]

Both Dirk and ngbinh gives an excellent expression about how to deal with penetration.
But I think some of their method is a little sophisticate.
So I think if you are a beginner you just try one method that is very simple that is "feed back the penetration error to relative speed and let the speed to correct the penetration". That is what Dirk mentioned as "Bamugrate" Method. It's very very easy to implement and the effect is also acceptable ,of course it will cause some problem like "over shoot",so more sophisticated method is post-projection or splitt-impluse.
The "Bamugrate" method is very simple for example suppose you have a penetration error along the normal say "e",so the nextime you want your 2 objects to aparat from the penetration so the relative velocity of these 2 objects should be e*Normal / timestep, So When you write you LCP you just feed the right hand side this value then the relative speed will apart the penetration
Hopes that help

[aokman]

Thanks for all your reply, I think they give me plenty of hints to solve penetration.
I'll pay some time to dig into them.

[aokman]

In my opinion you cannot assume no penetrations in a game.

and

You are completely right at the point that penetration is pretty much unavoidable.

I'd like to confirm what you exactly mean. Do you mean that penetration is unavoidable because of finite precision of float number data type? i.e. if float number date type has infinite precision, there can be no penetration, right?

Recently, I read Brain Mirtch's PhD thesis 'Impulse-based Dynamic Simulation of Rigid Body'. I think it uses a contiuous physics, because it guarantees no collision would be missed. It seems that penetration can be avoided before it occurs.

Did anybody attempt to use this method in games?

[ngbinh]

In my opinion you cannot assume no penetrations in a game.

and

You are completely right at the point that penetration is pretty much unavoidable.

I'd like to confirm what you exactly mean. Do you mean that penetration is unavoidable because of finite precision of float number data type? i.e. if float number date type has infinite precision, there can be no penetration, right?

Recently, I read Brain Mirtch's PhD thesis 'Impulse-based Dynamic Simulation of Rigid Body'. I think it uses a contiuous physics, because it guarantees no collision would be missed. It seems that penetration can be avoided before it occurs.

Did anybody attempt to use this method in games?

No matter what kind of collision detection you use, if you formulate the probblem as LINEAR complementarity problems then rotation can always cause penetration. Besides, there are numerical errors. Look at the pictures: you can see that the normal of the box changes due to rotation, so if we use normal information at current time, we will always be off a bit.



Get a right continuous collision detection is hard if not say impossible. Because it requires information about the next time step which only available if you already solved it. And of course if you already solved it, you dont need collision detection anymore.

[aokman]

Brain Mirtch's PhD thesis didn't use LCP. He just uses impulse to solve everything.

[ngbinh]

Brain Mirtch's PhD thesis didn't use LCP. He just uses impulse to solve everything.

It's still the same thing. Beside suffering from resting contact, his method also use the same contact model : try to keep distance between two bodies along a normal positive. And that normal has to be determined in current time step, thus, it still off when there is rotation.

[aokman]

Brain Mirtch's PhD thesis didn't use LCP. He just uses impulse to solve everything.

It's still the same thing. Beside suffering from resting contact, his method also use the same contact model : try to keep distance between two bodies along a normal positive. And that normal has to be determined in current time step, thus, it still off when there is rotation.

But, Brain Mirtch's PhD thesis uses Lin-Canny algorithm to trace closest feature between two polyhedron using Voronoi regions. It doesn't depend on the normal between two polyhedron. So, I think by combining Lin-Canny algorithm and Newton's method, TOI between two polyhedron during a time interval can be calculated within a tolerance(precision). And then, integration of position of the two polyhedron to the TOI will not lead to any penetration(except for some numerical error).

[ngbinh]

Brain Mirtch's PhD thesis didn't use LCP. He just uses impulse to solve everything.

It's still the same thing. Beside suffering from resting contact, his method also use the same contact model : try to keep distance between two bodies along a normal positive. And that normal has to be determined in current time step, thus, it still off when there is rotation.

But, Brain Mirtch's PhD thesis uses Lin-Canny algorithm to trace closest feature between two polyhedron using Voronoi regions. It doesn't depend on the normal between two polyhedron. So, I think by combining Lin-Canny algorithm and Newton's method, TOI between two polyhedron during a time interval can be calculated within a tolerance(precision). And then, integration of position of the two polyhedron to the TOI will not lead to any penetration(except for some numerical error).

Once it find the closet features between two convex polygon, it will then still depend on a normal to prevent non-penetration. It's the problem with linearization of the contact surface, all linear models have this problem no matter what.

The TOI, conservative advancement was not in his thesis. It's exactly what we call continuous collision detection now. But there are alot of problem with it:

1. simulation depends on the number of event (collisions) happen during the time step. So for the case of big box stack is nightmare for the method. It basically, chop the time step into many segments. I usually have to allow some sort of tolerance (error) in order to advance, so in the end, penetration still happen.

2. As I mention before, continuous collision requires the information (states of bodies in the next time step) that only available if you actually solve the time-stepping problem. Position integratiion + TOI may work for 2 bodies, but as the number of bodies in the island increases it would become much harder.

[aokman]

Yes, combing Lin-Canny algorithm and Newton's method is my perspective, not Brain Mirtch's. I still believe that it works for the case where no resting contacts exist. Because only pairs of bodies no the top of the collision heap will be solved and integrated, this will not lead to penetration, after that all the TOI of pairs that are near enough will be recomputed and the heap is sorted on TOI, then repeat this process. I think no penetration will occur in this way. Maybe I am wrong, and maybe I should try it out, and prove it's right.

Right now, I just assume that there are only colliding contacts, and no resting contact. Brain Mirtch mentioned in his paper that it's hard to cope with resting contact. I will finish the rest chapter eg. 'Hybrid Simulation' and find a method to solve resting contact.

I think Brain Mirtch's method is a promising method for games.