Continuous GJK

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
boble
Posts: 2
Joined: Wed Mar 22, 2017 4:25 pm

Continuous GJK

Post by boble »

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?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Continuous GJK

Post by Dirk Gregorius »

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
boble
Posts: 2
Joined: Wed Mar 22, 2017 4:25 pm

Re: Continuous GJK

Post by boble »

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.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Continuous GJK

Post by Dirk Gregorius »

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 non-linear 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 non-convexity of the edge-edge case though.
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: Continuous GJK

Post by RandyGaul »

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 non-convexity of the edge-edge case though.
Would it be possible to elaborate on what the "non-convexity" of edge-edge 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.
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: Continuous GJK

Post by RandyGaul »

bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Continuous GJK

Post by bone »

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 edge-edge 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.
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: Continuous GJK

Post by RandyGaul »

Yes, the problem is the axis flips. It can flip when the axis goes from penetrating to non-penetrating, and can also flip as the two vectors rotate relative to one another: https://en.wikipedia.org/wiki/Cross_pro ... roduct.gif
Post Reply