Ouroboros

C++, OpenGL -

Ouroboros is my senior project, built with the dual purpose of pushing my graphics programming to its limits and indulging in my space and physics fascinations. The goal was explicitly to create an n-body physics system that supports thousands of particles with realistic stellar lighting that I could continue to expand upon in the future.

Throughout this project, I have learned a lot about physics simulations and new areas of graphics programming that I had not really delved into yet. This project is still in progress but I will now go over some of the more interesting implementation details.

Barnes-Hut Approximation

Computing the forces with a brute force method is O(n^2), and thus incredibly slow with 1,000+ particles. To address this, I used a Barnes-Hut approximation. This form of approximation works by segmenting the particles into different containers, each of which has their own center of mass and total mass. When you go to calculate the forces, if a box is far enough away, instead of iterating through all of its individual particles, you can use the box as an approximation of a large body. This reduces the complexity of force calculation to O(n log n).

Octree
In the video, you can visually see the octree data structure that is used to spatially partition the particles into different boxes. Essentially, each new particle finds the box it should be in, if it is empty the process is over, if it is full, we split the box into 8 new subsections to store new particles. We rebuild this tree every frame to account for particle position changes as it is a relatively cheap operation.
Octree
In the video, you can visually see the octree data structure that is used to spatially partition the particles into different boxes. Essentially, each new particle finds the box it should be in, if it is empty the process is over, if it is full, we split the box into 8 new subsections to store new particles. We rebuild this tree every frame to account for particle position changes as it is a relatively cheap operation.
Lighting

Beyond the physics system is the stellar lighting. Each body in the simulation is either a star or a planet. If it is a star, it emits a light that will be used to calculate lighting for planets. Without any visual effects, this creates a very dull visual. So, a post-processing bloom shader is applied. This downsamples the image and applies a blur effect that is then reapplied on top of the original frame. We have moved on from this in our current iteration as it was unrealistic but I think it is quite beautiful to look at (I recommend watching at 1080p or higher).

In this video, you can see over 5,000 bodies with real-time lighting and bloom being calculated for all of them. The rendering system uses instances and large SSBO buffers to reduce the impact of draw calls on performance.

JWST
In search of a more realistic lighting style, I discovered that more advanced bloom effects use diffraction kernels to simulate how the light behaves when it is actually interacting with a lens. With the limited timescale of this project, I did not have the time to calculate my own diffraction kernel. However, I was able to find some kernels to simulate the spikes of the JWST space telescope, and adapted them to work inside our current bloom system. Here is a rendering using the new method and with more realistic, but sadly less vibrant, star colors.
JWST
In search of a more realistic lighting style, I discovered that more advanced bloom effects use diffraction kernels to simulate how the light behaves when it is actually interacting with a lens. With the limited timescale of this project, I did not have the time to calculate my own diffraction kernel. However, I was able to find some kernels to simulate the spikes of the JWST space telescope, and adapted them to work inside our current bloom system. Here is a rendering using the new method and with more realistic, but sadly less vibrant, star colors.

These kernels were found on ShaderToy. You may notice a significant frame drop when all the particles begin to converge upon each other. This is due to the fact that if all the particles are close, the Barnes-Hut approximation will end up becoming equivalent to the brute-force algorithm.

Realism

The frame drop issue mainly arises due to the fact that the system is unitless. The stars are unrealistically close and the density of space is much too high. In reality, they would not all converge this close and strain the octree and approximation. I have begun to work on this by normalizing the units in the system. Now, bodies are in solar masses, distances are measured in AU, and gravity is set to a constant of 1. This in turn defines a time scale unit of around 58 days per second of simulation time.

This results in a proper space simulation that a user can understand. However, it causes a multitude of issues. The realistic distances mean that the simulation consists of mostly space and stars are so far apart from each other that you cannot see them. Even if you maximize the far plane, stars are at a subpixel scale and will not be rendered.

This also brings up floating point accuracy issues in the physics system. If two points are say 9 billion AU apart, the precision of their calculations becomes a concern. This is something I will have to test and tune with more time. To resolve the rendering issue, I plan on implementing logarithmic depth buffers and distance scaling. This will make stars far away appear much bigger without really any additional performance costs. Another option I may test is calculating the perceived radius of a star.

Future

There are still many performance optimizations that can be made.