Can someone explain me the GJK algorithm?

GJK is WAY overkill for OBB-OBB distance.

To do OBB-OBB, first realize that the boxes are AABBs in their own coordinate system, so transforming the query into one of the boxes systems turns into an AABB-OBB, which MAY help you save cycles.

Second, all you need is to use the separating axis theorem. Google for that, and you''ll be happy.

You could also code up a feature isolation approach, where you first detect which feature of the OBB will be closest to the AABB, and then calculate actual distance. Using the fact that the second box is an AABB in this space helps a lot in this case.

Thanks for your reply hplus0603,

However:

The separating axis will not give you an OBB-OBB distance. It can approximate it, but it''s not exact.

GJK is way overkill for OBBs, but what I want to do is have a specialized GJK function for boxes. In many papers GJK is used (a specialized implementation I guess) to compute fast OBB-OBB distances.

Brute-force calculation would be too long (edge-edge and face-vertex features)

No one? ...

I''ll give it a shot. first thing, the minkowski sum.

to find the closest points on convex A and convex B, it is equivalent to finding the closest point on convex (B - A) from the point (0, 0).

To ease the transition, you can first see it that way. Because objects are convex, for every points on the surface of A Ca, there is a unique closest point on the surface of B Cb. The vector between Ca and Cb is therefore simply (Cb - Ca). Then the closest point between A and B will be the points Ca(i) and Cb(i) where Ca(i) is on the surface of A, Cb(i) is on surface of B, and |Cb(i) - Ca(i)| is minimum. So, it is equivalent to finding the point C(i) = Cb(i) - Ca(i), where C(i) is minimum. And C(i) will be on the surface of the abstract construct (B - A), the minkowski sum of A and B.

right, now you are left to finding a point on a unknown convex hull C = B - A.

now the support functions. if you have a vector D, a direction, the points on Cb and Ca which are the closest along that direction D will be Ca(D) = min(Pa, D), Cb(D) = max(Pb, D), where Pa is a point on the surface of A, and Pb is a point on the surface of B. Then clearly, the distance d = |Cb(D) - Ca(D)| will be the minimum distance from all the collection of points Pa and Pb. Also, Cb(D) and Ca(D) are part of the convex hull of the minkowski sum (B - A), which brings us back to the problem of finding the pair Cb, Ca so that |Cb - Ca| is minimum.

So, the GJK algorithm tries to find the minimum d possible, by calculating support axis D, finding the support points on A and B, and narrowing it down until d (d = |Cb - Ca|) is indead the minimum distance.

now the maths part.
It achieves that by constructing a convex structure (call it S) as it goes along, that will approximate the surface patch of the convex object C, and finding the point on S the closest to the origin. To do that in 3D, S can be reduced to a maximum of a 4 point tetrahedron, and finding the point on the tetrahedron S that is the closest to the origin. Once that point is found, S is recomputed, so the vertices of S are all closest to the origin, and one of the previous vertex is discarded. All vertices of S will be on the surface of C.

That''s for 3D, it''s hard to visualise in 3D, but in 2D, the terahedron is replaced by a triangle. It''s then easy to see that, as you find a new support vertex on the convex C, you add that point to the list of 3 points, which generates a quad. Then you can remove one of the edge, the one that is the furthest away from the origin. Then you find another support point, and repeat the process.

The GJK uses barycentric coordinates, to find the closest point on the ''triangle'' the closest to the origin. In 3D, the same system is used, on 4 points (the points of the tetrahedron), which is like a set of 4 linear equations to solve.

Thanks a lot Oliii!!!
Now I understood