Bug in btSubsimplexConvexCast

[Dirk Gregorius]

I created the following setup:

Shape A:
Pyramid shape with height = 2 and width = 1. The origin is located at 0.25 * height.

Shape B:
Triangle shape with vertices (0,1,0), (-1,-1,0) and (1,-1,0)

Both shapes have identity orientations at their source and target positions. This means there is no relative rotation. The first shape is initialized at (0,5.5,0) and moves down to (0,1.5,0). The other shape is initialized at (0,0,0) and moves up to (0,4,0). I should also note that I used btConvexHullShape for both shapes.


Basically the distance between both shapes is 4m and they travel 8m relative to each other. This means the TOI should be 0.5. My code returned the wrong result, so I reproduced the setup in Bullet and I get the same error. So I wonder if something is wrong with the original algorithm? What seems to happen is that directly in the first iteration the origin is found. I tried to visualize the test case, but Bullet's debug functionality is very limited. Anyway, the visualization matches the actual result so you should get the idea.

I created at test case in Bullet which I attach to this message. So you can look for yourself. Maybe it is something simple, like not using the API correctly. I needed to change three files. You might consider keeping the btConvexHull.h file since it was not const correct and I needed to fix this...


Cheers,
-Dirk

[Dirk Gregorius]

The funny thing is that if you use a box shape with the same quadratic bottom face and same setup you get the correct result. Just replace (copy/paste) the pyramid setup with the below code if you are interested:

Code: Select all

float ex = 1.0f;
float ey = 0.5f;
float ez = 0.5f;

shapeA->addPoint( btVector3( -ex, -ey,  ez ) );
shapeA->addPoint( btVector3(  ex, -ey,  ez ) );
shapeA->addPoint( btVector3(  ex,  ey,  ez ) );
shapeA->addPoint( btVector3( -ex,  ey,  ez ) );
shapeA->addPoint( btVector3( -ex, -ey, -ez ) );
shapeA->addPoint( btVector3(  ex, -ey, -ez ) );
shapeA->addPoint( btVector3(  ex,  ey, -ez ) );
shapeA->addPoint( btVector3( -ex,  ey, -ez ) );

[Erwin Coumans]

If you replace the convexCaster by the btGjkConvexCast it works fine (this is the basic convervative advancement, without merging the CA and GJK loop as done in btSubsimplexConvexCast).

And if the convex shape is centered around the origin it works fine too:

Code: Select all

	btConvexHullShape* shapeA = new btConvexHullShape;
	shapeA->addPoint( btVector3( 0.0f,  0.50f * h, 0.0f ) );
	shapeA->addPoint( btVector3(   -r, -0.5f * h,    r ) );
	shapeA->addPoint( btVector3(    r, -0.5f * h,    r ) );
	shapeA->addPoint( btVector3(    r, -0.5f * h,   -r ) );
	shapeA->addPoint( btVector3(   -r, -0.5f * h,   -r ) );

I haven't had time to look into the issue with the btSubsimplexConvexCast, but I expect it to be an implementation problem, rather then algorithmic.

Thanks for the report!
Erwin

[Dirk Gregorius]

When I met with Gino he mentioned that he uses a new approach where he doesn't move the Minkowski sum anymore. Do you know how this works?

I know that the "centerer" pyramid works, but this is not a solution to the problem. The algorithm or implementation should work with any convex hull.

W.r.t the other method you mention I think I remember that this approach uses two nested iterative methods (CA and GJK), right? So this is not very tempting from a perfomance perspective.

I look into the problem tomorrow again and let you know if I find a solution.


Cheers,
-Dirk

[Erwin Coumans]

W.r.t the other method you mention I think I remember that this approach uses two nested iterative methods (CA and GJK), right? So this is not very tempting from a perfomance perspective.

I wouldn't exaggerate the performance difference, especially when all code and data fits in cache/local store (GJK typically uses less then 5 iterations), but I like to see issue bug fixed.

If you can help finding out what the issue is, that would be great.
Thanks for the feedback,
Erwin

[Erwin Coumans]

While writing a book section on conservative advancement, I got back to this issue and found the issue to be in the support mapping for the minkowski sum shape.

Support mapping for Minkowski sum/difference A-B should be Sa(v) - Sb(-v). It wrongly was Sa(v)+Sb(v), note the lack of minus signs.

Identical to using a minkowski sum shape is to directly use two separate support mapping calls, as is generally used in GJK:

Code: Select all

		supVertexA = interpolatedTransA(m_convexA->localGetSupportingVertex(-v*interpolatedTransA.getBasis()));
		supVertexB = interpolatedTransB(m_convexB->localGetSupportingVertex(v*interpolatedTransB.getBasis()));
		w = supVertexA-supVertexB;

It has been fixed in the bullet.googlecode.com repository, available in upcoming Bullet 2.68. In addition, the btSubsimplexConvexCast now returns the hitpoint.

Thanks Dirk for the reproduction case!
Erwin