Stability issue with btBvhTriangleMeshShape

[JHoule]

We're using btBvhTriangleMeshShape for the static scene, but it's proving to yield stability issues (Bullet 2.80-rev2531).

Take a simple scene: a box for the ground (static), and a smaller dynamic box placed on top of it. Everything is stable when using btBoxShape on both. But if we replace the static ground to instead use an equivalent btBvhTriangleMeshShape with 6x2 triangles, the dynamic box is a little shaky.

We've enabled debug rendering, and tried to make sense of the difference. From what we gathered, the box-box case (stable) quickly ends up with 4 persistent contact points at each corner of the contact face. But in the trimesh-box case, we can see the 4 contact points changing all of the time, and not converging to the 4 corners of the dynamic box (which is always a btBoxShape).

We've tried to trace things deeper, and noticed that the trimesh-box case had flipped normals, but we believe this is only a side-effect of having different A and B objects in the manifold (which always stores m_normalWorldOnB). We've also found that trimesh-box collision ends up using the GJK algorithm, but we're not sure if it's a potential cause for the instability. We understand that the contact manifold will always drop one of the 4 contact points, but shouldn't GJK normally restore it?

We've tried disabling KEEP_DEEPEST_POINT (btPersistentManifold.cpp@115) as well as turned 4-point area calculation (btPersistentManifold.cpp@26, set to false), to no avail.

We're a bit surprised no one in the forums reported such instability when using btBvhTriangleMeshShape, so we're hoping something simple we might have missed... Does anyone have any suggestion?

[JHoule]

We've isolated the issue further, and have written a quick fix.

The problem is that when we add a fifth contact point to the persistent manifold, it will always replace one of the previous 4. Only that replacement can sometimes result in a contact point area that shrinks.

Our fix is to compute the current area of the contact points, and only accept the new candidate if it improves the situation.

Here is the patch that dramatically improves our situation:

Code: Select all

--- src/BulletCollision/NarrowPhaseCollision/btPersistentManifold.cpp	2012-05-23 12:27:03.922020400 -0400
+++ src/BulletCollision/NarrowPhaseCollision/btPersistentManifold.cpp.fix	2012-05-23 12:27:16.203722800 -0400
@@ -23,7 +23,7 @@
 ContactProcessedCallback	gContactProcessedCallback = 0;
 ///gContactCalcArea3Points will approximate the convex hull area using 3 points
 ///when setting it to false, it will use 4 points to compute the area: it is more accurate but slower
-bool						gContactCalcArea3Points = true;
+bool						gContactCalcArea3Points = false;
 
 
 btPersistentManifold::btPersistentManifold()
@@ -126,6 +126,7 @@
 #endif //KEEP_DEEPEST_POINT
 		
 		btScalar res0(btScalar(0.)),res1(btScalar(0.)),res2(btScalar(0.)),res3(btScalar(0.));
+		btScalar res;
 
 	if (gContactCalcArea3Points)
 	{
@@ -159,6 +160,11 @@
 			btVector3 cross = a3.cross(b3);
 			res3 = cross.length2();
 		}
+		// Compute current area
+		btVector3 a = m_pointCache[1].m_localPointA-m_pointCache[0].m_localPointA;
+		btVector3 b = m_pointCache[3].m_localPointA-m_pointCache[2].m_localPointA;
+		btVector3 cross = a.cross(b);
+		res = cross.length2();
 	} 
 	else
 	{
@@ -177,11 +183,12 @@
 		if(maxPenetrationIndex != 3) {
 			res3 = calcArea4Points(pt.m_localPointA,m_pointCache[0].m_localPointA,m_pointCache[1].m_localPointA,m_pointCache[2].m_localPointA);
 		}
+		res = calcArea4Points(m_pointCache[0].m_localPointA,m_pointCache[1].m_localPointA,m_pointCache[2].m_localPointA,m_pointCache[3].m_localPointA);
 	}
 	btVector4 maxvec(res0,res1,res2,res3);
 	int biggestarea = maxvec.closestAxis4();
-	return biggestarea;
-	
+	//return biggestarea;
+	return maxvec[biggestarea] < res ? -1 : biggestarea;
 }
 
 
@@ -218,6 +225,7 @@
 #else
 		insertIndex = 0;
 #endif
+		if( insertIndex == -1 )  return 0;
 		clearUserCache(m_pointCache[insertIndex]);
 		
 	} else

We've switched to using calcArea4Points() instead of the 3-point path because the 3-point path can yield zero area when the 2 edges being used in the cross product are parallel to one another (a case that can happen when the 4 contact points converge to a square, for example). That said, we've coded sortCachedPoints() to work with gContactCalcArea3Points set to either true or false; we just feel setting it to false is warranted considering the improved quality versus performance impact.

In our code, sortCachedPoints() can now return -1 to indicate that the new candidate doesn't improve the situation (i.e. doesn't increase the area of the contact points). Since we were wary of such a change, we've decided to cut it short as soon as possible, which is right after sorting in addManifoldPoint(), where we return 0. Someone with a deeper understanding might prefer to propagate the -1 further up.

With this simple patch, we have noticeably improved stability on contacts of boxes on our btBvhTriangleMeshShape static scene. The contact points of simple boxes now very rapidly spread to the corners. We sometimes have the 4th contact point shift slightly, but since the other 3 are stable, we no longer observe the shakiness that we originally had.

We've looked at a few Bullet demos, and haven't noticed any difference in behavior, except for one: InternalEdgeDemo. That said, we do not quite understand why we would need to have the contact points follow an internal edge. Comparing internal edge enabled/disabled showed no noticeable difference, so we have to admit we don't understand what this test is meant to show in the first place.

[Laurent Coulon]

Hi JHoule,
Here's a couple more issues we have found in the way persistent manifolds are being managed in Bullet:
1: When a new contact point is created, Bullet determines which of the 4 existing contacts to replace in order to maximize contact area. It is done through an approximation but we found no issue with it in general. However the major issue we saw is that AFTER doing this Bullet then deletes contact points that are obsolete (i.e. that have drifted away too much from their initial position). This is obviously incorrect since the final contact surface can end up begin degenerate. Bullet used invalid points to try to maximize the contact surface.
A trivial fix is to first remove obsolete contacts, and only then decide which of the valid remaining contacts should be replaced (if any) by the new contact computed. In the case of your triMesh box what would then happen is some contacts would get deleted because of drifting, and the new contact would not feel the need to replace any of the remaining contacts since there are now less than 4 leading to greatly improved stability.

2: When computing which point should be replaced, in getCacheEntry(), Bullet does the distance math arbitrarily in the local space of A. Depending on how fast your object is sliding around this can lead to extremely incorrect results since the cached manifolds local position in A and B do not correspond to the same point in space. Both spaces need to be taken into account to get the full picture. the extra expense is fairly minimal and the result more correct.
You can replace this line:

Code: Select all

const btScalar distToManiPoint = diffA.dot(diffA);

with this:

Code: Select all

btVector3 diffB =  mp.m_localPointB- newPoint.m_localPointB;
const btScalar distToManiPoint = btMin(diffA.dot(diffA), diffB.dot(diffB));

Hope that helps.

[JHoule]

Concerning your point 1), I think I agree with you that removing outdated contact points prior to trying to add a new one would help. Only, I peeked at the code, and found that we'd need to change all of the resultOut->refreshContactPoints() to be before the resultOut->addContactPoint(), and there seem to be a bunch of *Algorithm.cpp files that would need to change.

As for 2), I think I see how it would track drifting more accurately, since checking both cases (bodyA and bodyB) increases your chances of finding the closest contact point corresponding to the position sent in getCacheEntry(). But I'm not convinced that what Bullet does in the first place is ideal to begin with: why would it try to merge a new contact point with an existing one if it is close enough (ref: btManifoldResult::addContactPoint())? My co-worker suspects it might have to do with how the force is computed, and that very close contact points don't play well there (might double the effective force at that location). But we're obviously talking through our hats, here...

Still, in the end, neither would have helped our case, since we had instability with a simple leveled floor and a bunch of box "quietly" sitting on it (no sliding). The reason we were losing/adding contact points was that the GJK code didn't converge on corners, and that was punting one of our contact points all of the time.

That said, both your points are nice improvements, I think...

[Laurent Coulon]

there seem to be a bunch of *Algorithm.cpp files that would need to change.

Correct, that is what we did. It's not that many places to change overall.

why would it try to merge a new contact point with an existing one if it is close enough

Consider a sphere sitting on a plane. Would you really want your sphere to report 4 contact points with the floor all exactly in the same position? the solver should work fine, each contact would account for 1/4th of the total contact forces applied, but that is obviously not an elegant approach. This is especially problematic if you want to use your manifold information to spawn effects at contact points based on impact forces. You end up with 4 overlapping point with 1/4 of the force each instead of a single one containing the real impact information.
Another reason that is specific to Bullet is that when a new contact point replaces an existing close one, the age of the contact is kept therefore not causing the new contact to generate parasite restitution.

we had instability with a simple leveled floor and a bunch of box "quietly" sitting on it

this would be fixed if you try the suggested change from my other thread The instability introduced by replacing a contact point by a new one is resolved by our changes. Your solution "hides" the problem by making contact points not be as volatile but the instability would reappear if you make the cube slide slightly.

[JHoule]

Consider a sphere sitting on a plane. (snip)

Yep, I see that case is better to collapse contact points.

this would be fixed if you try the suggested change from my other thread

Yeah, we're gonna try to get the files you gave to compile... Will keep you posted (on the other thread).

[Karrok]

I've had some trouble with rapidly shifting contact points myself as well.

Perhaps it is a good idea for you guys to submit a patch in the Bullet Issue list so Erwin can have a look at it and (if it pans out to be a good patch that doesn't break other things implement it for a new bullet version.

Meanwhile I'll be trying out the mentioned changes a bit myself, cheers!