## 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(*n ^{2}) *(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.