TABLE OF CONTENTS Shankar Krishnan, AT&+78T Research Labs, Florham Park, NJ, USA
Amol Pattekar, University of North Carolina, Chapel Hill, NC, USA
Ming C. Lin, University of North Carolina, Chapel Hill, NC, USA
Dinesh Manocha, University of North Carolina, Chapel Hill, NC, USA
Hierarchical data structures have been widely used to design efficient algorithms for interference detection for robot motion planning and physically-based modeling applications. Most of the hierarchies involve use of bounding volumes which enclose the underlying geometry. These bounding volumes are used to test for interference or compute distance bounds between the underlying geometry. The efficiency of a hierarchy is directly proportional to the choice of a bounding volume. In this paper, we introduce spherical shells, a higher order bounding volume for fast proximity queries. Each shell corresponds to a portion of the volume between two concentric spheres. We present algorithms to compute tight fitting shells and fast overlap between two shells. Moreover, we show that spherical shells provide local cubic convergence to the underlying geometry. As a result, in many cases they provide faster algorithms for interference detection as compared to earlier methods. We also describe an implementation and compare it with other hierarchies.
The problems of interference detection and distance computation between static or dynamic objects are fundamental to robotics and computer simulated environments. Given two or more geometric models, composed of polygonal or curved boundaries, the goal is to check whether they overlap or...
