Circle-line collision: using line's normal to find time of intersection
Author
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.
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.
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.
Author
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:
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.
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.
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.
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.
Author
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?
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?
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)
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)
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 :)
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 :)
Author
Thanks for the link, Lord Bart.
I eventually came up with this:
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:
Unfortunately, the ship passes completely through the line now.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
