Multi SAP implementation/timings

Post Reply
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Multi SAP implementation/timings

Post by Erwin Coumans »

I just finished the first working version of Bullet Multi-SAP, a dynamic spatial datastructure that I brought up here and futher discussed and implemented by Pierre Terdiman here.

It was tested inside Pierre Terdiman's CDTestFrameWork, with OPCODE Boxpruning, Bullet SAP and Bullet Multi-SAP.
In a nutshell:
  • The performance of Multi-SAP should become much better: this initial implementation has excessive overhead due to finding/adding/removing objects from the child broadphases: it uses an AABB tree to find the overlapping child broadphases, rather then a grid.
  • The Multi-SAP performance is currently better then SAP above 4096 objects when at least 10% objects move (0.01 in above testbed).
  • As soon as you have a lot of objects (above 4096), with around 10% moving, SAP and Multi-SAP is much faster then Box Pruning.
  • Multi-SAP uses currently btSortedOverlappingPairCache, with deferred removal, so pairs are not removed by the broadphase. Instead, pairs that are no longer overlapping are removed during pair traversal, using an additional check. Sorting deals with duplicats too.
  • The regular SAP uses btHashedOverlappingPairCache (re-using Pierre's work).
  • As Pierre already mentioned in his SAP document, this can be nicely parallelized (on SPU, multi-core etc), especially when the pair cache is not shared.
Broadphase comparison
//Static case (updating 10% of objects to same position ( -> no swaps)
//number of objects :OPCODE BoxPruning : Bullet SAP : Bullet MultiSAP
//1024: :0.35ms : 0.03ms : 0.15ms
//8192: :21ms : 0.2ms : 5ms
//16384: :92ms : 0.5ms : 28ms

//Dynamic case, 10% objects are moving as fast as this testbed allows (0.01?)
//number of objects //OPCODE BoxPruning / Bullet SAP / Bullet MultiSAP
//1024: 0.35ms, 0.2ms, 0.25ms
//8192: 21ms , 15ms , 13ms
//16384: 92ms, 80ms, 49ms
multisap_comparison.png
multisap_comparison.png (24.13 KiB) Viewed 7376 times
You can download binary Multi-SAP demo and source code here.

Thanks Pierre for the test. It helped me finding a few bugs that caused this issue of 'additional' pairs you mentioned in this earlier posting.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Multi SAP implementation/timings

Post by Dirk Gregorius »

It helped me finding a few bugs that caused this issue of 'additional' pairs you mentioned in this earlier posting.
Are/were these bugs also present in the current Bullet SAP implementation and if yes are the fixes already checked into SVN? Can you elaborate a bit about these bugs?


Cheers,
-Dirk
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Multi SAP implementation/timings

Post by Erwin Coumans »

Dirk Gregorius wrote:
It helped me finding a few bugs that caused this issue of 'additional' pairs you mentioned in this earlier posting.
Are/were these bugs also present in the current Bullet SAP implementation and if yes are the fixes already checked into SVN? Can you elaborate a bit about these bugs?
  • The array for storing broadphase handles in btAxisSweep3 already contained one handle used as sentinel, so we had to allocate one more handle to fit all user proxies. So this bug affects only users who fill up the broadphase with the maximum number of handles, due to array overflow.
    This has been fixed in latest SVN, located at googlecode (not sourceforge anymore).
    See line 278, where is starts with handle ID 1, because handle 0 is the reserved sentinel.
    http://code.google.com/p/bullet/source/ ... isSweep3.h
    Line 250 contains the fix, reserving one more then the user specified maximum handles.
  • Other bug was related to btMultiSapBroadphase, a btBroadphaseProxy used a union to either store a pointer to the parent (m_multiSapParentProxy) or m_collisionFilterGroup/m_collisionFilterMask. This data re-use is very error-prone, so we removed the union, so each proxy carries the extra 4 bytes of data for now.

The Multi-SAP is very promising, especially when you take away the current overhead/bottlenecks from Intel VTune:
MultiSapPerformance.png
MultiSapPerformance.png (33.73 KiB) Viewed 7036 times
See detailed timings here:
http://spreadsheets.google.com/pub?key= ... GyOSii3YSA

The sorting (downHeap) can be replaced by a reference-counted btHashedOverlappingPairCache (to deal with multiple add/remove of child SAPs). Once that is fixed, the next improvement is to improve the cost of search which child SAPs a proxy belong to. Instead of a AABB tree (for adding to a child SAP) and AABB check (to remove/check if the childSAP is still overlapping), a set of 'selection SAPs' can be used. Not one big SAP obviously, because then you are back to the beginning problem.

Thanks,
Erwin
sanjuly
Posts: 2
Joined: Fri Jun 25, 2010 2:29 am

Re: Multi SAP implementation/timings

Post by sanjuly »

What is the best tip for a SAP Fresher to get a job ? The SAP market is a tough market for consultants : You need at least 3 years of relevant SAP experience to get any project. A SAP fresher (no experience) will not find a job because he is a fresher. So what tip can you give him to find a job ?
___________________________
affiliateelite ~ affiliateelite.com ~ adgooroo ~ adgooroo.com
Post Reply