GJK Warm Starting

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

GJK Warm Starting

Post by Erin Catto » Fri Mar 13, 2009 12:19 am

I'm trying to reduce the iteration count in my GJK implementation when there is temporal coherence.

The final search vector can be re-used as the initial search direction in the next call. With small frame-to-frame rotations (~10 degrees) this increases performance in my tests by 8-20%. However, the iteration count is still often greater than one.

I am only using GJK for polytopes (1 to 32 vertices) and I need the distance. It seems that we should be able to warm start and perform only one iteration in many cases. If the closest features don't change, we ought to get away with just one support point call.

Stephen Cameron seems to store the simplex vertex indices for warm starting. This sounds great but I'm concerned this may have some bad implications. For example, large relative motion may distort the cached simplex into a degenerate configuration.

Does anyone have experience with these or other techniques for GJK warm starting?

Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: GJK Warm Starting

Post by Nathanael » Fri Mar 13, 2009 6:41 am

For polytopes, a cheap warming is to use center masses as an initial direction, that give you some speed-up, and does not require to store anything.

Now if you want to cache the last simplex, you could store it as a list of vertex pairs ([vertexIndexInA,vertexIndexInB], etc...) , rebuild and solve the actual simplex at start up, using current transforms. That should eliminate the degenerated configuration issue but only works for polytopes of course.

Hope it help,
Nat.

Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: GJK Warm Starting

Post by Erin Catto » Mon Mar 30, 2009 4:23 am

I've tried caching the simplex vertex indices to rebuild the simplex for warm starting. It works very well! In coherent scenarios GJK often converges with just one support point call. It also seems to produce a good guess when the cached simplex is non-optimal.

Degeneracies are still possible. For example, a cached triangular simplex (simplex-3) can potentially re-assemble into 3 colinear points when the shapes move between calls. The cure is to detect the degeneracy on startup and reset the simplex if necessary.

Nathanael
Posts: 78
Joined: Mon Nov 13, 2006 1:44 am

Re: GJK Warm Starting

Post by Nathanael » Mon Mar 30, 2009 9:13 am

Erin Catto wrote:Degeneracies are still possible.
Yes, right, I haven't thought about that, I'm going to check my own code :)

If you store simplex vertices (position, not index) in shape local space, it should be possible to make warm-starting work for implicit primitives too, but having to apply the inverse transform for each vertex may be overkill. An other possibility could be to index 'vertices' of implicit primitives too, say [0] for sphere, [0,1] for cylinder end points, etc...

Nat.

Post Reply