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

• Pedro Jose Silva Leite UFPE
• Joao Marcelo Xavier Natario Teixeira UFPE
• Thiago Souto Maior Cordeiro de Farias UFPE
• Veronica Teichrieb UFPE
• Judith Kelner UFPE

Resumo

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 163K points and the potential of our algorithm is demonstrated through a point-based rendering application.

Palavras-chave: Nearest neighbor searches, Clouds, Data structures, Neural networks, Bioreactors, Computer architecture, High performance computing, Computer science, Virtual reality, Multimedia computing, nearest neighbor query, massive parallel programming, KNN, ANN