The GJK Algorithm: A weird and beautiful way to do a simple thing
computerwebsite.net
computerwebsite.net
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.
https://www.youtube.com/watch?v=5lHqEwk7YHs
Did the patent expire yet? Would you consider releasing the code? It sounds of historical significance and an interesting doom-like read.
Falling Bodies itself was a plug-in for Softimage, a defunct 3D animation program. It's not very useful without Softimage.
And, of course: Take this with the appropriate amount of salt for a high school sophomore's explanation of anything math related.
I had hoped so, but I can see how it wouldn't come across that way.
I often read HN in the morning after waking up, and these kinds of mistakes in the comments always make me feel like I'm having a stroke.
For the "smooth rounded rectangle" example at the end of the article, what's to stop it from getting closer-and-closer to an answer, but never actually getting there?
I'm talking about idealized mathematical objects, of course. I realize that in real-world computing there's no point continuing beyond some practical precision threshold.
GJK works on convex polyhedra. The "convex" requirement is strict. For example, a cube with tesselated faces is not convex. The two triangles that make up the face of a cube are co-planar, and the edge between them has a zero break angle. This messes up GJK. It's necessary to be able to handle flat polygon faces, not just triangles. That creates a new problem. Polygons are not perfectly flat due to round-off error in floating point. What works is computing a convex hull with a minimum break angle of about 1 degree. That creates geometry GJK can process.
GJK is an example of an algorithm for which there is considerable distance between the naive algorithm that mostly works and the production-quality version that works reliably. Some other algorithms like that include:
- JPEG 2000 decoding. The open source reference implementation is slow and somewhat buggy. There is proprietary code that is faster and works reliably, but it is rather expensive. This is partly why JPEG 2000 never really caught on, outside of medical imagery.
- Mesh simplification. There are two common open source approaches - local triangle merging and quadric mesh simplification. Both can create a big mess if pushed too hard. The metric you really want is that the reduced mesh should look roughly the same as the original when seen from a distance at any angle. Neither of those approaches achieve that. The open source code in Blender works, but the results are disappointing for many cases. Simplygon and Unreal Engine have better approaches, but are proprietary.
- Convex hull decomposition. Given a non-convex mesh, produce a set of disjoint convex meshes which add up to the original. This is a preprocessing step before you can use GJK. Most algorithms for this produce terrible-looking decompositions, with long, skinny triangles. There's something called approximate convex hull decomposition, which relaxes the "disjoint" requirement, allowing some overlap. This results in much simpler sets of convex meshes. There's open source code for this, but it crashes if the input geometry is not absolutely correct, and sometimes when it is.
- Constructive solid geometry. Create a cylinder. Create a thread form. Extrude the thread form along a spiral. Subtract that from the cylinder to get a screw. Chamfer the end. Autodesk Inventor has been able to do that since about 2014, which is what you get for the big bucks. There's some open source code, but historically it hasn't handled the hard cases well. This matters when the next step is cutting the part out of metal.
- Layered clothing for game characters. Create a game character. Set them into an A-pose (arms out, legs apart). Put a rigged mesh shirt on them as a rigged mesh. Resize so that the shirt fits and the body doesn't poke through. Add a coat created by someone else than the one who created the shirt. Resize so the coat fits and the shirt doesn't poke through. Now observe that if the character moves out of A-pose, you probably get some peek-through at shoulders and elbows. Automatically adjust the mesh rigging to fix that. Clo and Marvelous Designer have non-real-time solutions to this, and Roblox has a real-time solution. There's no known open source solution.
Each of these problems is good for years of thesis-level hard work.
In freecad I didn't encounter any issue doing just that. Of course we are 10y later, so maybe things have improved.
I made quite elaborate custom threads for 3D printing this way.
Nice. I'll have to try FreeCAD again.
The epsilon terms are used for breaking ties. If you are deciding if a point is to the right or left of a line, you can use the factors on epsilon terms to decide. If the limit of the point for epsilon close to but greater than 0 is right or left, you use that answer.
You can use multiple epsilon terms, one for each dimension and claim that the x-dimension approaches zero faster than the y or z-dimension, etc. It makes it all work as integer linear algebra with simple greater than or less than on scalar result.
Hope this feedback is helpful.
If there is an intersection, there is at least one pair that consists of the same point twice; the difference of coordinates will be (0,0) and therefore, if there is an intersection then A-B contains the origin.
You have a talent, please keep doing this and who knows maybe one day you will write a fantastic text book.
I thought "as nice as this is already, what's missing from perfect" and here's what I can say:
- add a few comments on worst-case runtime complexity
- separate section about termination
- I always enjoy pseudo-code being part of an explanation. Your explanation comes from a mathematical point of view, which works very well, and which should be kept, but perhaps after each step in the maths explanation you could add a few lines of pseudocode that "capture" how far you got with the algorithm, e.g. define auxiliary functions like S(•).
But again, these are nitpicky extension proposals to make something already great perfect because I love it, not to criticize it.
PS: I also like your write-up about hidden Open AI models (I always check out what else people did whose output impressed me, and that additional time investment is nearly always worth it).
https://winter.dev/articles/gjk-algorithm
This one has an interactive demo near the end that shows Minkowski difference.
https://dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
It was years ago but I remember it was the only good ressource I could find that allowed me to understand how it works.
If checking for an intersection between two convex sets, another method is to solve a convex optimization problem minimizing the norm of the difference between two points, one constrained to be in the first (convex) set and the second constrained to be in the second (convex) set. If the optimal value is zero, then the sets have an intersection.
I'd be curious to see a comparison between the GJK algorithm and using convex optimization. Not sure if either has an advantage over the other.
I think deep learning draws on the same pool of concepts as well.
https://web.archive.org/web/20240612203731/https://computerw...
> And in general how do you get the volume as a single number?
It's not a single number. Imagine a triangle overlapping a square, it's actually a plane, and a depth. To figure that out you use EPA - here's [0] a video explaining it. You project the simplex outwards until it hits the minkowski difference. It's remarkably similar to GJK in implementation. IT's also a pain in the butt to do in a numerically stable way.
[0] https://handmade.network/forums/t/1521-gjk_+_expanding_polyt...
Imagine a bug coming from the ground state design: an object is grounded onto another object, but that other object slowly tilts. The grounded object never slides off, but remains suspended in air.
let Q dot P = 0 which means Q is perpendicular to P
to choose between R = Q or -Q you want R dot (-p) > 0 because -p points from the line containing p and S(-p) toward the origin so you can just dot product again
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.
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.
Type mismatch error: operation ‘+’ can not be applied to values ‘5’ and ‘“sophomore”’School districts in the US almost always start without established middle schools. Instead, there's so much elementary school capacity and so much secondary school capacity in a district. And then, whenever the population of students in the district changes, the choices of the district school board to respond to that are either to:
1. build one additional elementary school for every N additional grade 1-7 students, and/or one additional secondary school for every M additional grade 8-12 students (and continue to pay these CapEx costs even if student population goes down; and agree to deal with the fact that growth in elementary students will inevitably propagate to growth in secondary students 7 years later);
2. add temporary capacity to existing elementary + secondary schools with portable classrooms (which can easily be reduced back down if populations decrease — but which don't come with commensurate increases in central infrastructure, eventually straining the capacity of school facilities);
3. or, at one point, you look at the numbers of students in each year in your district, treat the years as vnodes, and then rebalance a contiguous set of those vnodes to a new "shard" called "middle schools". I.e. you pick a set of school-years, where extracting students from that set of years from one or two elementary and secondary schools in the district into a newly-built middle school, will result in a "good" amount of capacity being freed from those schools, and the resulting middle school instantly having a "good" utilization.
Once you've chosen option 3 one time, it sets a precedent in that district for what years middle school should cover in that district. Most districts only do the study for what years would be best to extract out the first time they build a middle school. After that, they just go with what they did before, even if it's no longer optimal (because skipping the study saves time and money.)
In theory, school districts could actually build successive middle schools that "pull" different years of utilization out of the elementary+secondary schools around them than previously-built middle schools have. The only issue would be in administrative assignment of students to schools — this would require you to place middle schools with different year coverage so they never have overlapping catchment area.