Wednesday, June 10, 2009

Collision Detection for Fast Objects and Circle-Line Intersection

In my current project I produced my own little set of classes for simulating physics.  It's very unrealistic, at this point, because realistic physics makes it very difficult to implement a thrust control AI.  More on that another time.  For now, I'm talking collision detection.

The objects I'm dealing with are very small relative to the velocities at which they may travel.  These are spacecraft and projectiles moving at realistic speeds -- not like one would see in a game like Star Control or indeed most other space sims, where craft seem to move slower than modern aircraft do.  In my program, projectiles like missiles are often moving so fast that simply collision detection allows them to pass right through their targets.  That's a problem.

The easiest solution to this is to simply use a smaller timestep.  I've locked the framerate at only 25 Hz, but I step through the physics update functions four times per frame.  As far as the physics is concerned, the actual framerate is 100 Hz.  Even with such a framerate, collisions often fail to register.  The solution I decided upon was to implement a second step to collision detection whereby the system would also look at the area between the object's current position and its previous position.

The basic collision detection simply uses circles.  I detect collisions between the circular collision hulls of the current and previous position by defining a rectangle between them whose side lie tangent to both circles.  The slope of those tangent lines is no chore to discover as the radius of each circle is the same.  The slope is simply the slope of the vector that connects their centres:

# get the positions
x0, y0 = pos
x0p, y0p = prev_pos

# get the distance between the two
dx, dy = x0 - x0p, y0 - y0p
dist = math.hypot (dx, dy)

# normalize the vector
ndx, ndy = dx / dist, dy / dist

slope = ndy / ndx

We will use the normalized vector to determine where the corners of the rectangle lie.  This is found simply by rotating the vector 90 degrees left and right.  Multiply the results by the radius of the circles to produce vectors and add them to the current and previous positions to get the corners.

# get the end-piece slopes
ex0, ey0 = -ndy, ndx
ex1, ey1 = ndy, -ndx

# get the corners of the rectangle
px0, py0 = x0p + ex0 * radius, y0p + ey0 * radius
px1, py1 = x0 + ex0 * radius, y0 + ey0 * radius
px2, py2 = x0 + ex1 * radius, y0 + ey1 * radius
px3, py3 = x0p + ex1 * radius, y0p + ey1 * radius

Assuming that the previous position (x0p, y0p) is to the left of the current position (x0, y0), the top-left point is (px0, py0).  The rest of the points continue clockwise around the rectangle.

What we now need to do is test for a collision between the rectangle and the circular collision hull of the other object.  Cirlce-Rectangle collision occurs when either the circle touches a rectangle edge or when the centre of the circle falls with the bounds of the rectangle.  The latter is easier to test for, of course.

Determining whether a point is within a rectangle is simply a matter of finding which side of each edge the point lies.  Simply:

def get_side (p0, p1, point):
  x, y = point
  x0, y0 = p0
  x1, y1 = p1
  ex0 = x1 - x0
  ey0 = y1 - y0
  ex1 = x - x1
  ey1 = y - y1
  return ex0 * ey1 - ey0 * ex1

The order in which points are entered into this function is important.  Entered clockwise: if the return value is positive, the point lies above the line; if the value is zero, the point lies on the line; if the value is negative, the point lies below the line.  Therefore the point lies within the rectangle if the return value is negative for all sides.

If the centre of the circle is not within the rectangle, it is still possible that it touches one of the edges.  The only two edges we have to test are the top and bottom edges.  The end-pieces lie within the circles of the current and previous position circles, so we need not test them.

I must admit that I had great difficult trying to find an algorithm for Circle-Line Intersection.  I found a few sources where simply code was given, but I prefer an explanation to accompany code.  Eventually it dawned upon me to simply use the equations for lines and circles:

# line
y = m * x + b

# circle
r**2 = (x + x0)**2 + (y + y0)**2

The circle equation is easiest to deal with if simplified to assume that its origin is (0, 0).  Therefore:

r**2 = x**2 + y**2

If we do that, however, we must account for that in the for the line equation.  The easiest way to do that is to simply subtract the origin coordinates from the coordinates of the current and previous positions.

For the line equation, we found the slope, m, previously, and can find b by substituting either the current or previous position coordinates (modified as in the previous paragraph) into x and y.  Solving for b:

b = y0 - m * x0

Now, let us take the original line equation and substitute it for y in the circle equation:

r**2 = x**2 + (m * x + b)**2

Before we try to solve for x, let's evaluate the equation as far as it can go:

r**2 = x**2 + m**2 * x**2 + m * x * b + m * b + b**2

It looks intimidating, but we can turn it into a quadratic equation:

0 = (1 + m**2) * x**2 + m * x * b + m * b + b**2 - r**2

We can then solve for x via the quadratic formula, but to be honest we don't actually need it.  As it turns out, all we need is the result of the discriminant:

D = b**2 - 4 * a * c

The discriminant, after all, exists within the quadratic formula's square-root, which will not result in a real number if the discriminant is negative.  Ultimately, what this means is that the circle does not intersect the line if the discriminant is negative.  If it is not negative, the circle intersects the line at one or two points.

The expressions a, b, and c are extracted from our quadratic equation as follows:

a = 1 + m**2

b = m * b

c = m * b + b**2 - r**2

The resulting discriminant is:

D = m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - r**2)

There are no unknown values in this equation.  We have m, the slope, r, the radius, and b.  Here's the final function for Circle-Line Intersection:

def circle_line_intersection (p0, p1, origin, radius):
    x, y = origin
    px0, py0 = p0[0] - x, p0[1] - y
    px1, py1 = p1[0] - x, p1[1] - y
    dx, dy = px1 - px0, py1 - py0
    if dx == 0.0:
        return radius > abs (px0)
    m = dy / dx
    b = py0 - m * px0
    return m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - radius**2) >= 0.0

I test if dx is equal to zero because if it is, we'll end up with a division-by-zero error.  However, all that means is that the line is vertical.  As such, we can simply test one of the positions' x-coordinates against the radius of the circle.

This form of collision detection will not tell you exactly where the collision occured, of course.  However, that was not relevant to my needs, so I gratefully never considered it.  All I needed to know was whether my projectile had hit something or not, and this works quite well.

There are some problems with this solution, of course.  For example, if the projectile is moving along a curved path, this does not provide a perfect solution, as a rectangle has entirely flat sides.  Right now, however, I don't particularily feel like looking into collisions with arbitrary curves. . .

1 comment:

  1. I think you have a mistake in your line-circle math. What you have here:

    r**2 = x**2 + m**2 * x**2 + m * x * b + m * b + b**2

    should be:

    r**2 = x**2 + m**2 * x**2 + 2 * m * x * b + b**2

    Hope this helps! Otherwise, this was a very helpful post for me. :)