TR-IIS-03-001    PDF format

Abstract

In the collision detection literature, use of ellipsoidal fits has been successfully made to accelerate the detection beyond polyhedron based methods. In this paper, we propose some improvements to the state-of-the-art work of this methodology. These improvements are made in the following three respects that are crucial to the overall performance of a collision detector. First, object-modeling robustness is enhanced by adopting a recent reliable algorithm for computing the maximum-volume inscribed ellipsoid. Second, detecting efficiency is furthered by avoiding reference to polyhedral models. Third, detecting accuracy is also improved by a correction of ellipsoidal overlap checking. These improvements have been verified by extensive numerical experiments using randomly generated convex polyhedra.

Keywords: Approximation, collision detection, ellipsoid, convex polyhedron, overlap checking, efficiency, accuracy