非常快速的3D距离检查？

问题描述

有没有办法做一个快速和肮脏的3D距离检查那里的结果是粗糙的，但它是非常非常快的？我需要做深度排序。我用STL 排序是这样的：

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?

推荐答案

可以离开了平方根，因为一切积极（还是真的，非负）数 X 和是，如果的sqrt（x）的＆LT;开方（Y）然后 X＆LT;是。因为你求和实数的平方，每次实数的平方非负，以及任何正数的总和为正时，平方根条件成立。

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.

您不能，消除了多元化，但不改变算法。这里有一个反例：如果 X 为（3,1，1）和是是（4,0，0） ， | x | ＆LT; | Y | ，因为的sqrt（1 * 1 + 1 * 1 + 3 * 3）＆LT;开方（4 * 4 + 0 * 0 + 0 * 0）和 1 * 1 + 1 * 1 + 3 * 3'; 4 * 4 + 0 * 0 + 0 * 0 ，而 1 + 1 + 3＆GT; 4 + 0 + 0 。

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.

由于现代的CPU可以计算点积速度比他们实际上可以从内存中加载的操作数，这是不可能的，你有什么要争取通过消除乘以反正（我认为最新的CPU有一个特殊的指令，可以计算点积每3个周期！）。

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?).

这篇关于非常快速的3D距离检查？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！