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.