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.

Objects

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

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.

Lighting

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.

Camera

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.

Controls

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.

• Currently we bind and unbind textures every time we draw a mass. Instead of doing this, we would like to sort our objects so that we draw all objects with the same texture together. By doing this, we don’t have to unbind and rebind the textures repeatedly and should increase performance.
• Currently we use the simulator’s internal vector when we’re drawing objects to the screen. By doing this, we have to pause the simulation from running so that the vector is not modified as we’re iterating through this. To fix this, it would be better to export a vector of just the attributes needed to draw the objects to this screen. This is already done for our octree leaf node drawing. Because this vector would be a new object, we could iterate through it without having to worry about the simulation, and the simulation could run without being locked for as long.
• The octree leaf nodes don’t seem to work perfectly. They should be drawing as cubes, but they are being drawn as squares. Might be an issue of how we’re converting coordinates.
• More interaction: Being able to add masses to the simulator at a time, or the ability to change the force of gravity.

Youtube Link: http://youtu.be/eBcLvTDogjE

Github Page: https://github.com/NiftyNico/UniverseSim

Screen Shots