我正在寻找有效的算法来检查一个点是否在 3D 中靠近另一个点。
sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius
这似乎并不太快,实际上我不需要这么大的准确性。我还能怎么做?
我正在寻找有效的算法来检查一个点是否在 3D 中靠近另一个点。
sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius
这似乎并不太快,实际上我不需要这么大的准确性。我还能怎么做?
平方距离,然后调用sqrt()
,这要快得多:
(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius
当然,在许多情况下,至少radius * radius
可以提前计算并存储为例如squaredRadius
.
好吧,如果您可以满足于立方体距离而不是球面距离,那么一个非常幼稚的实现将是这样的:
Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius
如果证明存在瓶颈,您可以使用自己喜欢的优化 Math.Abs 的方法。
我还应该补充一点,如果其中一个维度的变化通常小于其他维度,那么将最后一个维度放在最后应该会带来性能提升。例如,如果您主要处理“地面”xy 平面上的对象,那么最后检查 z 轴,因为您应该能够通过使用 x 和 y 检查来更早地排除碰撞。
如果您不需要很高的精度,也许您可以检查第二个点是否在立方体内(边长'2a'),而不是第一个点在中心的球体:
|x2-x1|<a && |y2-y1|<a && |z2-z1|<a
Because of the pipelined processor architectures it is - nowadays - in most cases more efficient to do the FPU calculation twice, as branching once. In case of a branch mis-prediction you are stalling for ages ( in cpu-terms ).
So, I would rather go the calculation-way, not the branching-way.
如果我们要优化它,因为它运行了数十亿次,我会使用unwind 的方法来解决这个问题,然后使用 SIMD 并行化它。有几种不同的方法可以做到这一点。您可以简单地在一个操作中执行所有减法 (x2-x1,y2-y1,z2-z1),然后在一个操作中进行乘法运算。这样你就可以在方法内部进行并行化,而无需重新设计算法。
或者,您可以编写一个批量版本,对许多元素计算 (x2-x1)^2+(y2-y1)^2+(z2-z1)^2 - r^2 并将结果存储在一个数组中。您也许可以获得更好的吞吐量,但这意味着重新设计您的算法并取决于测试的用途。
如果您真的连续进行大量测试,您也可以使用 OpenMP 之类的工具轻松优化它。
如果您不需要准确性,您可以检查您是否在立方体而不是球体中。
这里也有一些选项,您可以选择包围球体的立方体(无误报) 与球体体积相同的立方体(一些误报和否定,但最大误差最小化),包含在球体(无误报)。
这种技术也可以很好地扩展到更高的维度。
如果你想让所有点靠近另一个点,某种形式的空间索引也可能是合适的(也许是 kd-tree)
如果您必须检查许多其他点,您可以考虑使用空间排序方法来快速发现某个位置附近的点。看看这个链接: wiki 链接
去掉平方根后,如果值变大,最好应用对数。
使用最大值(abs(x1-x2),abs(y1-y2),abs(z1-z2))
这是立方距离,如果你做很多点,大多数时候它只做第一次测试。
close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);