发现在三维点云的近邻，GPU

Question

我想计算最近的邻居通过GPU的点云的每一个点。我的数据集是这样的：

<number of points in column>
<number of columns>

x   y   z
x   y   z
z   y   z
... ... ... 

有近20 ^ 6分。 我使用vector<PointXYZ> Input;数据存储与

class PointXYZ
{
public:
    PointXYZ();
    ~PointXYZ();
    PointXYZ(float X, float Y, float Z) : x(X), y(Y), z(Z) {};

    float x;
    float y;
    float z;

};

读取数据是在for循环中，这忽略点不存在信息（x == 0 &&ÿ== 0 &&Ž== 0）。

PointXYZ* NewPoint = new PointXYZ(x, y, z);
Input.push_back(*NewPoint);

这里是我的问题：

1. 什么是最好的输入结构，将其发送到GPU之前读取数据？ （当前读数大约需要120秒）。
2. 我没有在2D图像点的适当指标（因为我忽略了点，而信息）。每个点都包含X，Y，Z值。什么是最准确的，但没有这么先进的算法来寻找3/6/9最近的邻居？是用于经由GPU该号码点的线性的比较（蛮力）没有效率？

我一直在寻找在八叉树，但我不知道怎么一点云都需要适合的指标进行划分。

Answer 1

我只是做了一些测试。我用了一个有点集群的3D数据集10'000'000点。实现在Java中，我用我的qthypercube2实现。

1. 对于我的测试中，我经常将数据存储在数据库中的大型浮法[] BLOB。载入10'000'000点到内存中大约需要0.5秒。
2. 将数据加载到一个四叉树（我用我自己的特殊实现）大约需要4秒。
3. 执行1'000'000 3-NN搜索花费约20秒，这将是约200秒或3.3分钟10'000'000 3-N的搜索。

我从来没有使用的GPU还是让我们做一些数学：我认为用“蛮力”你的意思是每一点比较每隔一点？ 10 ^ 7点，这意味着10 ^ 14比较操作。每个比较服用10个循环（只是有一个数）指10 ^ 15计算周期。比方说，GPU可以让1000点的操作并行执行，这仍然意味着10 ^ 12个周期。如果GPU的时钟频率为1GHz的（每秒10 ^ 9 OPS），总的搜索将是10 ^一十分之一十二^ 9 = 10 ^ 3 = 1000秒。这并不考虑到：将数据加载到GPU，存储所述（中间）最近的邻居，排序中间结果（如果它比1NN更多），...

当然，你的GPU和NN-搜索实现的细节可能会有所不同，因为可能是你的数据集的实际大小。所有这一切都可能减少或增加这一千秒。另外对于四叉树，该数据集的特点（集群等）可以发挥很大的作用，因为可能是搜索的类型（我试验了3个最近的邻居）。也是我实现的，因为它适用于任何维度的意义上的“通用”。专用的3D实现可能会更快。

我的猜测：在10M点，采用四叉树应该比GPU版本更快，肯定更容易实现。