Spatium

A collection of spatial partitioning techniques created for personal use in real-time applications as well as coursework.

The BVH implementations comfortably handle up to ~16,000 meshes in an unevenly dense 3D scene, while the K-D Tree begins to struggle at around ~870,000 triangles (tested using the Stanford Dragon model).

I suspect performance can be improved significantly with additional optimizations targeted at mid-build operations, which I’ve taken some liberties experimenting with (such as naive rotations and sorts).

The Quadtree and Octree implementations are intentionally simple yet effective. A search test over 10 million points yields roughly an 18× speedup compared to a regular search.

Optimizations were applied where possible (bit packing, locational codes, etc.) to reduce memory usage.

Interestingly, with a two-pass bottom-up approach, real-time performance sometimes surpasses the top-down method. I believe this may be due to the number of split points sampled along each axis (100), although data locality could also be a contributing factor.

For the K-D Tree, SAH is used by sampling a fixed number of uniform positions within the AABB along each axis and selecting the lowest-cost split. Heavy optimizations reduce per-node memory usage to improve traversal performance.

To build the project, navigate to the Scripts folder and run SpatiumBuildWindows.bat. This leverages Premake to automatically generate a C++17 solution in the project’s root directory.

• BVH — Top-down: K-split point construction using Surface Area Heuristics (SAH).
• BVH — Bottom-up: Two-pass merge approach using best-pair filtering with priority queues and candidate merging.
• BVH — Incremental: Dynamic insertion with volume heuristics and self-balancing.
• K-D Tree — SAH-based splitting by sampling uniform positions inside the AABB along each axis.
• K-D Tree — Aggressive node memory optimization to improve traversal performance.
• ---
• Validated BVH handling ~16,000 meshes in unevenly dense 3D scenes; tested K-D Tree performance at ~870,000 triangles (Stanford Dragon).
• Implemented Quadtree and Octree with memory optimizations (bit packing, locational codes) for large-scale point queries.
• Achieved ~18× speed improvements in a 10M-point search benchmark versus naive search.
• Provided a Premake-based Windows build pipeline via SpatiumBuildWindows.bat to generate a C++17 solution.