EPA in 2d

[innochenti]

Hi.
i have few question about implementing EPA in 2d.

in pseudocode:

For Each X Of P
construct_entry(X);

But what about case when origin is lying on line (simplex size = 2, W[0], W[1] )? We have ||e.V|| = 0,
and dot(V,W) - V become infinity.

How to blow up line into triangle case?

my base code for epa

Code: Select all

void GJK( Convex& A, Convex& B )
{
//...
//	find W,P,Q.
}

	bool closest_is_internal( const entry& e )
	{
		return e.s > 0 && e.t > 0;
	}

entry construct_entry( const mt::vec3f& A, const mt::vec3f & B, const mt::vec3f & p0, const mt::vec3f & q0, const mt::vec3f & p1, const mt::vec3f & q1 )
	{
		entry e;

		e.y0 = A;
		e.y1 = B;

		e.p0 = p0;
		e.p1 = p1;

		e.q0 = q0;
		e.q1 = q1;

		mt::vec3f	ab = B - A;
			
		float t = mt::dot_v3_v3(-A, ab) / ( mt::dot_v3_v3(ab, ab) );

		if ( t < 0.0f )
		{
			t = 0.0f;
		}

		if ( t > 1.0f )	
		{
			t = 1.0f;
		}
			
		e.s = 1-t;
		e.t = t;
		e.v = A + t * ab;
		e.key = e.v.length();
		return e;
	}

mt::vec3f	epa( Convex& A, Convex& B )
	{
		Qheap.clear();
		
		if( size == 2)	// simplex size = 2, line
		{
			// ???
		}

		for( int i = 0; i < size; i++ )
		{
			int next_i = (i+1) % size;

			entry e = construct_entry(W[i],W[next_i],P[i],Q[i],P[next_i],Q[next_i]);

			if (closest_is_internal(e))
			{
				Qheap.push_back( e );
			}
		}

		bool	close_enough = false;

		int iteration = 0;

		entry e;

		do
		{
			e = Qheap.best();
			
			Qheap.pop_best();

			mt::vec3f v = e.v;
				
			mt::vec3f P = A.support( v );
			mt::vec3f Q = B.support( -v );

			mt::vec3f w = P - Q;

			float vl = v.length();

			if(fabs(vl) <= eps)
			{
				// v == 0 ???
			}

			float dot = dot_v3_v3(v,w) / vl;
			close_enough = (dot - vl) <= fabs(eps);

			if(close_enough == false)
			{
				entry e1 = construct_entry(e.y0, w, e.p0, e.q0, P, Q );

				if (closest_is_internal(e1))
				{
					Qheap.push_back( e1 );
				}

				entry e2 = construct_entry(e.y1, w, e.p1, e.q1, P, Q );
			
				if (closest_is_internal(e2))
				{
					Qheap.push_back( e2 );
				}
			}

			iteration++;
		}
		while(close_enough == false);

		ClosestPoints[0] = e.s * e.p0 + e.t * e.p1;
		ClosestPoints[1] = e.s * e.q0 + e.t * e.q1;

		return e.v;
	}

[Erwin Coumans]

Hi,

How to blow up line into triangle case?

In 2D there are just lines/edges, no triangles. If EPA starts with the origin on a line, it means the objects are touching, and you can report zero penetration. If the origin is inside the 2D polygon, you find the closest line/edge, break it into 2 edges, and project the new point onto the surface. Then make sure that the resulting polytope is convex.

Pictures explain this process better.

Hope this helps,
Erwin

[Dirk Gregorius]

Doesn't Gino's book explain EPA in 2D before extending it into 3D? Actually with some nice sketches?

[innochenti]

hm. i take bullet epa solver and write simple test:

Code: Select all

//init
tr[0].setIdentity();
tr[1].setIdentity();

btConvexHullShape*	boxA = new btConvexHullShape();

boxA->addPoint(btPoint3(0,0,0));
boxA->addPoint(btPoint3(0,2,0));
boxA->addPoint(btPoint3(2,2,0));
boxA->addPoint(btPoint3(2,0,0));

boxA->setMargin(0);

btConvexHullShape*	boxB = new btConvexHullShape();

boxB->addPoint(btPoint3(0+1,0+1,0));
boxB->addPoint(btPoint3(0+1,2+1,0));
boxB->addPoint(btPoint3(2+1,2+1,0));
boxB->addPoint(btPoint3(2+1,0+1,0));

boxB->setMargin(0);

shapePtr[0] = boxA;
shapePtr[1] = boxB;

//solver
static btGjkEpaPenetrationDepthSolver Solver0;

btPoint3 witnessA;
btPoint3 witnessB;

btVoronoiSimplexSolver sGjkSimplexSolver1; 

bool result = Solver0.calcPenDepth(sGjkSimplexSolver1,shapePtr[0],shapePtr[1],tr[0],tr[1],btVector3(1,0,0),witnessA,witnessB,0,&gStackAlloc);
//

result == false, and simplex = line (origin is lying on line )

(but btGjkPairDetector return triangle)

why?

[John McCutchan]

result == false, and simplex = line (origin is lying on line )

(but btGjkPairDetector return triangle)

why?

Bullet's EPA uses an internal GJK implementation to rebuild the simplex, that could explain the different results.

Also, Dirk is correct that Gino's book explains EPA in 2D in great detail including diagrams and pseudo code.

[Erwin Coumans]

My comment on 'Pictures explain this process better' was referring to Gino's book and I was about to add some similar picture, so here it is:

First the stages of EPA:

epa_steps.jpg

However, we are concerned about the origina lying on the line. See those two different cases:

epa_2_cases.jpg

Case B we are finished. Bullet GjkEPA will return 'false' (false meaning there is no penetration detected).
In case A, the line on which the origin lies is the closes, so in this case we can break the line at the origin, and move it onto the surface.

Indeed, Bullet relies on a hybrid collision mechanism, using a collision margin. On deep penetration (deeper then the sum of the collision margins) it will use EPA with its own built-in GJK (that was part of the contribution, no efforts have been made to remove/merge redundant GJK calculations).

Can you clarify your issue with 2D EPA more in detail?
Hope this helps,
Erwin