Real-Time Physics Simulation Forum

Box vs. Box primitive collision in Bullet ?

2006-10-28T02:42:07+00:00

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

Statistics: Posted by Erwin Coumans — Sat Oct 28, 2006 2:42 am

Box vs. Box primitive collision in Bullet ?

2006-10-27T15:35:13+00:00

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

Statistics: Posted by Erwin Coumans — Fri Oct 27, 2006 3:35 pm

Box vs. Box primitive collision in Bullet ?

2006-10-26T01:13:06+00:00

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.

Statistics: Posted by Erwin Coumans — Thu Oct 26, 2006 1:13 am

Box vs. Box primitive collision in Bullet ?

2006-10-26T01:09:57+00:00

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.

Statistics: Posted by dog — Thu Oct 26, 2006 1:09 am

Box vs. Box primitive collision in Bullet ?

2006-10-26T00:45:27+00:00

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:

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

Statistics: Posted by Erwin Coumans — Thu Oct 26, 2006 12:45 am

Box vs. Box primitive collision in Bullet ?

2006-10-25T20:30:09+00:00

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?

Statistics: Posted by dog — Wed Oct 25, 2006 8:30 pm

Box vs. Box primitive collision in Bullet ?

2006-10-25T14:07:09+00:00

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:

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 vectorsP0[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 alloweddContactGeom 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; iaddContactPoint(SIMD_normal, SIMD_pos, -contacts[i].depth);}}

Statistics: Posted by andrei.lupas — Wed Oct 25, 2006 2:07 pm

Box vs. Box primitive collision in Bullet ?

2006-10-23T15:07:08+00:00

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

Statistics: Posted by Erwin Coumans — Mon Oct 23, 2006 3:07 pm

Box vs. Box primitive collision in Bullet ?

2006-10-23T15:04:53+00:00

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.

Statistics: Posted by andrei.lupas — Mon Oct 23, 2006 3:04 pm

Box vs. Box primitive collision in Bullet ?

2006-10-23T15:01:22+00:00

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

Statistics: Posted by Dirk Gregorius — Mon Oct 23, 2006 3:01 pm