有没有办法在结果粗糙的地方进行快速而肮脏的3D距离检查,但速度非常快？我需要做深度排序.我sort像这样使用STL :
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));
}
有可能没有平方根或可能没有乘法的方法吗？
Gab*_*abe 64
你可以离开了平方根,因为对所有正(或真的,非负)数x和y如果,sqrt(x) < sqrt(y)然后x < y.由于你是实数的平方和,所以每个实数的平方都是非负的,任何正数之和都是正数,平方根条件成立.
但是,如果不更改算法,则无法消除乘法.这是一个反例:if 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个周期!).
如果不首先进行一些分析,我不会考虑更改算法.您选择的算法在很大程度上取决于数据集的大小(它是否适合缓存？),运行它的频率,以及您对结果的处理方式(碰撞检测？邻近？遮挡？).
sle*_*man 27
我通常做的是先按曼哈顿距离过滤
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;
}
在粗略的第一次排序之后,您可以获得最顶级的结果,比如前十名最接近的玩家,并使用适当的距离计算重新排序.
Kei*_*all 17
这是一个可以帮助你摆脱sqrt和multiply的等式:
max(|dx|, |dy|, |dz|) <= distance(dx,dy,dz) <= |dx| + |dy| + |dz|
这将为您提供距离的范围估计,将其降低到3倍(上限和下限最多相差3倍).然后,您可以对较低的数字进行排序.然后,您需要处理数组,直到到达比第一个遮蔽对象远3x的对象.然后,您可以保证找不到数组中较晚的任何对象.
顺便说一下,这里排序太过分了.一种更有效的方法是制作一系列具有不同距离估计值的桶,比如[1-3],[3-9],[9-27],......然后将每个元素放入桶中.从最小到最大处理铲斗,直到到达模糊物体.处理1个额外的桶只是为了确定.
顺便说一句,浮点数乘法现在相当快.通过将其转换为绝对值,我不确定你获得了多少收益.
我很失望,那些伟大的数学技巧似乎正在迷失.以下是您要求的答案.来源是Paul Hsieh的优秀网站:http://www.azillionmonkeys.com/qed/sqroot.html.请注意,你不关心距离; 你会用距离的平方来做得很好,这会更快.
在2D中,我们可以得到距离度量的粗略近似值,而没有使用公式的平方根:
distanceapprox(x,y)= (1 + 1 /(4-2*√2))/ 2*min((1 /√2)*(| x | + | y |),max(| x |,| y |))http://i52.tinypic.com/280tbnc.gif
这将偏离真正的答案最多约8%.3维的类似推导导致:
distanceapprox(x,y,z)= (1 + 1 /4√3)/ 2*min((1 /√3)*(| x | + | y | + | z |),max(| x |, | y |,| z |))http://i53.tinypic.com/2vlphz8.gif
最大误差约为16%.
但是,应该指出的是,通常距离仅用于比较目的.例如,在经典的mandelbrot集(z←z2 + c)计算中,复数的大小通常与边界半径长度2进行比较.在这些情况下,可以简单地通过基本平方来减小平方根.比较的两面(因为距离总是非负的).也就是说:
?(?x2+?y2) < d is equivalent to ?x2+?y2 < d2, if d ? 0
我还要提一下,Richard G. Lyons的"理解数字信号处理"第13.2章有一系列令人难以置信的2D距离算法(又称复数幅度近似).举个例子:
Max = x> y？x:y;
Min = x <y？x:y;
if(Min <0.04142135Max)
Run Code Online (Sandbox Code Playgroud)|V| = 0.99 * Max + 0.197 * Min;其他
Run Code Online (Sandbox Code Playgroud)|V| = 0.84 * Max + 0.561 * Min;
它与实际距离的最大误差为1.0%.惩罚当然是你做了几个分支; 但即使是这个问题的"最被接受"的答案也至少有三个分支.
如果您真的想要对特定精度进行超快速距离估计,可以使用与编译器供应商相同的基本方法编写自己的简化fsqrt()估计,但精度较低,通过执行固定的迭代次数.例如,您可以消除极小或大数字的特殊情况处理,和/或减少Newton-Rapheson迭代次数.这是所谓的"Quake 3" 快速逆平方根实现的关键策略- 它是经典的Newton算法,只有一次迭代.
不要假设你的fsqrt()实现很慢而没有对它进行基准测试和/或读取源代码.大多数现代fsqrt()库实现都是无分支的,并且非常快速. 例如,这是一个旧的IBM浮点fsqrt实现. 过早优化是,而且永远都是所有邪恶的根源.
请注意,对于图2(非负)的距离A和B,如果sqrt(A) < sqrt(B),然后A< B.创建的专用版本Get3DDistance()(GetSqrOf3DDistance())不调用的sqrt(),将只为使用sortfunc().
如果您担心性能，您还应该注意发送参数的方式：
float Get3dDistance( Vec3 c1, Vec3 c2 );
意味着 Vec3 结构的两个副本。使用参考文献代替：
float Get3dDistance( Vec3 const & c1, Vec3 const & c2 );