[TL,DR: if you’d like to play with a simple Barnes-Hut octree code, scroll down to the little embedded app.]
Gah! It’s been quite a while since my last post. Despite my best intentions, work (and a lot of feedback from Super Planet Crash!) has taken precedence over blogging. I do have a sizable list of interesting topics that I’ve been meaning to write about, however, so over the next few weeks I’ll try to keep to a more steady posting clip.
Super Planet Crash has been a resounding success. I have been absolutely, positively astounded with the great feedback I received. My colleagues and I have been coming up with lots of ideas for improving the educational value of SPC, add new, interesting physics, and addressing some of the complaints. In order to have the ability to dedicate more time to it, over the past few months, we’ve been furiously applying for educational and scientific grants to fund development. Hopefully something will work out — my goal is to make it into a complete suite of edu-tainment applications.
When Giants Collide
I’ve recently started experimenting with a new visualization that I think will turn out pretty darn cool. Its draft name is When Giants Collide. When Giants Collide will address a common request from planetary crashers: “Can I see what happens when two giant planets collide”?
When Giants Collide will be a super-simple JavaScript app (so it will run in your browser) that will simulate the collision of two massive spheres of gas. The simulation will have to model both gravity and the dynamics of the gas: to address this, I’ve been dusting off and reviewing an old Smoothed-Particle Hydrodynamics (SPH) code I worked on for a brief period in graduate school. SPH is a very simple technique for cheaply simulating gas flows with good spatial accuracy, and is somewhat straightforward to code. There are some shortcuts that have to be taken, too — large time steps, low particle counts, and more (e.g., a polytropic equation of state for the gas giants; more on this in future posts). These shortcuts come at the expense of realism, but will enable fast, smooth animation in the browser.
Gravity with the Barnes-Hut algorithm
Gravity is an essential ingredient of When Giants Collide! Even with very low particle counts (say, N = 1000), a brute force calculation that just sums up the mutual gravitational force between particles won’t do if you want to run the simulation at 60 frames per second. Direct summing is an N^2 operation:
(this is a simple force accumulator written in R).
A better way that involves only a slightly more complicated algorithm is to use the Barnes-Hut algorithm (a short Nature paper with more than 1,000 citations!). The algorithm involves recursively subdividing space into cubes and loading them with particles, such that every cube contains either 0 or 1 particles. This is represented in code with an oct-tree structure. Once such a tree is constructed, one can calculate the gravitational force on a given particle in the brute-force way for close particles, and in an approximate way for distant particles; whether to use one or the other is determined by walking the tree down from the top. An excellent explanation (with great visuals!) is provided in this article.
The other advantage is that, once the tree has been already built for the gravity calculation, it can be used to identify the nearest neighbors of a given particle through the same tree-walking procedure. The nearest neighbors are needed for the hydrodynamical part of the SPH algorithm (see, e.g., this review article by Stefan Rosswog or this one by Daniel Price).
An interactive tree
Below is an interactive JavaScript applet that subdivides space with the Barnes-Hut algorithm. You can add new points by clicking on the surface, or using the buttons to add new, random ones.
The code for building the Barnes-Hut tree from an array of 3D positions is available at the GitHub repository for When Giants Collide. I will be developing the code in the open, and post periodically about my progress. Hopefully by the end of summer I will have an attractive app running on any modern device and web browser. Any ideas on how to gamify it?