Visibility of point clouds and exploratory path planning in unkown environments. (English) Zbl 1162.65318

Summary: We present an algorithm for interpolating the visible portions of a point cloud that are sampled from opaque objects in the environment. Our algorithm projects point clouds onto a sphere centered at the observing location and performs essentially non-oscillatory interpolation of the projected data. Curvatures of the occluding objects can be approximated and used in many ways.
We demonstrate how our visibility formulation can be incorporated into novel algorithms for mapping unknown environments with single or multiple observers, and target finding problems. A convergence proof is provided indicating suitability of our algorithm for some canonical types of environments. Various postprocessing optimization techniques are considered to obtain a more uniform exposure of the region along the path.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65D05 Numerical interpolation
68T40 Artificial intelligence for robotics
68T45 Machine vision and scene understanding
Full Text: DOI