1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
|
#pragma OPENCL EXTENSION cl_khr_fp64: enable
/* Return the distance between the two given points
* param a: Pointer to a constant address memory of the first point
* param b: Pointer to a constant address memory of the second point
* param dim: Dimension of points
*/
double sqrtDistance (__global double* a, __global double* b, const int dim)
{
double dist = 0.0;
for (int i = 0; i < dim; ++i)
dist += ((a[i] - b[i]) * (a[i] - b[i]));
return sqrt (dist);
}
/* Return the nearest neighbor of the query point
* param vertices: Vertices coordinates among which to search the nearest neighbors (__constant to allow all work-items to read only)
* param queries: Array containing the query points coordinates
* param nearests: Array containing the nearest neighbor, (__global to allow all work-items to read/write it)
* param nearestDist: Array containing the nearest distances, (__global to allow all work-items to read/write it)
* param k: Number of nearest neighbors required
* param nbVertices: Number of vertices in the cloud
* param nbQueries: Number of query points
* param dim: Dimension of points
*/
__kernel void nearestNeighbors (__global double* vertices,
__global double* queries,
__global int* nearests,
__global double* nearestDists,
const int k,
const int nbVertices,
const int nbQueries,
const int dim)
{
__private int queryIdx = get_global_id (0); // Retrieve the index of the work-item that will perform the KNN for the "queryIndex" query point
if (queryIdx >= nbQueries)
return;
__global double* ptrCurrentVertex;
__global double* ptrCurrentQuery = queries + (dim * queryIdx);
double distanceVertexToQuery = 0.0;
if (distanceVertexToQuery >= nearestDists[k - 1])
return;
for (int vertexIdx = 0; vertexIdx < nbVertices; ++vertexIdx)
{
ptrCurrentVertex = vertices + (dim * vertexIdx);
distanceVertexToQuery = sqrtDistance (ptrCurrentVertex, ptrCurrentQuery, dim);
// Need to compare the distance computed with the maximum distance
// If the distance from the current vertex is lower than the greater distance stored in the array of k distances
if (distanceVertexToQuery < nearestDists[k * (queryIdx + 1) - 1])
{
for (int i = k * (queryIdx + 1) - 2; i >= k * queryIdx - 1; --i) // Search the position where to insert the new distance: distanceVertexToQuery
{
if ((i == k * queryIdx - 1) || (distanceVertexToQuery >= nearestDists[i]))
{
for (int j = k * (queryIdx + 1) - 1; j > i + 1; --j)
{
nearestDists[j] = nearestDists[j - 1];
nearests[j] = nearests[j - 1];
}
nearestDists[i + 1] = distanceVertexToQuery;
nearests[i + 1] = vertexIdx;
break;
}
}
}
}
} |
Partager