Comments on: Contact generation between 3D convex meshes Thanks for the tip Kester, I recall you reported this with source code in your vehicle dynamics write-up. In the comments you point out that you also search the preferred directions for each shape, but I don’t see this in the source code. Did you remove testing those directions later?


// The separating axis test returns true if there is an axis that separates the two objects.
// It checks the vector between their origins, and the preferred directions of each shape.
bool ChungWangSeparatingAxisTest(const btConvexShape* shape1, const btConvexShape* shape2, const btTransform& transform1, const btTransform& transform2, btVector3& cachedSeparatingAxis)
{
const btMatrix3x3& basis1 = transform1.getBasis();
const btMatrix3x3& basis2 = transform2.getBasis();

const btVector3 separatingVector = (transform2.getOrigin() - transform1.getOrigin());

btVector3 separatingAxis = cachedSeparatingAxis;
// The paper suggests an algorithm to calculate when the SAT should terminate... I'll just
// do a few iterations and then give up. The separating axis is cached between steps, so
// we can use it & refine it over a few frames.
int max_iterations = 5;
while(max_iterations--)
{
btVector3 p0 = basis1 * shape1->localGetSupportingVertex(separatingAxis * basis1);
btVector3 p1 = basis2 * shape2->localGetSupportingVertex(-separatingAxis * basis2);

btScalar radius1 = p0.dot(separatingAxis) - p1.dot(separatingAxis);

if (radius1 + SIMD_EPSILON < separatingVector.dot(separatingAxis))
{
cachedSeparatingAxis = separatingAxis;
return true;
}

btVector3 r = (p1 - p0).normalized();
separatingAxis = separatingAxis + 2.0f * r.dot(separatingAxis) * r;
}

cachedSeparatingAxis = separatingAxis;
return false;
}

In case someone is interested, the original Chung-Wang paper is online here: I find the GJK/EPA algorithm to be quite expensive. I use the Chung-Wang separating axis test (see Real Time Collision Detection by Christer Ericson) to early out - if you can prove that two convex objects do not overlap, you can skip the GJK test. You only need a few iterations, and you can use temporal coherence to find the initial test axis. I find the GJK/EPA algorithm to be quite expensive. I use the Chung-Wang separating axis test (see Real Time Collision Detection by Christer Ericson) to early out – if you can prove that two convex objects do not overlap, you can skip the GJK test. You only need a few iterations, and you can use temporal coherence to find the initial test axis.

]]>