A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)

In 1988, three engineers came together and developed one of the most clever solutions to the problem of detecting when two complex objects collide. Their solution, the Gilbert Johnson Keerthi (GJK) algorithm, named after the authors, made an incredible impact in the fields of robotics, control, and computer graphics. This video is about understanding this ingenious algorithm from first principles.

The video covers a broad range of topics from Minkowski sums and differences to support functions to the full implementation of the 2D GJK algorithm. But what I hope you get out of this is an appreciation of the incredible shifts in perspective that lead to the final algorithm. Coming up with the algorithm is an amazing feat and useful for specific applications, but the overarching problem solving techniques that come through in the journey to the solution is truly invaluable.

0:00 Introducing the Problem
2:02 Convexity
3:15 Infinite Point Perspective
4:07 Minkowski Sums and Differences
6:37 Triangles inside Minkowski Differences
7:41 Simplexes
8:57 Support Functions
13:05 Core GJK Algorithm: Broad Perspective
17:15 Remaining Key Questions
17:56 How to determine if a point passed the origin?
19:10 The line case
20:41 The triangle case
26:25 GJK Implementation
29:38 Recap and quick note about original GJK paper

This video is supported by a community of Patreons
Special Thanks to the following Patreons:
Burt Humburg
Justin Hiester
Michael Nawenstein
Richard Wells
Sebastian Gamboa
Zac Landis

There's a lot more to the GJK algorithm to learn for those interested. Here are some resources I recommend:

Music attributions:
All other tracks by Aakash Gandhi

[SebastianLague]

Really clever algorithm, beautifully explained!

[MeshMachine]

I'm a game dev and implemented this algorithm in 3D for an in house physics engine, long since defunct, as commercial physics engines are used almost universally these days.
This is a great illustration of a well designed algorithm.

[eshh]

This is definitely the most complex topic you have picked till date! And to support that, you came up with your BEST work till date!

Truly speechless! After your last video on collision detection, I was inspired to read more into computer animation. And the shear number of times that the name GJK came up was astounding!
I tried reading about it from a number of sources, but couldn't go on after the introduction of support functions! Little did I know that you had planned such a great surprise for us!

Much like the immense ingenuity of this algorithm, the difficulty that one faces in communicating such beautiful, yet daunting math and science, is often overlooked!
Thank you so much for making these videos!!

[altervoid]

i smashed my keyboard because i want to learn something and whatever pops up ill learn that, and this guy pop up

[NovaWarrior]

I live for the day that these are on trending. I really do.

[zemaumm]

My eyes just opened up when you reinterpreted the problem as a minkowski difference problem… I’m a software engineer ( who fiddle with graphics a little ) and it’s genuinely beautiful how the maths I briefly learned at college is so diverse yet relevant to what I do.

[kenthedawg]

As someone with a graduate background in computational geometry, this is a fantastic video and you really know your stuff! Please make more of these!

[fredoo]

Manim should be used by every math teacher. It's so beautiful.

[mikemullen]

This was an interesting problem for TV games, since most actions involved collisions between screen objects. Early 8 bit computers couldn't have handled this algorithm, so a simpler system was needed. The solution was invented by Ralph Baer (see Wikipedia). Objects were 'painted' on the screen by shifting out bits from a shift register when the line number and pixel numbers matched. As well as going to the screen, the signals were sent to an AND gate, which went high if the same pixel was being loaded by two different objects. Magnavox bought the patent rights:. I helped develop the Odyssey II which used these patents. Other manufacturers bought rights to the circuit from us.

[paulomag]

This is perhaps the clearest and most beautifully explained GJK explanation I've ever seen. I do believe, though, the direction vector does not require normalization on any step. I've implemented this algorithm for my graduation paper, and I have to say it is one the most brilliant computer algorithms I've seen in my studies.

[elijahbuchanan]

9:30 makes me think of a great line from numberphile. "You've broken maths, Brady, stop that."

[kattenelvis]

HAHAHAHAHAA I love the bit when you say that if I find a counter-example 3blue1brown would be after me

[gormster]

9:01 I had to go back over this section a few times because it misses some key points I had to figure out on my own.

Firstly - you can slide a shape around on the plane, and the support function always returns the same vertex for a given direction vector. While the actual values of the dot products will change a lot, which one is largest always remains the same. The confusing part of this is when the vector from the origin is actually pointing away from all of the vertices, but while all the dot products might be negative, one of them is still going to be greater than the rest.

The other thing that confused me is the way that the highlighted point on the hexagon seems to jump instantly from one vertex to the next, which would appear to contradict the line “for every point on the shape, there is a direction where it is the furthest point.” What about the points along the edges of the hexagon? Well, when the direction is perpendicular to that edge, *every* point on that edge is the furthest point.

Think about it like a single straight wave on a calm ocean, travelling in that direction. It starts way outside the shape, and then gradually passes over it. The support point is the very last point it touches. If it’s travelling from left to right in this hexagon example, the last point is the vertex on the far right. But if it’s travelling from top to bottom, the last thing it touches is the bottom edge, and it touches the whole edge at the same time. So the support point for that direction is every point on the bottom edge.

[startscratching]

As a normal secondary school student who's into competitive programming, we usually tackle the triangle case with a much more natural idea: we calculate the 2D cross product AB * BO; BC * CO; CA * AO. If one is equal to zero, the point is collinear with the corresponding edge, and we just check if the point is on the side. Else, point O lies inside triangle ABC if and only if all of these values are all positive or negative. An intuitive way to understand it is if the triangle ABC contains O, then we can walk around the triangle, and the direction we see from that point we stand to the point O is always in our right hand or in our left hand. Hope that helps.

[Speykious]

Wow... This is... Beautiful... I've looked at it for 5 hours now

[ToothbrushMan]

Really well explained. You have only a few competitors for this subject, but this is the best I think I've seen.
I've been through the process of implementing a 3D version. It's good fun, but I found myself using a recursive method because, quite frankly, it's easier to understand and yes, more aesthetically pleasing. It also deals very elegantly with the "edge" cases - where the origin lies on a vertex, edge or face of the simplexes (point, line, triangle, tetrahedron). There are quite a few "edge" cases, all have to be dealt with. So if you've got a tetrahedron and you find that your origin lies on one of the edges of the tetrahedron, then the next call is back to the function (already in the call stack) that deals with edges, passing in the new edge just discovered. The other nice thing about a recursion is that the optimisation of not having to check Voronoi regions because they've already been checked in previous recursions is performed by carefully cycling the order of the vertices in the function calls (with the most recently discovered vertex first and the oldest discovered vertex last). And a third nice thing is that all the data is held on the stack - no heap allocation/deletion. Hence falling out of the recursion after a termination is super quick. My GJK works (almost) faultlessly, but there are some (painful) lessons that I learnt that readers might be interested in:
1. Numerical precision. Detecting the "edge" cases (origin on a point/edge/face of an edge/triangle/tetrahedron) is not as easy as it seems, because although the origin can mathematically be on a point/edge/triangle - and a dot product *should* be zero - only it isn't because of numerical precision. With my recursion, I found that on successive calls to trap the origin in a tetrahedron were being thwarted when the origin appeared to "jump" from one side of a tetrahedron face to the other as I chased it - running out of stack in the process. I was using 4 byte floats and the numerical precision HAS to be considered, but if you're using 8 byte doubles, you should do much better.
2. There is the case that the triangles get smaller and smaller and flatter and flatter when iterating to towards an origin on the Minkowski difference between two smooth convex objects (e.g. two ellipsoids). If the tetrahedron get too small or too flat, you could be looking at numerical rounding issues again.
3. If the first two directions happen to be on opposite sides of the origin chosen then you've got an edge with an origin on it. Picking the 3rd direction as being perpendicular to this edge *on the side of the origin* gets a bit ambiguous. I spent a few hours with graph paper and a pencil with this.
I surprised to see no mention of the Expanding Polytope Algorithm (EPA). The GJK and the EPA are a pair of algorithms that are complementary to each other. Whereas the GJK works out IF two solids intersect, the EPA works out HOW they intersect (penetration depth and collision normal) - and the collision normal is needed for the collision physics. But the great thing about the EPA is that the data structure that the GKJ finishes with (a simplex that surrounds the origin) is precisely the same data structure that the EPA starts with.

[thedoublehelix]

I heard about this algorithm for the first time while watching a talk by Casey Muratori, and my mind was blown! It was a really neat piece of math.

[konstantinkh]

I've written a working implementation of GJK, and I still learned things from this video, like the fact that I was checking some cases I didn't need to, as they would have led to a rejection at an earlier stage. This video also has visualizations I really wish I had when writing my implementation and that I had to sketch out on grid paper. Definitely going to recommend this video to anyone who needs to know how the relevant code works.

[Zimbleton]

Note that in computer games etc, shapes normally have a bounding sphere/circle or box that is used to perform very quick check for intersection and only if the simple bounding shapes intersect then you perform more complex algorithm like this.

[kika]

So well explained! I read several blog articles about GJK last year and remember feeling like it didn't quite click for me. In 30 minutes, now I can say for sure that I understand how it works. Thanks so much for your content, you never cease to make math and CS as fun as they should be!