Massively-Parallel Proximity Queries for Point Clouds

Abstract

We present a novel massively-parallel algorithm that allows real-time distance computations between arbitrary 3D objects and unstructured point cloud data. Our main application scenario is collision avoidance for robots in highly dynamic environments that are recorded via a Kinect, but our algorithm can be easily generalized for other applications such as virtual reality. Basically, we represent the 3D object by a bounding volume hierarchy, therefore we adopted the Inner Sphere Trees data structure, and we process all points of the point cloud in parallel using GPU optimized traversal algorithms. Additionally, all parallel threads share a common upper bound in the minimum distance, this leads to a very high culling efficiency. We implemented our algorithm using CUDA and the results show a real-time performance for online captured point clouds. Our algorithm outperforms previous CPU-based approaches by more than an order of magnitude.