Sign in to follow this  
PurpleAmethyst

Circle - Line Collsion 2D

Recommended Posts

This problem is wrecking my head. I have a moving circle, with a movement vector (mvx,mvy), about to hit an abritary line (x1,y1)-(x2,y2). How do I correctly find the exact point of intersection, correctly, even if the movement vector would move the circle over the boudary line? I've tried serval different methods from the net and written loads of paper diagram, I know I'm neraly there. But I still don;t think it's working right. I can't give out the code I'm afraid.

Share this post


Link to post
Share on other sites
treat the problem as a moving point vs line collision.

if the distance peripendicular to the line goes below the radius of the sphere, you have a collision. only if this happens within the areathat lies between the endpoints though. do a point-sphere check for the endpoints/vertices.

moving point vs line is quite easy.

px(t) = p.pos.x + p.vel.x * t;
py(t) = p.pos.y + p.vel.y * t;


dist(t) = (px(t) - line.end.x) * line.normal.x + (px(t) - line.end.y) * line.normal.y = p.radius;

a simple linear equation you can solve for t.

sphere vs point is just a special case of sphere-sphere, and extremely googleable.

Share this post


Link to post
Share on other sites

bool CircleSegmentIntersection
(
Vector2D lp1, //first point of segment
Vector2D lp2, //second point of segment
Vector2D C, //centre of circle
float r, //radius of circle
Vector2D& I, //intersection point
float& t //time of intersection
)
{
lp2 -= lp1;
float length = lp2.Length();
lp2.Normalize();
Vector2D L = C - lp1;
float d = L.Dot( lp2 );
float lsquared = L.Dot( L );
float rsquared = r * r;
if (d < 0 && lsquared > rsquared)
return false;
float dsquared = d*d;
float msquared = lsquared - dsquared;
if (msquared > rsquared)
return false;
float q = (float) sqrt( rsquared – msquared );
if ( lsquared > rsquared )
t = d - q;
else
t = 0.0f;

if( t > length ) return false;
else
{
I = lp1 + lp2 * t;
t /= length;
}
return true;
}

bool PointConfined( Vector2D lp1, Vector2D lp2, Vector2D p )
{
if( p == lp1 || p == lp2 )
return true;

if( sign( ( p - lp1 ).Dot( lp2 - lp1 ) ) != sign( ( p - lp2 ).Dot( lp2 - lp1 ) ) )
return true;

return false;
}

Vector2D RayPlaneIntersection( Vector2D po, Vector2D pn, Vector2D ro, Vector2D rv )
{
float d = -pn.Dot( po );
float numer = pn.Dot( ro ) + d;
float denom = pn.Dot( rv );

return ro + rv * -( numer / denom );
}

bool CirclePlaneSweep
(
float r, //circle radius
Vector2D c0, //previous position of circle
Vector2D c1, //current position of circle
Vector2D lp0, //the plane
Vector2D lp1,
float& t, //time of collision
Vector2D &cpn //collision plane normal
)
{
//Cancel out if our velocity is 0 or plane is facing away from us
if( ( ( c1 - c0 ).x == 0 && ( c1 - c0 ).y == 0 ) || ( c1 - c0 ).Cross( lp1 - lp0 ) > 0 )
return 0;

//Intersection point
Vector2D ci;

//Determine the plane normal
Vector2D pn = Vector2D( lp1.y - lp0.y, lp0.x - lp1.x ).Normalized();

//Determine velocity
Vector2D v = ( c1 - c0 ).Normalized();

//Determine the inverted plane normal sized to the ball's radius
Vector2D ipn = pn.Inverted() * r;

//Add this to the balls origin:
Vector2D ip = c0 + ipn;

//Now find the intersection point with the plane by casting the velocity
//from IP and checking for intersection with the plane

ip = RayPlaneIntersection( lp0, pn, ip, v );

ci = ip + pn * r;

//Determine if the intersection point is actually on the plane
if( !PointConfined( lp0, lp1, ip ) )
{
//No? Then check for collision against endpoints

//Find the closest endpoint by comparing the squared distances
Vector2D ep = ( lp0 - c0 ).LengthSqr() < ( lp1 - c0 ).LengthSqr() ? lp0 : lp1;

//Check for point segment/circle intersection
if( !CircleSegmentIntersection( c0, c1, ep, r, ci, t ) )
return 0;

//CircleSegmentIntersection determined the time of collision for us
//Collision Plane Normal is the vector from the end point to the circle centre at
//time of collsion
cpn = ( ci - ep ).Normalized();

return 1;
}

//Determine if the sphere's new position is actually on the path it followed
if( !PointConfined( c0, c1, ci ) )
{
return 0;
}

//Determine time of collision
t = ( ci - c0 ).Length() / ( c1 - c0 ).Length();
//Collision Plane Normal is that of the plane
cpn = pn;

return 1;
}



That is the code I use. The CirclePlaneSweep() function only detects against one side of the segment (my game world consists of enclosed polygons) but I imagine this can be altered.
I based this code on prior knowledge an the concepts outlined in this article. It is a good read that simplifies the procedure considerably. The CircleSegmentIntersection() function is Oliii’s (thanks for that one).

Note: this code could well be optimized. It seems fast enough for my needs (fast-action game, levels consisting of several hundred segments). I’ve not encountered any bugs and I have been using it for some time but I wouldn’t go so far as to ensure that none exist.

Hope this helps,
Jackson Allan

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