Usually there is more than one way to solve the same mathematical problem, and generally the best way to solve a problem is solve it in the simplest fashion with the tools you have already available.
I looked at this, and it got me thinking how you can do this, and you don't need to mess around with solving equations (it wouldn't help you much in this case either), instead this is what I came up with:
(this may appear blurry in some browsers, I don't know why, but should still be perceptible)
The above is my process of solving this particular problem, represented visually.
Here I used a 2D circle and a 2D line, but the same applies in the exact same way for 3D, so I am just using 2D to make the explanation easier to understand.
We have the circle (your sphere) with point
A as its center, and we have the line intersecting the circle between the points
C and
D, and this line happens to intersect the circle at points
E and
F.
And the key point you actually need to solve this is actually another point, the point
G.
The first thing to note about this point
G is that, for any given line of infinite length (imagine that
C and
D are just 2 points in an infinitely long line), this point is what tells you whether or not the line intersects or touches the circle at all.
Basically, if the distance between
A and
G is equal or shorter than the radius of the circle, then the line is intersecting the circle (either at 1 or 2 points), otherwise it isn't.
The second thing to note about this point
G is that it sits exactly in the middle between
E and
F, meaning that the distances
E to
G and
G to
F are exactly the same, and also at this point the line
CD is perpendicular to
AG (the lines between
C and
D, and
A and
G, respectively, and will use this short form from here on to identify which line I am talking about), hence the green square indicating a 90º angle.
With this you have all the required ingredients to be able to solve this by using fairly straightforward trigonometry: you know points
A,
C and
D (blue points), and from here you just have to solve for points
G,
E and
F (the gray points, in this order).
So, first, you have to find out
G, and here you will notice that due to all the aforementioned properties of this point that you have a right-angle triangle formed by the points
C,
G and
A (or simply
CGA), where you know the values of
C and
A already.
This means that you can find
G by calculating the distance of
AC, and also the angle
ACG, or rather its cosine, which you can get by using the dot product between the normal of vectors of
CA and
CD, to then calculate the vector
CG, as follows:
Code: Select all
CA_Distance = VSize(A - C);
CA_Normal = Normal(A - C);
CD_Normal = Normal(D - C);
ACG_Angle = CA_Normal dot CD_Normal;
CG = CD_Normal * CA_Distance * ACG_Angle;
and from here you can find
G:
And at this point you already know if the line (at infinite length) intersects the circle or not, and at how many points:
Code: Select all
GA_Distance = VSize(A - G);
if (GA_Distance < Radius) {
//intersects at 2 points
} else if (GA_Distance == Radius) {
//intersects at 1 point
} else {
//does not intersect at any point
}
Now that you know
G, and as long as it's inside the circle, you can then now find
E and
F.
Of course, if the intersection is at 1 point only, then
E and
F are one and the same:
G itself.
As you may notice, by finding
G you end up having another right-angle triangle (with the purple line), the triangle
EGA, except that now in order to find
E, you need to find the distance
GE, so you can then use that to go up in the line and find the point you want.
At this point we not only know the points
G and
A of that triangle, but we also actually know the distance between
E and
A already, which matches the radius of the circle, since that's what an intersection point is all about: a point which resides at the edge (radius) of the circle.
Therefore that means that we know 2 sides of the right-angle triangle, and we have just have to find out the 3rd by using the basic Pythagorean theorem:
Code: Select all
EA_Distance = Radius;
GA_Distance = VSize(A - G);
GE_Distance = Sqrt(Square(EA_Distance) - Square(GA_Distance));
and from there you can then find
E very easily:
and since
G sits right between
E and
F, then
EG and
GF have the exact same distance, so you can find
F immediately as well:
Code: Select all
GF_Distance = GE_Distance;
F = G + GF_Distance * CD_Normal;
and you're done.
... except that you aren't quite yet.
Remember, this was all about a line with infinite length, but the length of your line is finite, because you have set those two points
C and
D at specific locations, and that's what your line actually is, so you have to consider additional scenarios, such as:
as well as other variations of the same situation, where the line may actually not intersect at some points, or at any at all, if the line is completely inside the circle, or even completely outside, such as:
For this you can simply check where the
E and
F points are in relation to both
C and
D, and reject
E or/and
F depending on whether or not they are outside the
CD line (and decrement the number of intersected points accordingly), by checking their distances to each point:
Code: Select all
CD_Distance = VSize(D - C);
EC_Distance = VSize(C - E);
ED_Distance = VSize(D - E);
if (EC_Distance > CD_Distance || ED_Distance > CD_Distance) {
//then E is not a valid intersection point (decrement intersected points by one, and reject E)
}
FC_Distance = VSize(C - F);
FD_Distance = VSize(D - F);
if (FC_Distance > CD_Distance || FD_Distance > CD_Distance) {
//then F is not a valid intersection point (decrement intersected points by one, and reject F)
}
and now you're really done.
Having that said, I am not sure if I made any mistakes or missed anything here (it's almost 2:00AM here, going to sleep after this, and my math on this type of thing is quite rusty on top of it), but I think it should all check out and work exactly like you want for you (will likely proof-read tomorrow with a clear head and edit any mistake or typo I may have made).
Furthermore, all this code can be optimized of course, I only broke it down so that each step is as clear as possible, for you and everyone understand what's going on there.
so I guess i'll leave my code wrong as it's working... 