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

Question

有没有办法在结果粗糙但非常非常快的情况下进行快速而肮脏的 3D 距离检查？我需要进行深度排序。我像这样使用 STL sort:

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

有没有一种方法可以不用平方根或不用乘法？

Answer 1

您可以省略平方根，因为对于所有正数(或真正的非负数)x和 y , 如果 sqrt(x) < sqrt(y)然后 x < y .由于您要对实数的平方求和，因此每个实数的平方都是非负数，并且任何正数的和都是正数，因此平方根条件成立。

但是，如果不更改算法，就无法消除乘法。这是一个反例:如果 x是 (3, 1, 1) 和 y是 (4, 0, 0), |x| < |y|因为sqrt(1*1+1*1+3*3) < sqrt(4*4+0*0+0*0)和 1*1+1*1+3*3 < 4*4+0*0+0*0 , 但是 1+1+3 > 4+0+0 .

由于现代 CPU 计算点积的速度比它们实际从内存中加载操作数的速度要快，因此通过消除乘法您不太可能获得任何好处(我认为最新的 CPU 有一个特殊指令可以计算每 3 个周期点积!)。

如果不先进行一些分析，我不会考虑更改算法。您对算法的选择在很大程度上取决于数据集的大小(它是否适合缓存？)、运行它的频率以及您对结果的处理方式(碰撞检测？接近度？遮挡？)。