Jump to content

  • Log In with Google      Sign In   
  • Create Account

Nick's Corner

Octrees are a dev's best friend

Posted by , 23 May 2012 - - - - - - · 286 views
Octree, diamonds, positioning and 3 more...
I've been using an octree system for space partitioning for a long time now, and a couple of the reasons I'm using one are:
  • It can adapt well to any number of items in them
  • It only really falls down as structures get very close together (and I'm dealing with celestial objects - which have a tendency to explode or absorb each other as they get too close)
  • It can be built and rebuilt fairly quickly
  • It's essential for Bayes-Hut
Now there's more than one way to skin a cat, apparently, and there's also more than one way to build an octree. Traditionally you build the hierarchy based on position, splitting a node into 8 smaller nodes as the number of items near each other reaches a pre-set threshold. This is how you should have it for Bayes-Hut to work as intended.

Alternatively however, (and useful for level of detailing in a space sim), you can build your octree hierarchy based on size, visibility, temperature or any other characterization.

Taking size as an example, let's say we want to render far away stars only if they're very large (why waste rendering calls on a star that's barely larger than a couple of pixels?). Normally we LOD to distance, but in this case a very, very large star or a very, very bright star can be seen from quite a distance compared to an asteroid. So we build an octree, with size, brightness, temperature, magnitude, etc as the function for calculating heirarchy. The giant items make up the first level of the tree, with maybe four or five of them in any one galaxy. Then, as the size gets smaller, we put them in finer and finer-grained octree nodes. This lets us operate by octree level, setting different view distances per size. Does this also work with Bayes-Hut? No.

Let's take a look at the Newtonian formula for pair-wise gravitational interactions:

F = (G*m1*m2 / r^2)

Here F is the force, G is the gravitational constant, m1 is the mass of the first body, m2 is the mass of the second body and r^2 is the distance between the two bodies squared.

You see, there are two important variables in the gravity calculation: mass and distance, but it's clearly seen that as distance increases, the force is reduced exponentially, so distance is more important in the long term. If you think about it, you'd want a planet that's orbiting a star to directly gravitate against that star instead of with every other planet in the galaxy. It just doesn't make sense otherwise.

So how do we cull the bodies that are far away and small, but keep the really big ones?

Well we build a formula for it.

There's a very complicated formula for what size an object will appear on the screen in pixels, but we don't actually need that and it makes me queasy just thinking about it. Astrophysics has our back. The visibility of a celestial object is described using its apparent magnitude.