非常快的3D距离检查？
有没有办法做一个快速和肮脏的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)); }
有没有办法做到这一点没有平方根或可能没有乘法？
如果sqrt(x) < sqrt(y)则x < y ，所以可以忽略平方根，因为对于所有的正数（或者非负数） x和x < y 。 由于你是实数的平方和，每个实数的平方是非负的，任何正数的和是正的，平方根的条件成立。
但是，如果不更改algorithm，则无法消除乘法。 这里有一个反例：如果x是（3,1,1）， y是（4,0,0）， |x| < |y| |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个周期！）。
如果不先做一些分析，我不会考虑改变algorithm。 你select的algorithm在很大程度上取决于你的数据集的大小（是否适合caching？），你需要多长时间运行一次，以及你对结果做了什么（碰撞检测？接近？闭塞？）。
我通常做的是先曼哈顿距离过滤
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 }
对不起，我没有意识到这个函数是用来sorting的。 你仍然可以使用曼哈顿距离来得到一个非常粗糙的第一类：
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; }
经过粗略的第一次sorting后，您可以获得最高的结果，说出前10名最接近的球员，并使用适当的距离计算重新sorting。
这里有一个方程可能会帮助你摆脱sqrt和multiply：
max(|dx|, |dy|, |dz|) <= distance(dx,dy,dz) <= |dx| + |dy| + |dz|
这可以得到距离的距离估计值，这个距离可以在3倍的范围内（上限和下限相差至多3倍）。 然后，您可以sorting，例如，较低的数字。 然后，您需要处理该数组，直到到达比第一个模糊对象距离更远的对象。 然后保证在数组中稍后找不到任何对象。
顺便说一下，sorting在这里是矫枉过正的。 一个更有效的方法是制作一系列具有不同距离估计的桶，比如说[1-3]，[3-9]，[9-27]，然后把每个元素放入一个桶中。 处理桶从最小到最大，直到你到达一个模糊的对象。 处理1额外的桶只是为了确保。
顺便说一句，浮点乘法现在是相当快的。 我不确定你通过将其转化为绝对值获得了多less收益。
我感到失望的是，伟大的旧math技巧似乎正在迷失。 这是你要求的答案。 资料来源是谢霆锋杰出的网站： http ： //www.azillionmonkeys.com/qed/sqroot.html 。 请注意，你不关心距离; 你会做的很好，你的sorting方式的距离，这将更快。
在2D中，我们可以得到没有平方根的距离度量的粗略近似公式：
distanceapprox（x，y）= （1 + 1 /（4-2 *√2））/ 2 * min（（1 /√2）*（| x | + | y |），max（| x | y |））160wpb4.gif
这会偏离真正的答案最多8％左右。 类似的三维推导导致：
（x，y，z）= （1 + 1 /4√3）/ 2 * min（（1 /√3）*（| x | + | y | + | z | | y |，| z |））160wpb4.gif
最大误差约为16％。
但是，应该指出的是，通常距离只是为了比较的目的。 例如，在经典Mandelbrot集（z←z2 + c）计算中，通常将复数的幅度与边界半径长度2进行比较。在这些情况下，可以简单地通过平方根比较的两边（因为距离总是非负的）。 也就是说：
√(Δx2+Δy2) < d is equivalent to Δx2+Δy2 < d2, if d ≥ 0
我还要提到Richard G. Lyons的“了解数字信号处理”的第13.2章有一个令人难以置信的二维距离algorithm（又名复数数量级近似值）的集合。 举一个例子：
Max = x> y？ x：y;
Min = x <y？ x：y;
如果（Min <0.04142135Max）
|V| = 0.99 * Max + 0.197 * Min;其他
|V| = 0.84 * Max + 0.561 * Min;
其实际距离最大误差为1.0％。 当然，惩罚是你在做一对夫妇的分支; 但即使这个问题“最被接受”的答案也至less有三个分支。
如果你认真的做一个特定精度的超快速距离估计，你可以通过使用编译器厂商提供的相同的基本方法来编写你自己的简化的fsqrt（）估计来做到这一点，但是通过做一个更低的精度固定的迭代次数。 例如，您可以消除极小或大数的特殊情况处理，和/或减less牛顿 – 拉皮逊迭代次数。 这是所谓的“Quake 3” 快速反平方根实现的关键策略 – 这是经过一次迭代的经典牛顿algorithm。
不要假设你的fsqrt（）实现很慢，没有对它进行基准testing和/或读取源代码。 大多数现代的fsqrt（）库实现是无分支的，而且非常快。 例如，这里是一个旧的IBM浮点fsqrt实现。 不成熟的优化是永远是邪恶的根源。
请注意，对于2（非负）距离A和B ，如果sqrt(A) < sqrt(B) ，则A < B 。 创buildGet3DDistance() （ GetSqrOf3DDistance() ）的专用版本，该函数不会调用仅用于sortfunc()的sortfunc() 。
如果你担心performance的话，你还应该照顾你发表论点的方式：
float Get3dDistance( Vec3 c1, Vec3 c2 );
意味着两个Vec3结构的副本。 改用引用：
float Get3dDistance( Vec3 const & c1, Vec3 const & c2 );
由于d 2 =（x 1 -x 2 ） 2 +（y 1 -y 2 ） 2 +（z 1 -z 2 ） 2 ，所以可以比较距离的平方而不是实际的距离。 它没有摆脱乘法，但它消除了平方根操作。
input向量多久更新一次，以及它们的sorting频率如何？ 取决于你的devise，用预先计算的距离来扩展“Vec3”类可能是相当有效的，然后对其进行sorting。 如果您的实现允许您使用vector化操作，那么尤其重要。
除此之外，请参阅关于近似距离函数的flipcode.com文章 ，以讨论另一种方法。
取决于你用来比较的点的数量，下面的内容几乎可以保证以近似的顺序得到点列表，假定所有点在所有迭代中都变化。
1）将数组重写为单个曼哈顿距离列表，其中out [i] = abs（posn [i] .x – player.x）+ abs（posn [i] .y – player.y）+ abs（posn [我] .z – player.z）;
2）现在你可以使用基数sorting浮点数来sorting它们。
请注意，在实践中，这比sorting3d位置的速度要快很多，因为它显着减less了sorting操作中的内存带宽需求，所有的时间将花费在不可预知的访问和写入中发生。 这将在O（N）时间运行。
如果许多点在每个方向上都是固定的，那么使用KD-Tree的algorithm要快得多，尽pipe实现要复杂得多，并且要获得好的内存访问模式要困难得多。
如果这只是一个sorting的值，那么可以将sqrt（）换成一个abs（）。 如果您需要将距离与设定值进行比较，请获取该值的平方。
例如，不要检查sqrt（…）与a，你可以比较abs（…）和a * a。
你可能要考虑caching播放器和对象之间的距离，然后在你的sortfunc使用它。 这将取决于你的sorting函数看着每个对象的次数，所以你可能必须确定configuration文件。
我得到的是你的sortingfunction可能会做这样的事情：
compare(a,b); compare(a,c); compare(a,d);
你会每次计算玩家和“a”之间的距离。
正如其他人所说，在这种情况下，你可以省略sqrt 。
如果你可以在玩家的中心坐标，使用球坐标？ 然后你可以按半径sorting。
但是，这是一个很大的问题。
如果您的操作发生了很多，可能将其放入一些3D数据结构中。 您可能需要距离sorting来决定哪个对象是可见的，或者一些类似的任务。 为了复杂性，您可以使用：
-
统一（立方）细分
将使用的空间分成单元格，并将对象分配给单元格。 快速访问元素，邻居是微不足道的，但空单元占用大量的空间。
-
四叉树
给定一个阈值，将已用空间recursion分成四个四元组，直到小于阈值数的对象在里面。 对数访问元素如果对象不互相堆栈，邻居不难发现，空间高效的解决scheme。
-
八叉树
与四叉树相同，但分为8个，即使对象在上面也是最佳的。
-
Kd树
给定一些启发式成本函数和一个阈值，将成本函数最小的平面分割成两半。 （例如：每边有相同数量的物体）recursion地重复直到达到阈值。 总是对数的，邻居是难以获得，空间效率（并在所有维度工作）。
使用上述任何一种数据结构，您可以从一个位置开始，从邻居到邻居，以增加距离列出对象。 您可以在所需的切割距离停止。 您也可以跳过相机无法看到的单元格。
对于距离检查，您可以执行上面提到的例程之一，但最终不会随着对象数量的增加而良好地扩展。 这些可用于显示需要数百GB硬盘空间的数据。
