Optimized Sphere-Line Check Only?

Question

Is there an optimized equation for calculating if a sphere and line will intersect, i'm aware of the closest point solution but i was wondering if there was another. There's also the quadratic equation but it requires a lot of calculations, and i'm not sure of all the early outs that are possible with it. I know of two by (i think)...

Vec3 d = lineEnd - lineStart; // the ray
Vec3 f = lineStart - sphereCenter; // center -> lineStart


float c = dot(f, f) - radius * radius;

if(c <= 0)
{
    // first out
    // sphere is touching the vertex
    // hit !
}

float b = dot(f, d);

if(b >= 0)
{
    // second out
    // line ray and center -> start, are going same direction
    // if the start point didn't intersect above
    // then there's no way for the segment or other point to
    // miss
}

float a = dot(d, d);

// ... any other optimizations

if(b*b - a*c < 0)
{
    // miss
}

Note, `b` should actually be `dot(f, d) * 2`. (Or, if you really want to leave the 2 factor out, the `2*b*b` in the discriminant check should be `4*b*b`.) — Wyzard, Aug 29 '14 at 07:48
@Wyzard good catch, i could remove both those 4s now though could i not ? — user3901459, Aug 29 '14 at 08:33

score 1 · Accepted Answer · answered Aug 29 '14 at 08:10

I don't think you can really get much better. You might be able to eliminate some simple cases . If say the start and end point of the line have x coordinates less that the sphere center minus the radius and ones above above the sphere center and ones below then it will not be possible. You could consider the cube surrounding the sphere. If a line does not intersect the box then it can't intersect the sphere. That might be a bit easier to calculate.

The quadratic algorithm is not that bad. Dot product is three multiplications and three additions. I think the whole thing can be done in twelve multiplications (excluding multiplying by 2 and 4). There is a chance you could eliminate a few of these. Note you don't need to calculate the square root which is the really expensive bit, just check the sign of the discriminant as in your code.

score 0 · Answer 2 · edited May 23 '17 at 11:57

0

look here ray and ellipsoid intersection accuracy improvement

just set r[3] as (1/R*R,1/R*R,1/R*R)
or update equations to singular radius (can multiply whole equation by 1/(R*R) later)
in current state it need 3 x triple dot's, 1 x sqrt, 2 x div and some minor operations like +,-,*

edited May 23 '17 at 11:57

Community

1
1

answered Aug 29 '14 at 07:50

Spektre

49,595
11
110
380

I don't need the intersection though, i'm testing only to see if one does exist. – user3901459 Aug 29 '14 at 08:31

Optimized Sphere-Line Check Only?

2 Answers2