Approximate distance queries for path-planning in massive point clouds

D. Eriksson, E. Shellshear. 11th International Conference on Informatics in Control, Automation and Robotics (ICINCO 2014)


In this paper, algorithms have been developed that are capable of efficiently pre-processing massive point clouds for the rapid computation of the shortest distance between a point cloud and other objects (e.g. triangulated, point-based, etc.). This is achieved by exploiting fast distance computations between specially structured subsets of a simplified point cloud and the other object. This approach works for massive point clouds even with a small amount of RAM and was able to speed up the computations, on average, by almost two orders of magnitude. Given only 8 GB of RAM, this resulted in shortest distance computations of 30 frames per second for a point cloud originally having 1 billion points. The findings and implementations will have a direct impact for the many companies that want to perform path-planning applications through massive point clouds since the algorithms are able to produce real-time distance computations on a standard PC.


This work was carried out at the Wingquist Laboratory VINN Excellence Centre, and is part of the Sustainable Production Initiative and the Production Area of Advance at Chalmers University of Technology. It was supported by the Swedish Governmental Agency for Innovation Systems.

Authors and Affiliations

  • D. Eriksson, Fraunhofer-Chalmers Centre
  • E. Shellshear, Fraunhofer-Chalmers Centre

Photo credits: Nic McPhee