Simulation Islands

[Jondolf]

Simulation Islands are a fundamental low-level performance optimization feature for physics simulations. They can have a massive impact on solver design and performance, both for single-threaded and multi-threaded applications.

What Are Simulation Islands?

Islands are essentially graphs where rigid bodies are nodes, and constraints (contacts and joints) are edges. Each body belongs to one island, with the exception of static bodies, which can and should be shared between islands, because nothing affects their position or velocity.

Islands have two primary purposes:

1. Sleeping and waking

Currently, we have very bad per-body sleeping, which is only enabled for dynamic bodies that are not in contact with other dynamic bodies. Per-body sleeping for piles of bodies can easily lead to overlap, instability, and various other artifacts.

Sleeping should be handled at the island level.

2. Parallel constraint solver

Islands are distinct, and bodies in one island cannot interact with bodies in any other island. This means that each island can be solved in parallel, independent of each other. This could yield significant performance gains for typical game worlds where bodies are scattered around, with some small piles here and there.

Parallel simulation islands are not a silver bullet however, and they do still struggle with large islands, where constraints must be solved serially. The solution to large islands is graph coloring, but it has its own complexity and overhead, so I think it's better to start with a parallel island solver.

I heavily recommend reading Erin Catto's article on Simulation Islands for more information.

Implementation

There are at least a few different approaches to consider for island management:

• Depth-first-search (not parallel)
• Parallel union-find (not deterministic)
• Persistent islands

We might explore a few different options, but I think we should implement parallel persistent islands, as outlined in Erin Catto's article.

At a high level:

• Each dynamic body has its own island
• When a constraint between two bodies is created, their islands are merged with a serial union-find algorithm
• When a constraint is removed, its island is marked as a candidate for splitting with a depth-first search (or union find)
  • Unlike merging, splitting can be deferred, and performed based on some heuristic. For example, only splitting at most one island per frame, choosing the largest island.

This likely also involves reworking the narrow phase to be deterministic even when multi-threaded, and using bit arrays to efficiently indicate edge addition and removal. The exact implementation details can be decided on when implementing the algorithm.

I expect this to require some pretty large refactors for the solver. We may need to reduce the many individual systems in the solver into one, to avoid having to spin up tasks and iterate over islands many times, or figure out some ECS magic. I think it'll be worth it though.

Other Considerations

There seems to be some vague overlap between these "simulation islands" and proximity-based "physics islands" with big_space for simulating groups of entities independently with different frames of reference. It could be interesting to consider how the two could interact. For example, could we use simulation islands to accelerate the neighbor-search in big_space for physics entities?