Approximate Distance Queries for Path-planning in Massive Point Clouds

David Eriksson, Evan Shellshear

2014

Abstract

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.

Paper Citation

in Harvard Style

Eriksson D. and Shellshear E. (2014). Approximate Distance Queries for Path-planning in Massive Point Clouds . In Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO, ISBN 978-989-758-040-6, pages 20-28. DOI: 10.5220/0005002000200028

in Bibtex Style

@conference{icinco14,
author={David Eriksson and Evan Shellshear},
title={Approximate Distance Queries for Path-planning in Massive Point Clouds},
booktitle={Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,},
year={2014},
pages={20-28},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005002000200028},
isbn={978-989-758-040-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,
TI - Approximate Distance Queries for Path-planning in Massive Point Clouds
SN - 978-989-758-040-6
AU - Eriksson D.
AU - Shellshear E.
PY - 2014
SP - 20
EP - 28
DO - 10.5220/0005002000200028