Stack-free k-d Tree Traversal

Yes, I haven’t written anything on this blog in a while – been too busy coding and already way overdue writing things up in latex/paper form – but since I finally managed to finally finish the write-up for that technique (which by now was overdue for now several years!) I thought I’d celebrate that milestone by at least dropping a note on that technique here, in case it’s useful for others, too….

The technique I’m referring to is a stack-free traversal method for k-d trees – and to be specific, I mean the kind of k-d trees that encode k-dimensional data points https://en.wikipedia.org/wiki/K-d_tree, not the ray tracing-related ones I used so much in my early days of ray tracing research… The algorithm is actually super-simple once you think it through – a write-up in “paper”-form (i.e., with full explanation of how it works) can be found here https://arxiv.org/abs/2210.12859; in addition, if you’re somebody that prefers header-files over PDFs you can also find some sample code here: https://github.com/ingowald/cudaKDTree. The repo that the latter link points to also contains some pretty neat GPU-friendly and parallel builder for left-balanced k-d trees, too (which is arguably even more interesting than the traversal…) … but that’s the topic for another post if and when I ever finish the write-up of that technique (in another few years!?).

Now what’s so interesting about this technique? First, it’s simple, which is always good; but more importantly, it allows you to traverse k-d trees (for photon mapping, point data, p-kd trees, etc) without needing a stack. It’s not necessarily faster than stack-based techniques (and if memory is not a concern a good BVH is almost certainly faster than a k-d tree, anyway), but in my experience on a GPU stacks always come with some strings attached, so I’ve come to now default to this technique if and when I ever need to use a k-d tree. The samples I added to this repo are intentionally small and self-contained; you can use the same technique for other queries, other dimension and data types (templates are your friend…), etc; but I wanted to keep that repo small – feel free to send PRs with other use cases if you have any to share.

With that – have fun!

PS: Again:

• link to whitepaper: https://arxiv.org/abs/2210.12859
• link to sample code: https://github.com/ingowald/cudaKDTree