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.

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

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).

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

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.

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

I think I understand why they are called "pseudo-velocities" now: they don't modify the velocities of the object, but get used for the post-integration after the contact has been resolved. I'm still not sure exactly how it's supposed to work. Is it as simple as projecting the penetration vector against the contact normals, and then re-running the PGS solver with new target normal velocities that are adjusted by this extra amount? It doesn't sound that much different from steering velocity or Baumgarte, except that this extra velocity doesn't accumulate in the object momentum since it is "thrown away" at the end of the frame.

It's not really a "physically based" phenomena. But the gist is to take the gradient from the constraint equation and use that as an orthogonal projection in terms of position. It's not physically based since this sort of post-project actually moves position, effectively doing work since the moment the position is moved the gradient changes.

Whereas constraints apply velocities that fall under the principle of virtual work at an instant of time.

In laymen's terms: take the direction velocity would be applied and do a position update instead!

Not sure what the "gradient" is supposed to be here?

Here is how I currently solve for normal velocity constraints:

The difference between the current velocity and the target velocity (zero for resting contacts) in the direction of the contact normal is computed and then multiplied by a scalar (basically the "kn" value on slide 21 here [Catto GDC06](http://ppt-online.org/187866): it involves the skew symmetric of the contact point vectors, the inverse intertia tensors, inverse masses, and the contact normal itself), giving the magnitude of the impulse to be applied

After this successive impulses converge on a solution, position is integrated with the new velocities to give the resulting poses at t==1.0. Now if there is a penetration here, I will have a penetration vector indicating the depth and direction of the penetration.

So do we then go *back* to the time of contact, and based on the penetration depth and direction, apply pseudo-velocity impulses to reach some target pseudo-velocity along the *penetration vector direction*? So the `kn` scalar above would be the same except that it should be computed with the (normalized) penetration vector `p` as the input "direction", giving some other scalar, say `kp`. Then the solver iterations are essentially the same, except each contact point has its current velocity computed along the *penetration vector direction* instead of the contact normal direction, until the target velocity along the penetration vector direction is reached.

Once the pseudo-velocity targets converge, integrate to t==1.0 using velocity + pseudo-velocity and check the poses again for penetration, running another penetration solve, with a new penetration vector, if needed.

It sounds like this would eventually solve all penetrations, the only thing that seems a little odd is that each contact point would have the same target pseudo-velocity, since the depths of individual contact points weren't computed. Maybe the right way is to look at the resulting distance vector between the contact points on the surfaces of each object, and project that against the penetration vector? So each contact point would have its own target pseudo-velocity, which would be zero for points that have a positive dot product with the penetration vector.