Circle - Line Collsion 2D
Author
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.
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.
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.
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
