An implementation of the Octree data structure, written using C++20. Octrees are tree-based structures typically used for 3D graphics to manage a large number of points at once by recursively subdividing a space. The lowest depth nodes (where points are stored) are known as leaf nodes; when the node exceeds a specific amount it subdivides into 8 leaf nodes, or octants.

The source code is public and viewable on GitHub, containing three subprojects: the Octree implementation, a Demo, and Tests.

Features

A full list of features can be found on the repository’s readme.

Raycasting

The Octree provides support for obtaining a list of points that intersect a ray. It can also provide a list of nodes that the ray intersected with.

On an AMD Ryzen 5 5600X CPU, the Octree supports real-time raycasting up to 3,500,000 points with minimal performance loss.

K-Nearest Neighbor

K-Nearest Neighbor describes finding a set of $k$ points nearest specific location.

Tests

Before creating the demo, a set of unit tests using GoogleTest was created to ensure that Octree functions behaved as expected, including creation of parameterized tests to check the Octree against a variable number of randomized points.

Any changes to the Octree code after the demo had been created was also verified using the unit tests to ensure correct results.

Demo

The Demo is a minimal, interactive OpenGL 4.6 implementation (with Direct State Access (DSA)) created to showcase the Octree. It uses a rendered ray to demonstrate raycasting and nearby neighbors against a randomized set of points, representing entities. The ray can be set to a static position or to follow camera position and rotation.

The Octree can also be regenerated with new points & depth settings.

Besides the graphical user interface, the user can also navigate the scene with a simplified FPS control scheme:

• WASD / Shift / Space to move
• Mouse to look around
• Esc to lock/unlock camera rotation

The demo uses the following libraries for convenience:

• GLFW
• GLM
• Glad
• imgui

Optimizing the Demo

The demo makes use of several optimizations for smoother framerate during rendering.

Instanced Rendering

In OpenGL, it is well known that multiple individual draw calls for a single mesh over a single frame can incur significant performance costs, in part due to the CPU-GPU communication bottleneck. Instanced rendering helps alleviate some of the performance loss by batching transformations as a group before drawing.

The points and grid are both rendered using this method.

Point Instancing

To support point instancing, the Octree includes an identifier parameter for later identification when raycasting and searching for nearest neighbors. This makes it possible to note which relevant points should be drawn in a different color.

Grid Instancing

The grid is comprised of multiple cubes, where each cube represents a node. The demo batches cubes to be rendered through prepare_cube() calls, then draws them all at once.

Result Caching

When the ray is placed at a static location, the results from searching nearest neighbors are cached by storing them long-term during runtime, reducing need to requery until the ray is placed at a different location.

Challenges & Decisions

The K-Nearest Neighbors algorithm was found to incur significant performance costs during Demo runtime. This was attributed to sorting the list of possible candidates after results were found, and so storage was switched to a priority queue (highest distance first), which keeps items sorted on insertion instead. Further diagnostic testing revealed that all candidates of a leaf node was added at once and unconditionally, instead of evaluating whether their distance to the input position was closer to that furthest distance.

Despite the grid using instanced rendering, it is disabled when a large number of points are used. This helps prevent the cube rendering process from bottlenecking (where the focus should be on Octree traversal). Due to the recursive nature of the Octree, the number of possible nodes grows exponentially with depth, which becomes impractical to preallocate rendering information without excessive memory usage.

Future Work

• Benchmark performance of this implementation compared to other Octree implementations
• Add frustum casting to cull for visible points for improved rendering performance
• Support for storing triangles and other structures for meshes
• Ability to move and remove points