lordcoste

03-21-2011, 07:54 PM

Hello, I'm using OpenCL to find the nearest neighbour between two set of 3D points.

Nearest Neighbour: For each point(x,y,z) in the DataSet I have to find the nearest one in the model. Squared distance = (Ax-Bx)^2 + (Ay-By)^2 + (Az-Bz)^2

So I think that every point of the dataset need to have read access to ALL the points of the model. Is this the only way or are there other approaches?

Here what I've done so far:

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;

/* Ottimizzato per memoria locale */

int local_x, local_y, local_z;

local_x = dataset[g_dataset_id].x;

local_y = dataset[g_dataset_id].y;

local_z = dataset[g_dataset_id].z;

/* Fine ottimizzazione */

for (int i=0; i<model_size; ++i) {

dx = model[i].x - local_x;

dx = dx * dx;

dy = model[i].y - local_y;

dy = dy * dy;

dz = model[i].z - local_z;

dz = dz * dz;

d = dx + dy + dz;

if(d < dmin || dmin == -1)

{

nearest[g_dataset_id] = i;

dmin = d;

}

}

}

The code seems to work, but I'm sure that it can be optimized.

The optimization is important because this kernel will be part of a bigger program.

Any advice?

Thanks :)

P.S. I know that there are other (better) methods to find nearest neighbour, like kd-tree, but for now I would like to do the easy one.

Nearest Neighbour: For each point(x,y,z) in the DataSet I have to find the nearest one in the model. Squared distance = (Ax-Bx)^2 + (Ay-By)^2 + (Az-Bz)^2

So I think that every point of the dataset need to have read access to ALL the points of the model. Is this the only way or are there other approaches?

Here what I've done so far:

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;

/* Ottimizzato per memoria locale */

int local_x, local_y, local_z;

local_x = dataset[g_dataset_id].x;

local_y = dataset[g_dataset_id].y;

local_z = dataset[g_dataset_id].z;

/* Fine ottimizzazione */

for (int i=0; i<model_size; ++i) {

dx = model[i].x - local_x;

dx = dx * dx;

dy = model[i].y - local_y;

dy = dy * dy;

dz = model[i].z - local_z;

dz = dz * dz;

d = dx + dy + dz;

if(d < dmin || dmin == -1)

{

nearest[g_dataset_id] = i;

dmin = d;

}

}

}

The code seems to work, but I'm sure that it can be optimized.

The optimization is important because this kernel will be part of a bigger program.

Any advice?

Thanks :)

P.S. I know that there are other (better) methods to find nearest neighbour, like kd-tree, but for now I would like to do the easy one.