Collision Detection: Circle/Line Segment, Circle/Capsule
I’m working on a game at work where a ball interacts physically with a series of capsules. The system was originally written to support circle vs line collision tests. It was then decided that it would be capsules instead of lines.
This post will show how finding the closest point on a line segment to a point can be easily extended to determine if and where a circle and line segment are intersecting; and how that test can be extended again to identify the point of intersection between a circle and capsule.
First, we need a test for the closest point, P, on a line segment, L, to point X.
We can define L as its endpoints A and B:
L = AB
We can derive the vector, v, as that which points from A to B:
v = AB = B - A
Next, we define a vector, w, pointing from A to our point, X.
w = AX = X - A
Now, we’ve expressed the relationship between X and L in terms of vectors. By defining w and v each pointing from A, we’re working in a 2D Cartesian coordinate frame where A is the origin. Because of this, we can take advantage of some geometrical properties of vectors that will allow us to find the closest point on L to X. Specifically, we’re going to project w onto v:
proj(w,v) = dot(w,v) / dot(v,v)
where dot is the dot product:
dot(w,v) = w.x * v.x + w.y * v.y
When envisioning projection, I find it helpful to think of vectors as having a spatial domain. If you compute the dot product of 2 vectors, it represents how much 1 vector exists in the domain of the other. The dot product of a vector and itself is a value which is a maximum of that vector’s domain. Anything greater than this value exceeds the domain. The dot product of a vector and one perpendicular to it is zero, and defines the minimum of that domain (exclusive). So the domain of a vector, u, in practice, ends up being spanned by any scalar value, q, which satisfies the constraint:
0 < q <= dot(u,u)
Now let’s apply this geometric intuition to our problem of finding the closest point on a line segment. What happens if the vector w points in an opposite direction than v? dot(w,v) will be negative. Therefore w cannot exist in the domain of v. If this is the case, it should be evident that A will be the closest point on L to X. Next, let’s consider the easy-to-imagine scenario of w exceeding the maximum of v’s domain, by defining w as pointing in the same direction as v, but having twice its length. Clearly, B in this case will be the closest point to X.
Example 1. Closest point on segment to user’s mouse:
If the projection of w onto v does satisfy the domain constraint, then P will be on the segment L (and may also be A or B). So what we need is for our projection to parametrize a point on v. Because projection includes division by the squared length of the vector being projected onto, our domain becomes:
0 <= t <= 1
Where t is the projection. By clamping t to this range, and using it to scale the vector v, we find the point on v closest to X. Because we’re working in the space of A, we need to transform back to world coordinates, by adding A:
P = A + v * clamp( proj(w,v), 0, 1 )
Here’s the implementation in my geometry library (Vector2D is not a native data type), with the variables changed to match the description of the problem:
public static function closestPointLineSegment( X:Vector2D, A:Vector2D, B:Vector2D ) : Vector2D { var v:Vector2D = B.minus( A ); var w:Vector2D = X.minus( A ); var wDotv:Number = w.dot( v ); var t:Number = w.dot( v ) / v.dot( v ); t = MathUtil.clamp( 0, 1, t ); return A.plus( v.times( t ) ); }
Circle/Line Collision Test
Now that we’ve found the closest point on a line segment, L, to a point, X, determining intersection of a circle and line segment is as simple as checking whether the distance between X and P is less than the radius of the circle. Of course, X defines the center of the circle.
Example 2. Intersecting a circle and line segment:
Note that in the code below, I’m checking for distance by comparing the squared distance against the squared length of the circle’s radius. This is to avoid an expensive square root call.
public static function testCircleSegment( X:Vector2D, r:Number, A:Vector2D, B:Vector2D ) : Vector2D { var P:Vector2D = closestPointLineSegment( X, A, B ); P.minusEquals( X ); if( P.dot( P ) <= r * r ) return P; return null; }
Circle/Capsule Collision Test
Lastly, intersecting a circle and a capsule is as simple as inflating the circle’s radius by the radius of the capsule. You can see in the below example that we’re really just doing a circle/line test on an inflated circle.
Example 3. Intersecting a circle and capsule:
One extremely nice aspect of working with circles is that, not allowing the shapes to penetrate, circle’s can be touching another convex shape at a maximum of 1 point. Due in part to this convenience, the collision normal will always point from the closest point on the convex shape through the circle’s center.
public static function testCircleCapsule( X:Vector2D, r1:Number, A:Vector2D, B:Vector2D, r2:Number ) : Vector2D { var P:Vector2D = closestPointLineSegment( X, A, B ); P.minusEquals( X ); if( P.dot( P ) <= ( r1 + r2 ) * ( r1 + r2 ) ) return P; return null; }
Very cool
Pointless, we get it you think you’re smart.
Your article was just explained enough so it looks like you’re trying to help, but some parts over explained key parts UNDER explained so that you clearly don’t help anyone at all.
I guess this site is the new FAILBLOG
Wow, somedude. I almost don’t know what to say to that. Almost.
1) “Pointless, we get it you think you’re smart”
Well if you got a point, it’s not pointless, now is it?
2) “Your article was just explained enough”
Who explained my article?
3) “looks like you’re trying to help”
If you find any incorrect information, I’m happy to correct it. As crazy as this sounds, my intent is not to PRETEND to present information. If it didn’t help you, that’s just too bad. It wasn’t me holding the gun to your head while you read.
4) “blah blah blah”
Without being specific, you offer nothing at all. Absolutely nothing except a brief expression of anger to no beneficial ends.
Your comment and you didn’t deserve any response, but it was important for me to defend correct information and give you 1 week to rectify yourself and post an actual comment detailing specific problems. If you can’t, I’ll remove your comment and this one.
After careful consideration, I’ve found out what has crawled up somedude’s rear end and died. He obviously missed the last episode of The Hills and is taking his aggression out here. Also, his girlfriend probably dumped him because she found out that he secretly watches the The Hills too. Epic.
shame on you somedude!
how many times have i told you not to troll and drag our anonymous name into it?
ps- you forgot mother’s day. again.
I totally understand this collision detection crap. I have no idea what somedude’s talking about. Maybe internet land would be more useful to him if he played nice.
“and give you 1 week to rectify yourself and post an actual comment detailing specific problems. If you can’t, I’ll remove your comment and this one.”
Ever heard of alcohol. Get off my back. But could you explain:
Example 2. Intersecting a circle and line segment, the way the line curves around points A and B is interesting
well, that’s a LITTLE better… not sure what you’d like explained though from example 2. the idea is that you find the closest point on the line segment from the circle’s center, which is detailed in the first half or so of the article. if the distance between that closest point and the circle’s center is less than the circle’s radius, the circle and segment are intersecting.
always nice to meet a fan.
@somedude
I have heard of alcohol.
Isn’t this a mistake in the code?
“…as checking whether the distance between X and P is less than the radius of the circle…”
- if( P.dot( P ) <= r * r )?
When i used that I got wildly high results for p.dot(p),
when i changed it to p.distanceRough(mousePositionVector) <= r * r, THEN when the ball was touching the line it would map it to that point?
-
I don’t know which is wrong if any, but I was able to recreate your first example fine, but example two only worked when i changed that
you’re right! there was a typo that’s now fixed in the last 2 code snippets. thanks!
see, that’s better, isn’t it?
Fine but that means i was right when i called it the new failblog
I see what you did there, is P.minus(X) better for some reason than saying P.distanceRough(X) [rough as in no sqrt]
This is what I have:
if(p.distanceRough(mouseVector) <= circleX._radius * circleX._radius)
{
circleX._center = mouseVector;
var angle:Number = Math.atan2(circleX._center.y - p.y, circleX._center.x - p.x);
var cos:Number = Math.cos(angle);
var sin:Number = Math.sin(angle);
var nx:Number = p.x + Math.cos(angle) * (circleX._radius);
var ny:Number = p.y + Math.sin(angle) * (circleX._radius);
circleX._drawPoint.x = p.x + cos * circleX._radius;
circleX._drawPoint.y = p.y + sin * circleX._radius;
// Just a line that extends to get an idea of the angle, only for visual
lineAX.visible = true;
lineAX.A = p;
lineAX.B.x = p.x + cos * 400;
lineAX.B.y = p.y + sin * 400;
lineAX._isDirty = true;
}
else
{
// Hide the line that shows the angle they’re touching at
lineAX.visible = false;
circleX._center = circleX._drawPoint = mouseVector; //Place the circle exactly where the mouse is
}
circleX._isDirty = true;
Ignore the double math.cos/sin calls - i hadn’t replaced them with the cos/sin variables
it depends what your distanceRough method is doing. the idea here though is that you’re checking the squared distance against the squared radius, so it probably doesn’t work properly at all.
“Fine but that means i was right when i called it the new failblog :-P”
Only because you comment here!
Yeah, and I am a fail.
No it works fine, I guess p.minusEquals(X), p.dot(p) is the same as p.distanceRough(X) since it subtracts then multiplies.
-
I guess you don’t wanna give away too much, or else everyone will go and make Hamster-Ball
I guess when one puts a good heaping load of effort and love and sleepless nights into a project and THEN spends extra hours writing up examples, equations, and prose to share - at no cost to you, dear reader - one’s insights gained during the process, it’s primarily to prove how smart one is and prevent others from doing the same? Is that what you’re saying, somedude? Because that is quite a cynical, offensive, and in this case incorrect point of view you have. I doubt you’re receptive to constructive criticism such as this, but I feel like I have to tell you: improve your attitude. Fine, point out errors, just don’t be a dick. Drew is doing a service in writing these articles.
Hey Drew - I’m not as smart as you; can you help me? Before doing so, let me put you and your blog down and hide behind this anonymous name. ZOMG and let me see how many times I can use the word FAIL because I am an internet poser. Hamster balls… LOL!!1
This article was extremely helpful!
Using it for a rolling ball on a teeter todder simulation. Problem is using this code the ball can never leave the todder lol.
Would you know of any way to calculate the collision resolution point without using sqrt? The only ways I can think of make use of sqrt to obtain a normalized vector…
Thanks!
@Harito, well ideally the point of intersection here and the point used in collision response are one in the same. in the case of the collision normal, yes, you’ll have to calculate a square root to normalize; unless you want to do something like solve for the angle between the circle and the point off of the x-axis and transform the vector (1,0) by the associated rotation matrix. i don’t think that would be worth it, though.
@drew
Thought as much :).
Thanks for taking the time to reply.
Wow! Great article! This is the first tutorial I’ve found on circle-line collision detection that I could understand without much effort. Thanks a lot!
And I have no idea what somedude is talking about, you explained everything just the right amount. I especially liked the part where you explained how to find the closest point on a line to another point. That was very clear and well written.
Glad you found it helpful, that’s very nice to hear!
Thank you for this article. I literally spent all of last night trying to figure out circle-line collision detection but without the interwebs of course. Now I log on today and the first result is this amazing tutorial. I’m still going to have to do a lot of work translating this code into the syntax I’m using but thanks a lot drew. To be honest I don’t quite get why the code for the closest point on the line works, but I comprehend enough to get by
fricking awesome tutorial/explanation. Admittedly its still a little over my head, but is a great starting point. Some things about circle line detection were doing my head in.