libnabo  1.0.7
nabo_private.h
Go to the documentation of this file.
1 /*
2 
3 Copyright (c) 2010--2011, Stephane Magnenat, ASL, ETHZ, Switzerland
4 You can contact the author at <stephane at magnenat dot net>
5 
6 All rights reserved.
7 
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are met:
10  * Redistributions of source code must retain the above copyright
11  notice, this list of conditions and the following disclaimer.
12  * Redistributions in binary form must reproduce the above copyright
13  notice, this list of conditions and the following disclaimer in the
14  documentation and/or other materials provided with the distribution.
15  * Neither the name of the <organization> nor the
16  names of its contributors may be used to endorse or promote products
17  derived from this software without specific prior written permission.
18 
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL ETH-ASL BE LIABLE FOR ANY
23 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30 */
31 
32 #ifndef __NABO_PRIVATE_H
33 #define __NABO_PRIVATE_H
34 
35 #include "nabo.h"
36 
37 #include <cstdint>
38 using std::uint32_t;
39 
40 // OpenCL
41 #ifdef HAVE_OPENCL
42  #define __CL_ENABLE_EXCEPTIONS
43  #include "CL/cl.hpp"
44 #endif // HAVE_OPENCL
45 
46 // Unused macro, add support for your favorite compiler
47 #if defined(__GNUC__)
48  #define _UNUSED __attribute__ ((unused))
49 #else
50  #define _UNUSED
51 #endif
52 
58 namespace Nabo
59 {
61 
62 
64  template<typename T, typename A, typename B>
65  inline T dist2(const A& v0, const B& v1)
66  {
67  return (v0 - v1).squaredNorm();
68  }
69 
71  template<typename T, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
72  struct BruteForceSearch : public NearestNeighbourSearch<T, CloudType>
73  {
74  typedef typename NearestNeighbourSearch<T, CloudType>::Vector Vector;
75  typedef typename NearestNeighbourSearch<T, CloudType>::Matrix Matrix;
76  typedef typename NearestNeighbourSearch<T, CloudType>::Index Index;
77  typedef typename NearestNeighbourSearch<T, CloudType>::IndexVector IndexVector;
78  typedef typename NearestNeighbourSearch<T, CloudType>::IndexMatrix IndexMatrix;
79 
85 
87  BruteForceSearch(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags);
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;
90  };
91 
93  template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
95  {
96  typedef typename NearestNeighbourSearch<T, CloudType>::Vector Vector;
97  typedef typename NearestNeighbourSearch<T, CloudType>::Matrix Matrix;
98  typedef typename NearestNeighbourSearch<T, CloudType>::Index Index;
99  typedef typename NearestNeighbourSearch<T, CloudType>::IndexVector IndexVector;
100  typedef typename NearestNeighbourSearch<T, CloudType>::IndexMatrix IndexMatrix;
101 
108 
109  protected:
111  typedef std::vector<Index> BuildPoints;
113  typedef typename BuildPoints::iterator BuildPointsIt;
115  typedef typename BuildPoints::const_iterator BuildPointsCstIt;
116 
118  const unsigned bucketSize;
119 
121  const uint32_t dimBitCount;
123  const uint32_t dimMask;
124 
126  inline uint32_t createDimChildBucketSize(const uint32_t dim, const uint32_t childIndex) const
127  { return dim | (childIndex << dimBitCount); }
129  inline uint32_t getDim(const uint32_t dimChildBucketSize) const
130  { return dimChildBucketSize & dimMask; }
132  inline uint32_t getChildBucketSize(const uint32_t dimChildBucketSize) const
133  { return dimChildBucketSize >> dimBitCount; }
134 
135  struct BucketEntry;
136 
138  struct Node
139  {
141  union
142  {
143  T cutVal;
144  uint32_t bucketIndex;
145  };
146 
148  Node(const uint32_t dimChild, const T cutVal):
149  dimChildBucketSize(dimChild), cutVal(cutVal) {}
151  Node(const uint32_t bucketSize, const uint32_t bucketIndex):
153  };
155  typedef std::vector<Node> Nodes;
156 
158  struct BucketEntry
159  {
160  const T* pt;
161  Index index;
162 
164 
167  BucketEntry(const T* pt = 0, const Index index = 0): pt(pt), index(index) {}
168  };
169 
171  typedef std::vector<BucketEntry> Buckets;
172 
175 
178 
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);
183 
185 
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;
198 
200 
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;
210 
211  public:
213  KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags, const Parameters& additionalParameters);
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;
216  };
217 
218  #ifdef HAVE_OPENCL
219 
221  template<typename T, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
222  struct OpenCLSearch: public NearestNeighbourSearch<T, CloudType>
223  {
224  typedef typename NearestNeighbourSearch<T, CloudType>::Vector Vector;
225  typedef typename NearestNeighbourSearch<T, CloudType>::Matrix Matrix;
226  typedef typename NearestNeighbourSearch<T, CloudType>::Index Index;
227  typedef typename NearestNeighbourSearch<T, CloudType>::IndexVector IndexVector;
228  typedef typename NearestNeighbourSearch<T, CloudType>::IndexMatrix IndexMatrix;
229 
234 
235  protected:
236  const cl_device_type deviceType;
237  cl::Context& context;
238  mutable cl::Kernel knnKernel;
239  cl::CommandQueue queue;
240  cl::Buffer cloudCL;
241 
243  OpenCLSearch(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType);
245 
249  void initOpenCL(const char* clFileName, const char* kernelName, const std::string& additionalDefines = "");
250 
251  public:
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;
254  };
255 
257  template<typename T, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
258  struct BruteForceSearchOpenCL: public OpenCLSearch<T, CloudType>
259  {
260  typedef typename NearestNeighbourSearch<T, CloudType>::Vector Vector;
261  typedef typename NearestNeighbourSearch<T, CloudType>::Matrix Matrix;
262  typedef typename NearestNeighbourSearch<T, CloudType>::Index Index;
263 
265 
267  BruteForceSearchOpenCL(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType);
268  };
269 
271  template<typename T, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
273  {
274  typedef typename NearestNeighbourSearch<T, CloudType>::Vector Vector;
275  typedef typename NearestNeighbourSearch<T, CloudType>::Matrix Matrix;
276  typedef typename NearestNeighbourSearch<T, CloudType>::Index Index;
277  typedef typename NearestNeighbourSearch<T, CloudType>::IndexVector IndexVector;
278  typedef typename NearestNeighbourSearch<T, CloudType>::IndexMatrix IndexMatrix;
279 
285 
288 
290 
291  protected:
293  struct BuildPoint
294  {
295  Vector pos;
296  size_t index;
297  BuildPoint(const Vector& pos = Vector(), const size_t index = 0): pos(pos), index(index) {}
299  };
301  typedef std::vector<BuildPoint> BuildPoints;
303  typedef typename BuildPoints::iterator BuildPointsIt;
305  typedef typename BuildPoints::const_iterator BuildPointsCstIt;
306 
308  struct CompareDim
309  {
310  size_t dim;
311  CompareDim(const size_t dim):dim(dim){}
314  bool operator() (const BuildPoint& p0, const BuildPoint& p1) { return p0.pos(dim) < p1.pos(dim); }
315  };
316 
318  struct Node
319  {
320  int dim;
321  T cutVal;
322  Node(const int dim = -1, const T cutVal = 0):dim(dim), cutVal(cutVal) {}
324  };
326  typedef std::vector<Node> Nodes;
327 
329  cl::Buffer nodesCL;
330 
331 
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;
337 
339  void buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos, const Vector minValues, const Vector maxValues);
340 
341  public:
343  KDTreeBalancedPtInLeavesStackOpenCL(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType);
344  };
345 
347  template<typename T, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> >
349  {
350  typedef typename NearestNeighbourSearch<T, CloudType>::Vector Vector;
351  typedef typename NearestNeighbourSearch<T, CloudType>::Matrix Matrix;
352  typedef typename NearestNeighbourSearch<T, CloudType>::Index Index;
353  typedef typename NearestNeighbourSearch<T, CloudType>::IndexVector IndexVector;
354  typedef typename NearestNeighbourSearch<T, CloudType>::IndexMatrix IndexMatrix;
355 
361 
364 
366 
367  protected:
369  typedef Index BuildPoint;
371  typedef std::vector<BuildPoint> BuildPoints;
373  typedef typename BuildPoints::iterator BuildPointsIt;
375  typedef typename BuildPoints::const_iterator BuildPointsCstIt;
376 
378  struct CompareDim
379  {
380  const CloudType& cloud;
381  size_t dim;
382  CompareDim(const CloudType& cloud, const size_t dim): cloud(cloud), dim(dim){}
385  bool operator() (const BuildPoint& p0, const BuildPoint& p1) { return cloud.coeff(dim, p0) < cloud.coeff(dim, p1); }
386  };
387 
389  struct Node
390  {
391  int dim;
392  Index index;
393  Node(const int dim = -2, const Index index = 0):dim(dim), index(index) {}
395  };
397  typedef std::vector<Node> Nodes;
398 
400  cl::Buffer nodesCL;
401 
402 
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;
408 
410  void buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos, const Vector minValues, const Vector maxValues);
411 
412  public:
414  KDTreeBalancedPtInNodesStackOpenCL(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags, const cl_device_type deviceType);
415  };
416 
417  #endif // HAVE_OPENCL
418 
420 }
421 
422 #endif // __NABO_H
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPoints
std::vector< BuildPoint > BuildPoints
points during kd-tree construction
Definition: nabo_private.h:301
Nabo::BruteForceSearchOpenCL::BruteForceSearchOpenCL
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
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::nodes
Nodes nodes
search nodes
Definition: nabo_private.h:328
Nabo::KDTreeBalancedPtInNodesStackOpenCL
KDTree, balanced, points in nodes, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:348
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BuildPointsCstIt
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to indices of points during kd-tree construction
Definition: nabo_private.h:115
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::getTreeSize
size_t getTreeSize(size_t size) const
Return the storage size of tree of a given size.
Definition: kdtree_opencl.cpp:440
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::cutVal
T cutVal
for split node, split value
Definition: nabo_private.h:143
Nabo
Namespace for Nabo.
Definition: brute_force_cpu.cpp:40
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::dim
const Index dim
the dimensionality of the data-point cloud
Definition: nabo.h:276
Nabo::Parameters
Parameter vector.
Definition: nabo.h:231
Nabo::OpenCLSearch::deviceType
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
Nabo::KDTreeBalancedPtInNodesStackOpenCL::CompareDim::dim
size_t dim
dimension on which to compare
Definition: nabo_private.h:381
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::Node::dim
int dim
dimension of the cut, or, if negative, index of the point: -1 == invalid, <= -2 = index of pt
Definition: nabo_private.h:320
nabo.h
public interface
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry::BucketEntry
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
Nabo::OpenCLSearch
OpenCL support for nearest neighbour search
Definition: nabo_private.h:222
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node
search node
Definition: nabo_private.h:138
Nabo::KDTreeBalancedPtInNodesStackOpenCL::Node::dim
int dim
dimension of the cut, or, if -1 == leaf, -2 == invalid
Definition: nabo_private.h:391
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Nodes
std::vector< Node > Nodes
dense vector of search nodes, provides better memory performances than many small objects
Definition: nabo_private.h:155
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt
KDTree, unbalanced, points in leaves, stack, implicit bounds, ANN_KD_SL_MIDPT, optimised implementati...
Definition: nabo_private.h:94
Nabo::OpenCLSearch::queue
cl::CommandQueue queue
the command queue
Definition: nabo_private.h:239
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::CompareDim::dim
size_t dim
dimension on which to compare
Definition: nabo_private.h:310
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::Node
Node(const uint32_t bucketSize, const uint32_t bucketIndex)
construct a leaf node
Definition: nabo_private.h:151
Nabo::KDTreeBalancedPtInLeavesStackOpenCL
KDTree, balanced, points in leaves, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:272
Nabo::KDTreeBalancedPtInNodesStackOpenCL::CompareDim::operator()
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
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::CompareDim::operator()
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
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::nodes
Nodes nodes
search nodes
Definition: nabo_private.h:174
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::dimBitCount
const uint32_t dimBitCount
number of bits required to store dimension index + number of dimensions
Definition: nabo_private.h:121
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::CompareDim
Functor to compare point values on a given dimension.
Definition: nabo_private.h:308
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt
KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const Parameters &additionalParameters)
constructor, calls NearestNeighbourSearch<T>(cloud)
Definition: kdtree_cpu.cpp:228
Nabo::KDTreeBalancedPtInNodesStackOpenCL::getTreeDepth
size_t getTreeDepth(size_t size) const
Return the max depth of a tree of a given size.
Definition: kdtree_opencl.cpp:581
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::CompareDim::CompareDim
CompareDim(const size_t dim)
Build the functor for a specific dimension.
Definition: nabo_private.h:312
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::cloud
const CloudType & cloud
the reference to the data-point cloud, which must remain valid during the lifetime of the NearestNeig...
Definition: nabo.h:274
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::CloudType
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
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::creationOptionFlags
const unsigned creationOptionFlags
creation options
Definition: nabo.h:278
Nabo::KDTreeBalancedPtInNodesStackOpenCL::nodes
Nodes nodes
search nodes
Definition: nabo_private.h:399
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::IndexMatrix
Eigen::Matrix< Index, Eigen::Dynamic, Eigen::Dynamic > IndexMatrix
a matrix of indices to data points
Definition: nabo.h:271
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry::pt
const T * pt
pointer to first value of point data, 0 if end of bucket
Definition: nabo_private.h:160
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BuildPoints
std::vector< Index > BuildPoints
indices of points during kd-tree construction
Definition: nabo_private.h:111
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::Matrix
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
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::createDimChildBucketSize
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
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry::index
Index index
index of point
Definition: nabo_private.h:161
Nabo::KDTreeBalancedPtInNodesStackOpenCL::Node::Node
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
Nabo::KDTreeBalancedPtInNodesStackOpenCL::BuildPointsIt
BuildPoints::iterator BuildPointsIt
iterator to points during kd-tree construction
Definition: nabo_private.h:373
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::onePointKnn
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
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPointsIt
BuildPoints::iterator BuildPointsIt
iterator to points during kd-tree construction
Definition: nabo_private.h:303
Nabo::KDTreeBalancedPtInNodesStackOpenCL::CompareDim::cloud
const CloudType & cloud
reference to data points used to compare
Definition: nabo_private.h:380
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::getTreeDepth
size_t getTreeDepth(size_t size) const
Return the max depth of a tree of a given size.
Definition: kdtree_opencl.cpp:460
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::Nodes
std::vector< Node > Nodes
dense vector of search nodes
Definition: nabo_private.h:326
Nabo::KDTreeBalancedPtInNodesStackOpenCL::BuildPoints
std::vector< BuildPoint > BuildPoints
points during kd-tree construction
Definition: nabo_private.h:371
Nabo::NearestNeighbourSearch
Nearest neighbour search interface, templatized on scalar type.
Definition: nabo.h:258
Nabo::OpenCLSearch::cloudCL
cl::Buffer cloudCL
the buffer for the input data
Definition: nabo_private.h:240
Nabo::OpenCLSearch::context
cl::Context & context
the CL context
Definition: nabo_private.h:237
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry
entry in a bucket
Definition: nabo_private.h:158
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::nodesCL
cl::Buffer nodesCL
CL buffer for search nodes.
Definition: nabo_private.h:329
Nabo::KDTreeBalancedPtInNodesStackOpenCL::Node::index
Index index
index of the point to cut
Definition: nabo_private.h:392
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::recurseKnn
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
Nabo::OpenCLSearch::initOpenCL
void initOpenCL(const char *clFileName, const char *kernelName, const std::string &additionalDefines="")
Initialize CL support.
Definition: kdtree_opencl.cpp:239
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::dimMask
const uint32_t dimMask
mask to access dim
Definition: nabo_private.h:123
Nabo::KDTreeBalancedPtInNodesStackOpenCL::buildNodes
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
Nabo::dist2
T dist2(const A &v0, const B &v1)
Euclidean distance.
Definition: nabo_private.h:65
Nabo::KDTreeBalancedPtInNodesStackOpenCL::CompareDim::CompareDim
CompareDim(const CloudType &cloud, const size_t dim)
Build the functor for a specific dimension on a specific cloud.
Definition: nabo_private.h:383
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Buckets
std::vector< BucketEntry > Buckets
bucket data
Definition: nabo_private.h:171
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::Node
Node(const uint32_t dimChild, const T cutVal)
construct a split node
Definition: nabo_private.h:148
Nabo::KDTreeBalancedPtInNodesStackOpenCL::Nodes
std::vector< Node > Nodes
dense vector of search nodes
Definition: nabo_private.h:397
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::Vector
Eigen::Matrix< T, Eigen::Dynamic, 1 > Vector
an Eigen vector of type T, to hold the coordinates of a point
Definition: nabo.h:261
Nabo::KDTreeBalancedPtInNodesStackOpenCL::BuildPoint
Index BuildPoint
a point during kd-tree construction is just its index
Definition: nabo_private.h:369
Nabo::OpenCLSearch::OpenCLSearch
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
Nabo::KDTreeBalancedPtInNodesStackOpenCL::Node
Tree node for CL.
Definition: nabo_private.h:389
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPoint
Point during kd-tree construction.
Definition: nabo_private.h:293
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::getDim
uint32_t getDim(const uint32_t dimChildBucketSize) const
get the dimension out of the compound index
Definition: nabo_private.h:129
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPoint::BuildPoint
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
Nabo::OpenCLSearch::knnKernel
cl::Kernel knnKernel
the kernel to perform knnSearch, mutable because it is stateful, but conceptually const
Definition: nabo_private.h:238
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::getChildBucketSize
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
Nabo::KDTreeBalancedPtInNodesStackOpenCL::KDTreeBalancedPtInNodesStackOpenCL
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
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::KDTreeBalancedPtInLeavesStackOpenCL
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
Nabo::KDTreeBalancedPtInNodesStackOpenCL::CompareDim
Functor to compare point values on a given dimension.
Definition: nabo_private.h:378
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::bucketSize
const unsigned bucketSize
size of bucket
Definition: nabo_private.h:118
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::buildNodes
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
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::Index
int Index
an index to a Vector or a Matrix, for refering to data points
Definition: nabo.h:267
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::dimChildBucketSize
uint32_t dimChildBucketSize
cut dimension for split nodes (dimBitCount lsb), index of right node or number of bucket(rest)....
Definition: nabo_private.h:140
Nabo::KDTreeBalancedPtInNodesStackOpenCL::getTreeSize
size_t getTreeSize(size_t size) const
Return the storage size of tree of a given size.
Definition: kdtree_opencl.cpp:564
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BuildPointsIt
BuildPoints::iterator BuildPointsIt
iterator to indices of points during kd-tree construction
Definition: nabo_private.h:113
Nabo::KDTreeBalancedPtInNodesStackOpenCL::nodesCL
cl::Buffer nodesCL
CL buffer for search nodes.
Definition: nabo_private.h:400
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPoint::pos
Vector pos
point
Definition: nabo_private.h:295
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPoint::index
size_t index
index of point in cloud
Definition: nabo_private.h:296
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::buildNodes
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
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::bucketIndex
uint32_t bucketIndex
for leaf node, pointer to bucket
Definition: nabo_private.h:144
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::Node::cutVal
T cutVal
value of the cut
Definition: nabo_private.h:321
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::buckets
Buckets buckets
buckets
Definition: nabo_private.h:177
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::Node
Tree node for CL.
Definition: nabo_private.h:318
Nabo::KDTreeBalancedPtInNodesStackOpenCL::BuildPointsCstIt
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to points during kd-tree construction
Definition: nabo_private.h:375
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::Node::Node
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
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::getBounds
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
Nabo::BruteForceSearch
Brute-force nearest neighbour.
Definition: nabo_private.h:72
Nabo::BruteForceSearchOpenCL
KDTree, balanced, points in leaves, stack, implicit bounds, balance aspect ratio.
Definition: nabo_private.h:258
Nabo::BruteForceSearch::BruteForceSearch
BruteForceSearch(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags)
constructor, calls NearestNeighbourSearch<T>(cloud)
Definition: brute_force_cpu.cpp:45
Nabo::KDTreeBalancedPtInLeavesStackOpenCL::BuildPointsCstIt
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to points during kd-tree construction
Definition: nabo_private.h:305