Square inside polygon results in no collision because of BiasGreaterThan.

[anon38]

I'm finding that the BiasGreaterThan function results in cases where a square can get stuck in a polygon at certain positions. This seems to be because the wrong reference/incidence face gets picked. It appears to be fixed by simply changing BiasGreaterThan to a naive

inline bool BiasGreaterThan( real a, real b )
{
  return a >= b;
}

Or doing what box2d does also works i.e.

...
const float k_tol = 0.1f * b2_linearSlop; 
if (separationB > separationA + k_tol)
...

This can happen if you spawn a square inside a polygon (with gravity off so the square doesn't move).

Here is an example case, but it's pretty noticeable if you spawn a square inside of any random convex polygon of appropriate size.

PolygonShape poly;
    Vec2 vertices[] = {Vec2(-0.5, -0.5), Vec2(0.5,-0.5), Vec2(0.5, 0.5), Vec2(-0.5,0.5)};
    poly.Set( vertices, 4 );
    Body *b1 = new Body(&poly,-1.6,0);
    b1->SetOrient(0);
    
    PolygonShape poly2;
    Vec2 vertices2[] = {Vec2( -3.740512982560686,  -0.5735584769983424), Vec2( -3.719614114679503,  -1.7226350555144725), Vec2( -2.4932647260279026,  -2.7316117009988794), Vec2( -0.8201915887684166,  -3.339520273224558), Vec2( 0.8485318324075104,  -3.768661315482074), Vec2( 1.4125001862587832,  -3.877552867283213), Vec2( 3.7734708786741002,  -2.3132118400651835), Vec2( 3.9056625143223886,  -2.053720640728945), Vec2( 3.9608941922040817,  -0.21303954202834152), Vec2( 3.4524715186551624,  1.0169073997947553), Vec2( 1.9124525889738742,  2.634607801080719), Vec2( 0.24731544222635193,  3.825379925658064), Vec2( -1.1199503300054676,  4.6035871781070306), Vec2( -3.0722506887204464,  2.6117852157357326)};
    poly2.Set( vertices2, 14);
    Body *b2 = new Body(&poly2,0,0);
    
    b2->SetOrient(0);

PolygontoPolygon(b2, b1); Will return false even though they do clearly intersect.
PolygontoPolygon(b1, b2); Will return true however.

But with the fixes mentioned above they both will return true.

[RandyGaul]

Thanks for this post. I wrote that code ages ago... And it looks buggy. Here is what I use in my qu3e repo, which should be robust.

// Artificial axis bias to improve frame coherence
const r32 kRelTol = r32( 0.95 );
const r32 kAbsTol = r32( 0.01 );
i32 axis;
r32 sMax;
q3Vec3 n;
r32 faceMax = q3Max( aMax, bMax );
if ( kRelTol * eMax > faceMax + kAbsTol )
{
	axis = eAxis;
	sMax = eMax;
	n = nE;
}
else
{
	if ( kRelTol * bMax > aMax + kAbsTol )
	{
		axis = bAxis;
		sMax = bMax;
		n = nB;
	}
	else
	{
		axis = aAxis;
		sMax = aMax;
		n = nA;
	}
}

So then to update our function here (no edge case, just two faces), it can look like:

inline bool BiasGreaterThan( real a, real b )
{
	const real k_relative = 0.95f;
	const real k_absolute = 0.01f;
	if (k_relative * a > b + k_absolute) {
		return true;
	} else {
		return false;
	}
}

Would you like to submit a pull request? If not I can make the modification. Let me know!

[anon38]

Wow thanks for the quick response! Your modification also fixes the issue. No more false negative intersections. However, I'm still experimenting with the bias in my engine (currently have sequential impulse solver+feature based contacts+warm starting working) to determine what is most stable. Interestingly enough, your original bias implementation was very stable with my stacking test cases (essentially just squares stacked in different nxm configurations). But I've come to realize that it is very dependent on the order of my pairs from the broadphase as this affects the distribution of the bias on each body. For example, when I add the bodies to the world in a reverse order, then the original bias becomes more unstable.

Anyway, your change does indeed fix the bug of missing intersections, which was the most critical issue. So you can feel free to make the modification. I'm going to continue to experiment in my own engine with different biases to determine which is most stable.