Collision Detection in large Particle Systems

Sebastian Stratbücker, September 2003

Introduction and overview

Goal of this project was, to examine methods of collision detection in large scale particle environments. The particles ought to have a positive radius, i.e. they are threedimensional objects, respectively balls with variable diameter. There yet exists a huge amount of very performant algorithms and methods to compute and simulate interaction between spatial models in computer simulations, but it is still another task to solve the famous N-Body Problem which arises in lots of computer simulation environments, like molecular behaviour in miscroscopic dimensions but also dynamics of galaxy clusters in macroscopic scales. Those problems however can be solved with computing power and time, that complies to the complexitiy of the system.

Features and targets

A vital aspect of my project was, to manage the collision and interaction of particles in a real time scenario. In particular there should be a possibility to manipulate the physics and forces that affect the system or change the amount of particles interactively. Another target was, to run the simulation with convenient framerates of 20 to 30 fps or even higher. It appeared unfortunately, that a lot of computational costs were spent by the graphics hardware by merely displaying the scene with tenthousands of polygons in it. Ignoring the effort for visualization, there just remain the costs of collision detection between particles.

Final approach and results

After attempting various approaches to the issue, I ended up with a very own implementation of a Collision Detection Method between ballshaped objects in a cubic bounded threedimensional space. It is a mixture of both twodimensional separation into uniform cells and onedimensional sorting of the particles along the remaining space axis. The resulting algorithm has an estimated average complexity of N log(N) at medium particle density. Disregarding the OpenGL and hardware performance when displaying high resolution ball geometries, the simulation runs in low resolution mode with an estimated 20 fps at a system size of 20000 particles (observated on a 2.8 GHz machine, equipped with the lastest graphics hardware available on September 2003).

Screenshots