[OpenCL]最近邻居使用欧氏距离

Question

我正在使用OpenCL来查找两组3D点之间的最近邻居.

最近邻:对于DataSet中的每个点(x,y,z),我必须找到模型中最近的一个.平方距离=(Ax-Bx)^ 2 +(Ay-By)^ 2 +(Az-Bz)^ 2

这是我到目前为止所做的:

struct point {
int x;
int y;
int z;
};

__kernel void 
nearest_neighbour(__global struct point *model,
__global struct point *dataset,
__global int *nearest,
const unsigned int model_size)
{
    int g_dataset_id = get_global_id(0);

    int dmin = -1;
    int d, dx, dy, dz;

    for (int i=0; i<model_size; ++i) {
        dx = model[i].x - dataset[g_dataset_id].x;
        dx = dx * dx;

        dy = model[i].y - dataset[g_dataset_id].y;
        dy = dy * dy;

        dz = model[i].z - dataset[g_dataset_id].z;
        dz = dz * dz;

        d = dx + dy + dz;

        if(dmin == -1 || d < dmin)
        {
            nearest[g_dataset_id] = i;
            dmin = d;
        }
    }
}

代码似乎有效,但我确信它可以优化.我想知道如何利用本地内存使其更好.

谢谢

PS我知道还有其他(更好的)方法可以找到最近的邻居,比如kd-tree,但是现在我想做一个简单的方法.

Answer 1

编译器可能会为您提升这些循环不变量，但为了确保完成，请尝试这段代码，将它们分配给名为datum_x等的临时变量。另外，将 dmin 初始化为MAX_INT可以避免与 进行多余的比较-1。另一种方法是展开第一个循环迭代（使用i=0）以初始化 dmin。

int dmin = MAX_INT;
int d, dx, dy, dz;
int datum_x, datum_y, datum_z;

datum_x = dataset[g_model_id].x;
datum_y = dataset[g_model_id].y;
datum_z = dataset[g_model_id].z;

for (int i=0; i<size_dataset; ++i) {
    dx = model[i].x - datum_x;
    dx = dx * dx;

    dy = model[i].y - datum_y;
    dy = dy * dy;

    dz = model[i].z - datum_z;
    dz = dz * dz;

    d = dx + dy + dz;

    if(d < dmin)
    {
        nearest[g_dataset_id] = i;
        dmin = d;
    }
}