Barnes Hut Universe Simulation

Donovan McKelvey

Nicolas Higuera

CPE 471 Fall 2014

Professor Shinjiro Sueda

Program Description

Our universe simulation simulates masses in a universe, calculating gravity between them and creating new masses when objects collide. It uses stars in the world to create light. It has masses go through their life cycle as they grow in size. The simulation uses a large number of optimizations to push the number of objects that can be simulated higher and higher.


By default when the universe is created, all objects will be of asteroid or planet type. The shape and texture of each object is randomized in an attempt to make each object unique.

As objects collide with one another, the mass and size is updated until the new object exceeds the threshold of a new object type. When this occurs, the object is converted into the greatest surpassed threshold object type. As objects increase in mass they change type in the following order: asteroid -> planet -> star -> black hole.


Textures of each shape type are dynamically loaded by inserting a bmp into the /res/img/shapetypehere folder. This allows us to easily randomize each object at runtime by selecting a random texture from the respective folder for each type. A randomized pool of textures and shapes for each type is frontloaded to reduce the complexity of the simulation.


By default, only stars are able to emit light and are always fully visible. All other shapes are lit depending on their respective distance from each star. In the event that there is no star present, a toggle was added to light up all objects in the universe.


The camera can be toggled to move between a preset location near the edge of the universe and that of the next object in outer space. In the event that the camera is set to an object, the camera will follow the object throughout it’s movements in space. Upon collision, the camera will follow the new object as it did with the first.

Collision Detection

To efficiently calculate collisions between planets, we had to create an octree implementation that we could use. When adding masses to the octree, we perform collision detection using the octree. We do this by following the octree, and checking nodes that overlap with the object we are inserting. When we check these nodes, we continue to do this overlap check until we reach a leaf node that holds an actual mass. We then perform sphere-sphere collision detection between this leaf node mass and the mass that we are inserting.

This greatly increased our computation speed as we only had to check masses in close proximity rather than checking every mass against every other mass.

Object textures are only updated in the event a threshold is surpassed, otherwise the new object will take on the texture of the object with the largest collided mass.

Force Calculation

For our force calculation, we implemented the Barnes-Hut algorithm. This algorithm works by reducing the number of calculations made to compute the force for each mass. Normally, you must compute the force of gravity between every individual mass. The Barnes-Hut algorithm says that if a mass is far enough away from a collection of masses, then that collection of masses can be treated as a single mass.

By using octrees, you then compare each mass to different nodes of the octree. If the node in the octree is deemed to be close enough, then you examine the children of that tree. If the node in the octree is determined to be too far away, then you use the center of mass and the total mass of all children of that node as a single mass to compute the force. The threshold value we chose for the Barnes-Hut algorithm was 0.5.


c: perform culling on objects

l: draw the objects as just the vertices of the triangles that define their shape

t: draws the leaf nodes of the octree onto the screen

n: shows the number of objects currently active in the simulation

m: moves the camera to focus on a different mass

b: switch between artificial light and the light of just the stars in the universe

o: toggle camera to a point to view the simulation from a distance

s: Activates “Sueda Mode”. All masses in the universe use a photo of Professor Sueda as their texture

click and drag to move

Future Work

There are a few issues we have with the simulator that we would like to improve upon.

Youtube Link:

Github Page:

Screen Shots