0
\$\begingroup\$

In my deliberations on GJK (after watching http://mollyrocket.com/849) I came up with the idea that it ins not neccessary to use different methods for getting the new direction in the doSimplex function.

E.g. if the point A is closest to the origin, the video author uses the negative position vector AO as the direction in which the next point is searched. If an edge (with A as an endpoint) is closest, he creates a normal vector to this edge, lying in the plane the edge and AO form. If a face is the feature closest to the origin, he uses even another method (which I can't recite from memory right now)

However, while thinking about the implementation of GJK in my current came, I noticed that the negative direction vector of the newest simplex point would always make a good direction vector.

Of course, the next vertex found by the support function could form a simplex that less likely encases the origin, but I assume it would still work.

Since I'm currently experiencing problems with my (yet unfinished) implementation, I wanted to ask whether this method of forming the direction vector is usable or not.

\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

Actually, the negative vector of the most recently added point will not always be a good search direction. I can understand if your intuition brought you to this conclusion, but it's wrong.

Search directions are about finding support points that are furthest along a Voronoi region, away from the current simplex. Search directions are not only about vertices. Besides just watching Casey's video you should study GJK more formally to make sure you really understand what is going on.

In the case of Casey's video, he's just trying to find any axis of separation between two convex hulls in order to early out GJK, not even caring to find the distance between the two objects. This is actually not the original GJK algorithm, but a modified one that quickly finds separating axes.

\$\endgroup\$
1
  • \$\begingroup\$ Actually, I read 2 papers and 3 websites about GJK. And I, too, only want to find seperation. Due to simplification I just cancel the movement if a collision occurrs. But still I thank you for your explanation. \$\endgroup\$
    – s3lph
    Commented Aug 23, 2014 at 14:56
2
\$\begingroup\$

Can't comment yet, but I feel a specific counterexample of why your proposed method won't work is worth the extra answer:

Consider the case where your Minkowski difference is octagonal with vertices horizontal, vertical, and along the diagonal (Stop sign rotated 1/16 turn), with the origin somewhere near the top left diagonal point. Let your simplex be between the two vertical points, and the left-most point as the most recently added.

Your method would have you pick the opposite triangle that is further from the origin (still vertical, but right-most point instead). You would then just alternate between those points, never breaking out of that loop, and never realizing that you do have a collision.

Proper GJK would take only one further iteration to find the origin.

\$\endgroup\$

You must log in to answer this question.

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