Performance comparison between state-of-the-art point-cloud based collision detection approaches on the CPU and GPU. Issue 30 (2016)

• Record Type: Journal Article
• Authors: Schauer, Johannes; Bedkowski, Janusz; Majek, Karol; Nüchter, Andreas
• Is Part Of: IFAC-PapersOnLine. Volume 49:Issue 30(2016)
• Page Start: 54
• Page End: 59
• Publication Date: 2016
• Subjects: k-d tree -- CUDA -- parallel algorithms -- 3D point clouds -- regular grid decompositio; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2016.11.125
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: We present two fundamentally different approaches to detect collisions between two point clouds and compare their performance on multiple datasets. A collision between points happens if they are closer to each other than a given threshold radius. One approach utilizes the main CPU with a k-d tree datastructure to efficiently carry out fixed range searches around points in 3D while the other mainly executes on a GPU using a regular grid decomposition technique implemented in the CUDA framework. We will show how massively parallel 3D range searches on a grid based datastructure on a GPU performs similarly well as a tree based approach on the CPU with orders of magnitude less parallelization. We also show how each method scales with varying input sizes and how they perform differently well depending on the spatial structure of the input data.