I am looking for efficent algorithm for checking if one point is nearby another in 3D.
sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius
This doesn't seem to be too fast and actually I don't need such a big accuracy. How else could I do this?
views:
290answers:
10
+24
A:
Square the distance, and drop the call to sqrt(), that's much faster:
(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius
Of course, in many cases at least radius * radius can be computed ahead of time and stored as e.g. squaredRadius.
unwind
2010-01-22 10:23:38
But like I've said, I don't need such a big accuracy. I was thinking that there may be another way to do such a distance check.
Balon
2010-01-22 10:24:58
Why don't you think this is fast? Is there any reason you think this code is going to be a problem, like being run a billion times?
John
2010-01-22 10:30:28
Mayme not a bilion times, but I'll have to check the distance maybe 5.000 times per second on machine with quite high load. And for example checking cube distance will work good for me + it will be much faster.
Balon
2010-01-22 10:33:30
@darid: What??!
KennyTM
2010-01-22 10:40:53
maybe what you need is to store your points inside a spatial structure like a octree to be able to have quite less points to compare. The distance between point is bounded by the distance between their boxes.
fa.
2010-01-22 10:41:57
@Balon, how did you find out that cube distance will be faster?
Shmoopty
2010-01-22 10:45:05
I don't see much of an inefficiency in the algorithm. If you want massively tuned algorithms, you're in the realm of mathematics soon. Look for example at this classic from Quake: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
Thorsten79
2010-01-22 10:50:35
Shmoopty: Cube distance does not do any multiplication or exponentiation.
Balon
2010-01-22 10:52:39
@darid: Do the maths again. √p < q is equivalent to p < q² as long as p, q are nonnegative. 0.6 = √0.36 < 0.7 and 0.36 < 0.49 = 0.7².
KennyTM
2010-01-22 10:56:09
Grizzly
2010-01-22 11:09:32
Yes, I'm just guessing. I haven't thought like this about it. You may be right.
Balon
2010-01-22 11:12:56
@Balon: it would be a unusual machine where `abs(x)` is faster than `(x * x)`, particularly for non-integers. The general rule, however, for knowing which algorithm is faster is *test them both and see for yourself*.
Shmoopty
2010-01-22 12:31:34
Okay! Thanks for all the tips :)
Balon
2010-01-22 12:41:40
Balon, you're guessing. 5,000 iterations is absolutely tiny. Let's guess it takes 100 cycles to do this once. So we'll round it up to 1 million cycles altogether. On a 1GHz core, you're using .1% of the power available. This is all very approximate but close enough. Profile it after you write it.
John
2010-01-22 13:36:08
@fa: Trees like that are good for many things, but I doubt that they'll beat three subtractions, three multiplications, and two additions for distance.
David Thornley
2010-01-22 15:59:18
Is that really any faster, with all those conditional logic tests? Multiplication is hardly inefficient on modern CPUs.
John
2010-01-22 10:29:26
Actually conditional logic in a tight loop could be less efficient than just calculating everything because of branch misprediction.
MadKeithV
2010-01-22 11:10:47
Do you need conditional logic for `double abs(double)` and `double max(double, double)` anyway?
MSalters
2010-01-22 13:27:26
Not sure. It's not a standard op IIRC, which makes it risky to assume optimisation.
John
2010-01-22 13:37:34
+10
A:
Well if you can be content with a cube distance rather than a spherical distance a pretty naive implementation would be like this:
Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius
You can use your own favourite methods of optimising Math.Abs if it proves a bottleneck.
I should also add that if one of the dimensions generally varies less than other dimensions then putting that one last should lead to a performance gain. For example if you are mainly dealing with objects on a "ground" x-y plane then check the z axis last, as you should be able to rule out collisions earlier by using the x and y checks.
Jack Ryan
2010-01-22 10:26:47
+1
A:
if you don't need the accuracy you can check whether you are in a cube rather than a sphere.
there are options here as well you can pick the cube that enclose the sphere (no false negatives) the cube with the same volume as the sphere (some false positives and negatives, but max error is minimized), the cube that is contained within the sphere (no false positives).
this technique also extends well to higher dimensions.
if you want to get all the points near another one some form of spacial indexing may also be appropriate (kd-tree perhaps)
jk
2010-01-22 10:27:39
+3
A:
If you do not need big accuracy maybe you can check if 2nd point is inside cube (side length '2a'), not sphere, where the 1st point is in center:
|x2-x1|<a && |y2-y1|<a && |z2-z1|<a
JBRWilkinson
2010-01-22 10:58:33
+2
A:
Because of the pipelined processor architectures it is - nowadays - in most cases more efficient to do the FPU calculation twice, as branching once. In case of a branch mis-prediction you are stalling for ages ( in cpu-terms ).
So, I would rather go the calculation-way, not the branching-way.
DarthCoder
2010-01-22 11:05:28
A:
After dropping the square root, if the values gets larger, its better to apply log.
Algorist
2010-01-22 13:27:50
A:
If we were going to optimise this because it was being run billions of times, I would solve this by using unwind's method, and then parallelizing it using SIMD. There's a few different ways to do that. You might simply do all the subtractions (x2-x1,y2-y1,z2-z1) in one op, and then the multiplies in one op also. That way you parallize inside the method without re-designing your algorithm.
Or you could write a bulk version which calculates (x2-x1)^2+(y2-y1)^2+(z2-z1)^2 - r^2 on many elements and stores the results in an array. You can maybe get better throughput, but it means re-designing your algorithm and depends what the tests are used for.
You could also easily optimize this using something like OpenMP if you were really doing lots of tests in a row.
John
2010-01-22 13:43:32
A:
This does the cube-distance, and if you are doing a lot of points, most of the time it only does the first test.
close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);
Mike Dunlavey
2010-01-22 15:36:35