Octree data structure

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 30 minutes | Coding time: 20 minutes

Octree is a tree data structure where each internal node has 8 children. An octree is generally used to represent relation between objects in a 3-dimensional space. It is used in 3D computer graphics. Octrees are also used for nearest neighbor search which can be done easily in logarithmic time.

Like a binary tree divides a 1-dimensional space into two segments, an octree subdivides the 3D space into 8 octants where each octant is represented by a node.

An octree save a large amount of space when storing points in a 3D space, especially if the space is sparsely populated. If there are k points in a 3D cube of dimension N, then space used by the tree is O(klog₂N)

The image below shows how an octree represents points in a space.

Algorithm

Three types of nodes are used in octree:
1. Point node: Used to represent of a point. Is always a leaf node.
2. Empty node: Used as a leaf node to represent that no point exists in the region it represent.
3. Region node: This is always an internal node. It is used to represent a 3D region or a cuboid.

A region node always have 4 children nodes that can either be a point node or empty node.

Insertion

Insertion: This is a recursive function used to store a point in the octree.

1. Start with root node as current node.
2. If the given point is not in cuboid represented by current node, stop insertion
    with error.
3. Determine the appropriate child node to store the point.
4. If the child node is empty node, replace it with a point node representing the
    point. Stop insertion.
5. If the child node is a point node, replace it with a region node. Call insert for
    the point that just got replaced. Set current node as the newly formed region
    node.
6. If selected child node is a region node, set the child node as current node.
    Goto step 2.

Search

Search: This is a boolean function used to determine weather a point exists in 3D space or not.

1. Start with root node as current node.
2. If the given point is not in boundary represented by current node, stop search
    with error.
3. Determine the appropriate child node to store the point.
4. If the child node is empty node, return FALSE.
5. If the child node is a point node and it matches the given point return
    TRUE, otherwise return FALSE.
6. If the child node is a region node, set current node as the child region node.
    Goto step 2.

Note that a 3D cuboid can be represented by 2 points of any of its diagonal.

Complexity

Time complexity:
1. Find: O(log₂N)
2. Insert: O(log₂N)
3. Search: O(log₂N)
Space complexity: O(k log₂N)

Where k is count of points in the space and space is of dimension N x M x O, N >= M, O.

Implementations

C++ 11

/*
 * Code for an octree that demonstrates insertion and search
 */
#include <iostream>
#include <vector>

#define TLF 0    // top left front
#define TRF 1    // top right front
#define BRF 2    // bottom right front
#define BLF 3    // bottom left front
#define TLB 4    // top left back
#define TRB 5    // top right back
#define BRB 6    // bottom right back
#define BLB 7    // bottom left back

struct Point{
    int x;
    int y;
    int z;

    Point() : x(-1), y(-1), z(-1) {}

    Point(int a, int b, int c) : x(a), y(b), z(c) {}
};

class Octree{
    // if point == NULL, node is regional.
    // if point == (-1, -1, -1), node is empty.
    Point *point;

    Point *top_left_front, *bottom_right_back;   // represents the space.
    std::vector<Octree *> children;
    
public:
    Octree(){
        // to declare empty node
        point = new Point();
    }

    Octree(int x, int y, int z){
        // to declare point node
        point = new Point(x, y, z);
    }

    Octree(int x1, int y1, int z1, int x2, int y2, int z2){
        if(x2 < x1 || y2 < y1 || z2 < z1)
            return;
        point = nullptr;
        top_left_front = new Point(x1, y1, z1);
        bottom_right_back = new Point(x2, y2, z2);
        children.assign(8, nullptr);
        for(int i = TLF; i <= BLB; ++i)
            children[i] = new Octree();
    }

    void insert(int x, int y, int z){
        if(x < top_left_front->x || x > bottom_right_back->x
            || y < top_left_front->y || y > bottom_right_back->y
            || z < top_left_front->z || z > bottom_right_back->z)
            return;
        int midx = (top_left_front->x + bottom_right_back->x) >> 1,
            midy = (top_left_front->y + bottom_right_back->y) >> 1,
            midz = (top_left_front->z + bottom_right_back->z) >> 1;
        int pos = -1;
        if(x <= midx){
            if(y <= midy){
                if(z <= midz)
                    pos = TLF;
                else
                    pos = TLB;
            }
            else{
                if(z <= midz)
                    pos = BLF;
                else
                    pos = BLB;
            }
        }
        else{
            if(y <= midy){
                if(z <= midz)
                    pos = TRF;
                else
                    pos = TRB;
            }
            else{
                if(z <= midz)
                    pos = BRF;
                else
                    pos = BRB;
            }
        }

        if(children[pos]->point == nullptr){
           // if region node
            children[pos]->insert(x, y, z);
            return;
        }
        else if(children[pos]->point->x == -1){
            // if empty node
            delete children[pos];
            children[pos] = new Octree(x, y, z);
            return;
        }
        else{
            int x_ = children[pos]->point->x,
                y_ = children[pos]->point->y,
                z_ = children[pos]->point->z;
            delete children[pos];
            children[pos] = nullptr;
            if(pos == TLF){
                children[pos] = new Octree(top_left_front->x, top_left_front->y, top_left_front->z,
                                        midx, midy, midz);
            }
            else if(pos == TRF){
                children[pos] = new Octree(midx + 1, top_left_front->y, top_left_front->z,
                                        bottom_right_back->x, midy, midz);
            }
            else if(pos == BRF){
                children[pos] = new Octree(midx + 1, midy + 1, top_left_front->z,
                                        bottom_right_back->x, bottom_right_back->y, midz);
            }
            else if(pos == BLF){
                children[pos] = new Octree(top_left_front->x, midy + 1, top_left_front->z,
                                        midx, bottom_right_back->y, midz);
            }
            else if(pos == TLB){
                children[pos] = new Octree(top_left_front->x, top_left_front->y, midz + 1,
                                        midx, midy, bottom_right_back->z);
            }
            else if(pos == TRB){
                children[pos] = new Octree(midx + 1, top_left_front->y, midz + 1,
                                        bottom_right_back->x, midy, bottom_right_back->z);
            }
            else if(pos == BRB){
                children[pos] = new Octree(midx + 1, midy + 1, midz + 1,
                                        bottom_right_back->x, bottom_right_back->y, bottom_right_back->z);
            }
            else if(pos == BLB){
                children[pos] = new Octree(top_left_front->x, midy + 1, midz + 1,
                                        midx, bottom_right_back->y, bottom_right_back->z);
            }
            children[pos]->insert(x_, y_, z_);
            children[pos]->insert(x, y, z);
        }
    }
    
    bool find(int x, int y, int z){
        if(x < top_left_front->x || x > bottom_right_back->x
            || y < top_left_front->y || y > bottom_right_back->y
            || z < top_left_front->z || z > bottom_right_back->z)
            return 0;
        int midx = (top_left_front->x + bottom_right_back->x) >> 1,
            midy = (top_left_front->y + bottom_right_back->y) >> 1,
            midz = (top_left_front->z + bottom_right_back->z) >> 1;
        int pos = -1;
        if(x <= midx){
            if(y <= midy){
                if(z <= midz)
                    pos = TLF;
                else
                    pos = TLB;
            }
            else{
                if(z <= midz)
                    pos = BLF;
                else
                    pos = BLB;
            }
        }
        else{
            if(y <= midy){
                if(z <= midz)
                    pos = TRF;
                else
                    pos = TRB;
            }
            else{
                if(z <= midz)
                    pos = BRF;
                else
                    pos = BRB;
            }
        }
        if(children[pos]->point == nullptr){
           // if region node
            return children[pos]->find(x, y, z);
        }
        else if(children[pos]->point->x == -1){
            // if empty node
            return 0;
        }
        else{
            if(x == children[pos]->point->x && y == children[pos]->point->y
                && z == children[pos]->point->z)
                return 1;
        }
        return 0;
    }
};

int main() {
    Octree tree(1, 1, 1, 4, 4, 4);
    std::cout << "Insert (3, 3, 3)\n";
    tree.insert(3, 3, 3);
    std::cout << "Insert (3, 3, 4)\n";
    tree.insert(3, 3, 4);

    std::cout << "Find (3, 3, 3):\n";
    std::cout << (tree.find(3, 3, 3) ? "True\n" : "False\n");
    std::cout << "Find (3, 4, 4):\n";
    std::cout << (tree.find(3, 4, 4) ? "True\n" : "False\n");
    std::cout << "Insert (3, 4, 4)\n";
    tree.insert(3, 4, 4);
    std::cout << "Find (3, 4, 4):\n";
    std::cout << (tree.find(3, 4, 4) ? "True\n" : "False\n");
    return 0;
}

Applications

Used extensively in 3D computer graphics, especially game design.
Used for triangle search. Paper.
Used to find closest object in 3D space efficiently.

References/ Further reading

Youtube video by DevDept Software showing how octree subdivides a 3d mesh.