An Accurate Distance Algorithm for Octree‐Encoded Objects

Abstract

Abstract Distance algorithms are most frequently used in robotics to determine the distance between two obstacles in the environment of a robot or between a sensor point and an object. Bounding volumes are a common technique; this technique relies on a hierarchical model representation of the two surfaces using axis‐aligned bounding boxes. Formoving objects it is interesting to use unaligned octrees to avoid the wrapping effect that occurs when performing octree decomposition in a common coordinate system after several rotations. We discuss the algorithm for computing accurate enclosures for the distance between objects represented by axis‐aligned or unaligned octrees. This algorithm is based on a new, recently published distance algorithm between two objects represented by axis‐aligned octrees. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)