accuracy of collision detection: Bullet vs. Solid
-
- Posts: 3
- Joined: Tue Feb 20, 2007 5:34 pm
accuracy of collision detection: Bullet vs. Solid
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.
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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: accuracy of collision detection: Bullet vs. Solid
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
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
rusin wrote: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.
-
- Posts: 3
- Joined: Tue Feb 20, 2007 5:34 pm
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 ).
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 ).
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Thanks for pointing this out, the comparison code should be updated.
The interface got one new parameter at the end, so just add
to the interface/implementation of
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.
The interface got one new parameter at the end, so just add
Code: Select all
btStackAlloc* stackAlloc
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
);
};
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.
-
- Posts: 3
- Joined: Tue Feb 20, 2007 5:34 pm
DEEP package?
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.
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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: DEEP package?
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).
Thanks a lot for the feedback,
Erwin
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).
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.Do you know the recent state-of-the-art concerning this DEEP package?
Thanks a lot for the feedback,
Erwin
Last edited by Erwin Coumans on Wed Mar 07, 2007 11:38 pm, edited 1 time in total.
-
- Posts: 34
- Joined: Thu Aug 18, 2005 6:27 pm
-
- Posts: 23
- Joined: Mon Jun 27, 2005 4:30 pm
- Location: Los Angeles
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 wrote: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.
-
- Posts: 34
- Joined: Thu Aug 18, 2005 6:27 pm
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.
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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
No Etherton/Jovani Cassini, I haven't changed a single character in any of the points.
I just changed the intro sentence from
Erwin
I just changed the intro sentence from
intoHere are several 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.Here are several of my thoughts about your topic
Erwin
-
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
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.
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: accuracy of collision detection: Bullet vs. Solid
Hello, Erwin.
You said:
You said:
Where could I find this new book? It seems very interesting to me.Erwin Coumans wrote: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.
Please, may we discuss this problem? I'm finding fast enough incremental alghorithm and local vs global convergence is its weakness.Erin Catto wrote:I actually implemented something very similar to DEEP. Unfortunately it doesn't work in general because incremental searches can get trapped at local minima
-
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
Re: accuracy of collision detection: Bullet vs. Solid
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] wrote: Please, may we discuss this problem? I'm finding fast enough incremental alghorithm and local vs global convergence is its weakness.
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: accuracy of collision detection: Bullet vs. Solid
But it's very important to choose initial axis. Are there any cases when alghorithm gets struck with initial choise as "centriod difference" axis?Suslik[PGS] wrote: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.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: accuracy of collision detection: Bullet vs. Solid
What do you mean with this? Any example?Local searches for the minimum separating axis fail because the problem is non-convex.