expanding GJK

[lonestar]

Hello,
this is my first post here.

I am currently building my 3d engine, and i am still doing my collision engine.

So for now, i made it working with a yes/no intersection test using GJK.
but i want to expand it, like have the normal, points of intersection, penetration depth.

What is the best way of do it?
Can someone explain it to me in an easy approach?

[lonestar]

And just to mention this, i implemented the GJK algorithm the way Casey explained it here:
https://mollyrocket.com/forums/viewtopic.php?t=245
as i've been reading somewhere that i should be changing the termination case or something like that.

So can anyone explain the steps i have to do in some details please? Because this is the first time i ever work on collision!

Thank you all

[Erwin Coumans]

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

[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 have the 2 books, but they are more confusing me, and it is hard for me to understand, there are a lot of methods, i dont know which one to use,
this is why i am asking,
like do i use Johnson's distance? EPA?

Bullet GJK's for example, when implementing GJK myself, i did it Casey's way,
then i took the simplex2,3,4 from your code, they only return intersection when the object1 hits another object2, but if object1 keeps on penetrating object2, your version will start giving me no intersection.

I never had this case with Casey's method.. mayne i am missing something like with the termination case

you've been saying that you're going to write a paper about extracting the info, did you ever had the chance to do it?


Regards

[Dirk Gregorius]

Johnson is the subalgorithm to find the closest point on the simplex to the orign. Bullet uses a Voronoi simplex solver.

I suggest looking at Christer's book page 401. What is a a little confusing in the book is that point 2 and 4 actually belong together. That is when you compute the currently closest point to the simplex you also directly reduce it. E.g. you have a segement and the closest point to the origin is vertex A, then you also directly reduce the simplex to vertex A or if your current simplex is the triangle ABC and you find the closest point is on the segement AC, then you directly reduce your simplex to the segement AC.
All these closest points calculations use Voronoi regions (see p. 127, 136, 142). Hence the name Voronoi simplex solver.

Casey's GJK implementation doesn't compute closest points, but it only is a boolean query whether to objects intersect or not. Gino calls this the SAT-GJK in his book IIRC.

GJK fails when to objects penetrate. In this case you need another algorithm to find the minimum penetration distance. For this you could use EPA (like Bullet does)


HTH a little,
-Dirk

[lonestar]

Johnson is the subalgorithm to find the closest point on the simplex to the orign. Bullet uses a Voronoi simplex solver.

I suggest looking at Christer's book page 401. What is a a little confusing in the book is that point 2 and 4 actually belong together. That is when you compute the currently closest point to the simplex you also directly reduce it. E.g. you have a segement and the closest point to the origin is vertex A, then you also directly reduce the simplex to vertex A or if your current simplex is the triangle ABC and you find the closest point is on the segement AC, then you directly reduce your simplex to the segement AC.
All these closest points calculations use Voronoi regions (see p. 127, 136, 142). Hence the name Voronoi simplex solver.

Casey's GJK implementation doesn't compute closest points, but it only is a boolean query whether to objects intersect or not. Gino calls this the SAT-GJK in his book IIRC.

GJK fails when to objects penetrate. In this case you need another algorithm to find the minimum penetration distance. For this you could use EPA (like Bullet does)


HTH a little,
-Dirk

well, i dont need to know the distance between the 2 objects if they are not intersecting, i only need to find the distance once i have collision, in other terms i want to find everything related to when the 2 objects intersect: penetration depth, points of contacts, and normal.

so i only need EPA? i wouldnt need Voronoi simplex solver?
that is what i've been asking, like what algorithm to use to have the information i need?


thanks

[Dirk Gregorius]

I think only using EPA would not be the best idea. When using GJK for contact generation you usually have to deal with shallow and deep penetration. Shallow penetration means that the distance is withing some specified margin. Only when you have real penetration you fall back on another method like e.g. EPA. Also note that GJK/EPA will only find one contact point and normal per frame. So you need to collect and maintain contact points over several frames. This is done in btPersistentManifold in Bullet.

The other option is to use SAT and specialized algorithms for sphere, capsule, etc.

Erin has made a nice presentation regarding this topic at this year GDC. You can find it here:

http://www.gphysics.com/files/GDC2007_ErinCatto.zip

Contact point generation is in my opinion one of the toughest problems when doing rigid body physics. If you have problems understanding how this works you better use Bullet directly. This will save you a lot of time...


HTH,
-Dirk

[lonestar]

I think only using EPA would not be the best idea. When using GJK for contact generation you usually have to deal with shallow and deep penetration. Shallow penetration means that the distance is withing some specified margin. Only when you have real penetration you fall back on another method like e.g. EPA. Also note that GJK/EPA will only find one contact point and normal per frame. So you need to collect and maintain contact points over several frames. This is done in btPersistentManifold in Bullet.

The other option is to use SAT and specialized algorithms for sphere, capsule, etc.

Erin has made a nice presentation regarding this topic at this year GDC. You can find it here:

http://www.gphysics.com/files/GDC2007_ErinCatto.zip

Contact point generation is in my opinion one of the toughest problems when doing rigid body physics. If you have problems understanding how this works you better use Bullet directly. This will save you a lot of time...


HTH,
-Dirk

i am not doing rigid body physics, i just want the info for my collision reaction thing.

Unfortunatly i cant use Bullet, it is a junior school project, and i have to be the one who wrote everything..

I am trying to understand it instead of just hacking it, you know.

I just want to have EPA explained in an easy way to understand so i can know how things work.

so you talked about deep penetration and shallow penetration, with deep penetration i'll be using EPA?
and for shallow penetration, how would i be doing the margin thing?


Erwin, are you planning to do like a documentation of your engine explaining the algorithms you are doing for example?

[lonestar]

so i've been reading more, and i want to do EPA.
i am running Casey's SA_GJK to see when i have intersection/no intersection
since i dont need the shallow penetration.

so after that what should i do?
i am actually getting somehow what i have to do..
however i have some questions:


we start with the last simplex, so i cast a ray having an origin (0.0.0) and as direction the direction vector (relative motion).

cant that ray have the opposite direction of the last direction i had when returning the tetrahedron as simplex after intersection? or should it be the relative motion vector?


so i do a ray triangle intersection from that ray to the 4 triangles of the tetrahedron to know which face i am exiting? or there is a faster way to do that (classical ray triangle intersection) ?


so after that i have the new face, and i call the support function along the direction, i'll get a new point, would the tetrahedron i get be always convex? or it wouldnt matter?


we are always assuming that what i start with is a tetrahedron, are there any cases where that is wrong? ie: returning a line or a triangle as a simplex?

i am glad i'm on the good track thinking of this, but here we go, i have a very good number of questions i need answers for..

[Dirk Gregorius]

Sorry, I haven't implemented EPA so far. All I remember that you need some special attention when the simplex containing the origin is not a tetrahedron. Might happen when two spheres are overlapping...

You have two good books and Bullet and SOLID have implementations for the presented algorithms, so you best try to understand how this works. I recommend running Bullet side to side with your collision stuff to see if it works and also this will allow you to step through the code.

HTH,
-Dirk

[raigan2]

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

[lonestar]

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?

[Erwin Coumans]

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

[lonestar]

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?

[Erwin Coumans]

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: Select all

/* Expand hull		*/
		for(;iterations<EPA_maxiterations;++iterations)
			{
			Face*		bf = FindBest();
			if(bf)
				{
				GJK::Mkv*	w = Support(-bf->n);
				const F		d(bf->n.dot(w->w)+bf->d);
				bestface	=	bf;
				if(d<-accuracy)
					{
					Face*	cf =0;
					Face*	ff =0;
					U		nf = 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