4
\$\begingroup\$

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?

\$\endgroup\$
5
  • 1
    \$\begingroup\$ There's a table that goes through a lot of resources for various object intersections here: realtimerendering.com/intersections.html \$\endgroup\$
    – Tetrad
    Dec 9, 2011 at 17:03
  • \$\begingroup\$ now we just need to work out which is the most efficient. \$\endgroup\$ Dec 9, 2011 at 17:25
  • \$\begingroup\$ Usually what you do is implement them and do performance testing on your target platform. \$\endgroup\$
    – Tetrad
    Dec 9, 2011 at 17:36
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 9, 2011 at 17:38
  • \$\begingroup\$ If you notice, in that page, it's written Entries are listed from oldest to newest, so often the last entry is the best. :) \$\endgroup\$
    – legends2k
    Mar 28, 2014 at 3:45

1 Answer 1

5
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ what is the vector CA? I assume some combination of C and A? but how? \$\endgroup\$ Dec 10, 2011 at 10:45
  • \$\begingroup\$ actually if you can be bothered, an example of how this would actually be written in code would be great for this answer. \$\endgroup\$ Dec 10, 2011 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .