Fast interference check method using octree representation

摘要

The efficiency of off-line robot teaching with a graphics simulator depends on the speed of the interference check algorithm between the model of the robot and the model of its obstacles. This paper proposes an efficient algorithm whose computational complexity does not depend directly on the number of obstacles and the shape complexity of each obstacle. In this work, the octree representation is adopted as the model of the robot's environment. It registers all obstacles in the environment with a hierarchical structure in positioning. On the other hand, the boundary representation (B-Reps) is adopted as the robot model. It can represent easily a complex robot motion including rotation by updating its coordinates table every sampling interval. The algorithm consists of a basic process which assigns successively each patch of the B-Reps within a region to some of the eight subregions when the region is divided into them. Then the division is guided recursively by the hierarchical structure of the octree. With the aid of both information induced by the assignment for a region and spatial information inherent to the region in the octree, the algorithm can rapidly select only regions that intersect both the robot and its obstacles. From this selection, it follows that the interference check algorithm deals with only parts of obstacles which lie around the robot. As a result, the algorithm runs rapidly even in a cluttered environment. Finally, the computational complexity of the algorithm is evaluated, and the reasonableness of the evaluation and the efficiency of the algorithm are further ascertained by several experiments.