Really clever algorithm, beautifully explained!

@josephwalker208

3 жыл бұрын

next coding adventure, maybe?

@ofekn

3 жыл бұрын

nice to see you here

@talonstride

3 жыл бұрын

This is amazing

@younghsiang2509

3 жыл бұрын

@@josephwalker208 Coding avengers, maybe?

@antoninperonnet6138

3 жыл бұрын

I have no idea what these two incredible youtubers could do together, but this would be amazing

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

@prezadent1

3 жыл бұрын

Have you seen Mr Beast reacts to breaking stuff with bowling balls? It's a new level of ugg.

@usualunusualkid7149

3 жыл бұрын

@@prezadent1 What does "ugg" mean?

@prezadent1

3 жыл бұрын

@@usualunusualkid7149 worthless content that gets really popular

@usualunusualkid7149

3 жыл бұрын

@@prezadent1 Makes sense. In order to get popular you have to appeal to big demographics, and one of the biggest demographics is young children.

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

@NinjaOfLU

3 жыл бұрын

That got me laughing, too!

@oximas

3 жыл бұрын

HAHA , he would be all Brown no blues from the amount of rage he would have

@JapanShopBrazil

2 жыл бұрын

Who are the 3bluebrown

@human.earthling

2 жыл бұрын

@@JapanShopBrazil 3blue1brown is another KZread 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.

@47lokeshkumar74

2 жыл бұрын

How can you add these function in game dev

@47lokeshkumar74

2 жыл бұрын

Hi. How can add these function in game dev

@sampletexto2113

2 жыл бұрын

@@47lokeshkumar74 you probably just need the coordinates of each vertex for each body

@windowsxseven

Жыл бұрын

@@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.

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

@elijahbuchanan2368

3 жыл бұрын

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.

@AmitKumar-xw5gp

3 жыл бұрын

Someone should make a GUI for manim.

@xnick99

3 жыл бұрын

@@yonatanbeer3475 Have you downloaded it? It took me

@willjohnson4579

3 жыл бұрын

@@xnick99 what tutorial resources did you use? I've been having trouble getting started with it and have just put it on hold

@xnick99

3 жыл бұрын

@@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.

@_spartan11796

2 жыл бұрын

Your wave analogy was very helpful!

@frontseatastronaut

2 жыл бұрын

Thanks, I was stuck here too! Wave analogy helped

@LuxmasterCZ

2 жыл бұрын

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.

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.

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!!

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.

@Reducible

3 жыл бұрын

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."

@mayabartolabac

3 жыл бұрын

what video is that from?

@elijahbuchanan2368

3 жыл бұрын

@@mayabartolabac idk, one on factorial I think.

@sponge1234ify

3 жыл бұрын

@@mayabartolabac He's right, it's the video on 0!

@mayabartolabac

3 жыл бұрын

@@sponge1234ify haha i watched it

@jrgalyen

3 жыл бұрын

Doesn’t that mean the axiom are changed? Math itself isn’t broken? lol

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.

@FredGlt

Ай бұрын

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)

@startscratching6282

Ай бұрын

@@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

@FredGlt

Ай бұрын

⁠​⁠@@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 :)

@startscratching6282

25 күн бұрын

​@@FredGlt I actually meant cross product in the original comment :))) Sorry for my poor English skills.

@FredGlt

25 күн бұрын

@@startscratching6282 No worries! Good luck with your studies and programming projects :)

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!

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.

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-og6hl6lv7p

7 ай бұрын

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.

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.

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

@elijahbuchanan2368

3 жыл бұрын

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.

@Speykious

3 жыл бұрын

@@elijahbuchanan2368 _I accelerated my brain activity_

@unaiuwu4271

3 жыл бұрын

@@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.

@Reducible

3 жыл бұрын

This might be my favorite comment thread on this channel :) Y'all made me laugh!

@unaiuwu4271

3 жыл бұрын

@@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)

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.

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!

@spyral00

2 жыл бұрын

delaunay triangulation

@animowany111

2 жыл бұрын

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)

@a2e5

2 жыл бұрын

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.)

@drewduncan5774

2 жыл бұрын

@@spyral00 How do you triangulate a circle?

@naturallyinterested7569

2 жыл бұрын

@@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.).

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

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.

@Reducible

3 жыл бұрын

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.

@ToothbrushMan

3 жыл бұрын

@@Reducible You made such a good job with this beautiful algorithm. Congratulations!

@teckleedeyi

2 жыл бұрын

this comment needs to be pinned!

@guydude82

2 жыл бұрын

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.

@guydude82

2 жыл бұрын

@@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 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.

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.

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-bp9fi

3 жыл бұрын

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.

@konstantinkh

3 жыл бұрын

@@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.

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!

Very well done, I like this exploration of high level algorithms that aren't terrible to grasp if presented well.

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

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

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!

@Reducible

3 жыл бұрын

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!

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. :)

@Reducible

3 жыл бұрын

Thanks for the comment about 3d ray tracing, I did not realize that was an application of this algorithm. Pretty cool!

@quillaja

3 жыл бұрын

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.

And he scores again! The use of manim is really impressive! This channel really fills a void in youtube

@angelr.5123

3 жыл бұрын

What is manim?

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 :)

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.

This channel is on its way to greatness. Please make more!

I am proud of supporting this channel. Great work!

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!

Great explanation and video. Love the exploration view while solving the problem

Watched this video about 5 times to be able to fully understand it. Great explenation!

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.

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 ;)

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.

What a great watch, amazing explanation of what seemed like such a complex problem.

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 am amazed by the level of quality, wow... Thank you!

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.

Really well produced and explained. Thank you so much for making this!

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.

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!

Your videos are awesome and they help thousands of people and make thousands more interested in CS and programming, don't stop!

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.

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.

@lycantropos

3 жыл бұрын

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

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!

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

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!

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

Love the content, so glad that Grant referred to this channel!

@danielbenjamin66

2 жыл бұрын

Who is this grant?

@vervok

2 жыл бұрын

@@danielbenjamin66 Look up 3Blue1Brown, amazing math channel. He also made the library (Manin) used in this video for animations.

@danielbenjamin66

2 жыл бұрын

@@vervok thanks man

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.

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!

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

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).

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 :-)

Tipping my hat, appreciating your great contribution intuitively explaining the algorithm

This was a really great video! Thanks a lot for making this. Looking forward to the next video :)

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

brain digestable content!! no rushing.. and also explaining the stuff that other explaining videos would take for granted.

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!

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

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.

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!

I've been on math youtube for 12 years and have never seen this channel!!! 100% instant sub!!! 😍😍😍

fantastic video, you explained this algorithm very well and the presentation was phenomenal

Thank you for a great tutorial. It's beautiful!!!

Well done. Clear easy steps. Thanks.

So cool. I can hardly wait to try it. There is so much to learn in the world!

I wish I saw this when I was doing my collision checking assignment lol. Your explanation is just waaaaay better.

Beautiful algorithm. Fantastic explanation.

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.

@cQunc

Жыл бұрын

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).

Nice. I have worked last year but this clearity I have not understand yet. Thanks for such beautiful video

Quite delightful video, thanks! A *bump* for the algorithm.

Amazing explanation. Thank you.

Thanks for sharing! Beautiful explanation

this video is a beautiful gem. thank you.

I remember googling for something like this a year ago, but nothing showed up Thank god it did just now!!

Great stuff, and nice work with Manim! 💪

Beautifully imparting wisdom 👏

Great explanation and demonstration!

Amazing explanation, you know what interesting topics to tackle! keep it up

thank you for explanation ! I wanted to understand how to find a collision between objects, but I've never searched for that KZreads algorithm showed me this video, KZread knows what I need better than I do xD

This is so beautiful. I can't wait to watch your channel grow❤️

Down to the nitty gritty of underline mechanism used in Elasticsearch to make it fast and Computationally more efficient, triangular tessellations, incredible explaination 👏

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.kzread.info/dash/bejne/n6qh16WJprXVh7Q.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.kzread.info/dash/bejne/aGSuwcqpdaTadJs.html gives a decent "pitch" for why it is very much worth learning.

@angeldude101

2 жыл бұрын

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 KZread.

Quality of your videos is outstanding. I wish you fast audience growth sir

Wonderful explanation and visualization of a beautiful algorithm! The only thing missing is an actual implementation of a support-function for some simple shape.

Brings back memories of struggling to implement the Painter's Algorithm when I was a teenager.

I love these computer science approach with the 3b1b style of visualization

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.

priceless reference for computer graphics people. I subscribed, and liked, hoping you get more ranking and income to keep this going.

Fabulous and very insightful, kudos