3 ms·
If you want the closest point between two convex polyhedra, GJK is useful, but it helps to think about the problem differently. You don't really need the Minkow
by Animats 5y ago
If you want the closest point between two convex polyhedra, GJK is useful, but it helps to think about the problem differently. You don't really need the Minkowsky difference, which requires looking at all the points. It's a local hill-climbing problem. You start with a point on each convex polyhedron and walk along the edges to a shorter distance between the points. You still need a simplex, but its geometric interpretation is clearer - it's describing a point-point, point-edge, edge-edge, point-face, edge-face, or face-face closest situation, all of which are possible. So you advance one point of the simplex at a time.
Visualize a small cube sitting just above a big cube for the face-face situation. The closest vertices may be much further apart than the faces.
Performance is O(sqrt(N+M)). And that's from a cold start. In practice, when simulating moving objects, you start the algorithm from the previous solution. If movement is slow relative to the frame time, it usually takes zero or one improvements to get the new closest points. So that's O(1). This is very good performance.
There are some numerical issues. First, you need a convex hull. Which means no coplanar faces. Faces should be flat polygons, not just triangles. Otherwise, you can get stuck on the wrong triangle of a flat face. Of course, polygons are never completely flat in floating point, which creates other problems. A good solution is to require at least a 1 degree break angle at each edge. Convex hull programs can do things like that. This also provides some mesh reduction in case someone puts in something with a huge number of faces.
Second, there's a loss of floating point significance if two faces are nearly parallel. This can cause the algorithm to go into an infinite loop, where the termination condition is not satisfied and the algorithm cycles between similar simplexes. If you're building a physics engine, that's what normally happens when one object comes to rest upon another. So that has to be dealt with.
I used to do ragdoll physics, back in the 1990s.[1] I used the implementation of the late Prof. Stephen Cameron at Oxford, and discovered the "problem in the termination condition" he mentions.[2] I had a somewhat clunky fix, but his was better.
[1] https://www.youtube.com/watch?v=-DaWIHc1VLY https://www.youtube.com/watch?v=-DaWIHc1VLY
[2] https://www.cs.ox.ac.uk/people/stephen.cameron/distances/ https://www.cs.ox.ac.uk/people/stephen.cameron/distances/
- plafl 5y agoI should be writing a thesis about AI but got inside the collision rabbit hole so I have this fresh. From the description of the algorithm you are doing I think you are thinking about Lin-Canny or V-Clip, which certainly may have that kind of numerical error problems. GJK has also numerical problems but they are different. In principle it shouldn't be affected by coplanarity of several faces since you just need the vertex with highest support for a given direction. It could be a problem if you find the support point by hill climbing from vertex to vertex. GJK however does have numerical problems but they are of a different kind related to the degeneracy of the simplices it computes. But you are so right about the subtetly of the problem: there is a very fine thread between infinite looping and incorrect answers. I have been bitten by this trying to implement geometric algos. There should be a special hell for people that output coplanar faces. I know one of Bullet Physics/MuJoCo has the GJK, not remember which one. If anyone is curious I know of two Julia implementations: https://github.com/JuliaRobotics/EnhancedGJK.jl https://github.com/JuliaRobotics/EnhancedGJK.jl and my favorite: https://github.com/arlk/ConvexBodyProximityQueries.jl https://github.com/arlk/ConvexBodyProximityQueries.jl This latter one is great as you are just required to implement the support function and are ready to go. Julia performance is great if you are concerned about using a dynamic language (i.e: ~2us for collision between two convex bodies of 1000 faces each) Finally, about the convex hull computation it looks like some kind of solved problem, I mean, O(n log(n)) for 3D. Wrong!!!! QHull in this regard is fantastic as it has several heuristics to solve problems caused by finite precision, not to mention that I think worse case is O(n^2) as it doesn't implement the asymptotically optimal algo (not sure...). If you scale to more dimensions, which could happen even in if 3D because you transformed your problem to a convex hull problem you will be hit with O(n^2), bad news. There are several other libraries (CCD, LRSLib and more) that allow you to use arbitrary precision but you will get something like a 100x penalization for the luxury.
- Animats 5y agoWhat I used is this.[1] Although I bought a license for the "unscrambled" source version. [1] https://www.cs.ox.ac.uk/stephen.cameron/distances/gjk2.1/ https://www.cs.ox.ac.uk/stephen.cameron/distances/gjk2.1/