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

有没有一种方法可以进行快速而肮脏的 3D 距离检查，虽然结果很粗糙，但速度非常快？我需要进行深度排序。我用STLsort像这样：

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

有没有一种方法可以不用平方根或不用乘法来做到这一点？

您可以省略平方根，因为对于所有正数（或真正的非负数）x and y, if sqrt(x) < sqrt(y) then 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) and 1*1+1*1+3*3 < 4*4+0*0+0*0, but 1+1+3 > 4+0+0.

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

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