Box vs. Box primitive collision in Bullet ?

[andrei.lupas]

Hi,

It seems like newer versions of Bullet include some support for primitive collision detection instead of GJK (sphere-sphere, box-sphere).

In an older version of Bullet (i.e. 1.5) for a scenario made only of boxes, I replaced GJK with box-box collision from OpenDynamicsEngine. At each frame I clear the previous manifold point and add the new points "dBoxBox"(ODE box-box routine) returns.

Contact points and contact normals seem be be right. However, my stack remains stable only for a couple of frames, and then becomes unstable. Boxes don't pass through each-other, but pop as they are getting a lot of energy.

Can this behavior be caused by lack of contact coherence that single-shot algorithms (ODE box-box) exhibit?

Are there any plans on introducing some box-box primitive collision algorithm in Bullet?


Thanks,
Andrei.

[Dirk Gregorius]

1) How many boxes?
2) Which dimension have the boxes?
3) How many iterations?
4) Do you clean the accumulated impulse each frame?

Cheers,
-Dirk

[andrei.lupas]

1) How many boxes?

I build a stack of 10 boxes. The stack breaks down rapidly even if it's made of 2 boxes.

2) Which dimension have the boxes?

Boxes half-sides are 1.0; the ground box half-sides are default (450,10,450)

3) How many iterations?

Impulse solver uses 10 iterations.

4) Do you clean the accumulated impulse each frame?

I don't apply impulses computed on previous frames. Even if I do, the behavior is the same.

[Erwin Coumans]

In an older version of Bullet (i.e. 1.5) for a scenario made only of boxes, I replaced GJK with box-box collision from OpenDynamicsEngine.

Why?
Have you tried recent Bullet 2.18 box-box, or any other GJK primitive?
As far as I know all convex primitives, including box show stable stacking.

I prefer one generic solution using GJK, rather then all those special cases. This way I can keep the core code (in /src folder) under the ZLib license. There are improvements that I'm intending to add to improve the contact manifold generation and maintenance. This will improve stability. At the moment, Bullet just adds only 1 point at a time, but it is possible to perform direct clipping to get all points at a time, still using GJK. Basically ODE and other libraries first determine the separating axis, and then clip/project the most parallel features for this axis. This can be done using GJK or SAT.

In the past I had some comparison sample code running the ODE box-box inside Bullet framework without problems. You want me to add this as a demo, for comparison?

Hope this helps,
Erwin

PS: btContinuousDynamicsWorld, based on Bullet's Continuous collision detection will be added back in soon. This requires closest distance query, which is not available for the generic SAT (which the ODE box-box is based on).

[Dirk Gregorius]

You must make sure that you clear the accumulated impulses to zero. The sequentiel impulses are clamped against the accumulated impulse when you pass the contact points from dBoxBox. Not applying the accumulated impulse is not enough in your case. Let me know if this helps. At 10 iterations you should be able to do at least 3 boxes without warmstarting.

Cheers,
-Dirk

[andrei.lupas]

In the past I had some comparison sample code running the ODE box-box inside Bullet framework without problems. You want me to add this as a demo, for comparison?

That would be excelent

Thanks a lot !
Andrei.

[Erwin Coumans]

OK, I will add such sample. I'll add the ODE box-box integration in the /Extras folder.

Dirk:
Bullet automatically sets the accumulated impulse to zero for new points, if you reset / clear out all manifold points each frame.
As I mentioned before, there is no reason to add a special box-box, GJK should simulate/run fine. Using GJK with out without warm starting you ocan stably stack more then 3 boxes at 60 hertz with default 9.8 gravity.
I will add some option to disable/toggle warmstarting, it doesn't improve stability much for Bullet actually.

Andrei:
Can you explain why you are not happy with Bullet's box-box? The CcdPhysicsDemo can be easily modified to use boxes instead of cylinders. Can you provide/modify a Bullet sample that shows which performance/quality improvement are needed?

Hope this helps,
Erwin

[andrei.lupas]

Here is my code in Bullet 2.18a.
If a single box rests on the ground box, everything seems fine. However, for bigger stacks, things go crazy. The behavior is the same with both SOR_LCP and impulse approaches. The problem is definitely in my code.

Maybe I don't understand well the relation between 3D coordinate system assumed by ODE and Bullet respectively.

Code: Select all

void btBoxBoxCollisionAlgorithm::processCollision (btCollisionObject* col0,btCollisionObject* col1,const btDispatcherInfo& dispatchInfo,btManifoldResult* resultOut)
{
	if (!m_manifoldPtr)
		return;

	btBoxShape* box0 = (btBoxShape*)col0->m_collisionShape;
	btBoxShape* box1 = (btBoxShape*)col1->m_collisionShape;

	
	btVector3 Box_0_pos = col0->m_worldTransform.getOrigin();
	btVector3 Box_1_pos = col1->m_worldTransform.getOrigin();

	btMatrix3x3 Box_0_rot = col0->m_worldTransform.getBasis();
	btMatrix3x3 Box_1_rot = col1->m_worldTransform.getBasis();

	btVector3 Box_0_halfSide = box0->getHalfExtents();
	btVector3 Box_1_halfSide = box1->getHalfExtents();

	//Z axis in Bullet corresponds to Y axis in ODE and vice-versa ?!
	dMatrix3 R0, R1;
	dVector3 P0, P1;
	dVector3 side0, side1;

	//Swap Y, Z for position vectors
	P0[0] = Box_0_pos[0]; P0[1] = Box_0_pos[2]; P0[2] = Box_0_pos[1];
	P1[0] = Box_1_pos[0]; P1[1] = Box_1_pos[2]; P1[2] = Box_1_pos[1];

	R0[0] = Box_0_rot[0][0]; R0[1] = Box_0_rot[0][1]; R0[2]  = Box_0_rot[0][2]; R0[3] = 0;
	R0[4] = Box_0_rot[1][0]; R0[5] = Box_0_rot[1][1]; R0[6]  = Box_0_rot[1][2]; R0[7] = 0;
	R0[8] = Box_0_rot[2][0]; R0[9] = Box_0_rot[2][1]; R0[10] = Box_0_rot[2][2]; R0[11]= 0;

	R1[0] = Box_1_rot[0][0]; R1[1] = Box_1_rot[0][1]; R1[2]  = Box_1_rot[0][2]; R1[3] = 0;
	R1[4] = Box_1_rot[1][0]; R1[5] = Box_1_rot[1][1]; R1[6]  = Box_1_rot[1][2]; R1[7] = 0;
	R1[8] = Box_1_rot[2][0]; R1[9] = Box_1_rot[2][1]; R1[10] = Box_1_rot[2][2]; R1[11]= 0;

	//Swap Y, Z for half-sides; ODE takes full box size (halfSize * 2)
	side0[0] = Box_0_halfSide[0]*2; side0[1] = Box_0_halfSide[2]*2; side0[2]= Box_0_halfSide[1]*2;
	side1[0] = Box_1_halfSide[0]*2; side1[1] = Box_1_halfSide[2]*2; side1[2]= Box_1_halfSide[1]*2;

		
	#define MAXC 4 //maximum 4 contacts allowed
	dContactGeom contacts[MAXC];
	int skip = sizeof(dContactGeom);

	dVector3 normal;
	dReal depth;	//not used;
	int retCode;	//not used;

	int noContacts;
	//ODE box-box collision:
	noContacts = dBoxBox(P0, R0, side0, 
						 P1, R1, side1,
						 normal, &depth, &retCode, MAXC, &contacts[0], skip);
	if(noContacts == 0)
		return;

	//Now add contacts to maniford:
	btVector3 SIMD_normal;
			SIMD_normal[0] = -normal[0];
			SIMD_normal[1] = -normal[2];
			SIMD_normal[2] = -normal[1];

	btVector3 SIMD_pos;
	
	resultOut->setPersistentManifold(m_manifoldPtr);
	for(int i=0; i<noContacts; i++){
			SIMD_pos[0] = contacts[i].pos[0];
			SIMD_pos[1] = contacts[i].pos[2];
			SIMD_pos[2] = contacts[i].pos[1];
		resultOut->addContactPoint(SIMD_normal, SIMD_pos, -contacts[i].depth);
	}
}

[dog]

There are improvements that I'm intending to add to improve the contact manifold generation and maintenance.

... it is possible to perform direct clipping to get all points at a time, still using GJK. Basically ODE and other libraries first determine the separating axis, and then clip/project the most parallel features for this axis. This can be done using GJK or SAT.

Do you have any links to papers on this?

[Erwin Coumans]

There are improvements that I'm intending to add to improve the contact manifold generation and maintenance.

... it is possible to perform direct clipping to get all points at a time, still using GJK. Basically ODE and other libraries first determine the separating axis, and then clip/project the most parallel features for this axis. This can be done using GJK or SAT.

Do you have any links to papers on this?

In 2002 on comp.graphics.algorithms John Nagle describes the projection on the separating plane and then the 2D contact clipping method:
http://groups.google.co.uk/group/comp.g ... 17f95d39db

What you want is the "contact polygon".
For two nearby, non-intersecting convex polyhedra, here's
the algorithm.

1. First, get from GJK (inside SOLID) the final simplex from
the GJK algorithm. This defines the closest set of features
for the two nearby bodies. Each body will have one, two,
or three points in the simplex. A body with one point
indicates the closest point is a vertex. A body with three
points indicates the closest point is in the interior of
a face. A body with two points indicates either that the
contact is along an edge or on a diagonal of a face.


2. With this data extracted, for each face, find the
"most parallel face" for each object. This is the
face most perpendicular to the line through the
closest points reported by GJK. If the GJK simplex
defined a face, that's the face. If it defined a
vertex, pick the most parallel face of those meeting
at that vertex. If the simplex defined an edge, pick
the most parallel face that includes that edge. The
output of this step is two faces, one on each body.


3. Project both faces from the previous step onto the
plane which goes through the midpoint of the line segment
between the closest points, and is perpendicular to
that line. This yields two convex polygons in a plane.


4. Compute the intersection of those two convex polygons.
This is the contact polygon.


This is all straightforward geometry and bookkeeping. Check
those GJK simplicies, though; if you get a simplex that has
points from more than one face, you've found a problem
with GJK (roundoff errors can occur) or the original geometry
wasn't convex. The input geometry should not have coplanar
faces. So don't tesselate your convex hulls. When you
have a cube on a bigger cube, you want a square contact
polygon, not a triangle.


John Nagle


Animats

Some discussion on this forum:
http://www.continuousphysics.com/Bullet ... c.php?t=39
Bullet contains an implementation (contributed by Simon Hobbs) of this projection/intersection for convex polyhedra in Extras/SATConvexCollision/Hull.cpp see

Code: Select all

int Hull::AddContactsHullHull(btSeparation& sep, const Point3* pVertsA, const Point3* pVertsB,
									   const Transform& trA, const Transform& trB,const Hull& hullA,const Hull& hullB,
									   HullContactCollector* hullContactCollector)
{
...
}

Jan Bender offered another recent contact generation/clipping method, I haven't found the time to integrate it into Bullet yet. Kenny Erleben's book Physics Based Animation discusses some other contact generation methods.
Erwin

[dog]

Doesn't seem so hot for implicit surfaces. The references all seem to care about whether you have face or edge features in the remaining simplex. I suppose you would have to classify the source of the vertex somehow (for a cylinder side, it would be a line from top to bottom). Sounds like a lot of book-keeping.

[Erwin Coumans]

Indeed, this clipping method assumes convex polyhedra. In Bullet I'm using the contact caching and reduction method, and I'm happy with the results for both convex polyhedra and implicit convexes. The CcdPhysicsDemo shows stable implicit cylinders stacking. I'll add the clipping method as a comparison.

Doesn't seem so hot for implicit surfaces. The references all seem to care about whether you have face or edge features in the remaining simplex. I suppose you would have to classify the source of the vertex somehow (for a cylinder side, it would be a line from top to bottom). Sounds like a lot of book-keeping.

[Erwin Coumans]

Here is my code in Bullet 2.18a.
If a single box rests on the ground box, everything seems fine. However, for bigger stacks, things go crazy. The behavior is the same with both SOR_LCP and impulse approaches. The problem is definitely in my code.

I haven't had the time yet to add the box-box comparison code in the Extras folder of Bullet (I have some old code that works, should take about an hour or so to update).

Have you checked this:

* is the normal pointing from B towards A in worldspace?
* is the penetration depth negative when overlap (positive distance means separation in Bullet)
* are the contact points in world space?

Thanks,
Erwin

[Erwin Coumans]

Hi Andrei,

Bullet 2.19a has a comparison collision algorithm in Extras/AlternativeCollisionAlgorithms/

There is also a native Bullet btSphereTriangleCollisionAlgorithm in src/BulletCollision/CollisionDispatch.

Have fun,
Erwin