Efficient continuous collision detection for bounding boxes under rational motion

Abstract

This paper presents a simple yet precise and efficient algorithm for collision prediction of two oriented bounding boxes under univariate (piecewise) rational motion. We present an analytic solution to the problem of finding the time of collision and the feature involved, or declaring that no collision should occur. Our solution can be applied to boxes of any size, under arbitrary rational rigid motion. The algorithm is based on the efficient examination of the Minkowski sum (MS) of the two boxes, using a spherical Gauss map dual representation, and a precise extraction of the collision time, if any, as a solution to a set of rational equations that are automatically derived. © 2006 IEEE.