[HN Gopher] The GJK Algorithm: A weird and beautiful way to do a...
___________________________________________________________________
The GJK Algorithm: A weird and beautiful way to do a simple thing
Author : arithmoquine
Score : 156 points
Date : 2024-06-12 17:35 UTC (5 hours ago)
(HTM) web link (computerwebsite.net)
(TXT) w3m dump (computerwebsite.net)
| arithmoquine wrote:
| I couldn't find any written explanation of the GJK collision
| detection algorithm which gave good intuition for it, so I spent
| an afternoon writing one up. Let me know of any ways I could make
| it more clear & efficient.
|
| And, of course: Take this with the appropriate amount of salt for
| a high school sophomore's explanation of anything math related.
| rayiner wrote:
| This is great!
| gfaure wrote:
| A video presentation of the same algorithm:
| https://www.youtube.com/watch?v=ajv46BSqcK4
| omoikane wrote:
| See also:
|
| https://winter.dev/articles/gjk-algorithm
|
| This one has an interactive demo near the end that shows
| Minkowski difference.
| Animats wrote:
| I spent about a year struggling with GJK back in the 1990s.
|
| It's useful for collision detection in 3D, and it can also be
| used as a closest-points algorithm. As a closest-points
| algorithm, it's easy to understand the basics. You have two
| convex solids. Start with a random point on each, and get the
| distance between those points. On each solid, try to improve the
| distance by advancing along each edge from the current point.
| Pick the new closest point. Repeat.
|
| This stops working when the closest point is no longer a vertex.
| That's when the "simplex" concept is needed. The closest points
| can be vertex-vertex, vertex-edge, vertex-face, edge-edge, edge-
| face (no unique solution) and face-face (no unique solution). The
| simplex thing is really doing a case analysis of those cases.
|
| Lots of things go wrong in practice. If you are doing a physics
| engine, objects will often settle into face-face contact. A
| single-point collision model will then result in vibration or
| incorrect movement. Also, as positions settle into face-face
| contact, the GJK algorithm runs into a small difference of large
| values problem that can result in a complete loss of floating
| point significance. The termination condition can also cause
| infinite looping.
|
| In theory, this is an elegant solution, but it's a difficult
| numerical analysis problem. Despite that, it's probably the
| fastest approach to the problem. It's O(log N) in normal cases,
| and O(1) for situations where the positions are closest to the
| previous positions and you use the last solution as the starting
| point.
|
| The late Prof. Steven Cameron at Oxford did a lot of work on
| getting GJK right. I used GJK in "Falling Bodies", the first
| commercial 3D ragdoll system, in the late 1990s.
| maccard wrote:
| Couldn't agree more. One thing to note is that once you have
| that contact, you almost certainly want to do something with
| it. In most cases doing something useful involves knowing the
| actual overlap information. Working that out is actually
| _worse_ numerically - you start with the simplex that GJK
| generates and expand out the way, and do triangle subdivision
| along the way. It's a total nightmare to do performantly.
| unholiness wrote:
| > There's probably a few things incorrect with what I said. So,
| take it with the appropriate amount of salt for a high school
| sophomore's explanation of anything math related.
|
| A high school sophomore! I'm thoroughly impressed, not just by
| the clarity of this explanation, but by the tone, showing
| appreciation for where and how the elegance pops up, and empathy
| for a reader who's never heard of these concepts. Throw in the
| minimal web design I was sure I was reading some graybeard.
|
| Excellent writing, you should be proud of this.
| OJFord wrote:
| > high school sophomore
|
| For the rest of us (and because I've previously heard that in
| films etc. about university students and never really known
| exactly what it meant except that it's one of the years) that's
| the second year of high school, which in a middle-school-having
| system (as is the norm in the US) is year 10, which in the US
| is two years (not three as it would be in the UK for example)
| of high school away from university.
|
| Just a bit of a tangent to understand. Impressive indeed.
| 63 wrote:
| For reference, the expected age would be ~15 years old
| IncreasePosts wrote:
| An easy rule of thumb for US grade-level ages is 5 + grade
| level = age of students in that grade
| jameshart wrote:
| Type mismatch error: operation '+' can not be applied to
| values '5' and '"sophomore"'
| rdevsrex wrote:
| This was a great writeup. I've never heard of the GJK algorithm
| before.
| arithmoquine wrote:
| Now that this is unexpectedly getting more attention, I should
| probably mention that my personal website is basically an
| elaborate set of in-jokes. Let me know via a reply if you're
| interested in contacting me or anything!
| JackYoustra wrote:
| I'd be interested!
| pjs_ wrote:
| Bad boy algorithm. Amazing algorithm
| ryankrage77 wrote:
| I've been using the Minkowski function in openSCAD for a while
| now, it's nice to know what it actually is.
| tehsauce wrote:
| Awesome article! Something slightly misleading though - the first
| image shows the intersection of a non-convex shape, but it isn't
| revealed until much later that the algorithm only works for
| convex shapes, not the type shown in the first image.
___________________________________________________________________
(page generated 2024-06-12 23:00 UTC)