Efficient way of finding distance between two 3D points

Question

hi,

I am writing a code in C++ and want to compute distance between two points. Question 1:

I have two points P(x1, y1, z1) and Q(x2, y2, z2) , where x, y and z are floats/doubles.

I want to find the distance between these two points. One way to do it is :

square_root(x_diff*x_diff + y_diff*y_diff + z_diff*z_diff)

But this is probably not the most efficient way . (e.g. a better formula or a ready made utility in math.h etc )

Question 2:

Is there a better way if I just want to determine if P and Q are in fact the same points?

My inputs are x, y and z coordinates of both the points.

Thank you

Answer 1

Do you need the actual distance? You could use the distance squared to determine if they are the same, and for many other purposes. (saves on the sqrt operation)

Answer 2

No there is no better way.

The implementation of square_root might be optimised.

If you are comparing two distances and want to know the longer, but do not care about what the actual distance is, then you can simply ingore the square-rooting step completely and manipulate your distances still squared. This would be applicable to comparing two pairs of points to determine if they are the same distance apart, for example.

Answer 3

Q2 answer: x1 = x2 and y1 = y2 and z1 = z2 if the points are the same.

Taking in consideration that you store points as float/double you might need to do the comparison with some epsilon.

Answer 4

No, there is no more efficient way to calc the dist. Any treatment with special cases p.x==q.x etc. will be slower on average.

Yes, the fastest way to see if p and q are the same points is just comparing x, y, z. Since they are float, you should not check == but allow for some finite, small difference which you define.

Answer 5

Is there a better way if I just want to determine if P and Q are in fact the same points?

Then just compare the coordinates directly!

bool areEqual(const Point& p1, const Point& p2) {
     return fabs(p1.x - p2.x) < EPSILON &&
            fabs(p1.y - p2.y) < EPSILON &&
            fabs(p1.z - p2.z) < EPSILON;
}

Answer 6

There are faster ways to get an approximate distance but nothing built into the standard libraries. Take a look at this article on FlipCode that covers the method for fast 2D distances. It essentially collapsed the sqrt function into a compound linear function that can be quickly calculated but isn't 100% accurate. However, on modern machines these days fpmath is fairly fast so don't optimize too early, you might find that you're fine taking your simple approach.

Answer 7

You might find this article interesting:

http://www.codemaestro.com/reviews/9

It describes how the square root was calculated in the Quake 3 engine, claiming that on some CPU's it ran 4 times as fast as the sqrt() function. Not sure whether it'll give you a performance boost in C++ nowadays - but still an interesting read

Answer 8

You may try to use SSE extensions. For example, you can init two vectors A(x1,y1,z1) and B(x2,y2,z2):

_m128 A = _mm_set_ps(x1, y1, z1, 0.0f)
_m128 B = _mm_set_ps(x2, y2, z2, 0.0f)

Then compute diff using _mm_sub_ps:

__m128 Diff = _mm_sub_ps(A, B)

Next compute sqr of diff:

__m128 Sqr = __mm_mul_ps(Diff, Diff)

And finally:

__m128 Sum = add_horizontal(Sqr)
__m128 Res = _mm_sqrt_ss(Sum)

Res[0] will be filled with your answer.

P.S. add_horizontal is a place for optimization

Answer 9

Note that when using sqrt(dx*dx+dy*dy+dz*dz) the sum of squares might overflow. hypot(dx, dy) computes a distance directly without any chance of overflow. I'm not sure of the speediest 3d equivalent, but hypot(dx, hypot(dy, dz)) does the job and won't overflow either.

Answer 10

As far as Question 1 goes, the performance penalty is the calculation of the square root itself. The formula for calculating the distance using the square root of paired coordinate differences is what it is.

I would highly recommend to read this A-M-A-Z-I-N-G square root implementation by John Carmack of ID software he used in his engine in Quake III. It is simply MAGICAL.

Answer 11

The GNU Scientific Library defines gsl_hypot3 that computes exactly the distance you want in the first part of your question. Kind of overkill compiling the whole thing just for that, given Darius' suggestion, but maybe there's other stuff there you want.