C++ Octree Container

Question

I've searched all over the web for an explanation of how an Octree Container works. I can not find any clear cut explanations of how one works. (atleast, that make sense to me...) Does anyone know how to implement an Octree Container? One that has 8 children (or so). And if so, do you mind sharing/explaining the logic... or where I can go to learn how to implement one.

Answer 1

Your question is quite general. But I'll try to give you the idea. Note that there are many ways to implement an octree which all depend on your application. In this example, I will focus on the simple case, where you always divide in the middle.

Let's first start simple. Imagine you have a set of numbers (1 dimensional data). You would want to group these so that you can more easily search for them. One way to do it (even though better ways exist in this particular case), is to create a tree. Let's call this a bitree (so that it won't get mixed with binary tree, even though it is a kind of binary tree).

In this bitree, each node will represent the middle of a range. On the left you will have values smaller than that, and on the right bigger. The root of the tree, of course would represent the middle between minimum and maximum values. In each leaf, if you have more values than you can handle, you split and create a sub-tree. For example, if you have values between 0 and 100, a bitree could look like this:

                  50
              /        \
           25            75
         /    \        /    \
        12   {27,33}  62    {}
      /    \        /    \
   {1,3}  {13}   {51,52} {72}

This tree represents this array:

{1, 3, 13, 27, 33, 51, 52, 72}

I assume you are familiar with binary trees, so implementing such a tree shouldn't be a problem for you.

The key here is that, each leaf can contain up to a certain number of nodes. Each time you insert in the bitree, if a leaf overflows, you get the middle of its range, create a node and divide the values in two leaves.

Now let's extend this to 2d. Imagine your values are in the form of (x,y) (instead of just x). We can divide these values the same way as above, but instead of dividing them into left and right of the middle, we divide them into up-left, down-left, up-right and down-right of the center. The rest is exactly the same. We call this a quadtree, because it has 4 children. The implementation of this quadtree is exactly the same as the bitree, so you should be able to understand it now.

An example from Wikipedia in which each leaf can contain only 1 value:

Final move is to extend this to 3d. The same as before, now the values are in the form of (x,y,z). This time, instead of dividing values in 4 regions, you divide them in 8: up-left-front, up-left-back, down-left-front, down-left-back, up-right-front, up-right-back, down-right-front and down-right-back. We call this an octree and the implementation again is exactly the same as the other ones.

I am stuck with how you would logically build one from scratch. What is the logic behind it? Does it use two containers? Does it use virtual functions in the class? How does the children part work?

Again, exactly the same way you would implement a binary tree. If you use virtual functions there, you can use virtual functions in the octree as well.