Collision Detection Technique for 2D

Convex Polygon

previously updated: 9-22-99 minor update: 2-28-03

INTRODUCTION

Even with the event of graphics acceleration cards, I don't know of any helper cards for collision detection. (I assume that is the next step.) For this reason, it makes sense that I must design my own routines to detect and handle collisions of freeform objects moving in a dynamic world. I certainly don't want object bouncing around at great distances from each other, or just as bad, flying right through each other without flinching!

IDEAS BEHIND THE METHOD

After much thought on the issue, I decided to go back to basic 2D math relationships. This has to do with points, lines, and vectors. The reason why I decided to start simple was that sometimes I find it easier to build complex algorithms from simpler identities and algorithms. If you can be assured of successful implementation of simple algorithms and build upward with success at each step, then the finished product is sure to work! :-)

My discussion starts with the intersection of two line segments. Then I move on to whether or not a point exists within a bounded convex polygon. Then I finally discuss how collision detection can be done given a displacement vector.

FUNDAMENTAL MATH CONCEPTS USED

Without the understanding of certain math concepts, it may hard to understand everything that goes into collision detection. This is one reason why I think good programmers should feel comfortable with math. (It's only an opinion, so don't jump on me if you hate math.)

Recall that the dot product, u.v, is equal to ||u||*||v||*cos(theta) where ||u|| represents the magnitude of the vector u and theta is the angle between the vectors u and v.

The cross product, which I'll symbolize as uXv results in a vector that is orthogonal (perpendicular) to the vectors involved in in the operation. The magnitude of the vector is given by ||u||*||v||*sin(theta) where theta is the angle between the vectors moving in the direction from u to v (the right hand rule). The cross product doesn't have much meaning in 2D, but the magnitude is extremely useful because of the sin(theta). Since any two vectors (not pointing in the same direction) on the 2D xy-plane will always point along the z-axis, the cross product easily provides us with the magnitude and direction of the vector. If the resultant vector points along increasing z, then theta must be between 0 and 180 degrees (0 and PI radians). A vector pointing along decreasing z means theta must be between 180 and 360 degrees (PI and 2*PI radians).

The cross product can be understand by using the the right-hand rule. Point your hand in the direction of the u vector, then bend your fingers in the direction of the v vector, and keep your thumb pointing up, perpendicular to your hand and finger directions. Unless you are double jointed (bending your fingers backward), you'll either have to point your thumb up or down. :) Up is positive, and down is negative. Remember to use your right hand! Doing this might help you visualize how some of the vector math works.

To find the point where two lines intersect, simply solve the system of equations. You have two equations and two unknowns. This can be solved through either substitution (my favorite), or setting up the following linear algebra equation and solving for x and y.

        [A1, B1]   [x]   [C1]
        [A2, B2] * [y] = [C2]

INTERSECTION OF 2D LINE SEGMENTS

There are two steps to find an interesection of two 2D line segments. They are:

POINT IN 2D CONVEX POLYGON

For each side of the 2D Convex Polygon, you must determine if the point is on the inside or outside of a side. This is done using the cross product. If we move clockwise around the polygon forming vectors, and take the cross product of these with a vector formed from a point on the same side to the desired point, we can know if it is on the inside or outside by the sign of the resultant vector's direction along the z-axis.

If it's increasing (symbolized by the dot with a circle around it) it's coming towards us, and it's outside. If it's decreasing (symbolized by a cross with a circle around it) it's going away from us, and it's inside. If the point is found to be inside all of the sides, it is inside the polygon, otherwise it is outside the polygon.

2D CONVEX POLYGON COLLISION DETECTION (1st Way)

Collision detection can be done in two ways. Either determine whether two polygons overlap after being moved, or if a moving polygon intersects another polygon. I prefer the latter because it insures that objects will not skip through other objects if they travel at extraordinary speeds.

Given the two objects and their displacement vector, all sides pointing away from the direction of displacement are culled away. We can do this in part because we make the assumption that the objects are not already intersecting each other. This means only a change in position could cause them to collide and whatever doesn't move won't make a difference. The endpoints from the culled sides then become points of new sides formed by moving all the remaining points by the displacement vector.

The last step is simply to first check and see if any of the line segments forming the sides intersect. If any of them do, a collision was detected. If none intersect, there is still one possibility which is that the object's region of displacement enveloped the other object, so simply test to see if one of the other object's points is in the region of displacement. If one of them is in there, they must all be in there and a collision occured!

2D CONVEX POLYGON COLLISION DETECTION (2nd Way)

There is yet a second way to find out if two polygons have collided with each other. First cull the vertices from both objects which are not connected to a side that can cause a collision. The moving object has the sides pointing away from the motion removed, and the stationary object has the sides pointing in the direction of motion removed.

To perfrom the culling, you take the cross product of the edge's vector with the displacement vector, you'll get either a positive or negative value. If all the edge vectors are aligned in the same direction around the polygon, then this cross product will produce one sign for facing the displacement and the other sign for facing away from the displacement. You only need to be concerned with the ones facing the displacement.

Line segments are now created starting from each remaining vertice. The line segments are created by finding a second point through the following processes: (1) Vertices on the moving object are added to the displacement vector. (2) Vertices on the stationary object are added to the negative of the displacement.

These line segments are then tested for collision with the unremoved sides. Any intersection means that a collision has occured. The bonus about this method of collision detection is that you can find out where the collision occured. By comparing the distances from the points of collision to the original vertices that caused the them, you can find out which vertice was the first to collide. The vertice that traveled the shortest distance wins!

2D CONVEX POLYGON COLLISION REGION FINDING
Once a collision has been found, if you wish to find out where it occurred, the second collision detection technique should be used. This not only tells you that the collision occured, but where it occured.

joshuacantrell@yahoo.com

(My Home Page) - (My Computer Science Page) - (My Personal Page) - (My Resume)