Add early-out optimizations to Bullet GJK's voronoi simplex solver

[GoogleCodeExporter]

For some ideas, see video and discussions here:

https://mollyrocket.com/forums/viewforum.php?f=13

Original issue reported on code.google.com by erwin.coumans on 1 Mar 2008 at 7:48

[GoogleCodeExporter]

I'm not sure if I can contribute something to this issue. I've just made some 
changes to class btVoronoiSimplexSolver to reflect the early-out optimization 
based on Casey's video (as the btVoronoiSimplexSolver.cpp attached). 

The major change is providing a new 
btVoronoiSimplexSolver::closestPtPointTriangle method which treats "c" as the 
newly added vertex to make things easy. When this new method is called within 
btVoronoiSimplexSolver::closestPtPointTetrahedron, the order of vertices should 
be adjusted to always place "d", the last added, on the rear.

The change is not completely follow Casey's tutorial which uses quite a few 
cross products (maybe just for straightforward representation there), instead, 
I borrow the way of the old code to utilize intermediate calculation results if 
possible.

I've done some simple test by SimplexDemo and CollisionDemo. However for the 
former, the new algorithm will fail. Because the new vertex on the simplex is 
not generated by searching the specific direction but directly from the 
tetrahedron, which doesn't fits GJK's situation. I also made a change to 
GL_Simplex1to4::calcClosest (as attached) to let this demo pass, but maybe this 
is not the best way:)

Original comment by Xiao.Clo...@gmail.com on 26 May 2011 at 12:29

Attachments:

• btVoronoiSimplexSolver.cpp
• GL_Simplex1to4.cpp

[GoogleCodeExporter]

I attached the patches for easy comparison.

Original comment by Xiao.Clo...@gmail.com on 26 May 2011 at 3:31

Attachments:

• btVoronoiSimplexSolver.cpp.patch
• GL_Simplex1to4.cpp.patch

[GoogleCodeExporter]

I haven't tried the patch yet, does it show any improvements in 
performance/robustness?

It is better to move this to Bullet 3.x, I created an issue 
here:https://github.com/erwincoumans/experiments/issues/1

Original comment by erwin.coumans on 1 Nov 2011 at 3:59

• Changed state: WontFix

[GoogleCodeExporter]

Hi Erwin, I have to say that no significant performance gain can be sensed when 
running a demo application (like I've tried AppBenchmarks, and no big jump to 
the fps shown out), because the voronoi solver may be not a bottle-neck. 

I've still done some simple profiling on just 
btVoronoiSimplexSolver::closestPtPointTriangle() which the optimization impacts 
most. When the early-out is taken, the time is about 15~30% less than before. 
But this is just the debug version. Below are two samples:

App_SimplexDemo:
        Time (ms)               Hit Count
No Early-out    14.4910501007868    22625
Early-out   9.84378838343094    22625
About 30% gain

AppLinearConvexCastDemo:
        Time (ms)               Hit Count
No Early-out    121.751363939225    173557
Early-out   99.781146963154     173636
About 18% gain

I modified the demo app a little to make it quits after running a certain 
number of frames. Since the early-out should just accelerate the algorithm but 
not change the behavior, the Hit Count should remain almost the same (the 
second sample has a small difference due to some precision errors).

Original comment by Xiao.Clo...@gmail.com on 2 Nov 2011 at 3:34

[GoogleCodeExporter]

It would be interesting to compare performance when using the Demos/Benchmarks 
(in optimized/Release build) and make sure in main.cpp it it set to #define 
benchmarkDemo benchmarkDemo4

Bullet has some build-in performance profiling, use CProfileManager::dumpAll 
after the stepSimulation. And while benchmarking, use a 
world->stepSimulation(1.f/60.f,0);

Original comment by erwin.coumans on 4 Nov 2011 at 5:38

[GoogleCodeExporter]

Hi Erwin, thanks for your tips, I've done some profiling using AppBenchmark 
(version 2.78) and CProfileManager.

I've to admit that there's indeed no much significant sign of performance gain 
overall. "btVoronoiSimplexSolver::closest" has about 10% increase (I added 
"BT_PROFILE" for this method). This method accounts for about 15% in one call 
of stepSimulation, so the overall gain is just about 1% and not easy to detect.

One thing unexpected is that the scene object have different trajectory than 
before, although still seems reasonable physically. Also, more calls (about 1%) 
of "btVoronoiSimplexSolver::closest" is counted. I tried debug version and 
double-precision but found the first diversion was caused by precision errors. 
I'm not sure how to verify correctness of my change (I've tried some basic 
algorithm apps, like AppSimplexDemo and AppCollisionDemo, and new program 
behaves the same as before). 

I attached the dump results, earlyout vs. noearlyout (I ran each a few times, 
and choose the middle value to attach here). I did not call dumpAll every step 
since this prints too much. I removed "startProfiling(timeStep)" in 
btDiscreteDynamicsWorld::stepSimulation, so to get an average time per-frame 
just at the end after 1000-step was done.

Original comment by Xiao.Clo...@gmail.com on 9 Nov 2011 at 11:45

Attachments:

• noearlyout.txt
• earlyout.txt

[GoogleCodeExporter]

I managed to find another machine to do the same benchmark. But this time, it 
is nearly impossible to see the performance gain after using the early-out 
optimization. Also, more amount of "btVoronoiSimplexSolver::closest" are called 
as the previous one. Now I want to first ensure the accuracy of my change, but 
still have no idea how...

Original comment by Xiao.Clo...@gmail.com on 7 Dec 2011 at 2:10