|
Line Segment/Circle collision detection? |
James Stanley
Member #7,275
May 2006
|
Can anyone link me to a tutorial about detecting collisions (and calculating responses would also be helpful) between line segments and circles? |
Thomas Harte
Member #33
April 2000
|
I think there was recently a thread here somewhere, but I can't find it now. Personally, I usually work it out every time from first principles. The line segment is u + tv, where u and v are vectors and t is a scalar with a value between 0 and 1. The circle is the collection of all points p such that | p - c | = r, where c is a vector, || is the modulus/length operator and r is a scalar. So then just solve for | (u + tv) - c | = r. It turns into a quadratic, throw the quadratic formula at it and you can see how you end up with either no solutions for r (the line misses the circle), one solution (the line is a tangent) or two solutions (the line crosses the circle). Check those solutions to see if t is between 0 and 1 inclusive. [My site] [Tetrominoes] |
GullRaDriel
Member #3,861
September 2003
|
"Code is like shit - it only smells if it is not yours" |
SiegeLord
Member #7,827
October 2006
|
I made a post awhile ago detailing how to calculate the distance between a line segment and a point, which can be used for collision detection part... it does give you the point of contact sort of, so you could use it for the response as well. Here it is. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
James Stanley
Member #7,275
May 2006
|
Thomas, while I believe what you say, I have no idea what that means. EDIT: |
SiegeLord
Member #7,827
October 2006
|
I just tested the code, and everything seems to work as it is supposed to. There's probably some issue in your code... perhaps stemming from my terrible documentation of the algorithm. And yes it is does work with negatives. Here's a better commented version of it, in case it helps:
"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
James Stanley
Member #7,275
May 2006
|
SiegeLord said:
float dot = A * C + B * D;//some interesting math coming from the geometry of the algorithm float len_sq = C * C + D * D; float param = dot / len_sq;
Would that be Pythagoras' theorem? Also, the dist() function. As far as I can tell, that needs Pythagoras' theorem to calculate the distance. I was using: That seem about right to you? |
Thomas Harte
Member #33
April 2000
|
My thoughts, turned into code:
You know, completely untested, just worked out on a piece of paper, etc. [My site] [Tetrominoes] |
James Stanley
Member #7,275
May 2006
|
I'm going to try implementing that now. EDIT: EDIT2: |
Thomas Harte
Member #33
April 2000
|
Quote: That has the same problem as the other code - it only detects collisions with the line start point. No it doesn't. What gives you that impression? Have you tested and discovered a mistake in my coding, or are you saying that just from reading it? EDIT: and SiegeLord's shouldn't either. Are you sure you aren't feeding incorrect numbers into your program somewhere? [My site] [Tetrominoes] |
SiegeLord
Member #7,827
October 2006
|
Quote: Can you explain why this works?
Here's a rough outline of how it works. First, we form the two vectors, one that is the line segment, and the other one that goes from one endpoint of the segment to the center of the circle. Note that they share the same starting vertex. Now, we take the dot product of the two vectors, which roughly represents the projection of one vector onto the other. Now, our goal is to get a normalized projection, i.e. such that if the point is directly above or below the segment vector we will get a parameter to be between 0 and 1. We accomplish this in two steps. First, we divide once by the length of . This gives us the magnitude of the projected point vector... basically as if it was casting a shadow onto the segment vector. Now, we divide that number again by the length of the to normalize the parameter. Why? Because clearly if the shadow of the vector is less than the length of the segment vector, we should get a number less than one. It does not take too much imagination to see that this relationship is linear. In any event, here's the net formula: Which nicely corresponds to the code. Note that we avoid taking the square root because we divide twice by the length, hence the variable being the length-squared. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
James Stanley
Member #7,275
May 2006
|
Quote: No it doesn't. What gives you that impression?
Read the line after the one you quoted . Quote: Are you sure you aren't feeding incorrect numbers into your program somewhere? I'm certain that I am. Problem is, I've checked them all and they all seem right. SiegeLord, that kinda makes sense. It seems to be a similar algorithm to Thomas Harte's, except you have the param thing and he has the quadratic formula. EDIT: EDIT2: |
|