algorithmintersectionraytracing

Testing whether a line segment intersects a sphere

I am trying to determine whether a line segment (i.e. between two points) intersects a sphere. I am not interested in the position of the intersection, just whether or not the segment intersects the sphere surface. Does anyone have any suggestions as to what the most efficient algorithm for this would be? (I'm wondering if there are any algorithms that are simpler than the usual ray-sphere intersection algorithms, since I'm not interested in the intersection position)

Solution

  • I don't know what the standard way of doing it is, but if you only want to know IF it intersects, here is what I would do.

    General rule ... avoid doing sqrt() or other costly operations. When possible, deal with the square of the radius.

    1. Determine if the starting point is inside the radius of the sphere. If you know that this is never the case, then skip this step. If you are inside, your ray will intersect the sphere.

    From here on, your starting point is outside the sphere.

    1. Now, imagine the small box that will fit sphere. If you are outside that box, check the x-direction, y-direction and z-direction of the ray to see if it will intersect the side of the box that your ray starts at. This should be a simple sign check, or comparison against zero. If you are outside the and moving away from it, you will never intersect it.

    From here on, you are in the more complicated phase. Your starting point is between the imaginary box and the sphere. You can get a simplified expression using calculus and geometry.

    The gist of what you want to do is determine if the shortest distance between your ray and the sphere is less than radius of the sphere.

    Let your ray be represented by (x0 + it, y0 + jt, z0 + kt), and the centre of your sphere be at (xS, yS, zS). So, we want to find t such that it would give the shortest of (xS - x0 - it, yS - y0 - jt, zS - z0 - kt).

    Let x = xS - x0, y = yX - y0, z = zS - z0, D = magnitude of the vector squared

    D = x^2 -2*xit + (i*t)^2 + y^2 - 2*yjt + (j*t)^2 + z^2 - 2*zkt + (k*t)^2

    D = (i^2 + j^2 + k^2)t^2 - (xi + yj + zk)*2*t + (x^2 + y^2 + z^2)

    dD/dt = 0 = 2*t*(i^2 + j^2 + k^2) - 2*(xi + yj + z*k)

    t = (xi + yj + z*k) / (i^2 + j^2 + k^2)

    Plug t back into the equation for D = .... If the result is less than or equal the square of the sphere's radius, you have an intersection. If it is greater, then there is no intersection.