2D Parametric Collision Detection

Today I'm going to describe a method for detecting collisions between arbitrary polygons in 2D. This is part one of a two-part series, in the next post I will show how to make use of this collision detection info to do collision response.

Many collision detection methods simply test for intersection between the two polygons - but what if they are moving at high speed? What if you have a point mass that is supposed to collide with a line? In some cases testing for intersection alone will result in objects clipping through other objects - and simple intersection tests won't tell you the time of collision, the point at which collision occurred, or the normal to the surface of collision, all of which are important for proper collision response. This method will allow us to calculate all three.

Let's start by describing a parametric equation of a line passing through p1 = (x1, y1) and p2 = (x2, y2):

$$\vec{p} = \vec{p}_{1} + t (\vec{p}_{2} - \vec{p}_{1})$$

Or in component form:

$$x = x_{1} + t (x_{2} - x_{1})$$ $$y = y_{1} + t (y_{2} - y_{1})$$

"Parametric" in this case means that the points along the line are described by a single parameter t. When t = 0 we're at p1 and when t = 1 we're at p2. Any t in [0, 1] is found on the segment described by the two points, any t outside of these values is not found on the segment. Another useful property of this form is that we can describe vertical lines equally well, whereas if we were using y = mx + b we would have to special case situations with vertical lines.

When a collision occurs, it's between a point on polygon A and a line segment on polygon B, or vice versa. So if we can do collision between a moving point and a moving line, then we can easily extrapolate to collision between two moving polygons.

Consider the situation where point p1 moves to point p2 as time t1 goes from 0 to 1. Line segment l1, l2 moves to become l3, l4 during the same frame.

So we have p1 going to p2, l1 going to l3, and l2 going to l4 as t1 goes from 0 to 1. To make notation a bit simpler I'll introduce intermediate points a and b that correspond to l1 going to l3 and l2 going to l4 respectively.

$$\vec{p} = \vec{p}_{1} + t_{1} (\vec{p}_{2} - \vec{p}_{1})$$ $$\vec{a} = \vec{l}_{1} + t_{1} (\vec{l}_{3} - \vec{l}_{1})$$ $$\vec{b} = \vec{l}_{2} + t_{1} (\vec{l}_{4} - \vec{l}_{2})$$

We have another parameter t2 describing the line from intermediate point a to b, which may or may not intersect with the line going from p1 to p2.

$$\vec{p} = \vec{p}_{1} + t_{1} (\vec{p}_{2} - \vec{p}_{1}) = \vec{a} + t_{2} (\vec{b} - \vec{a})$$ $$= (\vec{l}_{1} + t_{1} (\vec{l}_{3} - \vec{l}_{1})) + t_{2} ((\vec{l}_{1} + t_{1} (\vec{l}_{3} - \vec{l}_{1})) - (\vec{l}_{2} + t_{1} (\vec{l}_{4} - \vec{l}_{2})))$$

We need to solve for the two unknowns t1 and t2, and luckily we have two equations once we break up the above into x and y components. There are quite a few symbols but I solved for t2 in the equation with y-components, then subbed out t2 in the equations with the x-components and isolated t1. As a result we get a quadratic equation of the form at12 + bt1 + c = 0 where a, b, and c are the following:

$$a = (y_{l3} + y_{l2} - y_{l1} - y_{l4})(x_{p2} + x_{l2} - x_{p1} - x_{l4}) -$$ $$(y_{p2} + y_{l2} - y_{p1} - y_{l4})(x_{l3} + x_{l2} - x_{l1} - x_{l4})$$

$$b = (y_{l1} - y_{l2})(x_{p2} + x_{l2} - x_{p1} - x_{l4}) +$$ $$(x_{p1} - x_{l2})(y_{l3} + y_{l2} - y_{l1} - y_{l4}) -$$ $$(y_{p1} - y_{l2})(x_{l3} + x_{l2} - x_{l1} - x_{l4}) -$$ $$(x_{l1} - x_{l2})(y_{p2} + y_{l2} - y_{p1} - y_{l4})$$

$$c = (y_{l1} - y_{l2})(x_{p1} - x_{l2}) -$$ $$(y_{p1} - y_{l2})(x_{l1} - x_{l2})$$

$$t_{1} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

If we solve the quadratic equation for t1 we will get 0, 1, or 2 solutions. We only care about the smallest solution that is between 0 and 1 inclusive such that t2 is also between 0 and 1 inclusive. If there is no such solution for t1, we are done, because there was no collision in the time frame we're considering.

So for each solution between 0 and 1 for t1, we have to go back and solve for t2 to confirm that t2 is also between 0 and 1 - that is, we have to confirm that the collision between the point and the line actually occurred on the segment and not elsewhere on the line.

$$t_{2} = \frac{(\vec{p}_{1} + t_{1} (\vec{p}_{2} - \vec{p}_{1})) - (\vec{l}_{1} + t_{1} (\vec{l}_{3} - \vec{l}_{1}))}{(\vec{l}_{1} + t_{1} (\vec{l}_{3} - \vec{l}_{1})) - (\vec{l}_{2} + t_{1} (\vec{l}_{4} - \vec{l}_{2}))}$$

For simplicity I have shown this as a vector equation, but you need to use either all x or all y components to solve for t2 - and before attempting to solve you will need to check that the denominator is not zero. The denominator will be nonzero for either x or y components as long as the line segment's length was nonzero at the time of collision. And if the line segment did have zero length, we will say that once again this is evidence of no collision and stop the process here.

So now we know collision occurred between the moving point and the moving line segment at time t1, and we can solve for the point of collision with the original parametric equation of a line:

$$\vec{p} = \vec{p}_{1} + t_{1} (\vec{p}_{2} - \vec{p}_{1})$$

To extrapolate this to finding the first collision between polygons A and B, we can just run this algorithm for each point in A and each line segment in B, and vice versa. Keeping track of the time of collision we can find the earliest collision, the point at which collision occurred, and the normal of the line segment where we collided which will be used to apply an impulse force. We can rewind time by 1 - t1 multiplied by the real time between frames in order to prevent intersection between the polygons, and from there we can calculate an impulse force and do collision response.

Demo

You can drag around the start/end points for the point-line collision detection while this demo animates from t1 from 0 to 1 and uses the above equations to check for collisions.

Drawbacks

Depending on how many objects you have and how frequently they collide, this method for detecting collisions may be too computationally expensive. If we have n points on polygon A and m points on polygon B we will end up having O(nm) quadratic equations to solve, in addition to all the other computation that goes into checking point-line collision. A basic intersection test would also be O(nm) but the constant factor for this method I would expect to be much higher.

Beyond computational complexity, using this method I have approximated rotation of the polygons as straight-line movement of individual points. If your polygon rotates completely once per frame but has no translational velocity, there would be no perceived movement from p1 to p2! So this only works if the objects aren't rapidly rotating. If they are, you would need to use more complex parametric equations to represent movement of the points and line segments, which I have not done here.

Robert Fotino

I'm a former computer science student at UCLA, and a game developer in my free time. This site is a place for me to write about whatever I happen to be working on.