Question

I am implementing an Octree in C++ which should later contain a mesh for rendering. But at the moment I am struggeling with the construction of the Octree. To be more precisely it is the addNode() function which causes problems. I thought of a recursive implementation similar to a binary tree: Binary Tree implementation C++

However, in an octree every node has 8 sons and not only 2. Furthermore, therefore I cannot use a simple switch (left/right) as in the binary tree to decide where to add the node. I would need to check if one of the 8 sons is empty (pointer is NULL) and if no pointer is null I would need to call the add function with one of the sons as an argument. However, this will result in an octree where always the first son will contain all following sub octrees. How is this add function commonly implemented and this problem avoided?

No correct solution

OTHER TIPS

You need to check x,y,z dimension of the object and also the octree can save a limited number of object.

You've got the right idea, you just need to extend the concept to three dimensions. Rather than determining whether a child should be inserted to the left or right (x-dimension), you must also choose above or below (y-dimension), and in front or behind (z-dimension). You could use a three-dimensional array like this:

Node* children[2][2][2];

And your inner nodes (those with branches) should have a 3-D center and size. When deciding where a value should be inserted into the octree, you need to compare the position being inserted or searched to the center of the current octant:

children[position.x > center.x][position.y > center.y][position.z > center.z]

This gives the pointer where you'd insert. If there is node in this position, you'd need to recurse if it's a another branch, create a new node if it's null, or create a branch and reinsert if it's a leaf node.

You may find the three-dimensional array cumbersome when iterating over children. Instead you can use a one-dimensional array and index into as though it has three dimensions:

Node* children[8];

int index = (position.x > center.x) << 2 |
            (position.y > center.y) << 1 |
            (position.z > center.z);

This generates the index [0-7] by setting bits according to where the position is relative to the octant's center.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top