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?
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.
- 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.
- 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!
- 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:
- 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.
- If we’re at a leaf node and there’s nothing stored here, then we won’t insert a result for this node.
- 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.
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