GJK

Quote:

Original post by jimgeagea i am building a 3d engine, well, i implemented GJK for intersection test, however, it only gives me yes/no intersection, so i want to expand it, so i can have some info, like penetration depth, contact points and normals.

Consider turning your static GJK implementation into a continuous version of GJK, as described by Gino in Ray Casting against General Convex Objects with Application to Continuous Collision Detection.

Quote:

Original post by Christer Ericson Quote: Original post by jimgeagea i am building a 3d engine, well, i implemented GJK for intersection test, however, it only gives me yes/no intersection, so i want to expand it, so i can have some info, like penetration depth, contact points and normals. Consider turning your static GJK implementation into a continuous version of GJK, as described by Gino in Ray Casting against General Convex Objects with Application to Continuous Collision Detection.

Christer, i think you are familiar with Casey's method of doing GJK, so i have that implemented!

can you guide me through the process to expanding it so i can get the info i need?

i've been reading that i would first worry about shallow penetration, (having a margin on the minkowski sum)
so my problem is how would i expand Casey's GJK to get what i need?

as for the paper you gave me, would that be a general case? i mean it would work for any kind of penetration and collision?
is it faster than EPA?

Quote:

Original post by jimgeagea can you guide me through the process to expanding it so i can get the info i need?

I'm afraid you are asking for a lot for a forum post. You should read Gino's paper. If you have understood your implementation of GJK, it's not hard to understand Gino's algorithm or to implement it, but it's still quite lengthy trying to explain it, and I'm afraid I just don't have the time for that.

Quote:

as for the paper you gave me, would that be a general case? i mean it would work for any kind of penetration and collision? is it faster than EPA?

A continuous approach would get you the time of first contact. Realistically there will be some rounding errors causing penetration, but you are now guaranteed this is a shallow penetration, so it's a bit easier to handle.

For example, you can spherically extend both objects by some small distance, compute the collision with the continuous GJK, advance both objects to time t where they are "in contact" (which they actually aren't, as you spherically extended them) and now get the closest points between them to determine the collision normal.

EPA is for the static collision case, and more for deep penetration, so we're talking apples to oranges a bit. EPA is not easy to implement (at least not robustly) and I think people (Erwin, Dirk) on Erwin's Physics Simulation Forums have already informed you about this and how EPA works.

Dirk also pointed you to Erin Catto's presentation at this years physics tutorial at GDC where he talked about obtaining contacts. You should read this too.

Quote:

Original post by Christer Ericson Quote: Original post by jimgeagea can you guide me through the process to expanding it so i can get the info i need? I'm afraid you are asking for a lot for a forum post. You should read Gino's paper. If you have understood your implementation of GJK, it's not hard to understand Gino's algorithm or to implement it, but it's still quite lengthy trying to explain it, and I'm afraid I just don't have the time for that. Quote: as for the paper you gave me, would that be a general case? i mean it would work for any kind of penetration and collision? is it faster than EPA? A continuous approach would get you the time of first contact. Realistically there will be some rounding errors causing penetration, but you are now guaranteed this is a shallow penetration, so it's a bit easier to handle. For example, you can spherically extend both objects by some small distance, compute the collision with the continuous GJK, advance both objects to time t where they are "in contact" (which they actually aren't, as you spherically extended them) and now get the closest points between them to determine the collision normal. EPA is for the static collision case, and more for deep penetration, so we're talking apples to oranges a bit. EPA is not easy to implement (at least not robustly) and I think people (Erwin, Dirk) on Erwin's Physics Simulation Forums have already informed you about this and how EPA works. Dirk also pointed you to Erin Catto's presentation at this years physics tutorial at GDC where he talked about obtaining contacts. You should read this too.

i am into shallow penetration first,
my problem resides here, computing the collision with the continuous GJK.
how would i do that?

Quote:

Original post by jimgeagea i am into shallow penetration first, my problem resides here, computing the collision with the continuous GJK. how would i do that?

I already answered that. You (1) implement Gino's continuous GJK algorithm from his paper, and then (2) using the continuous GJK, compute the time t at which the objects intersect after having been (slightly) spherically extended, then advance the objects to time t, and finally compute the closest points between the static and nonextended objects at time t using normal GJK, which gives you the contact normal and point (see Section 9.5.3 of my book for this last calculation).