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.
(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?