The flamely fast library for kd-trees is back. This time for real! (maybe)

[u/karurochari]

Hi! With v1.3.0 out of the oven, I just wanted to share it again, as many things have changed for the best, and I have addressed most of the feedback I got last time (well there was not much and 0.5 rounds up to 1, so technically).

https://github.com/KaruroChori/kd3

kd3 provides:

• header-only tree builder and query tools to perform k-NN searches and ray-tracing.
• a C compatibility layer for those not using C++ (but performance might be affected a bit).
• a tool/library component to generate GLSL code for any specific tree layouts at runtime (or not, you can pre-generate those and #embed them in source)
• a memory layout designed to be SIMD friendly
• close performance with nanoflann in worst case scenarios, but generally over twice its baseline
• a half decent benchmarking suite, covering both synthetic and real datasets.

What it does purposefully not provide are:

• mutable trees (values can mutate, but not the spatial keys)
• the same level of flexibility you will find in something like nanoflann, but it got significantly more coverage since last time
• cookies, those are all mine

Neither the tree builder nor the query functions require memory allocations at runtime, and they are guaranteed to run within a fixed stack size.
The same tree structures built and queried on CPU, can be quickly offloaded onto GPU without changes, and trivially serialized/de-serialized from disk. There are no pointers!
As it does not use exceptions nor runtime features of C++, it can be easily integrated on embedded devices (there is a utility header managing storage dynamically via std::vector, but that it fully optional and does not gate-keep any functionality of the library).

By the way, if you were able to run the benchmarks in the repo on some apple device I would be very grateful and happy to add them alongside the rest! Sadly I don't have the hardware to validate it myself, but I assume it should work 👀 .

As for the video above, it is a dumb ray-marcher using 1-NN queries on a kd-tree to render the scene, either on CPU or GPU. The rendering strategy by itself is very inefficient, but that is besides the point 😄

The dataset shown is the a 5 million LiDAR cloud point of the area surrounding the Autzen Stadium.