I recently posted an article from last year, about the “sweep and prune” algorithm. I previously posted it on the Bullet forums but couldn’t upload it on CoderCorner for technical reasons.
Today, I finally found some time to put the source code together, extract it from ICE, and upload it as well. So, here it is. It’s an efficient implementation of an array-based sweep-and-prune. It should be fast. In my tests I found it faster than my previous version from OPCODE 1.3, and also slightly faster than the PhysX implementation. For technical details about this new version, please refer to the document above.
The library doesn’t support “multi-SAP” yet, I will need to find more time to seat and re-implement that in a releasable form. Oh well, later.
February 16th, 2008 at 7:38 pm
I just compared your SAP to mine on 30000 boxes using the same initial random number generator and also using the same settings for USE_WORDS and USE_INTEGERS. I also disabled call backs for new/removed pairs in your code because I don’t do that. For 10 iterations your code wins by .00167% (1798535 vs. 1801547). That is pretty amazing.
February 16th, 2008 at 7:51 pm
Oops, that is .167%, still pretty amazing considering they are totally independent implementations.
February 17th, 2008 at 9:19 am
Hey Pierre,
Good to see you blogging!
Your suggestion of using hashtable for pair management is now default in Bullet, with ’sorted pairs’ as second option. I think sorted pairs makes it a bit easier to support multi-sap, but I haven’t looked deeper into multi-sap either yet.
Did you measure how your SAP compares to latest Bullet SAP?
Cheers,
Erwin
February 17th, 2008 at 9:34 am
Hi Erwin! No, I haven’t looked at Bullet recently…
February 19th, 2008 at 2:27 am
Cool… Its good to see some SAP brilliant quality piece of code. And it would be good to see you impl of dynamic aabb tree)
March 13th, 2008 at 2:58 pm
Nice doc. But not sure I would agree about a hashtable for pair tracking being inferior to a list/array.
What I found was that a hash table was better in artificial tests when it stayed in the cache but the random access pattern was bad when it was large and there was cache pressure(eg from another thread on the same core). The profiles I did indicated that a list of (small) arrays had much better cache coherancy and allowed the index checks to be vectorized.
March 14th, 2008 at 1:24 am
Is that you, Dave? Nice to see you here
I guess it depends on the context / scenario. Bullet also switched from list/array to a hash table, but I don’t know how much they tested it against “real world” scenarios. In my tests, the hash table was faster. On another platform with multiple cores and inferior caches, I suppose things would be different. But maybe I wouldn’t even use SAP there? My favorite is still the brute-force box pruning for example.
March 14th, 2008 at 4:12 am
Yeah, afraid to say its me…
Currently I am messing around with hash tables for objects, but in the reverse to the multi-SAP thingy. Ie hash tables are defined for each asset/world chunk.
April 7th, 2008 at 2:45 am
[...] people have had troubles with the previously posted SAP code, claiming that it was crashing when deleting objects. As it turned out, they were incorrectly using [...]