A fast algorithm is presented to measure obstacle shape in the workspace and to register the shape to the octree that is suitable for path and motion planning of the robot. The octree is constructed hierarchically by a set of cubic regions in the workspace, and its data structure is suitable for detecting interference between a moving robot and its obstacles and searching for a free region in the robot path planning.>

A fast, efficient, algorithm that processes polyhedral cones from views of an object to produce an octree representation of the object is proposed. A polyhedral cone defined by both a viewpoint and a polygonal contour of the object in the image for each view always contains the object. Thus the common region of the cones for multiple views is considered to be an approximating one of the object. The octree representation controls all cubic regions in three-dimensional space as a set of nodes with a hierarchical description in positioning, and therefore is suitable for registration of the common region. The computational complexity of the algorithm is directly proportional to the common region surface area and exponentially proportional to the finest resolution level of the octree. The calculation time of the algorithm is determined for illustrative examples of three-dimensional objects.>