Continuous Collision Detection for Elliptic Disks
Yi‐King Choi, Wenping Wang, Yang Liu, Myungsoo Kim · 2005
Collision detection and avoidance is important for various tasks in robotics. Compared with commonly used circular disks, elliptic disks provide compact shape representation for robots or other vehicles confined to move in the 2D plane. Furthermore, elliptic disks allow simpler analytic representation than rectangular boxes do; this makes it easier to perform continuous collision detection. We shall present a fast and accurate method for continuous collision detection between two moving elliptic disks; continuous collision detection does not need to sample the time domain of motion, thus avoiding missing possible collision between time samples. Based on some new algebraic conditions on the separation of two ellipses, we reduce collision detection for two moving ellipses to the problem of detecting real roots of a univariate equation which is the discriminant of the characteristic polynomial of the two ellipses. Various techniques are investigated in detail for robust and accurate processing of this univariate equation for two classes of commonly used motions: (1) planar screw motions; and (2) planar rational motions, i.e. motions that can be represented as rational functions of the time parameter t. Experimental results are presented to demonstrate the efficiency, accuracy and robustness of our method.