An efficient online algorithm for direct octree construction from range images

Abstract

We present an algorithm for direct octree construction from range images. It uses a key property of most range sensors that all the voxels on sensed object surfaces are "visible" from the sensor. This enables us to define a projection map for range images. The projection map is used for efficiently checking if a given voxel is in the free region. Furthermore, this key property also reduces the number of faces to be checked for the nodes when constructing octrees. The algorithm is efficient in both memory space and run time, and is useful for sensor-based articulated robot motion planning, which is the main motivation for this work.