Abstract
Recently the area of motion planning research has been experiencing a significant resur- gence of interest based on hybrid working environments that combine point and CAD models. Companies are able to work with point clouds and perform certain operations, such as path-planning, but they lack the support for fast shortest-distance computations for point clouds with more than tens of millions of points. Therefore, there is a need for handling and pre-processing massive point clouds for fast-queries. In this thesis, algorithms have been developed that are capable of efficiently pre- processing massive point clouds for fast out-of-core queries allowing rapid computation of the exact shortest distance between a point cloud and a triangulated object. This is achieved by exploiting fast approximate distance computations between subsets of points and the triangulated object. This approach was able to compute, on average, the shortest distance in 15 fps for a point cloud having 1 billion points, given only 8 GB of RAM. The findings and im- plementations will have a direct impact for the many companies that want to perform path-planning through massive point clouds since the algorithms are able to produce near real-time distance computations on a standard PC.
Acknowledgement
First of all I would like to thank Evan Shellshear for his excellent supervision and feed- back throughout this thesis work. I would also like to express my gratitude to my supervisor and examiner from Chalmers, Thomas Ericsson, for his interest in this thesis. In addition, I would like to acknowledge Chalmers University of Technology and the Department of Mathematical Sciences, and everyone at FCC.
Authors and Affiliations
- D. Eriksson, Fraunhofer-Chalmers Centre