Optimizing points distance to sphere test.

Question

I would like to test if a point is within a particular distance of a sphere.

So you have these variables...

Point3F spherePnt;
F32 sphereRadius;
Point3F testPnt;

I could do...

F32 dist = ( spherePnt - testPnt ).len() - sphereRadius;

If dist is positive it is outside the radius, if dist is negative it is inside the radius.

Or as an optimization to avoid the square-root inside the len() function you might try this...

F32 dist = ( spherePnt - testPnt ).lenSquared() - ( sphereRadius * sphereRadius );

Ok this looks like it makes since at first glance, but apparently its actually giving me incorrect results.

For example, given variables are setup like this...

SpherePnt( 0, 0, 0 )
SphereRadius( 1 )
testPnt( 1, 1, 1 )

Take the result of...

F32 dist = ( spherePnt - testPnt ).len() - sphereRadius;
F32 dist2 = mSqrt( ( spherePnt - testPnt ).lenSquared() - ( sphereRadius * sphereRadius ) );

dist = 0.7320508075688772935274463415059;
dist2 = 0.4142135623730950488016887242097;

It is pretty obvious that this is in fact, wrong, mathematically. It reduces to expecting the square root of 2 to be the same as the square root of 3... so the question is, I guess...

Given that I DO want to perform this test, "is point p within range r of a sphere", is there a way to do this while avoiding the square root?

Answer 1

You don't need the sqrt computation in the "squared distances" approach! The distance between the two points (sphere center and testpoint) is less than the sphere radius iff the squared distance is less than the squared radius -- for the sole purpose of testing "within the sphere or out of it?", the fact that the square root of the difference is NOT the difference of the square roots, is totally irrelevant.