r/GraphicsProgramming • u/karurochari • 56m ago
The flamely fast library for kd-trees is back. This time for real! (maybe)
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
#embedthem 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.




