Any smart ideas on contact resolution priorities?

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Any smart ideas on contact resolution priorities?

Post by sphet »

Hi there. Currently in our engine we have three classes of bodies: static bodies, dynamic bodies, and keyframed bodies. One of my team members came to me and asked if there was any way to prioritize responses to collisions between these bodies. For example, if a keyframed gate animates onto a dynamic player, he will push through the static floor, but perhaps the floor should never be allowed to be penetrated, or at least not penetrated 'as much'.

To me this sounds odd - if the objects are penetrating, between a rock and a hard place, the dynamic player has no where to go. I also can't think how I would factor this kind of thing into the relatively simple gauss seidel solver we use. However, I thought I would ask if anyone has any smart ideas (beyond disabling the contact once collision occurs).

S
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: Any smart ideas on contact resolution priorities?

Post by RandyGaul »

Maybe you could try sorting the pairs the broadphase gives you in order to solve what is most important last. With Gauss Seidel the last constraints solved will be the most accurate, and perhaps for you the last contacts solved should be dynamic vs static.

Alternatively, maybe it would be good to see if the player is in the way of an animation and static body before playing the animation. If so, then do something about it (perhaps move the player), or not play the animation at all. I have seen doors in games attempt to shut, and once they come into contact with the player they just open back up without finishing their animation. This reminds me of elevator doors in real life.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Any smart ideas on contact resolution priorities?

Post by Dirk Gregorius »

Randy is right. You should sort your contacts such that static contacts are always solved last. This way you reduce chances that stuff gets pushed out of the world.

For doors I would use motors instead of kinematic bodies. You compute a motor force that will follow the animation. A kinematic body has essentially an infinite force which you want to avoid. This is helpful for all kind of stuff like e.g. also elevators. The down side is that you can now block doors and elevators with e.g. crates that get pushed around. Other solutions as e.g. shadow controllers are very complicated and I would try to avoid those.
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Any smart ideas on contact resolution priorities?

Post by sphet »

RandyGaul wrote:Maybe you could try sorting the pairs the broadphase gives you in order to solve what is most important last. With Gauss Seidel the last constraints solved will be the most accurate, and perhaps for you the last contacts solved should be dynamic vs static.

Alternatively, maybe it would be good to see if the player is in the way of an animation and static body before playing the animation. If so, then do something about it (perhaps move the player), or not play the animation at all. I have seen doors in games attempt to shut, and once they come into contact with the player they just open back up without finishing their animation. This reminds me of elevator doors in real life.
Randy,

It didn't really occur to me that the order that the constraints are solved would matter but when I stop and think about I see that they do. I'll give that a try - now I just need a free way to sort the constraints!

Dirk,

Motor forces occurred to me as well but the designer pointed out the specific 'problem' of crates in doors as you suggested.

Thank you both for your feedback!

Steven
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Any smart ideas on contact resolution priorities?

Post by sphet »

Dirk Gregorius wrote:Randy is right. You should sort your contacts such that static contacts are always solved last. This way you reduce chances that stuff gets pushed out of the world.
...
A question. My solver looks like this:

Code: Select all

for ( num_iterations )
{
    for ( num_solver_rows )
    {
         IterateRow( )
    }

    if ( maxDeltaLambda < tolerance )
       break;
}
I solve all the constraints together in the loop - are you suggesting that first I iterate on the dynamic and keyframe contacts, and then I iterate on the static afterwards, as if they are in separate islands? I can't imagine this is what you mean, or that it would work!

I currently don't employ warmstarting, and my iterations are quite high - I wonder if the sorted order is really going to help?

S
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Any smart ideas on contact resolution priorities?

Post by bone »

I'm pretty sure they mean to iterate over all of the sorted constraints in one loop.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Any smart ideas on contact resolution priorities?

Post by Dirk Gregorius »

I have more of a block solver. So it looks like this:

for ( n iterations )
{
for_each( dynamic_contact c )
c->solve();

for_each( static_contact c )
c->solve();
}
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Any smart ideas on contact resolution priorities?

Post by sphet »

Dirk Gregorius wrote:I have more of a block solver. So it looks like this:

for ( n iterations )
{
for_each( dynamic_contact c )
c->solve();

for_each( static_contact c )
c->solve();
}
Interesting - I have to admit while I have significantly refactored this code base I didn't write the original solver so I have not really looked at all the different techniques. What are the differences between the two solvers? The accumulated lambda that is used to determine the resulting forces to apply is part of the whole system of interconnected constraints - each line in my solver row looks almost identical, with the exception of clamping.

S
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Any smart ideas on contact resolution priorities?

Post by Dirk Gregorius »

Well, a good example would be a hinge. You usually solve the motor first, then the limit, followed by the two angular constraints and finally the three linear constraints.

Obviously you want this order as the motor can press on the limit and then as the limit comes after this and cancels the motor again. The motor pressing on the limit is kind of a problem with random constraint order. So this is a mini example of proper constraint ordering. Then you have a couple of options for the remaining five constraints. You can solve each constraint individually (what is what you are doing). Angular constraints are usually much easier (faster) to solve as the linear entries are zero, so I am not sure you utilize that. You can also solve two angular constraints together (as a 2x2 system) and finally solve the linear constraints as a 3x3 system. Of course you can solve the linear and angular constraint together as a 5x5 system as well. This is the most expensive, but also the most stable one as the linear and angular constraints are not fighting anymore. The very best is to solve the 5x5 hinge constraints with the limit together as a 6x6 LCP which can be solved elegantly with direct enumeration.

I never did the LCP approach as this is very expensive in 3D. But Box2D does it and it gives really good results (means stiff limits). I used the 5x5 block solve 10 years ago in Lair. We used varying timesteps which could become terrible large and it helped to keep things together (not stretch) e.g. when the dragon picked up something. Currently I only solve the linear constraints as a 3x3 system. This seems to be a good compromise since it is fast and gives good results. Also note that we solve linear constraints last as stretching is more visible there as for angular constraints. Especially with skinned models.

HTH,
-Dirk

PS:
Again I recommend looking at Box2D. It is all there and trivial to port to 3D.
Post Reply