使用正确的优化算法C ++查找3D空间中点之间的距离 [英] Finding distance between points in 3D space using correct optimization algorithm C++
问题描述
很容易使用数学公式来查找3D空间中任意两个点之间的距离，即:√((x2-x1)^2 )+(y2-y1)^2+(z2-z1)^2
It's easy to use the mathematical formula to find distance between any two points in 3D space which is:√((x2-x1)^2 )+(y2-y1)^2+(z2-z1)^2
查找空间中任意两个点之间的距离非常容易计算，其中每个点在3D空间中具有(x，y z)坐标.
And it's pretty easy to calculate for finding distance between any two points in space where each point has (x, y z) coordinates in 3D-space.
我的问题是，将这个公式扩展到我面临优化难题的地方.我所做的是创建一个简单的Vector类，并使用C ++中编码的此公式来计算距离.
My question, extends this formula to a large scale where I'm facing optimization hiccups. What I did was create a simple Vector class and use this formula coded in C++ to calculate the distance.
如果有1000分怎么办?我该怎么办?我在考虑使用简单的std::vector存储这些3D点将不会是计算这1000个点之间距离的优化方法.
What if there are a 1000 points? How do I go about it? I'm thinking using a simple std::vector to store these 3D points won't be optimized way of calculating the distance between these 1000 points.
推荐答案
优化级别不同，每个级别都取决于实际情况.
There are different level of optimization, each depends on actual situation.
在实现级别，您希望以友好的方式将数据布局到处理器. 即.
On implementation level, you want to layout the data in a friendly way to the processor. ie.
- 连续
- 正确对齐
- vector(SSE)友好(如果您通常使用垂直SSE，或者水平方向使用AoS，则为SoA)
- 实际上启用矢量化(编译器选项或手工制作)
这可以使您最多提升10％.
This may give you up to 10% boost.
在算法级别上，您可能需要再考虑一下为什么需要核心循环中每个点的距离
On algorithm Level, you may want to think again why do you need distances of every point in core loop
- 您是否需要非常频繁地重新计算(在 模拟)，或者您可以使用过时的值并可能重新计算 在后台(例如在游戏中)
- 可以用距离平方做哪些事，这样可以节省sqrt?
- 如果数据集不经常更改，如何将其转换为极坐标，您可以将其存储在每个点的r ^ 2处， 距离平方公式，然后减少到一个cos()运算: r1 ^ 2 + r2 ^ 2-2r1r2 cos(a1-a2).
- do you ever need to recalculate it very frequently (required in simulations) or you can live with stale values and possibly re-calc in background (e.g. in game)
- Can you do with distance squared, which you can save an sqrt?
- If your data set do not change frequently, how about convert it to polar coordinate which you can cache the r^2 of each point, the distance squared formula then reduce to about one cos() operation: r1^2 + r2^2 - 2r1r2 cos(a1-a2).
在3D空间中的运算符，其复杂度与笛卡尔坐标增长到同一水平，忽略点3.
GPU注意事项
虽然1000点太少了，无法以开销进行交易，但是如果将来有更多点，您仍然可以考虑将工作转移到GPU.
While 1000 points are too few to trade for the overhead, you may still consider off-load the work to GPU if you have a lot more points in future.
这篇关于使用正确的优化算法C ++查找3D空间中点之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
