Parallel BVH construction using k-means clustering

We propose a novel method for fast parallel construction of bounding volume hierarchies (BVH) on the GPU. Our method is based on a combination of divisible and agglomerative clustering. We use the k-means algorithm to subdivide scene primitives into clusters. From these clusters, we construct treelets using the agglomerative clustering algorithm. Applying this procedure recursively, we construct the entire bounding volume hierarchy. We implemented the method using parallel programming concepts on the GPU. The results show the versatility of the method: it can be used to construct medium-quality hierarchies very quickly, but also it can be used to construct high-quality hierarchies given a slightly longer computational time. We evaluate the method in the context of GPU ray tracing and show that it provides results comparable with other state-of-the-art GPU techniques for BVH construction. We also believe that our approach based on the k-means algorithm gives a new insight into how bounding volume hierarchies can be constructed.