32 #ifndef __NABO_PRIVATE_H 33 #define __NABO_PRIVATE_H 42 #define __CL_ENABLE_EXCEPTIONS 48 #define _UNUSED __attribute__ ((unused)) 64 template<
typename T,
typename A,
typename B>
65 inline T
dist2(
const A& v0,
const B& v1)
67 return (v0 - v1).squaredNorm();
71 template<
typename T,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
88 virtual unsigned long knn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
const Index k,
const T epsilon,
const unsigned optionFlags,
const T maxRadius)
const;
89 virtual unsigned long knn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
const Vector& maxRadii,
const Index k = 1,
const T epsilon = 0,
const unsigned optionFlags = 0)
const;
93 template<
typename T,
typename Heap,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
127 {
return dim | (childIndex << dimBitCount); }
129 inline uint32_t
getDim(
const uint32_t dimChildBucketSize)
const 130 {
return dimChildBucketSize & dimMask; }
133 {
return dimChildBucketSize >> dimBitCount; }
148 Node(
const uint32_t dimChild,
const T cutVal):
149 dimChildBucketSize(dimChild), cutVal(cutVal) {}
151 Node(
const uint32_t bucketSize,
const uint32_t bucketIndex):
152 dimChildBucketSize(bucketSize), bucketIndex(bucketIndex) {}
167 BucketEntry(
const T* pt = 0,
const Index index = 0): pt(pt), index(index) {}
180 std::pair<T,T> getBounds(
const BuildPointsIt first,
const BuildPointsIt last,
const unsigned dim);
182 unsigned buildNodes(
const BuildPointsIt first,
const BuildPointsIt last,
const Vector minValues,
const Vector maxValues);
197 unsigned long onePointKnn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
int i, Heap& heap, std::vector<T>& off,
const T maxError,
const T maxRadius2,
const bool allowSelfMatch,
const bool collectStatistics,
const bool sortResults)
const;
208 template<
bool allowSelfMatch,
bool collectStatistics>
209 unsigned long recurseKnn(
const T* query,
const unsigned n, T rd, Heap& heap, std::vector<T>& off,
const T maxError,
const T maxRadius2)
const;
214 virtual unsigned long knn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
const Index k,
const T epsilon,
const unsigned optionFlags,
const T maxRadius)
const;
215 virtual unsigned long knn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
const Vector& maxRadii,
const Index k = 1,
const T epsilon = 0,
const unsigned optionFlags = 0)
const;
221 template<
typename T,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
249 void initOpenCL(
const char* clFileName,
const char* kernelName,
const std::string& additionalDefines =
"");
252 virtual unsigned long knn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
const Index k,
const T epsilon,
const unsigned optionFlags,
const T maxRadius)
const;
253 virtual unsigned long knn(
const Matrix& query, IndexMatrix& indices, Matrix& dists2,
const Vector& maxRadii,
const Index k = 1,
const T epsilon = 0,
const unsigned optionFlags = 0)
const;
257 template<
typename T,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
271 template<
typename T,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
297 BuildPoint(
const Vector& pos = Vector(),
const size_t index = 0): pos(pos), index(index) {}
322 Node(
const int dim = -1,
const T cutVal = 0):dim(dim), cutVal(cutVal) {}
332 inline size_t childLeft(
size_t pos)
const {
return 2*pos + 1; }
333 inline size_t childRight(
size_t pos)
const {
return 2*pos + 2; }
334 inline size_t parent(
size_t pos)
const {
return (pos-1)/2; }
335 size_t getTreeDepth(
size_t size)
const;
336 size_t getTreeSize(
size_t size)
const;
339 void buildNodes(
const BuildPointsIt first,
const BuildPointsIt last,
const size_t pos,
const Vector minValues,
const Vector maxValues);
347 template<
typename T,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
385 bool operator() (
const BuildPoint& p0,
const BuildPoint& p1) {
return cloud.coeff(dim, p0) < cloud.coeff(dim, p1); }
393 Node(
const int dim = -2,
const Index index = 0):dim(dim), index(index) {}
403 inline size_t childLeft(
size_t pos)
const {
return 2*pos + 1; }
404 inline size_t childRight(
size_t pos)
const {
return 2*pos + 2; }
405 inline size_t parent(
size_t pos)
const {
return (pos-1)/2; }
406 size_t getTreeDepth(
size_t size)
const;
407 size_t getTreeSize(
size_t size)
const;
410 void buildNodes(
const BuildPointsIt first,
const BuildPointsIt last,
const size_t pos,
const Vector minValues,
const Vector maxValues);
417 #endif // HAVE_OPENCL Index index
index of point
Definition: nabo_private.h:161
std::vector< Node > Nodes
dense vector of search nodes, provides better memory performances than many small objects ...
Definition: nabo_private.h:155
std::vector< BuildPoint > BuildPoints
points during kd-tree construction
Definition: nabo_private.h:371
Index BuildPoint
a point during kd-tree construction is just its index
Definition: nabo_private.h:369
OpenCL support for nearest neighbour search.
Definition: nabo_private.h:222
uint32_t createDimChildBucketSize(const uint32_t dim, const uint32_t childIndex) const
create the compound index containing the dimension and the index of the child or the bucket size ...
Definition: nabo_private.h:126
Index index
index of the point to cut
Definition: nabo_private.h:392
KDTree, unbalanced, points in leaves, stack, implicit bounds, ANN_KD_SL_MIDPT, optimised implementati...
Definition: nabo_private.h:94
size_t index
index of point in cloud
Definition: nabo_private.h:296
const unsigned creationOptionFlags
creation options
Definition: nabo.h:278
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to points during kd-tree construction
Definition: nabo_private.h:305
const CloudType & cloud
reference to data points used to compare
Definition: nabo_private.h:380
const cl_device_type deviceType
the type of device to run CL code on (CL_DEVICE_TYPE_CPU or CL_DEVICE_TYPE_GPU)
Definition: nabo_private.h:236
T cutVal
for split node, split value
Definition: nabo_private.h:143
size_t parent(size_t pos) const
Return the parent of pos.
Definition: nabo_private.h:405
KDTree, balanced, points in nodes, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:348
cl::Buffer nodesCL
CL buffer for search nodes.
Definition: nabo_private.h:400
std::vector< Index > BuildPoints
indices of points during kd-tree construction
Definition: nabo_private.h:111
std::vector< BucketEntry > Buckets
bucket data
Definition: nabo_private.h:171
BuildPoints::iterator BuildPointsIt
iterator to indices of points during kd-tree construction
Definition: nabo_private.h:113
Nodes nodes
search nodes
Definition: nabo_private.h:328
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to points during kd-tree construction
Definition: nabo_private.h:375
Nearest neighbour search interface, templatized on scalar type.
Definition: nabo.h:258
cl::Buffer nodesCL
CL buffer for search nodes.
Definition: nabo_private.h:329
Node(const uint32_t bucketSize, const uint32_t bucketIndex)
construct a leaf node
Definition: nabo_private.h:151
BuildPoints::iterator BuildPointsIt
iterator to points during kd-tree construction
Definition: nabo_private.h:303
T cutVal
value of the cut
Definition: nabo_private.h:321
std::vector< Node > Nodes
dense vector of search nodes
Definition: nabo_private.h:397
const CloudType & cloud
the reference to the data-point cloud, which must remain valid during the lifetime of the NearestNeig...
Definition: nabo.h:274
cl::CommandQueue queue
the command queue
Definition: nabo_private.h:239
Nodes nodes
search nodes
Definition: nabo_private.h:174
KDTree, balanced, points in leaves, stack, implicit bounds, balance aspect ratio. ...
Definition: nabo_private.h:258
uint32_t getDim(const uint32_t dimChildBucketSize) const
get the dimension out of the compound index
Definition: nabo_private.h:129
size_t dim
dimension on which to compare
Definition: nabo_private.h:381
int dim
dimension of the cut, or, if -1 == leaf, -2 == invalid
Definition: nabo_private.h:391
std::vector< Node > Nodes
dense vector of search nodes
Definition: nabo_private.h:326
Vector pos
point
Definition: nabo_private.h:295
const uint32_t dimMask
mask to access dim
Definition: nabo_private.h:123
cl::Context & context
the CL context
Definition: nabo_private.h:237
size_t childRight(size_t pos) const
Return the right child of pos.
Definition: nabo_private.h:404
Functor to compare point values on a given dimension.
Definition: nabo_private.h:308
size_t dim
dimension on which to compare
Definition: nabo_private.h:310
Brute-force nearest neighbour.
Definition: nabo_private.h:72
Parameter vector.
Definition: nabo.h:231
Node(const uint32_t dimChild, const T cutVal)
construct a split node
Definition: nabo_private.h:148
size_t childRight(size_t pos) const
Return the right child of pos.
Definition: nabo_private.h:333
uint32_t getChildBucketSize(const uint32_t dimChildBucketSize) const
get the child index or the bucket size out of the coumpount index
Definition: nabo_private.h:132
size_t parent(size_t pos) const
Return the parent of pos.
Definition: nabo_private.h:334
size_t childLeft(size_t pos) const
Return the left child of pos.
Definition: nabo_private.h:332
Point during kd-tree construction.
Definition: nabo_private.h:293
const unsigned bucketSize
size of bucket
Definition: nabo_private.h:118
Namespace for Nabo.
Definition: brute_force_cpu.cpp:40
BucketEntry(const T *pt=0, const Index index=0)
create a new bucket entry for a point in the data
Definition: nabo_private.h:167
std::vector< BuildPoint > BuildPoints
points during kd-tree construction
Definition: nabo_private.h:301
Functor to compare point values on a given dimension.
Definition: nabo_private.h:378
const Index dim
the dimensionality of the data-point cloud
Definition: nabo.h:276
KDTree, balanced, points in leaves, stack, implicit bounds, balance aspect ratio. ...
Definition: nabo_private.h:272
Tree node for CL.
Definition: nabo_private.h:389
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to indices of points during kd-tree construction
Definition: nabo_private.h:115
T dist2(const A &v0, const B &v1)
Euclidean distance.
Definition: nabo_private.h:65
uint32_t bucketIndex
for leaf node, pointer to bucket
Definition: nabo_private.h:144
Buckets buckets
buckets
Definition: nabo_private.h:177
uint32_t dimChildBucketSize
cut dimension for split nodes (dimBitCount lsb), index of right node or number of bucket(rest)...
Definition: nabo_private.h:140
cl::Buffer cloudCL
the buffer for the input data
Definition: nabo_private.h:240
size_t childLeft(size_t pos) const
Return the left child of pos.
Definition: nabo_private.h:403
entry in a bucket
Definition: nabo_private.h:158
Tree node for CL.
Definition: nabo_private.h:318
int dim
dimension of the cut, or, if negative, index of the point: -1 == invalid, <= -2 = index of pt ...
Definition: nabo_private.h:320
BruteForceSearch(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags)
constructor, calls NearestNeighbourSearch<T>(cloud)
Definition: brute_force_cpu.cpp:45
CloudType CloudType
a column-major Eigen matrix in which each column is a point; this matrix has dim rows ...
Definition: nabo.h:265
Nodes nodes
search nodes
Definition: nabo_private.h:399
const T * pt
pointer to first value of point data, 0 if end of bucket
Definition: nabo_private.h:160
const uint32_t dimBitCount
number of bits required to store dimension index + number of dimensions
Definition: nabo_private.h:121
BuildPoints::iterator BuildPointsIt
iterator to points during kd-tree construction
Definition: nabo_private.h:373
search node
Definition: nabo_private.h:138
cl::Kernel knnKernel
the kernel to perform knnSearch, mutable because it is stateful, but conceptually const ...
Definition: nabo_private.h:238