Sign in to follow this  
Zaxx

Reliable collision between circles and lines.

Recommended Posts

Zaxx    142
I give up. I'm trying to devise a method to detect collision between a moving circle and a stationary line. I'm keeping track of time, so I want to calculate the time (between times 0 and 1) when the circle hits the line. I've spent more than a week trying numerous algorithms, using numerous formulae, reading numerous web pages and revising my code over and over again. But in the end my circle still slips past my wall somehow. Does anyone know where I can find a completed algorithm or code for collision between a circle and a line which can give me the time of collision and is easy to understand? I'm sorry to ask this but as I said it's been more than a week since I've started this and I've gotten no-where. Thank you anyway.

Share this post


Link to post
Share on other sites
jyk    2094
Hi,

The first step is to make sure the terminology is clear. You may very well be saying exactly what you mean, but quite often people use the term line when they actually mean line segment. As you probably know, a line is infinite while a segment is bounded, that is, it has a start and end point.

Anyway, I'd be glad to help you with this. I'm pretty sure I have completed code lying around somewhere for both lines and segments that you could use as a reference. Also, you might post your code in its current form so we can see what you've already tried.

Share this post


Link to post
Share on other sites
Zaxx    142
So we're clear, I am wanting to use segments.

Here's my algorithm:

I treat the line as a vector extending from its start point and find the normal of this vector. I then find the full vector from the line's start point extended to the circle's center. I find the dot product of this vector and the line's normal vector, clamping it if it's less than 0 or longer than the line. I now find the projection vector of the circle's center onto the line, which is the normal vector of the line multiplied by the dot product then added to the line's start point and finally subtracted from the point of the circle's center (what a mouthful). I can now find the shortest distance between the circle and the line segment.

As an early escape, I find the magnitude of the circle's velocity. If it's less than the shortest distance minus its radius, there's no possible collision. This part I can get.

Now I do an intersection test. I first find the point of intersection of the circle, which is the negative of the normalized projection vector multiplied by the circle's radius. I now have a line that's the circle's velocity vector starting at its intersection point. I take this vector's endpoints (right now I'll call them p3 and p4) and compare them to the line's endpoints (p1 and p2). I plug these values into the equations in this picture:

[img]http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/lineline2.gif[/img]

To start off, this is where I get a problem (I probably have problems after this, but I'll start with this one). The source I got those equations from said that if Ua and Ub are both within 0 and 1 the intersection point is within both line segments. So I did a check for if either value isn't within 0 or 1. That should mean the line segments don't cross so there isn't a collision. But my code seems to never detect the lines crossing, so no collision is ever detected. >:(

Here's my code in Java:
[source="java"]
/* Returns a time value for b's movement between 0 and 1.
The time is less than 1 if b will collide with the wall. */

private double calculateTranslation(Ball b, Line2D wall) {
// Find unit vector of wall.
double dLx = wall.getX2() - wall.getX1();
double dLy = wall.getY2() - wall.getY1();
double dL = Math.sqrt((dLx * dLx) + (dLy * dLy));
dLx /= dL;
dLy /= dL;

// Find vector from start-point of wall to b's center.
double Tx = b.x() - wall.getX1();
double Ty = b.y() - wall.getY1();

/* Find length of vector from end-point 1 of wall to projection of
b's center on wall using the dot product. */


double dotProd = (dLx * Tx) + (dLy * Ty);
if (dotProd < 0) // Vector extends beyond (X1, Y1) of wall.
dotProd = 0; // Clamp vector.
else if (dotProd > dL) // Vector extends beyond (X2, Y2) wall.
dotProd = dL; // Clamp vector.

// Find vector from projection point on wall to b's center.
double Px = b.x() - (wall.getX1() + (dLx * dotProd));
double Py = b.y() - (wall.getY1() + (dLy * dotProd));

// Length of projection vector.
double shrtDist = Math.sqrt((Px * Px) + (Py * Py));

// Magnitude of b's velocity.
double dV = Math.sqrt((b.dx() * b.dx()) + (b.dy() * b.dy()));

/* If b's change in position is less than it's distance from the wall,
there is no possibility of intersection. */

if (dV < shrtDist - b.radius())
return 1.0;

/* Find intersection point of b, which is coincident with projection
line. */

double bIx = (Px / shrtDist) * b.radius();
double bIy = (Py / shrtDist) * b.radius();

/* Look for intersection between wall and b's velocity vector
originating from it's intersection point. */


/* Find the coefficients needed for finding the intersection point of
two line segments. */

double[] u;
try {
u = intersection(wall.getX1(), wall.getY1(), wall.getX2(), wall.getY2(), bIx, bIy, bIx + b.dx(), bIy + b.dy());
}
catch(Exception e) { // Vectors are parallel.
return 1.0;
}

/* If u[0] and u[1] are not both within the range of 0 to 1, the
vectors don't intersect. */

if ((u[0] < 0) || (u[0] > 1) || (u[1] < 0) || (u[1] > 1))
return 1.0; // Only return if lines *DON'T* intersect.

return 0.0; // For now, just freeze b if it will collide with the wall.
/* Unfortunately, overlapping segments don't seem to get detected. b
keeps going past the wall. */

}

/* Finds the coefficients needed for finding the intersection point of
two line segments. */

private double[] intersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) throws Exception {
double[] u = new double[2];

double denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));

if (denom == 0) // Lines are parallel.
throw new Exception();

double numenA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
double numenB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));

u[0] = numenA / denom;
u[1] = numenB / denom;

return u;
}


Share this post


Link to post
Share on other sites
jyk    2094
From looking over your code, it looks like you're finding the point on the circle closest to the segment, and then sweeping this point against the segment using a segment-segment intersection test. I didn't look at the segment-intersection function, but regardless of whether it works I don't think the overall algorithm is correct. If you draw some example cases, I think you'll see that the point on the circle which first touches the segment is not necessarily the point which is closest to the segment at time = 0.

As always it's possible there's some better solution that I'm not aware of, but here's how I do it:

1. Sweep the circle against the infinite line supporting the segment. Find the first point of contact, if any.
2. If there is a collision and the point of contact lies on the segment, you're done.
3. If there is a collision and the point of contact lies past an endpoint, sweep the circle against that endpoint.

(That's only a brief overview - there's actually a little more to it, but not much.)

I'll include here some test code for circle-segment intersection. It's not tidy or production-quality, but I'm 99% sure it's correct. If nothing else it may give you a working example to compare against.

The code is a little more complicated than is strictly necessary because it detects and returns information about both swept and static intersections; when there is an intersection at t > 0, a contact point and normal is returned, and when there is an intersection at t = 0, information for minimum translation is returned. Once you understand what's going on, you can strip out whatever you don't need.

One last suggestion. I'd recommend breaking up the problem into smaller functions and testing them to make sure they work. Try writing a circle-infinite line intersection test, and a circle-point test. Once you're sure those work, you'll have the tools you need to create the circle-segment test.

Here's the code:


namespace jyk {
namespace Intersection {

// --------------------------------------------------------------------------------------
template <class T> struct Sweep2
{
enum {NONE,
STATIC,
STATIC_INVALID_NORMAL,
SWEPT};

int type;
T t;
Vector2<T> normal;
T distance;
int numPoints;
Vector2<T> points[2];
};
// --------------------------------------------------------------------------------------
template <class T> bool Circle2Seg2(
const Vector2<T> C, // Circle center
T r, // Circle radius
const Vector2<T> V, // Circle velocity
const Vector2<T> O, // Line origin
const Vector2<T> D, // Line direction
const Vector2<T> n, // Line normal
T tMax, // Max time (go elsewhere)
Sweep2<T>& sweep, // Output info
bool cullBack, // Cull if circle starts behind line
T epsilon = Math<T>::EPSILON) // Epsilon for parallel test
{
Vector2<T> d = C - O;
T dn = d.Dot(n);

// Starts behind line
int sweepEndpoint;
if (dn < (T)0.0)
{
if (cullBack)
return false;

// Sweep from back
if (dn < -r)
{
T Vn = V.Dot(n);
if (Vn < epsilon)
return false;

T num = -dn - r;
if (num > tMax * Vn)
return false;

sweep.t = num / Vn;
T s = Vector2<T>::Dot(d + sweep.t * V, D);
if (s < (T)0.0)
sweepEndpoint = 0;
else if (s > D.Dot(D))
sweepEndpoint = 1;
else
{
sweep.type = Sweep2<T>::SWEPT;
sweep.normal = -n;
sweep.numPoints = 1;
sweep.points[0] = C + sweep.t * V - r * sweep.normal;
return true;
}
}
// Initially intersects line
else
{
T s = d.Dot(D);
if (s < (T)0.0)
sweepEndpoint = 0;
else if (s > D.Dot(D))
sweepEndpoint = 1;
else
{
sweep.type = Sweep2<T>::STATIC;
sweep.normal = -n;
sweep.distance = r + dn;
return true;
}
}
}
// Starts on or in front of line
else
{
// Sweep from front
if (dn > r)
{
T Vn = V.Dot(n);
if (Vn > -epsilon)
return false;

T num = -dn + r;
if (num < tMax * Vn)
return false;

sweep.t = num / Vn;
T s = Vector2<T>::Dot(d + sweep.t * V, D);
if (s < (T)0.0)
sweepEndpoint = 0;
else if (s > D.Dot(D))
sweepEndpoint = 1;
else
{
sweep.type = Sweep2<T>::SWEPT;
sweep.normal = n;
sweep.numPoints = 1;
sweep.points[0] = C + sweep.t * V - r * sweep.normal;
return true;
}
}
// Initially intersects line
else
{
T s = d.Dot(D);
if (s < (T)0.0)
sweepEndpoint = 0;
else if (s > D.Dot(D))
sweepEndpoint = 1;
else
{
sweep.type = Sweep2<T>::STATIC;
sweep.normal = n;
sweep.distance = r - dn;
return true;
}
}
}

if (sweepEndpoint == 0)
{
sweep.normal = -n.Perp();
return (Circle2Point2(C, r, V, O, tMax, sweep));
}
if (sweepEndpoint == 1)
{
sweep.normal = n.Perp();
return (Circle2Point2(C, r, V, O + D, tMax, sweep));
}
}
// --------------------------------------------------------------------------------------
template <class T> bool Circle2Point2(
const Vector2<T> C, // Circle center
T r, // Circle radius
const Vector2<T> V, // Circle velocity
const Vector2<T> P, // Point
T tMax, // Max time
Sweep2<T>& sweep, // Output info
T epsilon = Math<T>::EPSILON) // Epsilon for normal validation
{
Vector2<T> d = C - P;
T c = d.Dot(d) - r * r;

// Sweep
if (c > (T)0.0)
{
T b = V.Dot(d);
if (b >= (T)0.0) // Directed away
return false;

T a = V.Dot(V);
T disc = b * b - a * c;
if (disc < (T)0.0) // Missed
return false;

sweep.t = -b - Math<T>::Sqrt(disc);

if (sweep.t < (T)0.0) // Shouldn't happen
return false;

if (sweep.t > tMax * a) // Intersection occurs after tMax
return false;

sweep.type = Sweep2<T>::SWEPT;
sweep.t /= a;
sweep.numPoints = 1;
sweep.points[0] = P;
sweep.normal = Vector2<T>::Normalize(d + sweep.t * V);
}
// Static intersection
else
{
sweep.type = Sweep2<T>::STATIC;
T l = d.Length();

if (l < epsilon) // No unique solution, normal not assigned
sweep.distance = r;
else
{
sweep.normal = d / l;
sweep.distance = r - l;
}
}
return true;
}
// --------------------------------------------------------------------------------------


} // namespace Intersection
} // namespace jyk


Share this post


Link to post
Share on other sites
Zaxx    142
I think I finally figured it out!

Instead of doing an intersection test, I find the unit vectors of the shortest distance between the circle and the extended line and the circle's velocity. I take the dot product between them to find the cos of the angle between them. I use pythagoras to find the distance the circle would actually go. Here's a picture to describe what I'm talking about:

[url]http://img12.echo.cx/img12/2046/circlelineintersection1qy.jpg[/url]

So far I haven't found any bugs when I test this. Here's the java code for my method:
[source="java"]
private double calculateTranslation(Ball b, Line2D wall) {
// For now, treat wall as infinite line.

// Find unit vector of wall.
double dLx = wall.getX2() - wall.getX1();
double dLy = wall.getY2() - wall.getY1();
double dL = Math.sqrt((dLx * dLx) + (dLy * dLy));
dLx /= dL;
dLy /= dL;

// Find vector from start-point of wall to b.
double Tx = b.x() - wall.getX1();
double Ty = b.y() - wall.getY1();

/* Find length of vector from end-point 1 of wall to projection of
b's center on wall using the dot product. */


// Treat wall as infinite.
double dotProd = (dLx * Tx) + (dLy * Ty);

// Point of projection.
double Px = wall.getX1() + (dLx * dotProd);
double Py = wall.getY1() + (dLy * dotProd);

// Vector of projection from b to projection point.
double projX = Px - b.x();
double projY = Py - b.y();

// Length of projection vector.
double shrtDist = Math.sqrt((projX * projX) + (projY * projY));

// Unit projection vector.
projX /= shrtDist;
projY /= shrtDist;

// Velocity & unit vector of b.
double dV = Math.sqrt((b.dx() * b.dx()) + (b.dy() * b.dy()));
double dVx = b.dx() / dV;
double dVy = b.dy() / dV;

/* If b's change in position is less than it's distance from the wall,
there is no possibility of intersection. Direction is ignored. */

if (shrtDist - b.radius() > dV)
return 1.0;

/* Use unit vectors of velocity and projection to find cos of angle
between vectors. */

double cosAngle = (dVx * projX) + (dVy * projY);

/* Is angle between velocity and projection vectors is
90 degrees or more? */

if (cosAngle < 0)
return 1.0;

// Find penetration point on ball.
double bPx = b.x() + (projX * b.radius());
double bPy = b.y() + (projY * b.radius());

// Distance b will actually travel.
double H = (shrtDist - b.radius()) / Math.abs(cosAngle);

if (H > dV)
return 1.0;

return H / dV;
}




So, to adapt this for line segments, I can just test if the projection point on the line is on the segment. If it isn't, I just sweep the endpoint the projection point is closest too.

Anyway, thank you people for your suggestions.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this