Hi, I'm experimenting with GJK and I have a question about warm starting by reusing the simplex from the previous time step.

Is this safe and straight forward to do? Will the GJK algorithm converge even if the vertices of the simplex are no longer extreme points of the CSO?

Are there any other things to consider?

Thanks!

It's a fairly safe thing to do so long as the simplex is not degenerate (which can definitely happen!), so upon warm-starting check for a degenerate case, and if found, invalidate your GJK cache.

Otherwise conceptually warm-starting should make quite a bit of sense. The GJK crawls through the volume of two shapes simultaneously -- so any configuration (that isn't degenerate) is OK as GJK iterations will always evolve the simplex towards the origin due to the properties of support mappings.

Have you tried reading Box2D's source on warm-starting? It is really quite simple: https://github.com/erincatto/Box2D/blob/master/Box2D/Collision/b2Distance.cpp#L104-L165 . Also a little more info: https://pybullet.org/Bullet/phpBB3/viewtopic.php?t=3338

Thanks @Randy Gaul!

I had a look at the link. In case someone searches for this in the future, here is a condensed 3D version of the strategy used in the Box2D source link that Randy posted.

float GetSimplexMetric(const Simplex &s) {

    const Vector3 sp = s.supportPoints;
    switch (s.count) {
        case 2: return (sp[1] - sp[0]).Norm();
        case 3: return (sp[1] - sp[0]).Cross(sp[2] - sp[0]).Norm();
        case 4: return (sp[1] - sp[0]).Cross(sp[2] - sp[0]).Cross(sp[3] - sp[0]).Norm();
    }
    return 0.0f;
}

void DoGJK(Cache* cache) {

    Simplex s(cache->indices, /* New support points calculated from cached vertex indices */);
    float metric = GetSimplexMetric(s);

    if (newMetric < cache->metric * 0.5f || newMetric > cache->metric * 2.0f)) {
    	s.clear();
    }

    // Do normal GJK...

    // Update the cache with the new simplex indices and the simplex metric    
    cache->set(s.indices, s.count);
    cache->metric = GetSimplexMetric(s);
}

The idea is to build a metric that is proportional to the length/area/volume of the simplex and then throw away the simplex if this area changes by two big of a factor between frames.

The exact ratio of the limits are not so important from what I can tell. It seems to be more of a "better safe than sorry" kind of thing. The big win is in avoiding recalculation of the simplex for resting and near resting contacts.

Box2D uses factors 0.5 and 2.0 with a linear metric. So to get the same factors for a square metric like in the example above I guess you would use 0.25 and 4.0 instead. But I doubt  there would be much difference in practice...

Hi,

I wrote an engine in Java a few years ago.
It includes this algorithm.
https://github.com/g-amador/JOT/blob/master/engine/Core-Toolkit-Components/src/main/java/jot/math/GJK.java

Back then I followed mainly these two articles: 
 
http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/

http://lewisresearchgroup.wikidot.com/gjk-algorithm

Best regards

Those two links do not cover numeric stability concerns of the GJK algorithm. The best resource is Erin's code and his GDC lecture. He hosts all his lectures at box2d.org in the downloads section.