accuracy of collision detection: Bullet vs. Solid

[rusin]

Hi!

I have to create the multibody simulation environment combining matlab/simmechanics and some of the existing collision detection software. Until now I have tested the collision detection functions from Vortex, Swift and Solid. Now I'm going to implement the same things with the Bullet. The last release of the Swift was made on 2001, of the Solid 3.5 on 2004, and of the Bullet 2.4 on 2006. Has the date of release any relations to accuracy of collision detection functionality (difference between GJK, EPA, SAT algorithms)? And what is about the Bullet in comparison with for example the Solid?

Thanks in advance.

[Erwin Coumans]

It probably all depends on the testcase.
Both libraries are still being improved, so so if accuracy is your biggest issue you might want to contact Gino van den Bergen, see http://www.dtecta.com

There are some cases that Bullet 2.4 accuracy is better then Solid 3.5:
Bullet contains a EPA testbed in Bullet/Demos/EPAPenDepthDemo, provided by Pierre Terdiman. I fixed some issues that makes Bullet's penetration depth solver work better for this testcase compared to Solid. In short, it propagates a generate case in the simplex solver, and tries to improve the results for those.

Another accuracy improvement (that is easy to built into Solid 3.5 too) is that Bullet performs all GJK calculations in a space, local to both objects. This improves accuracy when testing two closeby objects that are far from the origin.

There are some good performance improvements in Bullet Playstation 3 version, that will be integrated into the public version.

Hope this helps,
Erwin

Hi!

I have to create the multibody simulation environment combining matlab/simmechanics and some of the existing collision detection software. Until now I have tested the collision detection functions from Vortex, Swift and Solid. Now I'm going to implement the same things with the Bullet. The last release of the Swift was made on 2001, of the Solid 3.5 on 2004, and of the Bullet 2.4 on 2006. Has the date of release any relations to accuracy of collision detection functionality (difference between GJK, EPA, SAT algorithms)? And what is about the Bullet in comparison with for example the Solid?

Thanks in advance.

[rusin]

Erwin, thank you for the good state-of-the-art explanation.

Concerning the Bullet/Demos/EPAPenDepthDemo I can not compile this application even if I add all necessary .cpp files from Bullet/Extras/Epa and from Bullet/Extras/ExtraSolid35 because of the some strange errors by compiling the virtual "calcPenDepth" function
( can not make instance from the abstract classes:
#ifdef COMPARE_WITH_SOLID35_AND_OTHER_EPA
static Solid3EpaPenetrationDepth Solver2;
static EpaPenetrationDepthSolver Solver3;
#endif ).

[Erwin Coumans]

Thanks for pointing this out, the comparison code should be updated.

The interface got one new parameter at the end, so just add

Code: Select all

btStackAlloc* stackAlloc

to the interface/implementation of

Code: Select all

bool Solid3EpaPenetrationDepth::calcPenDepth( btSimplexSolverInterface& simplexSolver,
		btConvexShape* convexA,btConvexShape* convexB,
					const btTransform& transformA,const btTransform& transformB,
				btVector3& v, btPoint3& pa, btPoint3& pb,
				class btIDebugDraw* debugDraw,btStackAlloc* stackAlloc
				)

Code: Select all

/// Solid3EpaPenetrationDepth contains the 'Expanding Polytope Algorithm' from Solid 3.5
class Solid3EpaPenetrationDepth : public btConvexPenetrationDepthSolver
{
public:

		virtual bool calcPenDepth( btSimplexSolverInterface& simplexSolver,
		btConvexShape* convexA,btConvexShape* convexB,
					const btTransform& transA,const btTransform& transB,
				btVector3& v, btPoint3& pa, btPoint3& pb,
				class btIDebugDraw* debugDraw,btStackAlloc* stackAlloc
				);

};

Just add the following two projectfiles, and make this appEPAPenDepthDemo dependend on those projects

bullet\msvc\8\libExtraSolid35.vcproj
bullet\msvc\8\libEPA.vcproj

(replace 8 by your version)

It will be fixed in upcoming version of Bullet,
Hope this helps,
Erwin

PS: this is my own integration of Solid 3.5, but I might have introduced issues. For any serious purposes, I encourage to re-do the comparison on your own. Also, please don't use Bullet for anything dangerous or life-threatening: it has been designed for game-applications, where an inaccuracy has limited effect.

[rusin]

Hi, Erwin!

You have definitely compared various collision detection algorithms on speed and robustness. Earlier I thought, that the GJK and GJK-based EPA are better algorithms than algorithms from the group of University of North Carolina at Chapel Hill for this goal (after the article of Gino van den Bergen: our GJK implementation detects intersections between convex polyhedra roughly five times faster than the implementation of the Lin-Canny closest-feature algorithm used in I-COLLIDE).

Recently I have found the article "Incremental Penetration Depth Estimation Between Convex Polytopes Using Dual-space Expansion. Young J. Kim, Ming C. Lin and Dinesh Manocha. 2002" in which the comparative analysis is given and shows, that DEEP algorithm is much more faster and robuster that EPA. However the source code of DEEP is also from 2002.

Do you know the recent state-of-the-art concerning this DEEP package?

Thank you in advance!
rusin.

[Erwin Coumans]

Hi Rusin,

Here are several of my thoughts about your topic:

* The paper is outdated, and makes some outdated/incorrect claims in my opinion: EPA is not an approximation, it can calculate the penetration depth within a given tolerance. Gino's original EPA paper & implementation had a big flaw: the expanding polytope was not kept convex. This has been fixed in his recent book, which is newer then that paper.

* The performance usually becomes more important when you need a lot of objects. In such cases, the broadphase implementation (finding potential overlapping pairs) and the overlapping pair management is more important then the narrowphase (GJK/SAT). The total number of pairs grow O(n^2), where the actual overlapping pairs are only growing O(n) when object sizes are similar: objects don't have more then 6 neighbours usually.

* GJK and EPA are succesfully used in practice by many, Havok is using it (search for GJK and expanding polytope in their recent Havok CCD patent application 20060149516, Bullet 2.44a GJK and EPA colision seems to work fast and robust (as long as you use it properly, avoid extremely small/big objects, set the collision margins), and many games shipped using GJK collision detection.

* robustness and performance depends on many aspects. For example, in Bullet the collision detection is performed in relative space (close to the origin) where the floating point precision is much higher. Solid and others perform the collision detection in world space, and loose a lot of precision.
Also, implementation details have a big impact on performance, in particular being cache friendly. You can get a 10 times speedup using the same algorithm, so comparing two algorithms and telling one is 5 times faster is not so useful in my opinion.

* Using hybrid GJK-EPA with a margin, you hardly ever get into deep penetration, so the performance/robustness is mostly determined by GJK and not EPA. Please check out Bullet 2.44a, and run the CcdPhysicsDemo. The number of 'deep penetrations' (EPA) is showed at the screen, and stays very low. Several game implementations use GJK with an ad-hoc / brute force penetration depth algorithm, because it is hardly used (see Bullet 'minkowsky depth penetration depth solver).

Do you know the recent state-of-the-art concerning this DEEP package?

FAST + Swift++ are more recent UNC collision packages. You can download FAST collision library build on top of the included Swift++ collision library. Please feel free to make a comparison with Bullet 2.44a or later and let us know the results.

Thanks a lot for the feedback,
Erwin

[Etherton]

I think you should also mention that those bullet points are not facts, they are your own personal opinions, and it is unlike they have any base on any rigorous analysis.

[Christer Ericson]

I think you should also mention that those bullet points are not facts, they are your own personal opinions, and it is unlike they have any base on any rigorous analysis.

I see nothing objectionable in Erwin's post, which Erwin very clearly marked as "my thoughts" at the start of the article. If you have any particular objections with Erwin's post, instead of taking potshots, why not express your concerns along with some well-thought out arguments. Your abrasive and antagonistic posts are uncalled for.

[Etherton]

In hindsight everything is always better. The post was edited.
Basically it was stating that collision in bullet is better than collision in any other package (other than Havok and Physx) implementing closest feature algorithm, which is simple false.
Perhaps if you read the post carefully you will see that the phase ?my though? along with reformulation of the points happened after I made the observation.

[Erwin Coumans]

No Etherton/Jovani Cassini, I haven't changed a single character in any of the points.

I just changed the intro sentence from

Here are several thoughts about your topic

into

Here are several of my thoughts about your topic

Please discuss the specific points you don't agree with, and be a man and post with your real name. Like you did in this posting.
Erwin

[Erin Catto]

I actually implemented something very similar to DEEP. Unfortunately it doesn't work in general because incremental searches can get trapped at local minima. The examples in their paper are designed to converge. They take spheres and sprinkle hundreds of points on them to form fat polytopes. Incremental algorithms converge well for those cases. Problems arise when you have long and thin polytopes.

[Suslik[PGS]]

Hello, Erwin.
You said:

Gino's original EPA paper & implementation had a big flaw: the expanding polytope was not kept convex. This has been fixed in his recent book, which is newer then that paper.

Where could I find this new book? It seems very interesting to me.

I actually implemented something very similar to DEEP. Unfortunately it doesn't work in general because incremental searches can get trapped at local minima

Please, may we discuss this problem? I'm finding fast enough incremental alghorithm and local vs global convergence is its weakness.

[Erin Catto]

Please, may we discuss this problem? I'm finding fast enough incremental alghorithm and local vs global convergence is its weakness.

What is your question? Like I said, I don't think this algorithm will work. It is basically a separating axis test with a local search. Local searches for the minimum separating axis fail because the problem is non-convex.

[Suslik[PGS]]

What is your question? Like I said, I don't think this algorithm will work. It is basically a separating axis test with a local search. Local searches for the minimum separating axis fail because the problem is non-convex.

But it's very important to choose initial axis. Are there any cases when alghorithm gets struck with initial choise as "centriod difference" axis?

[Dirk Gregorius]

Local searches for the minimum separating axis fail because the problem is non-convex.

What do you mean with this? Any example?