Fast neighbor cells finding method for multiple octree representation

A cell occupancy map has been used widely for efficiently representing obstacles in robotic navigation. Such a map can often be formed based on the multi-resolution octree representation (MOR) of 3D point clouds captured from objects and workspace. This elevated cell-based approach may offer the capability of understanding the geometric context of workspace, expanding its applicability to robotic manipulation in a cluttered workspace. Under this context, the main issue of MOR becomes how to represent and generate cell addresses in such a way as to find neighboring cells efficiently. This paper presents a novel method for efficiently searching for neighboring cells with the fast generation of all the neighboring cell addresses. The original contribution of this paper is that not only the direct neighbors defined by those cells the edges or corners of which are directly connected to the given cell, but also the indirect neighbors of distance r, defined by those cells being separated from the given cell by the distance r, are included. The proposed method have been implemented and applied to obstacle representation in the 3D workspace modeling.