Real-Time Physics Simulation Forum

Re: Continuous GJK

2017-04-14T17:14:26+00:00

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

Statistics: Posted by RandyGaul — Fri Apr 14, 2017 5:14 pm

Re: Continuous GJK

2017-04-11T13:51:09+00:00

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.

Statistics: Posted by bone — Tue Apr 11, 2017 1:51 pm

Re: Continuous GJK

2017-04-10T19:09:42+00:00

Convexity https://en.wikipedia.org/wiki/Convex_function

Statistics: Posted by RandyGaul — Mon Apr 10, 2017 7:09 pm

Re: Continuous GJK

2017-04-07T20:01:53+00:00

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.

Statistics: Posted by RandyGaul — Fri Apr 07, 2017 8:01 pm

Re: Continuous GJK

2017-03-23T19:07:33+00:00

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.

Statistics: Posted by Dirk Gregorius — Thu Mar 23, 2017 7:07 pm

Re: Continuous GJK

2017-03-23T16:02:03+00:00

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.

Statistics: Posted by boble — Thu Mar 23, 2017 4:02 pm

Re: Continuous GJK

2017-03-22T18:21:11+00:00

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

Statistics: Posted by Dirk Gregorius — Wed Mar 22, 2017 6:21 pm

Continuous GJK

2017-03-22T16:30:29+00:00

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?

Statistics: Posted by boble — Wed Mar 22, 2017 4:30 pm