search

phetsims / collision-lab

"Collision Lab" is an educational simulation in HTML5, by PhET Interactive Simulations.
GNU General Public License v3.0
6 stars 4 forks source link

Branch: fastDetection. Potentially optimize collision detections #126

Closed brandonLi8 closed 4 years ago

brandonLi8 commented 4 years ago

From #123, collisions are detected by predicting if a collision will occur in a given time step.

However, the computations for predicting collisions happen on every time step. This process can be redundant since the same collision is detected over and over on every step until it is "close enough". One potential optimization (unsure if needed) would be to save detected collisions (even if they don't happen for a long time). This detected collision is removed when the user manipulates any of the balls, when the collision is handled, when a ball is added/removed, or when the colliding object is handled in another collision. I'll investigate.

brandonLi8 commented 4 years ago

This will probably be a somewhat big change in CollisionEngine and its subtypes. I'll reevaluate once https://github.com/phetsims/QA/issues/521 is done. If performance is deemed unacceptable, this would probably be the first optimization I would do.

brandonLi8 commented 4 years ago

Performance was deemed acceptable, but I still want to investigate how complex this will be. I don't want this to affect the prototype so I'm going to do some investigating work in a separate branch.

brandonLi8 commented 4 years ago

So far this is looking really promising! This is probably something that I want to merge into master once the prototype is released.

brandonLi8 commented 4 years ago

Actually, playing around with the sim locally, it is a noticeable change. This works by saving collisions that it knows will happen regardless of how long until it occurs, but doesn't save collisions that wont happen. The sim runs noticeably smoother when balls are traveling towards each other (when a collision is calculated once and saved) compared to when balls are traveling away from each other (no collision detected, so it redetects it on every step). I think this is definitely going to be worth it.

This makes me wonder if it would be possible to save "blacklisted" collisions (collisions that will not occur) as well.

brandonLi8 commented 4 years ago

In the commit above, i added a collection of blacklisted collisions for collisions that will not happen. This also noticeably improved performance (drastically). I'm running the sim on a overheating slow device and it is running 60 fps consistently while the sim is running with 4 balls (no paths)!

brandonLi8 commented 4 years ago

This is working well for the Explore 1D and Explore 2D screens. I now am going to update the CollisionEngine subtypes. In the meantime, I'm going to try using a bisection approximation for predicting rotating ball clusters colliding with the wall. This approximation will be much better than the strategy described in #117. This will also better parallel how the collision engine is structured.

brandonLi8 commented 4 years ago

Bisection method works really well. On average, predicting the collision once is faster than checking for overlapping on every frame. However, on the time step when the collision needs to be predicted it is slower than checking for overlapping. Overall, this works really well and InelasticCollisionEngine is cleaned up. Now to update the IntroCollisionEngine and merge this into master!

brandonLi8 commented 4 years ago

Done in the commit above. Merging!

brandonLi8 commented 4 years ago

Done closing.