The Barnes-Hut Approximation For Fast N-Body Simulations
Visual effects simulating space, planets and galaxies is nothing new for the VFX industry, and while the visual result is often much more important than one-to-one real-life accuracy, basing the 3D reproduction of these complex phenomena on accurate scientific foundations really pushes the end visuals, and heightens its artistic value. A perfect example of this is DNEG’s work on the movie Interstellar and their ray-tracer simulating gravitational lensing around a black hole. On a similar note, cosmological simulations are a well-researched topic, whose progress has been going on for many years. These simulations and solvers are highly specialized and usually require large computational power – due to gravitational pull on each other, each object’s change of state (position, temperature, pressure) requires it to iterate through all the others, creating an algorithm of complexity O(n2) (usually referred to as the N-body problem), which scales the computation time exponentially, making a simulation of about million particles impossible on a home machine, even when executed parallelly on the GPU. Due to this, many methods of n-body calculations have been researched and developed, and although the performance boost they offer makes them viable for use by individual 3D-artists, there are no public implementations of them in any popular 3D software. The goal of this project is to create a basis for cosmological simulations in a more artist-friendly environment, specifically the Houdini software package by SideFX, and achieving performance which would allow the simulation of a large number of particles without the performance impact that comes with the unoptimized algorithm.