A question about penetration handling

[aokman]

Hi, guys:
I'm new to physics simulation, and there is a question disturbing me until now.
I know this question may be easy to you, but I'm new you see.
So, I come here to ask my question, and I wish to get a answer.

Actually, I would like to apply some physics to game. I had just read 'Physically Based Modeling' by Baraff.
In the article, Baraff eliminates penetration by calculating time of impact with some numerical methods.
But, when a pair of contact is resolved, it may cause other new contact occur within the same time step.
If these new contact is not resolved, then at the beginning of next time step, there will be already some
penetration existing, and if we resolve them now, will we get a negative time of impact? Because, the time
of impact occured in last time step. Is it right? Should I eliminate all contact pairs in this time step to
guarantee that no penetration would happen in the next time step? If the answer is I should, then I think
it may lead to a poor performance.

I wish someone could give me a answer to this question, or give some advice about how to handle penetration
using other better method, or show me more information about this topic.

Thanks in advance.
Li Jiacan.

[aokman]

Could anybody help me?

[raigan2]

I don't know specifically about Baraff's method, but in general you should be able to handle small amounts of penetration as they're pretty unavoidable.

[aokman]

Well,...
anything more?

[raigan2]

Look into Box2D or Bullet? http://gphysics.com/ has some useful materials.

[ngbinh]

Have you tried Kenny Erleben PhD thesis?

[aokman]

Have you tried Kenny Erleben PhD thesis?

Uh, you mean "Stable, Robust, and Versatile Multibody Animation"?
I found a version from internet, but it contains just 5 pages. And
I don't think it is a complete version for a PhD thesis. Would you please
post a link to the paper for me? Or would you please email it to me to
lilei9110@yahoo.com.cn?

Thanks.

[aokman]

Look into Box2D or Bullet? http://gphysics.com/ has some useful materials.

Well, I am new to this field. And I think I should know
some theory first, and then go into real source code.
But thanks for your advice and resource.
I will look into them in detail.

[Dirk Gregorius]

Physic Engines must be able to deal with penetrations. You cannot guarentee or assume no penetrations. To recover from penetration you basically feed some of the penetration into the solver. This means instead of solving such that the relative velocity at a contact point along the normal is zero, you push objects *slightly* apart. This method is called Baumgarte stabilization and it goes back to general constraint stabilization.

[ngbinh]

A little googling gives me this:
# Kenny Erleben.
Stable, Robust, and Versatile Multibody Dynamics Animation.
PhD thesis, Department of Computer Science, University of Copenhagen (DIKU), Universitetsparken 1, DK-2100 Copenhagen, Denmark, March 2005.
ftp://ftp.diku.dk/diku/image/publicatio ... 050401.pdf

[ngbinh]

Physic Engines must be able to deal with penetrations. You cannot guarentee or assume no penetrations. To recover from penetration you basically feed some of the penetration into the solver. This means instead of solving such that the relative velocity at a contact point along the normal is zero, you push objects *slightly* apart. This method is called Baumgarte stabilization and it goes back to general constraint stabilization.

That's not the case for ALL physics engines.

[Dirk Gregorius]

In my opinion you cannot assume no penetrations in a game. You might stop the solver after a fixed number of iterations, the user might spawn objects at penetrating positions or AI moves objects into each other. There are plenty of other secenarios that can lead to artifacts from where a solver needs to recover. This is why I stay with my statement: Physic engines must be able to recover from penetrations.

I am aware of the ST method and it is indeed very interesting. But to my knowledge it wasn't used in a shipped game so far and I would say that everything regarding ST is hypothetical until then. Still good work and please prove me wrong!



Cheers,
-Dirk

[ngbinh]

In my opinion you cannot assume no penetrations in a game. You might stop the solver after a fixed number of iterations, the user might spawn objects at penetrating positions or AI moves objects into each other. There are plenty of other secenarios that can lead to artifacts from where a solver needs to recover. This is why I stay with my statement: Physic engines must be able to recover from penetrations.

I am aware of the ST method and it is indeed very interesting. But to my knowledge it wasn't used in a shipped game so far and I would say that everything regarding ST is hypothetical until then. Still good work and please prove me wrong!



Cheers,
-Dirk

You are completely right at the point that penetration is pretty much unavoidable. There are three main causes of penetration during simulation:

1) Penetration by-design: inherent to wait-and-recover types of methods like ODE,Bullet,Box2D,etc..
2) Penetration due to linearization error: almost all current methods are linear so rotations always introduce errors.
3) Numerical error

All I wanted to say is your comment on how to recover penetration is not correct for all methods.
Also, while I notice that most games are using Box2D,Bullet-like methods, I think there are people (like me) who care more about using simulation in scientific researches than games. Even though, I do think that ST method should be useful to games. That's why I'm here trying to communicate.

[aokman]

I found Box2D library use 'Baumgarte stabilization' and Full NGS method to
complete position correction.

Is there any good paper about them available online?

Although having read Kenny Erleben's PhD thesis, I'd like to read more paper
to compare them together.

[Ratslayer]

The answer to this question actually depends on the time stepping your program uses. If you read through the Kenny Erleben's PhD, you'll see that he treats this subject with great depth. I, personally, like to have as little penetrations as possible, but not at the expense of having complicated Time-Stepping methods that would screw over my program's logic. A way to do this is to adopt a fixed time-stepping scheme, and manually correct the penetrations at each time step, before entering the constraint solving loop.

One way to do it: within the contact group, for each contact, move the objects apart from each other by a distance equal to the amount of penetration (weighted by velocity for each particular object). Since, if done sequentially, this produces more penetrations within other objects, you have to update the penetrations with other objects after moving the 2 bodies apart. So this thing does not loop, fix the resolved contacts between each other and move them together, instead of updating the penetration inside them. For believability of the simulation, make the fixed/scripted and 0 velocity objects move the whole contact group. Then run the constraint solver module.

The good thing about this, is that big penetrations are not a problem for the system, and the time stepping is kept simple. The bad is that in some situations, like an object being stuck between 2 scripted bodies (like a ball between 2 moving walls), this function can actually enter an infinite loop, as the scripted bodies will be moving the object forever. This can be solved by limiting the moving function to only affect moving objects and by assuming that this system won't always solve the penetrations and still applying the constraint stabilization to the collisions.

This is one way to do it but, as I said, penetration handling depends on the way the penetrations occur in your program, i.e. mainly your time-stepping method. You might want to get creative with that problem, since the math is pretty simple.