GJK: Collision detection algorithm in 2D/3D(blog.winter.dev)
blog.winter.dev
GJK: Collision detection algorithm in 2D/3D
https://blog.winter.dev/2020/gjk-algorithm/
30 comments
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.
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.
What 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/
[1] https://www.cs.ox.ac.uk/stephen.cameron/distances/gjk2.1/
Another perspective for understanding GJK, one that I have not yet seen thoroughly explained, is that it's a special case of a convex quadratic program: find two points, each constrained to a respective polyhedron (e.g. intersection of halfspaces), with minimum distance between them. The constraints are linear inequalities, and the objective is convex quadratic.
I'm more interested in the shape that defines the set of points where there is no collision.
Reducible's introduction to GJK [1] is also really great.
[1] https://www.youtube.com/watch?v=ajv46BSqcK4
[1] https://www.youtube.com/watch?v=ajv46BSqcK4
Yep! I saw it and stumbled upon this pretty blog post.
Misread the headline, thought this was a way for identifying when @pc was in a thread.
I don't understand what you mean
They made an inside joke outside. Innocent mistake, harmless except that HN sometimes punishes attempted humor.
"HN sometimes punishes attempted humor"
I've felt like that a few times!
Learned to try and be a bit more dry around here ... Humor is not necessarily a strong suit of mine, anyway :-)
I've felt like that a few times!
Learned to try and be a bit more dry around here ... Humor is not necessarily a strong suit of mine, anyway :-)
Shame on me for not realizing the joke about HN on HN would be seen as outside :shrug:
pc = Stripe cofounder Patrick Collison's username
A similar, but IMO easier to understand and implement algorithm is Xenocollide: http://xenocollide.snethen.com/
I'm implementing this right now.
Trying to figure out a way to render the support functions to assist with debugging my implementation. At the moment I just sample the function in various directions around a unit sphere and try build a mesh from that. Too patchy.
Trying to figure out a way to render the support functions to assist with debugging my implementation. At the moment I just sample the function in various directions around a unit sphere and try build a mesh from that. Too patchy.
Another nice thing about this one is that in the case where the objects intersect, you can just keep iterating mostly the same algorithm to get the intersection points, rather than needing to use Expanding Polytope as with GJK.
I'm in the process of learning about GJK but Vatti's clipping algorithm [0] is a way to polynomially do Boolean operations on arbitrary 2d polygons (convex, concave, etc.). From Boolean operations, you can get collision detection.
Angus Johnson's ClipperLib [1] is a library that implements this in C++ and other languages and there are Javascript ports available [2] [3].
[0] https://en.wikipedia.org/wiki/Vatti_clipping_algorithm
[1] http://www.angusj.com/delphi/clipper.php
[2] https://github.com/junmer/clipper-lib
[3] http://jsclipper.sourceforge.net/6.2.1.0/main_demo.html
Angus Johnson's ClipperLib [1] is a library that implements this in C++ and other languages and there are Javascript ports available [2] [3].
[0] https://en.wikipedia.org/wiki/Vatti_clipping_algorithm
[1] http://www.angusj.com/delphi/clipper.php
[2] https://github.com/junmer/clipper-lib
[3] http://jsclipper.sourceforge.net/6.2.1.0/main_demo.html
I implemented GJK years ago based on a nice presentation by Casey Muratori: https://www.youtube.com/watch?v=Qupqu1xe7Io
This is the explanation that made it click for me, although in my experience it seems like he's wrong about being able to rule out the need for doing certain checks when you already "know" the origin is not in that section due to how you got to where you are. Not sure if my implementation was just shitty, but you'll get weird results when objects are very close if you don't exhaustively check every sector - probably due to numerical imprecision, if I had to guess.
GJK handles closest points (and distance, separating axis) between two non-overlapping convex shapes. Once convex shapes penetrate, you can use EPA, the Expanding Polytope Algorithm, invented Gino van den Bergen (while we were working together at NaN/Blender, around 20 years ago). See also http://dtecta.com/publications and check out this recent implementation in C++ for both GJK and EPA is in Jolt Physics (used in the game Horizon Forbidden West): https://github.com/jrouwe/JoltPhysics/tree/master/Jolt/Geome...
Nice, I didn't know about Jolt.
A good book also is "Real Time Collision Detection" (Christer Ericson).
A good book also is "Real Time Collision Detection" (Christer Ericson).
In the context of a game engine, when you have fast moving objects, and your collision detection only runs a few times each second, how do you detect if objects should have collided, if the fast moving object fully passes through another, between each tick?
As the other comments note, you can create a sweep form to detect penetration. But this belies the more thorny issues of achieving a "high quality" solution: if two things impact a third within the exact same time step, you have to come up with a globally satisfying solution that coordinates all three, and sweeping doesn't do that by itself, it just says "well at some time it might hit one or both of them" - which if you run with directly, leads to weird behaviors related to the information loss where objects squeeze past each other or gain excess energy or trigger events they shouldn't. The solution to that problem is generally handled through the solver by various iterative methods. In a 2D platforming game using AABBs this is as simple as "step the physics on Y axis, then step them on X axis" - which completely eliminates the possibility of hitting two things at once, albeit it makes corners "sticky" on one axis. Once you have things rotating and colliding at any angle it gets a lot harder and the focus then is on how to iterate approximately in a way that produces the least error. (If you can afford it, backtracking the solver to optimize the solution quality to some metric of fewest/smallest impacts is one way to create satisfying interactions).
This is actually a fairly common problem in game development! There are two largely used solutions:
1. Don't have fast moving objects
2. Use "continuous" collision detection.
Option 2 is more interesting. Continuous collision detection is, in essence, "looking ahead" at where an object is going and seeing if there are any potential collisions (typically using a bounding box or simplified geometry to save on CPU power). If there are no potential collisions, all is well, and if there is a potential collision we can then calculate its outcome.
Option 2 is more interesting. Continuous collision detection is, in essence, "looking ahead" at where an object is going and seeing if there are any potential collisions (typically using a bounding box or simplified geometry to save on CPU power). If there are no potential collisions, all is well, and if there is a potential collision we can then calculate its outcome.
One option is to not worry about it so speedrunners can have a bit of extra fun breaking the game.
It's a feature, not a bug!
It's a feature, not a bug!
The usual approach is some form of sweep to get a time of impact. Once you've got a time of impact, you can either generate contacts, or avoid integrating the involved bodies beyond the time of impact, or do something fancier like adaptively stepping the simulation to ensure no lost time.
If the details don't matter much, it's common to use a simple ray cast from the center at t0 to the center at t1. Works reasonably well for fast moving objects that are at least kinda-sorta rotationally invariant. For two dynamic bodies flying at each other, you can test this "movement ray" of body A against the geometry of body B, and the movement ray of body B against the geometry of body A.
One step up would be to use sphere sweeps. Sphere sweeps tend to be pretty fast; they're often only slightly more complicated than a ray test. Pick a sphere radius such that it mostly fills up the shape and then do the same thing as in the previous ray case.
If you need more detail, you can use a linear sweep. A linear sweep ignores angular velocity but uses the full shape for testing. Notably, you can use a variant of GJK (or MPR, for that matter) for this: http://dtecta.com/papers/jgt04raycast.pdf
If you want to include angular motion, things get trickier. One pretty brute forceish approach is to use conservative advancement based on distance queries. Based on the velocity and shape properties, you can estimate the maximum approaching velocity between two bodies, query the distance between the bodies (using algorithms like GJK or whatever else), and then step forward in time by distance / maximumApproachingVelocity. With appropriately conservative velocity estimates, this guarantees the body will never miss a collision, but it can also cause very high iteration counts in corner cases.
You can move a lot faster if you allow the search to look forward a bit beyond potential impact times, turning it into more of a root finding operation. Something like this: https://box2d.org/files/ErinCatto_ContinuousCollision_GDC201...
I use a combination of speculative contacts and then linear+angular sweeps where needed to avoid ghost collisions. Speculative contacts can handle many forms of high velocity use cases without sweeps- contact generation just has to be able to output reasonable negative depth (separated) contacts. The solver handles the rest. The sweeps use a sorta-kinda rootfinder like the Erin Catto presentation above, backed up by vectorized sampling of distance. A bit more here, though it's mainly written for users of the library: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
If the details don't matter much, it's common to use a simple ray cast from the center at t0 to the center at t1. Works reasonably well for fast moving objects that are at least kinda-sorta rotationally invariant. For two dynamic bodies flying at each other, you can test this "movement ray" of body A against the geometry of body B, and the movement ray of body B against the geometry of body A.
One step up would be to use sphere sweeps. Sphere sweeps tend to be pretty fast; they're often only slightly more complicated than a ray test. Pick a sphere radius such that it mostly fills up the shape and then do the same thing as in the previous ray case.
If you need more detail, you can use a linear sweep. A linear sweep ignores angular velocity but uses the full shape for testing. Notably, you can use a variant of GJK (or MPR, for that matter) for this: http://dtecta.com/papers/jgt04raycast.pdf
If you want to include angular motion, things get trickier. One pretty brute forceish approach is to use conservative advancement based on distance queries. Based on the velocity and shape properties, you can estimate the maximum approaching velocity between two bodies, query the distance between the bodies (using algorithms like GJK or whatever else), and then step forward in time by distance / maximumApproachingVelocity. With appropriately conservative velocity estimates, this guarantees the body will never miss a collision, but it can also cause very high iteration counts in corner cases.
You can move a lot faster if you allow the search to look forward a bit beyond potential impact times, turning it into more of a root finding operation. Something like this: https://box2d.org/files/ErinCatto_ContinuousCollision_GDC201...
I use a combination of speculative contacts and then linear+angular sweeps where needed to avoid ghost collisions. Speculative contacts can handle many forms of high velocity use cases without sweeps- contact generation just has to be able to output reasonable negative depth (separated) contacts. The solver handles the rest. The sweeps use a sorta-kinda rootfinder like the Erin Catto presentation above, backed up by vectorized sampling of distance. A bit more here, though it's mainly written for users of the library: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
In games the fastest moving object is bullets, so model them as lines, not points.
Is GJK a suitable algorithm for preventing collisions of 2D text being randomly placed in a canvas at random angles?
I’m assuming the bounding boxes of the text would provide the vertices.
Is there anything better?
I’m assuming the bounding boxes of the text would provide the vertices.
Is there anything better?
You can use GJK for 2D also. You don't need to compute the bounding boxes as GJK will automatically "convexify" the body although if you "precompute" the bounding boxes it will be better. You just need to compute the support function in an arbitrary direction.
If you want to use bounding boxes then you can do it faster using the separating axis theorem.
If you want to use bounding boxes then you can do it faster using the separating axis theorem.
GJK is more than just collision detection. If you really just need to detect collisions, there are usually much simpler ways to do it.
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
[2] https://www.cs.ox.ac.uk/people/stephen.cameron/distances/