I have no idea what these two incredible youtubers could do together, but this would be amazing
@altervoid32353 жыл бұрын
i smashed my keyboard because i want to learn something and whatever pops up ill learn that, and this guy pop up
@MeshMachine3 жыл бұрын
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.
@47lokeshkumar742 жыл бұрын
How can you add these function in game dev
@47lokeshkumar742 жыл бұрын
Hi. How can add these function in game dev
@sampletexto21132 жыл бұрын
@@47lokeshkumar74 you probably just need the coordinates of each vertex for each body
@windowsxseven2 жыл бұрын
@@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
@deliciousnoodles5505 Жыл бұрын
Had to implement this in 3D too and pulled chunks of hair out in the process.
@NovaWarrior773 жыл бұрын
I live for the day that these are on trending. I really do.
@prezadent13 жыл бұрын
Have you seen Mr Beast reacts to breaking stuff with bowling balls? It's a new level of ugg.
@usualunusualkid71493 жыл бұрын
@@prezadent1 What does "ugg" mean?
@prezadent13 жыл бұрын
@@usualunusualkid7149 worthless content that gets really popular
@usualunusualkid71493 жыл бұрын
@@prezadent1 Makes sense. In order to get popular you have to appeal to big demographics, and one of the biggest demographics is young children.
@mikemullen55633 жыл бұрын
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.
@Reducible3 жыл бұрын
That is an awesome tidbit, thanks for sharing!
@eshh1833 жыл бұрын
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!!
@zemaumm2 жыл бұрын
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.
@fredoo66273 жыл бұрын
Manim should be used by every math teacher. It's so beautiful.
@elijahbuchanan23683 жыл бұрын
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.
@AK56fire3 жыл бұрын
Someone should make a GUI for manim.
@tnick000013 жыл бұрын
@@yonatanbeer3475 Have you downloaded it? It took me
@willjohnson45793 жыл бұрын
@@tnick00001 what tutorial resources did you use? I've been having trouble getting started with it and have just put it on hold
@tnick000013 жыл бұрын
@@willjohnson4579 I downloaded examples from github and used some of the github tutorials
@elijahbuchanan23683 жыл бұрын
9:30 makes me think of a great line from numberphile. "You've broken maths, Brady, stop that."
@mayabartolabac3 жыл бұрын
what video is that from?
@elijahbuchanan23683 жыл бұрын
@@mayabartolabac idk, one on factorial I think.
@sponge1234ify3 жыл бұрын
@@mayabartolabac He's right, it's the video on 0!
@mayabartolabac3 жыл бұрын
@@sponge1234ify haha i watched it
@jrgalyen3 жыл бұрын
Doesn’t that mean the axiom are changed? Math itself isn’t broken? lol
@kenthedawg63833 жыл бұрын
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!
@startscratching628211 ай бұрын
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.
@FredGlt4 ай бұрын
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)
@startscratching62824 ай бұрын
@@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
@FredGlt4 ай бұрын
@@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 :)
@startscratching62824 ай бұрын
@@FredGlt I actually meant cross product in the original comment :))) Sorry for my poor English skills.
@FredGlt4 ай бұрын
@@startscratching6282 No worries! Good luck with your studies and programming projects :)
@kattenelvis17783 жыл бұрын
HAHAHAHAHAA I love the bit when you say that if I find a counter-example 3blue1brown would be after me
@NinjaOfLU3 жыл бұрын
That got me laughing, too!
@oximas3 жыл бұрын
HAHA , he would be all Brown no blues from the amount of rage he would have
@JapanShopBrazil3 жыл бұрын
Who are the 3bluebrown
@human.earthling3 жыл бұрын
@@JapanShopBrazil 3blue1brown is another KZbin channel with similar a very explanation style and animations. Both this one and that one are excellent.
@gormster3 жыл бұрын
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.
@_spartan117962 жыл бұрын
Your wave analogy was very helpful!
@frontseatastronaut2 жыл бұрын
Thanks, I was stuck here too! Wave analogy helped
@LuxmasterCZ2 жыл бұрын
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.
@Zimbleton2 жыл бұрын
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.
@user-og6hl6lv7p10 ай бұрын
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.
@thedoublehelix56613 жыл бұрын
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.
@Speykious3 жыл бұрын
Wow... This is... Beautiful... I've looked at it for 5 hours now
@elijahbuchanan23683 жыл бұрын
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.
@Speykious3 жыл бұрын
@@elijahbuchanan2368 _I accelerated my brain activity_
@unaiuwu42713 жыл бұрын
@@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.
@Reducible3 жыл бұрын
This might be my favorite comment thread on this channel :) Y'all made me laugh!
@unaiuwu42713 жыл бұрын
@@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)
@paulomag21063 жыл бұрын
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.
@Waffle45692 жыл бұрын
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.
@walker-snow Жыл бұрын
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.
@Waffle4569 Жыл бұрын
@@walker-snow sometimes its done in combination with that, to avoid jittering that would otherwise be more apparent
@LouSaydus Жыл бұрын
@@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.
@ToothbrushMan3 жыл бұрын
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.
@Reducible3 жыл бұрын
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.
@ToothbrushMan3 жыл бұрын
@@Reducible You made such a good job with this beautiful algorithm. Congratulations!
@teckleedeyi3 жыл бұрын
this comment needs to be pinned!
@guydude822 жыл бұрын
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.
@guydude822 жыл бұрын
@@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.
@konstantinkh3 жыл бұрын
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.
@AB-bp9fi3 жыл бұрын
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.
@konstantinkh3 жыл бұрын
@@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.
@jursamaj3 жыл бұрын
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.
@brianlittle9816 Жыл бұрын
I was thinking the same thing. If the goal is to just check for overlap
@arpyzero3 жыл бұрын
Very well done, I like this exploration of high level algorithms that aren't terrible to grasp if presented well.
@kika4333 жыл бұрын
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!
@Reducible3 жыл бұрын
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!
@rubenferreira18883 жыл бұрын
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
@petergilliam40053 жыл бұрын
And he scores again! The use of manim is really impressive! This channel really fills a void in youtube
@angelr.51233 жыл бұрын
What is manim?
@codytapscott893 жыл бұрын
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.
@sergeboisse3 жыл бұрын
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!
@pdjinne652 жыл бұрын
delaunay triangulation
@animowany1112 жыл бұрын
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)
@a2e52 жыл бұрын
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.)
@drewduncan57742 жыл бұрын
@@pdjinne65 How do you triangulate a circle?
@naturallyinterested75692 жыл бұрын
@@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.).
@tdc22a3 жыл бұрын
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. :)
@Reducible3 жыл бұрын
Thanks for the comment about 3d ray tracing, I did not realize that was an application of this algorithm. Pretty cool!
@quillaja3 жыл бұрын
I'll definitely store this nugget away for later. =)
@simondemeule39343 жыл бұрын
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.
@qu7653 жыл бұрын
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.
@lycantropos3 жыл бұрын
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
@Stelios.Posantzis3 жыл бұрын
This is a great introduction into convex sets and their geometrical properties that also touches upon other areas, both inspirational and intuitive.
@vervok3 жыл бұрын
Love the content, so glad that Grant referred to this channel!
@danielbenjamin663 жыл бұрын
Who is this grant?
@vervok3 жыл бұрын
@@danielbenjamin66 Look up 3Blue1Brown, amazing math channel. He also made the library (Manin) used in this video for animations.
@danielbenjamin663 жыл бұрын
@@vervok thanks man
@dorcsyful2 жыл бұрын
Watched this video about 5 times to be able to fully understand it. Great explenation!
@givememypackage63 жыл бұрын
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
@prahjex25013 жыл бұрын
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!
@juliogodel3 жыл бұрын
Great explanation and video. Love the exploration view while solving the problem
@TheHamoodz3 жыл бұрын
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!
@skejeton2 жыл бұрын
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
@mastershooter643 жыл бұрын
Your videos are awesome and they help thousands of people and make thousands more interested in CS and programming, don't stop!
@losjx2 жыл бұрын
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.
@nimcapcik2 жыл бұрын
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 :)
@6183613 жыл бұрын
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.
@cQunc2 жыл бұрын
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).
@narcopolo44642 жыл бұрын
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!
@noahtaul3 жыл бұрын
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!
@teckleedeyi3 жыл бұрын
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!
@fordred3 жыл бұрын
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.
@WaxyLT2 жыл бұрын
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!
@sammitchell63223 жыл бұрын
The 3Blue1Brown of computer science. I am beginning my PhD in computer science this September and I love this channel!
@47lokeshkumar743 жыл бұрын
Nice. I have worked last year but this clearity I have not understand yet. Thanks for such beautiful video
@nraynaud3 жыл бұрын
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).
@jakobthomsen159510 ай бұрын
Wonderful explanation and visualization of a beautiful algorithm! The only thing missing is an actual implementation of a support-function for some simple shape.
@user-eh5zk5bb9k2 жыл бұрын
I am amazed by the level of quality, wow... Thank you!
@CameronOwen1013 жыл бұрын
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.
@NonTwinBrothers3 жыл бұрын
I remember googling for something like this a year ago, but nothing showed up Thank god it did just now!!
@mrinmoybanik55983 жыл бұрын
Manim library is great!But I still give the honour to the most elegant algorithm to DFT.In GJK most things are predictable after knowing the Minkawaski sum and that direction search.Rest are borrowed from vector algebra.
@Reducible3 жыл бұрын
Can't argue with you there, the DFT/FFT has always been my favorite algorithm but GJK is up there as well.
@aloysiuskurnia76433 жыл бұрын
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.
@riana59972 жыл бұрын
i'm a little confused, wouldn't point a be the furthest point in that direction if the vector pointed exactly to it?
@alexismandelias3 жыл бұрын
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!
@koopa10183 жыл бұрын
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.
@TheSentientCloud2 жыл бұрын
I've been on math youtube for 12 years and have never seen this channel!!! 100% instant sub!!! 😍😍😍
@KirbzXXX3 жыл бұрын
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!
@wiiasd36822 жыл бұрын
I wish I saw this when I was doing my collision checking assignment lol. Your explanation is just waaaaay better.
@derekelkins63172 жыл бұрын
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.kzbin.info/www/bejne/o6fQpnaGq7eijbM, 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.kzbin.info/www/bejne/bGHdkJumeqanepo gives a decent "pitch" for why it is very much worth learning.
@angeldude1012 жыл бұрын
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 KZbin.
@TheMRJewfro3 жыл бұрын
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
@thewiirocks Жыл бұрын
Brings back memories of struggling to implement the Painter's Algorithm when I was a teenager.
@BatBallBites2 жыл бұрын
Down to the nitty gritty of underline mechanism used in Elasticsearch to make it fast and Computationally more efficient, triangular tessellations, incredible explaination 👏
@helgefan89942 жыл бұрын
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.
@matt.jordan3 жыл бұрын
Oh my god this is literally one of the best math videos I’ve ever seen on KZbin good shit!!!!!
@desine_ Жыл бұрын
thank you for explanation ! I wanted to understand how to find a collision between objects, but I've never searched for that KZbins algorithm showed me this video, KZbin knows what I need better than I do xD
@nikilragav3 жыл бұрын
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
@null-000002 жыл бұрын
I love these computer science approach with the 3b1b style of visualization
@tommydrager5497 Жыл бұрын
brain digestable content!! no rushing.. and also explaining the stuff that other explaining videos would take for granted.
@brockobama257 Жыл бұрын
Congratulation! You just earned the 3Blue1Brown award for Computer Science! Which means you're not as goatee but your video quality surpasses all expectations, has breadth, and is extremely clear for fumbasses like me!
@Sollace2 жыл бұрын
This algorithm is **french kiss*.* A work of art.
@bubsztyn3 жыл бұрын
Quality of your videos is outstanding. I wish you fast audience growth sir
@macgyverswissarmykni3 жыл бұрын
The video I wish I had discovered a year ago, solves several problems I've ignorantly wrestled with.
@justkeerat3 жыл бұрын
This is so beautiful. I can't wait to watch your channel grow❤️
@SimonvandenBroek-zl5jpАй бұрын
First time I skimmed by your video I was like. nope... not going that way. SAT will do Just fine. Then after implementing the SAT I grew curious about the GJK and actually started watching your video from the start. I have to say you explain extremely well! I understood it in 1 go. Now about to implement it. super epic!
@andreaquek96373 жыл бұрын
This channel is on its way to greatness. Please make more!
@IridescentBob3 жыл бұрын
Great topic, i like how you walked through the steps, building seemingly unrelated topics on top of anther
@arseneferriere51512 жыл бұрын
Thank you for this very clear video. I didn't know anything about this topic and it encourages me to dig deeper into this topic. There are however two things that I don't understand in your video. These things are about the stoping conditions of the algorithm. 1. I don't get where in your code you decide to stop the loop. I assume it is the condition dot(A,d)
@dravorek3 жыл бұрын
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.
@luchong38812 жыл бұрын
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.
@timothytyree52112 жыл бұрын
I dig your diction. Simplicity provides inference.
@MineRoyale.3 жыл бұрын
My immediate thoughts were about lines from opposing vertices, and I'm pleasantly surprised that that was how we started this video off.
@jimparsons68032 жыл бұрын
Liked the clip on topology. I was into topology when I took my BS back when, as this approach was the easiest for some sorts of engineering problems. As time rolled on, the maths behind these problems took on a life of their own and presented solutions to newer difficulties that hadn't yet occurred to a newly minted plebe, in a manner of speaking, still very wet behind the ears.
@andyl99003 жыл бұрын
this channel has great potential! please make more DS&A videos
@Moonjay07143 жыл бұрын
Just discovered your channel and you are soooo underrated. Hell, you got people like Sebastian Lague here. Came here from the FFT video, and now I'm looking all the other cool stuff you're doing. Keep up the good work man. Will you do the SoME1 from 3b1b?
@Reducible3 жыл бұрын
Hey thanks for the comment! On SoME1, the truth is it takes me so long to make one of these videos, I'm pretty sure I could never make the deadline, even if I wanted to be part of it. I work full time so there's literally just not enough hours in the day (if I want to have a life haha). I think also one part of SoME1 is to highlight voices that haven't been heard in the math/CS education space, and honestly I feel like my channel has grown a ridiculous amount from Grant's gracious shoutouts.
@Magnasium0382 жыл бұрын
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
@limackthrejjal13583 жыл бұрын
For anyone not understanding "furthest point in a direction" as well: I think it means the following: take a plane with the direction as the normal and move it away from your starting point (usually the origin) until the last time it contains a point from the shape. That point is the furthest point in the direction and doesn't have to lie directly in the direction. Basically the furthest is meant with reference to the projection on the direction, not only the distance of points lying on a line in the direction.
@nolanfaught69743 жыл бұрын
This is exactly what it means. If you study convex analysis you define the projection onto a convex set as the closest point in the set to the point of interest. The plane you refer to creates a partition in the d-dimensional space known as a half space, which is a convex set containing every element x whose dot product with the normal of the plane is either nonnegative or nonpositive. The "closest point" spoken of is simply the convex projection onto this half space
@cookiemonster09653 жыл бұрын
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.
@thisismyname21853 жыл бұрын
This is amazing, I don't understand the maths, but I understand the concept, its just neat
@XORBob7 ай бұрын
So cool. I can hardly wait to try it. There is so much to learn in the world!
@fominvic813 жыл бұрын
Thank you for a great tutorial. It's beautiful!!!
@Narutoninjaqiu2 жыл бұрын
Really well produced and explained. Thank you so much for making this!
@guac61333 жыл бұрын
What a great watch, amazing explanation of what seemed like such a complex problem.
@Xxnightwalk12 жыл бұрын
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 ;)
@Piols3 жыл бұрын
Tipping my hat, appreciating your great contribution intuitively explaining the algorithm
@ahr2g63 жыл бұрын
This topic is from my professional field and I still leared something. Thanks.
@baptistedemontangon82243 жыл бұрын
I love the fact that this is not computionally heavy, these are just small vectors calculations and most of the times the solution is found in the firsts iterations
@meanmole32123 жыл бұрын
Tell me if this is correct: at 17:57 visualize a vector from origin to point A, which I call here OA^. Now compare the angle between vectors d^ and OA^. If the angle is more than 90 degrees, the point A does not pass origin. If the angle is less than 90 degrees, point A passes origin. In other words, the dot product between OA^ and d^ is either positive or negative as stated in the video. A visualization to emphasize this would have been a nice helpful addition but I guess it's self-explanatory enough as it is.