Efficient Continuous Collision Detection for Bounding Boxes under Rational Motion

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

Authors

• Dan Albocher
• Uzi Sarel
• Yi-King Choi
• Gershon Elber
• Wenping Wang

Keywords

• Motion detection
• Charge coupled devices
• Motion analysis
• Equations
• Algorithm design and analysis
• Computer science
• Prediction algorithms
• Gaussian processes
• Application software
• Robot motion
• Bounding Box
• Collision Detection
• Rational Motions
• Continuous Collision Detection
• Rigid Transformation
• Collision Time
• Dual Representation
• Minkowski Sum
• Axis Parallel
• Path Planning
• Translational Motion
• Topological Changes
• Matched Pairs
• Continuous Motion
• Pair Of Elements
• Convex Polytope
• Motion Path
• Linear Translation
• Minimum Bounding Box