9
\$\begingroup\$

In a physics engine I'm developing (for learning) using love-2d, I implemented collision resolutions in this way:

FixedUpdate(dt)  // I use fixed timestep
 foreach collide c1 in allNotStaticColliders
   c1.integartePhysic // i.e. apply gravitational force..
   foreach collider c2 "near" c1 // "near"= I use spatial hashing 
      if collide(c1,c2)
        resolve collision (c1,c2)  // the heavy operation
        collison callbacks c1
        collison callbacks c2
        ...

animation of objects falling and settling to a stop

As you can see at the end of the gif animation, there's a FPS decay when all colliders are almost grounded over a static object.

the final static state, with 2 FPS

This because the number of collision resolutions grows as objects spend more time touching as they settle. However, many of the calculations are "useless" because objects have already settled into stable positions against each other.

What's the best practice (hopefully not requiring a physics degree) to avoid these "useless" collision detections?

Edit : accepted DMGregory hints and come to this result (not yet optimal)

enter image description here

(Red=static, Blue=active, Green=sleeping)

\$\endgroup\$
  • 1
    \$\begingroup\$ The usual approach is to "sleep" objects that come to rest, and not consider interactions between sleeping/static objects (but a sleeping object can still be woken by an interaction from a dynamic object that's still awake & moving). Unfortunately this only helps once an object is fully at rest. If I'm reading your example correctly, it looks like your performance troubles start when the objects are still settling and moving slightly. All I can think to do here is add more friction/damping to the system (possibly with a velocity threshold) so that small movements decay to true rest faster. \$\endgroup\$ – DMGregory Jan 15 '16 at 18:00
  • \$\begingroup\$ @DMGregory That sounds like a good answer. Add it? \$\endgroup\$ – Anko Jan 15 '16 at 21:27
8
\$\begingroup\$

I suspected OP already knew this approach so I mentioned it in a comment as just a starting point, but I'll try fleshing it out a bit more...

Most physics engines divide dynamic objects into two groups, "awake," and "sleeping."

Objects sleep when they sit at rest, and wake when moved or accelerated by some outside influence.

A sleeping object behaves like a static object in most respects - its movement isn't integrated over time (because it's at rest, so it has no movement) and the engine ignores collisions between objects that are sleeping or static.

A sleeping object sitting on a static floor doesn't fall through it, despite the lack of a collision response, because all movement integration is skipped for sleeping objects, including gravity.

So, only collisions involving at least one awake dynamic object need to be checked:

Collisions    Static          Sleeping           Awake
          ------------------------------------------------
Awake     |    Check        Check & Wake         Check
Sleeping  |     No               No
Static    |     No

This can dramatically reduce the number of objects that need active simulation, especially in piles which as illustrated in the question have a lot of mutual collisions to check for little to no net movement.

Sleeping only helps once the objects actually reach rest though, which might take a while.

Some things you can do to reach rest sooner:

  • Have a nonzero minimum speed or momentum, and clamp anything that falls below it to zero. (This is basically an epsilon, commonly used in comparing floats)

  • Use friction, damping, and inelastic collisions to sap energy out of the system and help it reach rest faster overall.

  • Increase friction/damping/inelasticity selectively for slow-moving objects to give them that final nudge to rest, without affecting the behaviour of more energetic bodies.

\$\endgroup\$
  • \$\begingroup\$ Good answer. You point out a bounch of good ideas.For the sleep/awake checks I see 2 weak points : 1) if the sleeping object o1 under the sleeping objet o2 awakes moving away from o2 , it does not awake o2; 2) if I remove a static platform under a sleeping object , that object does not awake (under gravitation force) \$\endgroup\$ – dnk drone.vs.drones Jan 16 '16 at 11:02
  • \$\begingroup\$ @dnkdrone.vs.drones Good observations. Having never written a physics engine myself, I'm not sure how this is normally handled. One possibility is, when setting an object to sleep, we store a list of objects it's touching (or add it to a local cluster of objects). When we wake a sleeping object, we also wake everything in its list/cluster. There may be more elegant options, like checking for nearby contacts at the moment of waking (before it's moved away). \$\endgroup\$ – DMGregory Jan 16 '16 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.