Solving Collision Detection Problems Using Algebraic Methods

Collision detection problem is a basic problem in computer simulation, CAD, robotics. It is mainly used to enhance the reality of virtual scene or applied for robot path planning. Collision Detection algorithms are different for different applications, providing different information. Some applications require collision detection algorithm to give information of whether the collision occurred along their respective moving course of these two objects. Other applications require collision detection algorithm not only to give whether the collision occurred, but also to provide distance information: the shortest puncture distance between these two objects when there is a collision along their moving course and the minimum separation distance between these two objects when there is no collision.Currently, there are many collision detection methods. Usually, they are divided into two major categories: one is discrete collision detection, like algorithms based on computational geometry, based on separation plane, based on graphics hardware etc.; the other is continuous collision detection, such as swept volume method, algorithm based on duality and Minkowski Sum, algorithm based on KDS (Kinetic Data Structure) and algebraic methods. Discrete Collision Detection Methods of two moving objects use time sampling. In each sampling time we judge whether the two static objects collide. In this kind of method, if the speed of moving objects is very high, or objects are very small, collision during interzone of two sampling time may be missed. W can improve accuracy through shortening the time sampling interval, but this will reduce efficiency. Continuous Collision Detection methods constructed a continuous path. Based on the path between objects we judge whether these two objects collision. We studies continuous collision detection using algebraic methods. There are two algorithms: one is collision detection of two curve polygons, another is collision detection and distance information of two moving LSS (Linearly Swept Spheres).In algebraic method, collision condition using algebraic expression of two stationary objects is proposed, then the movement of objects modeled as a function of time. Based on these former two factors, collision condition between two moving objects is proposed.Algebraic method has been used for collision detection of two elliptic discs and ellipsoids. Collision detection of two elliptic discs cannot be used directly to solve problem of collision detection between two curve polygons. Ellipsoid as a bounding volume cannot envelop objects very tight, such as the arms, in which case LSS will be better.Present collision detection methods of curve polygons, like method based on graphics hardware and method based on KDS is directed at polygon. Method based on the graphics hardware uses repeating detection method. Method on KDS solve problem of general motion need to decompose motion in each direction, increasing the algorithm's complexity.Contents of this paper: quadratic curve segments set is used to represent polygon; use Rational movement as motion of objects in two and three dimensional space; calculated equations of motion through interpolation of the dynamic image control points of motion trajectory; propose collision detection of two quadratic curve segments under rational motion; propose collision detection algorithm of two moving curve polygons using direct computation of curves; Bernstein polynomial form of the solution; bounding box is used to improve the efficiency of algorithms; distance formula is used in collision detection between two LSS, which is formulated into nine polynomials; Bernstein polynomial form of the solution; compute distance information: the shortest puncture distance between these two objects when there is a collision along their moving course and the minimum separation distance between these two objects when there is no collision.Main contributions:1) propose algebraic collision detection method of two moving conic segments;2) direct use of planar curves in the polygon collision detection algorithm. The algorithm is more precise than former curve polygons collision detection algorithms, and its efficiency is also high. Polygon represented using conic segments requires only one degree continuity at the end points;3) propose fast and efficient collision detection algorithm of two moving LSS as bounding volumes; compute distance information: the shortest puncture distance between these two objects when there is a collision along their moving course and the minimum separation distance between these two objects when there is no collision.