Collision Detection Technique for 2D Rotating

Convex Polygon

By Joshua Cantrell

concept last updated: 10-25-99
page last updated: 11-14-00

INTRODUCTION

After coming up with a method to stop objects moving in straight lines from colliding with each other (read Collision Detection Technique for 2D (Convex Polygon)), I was reminded that sometimes an object must turn. This can happen both while moving forward, making an arc like motion, or simply turning in place. This can be solved in two ways:
In my discussion on straight line collision detection, I was able to find out exactly (or a close approximation due to numerical quantization errors) where the two objects collided with each other. For turning the solution of this question becomes more difficult, which in turn means it is computationally complex. The good news is that it is possible if you really need the information for your simulation.

IDEAS BEHIND THE METHOD

Using my previous article on 2D collision detection as an introduction to the topic, I will be continuing from where I left off. The question about collision due to moving in an arc and turning in one place is certainly something which can happen in any type of simulation. In fact, moving in higher order curves is also a possibility (but too complex to really be feasible)! There are two ways of approaching this problem:
The first approach is easier to see from our perspective, and is also the first way I will solve the problem. The second approach is much more approximate, but is practical when the approximation is acceptable. Modifying the environment to accommodate the previous algorithm rather than fitting an algorithm to the environment has the added benifit that it can be applied to many other problems where an algorithm with a line-path is available, yet an algorithm for an arc-path is desired.

FUNDAMENTAL MATH CONCEPTS USED

For both the first brute force approach and object transformation methods, simple polar coordinate and trigonometric math is required. In the brute force approach, finding the point of collision is done through an algorithm which recursively approximates the point of collision until the error becomes satisfactorily low.
It should be noted that finding the point of collision due to rotation or arcing can be a computationally expensive process compared to the process of actually detecting a collision. I have tried to think of ways around this problem, but have not thought of an answer yet. (Considering that I am not researching this topic either, it may be this way for awhile.)

FEATURES OF ROTATING/ARCING A 2D LINE SEGMENT

The brute force method is composed of finding the path a line segment travels in and then finding out if this path conflicts with another object. Of prime importance is whether this path can be easily computed given a reasonable amount of overhead.
What we need for this computation are as follows: Most of this information is easy to come by because it is already needed to simply move the object in an arcing pattern. The position of the center of the arc (the center of the object for turning in place) is required in producing the rotation/transformation matrix which is required to move the points of an object from the original position to the new position.
Observe that the endpoints of the line segment are each a particular distance from the center of rotation. Also notice that they are always this distance from the center of rotation. This tells us that as the line segment rotates the two points will both rotate about the center in a normal circular fashion through a number of degrees (or radians). Anything within the circle that an inner point follows will not cause a collision. Anything beyond the circle that an outer point follows will also not cause a collision.
Finally we need to determine if a collision occurs between the two circles of rotation created by the two endpoints. This can be done using the original line and rotated line. Anything between these two line positions and inside the carefully chosen circle boundaries (to match the movement of the corresponding endpoint) is a collision point.
What is between the two line segments can be found by using the dot product. Each line segment has a vector that represents the direction it points. The dot product between this vector and a vector formed between a point on the line segment and a point on the object will return a positive or negative number depending on whether the point on the object is inside or outside.

2D CONVEX POLYGON ARCING/ROTATING COLLISION DETECTION (1st Way)

The brute force collision detection is done by moving each line segment on the first object (as described above) and seeing if any of the points of the second object collide. If none collide, then the transpose of the matrix can be aquired and each line segment of the second object can be tested against the first object. Note that this will only find any possible point that could have collided. It doesn't say whether the point was the first to collide or not, it only says it would have collided if the movement had been carried out.
If the object(s) are moving around the center of rotation rather than on it, some of the edges can be culled if it is determined that they couldn't possibly result in a collision. Obviously, if an edge is rotating through where the object had been previously, some other edge will collide before this edge. It can then be ignored and reduce the number of edges checked. These edges can be found by finding the vector representing the initial direction of movement of the shape (tangent to the arc) and culling those edges pointing in an opposite direction.

2D CONVEX POLYGON ARCING/ROTATING COLLISION POINT FINDING

Once a collision has been found, if you wish to find out where it occurred, each point where a collision is found to happen must be traced backwards to the location on the edge which caused the collision. The position on the edge is found by taking the distance from the point to the origin of rotation and forming a circle with it. Where this circle intersects the edge is where the collision took place. The arclength which separates the point and the edge is the distance traveled before the collision took place. To find the first point of collision, the shortest arclength must be found and chosen.

MAKING THE ARC LOOK LIKE A STRAIGHT LINE

When objects are undergoing large arc like motions, the amount they rotate per amount traveled forward is very little. This allows us to approximate the turning as a straight line if we move and translate the objects accordingly. If the problem is translated into a straight line of travel problem, then we can easily find out if there is a collision and the points of collision by the old 2D collision detection method.
If we are given two objects, O1 and O2, where O2 is moving in an arc towards O1, we can reposition O1 so that moving O2 in a straight line closely mimics the same effects as encountered along the arc. Here is what we need to do to O1:
The amount to rotate O1 can be determined by the angle between the center of O1 to the origin of rotation and the center of O2 to the origin of rotation. Once this is found, simply rotate O1 to face O2 using the proper 2D rotation matrix.
How far to place O1 in front of O2 can be determined by the distance between the origin of rotation and the center of O2 multiplied by the number of radians that O1 needed to be rotated in order to face O2. This finds the arc length between O2's position and the closest point it swings by O1.
How far to place O1 off to the side of O2 can be determined by the difference in the distances of each one's center from the origin of rotation. It can be seen that this represents the closest that O2 ever comes to O1

2D CONVEX POLYGON ARCING/ROTATING COLLISION DETECTION (2nd Way)

To find out if a collision occurs, simply do the transformation described above, and use the standard straight line displacement collision detection. Using this method, you can find a point of collision, and simply do a reverse transformation on the point to find out where it is approximately in the real world.

joshuacantrell@yahoo.com
(My Home Page) - (My Computer Science Page) - (My Personal Page) - (My Resume)