CODEWITHSUNDEEP
c++performancemath
memC
memC

Reputation: 1025

Efficient way of finding distance between two 3D points

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_diffx_diff + y_diffy_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

Upvotes: 18

Views: 17861

Answers (11)

shuvalov
shuvalov

Reputation: 4913

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

Upvotes: 6

Charles Stewart
Charles Stewart

Reputation: 11837

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.

Upvotes: 1

Theodore Zographos
Theodore Zographos

Reputation: 2395

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.

Upvotes: 0

Darius Bacon
Darius Bacon

Reputation: 15124

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.

Upvotes: 4

pheelicks
pheelicks

Reputation: 7469

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

Upvotes: 4

Trevor Tippins
Trevor Tippins

Reputation: 2847

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.

Upvotes: 1

Mehrdad Afshari
Mehrdad Afshari

Reputation: 421968

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;
}

Upvotes: 15

user231967
user231967

Reputation: 1975

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.

Upvotes: 7

Victor Hurdugaci
Victor Hurdugaci

Reputation: 28425

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.

Upvotes: 2

Will
Will

Reputation: 75615

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.

Upvotes: 5

James
James

Reputation: 25513

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)

Upvotes: 47

Related Questions