Weller, RenéMainzer, DavidSrinivas, AbhishekTeschner, MatthiasZachmann, GabrielJan Bender and Christian Duriez and Fabrice Jaillet and Gabriel Zachmann2014-12-162014-12-162014978-3-905674-71-2https://doi.org/10.2312/vriphys.20141219Ordinary bounding volume hierarchy (BVH) construction algorithms create BVHs that approximate the boundary of the objects. In this paper, we present a BVH construction that instead approximates the volume of the objects with successively finer levels. It is based on Batch Neural Gas (BNG), a clustering algorithm that is known from machine learning. Additionally, we present a novel massively parallel version of this BNG-based hierarchy construction that runs completely on the GPU. It reduces the theoretical complexity of the sequential algorithm from O(nlogn) to O(log2 n) and also our CUDA implementation outperforms the CPU version significantly in practice.I.3.5 [Computer Graphics]Computational Geometry and Object ModelingObject hierarchiesI.5.3 [Pattern Recognition]ClusteringAlgorithms