Problem with convexSweepTest

[nokkie]

Hello, I'm currently using bullet 2.7.5 and I've been having trouble using convexSweepTest called from my btDiscreteDynamicsWorld. I've been calling it with a capsule shape (in a 2D world if that makes any difference) but it seems to give an inaccurate result once every 100 times or so. It was very strange.

I traced the problem down to the gjk algorithm, specifically the "btGjkPairDetector::getClosestPointsNonVirtual()" function. For some reason, every once in awhile it would say that there was no collision even though the frame before would report that there was a collision and the frame after it would also report that there was a collision and there would be virtually no change in the 3 frames. It looks like the problem has been noticed before though because I have noticed a lot of printf's and debugging lines based around 2d convexes, but I'm not sure.

The problem is further traced down to the simplex solver, when it adds a vertex in line 222 of btGjkPairDetector.cpp, occasionally it would add a w that would be extremely close (but not exactly the same, maybe 0.00001 off) to another vertex that already exists within the simplex solver, which causes the simplex solver to fail when it tries to solve minimum Minkowski difference.

I was able to fix (hack) the problem by modifying btVoronoiSimplexSolver::inSimplex() in btVoronoiSimplexSolver.cpp from

Code: Select all

290>for (i=0;i<numverts;i++)
291>{
292>	if (m_simplexVectorW[i]==w)
293>		found = true;
294>}

to

Code: Select all

290>for (i=0;i<numverts;i++)
291>{
292>	if ( m_simplexVectorW[i].distance2(w) < 0.0001f )
293>		found = true;
294>}

This way, when it detects that a vertex really close already exists, it will assume it's the same vertex and we have already found the minimum solution. I'm not sure if this is the best solution, but it works for all of my purposes at least. If anyone could chime in and expand upon what could cause this in the gjk algorithm, that would be great.

[Erwin Coumans]

Thanks for the report and tracing it down.

I created this issue, perhaps we can apply your fix, but use a relative threshold (based on collision shape/aabb sizes).
http://code.google.com/p/bullet/issues/detail?id=305

Thanks!
Erwin