Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
1  
There's a table that goes through a lot of resources for various object intersections here: realtimerendering.com/intersections.html –  Tetrad Dec 9 '11 at 17:03
    
now we just need to work out which is the most efficient. –  Asher Einhorn Dec 9 '11 at 17:25
    
Usually what you do is implement them and do performance testing on your target platform. –  Tetrad Dec 9 '11 at 17:36
    
sure, I was just wondering if there was a known algorithm that was head and shoulders above the rest like I said in the question. Great resource though. –  Asher Einhorn Dec 9 '11 at 17:38
    
If you notice, in that page, it's written Entries are listed from oldest to newest, so often the last entry is the best. :) –  legends2k Mar 28 at 3:45

1 Answer 1

up vote 3 down vote accepted

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)).

share|improve this answer
    
what is the vector CA? I assume some combination of C and A? but how? –  Asher Einhorn Dec 10 '11 at 10:45
    
actually if you can be bothered, an example of how this would actually be written in code would be great for this answer. –  Asher Einhorn Dec 10 '11 at 10:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.