A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)
ฝัง
- เผยแพร่เมื่อ 28 พ.ค. 2024
- 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:
• Implementing GJK - 2006 - a full walkthrough of how to implement GJK in 3D by Casey Muratori, the game developer/engineer that came up with some of the clever optimizations that I present in this video.
www.dyn4j.org/2010/04/gjk-gilb... - a really nice writeup on GJK
• GJK Algorithm Explanat... - A quick intro to GJK and an implementation in C++
www.toptal.com/game/video-gam... - solid resource for collision detection in general and goes deeper into the theory.
box2d.org/files/ErinCatto_GJK... - an alternative perspective to GJK using barycentric coordinates -- I really wanted to cover this in this video, but it would have been an hour long instead of half an hour long so I'll compromise and give you this resource :)
Support: / reducible
Twitter: / reducible20
This video wouldn't be possible without the open source library manim created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music attributions:
Midsummer Sky by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. creativecommons.org/licenses/...
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
Luminous Rain by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. creativecommons.org/licenses/...
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
Prelude No. 23 by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. creativecommons.org/licenses/...
Source: chriszabriskie.com/preludes/
Artist: chriszabriskie.com/
All other tracks by Aakash Gandhi
Really clever algorithm, beautifully explained!
next coding adventure, maybe?
nice to see you here
This is amazing
@@josephwalker208 Coding avengers, maybe?
I have no idea what these two incredible youtubers could do together, but this would be amazing
HAHAHAHAHAA I love the bit when you say that if I find a counter-example 3blue1brown would be after me
That got me laughing, too!
HAHA , he would be all Brown no blues from the amount of rage he would have
Who are the 3bluebrown
@@JapanShopBrazil 3blue1brown is another TH-cam channel with similar a very explanation style and animations. Both this one and that one are excellent.
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.
How can you add these function in game dev
Hi. How can add these function in game dev
@@47lokeshkumar74 you probably just need the coordinates of each vertex for each body
@@47lokeshkumar74 why do all videos that in the slightest technology-related necessarily have at least one completely clueless indian in the comments asking either to have the entire project or a dumb question like yours that shows they don't even have 10% the know-how to do it? Get your kind off the internet
Had to implement this in 3D too and pulled chunks of hair out in the process.
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!!
I live for the day that these are on trending. I really do.
Have you seen Mr Beast reacts to breaking stuff with bowling balls? It's a new level of ugg.
@@prezadent1 What does "ugg" mean?
@@usualunusualkid7149 worthless content that gets really popular
@@prezadent1 Makes sense. In order to get popular you have to appeal to big demographics, and one of the biggest demographics is young children.
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.
Manim should be used by every math teacher. It's so beautiful.
Every math teacher should show videos made with it, but not every math teacher should use it cuz it has a fair learning curve and not everyone has time for that.
Someone should make a GUI for manim.
@@yonatanbeer3475 Have you downloaded it? It took me
@@xnick99 what tutorial resources did you use? I've been having trouble getting started with it and have just put it on hold
@@willjohnson4579 I downloaded examples from github and used some of the github tutorials
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.
Your wave analogy was very helpful!
Thanks, I was stuck here too! Wave analogy helped
Yes. To find the vertex with highest value doesnt mind the value has to be positive. Each vertex is checked against previous one to see if its greater. First vertex I check against negative infinity. I hope not catching exception there wont bite me
Another analogy for your second confusion that helped me was to think about the direction not as a vector rotating inside stationary shape, but have the shape rotate instead and always check point that is highest (the direction doesnt matter, its just its always the same direction). You are right that at certain orientations there isnt a single point furthest, it is a line between two vertexes. Why I think it doesnt matter is that you are looking for furthest point in that direction, you dont care if the point is to the left or right, you just need to pick the furthest. As such, picking any point on the line is valid, so there is no need to check every point on line, just the two vertexes, and arbitrairly choose one of them.
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!
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.
Hello! As a side project, I am currently working on a softbody physics engine. When I was doing line-triangle intersection, I had to see if the intersection point between the line and the triangle plane was within the triangle. Your algorithm doesn't work: try it with the point at the end of the arrow ABperpendicular at 25:57 . Here's one that works:
a = cross(AB, AO)
b = cross(BC, BO)
c = cross(CA, CO)
Return (dot(a, b) >= 0) and (dot(a, c) >= 0)
@@FredGlt Actually, I got accepted in a problem on Codeforces with my approach :))). Would you please send me a counter-test (exact coordinate of the points)? I'd be very appreciated
@@startscratching6282 are you sure you mean the dot product and not the cross product in your original explanation?
Your algorithm as explained checks if a point is inside a triangle whose *edge's normals* are AB, BC and CA, which is a very different triangle than the one you want whose *edges* are AB, BC and CA.
Take the triangle (5,2), (-4,1), (1,-3) and the point (0,2) if you want to confirm.
For reference, I am currently studying for a baccalaureate in physics and computer science :)
@@FredGlt I actually meant cross product in the original comment :))) Sorry for my poor English skills.
@@startscratching6282 No worries! Good luck with your studies and programming projects :)
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.
That is an awesome tidbit, thanks for sharing!
9:30 makes me think of a great line from numberphile. "You've broken maths, Brady, stop that."
what video is that from?
@@mayabartolabac idk, one on factorial I think.
@@mayabartolabac He's right, it's the video on 0!
@@sponge1234ify haha i watched it
Doesn’t that mean the axiom are changed? Math itself isn’t broken? lol
Wow... This is... Beautiful... I've looked at it for 5 hours now
I love the fact that you physically couldnt have looked at it for 5 hours because of when the video was uploaded and when you commented. You must have bent spacetime to get more beauty out of the video.
@@elijahbuchanan2368 _I accelerated my brain activity_
@@elijahbuchanan2368 his brain got so wavy it became a black hole and bent spacetime around itself, if everything this comment speaks about the magnificence of this marvelous work of divine creation.
This might be my favorite comment thread on this channel :) Y'all made me laugh!
@@Reducible poggers, how has It been to work on this video? Tbh feels like the hardest on the channel atm (maybe rivaling with the CG one at least to me)
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.
Yeh no derrr dude. It's stupid to continously check every object in the scene constantly. Most people can figure that out dude. You're stating the obvious, you nonce.
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.
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.
30:52 Calculating the closest distance between objects is extremely useful in physics engines, where you need to not only detect when a collision occurred, but also de-intersect the objects after the collision.
Pushing back the objects by setting their positions is not the right way handling collisions. You have to apply a reaction force to colliding objects. But you may like to adjust the reaction force according to the penetration depth.
@@walker-snow sometimes its done in combination with that, to avoid jittering that would otherwise be more apparent
@@walker-snow de-intersection is mandatory before the next step, or else you get another collision which shouldn’t happen. This leads to erroneous collisions and a whole host of wacky physics issues.
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.
Sketchnig out on grid paper is best method for me, i often do this . Did You implement such algorithm for 3d shapes ? If yes, let me know where to look for good explanation of similar algorithms, if You know.
@@AB-bp9fi Yeah, I implemented it for intersection tests in a simple 3D engine. There is a way to extend the method for sweep tests as well. Effectively, take Minkowski difference and ray-cast against it. The ray test uses combination of a ray march and simplex methods to converge to an impact point really quickly. Being able to do intersection and sweep tests with literally any convex shape using single algorithm is fantastic for quickly standing up simple physics and other interactions. Unfortunately, I don't think I can recommend any other resources, because this video is by far the best. It covered in 30m what took me many hours to divine from other sources, and as mentioned above, showed me that I've missed a few optimizations. 3D works literally the same way, though. The only difference is that the regions you are considering are extensions of 3 faces of the tetrahedron, and you pick +/- face normal (whichever points more towards origin) to find your next support point, and whichever face you ended up choosing, discard the vertex opposite to it.
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.
Man, this is a gem of a comment -- thank you for sharing. And the numerical precision issue is a real practical consideration and one of the major annoyances with this algorithm in practice. That's part of the reason why I made a note about the edge case with the origin landing on edge or vertex of Minkowski difference because even though it seems that it would be easy to handle with the dot product, these degenerate cases do need to be carefully handled with numerical precision in mind.
And yeah EPA does go hand in hand with this algorithm. I briefly debated adding a small section on it, but felt it might have gone on way too much of a tangent and the video was already getting fairly long for my liking.
@@Reducible You made such a good job with this beautiful algorithm. Congratulations!
this comment needs to be pinned!
Hi Toothbrushman, I'm currently trying to implement a 3D version of this myself and I'm not sure I understand your claims about the benefits of a recursive approach (granted, I haven't worked on this for long yet).
1. With an iterative approach, I don't see any data that needs to be allocated on the heap. You have the simplex array, which contains at most four vec2s (one for each point of a tetrahedron), and a direction vector (a vec3). This is so little data that you can surely allocate it on the stack.
2. As for "edge" cases, I *think* I understand the benefit of recursion here, but I want to clarify. You're saying that, in a recurisve approach, you only have to code a check for the "edge" case once - for a 1-simplex (a line). Then, the triangles, which are built of lines, automatically get checked? Not quite sure how this works, seems like it might cause unnecessary checks though
Would be curious to see your implementation of GJK and how it simplifies the optimization of not checking certain voronoi regions.
@@Reducible
Just came up with a good way to deal with the numerical precision issue for the line case.
If the line contains the origin, the magnitude of the triple product will be 0. In practice, with numerical error, it'll only be close to zero. In my implementation, I defined a tolerance constant and if tripleProduct < tolerance, then the line contains the origin.
For high performance applications, you may want to avoid magnitudes (square roots can be slow). Easy fix - just use the squared magnitude instead. If the magnitude of the triple product is 0, so is the squared magnitude.
In any real use of this, it will be easy to check the axis-oriented bounding boxes of the shapes. In 2D, that will only require at most 4 numeric comparisons. GJK requires at least 25 dot products. So, step 0: if the bounding boxes don't intersect, return false.
That may seem trivial, but the little things often make a big difference.
I was thinking the same thing. If the goal is to just check for overlap
And he scores again! The use of manim is really impressive! This channel really fills a void in youtube
What is manim?
2:48 Wait... Is there really a simple algorithm do break down concave shapes into convex ones? If so, can you explain it in another video? I would love it!
delaunay triangulation
I have bad memories of attempting to do exactly that during my geometric algorithms course.
If I recall correctly, it requires the polygon to be monotonic in some axis (aka, that from a 'highest' to a 'lowest' point, there are two chains on which the relevant coordinate always decreases along the chain.) There might have been something about breaking shapes into monotonic ones, but I don't exactly recall that, it was ages ago.
I had tons of bugs, numerical stability issues with nearly colinear points, and in general it was a pain.
Just before posting I checked wikipedia and apparently Delaunay triangulation is something completely different, it applies to sets of points and their voronoi diagrams (the intersections of the cells always forming a convex shape, if they weren't, you could extend the lines perpendicular to the concave part and find an intersection)
Look for “polygon triangulation”. The easier ways require monotone polygons already mentioned in the previous comment. (Looking at 2:59 though, it looks like the video is using a probably simpler, or even trivial, solution of introducing extra vertices. AHHH NEVERMIND IT WAS SPECIALLY CONSTRUCTED.)
@@spyral00 How do you triangulate a circle?
@@drewduncan5774 Well, here you don't actually have to, as a circle is convex and has a support function (mentioned in the video), but you can simply generate roughly evenly spaced points on the circle and then either define those as a polygon, or do some kind of triangle strip (from first point to each pair of adjacent points) or other possibilities (center to adjacent pairs, grouping each three points on the outside polygon therefore reducing the number of uncovered points and then recursing on the inner polygon, etc.).
i smashed my keyboard because i want to learn something and whatever pops up ill learn that, and this guy pop up
Thank you for putting in all the effort necessary to creating these. I love that they're an accessible, entertaining way to broaden your algorithmic problem solving skills.
Very well done, I like this exploration of high level algorithms that aren't terrible to grasp if presented well.
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!
Thank you so much for this comment Erika. I definitely empathize with that feeling, since I also went through that stage where it took several weeks of research into the current blogs/videos/literature for GJK and putting the pieces together on my own for things to click. I'm glad this video made it easier for people like you!
Finding this channel was like winning the lottery, you sir have managed to reignite the fading passion I had for computer science and most importantly, learning. I can't stress enough how useful your videos are and I wish more teachers would take the time to explain things the way you do. Hope you keep up the great work, you deserve all the recognition
Beautiful walkthrough. Didn’t expect to imbibe a half hour geometry video first thing in the morning, but now I have a fresh appreciation for creative problem solving to propel me through some projects I’m working on. Thank you!
Great Video! Fun Fact: you can also use a 2d GJK for 3d raytracing by placing an imaginary camera in the ray origin and projecting the support function on the "camera-plane". For 2d this approach has constant runtime and you don't need to iterate.
This is probably the best introductory resource for this algorithm on the internet. The algorithm is really cool even though many people justifiably prefer something simpler especially since already in three dimensions you get precision issues with a pure float implementation. If precision wasn't such a huge issue it would also be interesting to think about a 4d implementation for CCD.
I could have really used the videos like 8 or so years ago when implementing GJK myself. It would have saved me a lot of work and I think this will be a huge help to people implementing this in the future. :)
Thanks for the comment about 3d ray tracing, I did not realize that was an application of this algorithm. Pretty cool!
I'll definitely store this nugget away for later. =)
Sir, I don't think I can express enough how incredibly helpful this video's been. I've been banging my head against collision math for a while, and having _so_ much of the math I'm missing abruptly laid bare is...I think it's a genuine gift from heaven.
This is a great introduction into convex sets and their geometrical properties that also touches upon other areas, both inspirational and intuitive.
Love the content, so glad that Grant referred to this channel!
Who is this grant?
@@danielbenjamin66 Look up 3Blue1Brown, amazing math channel. He also made the library (Manin) used in this video for animations.
@@vervok thanks man
I keep coming back to this video. And every time I watch, I realize a neat detail that I missed previously.
I took a backup of this video to preserve it for the future generations :)
It seems like you can view this algorithm as the composition of two simpler algorithms:
1. "Compute the support points of the Minkowski difference given the support points of the input shapes" (or provide a function which provides a support point as a function of direction, given the same for the inputs)
2. "Check whether a convex shape contains the origin" (given a function that provides a support point as a function of direction)
My first instinct when half-way through the video was to implement just (1) and compute (2) by brute force checking all possible simplexes across the support points. This initially almost appears to be more tractable because your sets are all discrete, so the combinatorics stay finite (ignoring important details like circles)
However, the video demonstrates that (2) as performed in the algorithm is a powerful trick to allow you to check whether the origin is contained by a shape, without computing all of its support points or testing all possible simplexes - all you need to provide is a simple-to-compute function to get a support point based on a direction. This technique, despite having a continuous input to "search" across (the input 'direction') actually has a finite number of iterations to the exact solution
This decomposition of the problem is really well-explained in the video (super impressive!) - Perhaps drawing a comparison to naive solutions to these sub-problems (like the brute-force inclusion check above) might help clarify the motivation/connection further, including how these things were invented in the first place.
I am proud of supporting this channel. Great work!
This channel is on its way to greatness. Please make more!
Thank you very much, this is so well explained! I've been searching for an intuitive explanation for this topic for a long time and this is more than I ever had hoped for.
Holy crap YOURE AWESOME! I spent soooooo long staring at this algorithm in my company's code base (written by one of our senior engineers) and I was completely confused. This video explains it better than anything I've seen online!
This video is mind blowingly good. I'm messing around with building my own physics engine and this topic came up when I was looking at collision detection and I had no idea where to start. Thank you so much!
Watched this video about 5 times to be able to fully understand it. Great explenation!
What a great watch, amazing explanation of what seemed like such a complex problem.
Great explanation and video. Love the exploration view while solving the problem
Great presentation! 10 years ago I had to come up with my own method when I was designing the HW to do simplex culling on the PowerVR GPU. I wish I had known this method already existed, it would have saved me a few weeks.
before people get too excited, checking if a point is on the right or on the left of line is in on itself a deep subject of computer science. The issue is that if the point is close to the line (there is a smarter way to put it) then computation error might put it on the wrong side of the line. the hand wavy way to put it is "floating point is never really precise, and that's a problem". The more educated way to put it is that there is an unremovable subtraction in the computation, and we can get catastrophic cancellation (which bring immediately the first remedy: you can't represent the result of your subtraction, but you can represent its error, it gets smarter from there).
Your videos are awesome and they help thousands of people and make thousands more interested in CS and programming, don't stop!
Really well produced and explained. Thank you so much for making this!
This is very cool.
Before I always checked if every line segment intersected any other line segment.
Not the fastest at all!
Glad I learned this now.
this approach (with checking line segments intersections) can be made faster using Bentley-Ottmann sweep-line algorithm and it will also work for concave polygons
Man just about to finish a data structures and algorithms class and this has to be the crown jewel on top of it all. What a complex and creative way to solve the problem!
I have had this question in mind for years. It finally get solved after watching this video. Thank you! It will be best if there is other video go through more details about dealing with concave shapes.
This is crazy! I agree with you about the denseness of the original GJK paper: I had a setup I had to use it in, and it took me 3 days to read it and pull everything out of it (and it’s a pretty short paper!). My setup was: Given the space of points (x,y) in [-2,2]^2, find the largest c so that there’s a probability distribution so that 32 explicit expectation equalities hold (E(x)=E(y)=E(x^2-1)=...=E(y^8-14)=0), and its support is on the half-plane x+y>=c. The way I looked at it was to take the possible support space [-2,2]^2 cap {x+y>=c} and look at its image in R^32 under the map (x,y)->(x, y, x^2-1, ..., y^8-14). There being a probability distribution satisfying the equalities means that (0,...0) is in the convex hull of these points.
So I had to use the GJK algorithm to check whether the origin was in this R^32 subset, and basically binary search my way to find the best c (which happens to be approx −2.4763827913319, I am 99.999999% sure is an algebraic number, but I don’t know how to prove it). Along the way, the GJK algorithm gave me at each step either a hyperplane separating the origin from the image, which gives me a polynomial that was positive on the entire region [-2,2]^2 cap {x+y>=c} but negative at the origin, or it gave me 33 points whose convex hull enclosed the origin, and whose probabilities were then easily found with linear algebra. So either way, I had a certificate of proof that the algorithm was working, which doesn’t necessarily always happen.
Anyway, struggling through that made me feel 31:15 in my soul. Great video, I subbed to your channel!
immediately subscribed. This is some really good stuff that's burried , really glad my friend showed me this and now i'll attempt to implement this algorithm into my project!
You are motivating me so much to learn and understand computer science. Thanks for guiding me in that creative and fancy way to at least get an understanding of how this komlex Algorithem is build up.
Your vids are always so interesting. I look forward to each one of them and they really help me understand things.
Not coming from a computer science background it's really good insight and makes me want to go deeper.
However, I never know if I feel stupid at the end because I barely know the concepts you use or cover, or if I should feel smarter at the end because now I know more ( even though I usually don't understand everything X) )
Anyway, keep up the good work, we need more people like you on the internet ;)
This was a really great video! Thanks a lot for making this. Looking forward to the next video :)
Really well explained, good job.. As for the fun math challenge:
k,s are the vertical and horizontal sizes of the ellipse
a = angle * pi / 180.
m = sqrt( (cos(a)/k)^2 + (sin(a)/s)^2 )
x = cos(a)/m
y = sin(a)/m
I'd come across a lot of these terms before they were never explained well and I never quite got them till seeing this. Thankyou.
Great topic, i like how you walked through the steps, building seemingly unrelated topics on top of anther
Very high quality video, comparable to 3b1b. I'm so glad I found your channel, you've earned a sub. Keep up the amazing work!
Nice, I've seen "GJK" a bunch of times in code. I always just looked at the purpose of of it but I never took the opportunity to look into the details of how it works.
Thanks for the engaging video explanation.
I am amazed by the level of quality, wow... Thank you!
This video frustrates me......because of how good it is. I haven't studied mathematics on the level required to understand everything in this video, far from it. Yet it does make sense to me since you explain the concepts very well. Basically what I'm trying to say is that I am impressed by the fact that you made a video someone like me can find absolutely fascinating despite the intersection of its content and my mathematical understanding being somewhere around 5%. Had I not already been super focused on exploring other subjects, a video like this could very well become the reason for years of mathematical studies to come!
The 3Blue1Brown of computer science. I am beginning my PhD in computer science this September and I love this channel!
Thank you for a great tutorial. It's beautiful!!!
Beautiful video! I always strive to gain a complete and deep understanding to such algorithms and this video did just that. You have a new subscriber :-)
i think this is the perfect video on how easy to understand but uncomputable problem (infinite points) can be turned into hyper optimized computable problem
Tipping my hat, appreciating your great contribution intuitively explaining the algorithm
Awesome explanation, thanks! I tried to wrap my head around the GJK during my PHD a couple of years ago, but didn't quite manage to understand it, eventually giving up. Luckily it wasn't crucial for my work and I could simply rely on the freely available SOLID library which has a pretty good 3D GJK implementation.
Beautiful algorithm. Fantastic explanation.
This is really beautiful. All the parts are simple concepts which are easy to grasp, and yet the whole is a result and direction which is astounding that I would not hvae thought of
Well done. Clear easy steps. Thanks.
Great video! Collision arbitrary polygon intersection detection has always been something I've struggled to understand, but you broke it into easily digestible chunks that any undergrad could understand.
Something that you mentioned but never covered is how you break concave polygons into concave polygons. I would love a video explaining that. If I'm not mistaken that would also cover Voronoi triangulation, which is another topic I've never fully understood how to implement
Beautifully imparting wisdom 👏
Wow. The presentation of this video is amazing, and has great references to outside concepts. If I ever become a professor, I will be sure to take a page from your book!
fantastic video, you explained this algorithm very well and the presentation was phenomenal
Quite delightful video, thanks! A *bump* for the algorithm.
I've been on math youtube for 12 years and have never seen this channel!!! 100% instant sub!!! 😍😍😍
This algorithm is **french kiss*.* A work of art.
Amazing explanation. Thank you.
this video is a beautiful gem. thank you.
Hey I love this video. I was just thinking about how to make a Pong game with elliptical paddles and so the dot product direction concept helped me solve the last piece of finding the reflection vector for the ball without having to find the tangent slope of the ellipse
This was beautiful and I learned a ton, thank you!
I recommend that instead of the triple cross product which is opaque and only works in 3D, you simply subtract the parallel component to get the perpendicular one. This is imo simpler and generalizes readily to higher dimensions. In any dimension, the vector component of v perpendicular to unit vector x would be v - (v.x)x where v.x is the dot product of v and x. The vector component of v perpendicular to a plane shared by two perpendicular unit vectors x and y is simply v - (v.x)x - (v.y)y. If x and y are not perpendicular, you can make them so by using y' = y - (x.y)x and then normalize y' to get a unit vector perpendicular to x which lies on the same plane as x and y.
I thought this too, though i wonder (1) if most practical cases only care about 2D/3D, and if so, (2) if there's a shortcut for the triple product that makes it faster to compute than the process you describe (which has a name in linear algebra - the Gram-Schmidt Process).
This topic is from my professional field and I still leared something. Thanks.
Thanks for sharing! Beautiful explanation
Great explanation and demonstration!
Fabulous and very insightful, kudos
So cool. I can hardly wait to try it. There is so much to learn in the world!
Amazing explanation, you know what interesting topics to tackle! keep it up
Beatiful. Thanks for sharing!
Great stuff, and nice work with Manim! 💪
I remember googling for something like this a year ago, but nothing showed up
Thank god it did just now!!
I wish I saw this when I was doing my collision checking assignment lol. Your explanation is just waaaaay better.
For those who don't know what "the furthest point in that direction" means, just like I did originally:
Assume a direction. Rotate the shape and the direction so that the direction points at right. The furthest point in that direction is the rightmost point, i.e. the point with the largest x value.
i'm a little confused, wouldn't point a be the furthest point in that direction if the vector pointed exactly to it?
This is so beautiful. I can't wait to watch your channel grow❤️
priceless reference for computer graphics people. I subscribed, and liked, hoping you get more ranking and income to keep this going.
This is... USEFUL! Applying it now.
Please bring more content like this!
I love these computer science approach with the 3b1b style of visualization
Nice. I have worked last year but this clearity I have not understand yet. Thanks for such beautiful video
Nice description. One place that could be improved is removing the uses of the triple vector product. As several comments point out, the use of the cross product makes it less obvious that the algorithm generalizes to any dimension. It also necessitates adding a third dimension to talk about a completely 2-dimensional concept.
What I would strongly recommend instead is the use of geometric algebra. With that the relevant triple vector product becomes (u /\ v) • v. The operators used here work in any dimension and geometrically don't require introducing 3D vectors when working in 2D. For the purposes of this video, one way of explaining this is that u /\ v behaves like the imaginary number i in the u-v-plane, i.e. it rotates vectors in that plane by 90°. (And scales them if u and v aren't unit vectors, but that doesn't matter here since we only care about the direction.) Assuming the watcher is familiar with this behavior of i, this makes what's happening in the algorithm here completely intuitive. You've probably seen the 3blue1brown videos that explain this e.g. m.th-cam.com/video/mvmuCPvRoWQ/w-d-xo.html, though understanding this behavior from the perspective of geometric algebra would arguably be even more clear.
Assuming you haven't looked much into geometric algebra, m.th-cam.com/video/60z_hpEAtD8/w-d-xo.html gives a decent "pitch" for why it is very much worth learning.
Seems I won't have to mention GA myself since someone already did it for me. Other people subtracted the projection, but (at least in GA) that requires doing a general product anyways (and an inverse). Of course if you're using GA, then you're probably actually doing PGA (or CGA if you're crazy like me) in which case intersection is literally a primitive operation with 1 operator.
Also I knew exactly what video that second link was before clicking it. It's honestly one of my favourite math videos on TH-cam.
Quality of your videos is outstanding. I wish you fast audience growth sir