有没有一种快速而粗略的方法来进行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));
}
有可能不使用平方根或乘法的方式来实现吗？
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。std::sort 就能击败很多人试图放弃的垃圾代码。例如，大量函数调用的问题在 g++ 中基本上消失了，如果你传递一个 lambda 而不是一个函数指针。（没有尝试过其他编译器；如果指针值在编译时可知，它们甚至可以完全优化掉它。） - cHao我通常会先按曼哈顿距离进行过滤。
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
}
如果您更了解您的环境，实际上可以进一步优化此过程。例如，在像飞行模拟器或第一人称射击游戏这样有地面的环境中，水平轴比垂直轴要大得多。在这样的环境中，如果两个物体相距很远，则它们很可能更多地由x和y轴分隔而不是z轴（在第一人称射击游戏中，大多数物体共享相同的z轴）。因此，如果您首先比较x和y，则可以从函数中提前返回并避免进行额外的计算：
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
}
抱歉，我没有意识到这个函数是用于排序的。你仍然可以使用曼哈顿距离来进行第一次粗略的排序：
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;
}
在粗略的第一次排序之后，您可以选择最靠前的结果，例如最接近的前10名玩家，并使用正确的距离计算进行重新排序。
> 可能和 - 一样慢，而 abs 的成本并不高，但每个 if 都会创建一个条件分支 - 因此可能会被错误地预测。对于简单的曼哈顿距离（或者说简单的三个乘积之和的距离平方），我不会在没有良好的分析证据的情况下增加复杂性。消除平方根是值得的，但这个曼哈顿距离需要小心处理，即使在第一个版本中，我也会使用一个带有 and 运算符的单个返回。 - user180247(x1-x2)^2+(y1-y2)^2+(z1-z2)^2 运算可以轻松地进行向量化处理，只需使用4个操作：加、乘、加、加。考虑到两组向量的操作可以轻松地进行流水线处理，你可能会发现完整比较版本的速度平均比曼哈顿距离版本更快。 - Gabe这里有一个方程式，可能会帮助您同时消除平方根和乘法：
max(|dx|, |dy|, |dz|) <= distance(dx,dy,dz) <= |dx| + |dy| + |dz|
这将为您提供一个距离范围估计，将其定位到3倍因子内（上下界最多相差3倍）。 然后您可以按较低的数字排序。 然后，直到您达到第一个遮挡对象的3倍远的对象时，您需要处理数组。 然后，保证在数组中后面不会找到更接近的任何对象。
顺便说一句，在这里进行排序是过度的。 一种更有效的方法是制作一系列具有不同距离估计的桶，例如[1-3]，[3-9]，[9-27]，....然后将每个元素放入桶中。 从最小到最大处理桶，直到你找到一个遮挡物体。 多处理1个桶以确保。
顺便说一句，浮点乘法现在非常快。 我不确定将其转换为绝对值能带来多少好处。
该公式计算结果与真实答案最多相差约8％。类似地，在三维中进行类似推导，得到如下公式:
distanceapprox (x, y, z) =
最大误差约为16%。
然而，需要指出的是，在许多情况下，距离仅用于比较。例如，在经典曼德博集合（z←z2+c）计算中，复数的大小通常与半径长度为2的边界进行比较。在这些情况下，可以通过实质上平方比较两侧（因为距离始终为非负），简单地放弃平方根。也就是说：
√(Δx2+Δy2) < d is equivalent to Δx2+Δy2 < d2, if d ≥ 0
我还应该提到，Richard G. Lyons的《理解数字信号处理》第13.2章收录了令人难以置信的二维距离算法（也称为复数幅度近似）。以下是一个例子：
这个方法最大误差只有实际距离的1.0%。当然，代价是要进行几个分支；但即使对于此问题“被广泛接受”的答案至少也有三个分支。Max = x > y ? x : y;
Min = x < y ? x : y;
if ( Min < 0.04142135Max )
|V| = 0.99 * Max + 0.197 * Min;else
|V| = 0.84 * Max + 0.561 * Min;
A和B，如果sqrt(A) < sqrt(B)，则A < B。创建一个专门用于sortfunc()的Get3DDistance()（GetSqrOf3DDistance()）的特殊版本，该版本不调用sqrt()。Vec3实现了减法和点积运算，那么这样就足够了：Vec3 d = A - B; float dist = dot(d,d); - greyfadefloat Get3dDistance( Vec3 c1, Vec3 c2 );
意味着需要两个Vec3结构的副本。请使用引用代替：
float Get3dDistance( Vec3 const & c1, Vec3 const & c2 );
根据您用于比较的点数略有不同，以下内容几乎可以保证在所有迭代中假设所有点都发生变化的情况下以近似顺序获取点列表。
1）将数组重写为曼哈顿距离的单个列表，其中out [i] = abs（posn [i] .x - player.x）+ abs（posn [i] .y - player.y）+ abs（posn [i] .z - player.z）;
2）现在您可以对浮点数使用基数排序进行排序。
请注意，在实践中，这比对3D位置列表进行排序要快得多，因为它显着降低了排序操作中的内存带宽要求，而所有时间都会花费在其中不可预测的访问和写入。 这将在O（N）时间内运行。
如果许多点在每个方向上都是静止的，则有更快的算法，例如使用KD-Tree，尽管实现要复杂得多，并且很难获得良好的内存访问模式。
sqrt 的参数始终为正数，使得使用 abs 是多余的。 - Gabe