Go to the documentation of this file.
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> >
129 inline uint32_t
getDim(
const uint32_t dimChildBucketSize)
const
130 {
return dimChildBucketSize &
dimMask; }
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> >
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; }
347 template<
typename T,
typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
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; }
417 #endif // HAVE_OPENCL
std::vector< BuildPoint > BuildPoints
points during kd-tree construction
Definition: nabo_private.h:301
BruteForceSearchOpenCL(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType)
constructor, calls OpenCLSearch<T, CloudType>(cloud, ...)
Definition: kdtree_opencl.cpp:411
Nodes nodes
search nodes
Definition: nabo_private.h:328
KDTree, balanced, points in nodes, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:348
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to indices of points during kd-tree construction
Definition: nabo_private.h:115
size_t getTreeSize(size_t size) const
Return the storage size of tree of a given size.
Definition: kdtree_opencl.cpp:440
T cutVal
for split node, split value
Definition: nabo_private.h:143
Namespace for Nabo.
Definition: brute_force_cpu.cpp:40
const Index dim
the dimensionality of the data-point cloud
Definition: nabo.h:276
Parameter vector.
Definition: nabo.h:231
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
size_t dim
dimension on which to compare
Definition: nabo_private.h:381
int dim
dimension of the cut, or, if negative, index of the point: -1 == invalid, <= -2 = index of pt
Definition: nabo_private.h:320
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
OpenCL support for nearest neighbour search
Definition: nabo_private.h:222
search node
Definition: nabo_private.h:138
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, provides better memory performances than many small objects
Definition: nabo_private.h:155
KDTree, unbalanced, points in leaves, stack, implicit bounds, ANN_KD_SL_MIDPT, optimised implementati...
Definition: nabo_private.h:94
cl::CommandQueue queue
the command queue
Definition: nabo_private.h:239
size_t dim
dimension on which to compare
Definition: nabo_private.h:310
Node(const uint32_t bucketSize, const uint32_t bucketIndex)
construct a leaf node
Definition: nabo_private.h:151
KDTree, balanced, points in leaves, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:272
bool operator()(const BuildPoint &p0, const BuildPoint &p1)
Compare the values of p0 and p1 on dim, and return whether p0[dim] < p1[dim].
Definition: nabo_private.h:385
bool operator()(const BuildPoint &p0, const BuildPoint &p1)
Compare the values of p0 and p1 on dim, and return whether p0[dim] < p1[dim].
Definition: nabo_private.h:314
Nodes nodes
search nodes
Definition: nabo_private.h:174
const uint32_t dimBitCount
number of bits required to store dimension index + number of dimensions
Definition: nabo_private.h:121
Functor to compare point values on a given dimension.
Definition: nabo_private.h:308
KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const Parameters &additionalParameters)
constructor, calls NearestNeighbourSearch<T>(cloud)
Definition: kdtree_cpu.cpp:228
size_t getTreeDepth(size_t size) const
Return the max depth of a tree of a given size.
Definition: kdtree_opencl.cpp:581
CompareDim(const size_t dim)
Build the functor for a specific dimension.
Definition: nabo_private.h:312
const CloudType & cloud
the reference to the data-point cloud, which must remain valid during the lifetime of the NearestNeig...
Definition: nabo.h:274
Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > CloudType
a column-major Eigen matrix in which each column is a point; this matrix has dim rows
Definition: nabo.h:265
const unsigned creationOptionFlags
creation options
Definition: nabo.h:278
Nodes nodes
search nodes
Definition: nabo_private.h:399
Eigen::Matrix< Index, Eigen::Dynamic, Eigen::Dynamic > IndexMatrix
a matrix of indices to data points
Definition: nabo.h:271
const T * pt
pointer to first value of point data, 0 if end of bucket
Definition: nabo_private.h:160
std::vector< Index > BuildPoints
indices of points during kd-tree construction
Definition: nabo_private.h:111
Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > Matrix
a column-major Eigen matrix in which each column is a point; this matrix has dim rows
Definition: nabo.h:263
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 point
Definition: nabo_private.h:161
Node(const int dim=-2, const Index index=0)
Build a tree node, with a given index and a given dimension to cut on.
Definition: nabo_private.h:394
BuildPoints::iterator BuildPointsIt
iterator to points during kd-tree construction
Definition: nabo_private.h:373
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
search one point, call recurseKnn with the correct template parameters
Definition: kdtree_cpu.cpp:339
BuildPoints::iterator BuildPointsIt
iterator to points during kd-tree construction
Definition: nabo_private.h:303
const CloudType & cloud
reference to data points used to compare
Definition: nabo_private.h:380
size_t getTreeDepth(size_t size) const
Return the max depth of a tree of a given size.
Definition: kdtree_opencl.cpp:460
std::vector< Node > Nodes
dense vector of search nodes
Definition: nabo_private.h:326
std::vector< BuildPoint > BuildPoints
points during kd-tree construction
Definition: nabo_private.h:371
Nearest neighbour search interface, templatized on scalar type.
Definition: nabo.h:258
cl::Buffer cloudCL
the buffer for the input data
Definition: nabo_private.h:240
cl::Context & context
the CL context
Definition: nabo_private.h:237
entry in a bucket
Definition: nabo_private.h:158
cl::Buffer nodesCL
CL buffer for search nodes.
Definition: nabo_private.h:329
Index index
index of the point to cut
Definition: nabo_private.h:392
unsigned long recurseKnn(const T *query, const unsigned n, T rd, Heap &heap, std::vector< T > &off, const T maxError, const T maxRadius2) const
recursive search, strongly inspired by ANN and [Arya & Mount, Algorithms for fast vector quantization...
Definition: kdtree_cpu.cpp:368
void initOpenCL(const char *clFileName, const char *kernelName, const std::string &additionalDefines="")
Initialize CL support.
Definition: kdtree_opencl.cpp:239
const uint32_t dimMask
mask to access dim
Definition: nabo_private.h:123
void buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos, const Vector minValues, const Vector maxValues)
Recurse to build nodes.
Definition: kdtree_opencl.cpp:594
T dist2(const A &v0, const B &v1)
Euclidean distance.
Definition: nabo_private.h:65
CompareDim(const CloudType &cloud, const size_t dim)
Build the functor for a specific dimension on a specific cloud.
Definition: nabo_private.h:383
std::vector< BucketEntry > Buckets
bucket data
Definition: nabo_private.h:171
Node(const uint32_t dimChild, const T cutVal)
construct a split node
Definition: nabo_private.h:148
std::vector< Node > Nodes
dense vector of search nodes
Definition: nabo_private.h:397
Eigen::Matrix< T, Eigen::Dynamic, 1 > Vector
an Eigen vector of type T, to hold the coordinates of a point
Definition: nabo.h:261
Index BuildPoint
a point during kd-tree construction is just its index
Definition: nabo_private.h:369
OpenCLSearch(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType)
constructor, calls NearestNeighbourSearch<T, CloudType>(cloud)
Definition: kdtree_opencl.cpp:231
Tree node for CL.
Definition: nabo_private.h:389
Point during kd-tree construction.
Definition: nabo_private.h:293
uint32_t getDim(const uint32_t dimChildBucketSize) const
get the dimension out of the compound index
Definition: nabo_private.h:129
BuildPoint(const Vector &pos=Vector(), const size_t index=0)
Construct a build point, at a given pos with a specific index.
Definition: nabo_private.h:298
cl::Kernel knnKernel
the kernel to perform knnSearch, mutable because it is stateful, but conceptually const
Definition: nabo_private.h:238
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
KDTreeBalancedPtInNodesStackOpenCL(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType)
constructor, calls OpenCLSearch<T, CloudType>(cloud, ...)
Definition: kdtree_opencl.cpp:644
KDTreeBalancedPtInLeavesStackOpenCL(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType)
constructor, calls OpenCLSearch<T, CloudType>(cloud, ...)
Definition: kdtree_opencl.cpp:517
Functor to compare point values on a given dimension.
Definition: nabo_private.h:378
const unsigned bucketSize
size of bucket
Definition: nabo_private.h:118
unsigned buildNodes(const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
construct nodes for points [first..last[ inside the hyperrectangle [minValues..maxValues]
Definition: kdtree_cpu.cpp:110
int Index
an index to a Vector or a Matrix, for refering to data points
Definition: nabo.h:267
uint32_t dimChildBucketSize
cut dimension for split nodes (dimBitCount lsb), index of right node or number of bucket(rest)....
Definition: nabo_private.h:140
size_t getTreeSize(size_t size) const
Return the storage size of tree of a given size.
Definition: kdtree_opencl.cpp:564
BuildPoints::iterator BuildPointsIt
iterator to indices of points during kd-tree construction
Definition: nabo_private.h:113
cl::Buffer nodesCL
CL buffer for search nodes.
Definition: nabo_private.h:400
Vector pos
point
Definition: nabo_private.h:295
size_t index
index of point in cloud
Definition: nabo_private.h:296
void buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos, const Vector minValues, const Vector maxValues)
Recurse to build nodes.
Definition: kdtree_opencl.cpp:475
uint32_t bucketIndex
for leaf node, pointer to bucket
Definition: nabo_private.h:144
T cutVal
value of the cut
Definition: nabo_private.h:321
Buckets buckets
buckets
Definition: nabo_private.h:177
Tree node for CL.
Definition: nabo_private.h:318
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to points during kd-tree construction
Definition: nabo_private.h:375
Node(const int dim=-1, const T cutVal=0)
Build a tree node, with a given dimension and value to cut on, or, if leaf and dim <= -2,...
Definition: nabo_private.h:323
std::pair< T, T > getBounds(const BuildPointsIt first, const BuildPointsIt last, const unsigned dim)
return the bounds of points from [first..last[ on dimension dim
Definition: kdtree_cpu.cpp:94
Brute-force nearest neighbour.
Definition: nabo_private.h:72
KDTree, balanced, points in leaves, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:258
BruteForceSearch(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags)
constructor, calls NearestNeighbourSearch<T>(cloud)
Definition: brute_force_cpu.cpp:45
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to points during kd-tree construction
Definition: nabo_private.h:305