1
\$\begingroup\$

The very informative mollyrocket video has given me quite a lot to work with, but one thing that the video seems to suggest is that the algorithm should ideally run until it definitely determines whether or not there's a hit.

I was of the idea that if there's no collision, it would be obvious by testing the dot product of the latest point against the search direction; if it is not positive, then we did not pass the origin, so a tetrahedron which encloses the origin simply cannot be built.

In cases where there is a hit OR a clear miss, the routine typically picks up less than 11 loops through. However, as I tend towards 'questionable territory' and the definitive hit/miss is visually less distinct, there are times when the method apparently continues to pass the origin yet construct unsuccessful simplexes.

Is it common to cap this kind of function at a max number of tries? Right now I am somewhat arbitrarily using the number of points in one shape times the number of points in the other shape; in other words:

max_tries = len(shape1.pts) * len(shape2.pts)

It feels a bit hacky and I have to assume that the routine is geared towards simply running ad nauseum until it smacks into a clear hit/miss situation.

Has anyone experienced this before? Is this a problem or an anticipated safety measure in such an algorithm? If it needs to be done I'll gladly share some code, but I think it stands as self-evident that it is kind of a longer read than most code snippets so I've abstained for now.

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Yes, it's common to cap GJK to small number of iterations. This is because the algorithm is most limited by numeric precision. Also I should note that some of Casey's optimizations don't actually work in practice if you need really accurate results. For graphics culling and whatnot, perhaps this is a non-issue, for collision detection in a physics engine this isn't acceptable.

A good example of a solid GJK implementation is in Erin Catto's work in Box2D. He also gave an easier to learn from example in his 2010 GDC lecture and the code is freely available. This is the go-to demo for learning GJK and can be ported to 3D without too much work.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I always appreciate more learning material! Which optimizations are ineffectual? Surely not the actual test cases which are out of the question (not testing line BC in triangle ABC, for example, that's got to be by design) - is it worthwhile to cache the number of unique tested points, then, or get the entire Minkowski difference and cherry-pick points from there, or which optimizations in particular are not effective? \$\endgroup\$
    – Stick
    Jan 22, 2015 at 22:50
  • \$\begingroup\$ @Stick Actually you need to test all voronoi regions! You can't skip any. A simple way to test this is to implement GJK through testing all voronoi regions, and run a series of test cases with various configurations. Then, delete the cases Casey mentioned we can skip and add in asserts instead. These asserts are still sometimes hit. \$\endgroup\$
    – RandyGaul
    Jan 22, 2015 at 23:00
  • \$\begingroup\$ @Stick Oops I hit enter too early. I had more to say: In Erin's implementation there's not a whole lot of caching going on and the code is pretty simple. I don't think anyone needs to do any complex caching like Casey mentioned in his video. \$\endgroup\$
    – RandyGaul
    Jan 22, 2015 at 23:01
  • \$\begingroup\$ well Casey doesn't advocate caching anything, but... hunh. That's weird, I wouldn't have thought we'd need to test in the opposite direction of the search, though I glanced at the slides and it does make sense to look out for repeated support returns (that's got to be a wasted effort to continue to check those points) \$\endgroup\$
    – Stick
    Jan 22, 2015 at 23:10
  • \$\begingroup\$ @Stick Right, Casey nor anyone else advocates caching anything. I think I just misunderstood what you were asking when I said that. Like I said about Casey's voronoi skip optimization, if you don't believe me then take Erin's demo and delete previously checked voronoi regions and insert asserts. You will see that they are sometimes still hit, and therefor must still be checked. \$\endgroup\$
    – RandyGaul
    Jan 22, 2015 at 23:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .