Very fast 3D distance check?

Question

Is there a way to do a quick and dirty 3D distance check where the results are rough, but it is very very fast? I need to do depth sorting. I use STL sort like this:

bool sortfunc(CBox* a, CBox* b) {     return a->Get3dDistance(Player.center,a->center) <       b->Get3dDistance(Player.center,b->center); }  float CBox::Get3dDistance( Vec3 c1, Vec3 c2 ) {     //(Dx*Dx+Dy*Dy+Dz*Dz)^.5      float dx = c2.x - c1.x;     float dy = c2.y - c1.y;     float dz = c2.z - c1.z;  return sqrt((float)(dx * dx + dy * dy + dz * dz)); } 

Is there possibly a way to do it without a square root or possibly without multiplication?

Answer 1

You can leave out the square root because for all positive (or really, non-negative) numbers x and y, if sqrt(x) < sqrt(y) then x < y. Since you're summing squares of real numbers, the square of every real number is non-negative, and the sum of any positive numbers is positive, the square root condition holds.

You cannot eliminate the multiplication, however, without changing the algorithm. Here's a counterexample: if x is (3, 1, 1) and y is (4, 0, 0), |x| < |y| because sqrt(1*1+1*1+3*3) < sqrt(4*4+0*0+0*0) and 1*1+1*1+3*3 < 4*4+0*0+0*0, but 1+1+3 > 4+0+0.

Since modern CPUs can compute a dot product faster than they can actually load the operands from memory, it's unlikely that you would have anything to gain by eliminating the multiply anyway (I think the newest CPUs have a special instruction that can compute a dot product every 3 cycles!).

I would not consider changing the algorithm without doing some profiling first. Your choice of algorithm will heavily depend on the size of your dataset (does it fit in cache?), how often you have to run it, and what you do with the results (collision detection? proximity? occlusion?).

Answer 2

What I usually do is first filter by Manhattan distance

float CBox::Within3DManhattanDistance( Vec3 c1, Vec3 c2, float distance ) {     float dx = abs(c2.x - c1.x);     float dy = abs(c2.y - c1.y);     float dz = abs(c2.z - c1.z);      if (dx > distance) return 0; // too far in x direction     if (dy > distance) return 0; // too far in y direction     if (dz > distance) return 0; // too far in z direction      return 1; // we're within the cube } 

Actually you can optimize this further if you know more about your environment. For example, in an environment where there is a ground like a flight simulator or a first person shooter game, the horizontal axis is very much larger than the vertical axis. In such an environment, if two objects are far apart they are very likely separated more by the x and y axis rather than the z axis (in a first person shooter most objects share the same z axis). So if you first compare x and y you can return early from the function and avoid doing extra calculations:

float CBox::Within3DManhattanDistance( Vec3 c1, Vec3 c2, float distance ) {     float dx = abs(c2.x - c1.x);     if (dx > distance) return 0; // too far in x direction      float dy = abs(c2.y - c1.y);     if (dy > distance) return 0; // too far in y direction      // since x and y distance are likely to be larger than     // z distance most of the time we don't need to execute     // the code below:      float dz = abs(c2.z - c1.z);     if (dz > distance) return 0; // too far in z direction      return 1; // we're within the cube } 

Sorry, I didn't realize the function is used for sorting. You can still use Manhattan distance to get a very rough first sort:

float CBox::ManhattanDistance( Vec3 c1, Vec3 c2 ) {     float dx = abs(c2.x - c1.x);     float dy = abs(c2.y - c1.y);     float dz = abs(c2.z - c1.z);      return dx+dy+dz; } 

After the rough first sort you can then take the topmost results, say the top 10 closest players, and re-sort using proper distance calculations.