Octrees for faster intersection #

Efficient intersection between rays and objects can be achieved by using acceleration structures such as octrees. The idea of an octree is to split the space into \(8\) equal-sized octants (hence the name). The 2D variant of an octree is a quadtree. Analogous a binary tree can be considered to be the 1D variant of an octree and a quadtree. I use quadtrees in the case where considering an octree does not bring any additional value over the quadtree and where the mapping of the concepts from quadtrees to octrees is straightforward. The following figure shows a few triangles and a corresponding quadtree:

The start bounding box #

The initial bounding box (axis-aligned bounding box) around the scene is a rectangle which is not necessarily a perfect quad. Since the quadtree should consist only of quadratic elements (quads) the bounding box of the scene needs to be “squarified”. Theoretically also a non-squarifed rectangle could be split into four equal parts and used within a quadtree, but this is something I would not consider as a “classical” quadtree approach. Therefore, I want to focus here only on square-shaped elements. Assume that for a given 2D scene the 2D axis-aligned bounding box minimum is \((0,0)\) and the maximum corner is \((2,1)\) . What would be a good squared box? One could say \((0,0)\times(2,2)\) is fine since it is squared (constraint A) and the original box is completely inside it (constraint B). Another idea would be to center the bigger squared box around the original box. However, you can implement it as you like as long it fulfills the two mentioned constraints. The strategy that I have chosen here is to use the maximum value of the dimensions (width \(\times\) height) of the bounding box for the squared and keep the bottom left corner fixed (see above figure).

Constructing a quadtree #

The following rules were chosen to construct the quadtree:

1. Child nodes should only contain one single triangle
2. A triangle can be at the same time part of multiple quadtree child nodes (e.g. see figure above: Triangle \(C\) and \(D\) are part of two different child nodes; no splitting is performed for triangles)
3. As long as constraint \(1.\) is not fulfilled a split is performed

The split as performed in the following way:

G---------H---------I
|         |         |
|   (2)   |   (3)   |
|         |         |
D---------E---------F
|         |         |
|   (0)   |   (1)   |
|         |         |
A---------B---------C

Similar for a octree the split can be peformed:

Quadtree construction #

Endless splits #

One situation that can occur when performing splits according to the previously described rules is that you can land in a situation where you perform endless splits. For example, this can happen if two triangles share an edge as can be depicted from the next figure:

Along the shared edge, each further subdivision of the quadtree will lead to cells that contain always two triangles. Therefore you need some criteria to stop splitting.

Building strategies #

One possibility to avoid endless splits is to introduce a maximal tree depth. As you can see from the figure above splitting stops at depth level \(6\) . But this strategy is obviously not good, since it leads to many unnecessary splits, which makes the quadtree deeper and slower to trace.

Another possibility is to stop splitting if a split would lead to one child element that has as many triangles as the corresponding parent. This strategy works but is sometimes too conservative:

Maybe you wonder why splitting stopped for the main part of the head of the Standford Bunny. That is because further splitting would lead to four child elements where at least one child element would have the same amount of triangles as the parent. Nevertheless, it can be desirable to perform the split when only one splitting zone gets all triangles and the other zones are empty.

Here is another strategy:

The idea here is to continue splitting when only one child element violates the “as many sub shapes” as the parent element. Which gives a bit nicer quadtree.

There are endless strategies to build a quad- or octree. One another idea could be that you first follow the max depth rule until some certain minimal shape for the node elements and then switch to the not the same amount of sub shapes in child as in parent node strategy.

More cells occupy more memory and a very nested deep tree can have negative effects on performance.

FlatlandRT testbed #

If you need a testbed to test our quadtree construction strategies you can try out FlatlandRT. FlatlandRT is a 2D raytracer visualization tool. It is written in C++ and uses Bazel as a build system.

It should be easy to get FlatlandRT running on your system. For instance, using Ubunutu 20.04, you only need to run

git clone https://github.com/Vertexwahn/FlatlandRT.git
cd devertexwahn
bazel run --config=gcc9 //flatland/cli:flatland.cli -- some_scene.xml

If you have not installed the Bazel build system on your system, you can install it via:

echo "deb [arch=amd64] http://storage.googleapis.com/bazel-apt stable jdk1.8" | sudo tee /etc/apt/sources.list.d/bazel.list
curl https://bazel.build/bazel-release.pub.gpg | sudo apt-key add -
sudo apt-get update && sudo apt-get install -y bazel

The README.md contains more information to get it running on other operating systems such as Windows or macOS. More details on how to install Bazel on your system can be found here.

FlallandRT contains a function name build_quadtree. This is the place where the construction of the quadtree takes place. There is also an enumeration for different quadtree strategies. You can add your own quadtree construction strategy. To able to select you strategy you can add support for it here. The property set handed over to constructor of the class QuadtreeIntersector is created out of a scene XML file. A build strategy can be selected by adding to the scene file format to an intersector the strategy property:

<intersector type="quadtree">
    <string name="strategy" value="StopAtMaxDepth"/>
</intersector>

Bounds check #

One important part of a quadtree implementation is the check if a shape (e.g. triangle) overlaps a quadtree cell. For triangles usually, one does not do a triangle to cell intersection test but instead, checks only as an approximation if the axis-aligned bounding box of the triangle overlaps a quadtree cell. The nice thing with working with bounding boxes instead of the real geometry is that this way easily other geometry types such as disks (or spheres in 3D case) can be supported and determining a bounding box is quite often more easy than doing a complicated real geometry intersection test.

Implementing a quadtree #

A good first exercise before starting with the real quadtree implementation is to start with something simpler, but similar. Imagine you get as an input a list of numbers, and you have to distribute those numbers across a quadtree. Each node is only allowed to hold as max 4 numbers. Here is my C++ implementation of this exercise:

/*
*  SPDX-FileCopyrightText: Copyright 2022-2023 Julian Amann <dev@vertexwahn.de>
*  SPDX-License-Identifier: Apache-2.0
*/

#include <iostream>
#include <vector>
#include <array>

struct QuadTreeNode {
    std::vector<int> values;
    std::array<QuadTreeNode*,4> nodes = {nullptr, nullptr, nullptr, nullptr};
};

// split vector in almost equal parts
std::pair<std::vector<int>, std::vector<int>> split(const std::vector<int>& v) {
    std::size_t const half_size = v.size() / 2;
    std::vector<int> first_half(v.begin(), v.begin() + half_size);
    std::vector<int> second_half(v.begin() + half_size, v.end());
    return std::make_pair(first_half, second_half);
};

// split vector in almost 4 equal parts
auto split4(const std::vector<int>& v) {
    auto first_split_result = split(v);
    auto second_split_first_half = split(first_split_result.first);
    auto second_split_second_half = split(first_split_result.second);

    std::array<std::vector<int>, 4> zones = {
            second_split_first_half.first,
            second_split_first_half.second,
            second_split_second_half.first,
            second_split_second_half.second};

    return zones;
}

QuadTreeNode* create_tree(std::vector<int>& numbers) {
    if(numbers.empty())
        return nullptr;

    const int MAX_NUMBERS_PER_CHILD_NODE = 4;

    if(numbers.size() <= MAX_NUMBERS_PER_CHILD_NODE) {
        QuadTreeNode *leaf_node = new QuadTreeNode();
        leaf_node->values = numbers;
        return leaf_node;
    }

    auto zones = split4(numbers);

    QuadTreeNode *parent = new QuadTreeNode();
    for (int i = 0; i < 4; ++i) {
        parent->nodes[i] = create_tree(zones[i]);
    }

    return parent;
}

void destroy_tree(QuadTreeNode* node) {
    if(node == nullptr) {
        return;
    }

    for(QuadTreeNode* n : node->nodes) {
        destroy_tree(n);
    }

    delete node;
}

void print(QuadTreeNode* node) {
    if(node == nullptr) {
        return;
    }

    for(auto value : node->values) {
        std::cout << value << " " << std::endl;
    }

    for(auto n : node->nodes) {
        print(n);
    }
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

    auto root = create_tree(vec);
    print(root);
    destroy_tree(root);

    return 0;
}

Even for this very simple quadtree variant, it took me already nearly 100 lines of code.

Performance considerations #

I compared my own implementation of an octree to Brute Force rendering and to Embree (version 3.13.0 with oneTBB). Rendering was performed on a AMD Ryzen 9 3900X 12-Core Processor on Ubuntu 20.04.3 LTS.

In the octree traversal phase, the octree cells are sorted according to their distance from the viewer.

References & Further Reading #

There are many resources about Octrees and Quadtrees, e.g.:

• Quadtrees and Octrees for Representing Spatial Information
• Vorlesung Algorithmen für hochkomplexe Virtuelle SzenenScript (German language)

When it comes to performance and C++ you can see strange effects:

• Never trust the compiler pt1

Several state of the art ray tracers are using GPUs for intersection:

• Cycles X Project Update

Besides Embree there are also some intersections libraries one can use:

• https://github.com/madmann91/bvh