5
\$\begingroup\$

The GJK algorithm depends upon a function in its loop that updates the simplex and search direction for the next iteration (which is often called something like DoSimplex() or ProcessSimplex()). In order to find the next simplex, the algorithm divides the current simplex into regions, and determines which region contains the origin.

Here is an example of the regions for a 1-simplex (i.e. a line). In this example, the simplex previously only contained point B, and then point A was added in the direction of the origin.

GJK simplex regions

(http://entropyinteractive.com/2011/04/gjk-algorithm/)

Now it makes sense to me why the origin can't be in region 4, since we just came from there. However, I can't think of any case where the origin would be in region 1 either. We just traveled from B to the origin, and if we didn't reach the origin, then we know there was no collision. So won't the origin always be in 2 or 3? Why does every algorithm always check whether the origin is in region 1?

\$\endgroup\$
2
\$\begingroup\$

I discovered my answer. If the origin is in region 1, then it is a termination condition. It means that the origin isn't inside the Minkowski Difference, and therefore the shapes are not colliding. We just return the single point so that the next loop will terminate, and we can keep our support code general, without any special casing for exiting early.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.