Coding a Simple Octree

octree-vortons

Octrees are fundamental in many computer graphics and simulation applications, but I found myself writing one for the first time last weekend, so I thought I’d share the basic ideas and show some code demonstrating how it could be used. The code for this post is available on Github for those eager to jump the gun, but below is an explanation of the semi-interesting parts of the code.

What is an Octree?

simple-octree

An octree is tree built over a region of space, allowing for fast queries for nearby objects. As the name implies, every interior node in the tree has 8 children. The 8 children are determined by the physical center point of their parent node. Pictured above is a simple octree. In 2D, there is a very similar data structure called the Quadtree, which is the same thing but with only 4 children per node since it is in 2D. (You can imagine analogous data structures for higher dimensional spaces with $2^d$ children per node.) A great visualization of an octree is available here.

Typically, we will store objects in an octree so that we can have fast queries for questions like “what points lie withing a certain bounding box”, or equivalently, which points are within a distance $r$ from some query point. There are other uses that we will explore in a later article on particle-based fluid dynamics.

The idea of storing objects is pretty simple in an octree. The actual data that you will eventually want to query will be stored in leaf nodes, and at least for the purpose of this article, interior nodes of the tree will not store data. Oftentimes we will just store one point in a leaf node, but it is easy to handle more than one point in a leaf. We should also notice that

How can we build an Octree?

Building the octree simply requires $n$ calls to $insert$, one for each point to be inserted into an empty tree. The logic for inserting into the tree is relatively straight forward. There are precisely three cases which must be considered for inserting points into an octree.

  1. The node is an interior node to the tree (has 8 children).

    Since we never store data in an interior node of the tree in this article, we will find out which of the eight children the data point lies in and then make a recursive call to insert into that child.

  2. The node is a leaf (no children/not split) and has no data assigned.

    This is the easiest! We’ve ended up in a small region of space with no data currently assigned and no children, so we will simply assign this data point to this leaf node and we’re done!

  3. The node is a leaf (no children/not split), but it already has a point assigned.

    This is slightly more complicated. We are at a leaf but there’s something already here. Since we only store one point in a leaf, we will actually need to remember what was here already, split this node into eight children, and then re-insert the old point and our new point into the new children.  Note: it’s entirely possible that this will happen several times during insert if these two points are really close to each other. (On the order of the logarithm of the space separating them.)

This is hopefully pretty simple. I’ve tried to comment the code for insertion well so that this is as understandable as possible.

How can I determine which child of a node contains a point?

Since we use this several places, it’s important to know why/how this works, but it’s really simple. Remember that every node has a center point (which I called the “origin” in the code) and that all of the child nodes meet at this center point. There are eight children, which is exactly three bits of data. The children are assigned numbers in a simple way so that we can perform this operation quickly. If the point’s x-value is greater than the center point’s x-value, then the third bit of the children index will be set, otherwise it will be zero. Similarly if the y-value of the point is greater than the center point’s y-value, than the second bit is set, and similarly for the z-value. This basically means we do three comparisons and a few bitwise ORs in order to get the child index.

How can I quickly find all the points in a query box?

The main point of making this octree was so we could build the tree with tons of points in it before we start rendering/simulating something/etc and then quickly make many calls to “getPointsInsideBox” during execution. This is also pretty straight forward. The input to this algorithm is a axis-aligned bounding box defined by it’s minimum and maximum corner points and a list which we will insert our results onto. Like when we were building the tree, we can imagine this as a number of “cases” and just look at what we should do in each case. We begin by looking at the root:

  1. If this node is a leaf node and we have data, see if the point is contained within the query box. If it is, then insert it into the results list.
  2. If we’re at a leaf node and there’s nothing stored here, then we won’t insert a result for this node.
  3. We must be at an interior node in this case. We will look at each of this nodes eight children. If the child’s bounding box lies outside the bounding box, then there is no need to check that child or any of it’s descendants in the tree. In any other case, we will recursively look into the child node (step 1).

Note: If the size of the querying box is large with respect to the whole space the tree encompasses, then you will visit many (or, in the worst case, all) nodes in the tree. When you are looking at this many nodes, it may actually be faster to use another method. In the case where the result is all the points, you can see how the octree actually performs worse than brute-force checking every node manually! But, octrees give huge gains when the query is a small region of space compared to the size of the tree’s space, as the code demonstrates.

Example Code

The example code at github is meant to educate rather than be extremely optimized. I hope there is a good amount of explanation between this post and the code comments. If not, please leave a comment here!

For those curious, the opening picture depicts an octree used for quickly simulating fluids using “vortons”, which will be the subject of the next article :)

8 thoughts on “Coding a Simple Octree”

  1. Looking at the code, it seems like you are only ever querying against a small region. Have you considered maybe using a regular grid instead? An octree has an overhead per range query of at least \Omega(n^{2/3}), and can in practice be much worse. With a regular you should be able to look up all the points within small, fixed size regions much more efficiently, and the memory overhead can be drastically reduced by storing only the filled cells using a hash table/binary search tree.

    1. Excellent point :) For small fixed-size queries, uniform grids will likely be more efficient (I tried to make a note of this property here and in the code). One great benefit not shown here relies on the fact that we can store information in the interior nodes, as I will show in the next article on vortons. If you haven’t seen it before, I suggest you check out “Barnes-Hut Algorithm”.

      Also, there will be a later article on SPH (actually more of a recreation of an old article I wrote that no longer exists and many people have asked me for), that uses this exact same spatial hashing technique you described!
      Thanks for the insight!

  2. Hi Brandon,

    I recently tried to emulate your simple octree code. I am trying to map solution of a coarse mesh to a fine mesh. So I first created an octree similar to yours using just the coarse mesh points. Then using the query function I tried to find three neighbouring points to each of the fine mesh points. And finally use these neighbour points to find flow variables at each fine mesh point.

    To do this I create a querybox around each of the fine mesh point and then find the coarse mesh points lying in this box.

    For finding the three neighbours I stop the findPointsInsideBox function once the size of results vectors reaches three. Also another modification that I have made is that I expand the box if the three neighbours are not found with current dimension.

    I don’t know where I went wrong but the program gives the same three coarse mesh points as neighbour to every fine mesh point.

    Can you please just where I might be going wrong?

    1. Hello again,

      The problem was troubling me for quite sometime but got it sorted minutes after posting the question.
      Wish there were a delete button for comments.

      Thanks for such a good example on octrees!

  3. Nicely done! Simple and to the point explanations are always better than convoluted papers and algorithm, while the latter may provide some other benefits as well. Anyways, I’ve been trying to make a method that can return all of an octree’s children than intersect an incoming ray. I already have an AABB-ray intersection algorithm that i’m using that can return true/false and distance to hit. Any ideas on how to implement this without brute-forcing each child or using trig functions?

  4. Dear Brandon,

    I came across your work on Octree based spatial subdivision based upon an applied point cloud. It was very nice concise work and I am contacting you because I would like to implement some of it in the research that I am currently undertaking at the Architectural Association in London.

    My current research project is focussing on eye tracking, observing and quantifying the way that people reconstruct visual space around them. I am using a head worn eye tracking device named Pupil Pro that correlates the eyes focus with a point in space and am thus gathering systems of point clouds.

    I am now at the point at which i would like to quantify these results and also create a form of three dimensional cartography for this newly discovered visual space, and from my research I feel the Octree system would be a good start. After this I would like to incorporate a dynamic element in the form of moving points, in order to explore how the viewers gaze changes over time and position.

    I am writing to you as I would like to utilize your program and your expertise in achieving a new frontier in digital cartography, one which strongly compounds with the incoming dawn of augmented reality and such.

    If you have some idea of how I could approach this and would be interested in some sort of academic collaboration, even if it just advice driven I would be most thankful.

    I hope to hear from you soon.

    Sincerely,

    Leander

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>