Objective

Closes #578.

Sleeping and waking are crucial for reducing CPU overhead for large game worlds. Up until now, Avian has used basic per-body sleeping that only allows sleeping for dynamic bodies that are not in contact with each other and not connected via joints. This means that object piles and joints are never allowed to sleep.

The standard solution to this problem is simulation islands. Bodies that are touching or connected by a joint belong to the same island, and can only sleep if the whole island can sleep. Conversely, if any dynamic body in an island is woken up, the whole island is woken up.

Solution

Implement persistent simulation islands for sleeping and waking. Islands are persisted across time steps, merged when constraints are added between different islands, and split heuristically in a deferred manner.

The below video displays the combined bounds of each body in each island as a red bounding box. When islands are marked as sleeping, the outline becomes darker.

Implementation

The island implementation is primarily based on Erin Catto's Simulation Islands article and Box2D.

• Each dynamic body starts with its own PhysicsIsland, stored in the PhysicsIslands resource.
• Bodies, contacts, and joints form island linked lists with an IslandNode stored in each BodyIslandNode component, ContactEdge, and JointEdge.
• When a constraint between two dynamic bodies is created, their islands are merged with a serial union find.
• When a constraint is removed, PhysicsIsland::constraints_removed is incremented.
• At each time step, the sleepiest island with one or more constraints removed is chosen as a split_candidate, and split using DFS. Splitting is expensive, but it can safely be deferred and done heuristically like this.

Sleeping and Waking Changes

For a body to fall asleep, its whole island must be able to sleep. A body and its island are woken up when any of the following happens:

• An awake body collides with a sleeping body.
• A joint is created between an awake body and a sleeping body.
• A joint or contact is removed from a sleeping body.
• The Transform, LinearVelocity, or AngularVelocity of a sleeping body is modified.
• A constant force component of a sleeping body is modified.
• A force, impulse, or acceleration is applied via Forces, without using non_waking.
• The Gravity resource or GravityScale component is modified.

A body and all bodies connected to it can also be forced to sleep or wake up using the SleepBody or WakeBody commands, or by using the SleepIslands or WakeIslands commands.

The SleepingPlugin has been replaced by the IslandSleepingPlugin. It uses an AwakeIslandBitVec to track which islands should be kept awake, and updates sleep timers and splitting candidates.

Additionally, I renamed some components for clarity and consistency:

• TimeSleeping -> SleepTimer
• SleepingThreshold -> SleepThreshold
• DeactivationTime -> TimeToSleep (also a component and not a resource now)

Alternatives

In this PR, I have implemented persistent simulation islands. This implies caching state. For a "stateless" solution, islands could also be built from scratch each frame with a depth-first search or union-find algorithm.

Based on Erin's results, persistent islands can be roughly an order of magnitude faster than building islands from scratch with DFS. A decent alternative could be Jolt's parallel union find algorithm, but it appears to require expensive sorting for determinism.

Still, in the future, we could look into a stateless alternative alongside the persistent one, for cases where that may be desirable, such as rollback or scrubbing through time.

Note on Parallelism

While simulation islands can also be used for solver parallelism, we only use them for sleeping and waking, similar to Box2D. Graph coloring (#771) is used for the multi-threaded constraint solver.

Migration Guide

Stacks of bodies as well as bodies connected by joints now form "simulation islands" that are allowed to enter a low-cost sleeping state when all bodies in a given island are resting. This can significantly reduce CPU overhead for large game worlds with lots of dynamic bodies. Previously, bodies were only allowed to sleep when they were not interacting with other dynamic bodies.

The following components have been renamed:

• TimeSleeping -> SleepTimer
• SleepingThreshold -> SleepThreshold
• DeactivationTime -> TimeToSleep (also a component and not a resource now)

Additionally, the SleepingPlugin has been replaced by the IslandSleepingPlugin.