Collapsible cubes: Removing overhangs from 3D point clouds to build local navigable elevation maps

Elevation maps offer a compact 2½ dimensional model of terrain surface for navigation in field mobile robotics. However, building these maps from 3D raw point clouds containing overhangs, such as tree canopy or tunnels, can produce useless results. This paper proposes a simple processing of a ground-based point cloud that identifies and removes overhang points that do not constitute an obstacle for navigation while keeping vertical structures such as walls or tree trunks. The procedure uses efficient data structures to collapse unsupported 3D cubes down to the ground. This method has been successfully applied to 3D laser scans taken from a mobile robot in outdoor environments in order to build local elevation maps for navigation. Computation times show an improvement with respect to a previous point-based solution to this problem.