Wednesday, November 9, 2011

Using Vector Mathematics, Line segment against sphere intersection test

This post is about checking for intersection between a line segment and a sphere. Please make sure you read the previous post about finding the closest point on a line from another point, located here.

Luckily, using the formula for finding the closest point on a line, there's not much work left to do to find out if the sphere is touching the line segment. The first step we have is to use that same formula, and the point we use is the center of the sphere.

We'll keep the same points and line from the last example, which we've already seen the math for, and we'll use a sphere (or circle if you're using 2D vectors) with a radius of 1. Judging from the image below, you already know the circle isn't touching the line segment that goes from (0, 0) to (5, 0), but lets prove it with some math.



We already know the point at the center of the sphere (3, 0, -2), and the closest point on the line segment (3, 0, 0) from our last blog post, so all we have to do is find out how far apart those two points are; And, since we only need that distance for a comparison with the sphere's radius, we can just get the squared-length and skip the square-root calculation.

Difference vector = (3, 0, -2) - (3, 0, 0) = (0, 0, -2)
Squared length of difference vector = (0² + 0² + -2²) = 4
Squared radius of sphere = 1² = 1

Because the squared radius is less than the squared length, we can say for certain that the sphere is not intersecting the line segment.

And now we'll use a circle that we know should touch, one with a radius of 2.2 units.

Difference vector = (3, 0, -2) - (3, 0, 0) = (0, 0, -2)
Squared length of difference vector = (0² + 0² + -2²) = 4
Squared radius of sphere = 2.2² = 4.84

And now because the squared radius of the sphere is greater than (or equal to) the squared length of the difference vector, we know it's intersecting or touching the line segment.

There is a caveat though. In our last post we said that points A and C in the example could be ignored because they weren't in the range of the line segment. While this is true, a large enough sphere centered at those points may still intersect with the line segment, so they cannot be ignored. The trick in the case of either of those points is to simply used the ends of the line segments for distance checks. In the case of point A, it will give a percentage along the line of less than 0.0, so we can use the starting point, and point C will give a value greater than 1.0, so we can use the end point of the line segment. So, rather than bailing out of the function if the percentage along the line is not between 0.0 and 1.0, we instead clamp the value in that range, if it's less than 0.0 we'll just pretend it's 0.0, and the same with 1.0.

So here's the function for determining line segement intersection with a sphere:
bool DoesLineSegmentIntersectSphere(const Vector3& LinePointStart,
                                    const Vector3& LinePointEnd,
                                    const Vector3& SphereCenter,
                                    const float SphereRadius)
{
    const Vector3 LineDiffVect = LinePointEnd - LinePointStart;
    const float lineSegSqrLength = LineDiffVect.LengthSqr();

    const Vector3 LineToPointVect = SphereCenter - LinePointStart;
    const float dotProduct = LineDiffVect.dot(LineToPointVect);

    const float percAlongLine = dotProduct / lineSegSqrLength;

    if ( percAlongLine < 0.0f )
    {
       percAlongLine = 0.0f;
    }
    else if ( percAlongLine > 1.0f )
    {
       percAlongLine = 1.0f;
    }

    const Vector3 IntersectionPt = ( LinePointStart 
              + (  percAlongLine  * ( LinePointEnd - LinePointStart ));

    const Vector3 SpherePtToIntersect = IntersectionPt - SphereCenter;
    const float SqrLengSphereToLine = SpherePtToIntersect.LengthSqr();

    return (SqrLengSphereToLine >= SphereRadius);
}



If we try this method with point C (pictured above), and the same sphere radius of 2.2, it looks like it should intersect with the sphere, so lets find out:

First we need to find the closest point on the line segment
line diff ( dot ) line to point = ( 5.7*5 + 0*0 + -1.8*0 ) = 28.5
Percentage along line = 28.5 / 25 = 1.14


1.14 is greater than 1.0 so we'll just clamp it to 1.0


And finding the closest point on the line finally requires this:
P1 + ( percAlongLine * ( P2 - P1 ) )

Which for our example becomes this:
(0, 0, 0) + ( 1.0 * ( 0, 0, 5 ) ), which simplifies to ( 5, 0, 0 )


This confirms that clamping the percentage along the line to 1.0 left us with the end point of the line segment as the closest point on the line segment to the center of the circle. From here we can continue on just like with the example we used earlier for point B.



Difference vector = (5.7, 0, -1.8) - (5, 0, 0) = (0.7, 0, -1.8)
Squared length of difference vector = (0.7² + 0² + -1.8²) = (0.49 + 0 + 3.24) = 3.73
Squared radius of sphere = 2.2² = 4.84

And finally we see here that the radius of the sphere is indeed greater than the distance from the point on the line segment closest to the center of the sphere, which verifies the sphere is intersecting the line segment.

3 comments:

  1. Hello

    Thanks for the post. It was very useful for me.

    I just wanted to say that I think the final return instruction is wrong (line 29).

    should be:
    return (SqrLengSphereToLine <= SphereRadius);

    From the text you write,

    "And finally we see here that the radius of the sphere is indeed greater than the distance from the point on the line segment closest to the center of the sphere, which verifies the sphere is intersecting the line segment.
    "

    We can see you mean to have the condition as I suggest?

    Regards

    Miguel

    ReplyDelete
    Replies
    1. Also, I think it should be:

      return ((sphereRadius * sphereRadius) >= sphereToLineLenSquared);

      because both should be squared so they can be compared in the same units.

      Delete
  2. Really helpful article. I actually had one doubt though, what if there are 2 intersection points. i.e what if the line segment just passes through the sphere?

    ReplyDelete