Sweeping a sphere against a point

Before beginning it is a good idea to grab a computer algebra package, since there is often a bunch of tedious algebraic manipulation involved in writing a sweep test (more so for later tests). A good choice is Maxima, which is free and fairly effective, although it does require a bunch of messing around to get it to do what you want with vectors.

First lets define the prototype for the function we want:

public static bool SweepSpherePoint(BoundingSphere sweepSphere, Vector3 pt, Vector3 direction, out SweepResult sweepResult)

I am using C# for the example code and relying on the XNA math types. The function returns true if there is an intersection along direction as t (the time of impact) ranges from 0 to 1, including an initial intersection at t equals zero. sweepSphere is the sphere we will be sweeping and pt is the point we are sweeping against. direction is the vector we will be sweeping along and sweepResult is information about the intersection, if it occurs.

       public struct SweepResult
       {
              public bool Intersection; // true if there is some intersection(including an initial intersection)
              public float? T;
              public int? FaceIndex;
              public Vector3? Point;
              public Vector3? Normal;
              public float? PenetrationDepth;
       }

SweepResult contains a bunch of information, a lot of it optional, which is only set when relevant to the situation.

Since many sweeps turn into solving a quadratic equation we will be making use of a function to solve quadratics:

public static bool SolveQuadratic(float a, float b, float c, out float t0, out float t1)

This function returns true when there are one or more solutions to the equation . The solutions are returned in t0 and t1, with t0 equal to t1 if there is only one solution. The function correctly handles zero coefficients (e.g. linear or constant equations).

Before we begin with the math for this, there are a number of strategies we can use to simplify the problem at hand and other similar problems:

• Change the subject of the sweep test, for instance sweeping a point against a sphere(a raycast) is the same as sweeping a sphere against the point. This works because we are just changing the frame of reference, only the objects we are considering matter so which one is moving is just a matter of perspective.
• Reduce the dimension of the problem by deflating one object and inflating the other. For example the time of impact between spheres of radius R1 and R2 is the same as the time of impact between a sphere of radius R1+R2 and a point located at the centre of the second sphere.
• Split the test based on the features of the objects. For example when sweeping against a polyhedron we can decompose this into a number of polygons, which in turn can be decomposed into a number of planes, edges and points.

It should be noted that decomposing shapes and deflating/inflating shapes has the added advantage of improved modularity. So we can write a test for a sphere against a point, check that it works as expected, then reuse this test in another situation. For example sphere-point can be used to check the end spheres of a capsule against the points at the end of an edge.

Lets begin, first we have the equation of a line. A point swept along the reverse of our direction, however we ignore the fact that the direction is reversed until we write the code:

Where:

q is the point of interest
p is the origin of the line
V is the direction of the line
t is the time

Then we have the equation of a sphere:

Where:

S is the centre of the sphere
R is the radius of the sphere

If we substitute the equation of the line into the equation for the sphere we can solve for the time of impact:

Something we should note is that when the quadratic is solved we can end up with a number of result:

• Two results, each result represents a time when the line passes through the shell of the sphere. Or alternatively a time at which the shell of the sphere is swept into the point. We just need to sort the results to obtain the time of impact.
• One result represents a grazing impact with the sphere.
• No results represents the cases where the sphere misses the point completely.

If any of the impact times are negative or greater than one(since by convention we only consider impacts confined to the movement along direction), then we throw away that result since it is outside the range for the sweep. If we throw away both results then there is no impact.

Obtaining the point of impact is as simple as plugging the value of t into the line equation. The normal (on the sphere) is just a case of subtracting the contact point from the sphere centre and normalizing. We reverse the normal in this test, because by convention we return a normal pointing away from the second object in the test. Obviously we couldn’t compute a true normal for a point.

If we look at the above formulae, we notice that we can simplify things a bit further and improve performance. We subtract the centre of the sphere from the origin of the ray. This makes S zero and eliminates a few multiplies and dot products.

Finally we should consider a few edge cases, if the direction is zero length, then our sweep test degenerates into a simple point-sphere intersection test. The case where the point and sphere initially intersect is handled by checking if 0 is contained in the range t0 to t1 and returning an appropriate value.

        public static bool SweepSpherePoint2(BoundingSphere sweepSphere, Vector3 pt, Vector3 direction, out SweepResult sweepResult)
        {
            //sweep point against sphere along -direction

            sweepResult = new SweepResult(null);

            if (direction.Length() < DirectionEpsilon)
            {
                //zero direction, is the point initially touching the sphere?
                return sweepResult.Intersection = Intersects(sweepSphere, pt);
            }

            Vector3 P = pt - sweepSphere.Center;

            float PdotV = Vector3.Dot(P, -direction);
            float PdotP = Vector3.Dot(pt, pt);

            float a = Vector3.Dot(direction, direction);
            float b = 2.0f * PdotV;
            float c = PdotP - sweepSphere.Radius * sweepSphere.Radius;

            float t0, t1;

            if (!FloatHelper.SolveQuadratic(a, b, c, out t0, out t1))
            {
                return sweepResult.Intersection = false;
            }

            FloatHelper.Sort(ref t0, ref t1);

            if ((t1 < 0.0f) || (t0 > 1.0f))
            {
                return sweepResult.Intersection = false;
            }

            if (t0 < 0.0f)
            {
                return sweepResult.Intersection = true;
            }

            Vector3 sphereHitCen0 = sweepSphere.Center + direction * t0;

            sweepResult.T = t0;
            sweepResult.Point = pt;
            sweepResult.Normal = Vector3.Normalize(sphereHitCen0 - pt);

            return sweepResult.Intersection = true;
        }

Advertisement