Let us consider a situation when you need to handle collisions between some objects. What do you do in this case? Probably, the easiest solution would be to check interaction between these objects. This is the right decision, and everything will be fine until you get a lot of objects. As soon as their number gets up to a few thousand, you will notice that everything works much slower. What if you get thousands of the particles? Then everything stops. Here things get much more interesting. What tricks and optimizations would you use to solve this problem?

Let us consider 2D case to make it simple, the particles are round, and the radius of the particles is the same for all of them.

Table of contents

1. Overview of algorithms
1.1. Exhaustive search
1.2. Sweep & Prune
1.3. Regular grid
2. Some optimizations
2.1. Sweep & Prune
2.2. Regular grid
3. Speed comparison
4. Application (software and source code)
5. Conclusion
KlauS 14 february 2012, 16:38