ConvexBodyProximityQueries.jl VS GeometricAlgorithms

I 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

and my favorite: 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.

Source code (Processing): https://github.com/volfegan/GeometricAlgorithms/tree/master/Marching_Squares_Coloured_Metaballs

Basically, most collision detection is done with line interception, circles, polygons, etc. So lines are important for games to exist and other interesting space/object interaction. Circle to circle collision is especially easy to do. Geometric Algorithms use a lot of math (books reference on link), but I never went ahead with all its concepts like triangulation Delaunay triangulation, simple non-overlapping Triangulation, etc.

As the circle objects flow, this actually forces their radius to become more homogeneous. Quite boring looking for something I spend a lot of time understanding its inner work. This is one of those things that the static image is better than the animated. It runs slow at this screen size, but as I didn't like the results I don't think I will improve its efficiency by implementing some quadtree or spatial hashing.