Sign in to follow this  

Circle-Line Collision

This topic is 2478 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

I'm trying to follow the tutorial on [url="http://www.t3hprogrammer.com/research/line-circle-collision/tutorial#TOC-Moving-Circle-and-Static-Line-Segme"]this[/url] website about circle-line collision.

The following is a copy from that tutorial:

[img]http://www.t3hprogrammer.com/_/rsrc/1278515062956/research/line-circle-collision/tutorial/letters.png[/img]
[color="#283769"][font="Arial, sans-serif"][size="2"]Find several other points:[/size][/font][/color][list][*]The point of intersection between line and the movement vector of the circle. (a)[*]The closest point on the line to the endpoint of the movement vector of the circle. (B)[*]The closest point on the movement vector to [color="#006000"][font="monospace"](x1, y1)[/font][/color]. ©[*]The closest point on the movement vector to the other endpoint. (d)[/list][size="2"][color=#283769][font=Arial, sans-serif]Using the points, it is then possible to eliminate many positions that would not result in a collision. A collision is possible if:[/font][/color][/size]
[list][*]a is less than [color="#006000"][font="monospace"]r[/font][/color] away from each endpoint on the movement vector and on the line.[*]b is less than r away from the endpoint of the movement vector and on the line segment.[*]c is less than r away from [color="#006000"][font="monospace"](x1, y1)[/font][/color] and on the movement vector.[*]d is less than r away from [color="#006000"][font="monospace"](x2, y2)[/font][/color] and on the movement vector.[/list]
[size="2"][color=#283769][font=Arial, sans-serif][color="#000000"][font="arial, verdana, tahoma, sans-serif"]Now, my problem is that my tests mostly fail on these last four points even when it is obvious that there is a collision. Take the above image for an example.[/font][/color]
[color="#000000"][font="arial, verdana, tahoma, sans-serif"] [/font][/color]
[color="#000000"][font="arial, verdana, tahoma, sans-serif"]Is this tutorial wrong/incomplete or am I missing something?
[/font][/color][/font][/color][/size][size="2"]
Thanks in advance![/size]

Share this post


Link to post
Share on other sites
Based on a single read-through, I can't really confirm whether the approach described in the tutorial is valid. (Maybe it is - it's just not immediately clear to me one way or the other.)

Here however is a method that's guaranteed to produce the correct results (provided all potential numerical issues are handled correctly, of course).

To determine whether a collision will occur, and if so, when it will occur and what the contact point and normal will be, intersect a line segment representing the motion of the circle with a capsule for which the line segment you're testing against is the medial segment, and for which the radius is the circle radius. This approach takes a little work to implement, but it'll handle all cases correctly.

(Again, maybe the method you're using now works, although on first read at least it seems a little questionable. Maybe someone else can comment on that further.)

Share this post


Link to post
Share on other sites
After reading the tutorial I second jyk's suggestion, because for the most part it reduces to a rather easy computation: distance between two possibly intersecting segments. If the distance between the trajectory of the circle center and the wall segment is smaller than the circle radius, they collide at some point of the considered movement.

Finding the time/place of impact is little extra work: the approach based on similar triangles found in the tutorial is simple and correct, although described with some confusion between segments and whole lines.

Share this post


Link to post
Share on other sites
This capsule method works great indeed. Still, at some point when the circle moves very slow the circle goes right through the wall. External forces are applied before the collision detection and do not alter the position of the circle, so that should not be the problem. Any ideas?

Share this post


Link to post
Share on other sites
[quote name='Twan Baten' timestamp='1298666351' post='4779095']
This capsule method works great indeed. Still, at some point when the circle moves very slow the circle goes right through the wall. External forces are applied before the collision detection and do not alter the position of the circle, so that should not be the problem. Any ideas?
[/quote]
Can't say for sure without seeing the code, but numerical problems can arise if the magnitude of the displacement is very low. (This problem is unavoidable even from a purely mathematical standpoint, since it makes little sense to compute the time of intersection for a non-moving object, unless that time is zero of course.)

I wouldn't expect the test to fail though unless the magnitude of the displacement vector was very low or (potentially) the circle was moving parallel or nearly parallel to the capsule axis. If you're finding that the test is failing in some cases, I'd recommend doing some debugging to try and determine where exactly the failure is occurring. (It may be due to an error in your implementation, or simply due to not handling the various potential numerical issues correctly.)

Share this post


Link to post
Share on other sites
Hi there,

Check out my old article about circle vs capsule collision detection - very similar to this problem:

[url="http://www.pfirth.co.uk/collision.html#CircleCapsule"]http://www.pfirth.co.uk/collision.html#CircleCapsule[/url]

Cheers, Paul.

Share this post


Link to post
Share on other sites

This topic is 2478 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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