Strategies for Simulation Islands

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Strategies for Simulation Islands

Post by sphet »

Hello,

I recognize there is a post from 2006 http://www.bulletphysics.org/Bullet/php ... ?f=4&t=543 about simulation islands, but I wondered about peoples opinions today about building simulation islands.

My engine currently uses union-find to rebuild the simulation islands every frame, effectively making islands persist for only long enough to split simulations down into parts and run them.

My environment has suddenly changed to a slower hand-held device with bad memory performance, so suddenly the iteration over a large number of sleeping bodies has started showing up in my profiler. Now I wonder if there isn't value moving island management out of simply the simulation step and make the island building/splitting persistent, and amortizable across multiple frames.

Given that broadphase implemented with AddOverlap/RemoveOverlap methods, we can use those pairs to merge islands along with adding general constraints. Keeping the list of islands split into two lists, active and sleeping, means the entire list of rigid bodies doesn't have to be traversed each frame. Furthermore, I imagine i can split islands periodically, in a round robin fashion, to amortize cost over multiple frames.

Before I jump into this further, I wonder if other people have any thoughts on island management strategies.

Best,

S
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Strategies for Simulation Islands

Post by Dirk Gregorius »

I don't use union find personally, but a simple Depth-First-Search (DFS) on the constraint graph. You can find example implementations of this both in Box2D and ODE. We compared both methods here and found union find four times slower. And the guy who implemented the UF really wanted to beat the DFS :). The nice thing about the simple DFS approach is that the islands are not persistent since you just build them from scratch. This reduces a lot complexity. Building the islands is already really fast (and never showed up in any profiling), but you can even start solving islands while finding the other ones which amortizes the cost.

Union find appears to be the right choice for this problem, but my practical experience showed me it is not.
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Re: Strategies for Simulation Islands

Post by sphet »

Dirk,

Thanks for the reply.

I have just replaced the Depth-First-Search with Union Find because DFS island building was showing up in the profile. Maybe there was just something in the implementation that was lacking. What do you use to track/stop loops with constraints given A overlaps B, B overlaps C, C overlaps A?

S
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Strategies for Simulation Islands

Post by Dirk Gregorius »

Well, you just set a flag on each body that is already part of an island and you don't expand islands over static bodies. I recommend looking into b2World::Solve(). IIRC this is where the islands are built. I cannot imagine any simpler implementation.

If you have very large scenes (e.g. > 10000 rigid bodies) iterating an array of pointers (or a linked list) can become significant. If you operate on these kinds of numbers you have to re-arrange your data in a more cache friendly way.

I just had a quick look at my engine and a typical test scene is dropping 3200 bodies onto a pile. The simulation time is spent in collision detection and solver. I cannot see the island builder taking any significant time. The same holds true for a test scene with many ragdolls on a triangle mesh that all build individual islands (the ragdolls are not colliding with each other). The time in the demo is also spent entirely in the collision detection and solver. The island builder doesn't show up here as well.

HTH,
-Dirk
Post Reply