Efi Fogel
home 
contact
 
search
 
[2D][3D][Arrangements]
 

2 Dimensional Collision Detection

Download
mink2d

We have implemented an exact procedure that given a convex polygon P of n edges stored in a direct-access data-structure, and a ray emanating from a point c P in a given direction d finds the boundary edge e P that intersects the ray in O(log n) time. We use this procedure to answer the collision detection and directional penetration depth queries in an exact manner as follows. Given two convex polygons P and Q, it constructs the Minkowski sum M (-Q) in linear time, and applies the procedure on M and an appropriate ray. For example, to detect collision, the ray emanating from the point r M and goes through the origin is chosen, where r is the sum of two points inside P and -Q respectively (e.g., the average of the boundary vertices). Once the intersection edge e is found, it is easy to determine whether the origin is inside or outside M. The procedure performs a binary search on the polygon edges using their slopes as the search key.

We have also implemented a similar procedure that computes the minimum distance between a polygon and an external point. Like the previous one, it also performs a binary search on the polygon edges using their slopes as keys. Each iteration it tests whether an external point o lies in a Voronoi region of an edge. If the test fails, it proceeds clockwise or counter clockwise to the next edge based on whether the point is to the right or to the left of the Voronoi region. We use this procedure to compute the separation distance.

In addition we developed another exact procedure that given two convex polygons P and Q it implicitly builds this portion of the boundary of the Minkowski sum M that intersects a ray emanating from a point p M in a given direction d, in O(log n log m) time. Naturally, this procedure can be applied almost directly to answer the collision detection and directional penetration depth queries. A slightly modified version that computes the separation depth was implemented as well.

We maintain two continuous ranges of edge normals RP and RQ initialized to contain the normals to all the boundary edges of P and Q respectively. They implicitly represent two section of the normal diagrams of P and Q. We choose a polygon, say P, and an edge eP RP. Using a binary search in RQ, we find the consecutive two edges eQ0,eQ1 RQ such that the normal to eQ0 is the largest among the normals smaller than the normal to efont size=1>P (the normal to eQ1 is then the smallest among the normals larger than the normal to eP). Let q be their shared endpoint, then the edge eM = eP + q P Q = M is on the boundary of the Minkowski sum. We test eM for intersection against our ray vec(ro). If the test fails, we narrow down the ranges RP and RQ, alternate the role of P and Q, and search for the next edge. In consequent iterations, we choose the median of the respective range to be the anchor, ensuring that the range reduces by at least half. The time consumption is obviously O(log n log m).

 
Last modified: December 19 2004.
2D 3D AOS