Real-Time Physics Simulation Forum

expanding GJK

2007-07-02T19:57:41+00:00

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

Statistics: Posted by Dirk Gregorius — Mon Jul 02, 2007 7:57 pm

expanding GJK

2007-07-02T19:07:23+00:00

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.

Statistics: Posted by lonestar — Mon Jul 02, 2007 7:07 pm

expanding GJK

2007-07-02T08:25:14+00:00

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

Statistics: Posted by Dirk Gregorius — Mon Jul 02, 2007 8:25 am

expanding GJK

2007-07-02T02:01:13+00:00

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

Statistics: Posted by lonestar — Mon Jul 02, 2007 2:01 am

expanding GJK

2007-07-01T21:35:46+00:00

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?

Statistics: Posted by lonestar — Sun Jul 01, 2007 9:35 pm

expanding GJK

2007-06-30T21:12:39+00:00

so the approach i gave is wrong?

Statistics: Posted by lonestar — Sat Jun 30, 2007 9:12 pm

expanding GJK

2007-06-30T16:51:38+00:00

There is no motion involved. It would help if you familiarize yourself with sampling the penetration depth, given a certain direction using the minkowski sum of the two objects. This is implemented in Bullet in Bullet/src/BulletCollision/NarrowPhaseCollision/btMinkowskiPenetrationDepthSolver.cpp

The search directions are based on the current triangle/face normals in the (expanding) polytope.

The ending criterium is more complex then 'hits the minkowski surface', I should have be more clear, perhaps some pictures help: imagine a triangle (simplex/polytope) inside a convex polyhedron. You can split the triangle and project the vertex onto the surface. The new simplex that includes the new projected vertex might be concave, so this needs to be made convex.

The ending criterium is when the new penetration distance is 'not decreasing' anymore (or as safety gap for degenerate cases terminate if the total number of iterations is exceeded).

EPA loop from btGjkEpa.cpp

Code:

/* Expand hull*/for(;iterationsn);const Fd(bf->n.dot(w->w)+bf->d);bestface=bf;if(d<-accuracy){Face*cf =0;Face*ff =0;Unf = 0;Detach(bf);bf->mark=++markid;for(U i=0;i<3;++i){ nf+=BuildHorizon(markid,w,*bf->f[i],bf->e[i],cf,ff); }if(nf<=2){ break; }Link(cf,1,ff,2);} else break;} else break;}

* FindBest, finds the best face to split.
* BuildHorizon, makes the expanded polytope convex.
* Support(direction) is the similar to 'localGetSupportingVertexWithoutMargin' in btMinkowskiPenetrationDepthSolver.

A series of pictures would probably explain this better.
Hope this helps,
Erwin

Statistics: Posted by Erwin Coumans — Sat Jun 30, 2007 4:51 pm

expanding GJK

2007-06-30T05:25:30+00:00

Basically when GJK terminates, the origin is inside the minwkowski sum, and GJK terminates with a simplex (tetrahedron or fewer verts) that encapsulates the origin. The goal is to inflate/expand this tetrahedron until it hits the surface of the minkowski sum, while keeping it convex. Expansion is done by breaking triangles. Keeping it convex is done by keeping the silhouette seen from the new vertex.

Which part of EPA don't you understand exactly?
Thanks,
Erwin

i understand the process EPA is doing,
but when it comes to implementing it, i am having a lot of wonders.

GJK terminates, i have intersection, so now i have the origin and a tetrahedron, i never terminate with less than 4 points in my list.

ok so the origin is in the tetrahedron, i need to know which face to select so i can make a new tetrahedron until i hit the surface of the minkowski sum.
do we agree until now?

so my question is here, how to do that?

how to select the face?
i've been told to cast a ray from the origin having as direction the relative motion vector of the 2 objects,( a with Va, b with Vb, the vector is Va-Vb)

i see that ray which face it hits, save it,
have a new point by calling the support function, do the same test again, keep on doing it until i cant find any furthest point along that direction, it would mean that i hit the minowski's sum.

The points that make up the triangle through which i finally exit the sum are minkowski sums of parts of my objects (each point is an a - b). These tell me what parts of the object are closest ("penetrating").

do you think this would work?

Statistics: Posted by lonestar — Sat Jun 30, 2007 5:25 am

expanding GJK

2007-06-29T21:14:09+00:00

I moved the topic, because EPA is complicated and not for beginners.

Before Gino published EPA, we were collegues and shared an office, so we discussed and tried EPA within Blender/Solid. Later I assisted implementing EPA in Havok, and now I'm providing an open source implementation through Bullet, contributed by Nathanael Presson. The basic idea is fairly simple, but getting to the current robust implementation in Bullet is extremely complicated.

Basic idea behind EPA:
Blowing up a balloon embedded within a convex object until it hits the surface.

Basically when GJK terminates, the origin is inside the minwkowski sum, and GJK terminates with a simplex (tetrahedron or fewer verts) that encapsulates the origin. The goal is to inflate/expand this tetrahedron until it hits the surface of the minkowski sum, while keeping it convex. Expansion is done by breaking triangles. Keeping it convex is done by keeping the silhouette seen from the new vertex.

Which part of EPA don't you understand exactly?
Thanks,
Erwin

Statistics: Posted by Erwin Coumans — Fri Jun 29, 2007 9:14 pm

expanding GJK

2007-06-29T16:41:31+00:00

I recommend Gino's book for GJK/EPA, I don't think the Ericson book covers EPA at all.

yeah i'm reading Gino's book, but still, it is somehow complicated for me, some areas are easy to understand, and some areas are not!
so that is why i had all the above questions.

anyone who implemented EPA can please explain it to me?

Statistics: Posted by lonestar — Fri Jun 29, 2007 4:41 pm