most efficient Bounding Sphere vs Ray collision algorithms

Question

Is there a known 'most efficient' algorithm for Sphere vs Ray collision detection?

I recently stumbled accross Arvo's AABB vs Sphere collision algorithm, and I am wondering if there is a similarly noteworthy algorithm for this.

One must have condition for this algorithms is that I need to have the option of querying the result for the distance from the ray's origin to the point of collision. Although if there is another, faster algorithm which does not return distance, then in addition to posting one that does, also posting that algorithm would be very helpful indeed.

Please also state what the function's return argument is, and how you use it to return distance or a 'no-collision' case. For example, does it have an out parameter for the distance as well as a bool return value? or does it simply return a float with the distance, vs a value of -1 for no collision?

Answer 1

Given a sphere with centre at point C with radius r and a ray starting at point A with direction vector d.

First check if the vector CA is shorter than r, if so A lies within the sphere and there is definitely a collision.

Second compute the dot product of CA and d, if it is negative A is "behind" the sphere and there may be a collision, otherwise there is no collision unless A is within the sphere.

The key to this problem is to find the minimum length from the sphere centre to the line. Project the vector CA onto d, subtract the result from CA, this gives you v, the shortest vector from C to the line going through A with direction d. If v is shorter than r, there is a collision.

You can find two points where the line intersect the sphere using Pythagoras, C + v +- d * sqrt(r^2 - |v|^2).

Edit:
And for the record, this is as good as it gets, everything is done using simple vector maths, it requires a limited number of basic arithmetic functions, and there are only a few branches.

Edit:
CA is the vector from C to A, computed as A - C.

In quick pseudocode, you'd do something like:

//input
vector A
vector d
vector C
float r
//end of input

vector collisionPoint
vector v
vector CA = A-C
float rSquared = r*r
float vSquared
if(dotProduct(CA,CA) <= rSquared){
    collisionPoint = A
}
else if(dotProduct(CA,d) <= 0){
    v = CA - projection(CA,d)
    vSquared = dotProduct(v,v)
    if(vSquared <= rSquared){
        collisionPoint = C + v - multiply(normalize(d),squareRoot(rSquared-vSquared))
    }
    else{
        collisionPoint = none
    }
}
else{
    collisionPoint = none
}

You could code up all the functions yourself, but it may be handy to use a vector library, note that while A and C are points I have declared them as vectors in the code as it is common not to differentiate between point and vectors in code. This code finds the point closest to A where the ray and the sphere collide. If you are interested in the furthest point that will be C + v + multiply(normalize(d),squareRoot(rSquared-vSquared)).