I'm trying to incorporate a sleep system into my engine. I've tried several approaches so far, and they all had significant issues. The putting objects to sleep part is simple enough, just detect when they stop moving for a certain amount of time and flag them as sleeping, and skip contacts between two sleeping objects.

The hard part is when to wake them up. Obviously, waking up any object in contact with an awake object is not going to work, because they'd just keep waking each other up indefinitely. Instead, I made them set each other's "sleep" time to the minimum of the two, so eventually the whole island goes to sleep. This works pretty well, but in some cases it's pretty useless - for instance, if I make a very long chain of dominos and start collapsing it, then the end of the collapsed chain will always keep the whole thing awake even though 90% of it isn't moving, so eventually the simulation slows down significantly.

I've checked some simpler engines and another approach I found was to only wake up objects when the awake object in the pair exceeds certain velocity. However, this means that sometimes the solver will try to solve contacts between a sleeping and awake object, so I made it treat sleeping objects as stationary (infinite mass/momentum). This fixed the domino chain, but caused a much bigger issue in other simulations. Taking the newton cradle example (or any other scene where something collides into a group of resting objects), it simply can't propagate impulses through the chain of stationary balls - if the third ball in chain never moves (since the fourth ball is blocking it), it will never wake up the fourth ball.

It seems that the waking up checks need to be repeated every time a body's velocity changes during contact resolution. This means an object has to be waken up, it's contacts with adjacent sleeping bodies need to be re-activated and initialized (which involves collision checks and some additional computations) and added to the active contact list for subsequent resolution steps.

It sounds like it could work, but I'm not sure if I like the idea of mixing the collision and resolution stages. Am I on the right track here?

Maybe an all general solution might be inflexible for different islands. Maybe you can take all your different strategies and organize them into hints: SLEEPING, SEMI-SLEEPING, TIMER-SLEEPING, IMPULSEACTIVATED etc. 

You can even code a module that would decide on the hint depending of types of meshes in that island (adjacency distance, intersection, proximity to a certain type of island etc.). 

Well I tried what I said, now it can never put objects to sleep, because due to gravity, at some point during the resolution step an body's speed will exceed the threshold and it will wake up every adjacent body.

Have you research Box2D's sleep mechanism? The idea is sleep an entire island of bodies by crawling an island graph, and computing the maximum linear/angular velocities. A timers is accumulated while the max are underneath a threshold (one threshold for linear, and one for angular velocity). Once the timer reaches a threshold, the island is put to sleep. Islands are awoken by force events or other user events, and if another collider enters the broadphase bounding shape for any of the island entries.

By islands here you mean any set of touching bodies? That seems like it would work similarly to my algorithm that propagates sleep times. It doesn't work well in the dominos case I mentioned - it can't put the tiles at the far end of the chain to sleep because everything is technically one island. It's also a part of the web demo I put together earlier: https://physics.rivsoft.net/Dominos - sleeping bodies can be shown with a checkbox on the right. Don't mind that I accidentally wake up extra bodies during broadphase, don't think it's the main issue here.

That is correct. Box2D's scheme will not put them to sleep.

There are a lot of potential strategies for optimization for the islands not moving much. Caching manifolds or other caching systems can be used to try and skip narrow phase.

The island building scheme can maybe be customized in some way to somehow skip non-moving bodies (like the beginning of a domino chain). But I think a caching mechanism would be better suited for this kind of problem, while leaving the island sleeping as a simple algorithm. Just my opinion.

So it looks like another problem not worth trying to solve I guess. Although I guess I could do a partial solution, where a body at least N edges away from other moving bodies (N being the number of resolution steps) is safe to leave sleeping. Otherwise I would have to wake up bodies based on the velocities in the middle of the resolution step, which doesn't seem to work well at all.

I'm using collision algorithms from Erin Catto's paper I believe, so I do have some caching like saving axis/features for hull-hull collisions in order to resolve the next step faster.

On 5/18/2018 at 3:22 PM, d07RiV said:

It seems that the waking up checks need to be repeated every time a body's velocity changes during contact resolution.

Really objects can be devided to 2 big groups - moving objects and resting objects. moving objects can cause a collision, while non-moving can not cause collision. So is good idea to exclude collizion cheks betwin zero-velocity objects, By other words - have 2 lists - one for objects that can receive collision (both resting anf mooving) and other for objects that can cause collision (moving objects only), and chek one list against other.  Presistence in second list can be easyly handled by the velocity vector setter, while presistece on first list can be handled . By other word it is good idea to put to sleep not a whole object, but switch off  parts of his functionality depends on his state. Im usualy using 5 processing list - 2 described lists for collisions, 3th lists for position calculatioions, 4th - for velocity and angular belocity calculation, and 5th for other object's internal processes, not related to mechanical dynamic simulation, like engines forces, autopilot and etc calculations. 

On 5/18/2018 at 3:22 PM, d07RiV said:

if I make a very long chain of dominos and start collapsing it, then the end of the collapsed chain will always keep the whole thing awake even though 90% of it isn't moving, so eventually the simulation slows down significantly.

It exists a exactly condition when object can sleep into dynamic simulation - his common energy is 0 (less than tolerance barrier). Common energy is sum of kinetic and potential energy. It really easy to check this condition for weake up - if kinetic energy (or speed) after collision, recived from other object, has exeeds tolerance barrier, or when supporting contact has disappear, object have to be waked up. Really it more triky to put object to sleep, becouse potential energy is respective to nearest possible supporting contact, not to global ground level, so usual approach is to put object to sleep, when kinetic energy still zero on 2 consecutive steps.

Also, sliping object may have all his contact with their siblings precalculated at go to sleep time, so it dont need to redetect contacts to calculate response until in moved to distance that exids some tolerance barrier. Really resting group have to react as whole joined system, until it received external energy enougt to break friction (or other kind - magnetic etc.) joints of objects. 

On 5/18/2018 at 3:22 PM, d07RiV said:

so I made it treat sleeping objects as stationary (infinite mass/momentum)

It just have to respond with accounting response of all joined siblings, not with infinite mass, and only then take descigion about wake up movement. By other words - for newton cradle example first resting ball have firts apply received impulse to second ball, at so on,   get response from it, and only then recalculate a velocity, that will be very close to zero, due to opposite directed response from other balls. So objects have to store linear and angular momentums, instead of linear and angular velocities, and recalculate velocities just after sum responses received from all his resting contacts.

Really resting groups works by mechanical static rules, but not by mechanical dynamics rules. So it have first to dissipate received energy tru the precalculated resting contacts, and only than wake up objects, that received more energy that it can dissipate.