Implicit convex-hull distance of finite-screw-swept volumes

Abstract

The need for collision detection arises in several robotics areas, including motion-planning, online collision avoidance, and simulation. At the heart of most current methods are algorithms for interference detection and/or distance computation. We presented (1997) an implemented technique for doing exact numerical distance computation and interference detection for translationally-swept bodies and approximate techniques for bodies swept under finite screw motion. Here, we extend the enhanced GJK and Gilbert-Foo, algorithms to obtain exact numerical distance computation and interference detection between the convex hulls of the volumes swept by two convex polyhedra under finite screw motions. This algorithm enables conservative distance and collision computations that are both tighter and more efficient than the previous result. It has been integrated into a bounding-volume hierarchy distance/interference code to extend the result to facetted non-convex rigid bodies.