Continuous GJK
Continuous GJK
I have been researching how to use GJK for continuous collision detection and I feel like I must be missing something because I don't understand why no implementation simply uses a generalized GJK in 4D to include the time dimension. Instead I can only find adaptations of the 3D GJK. Can anyone shed some light on why that is?

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Continuous GJK
Interesting question. Here is how I see it. Say we have two initially disjoint shapes which move through time. At each moment in time there will be two closest points cp2(t) and cp1(t). We need to track these closest points until the distance becomes zero. Hence:
d(t) = ( cp2(t)  cp1(t) ) * n(t) = 0 (here n is the current contact normal pointing from shape1 towards shape2)
I don't see how a 4d GJK will solve this equation.
Regarding other references Gino wrote about raycasting against the CSO here:
http://dtecta.com/papers/jgt04raycast.pdf
This is a nice optimization for linear conservative advancement by combining the outer CA and inner GJK loop. At Valve my colleague Jay Stelly wrote an algorithm which uses raycasts backwards to get out of the CSO to solve for the TOI. This is similar to Minkowski Portal Refinement (MPR) which Gary Snethen wrote about in Game Programming Gems.
HTH,
Dirk
d(t) = ( cp2(t)  cp1(t) ) * n(t) = 0 (here n is the current contact normal pointing from shape1 towards shape2)
I don't see how a 4d GJK will solve this equation.
Regarding other references Gino wrote about raycasting against the CSO here:
http://dtecta.com/papers/jgt04raycast.pdf
This is a nice optimization for linear conservative advancement by combining the outer CA and inner GJK loop. At Valve my colleague Jay Stelly wrote an algorithm which uses raycasts backwards to get out of the CSO to solve for the TOI. This is similar to Minkowski Portal Refinement (MPR) which Gary Snethen wrote about in Game Programming Gems.
HTH,
Dirk
Re: Continuous GJK
Thanks for the answer! My intuition was that using GJK on 4d objects, built from the combined vertices of 3d objects at times t and t+1, would determine whether a collision occurs within that time interval or not. I can't think of a simple way of getting minimum distance or penetration depth though, so I guess the application of that would be limited to binary searching for finding the collision time?
The advantage of this over simply using the 3D swept volumes is that sometimes swept volumes can intersect when there is really no collision and these false positives would be avoided. Not sure if there's any application where it's worth it, though.
The advantage of this over simply using the 3D swept volumes is that sometimes swept volumes can intersect when there is really no collision and these false positives would be avoided. Not sure if there's any application where it's worth it, though.

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Continuous GJK
You can maybe think of it this way. Say you sweep two spheres. The swept volumes would be capsules. If you compute the overlap of these capsules with GJK it still wouldn't give you the TOI.
CCD is a root finding problem. So I think your intuition for binary searching is good. For linear time of impact (no rotation) using conservative advancement is a simple choice. You can look into Gino's paper I posted earlier for an optimization. For nonlinear time of impact (with rotations) you can look into conservative advancement. I would't use it in practice though as it has a couple of problems which Erin explained and solved in his excellent presentation here:
http://box2d.org/files/GDC2013/ErinCatto_GDC2013.zip
We use this technique in Source 2 and it works great. It is not trivial to extend to 3d due to the nonconvexity of the edgeedge case though.
CCD is a root finding problem. So I think your intuition for binary searching is good. For linear time of impact (no rotation) using conservative advancement is a simple choice. You can look into Gino's paper I posted earlier for an optimization. For nonlinear time of impact (with rotations) you can look into conservative advancement. I would't use it in practice though as it has a couple of problems which Erin explained and solved in his excellent presentation here:
http://box2d.org/files/GDC2013/ErinCatto_GDC2013.zip
We use this technique in Source 2 and it works great. It is not trivial to extend to 3d due to the nonconvexity of the edgeedge case though.
Re: Continuous GJK
Would it be possible to elaborate on what the "nonconvexity" of edgeedge is? After studying Box2D, it seems like an approach could be to form a plane with the normal as Cross( n0, n1 ) where n0 and n1 are the edge directions, and use that as a plane (and a vert from one of the edges) to perform a bilateral advancement.Dirk Gregorius wrote:We use this technique in Source 2 and it works great. It is not trivial to extend to 3d due to the nonconvexity of the edgeedge case though.
Re: Continuous GJK
I'm not enough of a mathematician to figure out what is meant by Dirk there, but in practice it is incredibly difficult to get accurate CCD for the 3D edgeedge case, even if you assume the 4 vertices are linearly moving through space. The normal you speak of often twists around in space between time steps.
Re: Continuous GJK
Yes, the problem is the axis flips. It can flip when the axis goes from penetrating to nonpenetrating, and can also flip as the two vectors rotate relative to one another: https://en.wikipedia.org/wiki/Cross_pro ... roduct.gif