Broad Phase Performance
Posted: Wed Jun 01, 2011 8:01 pm
Erwin: you suggested the following in another thread:
"Dynamic aabb tree based broadphase is better than multisap in general. Non-moving objects are free and it can handle moving objects better."
I did some work on sweep and prune a few years ago and have a nice implementation of MultiSAP. I decided to test it against the btDBVT broad phase and see how it fared. I used "scalability tests", where I increase the environment and object count until the broad phase reaches some set processing time (1/60th second in this case).
Now, I had to create an adapter for bullet broad phases to be used in my test framework, so there may be some issues there. Also, I'm making a reverse adapter that can plug my broad phases into Bullet, but there is some difficulty there so far.
Anyways, some test results on my 2.4 GHz Intel Core 2 Duo 15" MacBook Pro w/ 4 GB 667 MHz DDR2 SDRAM, Mac OS X 10.6.7, Xcode 3.2.6:
Bullet DBVT:
All moving: 7,000 objects in 1/60th second
1% moving (the rest static): 100,000 total objects in 1/60th second
100,000 objects, none moving, insertions & removals: 55 adds & 55 deletes in 1/60th second
Grid S&P (single thread):
All moving: 20,000 objects in 1/60th second
1% moving (the rest static): 450,000 total objects in 1/60th second
100,000 objects, none moving, insertions & removals: 530 adds & 530 deletes in 1/60th second
These tests utilize an "output all overlaps" interface for both broad phases, which is less efficient, but I'm still learning how Bullet's interface works. All other parameters are identical (density, velocity, etc). My implementation is a Grid with Sweep and Prune in each cell. The tests are all uniformly distributed objects so far. I should continue the work and make a more adaptive superstructure: the overhead of the mapping phase can be eliminated by use of a "triggered migrations" feature where I add just the bounding boxes of adjacent/parent spatial domains to each sweep and prune cell, allowing the sort to find objects that are migrating between spaces. There is also undone work on combining batch insertion/removal with segmented interval lists.
But the implementation is pretty efficient. It seems to scale fairly well in a multithreaded environment, as well. The broad phase is open source should be available at http://www.danieljosephtracy.com/. I haven't updated the site in some time, but I could clean up and post the testing framework as well if anyone's interested.
I'll have to look into the details of the DBVT algorithm, but my testing so far indicates that it's not as sensitive to objects transitioning between resting & moving states as I thought. It performs insertions & removals quickly, but what holds it up in that department is having to traverse the overlap set to find/remove pairs containing the object being removed. Ideally, the broad phase should determine algorithmically which overlaps exist and then find those specific pairs. That would be much faster, especially for environments with large numbers of objects.
Daniel
"Dynamic aabb tree based broadphase is better than multisap in general. Non-moving objects are free and it can handle moving objects better."
I did some work on sweep and prune a few years ago and have a nice implementation of MultiSAP. I decided to test it against the btDBVT broad phase and see how it fared. I used "scalability tests", where I increase the environment and object count until the broad phase reaches some set processing time (1/60th second in this case).
Now, I had to create an adapter for bullet broad phases to be used in my test framework, so there may be some issues there. Also, I'm making a reverse adapter that can plug my broad phases into Bullet, but there is some difficulty there so far.
Anyways, some test results on my 2.4 GHz Intel Core 2 Duo 15" MacBook Pro w/ 4 GB 667 MHz DDR2 SDRAM, Mac OS X 10.6.7, Xcode 3.2.6:
Bullet DBVT:
All moving: 7,000 objects in 1/60th second
1% moving (the rest static): 100,000 total objects in 1/60th second
100,000 objects, none moving, insertions & removals: 55 adds & 55 deletes in 1/60th second
Grid S&P (single thread):
All moving: 20,000 objects in 1/60th second
1% moving (the rest static): 450,000 total objects in 1/60th second
100,000 objects, none moving, insertions & removals: 530 adds & 530 deletes in 1/60th second
These tests utilize an "output all overlaps" interface for both broad phases, which is less efficient, but I'm still learning how Bullet's interface works. All other parameters are identical (density, velocity, etc). My implementation is a Grid with Sweep and Prune in each cell. The tests are all uniformly distributed objects so far. I should continue the work and make a more adaptive superstructure: the overhead of the mapping phase can be eliminated by use of a "triggered migrations" feature where I add just the bounding boxes of adjacent/parent spatial domains to each sweep and prune cell, allowing the sort to find objects that are migrating between spaces. There is also undone work on combining batch insertion/removal with segmented interval lists.
But the implementation is pretty efficient. It seems to scale fairly well in a multithreaded environment, as well. The broad phase is open source should be available at http://www.danieljosephtracy.com/. I haven't updated the site in some time, but I could clean up and post the testing framework as well if anyone's interested.
I'll have to look into the details of the DBVT algorithm, but my testing so far indicates that it's not as sensitive to objects transitioning between resting & moving states as I thought. It performs insertions & removals quickly, but what holds it up in that department is having to traverse the overlap set to find/remove pairs containing the object being removed. Ideally, the broad phase should determine algorithmically which overlaps exist and then find those specific pairs. That would be much faster, especially for environments with large numbers of objects.
Daniel