expanding GJK

[lonestar]

so the approach i gave is wrong?

[lonestar]

i have a question about doing the shallow penetration,
if you have a sphere, in the support function we are adding a certain margin,
so it is like we are testing 2 spheres with slightly bigger radius.

shouldn't it be smaller radius? so when there is collision we have the penetrating depth?

can someone explain it in some details please?

[lonestar]

I recommend just learning from Bullet's GJK and EPA implementation.

Otherwise, please read those forums more thoroughly, read Christer Ericson and Gino van den Bergen's books on this topic. For further info check:
http://www.continuousphysics.com/Bullet ... p?=&p=2247

Thanks,
Erwin

i thought i would go for the shallow penetration first,
how would i go?

i know that i should add some margin to the support function, i did that,
but how to get the distance and the points of intersection?

Thanks

[Dirk Gregorius]

Please read the material we provided here more sorrowly. All this is explained e.g. beginning from slide 20 in Erin Catto's slides.

From the slides:

- The support points are scaled up by a small margin to detect contact.
- Compute the closest points (no margin).
- This gives the position and normal.
- The penetration is the margin minus the true distance.

The next two slides have two nice sketches...


Also something that might help is to setup a nice simple example that you can follow easily using the debugger, e.g. two unit spheres with distance 1.


Cheers,
-Dirk

[lonestar]

Please read the material we provided here more sorrowly. All this is explained e.g. beginning from slide 20 in Erin Catto's slides.

From the slides:

- The support points are scaled up by a small margin to detect contact.
- Compute the closest points (no margin).
- This gives the position and normal.
- The penetration is the margin minus the true distance.

The next two slides have two nice sketches...


Also something that might help is to setup a nice simple example that you can follow easily using the debugger, e.g. two unit spheres with distance 1.


Cheers,
-Dirk

my question resides here:
Compute the closest points (no margin).

how would i compute the closest points, that is what i am not able to make.

[Dirk Gregorius]

The major difference is that instead of computing the projection of the origin onto a searched subsimplex, Casey determines a search direction perpendicular to the subsimplex in the direction of the origin without having the projected point.

This means when your simplex is e.g. a segment you compute the closest point on this segement to the origin. This is your search direction. In the SAT-GJK there is no simplex in this form. Also when you compute the closest points to the segment (or triangle, tetrahedron) you find baraycentric coordinates (look at Christer's book please!!!).

So your simplex has basically the following structure:

struct Simplex
{
int mSize; // Current number of vertices (1 - 4)
Vec3 mW[4], mP[4], mQ[4];
float mLambda[4]; // Barcentric coordinates
}

1) Compute u, v, w (SupportPoints - see Bullet)
2) Add support points to simplex (if not already contained)
3) Compute the closest point on the simplex to the origin (FindPoint OfMinimumNorm). Since the simplex is either a point, segment, triangle or tetrahedron this breaks down to the computations of (as I have already told you twice)

ClosestPointToPoint
ClosestPointToSegement
ClosestPointToTriangle
ClosestPointToTetrahedron

Your new search direction is the vector from the origin O to this closest point. Thats it! Even though there is quite some heavy math involved it is conceptually relatively easy.

So I suggest the following.

a) Clear your mind from Casey implemention for now
b) Look at Solid and Bullets implementation and learn form it!
c) Understand what Johnson's sub-algorithm is and how Bullet replaces it
b) Implement your own simplex solver based on Voronoi regions. That is implement functions like AddPoint() which should return false if the new point is already in the simplex or better is linear dependent on the current points. Also compute a function PointOfMinimumNorm() which falls back onto the four function mentionend above based on the current size of the simplex.

The major gotcha is the reduction of the simplex. (Steps 2 and 4 in Christers book). As pointed out earlier these steps belong together. So when you compute the closest point and find the barycentric coordinates those vertices that have barycentric coordinates of zero are removed. (E.g. you current simplex is a triangle ABC and you find the closest point on the edge BC all you need to do is to remove vertex A from your current simplex).


HTH,
-Dirk