Real-Time Physics Simulation Forum

Re: PGS Iteration: local vs. global

2013-05-24T19:44:30+00:00

Dirk,

Do you use the feature pair as a key, or a distance calculation? Currently I am doing a distance calculation but I am wondering if I should change to a feature key as suggested in the GPG4 article. Upside is faster search and unique contacts, even when updated. Downside is that contact point generation has to be more sophisticated. For example: when generating contacts between a capsule and a plane I need to generate a pair of contacts for the line each frame with a key for each end of the segment... maybe that's not such a bad idea, but returning just one point a frame seems to work.

S

I suggest going with feature pairs if possible. The only downside, like you said, is it is harder to do. If you'd like a good reference for generating feature pair information take a look at all of Box2D's collision routines. The nice thing about feature information is you can use indices as features for generalized polygons if you store feature information in an array. I actually just implemented generalized polygon vs polygon collision detection with the help of Dirk's GDC lecture, partially for the purpose of simpler feature pair generation.

IIRC the most recent version of Box2D has a feature pair like so:

Code:

struct featurePair{  union  {    struct    {      char indexA;      char typeA;      char indexB;      char typeB;    };    unsigned id;  };};

This style is in my opinion pretty cool. A and B are the colliding objects. The type of feature can be in 2D either a face or vertex. In 3D you throw edges into the mix. The index is an index into an array of features, such as face normals or vertices. The id can be used for integral comparison of feature pairs, and is very fast. What makes this easier to derive is using feature indices for generalized polygons, which lets you think in terms of your algorithm loop instead of cold-hard geometrical representations.

Statistics: Posted by RandyGaul — Fri May 24, 2013 7:44 pm

Re: PGS Iteration: local vs. global

2013-05-24T18:19:52+00:00

Dirk,

Do you use the feature pair as a key, or a distance calculation? Currently I am doing a distance calculation but I am wondering if I should change to a feature key as suggested in the GPG4 article. Upside is faster search and unique contacts, even when updated. Downside is that contact point generation has to be more sophisticated. For example: when generating contacts between a capsule and a plane I need to generate a pair of contacts for the line each frame with a key for each end of the segment... maybe that's not such a bad idea, but returning just one point a frame seems to work.

S

Statistics: Posted by sphet — Fri May 24, 2013 6:19 pm

Re: PGS Iteration: local vs. global

2013-05-22T23:56:58+00:00

I match contact points from the last frame with the current frame. I don't rescue points over several frames. That is why it is very important to make sure that your contact doesn't break (e.g. due to overshooting).

Statistics: Posted by Dirk Gregorius — Wed May 22, 2013 11:56 pm

Re: PGS Iteration: local vs. global

2013-05-22T23:31:48+00:00

Dirk How long do you keep the old contacts? I am sure they get rapidly less useful as time passes and they are psuedo warm starters in a sense.

Statistics: Posted by SinisterMephisto — Wed May 22, 2013 11:31 pm

Re: PGS Iteration: local vs. global

2013-05-17T03:22:51+00:00

Ah. I thought there were two different cases. Thanks for clearing it up.

Mike

Statistics: Posted by mikeshafer — Fri May 17, 2013 3:22 am

Re: PGS Iteration: local vs. global

2013-05-16T22:01:21+00:00

You keep a cache of contact points so you can match up old with new contact points based on the contact ID. If you can match two points you copy over the accumulated impulse from the last frame. In a persistent manifold you just find one contact point frame and need a contact point cache to find all four points.

The first cache is about warmstarting the contact solver and the second one is about building contact geometry. In the later one the warmstarting comes for free.

Statistics: Posted by Dirk Gregorius — Thu May 16, 2013 10:01 pm

Re: PGS Iteration: local vs. global

2013-05-15T04:39:36+00:00

Correct me if I'm wrong, but the reason Erin's paper says you need a "cache" for feature sets is because the contact points will come and go and you will want to store that memory somewhere so the next time that feature set is encountered, we have an impulse value ready for the solver. My understanding was that contact points are persistent and this alone is the cache. I think I was looking at it wrong, what do you think?

Mike

Statistics: Posted by mikeshafer — Wed May 15, 2013 4:39 am

Re: PGS Iteration: local vs. global

2013-05-15T02:56:50+00:00

Bah, I just divide displacement by the timestep and group everything as velocity constraints. Maybe I should separate them like you do. I'm not sure my warmstarting is accurate. For a given contact point, I store the impulse last calculated and use it (multiply by M^-1J^T) to form my guess for PGS in the next frame. Do you think collision is a factor? I'm not box clipping, I'm using GJK. But with more iterations it definitely stacks--so I don't know...

Mike

Statistics: Posted by mikeshafer — Wed May 15, 2013 2:56 am

Re: PGS Iteration: local vs. global

2013-05-15T02:12:12+00:00

I just checked. For 5 boxes starting nicely touching I need 4 velocity and 1 position iterations. If the boxes fall onto each other from 0.5 meters I need 8 and 2 iterations.
You will need warmstarting for this to work. With warmstarting you essentially get an amortized iteration count over several frames.

Statistics: Posted by Dirk Gregorius — Wed May 15, 2013 2:12 am

Re: PGS Iteration: local vs. global

2013-05-15T01:34:52+00:00

Wow that's a really low amount of iterations. Maybe I'm doing something wrong. I'll look into it.

Mike

Statistics: Posted by mikeshafer — Wed May 15, 2013 1:34 am