Thursday, February 23, 2017

In a 2D physics engine, how do I avoid useless collision resolutions when objects come to a rest?


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)



Answer



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.




No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...