Comment by dan-robertson | Hacker News Reader

Comment by dan-robertson | Hacker News Reader

Parent Full thread

A general technique that works for any convex shapes in any number of dimensions is GJK [1].

Conceptually it goes like this:

1. Consider your shapes as sets of points

2. If A and B intersect, there is some a in A and b in B such that a=b, or equivalently a - b = 0

3. Consider the Minkowski difference, A - B = { a - b : a in A, b in B }. Two shapes intersect if 0 is in A - B.

4. So answer this question.

And then to actually do this, you want A and B to be convex which importantly means you get (i) that A - B is a convex hull, and (ii) a support function which for any direction can tell you the point in the hull most in that direction. If f is the support function for A and g for B then the support function for A - B is h(x) = f(x) + g(-x).

The final problem is, given the support function for the Minkowski difference of your two sets, how do you determine if it has 0 in it? The answer in 2d is: 1. Pick a random direction and its opposite direction. If both are on the same side of the origin then you are done, otherwise you pick a vector perpendicular to the previous one which points towards the origin (or randomly if there is no such choice) giving you a triangle and three cases: the origin is in the triangle, the origin is not in the hull, or that you need to repeat. 3D is similar except you are going for tetrahedra instead of triangles. You can hopefully find some articles online with illustrations that show how this actually works.

[1] https://en.m.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_dist...

The reason GJK was commonly used in real time usage is that you can cache the previous iterations solution to seed the next iteration which will often have the same result turning it into an O(1). Other commonly used algorithms were SAT (Separating Axis Theorem) and MPR (Minkowski Portal Refinement) although these were all popular in the 2000s and I have no idea what modern engines use nowadays.

Minimizing Minkowski difference between convex bodies can also be formalized as a quadratic program. I wonder how the GJK performs against the QP formulation.

Here is a recent and interesting paper connecting GJK and convex optimization [1]. They show that GJK is equivalent to the iterations of the Frank-Wolfe algorithm applied to the QP, and that recent improvements to Frank-Wolfe can be applied to improve GJK.

Frank-Wolfe is a somewhat less well-known (compared to simplex, interior point, etc) convex optimization algorithm with many interesting properties [2, Section 3.3].

[1] https://roboticsproceedings.org/rss18/p039.html

[2] https://arxiv.org/abs/1405.4980

It’s nice that you understand this. But the explanation is too abstract. Need code to accompany the wiki illustration.

Yeah I had a look for a good article and didn’t find anything I loved in my brief search. I think illustrations are much more useful than code, fwiw. In particular:

- for what Minkowski sums/differences are (maybe some kind of sweep animation would help)

- maybe something to describe what a convex set is / what support functions are. Phrasing them as a supremum of dot products isn’t super useful. You need some idea of some properties implied by sets being convex to follow the next part

- maybe some kind of visual demonstration for the support function of the Minkowski difference

- several illustrations of the steps of the algorithm for determining if 0 is in the set. I think these are some of the more useful and specific illustrations

Reply on news.ycombinator.com