KDTree / BVH construction on GPU

Hi (i hope this is not offtopic here)

I’m looking for informations/publications how to CONSTRUCT KDTree (preferably with SAH) or BVHTree on the GPU.

There is a plenty of articles on how to traverse those structures on the GPU, and very little or none on construction of those.

I’m writing raycasting engine (using CUDA), and all is fine i can cast ~17M rays /second on my 8800 GTX (ShortStack KDTree builded with SAH) but I’m doomed to static scenes now, so I’m searching the way to add dynamic meshes to the engine.

Rebuilding the KDTree on the fly on the CPU is way too slow, BVH can be updated not just rebuilded from scratch, but again this is too slow on the CPU.

Any ideas, publications links ?


Has anybody implemented the KD-Tree construction as described in the paper in the above link? Looking at the code they use lists over and over, but there are no lists on GPUs, only arrays? Could anybody maybe explain this to me?

If by “lists” you mean linked lists, these are certainly possible on the GPU, but are not usually the most efficient way of doing things since you need to coalesce memory reads for maximum bandwidth.

I haven’t read the paper, but I assume when they say “lists” they actually mean tightly packed arrays. By the sounds of things they use scan to compact sparse arrays.


For BVH construction: http://www.cs.unc.edu/~lauterb/GPUBVH/