Massively Parallel Nearest Neighbor Queries for Dynamic Point Clouds on the GPU

We introduce a parallel algorithm to solve approximate and exact nearest neighbor queries on the GPU, exploiting its massively parallel processing power. Both data structure construction and nearest neighbor queries are performed on the GPU, avoiding memory copies from system memory to device memory. This algorithm achieves real-time performance, enabling its usage in dynamic scenarios, by minimizing the sorting comparisons needed for a large K value. The underlying data structure for spatial subdivision handles 3D points and is based on grid spatial hashing. Users can specify the grid size interactively. Comparisons were done with other nearest neighbor algorithms implemented on both CPU and GPU. Our approach clearly surpasses CPU implementations regarding processing time, while it presents a competitive solution to GPU ones. Real-time results were obtained with ANN searches (K = 10) for data sets up to 163 K points and the potential of our algorithm is demonstrated through a point-based rendering application.