Collision detection based on inner-outer ellipsoidal approximation: Some improvements

For collision detection of convex polyhedra, use of inner-outer ellipsoidal fits as boundary representation has been reported to be effective in accelerating the detection as compared to exact polyhedron based methods with a good balance of accuracy. In this paper, we propose some improvements that are crucial to the overall performance of collision detector based on enclosed ellipsoid. The improvements are: First, detecting accuracy is improved by (1) a robust reliable algorithm for computing the best inner-outer ellipsoidal fit that ensures a reasonable tight approximation of convex polyhedron, and (2) exact overlap checking of two ellipsoids. Next, detecting efficiency is done by avoiding the reference to polyhedral object models. The enhancement of performance is verified by extensive numerical experiments on randomly generated convex polyhedra pairs.