Sign in to follow this  
PrestoChung

When contact resolution fails

Recommended Posts

PrestoChung    334

What do people usually do when a contact resolution algorithm doesn't succeed in preventing overlap of collision manifolds?

 

I have n-object contact resolution working in 3D using velocity constraints, but since it's a linear approximation after enough time objects can slowly drift closer until they overlap, and the algorithm will do nothing for small negative velocities that are within the target tolerance.

 

Objects can also overlap after a contact resolve even when the local contact velocity constraint *is* satisfied (objects are separating at the given contact points): for example a box balanced on an edge or a corner tips over while remaining in contact, until it eventually falls flat. In that case I would want to break contact and perform a collision so that a 'bounce' will result when it lands.

 

What I've decided to do is a penetration resolve (solve for a position constraint: push the objects apart) *only* if the local contact velocity was negative after attempting to resolve the contact group. After applying a penetration resolve, I have been updating velocities to match the apparent motion resulting from the position update, which means that the contact group needs to be resolved again to make sure the velocity constraints are now satisfied, at least within tolerance, and no more overlaps remain. Whether or not this velocity update is a good idea or required I'm not sure if it's just causing extra work to be done.

 

Things get a little more complicated  when it's a new collision involving two contact groups: the trajectories of all the objects in the contact groups will be modified, so they will have to be re-entered into the collision pipeline to catch new collisions, but this is more of an implementation specific problem, I think.

 

Anyway, just wanted to see if these are valid approaches or if I'm solving an intractable problem.

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757

There are  two ways to handle this. The first one is to add a small velocity delta to resolve the penetration over several frames. This is usually added to the RHS of the velocity constraints and is called Baumgarte stabilization. The second approach is an orthogonal projection of the position constraints where you resolve all penetrations in an independent solver sweep . This is a non-linear problem and much harder and in particular more expensive to solve. It has the advantage that it doesn't affect the momentum state of the involved bodies and works much better for joints in practice.

You can find an example of the first in the ODE and an example of the second in Box2D. There is also small analysis in the comments which compares also a third method called "Split Impulses". It is kind of a hybrid of the two above which seems to work well with contacts, but not so much with joint. See "Position Correction Notes" here:

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Dynamics/b2Island.cpp

 

HTH,

-Dirk

Share this post


Link to post
Share on other sites
PrestoChung    334
On 9/15/2017 at 10:34 AM, Dirk Gregorius said:

The second approach is an orthogonal projection of the position constraints where you resolve all penetrations in an independent solver sweep .

What is this method called, is it related to one of the pseudo-velocity methods or NGS?

 

I don't have any joint constraints, so stability there is not a concern. So far we have gone to great lengths to prevent penetration , so I would probably not consider Baumgarte (solving the penetration over several frames).

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757

Both try to perform an orthogonal projection. When you project position constraints you iterate over the positions. Both the constraint function and the Jacobian are functions of the position. So if you change positions you need to recompute the constraint error and Jacobian. Pseudo velocities keep the constraint error and Jacobians constant while NGS properly recomputes constraint errors and Jacobians per constraint. 

If you want to prevent penetration you might be better off using continuous collision detection (CCD) and continuous physics (CP). The constraint projection is not really good for recovering from deep penetrations. In particular deep mesh collisions. If you target for penetration free simulation penetration recovery alone will not be good enough. I am working myself on VR currently and penetrations here are much more noticeable than on a 2d screen. I think the solution here is a combination of both. You want a continuous simulation to keep penetration shallow and position correction to patch up the rest. 

HTH,

-Dirk

 

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites
PrestoChung    334
14 hours ago, Dirk Gregorius said:

If you want to prevent penetration you might be better off using continuous collision detection (CCD) and continuous physics (CP).

I think what I have is considered CCD, the collision detection pipeline uses swept volumes in the broad phase with conservative advancement in the mid phase and bilateral advancement in the narrow phase, so it's good at detecting any collisions where rotational velocities are less than about PI radians per frame. Not sure what continuous physics is, but we handle the collisions in the order they occur (at exact fractional frame TOI) to prevent tunnelling. So ignoring high rotational velocities, penetration really only occurs in this case where contact resolution fails for some reason, and that's usually this gradual drifting where the negative velocity is a small value within the target tolerance.

I'm still not exactly clear on what orthogonal projection, pseudo velocities, NGS actually do, maybe because I don't have a general "constraint" framework to work with: right now the only constraint is the velocity constraint imposed by contact resolution, which I think is the "Projected-Gauss-Siedel" (PGS ) method where final impulses are arrived at iteratively that satisfy the "Signori Conditions".

It kind of sounds like  the algorithm for solving a set of non-penetration (position) constraints would be a similar process, applying penetration resolves in sequence over all contacts until the system converges to one where there are no more penetrations? One thing I do have at my disposal is the exact penetration depth and vector as calculated by GJK. With this information a simple linear offset can be applied that will solve a single penetration more or less exactly (accounting for relative masses of the objects), if one doesn't rotate the objects at all-- although a more "correct" solution would rotate the objects as well, so maybe this is where things get more complicated.

Share this post


Link to post
Share on other sites
coderchris    304

As an absolute last resort, you could look into using "rigid impact zones". It was originally devised for cloth simulation, but in my experience it works surprisingly well for complex rigid body collision scenarios. It will not resolve overlap that existed at the beginning of the time step, but it can guarantee that no new overlap will exist by the end of the step.

The basic idea is to take a group of colliding bodies for which normal collision resolution failed to find a solution for, and treat that group as a single rigid body. This is done by computing, for that group, an average linear and angular velocity, then applying that to all objects in the group. This should all be done as the very last step in your solver. 

The method is detailed here (section 7.5):

http://physbam.stanford.edu/~fedkiw/papers/stanford2002-01.pdf

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