Line intersection with circle

[Valaraukar]

Hey guys,

So my Maths has obviously gotten a little rusty and I seem to be struggling with what should be quite simple....

The scenario:
I have lines being drawn in 3D space that are calculated using an algorithm. These lines are actually made up of multiple line segments to create what looks like a single smooth curved line. I don't know where the lines will be drawn, in what direction etc. but I can grab the points on the line once the line object has been created. These lines are inside a cylinder and at some point may/may not intersect/collide with part of the cylinder.

The Task:
I have to mark exactly (or at least as close to exact as possible) the point at which a line intersects with part of the cylinder.

NB: I would appreciate if you ignored the z. This is quite easy to deal with on its own. i.e. collisions with the ends of the cylinder.

It is easy enough to single out the individual line segments which actually intersect with the radius of the cylinder. So this leaves me with (in effect) a 2D style calculation; determining exactly where a line intersects a circle.

A quick look on google and I find a good solution but, (and this is the problem) I don't fully understand the equations used because the website if very brief.
I have created a code version of the formula and it works perfectly well but only for some/most of my line objects. I think I know the reason for this but I don't fully understand the calculations used and hence can't solve this for myself.

The formula that I used can be found here

If you follow the link you will see that the formula uses:

x = Ddy +/- ...blah...
y = -Ddx +/- ...blah...

I basically need to know when I should be adding and when I should be subtracting. Currently I am only ever adding which is obviously why my code isn't quite working. I tried determining the direction of the line and adding/subtracting based on that but to no avail.

My Code:

// Definitions
   float x, y;
   float dx = p2.fX - p1.fX;
   float dy = p2.fY - p1.fY;
   float dr = sqrt( ( dx * dx ) + ( dy * dy ) );
   float D = ( ( p1.fX * p2.fY ) + ( p2.fX * p1.fY ) );

   float rtDescrim = sqrt( ( ( r * r ) * ( dr * dr ) ) - ( D * D ) );

   x = ( D * dy ) + ( ( sgn(dy) * dx ) * rtDescrim );
   x /= ( dr * dr );

   y = ( -D * dx ) + ( fabs( dy ) * rtDescrim );
   y /= ( dr * dr );

   TEveVector result = TEveVector( x, y, 0.001 );
   return result;

Any help would be greatly appreciated :)

[jonsca]

The +/- accounts for there being 2 points of incidence if the value of the discriminant is greater than 0. If the discriminant is 0, there is one point of incidence (the first part +/- 0 gives the same point). If the discriminant is negative, there are imaginary roots and so no intersection on the real plane. It's the cases outlined in the diagram at the top of the page.

So, if the discriminant is greater than zero, you need to have one calculation for [x = Ddy + (signum) * the discriminant, y = -Ddx + the discriminant as one point] and [x = Ddy -(signum) * the discriminant,y = -Ddx - the discriminant] as the second point.

Hope that makes it more clear, if not post back. Just think of it as the solution of a set of quadratic equations and maybe it will click for you.

[Valaraukar]

Well that's cleared that part up for me :)
However, I am a little confused about the results from my testing. I tested the value of the discriminant and found that it was usually a really high value but never 0 even though I know there will only be one point of incidence.

float descrim = ( ( ( r * r ) * ( dr * dr ) ) - ( D * D ) );

This means that I will always have to account for both + and -, but how do I know which one I need to use?
For example I noticed that if I only did

- x = Ddy + (signum) * the discriminant, y = -Ddx + the discriminant

then the lines intersecting in the top half of the cylinder were accurate but the lines at in the bottom half were drawn on the opposite side of the cylinder (i.e. alongside the accurate points). The opposite was true when using - .

If I know when I should use - and when I use + then I think it should be problem solved :)

[Valaraukar]

I shouldn't be double posting but seeing as I basically answered my own question in the last post I feel I should just make the thread complete. All I had to do was check whether dy is < 0 and if so, subtract instead of add.

Thanks again for your help jonsca, it's much appreciated :)

[jonsca]

I would take a "toy" problem and use the equations on pencil and paper. Take a circle with radius 3 and find the points where it intersects with the lines x = -3, x = 0, and x = +3 (you can construct lines with any two of the points along those, for example (-3,2) and (-3,-2) will make up x = -3(to keep calculations simple). You know that x = -3 will meet up with the circle at y = 0, so that should give you a discriminant of 0, you know that x=0 will meet up with the circle at (0,3) and (0,-3). Knowing that, you can come up with which should be + and which should be - (since both the x values are zero, you could choose a line with slope 1 passing through the circle to verify both x and y at the same time. It's possible the author of that page made an error and one should be +/- and the other should be -/+ (but I think using the signum he's trying to fix that). I wish I knew the absolute answer, but it should just take you a few minutes with pencil and paper.

[jonsca]

No problem! (our posts crossed). Good luck with your project.