I'm trying to calculate if a vector, at any point, intersects with a circle. I've looked over the many forum posts on the matter and have attempted to utilize the information there. What I've gotten however is something that works very irraticaly. Here is my code - Ok, some explaination - I am using DirectX 9 (which isn't important), but the call D3DXVec3Dot retrieves the dot product of two vectors and the call D3DXVec3Length retrieves the length of the vector. Do I perhaps need to normalize either or both of the two vectors I use to calculate the dot product? I'm also simply assuming that the way vecClosestPoint is being caluclated is correct. I don't understand the maths behind that, if someone could explain how times-ing the direction vector with the dot product and adding that onto the start position gets you the closest point on the vector to the circle, I would be greatly appreciative. Any help would be great. Cheers in advance.

Here is your code with a couple of additional notes that may address the problem:

vecToPrey = EndObject->vecPosition - StartObject->vecPosition;vecToCircle = CircleObject->vecPosition - StartObject->vecPosition;fDotResult = D3DXVec3Dot(&vecToCircle, &vecToPrey);     // Need to add thisfDotResult /= D3DXVec3Dot(&vecToPrey, &vecToPrey);    // At this point you're testing against an infinite line, which may not be    // what you want. If you want to treat the vector as a ray, add this:if (fDotResult < 0.0f) fDotResult = 0.0f;    // If you want to treat the vector as a segment, also add this:if (fDotResult > 1.0f) fDotResult = 1.0f;vecClosestPoint = StartObject->vecPosition + (vecToPrey * fDotResult);fDistanceTo = D3DXVec3Length(&(vecClosestPoint - CircleObject->vecPosition));

Once you get this working, you could also switch to a squared-distance test to avoid the square root (although it probably won't matter much either way).

I think that should cover it, but ask if you have any further problems.

Thanks jyk for your answers, it all seems to be working now. I guess the example that I based my code on equivalent of vecToPrey must of been a unit vector and hence they didn't include the added call (as dividing by 1 would be do nothing).

I am curious as to the maths involved in this example. Could you, or anyone else, point me in the direction of some resources that explain why it works the way it does? In particular caluclating the closest point on the line to the centre of the circle. It seems just like magic to me atm :)

Cheers.

Quote:Original post by GambitSnax
I am curious as to the maths involved in this example. Could you, or anyone else, point me in the direction of some resources that explain why it works the way it does? In particular caluclating the closest point on the line to the centre of the circle. It seems just like magic to me atm :)

There are several ways one can approach this problem.

Derivation 1

One way involves the property of the dot product (which I'll give here without proof) that dot(a,b) is the length of the perpendicular projection of a onto b in units of |b|, and vice versa.

We're interested in finding the closest point on the line O+tD to a point; to do this we must find t. Let m be the difference vector P-O, where P is the query point in question. If |D| = 1, then m.D gives us t in units of 1, and we're good to go.

Now let's say that |D| is unknown; in this case we of course still know that D/|D| is unit length, so we can plug that into the unit-length D equation:

closest = O+dot(m,D/|D|)*(D/|D|)closest = O+(dot(m,D)/|D|)*(D/|D|)closest = O+(dot(m,D)*D)/|D|^2closest = O+(dot(m,D)/|D|^2)*DThus:t = (m.D)/|D|^2

That was a lousy explanation, but moving on.

Derivation 2

Another fact we know about the closest point C on O+tD to P is that P-C (or C-P if you prefer) is perpendicular to D. This means among other things that dot(P-C,D) must be zero, so let's see if we can use that to our advantage:

(P-(O+tD)).D = 0(P-O-tD).D) = 0P.D-O.D-(D.D)t = 0(P-O).D-(D.D)t = 0m.D-(D.D)t = 0-(D.D)t = -m.Dt = (-m.D)/-(D.D)t = (m.D)/(D.D)t = dot(m,D)/|D|^2

And viola.

Derivation 3

Finally a bit 'o calculus. Let's look at the functions for the distance and squared distance from P to the point O+tD:

d(t) = |P-(O+tD)|d2(t) = |P-(O+tD)|^2d2(t) = (P-(O+tD)).(P-(O+tD))

I think we can agree that at the value of t corresponding to the closest point on O+tD to P, the value of d2(t) must be at its global minimum. The graph of this function (if the input is non-degenerate) is a simple parabola, so we can apply some calculus to find this minimum:

d2(t) = (P-(O+tD)).(P-(O+tD))d2(t) = (P-O-tD).(P-O-tD)d2(t) = (m-tD).(m-tD)d2(t) = (D.D)t^2-2(m.D)t+(m.m)d2'(t) = 2(D.D)t-2(m.D)2(D.D)t-2(m.D) = 02(D.D)t = 2(m.D)(D.D)t = (m.D)t = (m.D)/(D.D)t = (m.D)/|D|^2

This post has become somewhat long-winded, but I think this particular problem, in its relative simplicity, is a good example of how many problems in math and geometry can be approached from different directions, and yet these directions must all necessarily lead to the same conclusion (in this case, the 't = (m.D)/|D|^2' with which each derivation ends).

The methods shown here are applicable to a wide variety of problems; in particular, many 'closest point' problems in 2D and 3D can be expressed and solved similarly to the above.

Thanks for the detailed information. They all give good reasons why it works.

Could I ask if it was easy to adjust my algorithm so that I could return the position at which the first intersection happens between the ray and the sphere?

Quote:Original post by GambitSnax
Could I ask if it was easy to adjust my algorithm so that I could return the position at which the first intersection happens between the ray and the sphere?

Yup, it's easy. It's actually easier to find this algorithm online than the boolean test; just google 'raytrace sphere', 'ray sphere intersection', or similar terms. Note that the circle and sphere versions are the same algorithm (just in different dimensions), so you can easily apply the sphere version to the circle problem.

If you have any trouble finding an explanation or example, just post back here; the algorithm is only a few lines of code (it involves solving a simple quadratic) and is easy to post.

Ahhh I think I understand how to do it now.
Let me know if i'm right.

I already know the closest point to the center of the circle and thus the vector from that to the center of the circle. Using Pythag with the length of this vector and the length of the radius, I can get the length from the closest point to the edge of the circle. Then I (using a normalized vector that the ray is on), translate back the required distance from the closest point and that should be my point of intersection.

Am I right?

Also I'm thinking I could get rid of the boolean test all together and just test to see if the length of the calculated side is greater than or equal to zero, and if so, the line has passed through (or clipped) the circle.

Is this correct?