• Advertisement
Sign in to follow this  

Circle-line collision: using line's normal to find time of intersection

This topic is 4709 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

O.K. I'm making a collision test for moving circles and stationary lines. I'm able to find the normal of the line and find the circle's intersection point. My question is, how do I find at what time the circle makes contact with the line? How do I find the distance the ball can travel before collision? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
You're probably close to the solution already, but...

The circle has center C and radius r. The equation for the line is p.n = d, where p is any point on the line, n is the line's unit-length normal, and d is the line distance. The equation p.n - d gives you the signed distance from p to the line.

The circle has velocity V, and traces out the ray C+tV as it moves. We are interested in finding the times (values of t) at which C is exactly a distance of + or - r from the line. +r is when it touches on the front side, -r on the back.

Substituting C+tV into our distance-point-line function, we have:

f(t) = (V.n)t+(C.n)-d

This function gives the signed perpendicular distance from C to the line at time t. To find the times at which the circle just touches the line, set the function to + or - r and solve:

(V.n)t+(C.n)-d = +/- r

t0 = (d-(C.n)+r)/(V.n)
t1 = (d-(C.n)-r)/(V.n)

There are various issues you'll have to deal with, such as deciding which sides of the line are valid for colliding, and catching the nearly-parallel case. Depending on the circumstances there are also various opportunities for early-outs.

As always, I could have messed something up somewhere, but that's the general idea.

Share this post


Link to post
Share on other sites
Well, I tried that, but now my circle jumps around the screen wildly. :P

Just to clairify, C.n and V.n are dot products right? So, C.n = (Cx * nx) + (Cy * ny), right? As for t0 and t1, you use the equation for t0 to find when the circle hits the front of the line and t1 to find when the circle hits the back, right?

Here's the java code I'm using:
[source="java"]
private double calculateTranslation(Ship ship, Line2D line) {
// Find vector from (x1, y1) to (x2, y2) of line.
double dLx = line.getX2() - line.getX1();
double dLy = line.getY2() - line.getY1();
// Length of dL.
double dL = Math.sqrt((dLx * dLx) + (dLy * dLy));

// Normalize this vector.
dLx /= dL;
dLy /= dL;

/* Find vector from (line.getX1(), line.getY1())
to (ship.x(), ship.y()). */

double dPLx = ship.x() - line.getX1();
double dPLy = ship.y() - line.getY1();

// Find magnitude of component of dPL parallel to dL.
double dotprod = (dPLx * dLx) + (dPLy * dLy);

// Find shortest vector from ship to line.
double dNx, dNy, dN;
if (dotprod >= dL) {
// Vector from the ship to the line's end-point.
dNx = line.getX2() - ship.x();
dNy = line.getY2() - ship.y();
}
else if (dotprod <= 0) {
// Vector from the ship to the line's start-point.
dNx = line.getX1() - ship.x();
dNy = line.getY1() - ship.y();
}
else {
// Vector from the ship to the line (line's normal).
dNx = (line.getX1() + (dLx * dotprod)) - ship.x();
dNy = (line.getY1() + (dLy * dotprod)) - ship.y();
}
// Magnitude of vector.
dN = Math.sqrt((dNx * dNx) + (dNy * dNy));
// Normalize this vector.
dNx /= dN;
dNy /= dN;

// Point on ship's radius collision occurs.
/*double Cx = ship.x() + (dNx * ship.radius());
double Cy = ship.y() + (dNy * ship.radius());*/


double dV_dot_dN = (ship.dx() * dNx) + (ship.dy() * dNy);
double p_dot_dN = (ship.x() * dNx) + (ship.y() * dNy);

double time = (dL - p_dot_dN - ship.radius()) / dV_dot_dN;

if (time >= 1.0)
return 1.0;
else
return time;
}


There're no early escape tests yet. Time is measured in frames, and the value returned by this method is passed to the ship when it's position is updated.

Share this post


Link to post
Share on other sites
Looked at the code; I think you may be misunderstanding a few things about the algorithm, which is why it's not working. Also, it looks like you want to intersect the circle with a line segment rather than an infinite line, which has to be handled a little differently.

A line in 2d is similar to a plane in 3d; in fact, the equations I posted for circle-line intersection are the same as those for sphere-plane intersection. This thread has some discussion of planes and how they are represented that might be helpful to you.

Anyway, please ask if you have other specific questions. Also, I do have some code for this lying around. It's not production-quality, but if you think a reference would be helpful I'd be glad to post it.

Share this post


Link to post
Share on other sites
I found a tutorial at <url>http://www.gamespp.com/algorithms/collisionDetectionTutorial02.html</url> that deals with what I'm wondering about. It talks about a ray intersecting an infinite plane. The function devised returns the distance between the ray (source point & vector) and the plane or a negative number if the ray doesn't intersect the plane.

The problem is that it uses a "planeD" variable to find "the plane's distance from the origin minus the ray's distance from the origin." What's this planeD thing?

Share this post


Link to post
Share on other sites
If you have the plane normal 'n', and you have a point 'p' known to be on the plane, then 'planeD' is simply Dot(p, n).

It's exactly the same with lines. You know the endpoints of the lines; they are both on the line, so you can substitute either of them in for 'p'. The (unit-length) normal to the line with endpoints p0 and p1 is:

n = normalize(perp(p1-p0))

Then for the value equivalent to 'planeD':

d = Dot(p0, n)

Or:

d = Dot(p1, n)

Share this post


Link to post
Share on other sites
Hello Zaxx,

If your circle travel paths describe by a math formula take a look at my old web site.

http://www.angelfire.com/fl/houseofbartlett/solutions/solution.html

It has some code and explanation for bullet and sphere and some other hit test.

Cicrles are Spheres in 2D, and bullets travel a stright line path.

Lord Bart :)

Share this post


Link to post
Share on other sites
Thanks for the link, Lord Bart.

I eventually came up with this:

// Find line's distance from origin minus ship's distance from origin.
double planeD = (line.getX1() * dNx) + (line.getY1() * dNy);
double deltaD = planeD - ((ship.x() * dNx) + (ship.y() * dNy));
double ship_line_distance = (deltaD / cosAlpha) - ship.radius();

if (dV <= ship_line_distance)
return 1.0;

double time = ship_line_distance / dV;
return time;


This works fine when the ship hits the line straight on, but there's still penetration when the ship comes in at an angle.

I also tried replacing ship.x() and ship.y() with what are supposed to be the coordinates of the point of penetration on the ship's radius, which I got this way:

// Find intersection point on ship's radius.
double Ix = (-dNx * ship.radius()) + ship.x();
double Iy = (-dNy * ship.radius()) + ship.y();


Unfortunately, the ship passes completely through the line now.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement