Point Cloud Library (PCL)  1.12.1-dev
octree.hpp
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2011, Willow Garage, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above
14  * copyright notice, this list of conditions and the following
15  * disclaimer in the documentation and/or other materials provided
16  * with the distribution.
17  * * Neither the name of Willow Garage, Inc. nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Author: Anatoly Baskeheev, Itseez Ltd, (myname.mysurname@mycompany.com)
35  */
36 
37 #ifndef _PCL_GPU_OCTREE_
38 #define _PCL_GPU_OCTREE_
39 
40 #include <limits>
41 #include <vector>
42 
43 #include <pcl/memory.h>
44 #include <pcl/point_types.h>
45 #include <pcl/pcl_macros.h>
46 #include <pcl/gpu/containers/device_array.h>
47 #include <pcl/gpu/octree/device_format.hpp>
48 
49 namespace pcl
50 {
51  namespace gpu
52  {
53  /**
54  * \brief Octree implementation on GPU. It suppors parallel building and parallel batch search as well .
55  * \author Anaoly Baksheev, Itseez, myname.mysurname@mycompany.com
56  */
57 
59  {
60  public:
61 
62  /** \brief Default constructor.*/
63  Octree();
64 
65  /** \brief Denstructor.*/
66  virtual ~Octree();
67 
68  /** \brief Types */
69  using Ptr = shared_ptr<Octree>;
70  using ConstPtr = shared_ptr<const Octree>;
71 
72  /** \brief Point typwe supported */
74 
75  /** \brief Point cloud supported */
77 
78  /** \brief Point Batch query cloud type */
80 
81  /** \brief Point Radiuses for batch query */
83 
84  /** \brief Point Indices for batch query */
86 
87  /** \brief Point Sqrt distances array type */
89 
91 
92  /** \brief Sets cloud for which octree is built */
93  void setCloud(const PointCloud& cloud_arg);
94 
95  /** \brief Performs parallel octree building */
96  void build();
97 
98  /** \brief Returns true if tree has been built */
99  bool isBuilt() const;
100 
101  /** \brief Downloads Octree from GPU to search using CPU function. It use useful for single (not-batch) search */
103 
104  /** \brief Performs search of all points within given radius on CPU. It call \a internalDownload if necessary
105  * \param[in] center center of sphere
106  * \param[in] radius radious of sphere
107  * \param[out] out indeces of points within give sphere
108  * \param[in] max_nn maximum numver of results returned
109  */
110  void radiusSearchHost(const PointType& center, float radius, std::vector<int>& out,
111  int max_nn = std::numeric_limits<int>::max());
112 
113  /** \brief Performs approximate nearest neighbor search on CPU. It call \a internalDownload if necessary
114  * \param[in] query 3D point for which neighbour is be fetched
115  * \param[out] out_index neighbour index
116  * \param[out] sqr_dist square distance to the neighbour returned
117  */
118  void approxNearestSearchHost(const PointType& query, int& out_index, float& sqr_dist);
119 
120  /** \brief Performs batch radius search on GPU
121  * \param[in] centers array of centers
122  * \param[in] radius radius for all queries
123  * \param[in] max_results max number of returned points for each querey
124  * \param[out] result results packed to single array
125  */
126  void radiusSearch(const Queries& centers, float radius, int max_results, NeighborIndices& result) const;
127 
128  /** \brief Performs batch radius search on GPU
129  * \param[in] centers array of centers
130  * \param[in] radiuses array of radiuses
131  * \param[in] max_results max number of returned points for each querey
132  * \param[out] result results packed to single array
133  */
134  void radiusSearch(const Queries& centers, const Radiuses& radiuses, int max_results, NeighborIndices& result) const;
135 
136  /** \brief Performs batch radius search on GPU
137  * \param[in] centers array of centers
138  * \param[in] indices indices for centers array (only for these points search is performed)
139  * \param[in] radius radius for all queries
140  * \param[in] max_results max number of returned points for each querey
141  * \param[out] result results packed to single array
142  */
143  void radiusSearch(const Queries& centers, const Indices& indices, float radius, int max_results, NeighborIndices& result) const;
144 
145  /** \brief Batch approximate nearest search on GPU
146  * \param[in] queries array of centers
147  * \param[out] result array of results ( one index for each query )
148  */
149  PCL_DEPRECATED(1, 14, "use approxNearestSearch() which returns square distances instead")
150  void approxNearestSearch(const Queries& queries, NeighborIndices& result) const;
151 
152  /** \brief Batch approximate nearest search on GPU
153  * \param[in] queries array of centers
154  * \param[out] result array of results ( one index for each query )
155  * \param[out] sqr_distance corresponding square distances to results from query point
156  */
157  void approxNearestSearch(const Queries& queries, NeighborIndices& result, ResultSqrDists& sqr_distance) const;
158 
159  /** \brief Batch exact k-nearest search on GPU for k == 1 only!
160  * \param[in] queries array of centers
161  * \param[in] k number of neighbors (only k == 1 is supported)
162  * \param[out] results array of results
163  */
164  void nearestKSearchBatch(const Queries& queries, int k, NeighborIndices& results) const;
165 
166  /** \brief Batch exact k-nearest search on GPU for k == 1 only!
167  * \param[in] queries array of centers
168  * \param[in] k number of neighbors (only k == 1 is supported)
169  * \param[out] results array of results
170  * \param[out] sqr_distances square distances to results
171  */
172  void nearestKSearchBatch(const Queries& queries, int k, NeighborIndices& results, ResultSqrDists& sqr_distances) const;
173 
174  /** \brief Desroys octree and release all resources */
175  void clear();
176  private:
177  void *impl;
178  bool built_;
179  };
180 
181  /** \brief Performs brute force radius search on GPU
182  * \param[in] cloud cloud where to search
183  * \param[in] query query point
184  * \param[in] radius radius
185  * \param[out] result indeces of points within give sphere
186  * \param[in] buffer buffer for intermediate results. Keep reference to it between calls to eliminate internal allocations
187  */
188  PCL_EXPORTS void bruteForceRadiusSearchGPU(const Octree::PointCloud& cloud, const Octree::PointType& query, float radius, DeviceArray<int>& result, DeviceArray<int>& buffer);
189  }
190 }
191 
192 #endif /* _PCL_GPU_OCTREE_ */
PointCloud represents the base class in PCL for storing collections of 3D points.
Definition: point_cloud.h:173
Octree implementation on GPU.
Definition: octree.hpp:59
bool isBuilt() const
Returns true if tree has been built.
void radiusSearchHost(const PointType &center, float radius, std::vector< int > &out, int max_nn=std::numeric_limits< int >::max())
Performs search of all points within given radius on CPU.
shared_ptr< Octree > Ptr
Types.
Definition: octree.hpp:69
virtual ~Octree()
Denstructor.
void internalDownload()
Downloads Octree from GPU to search using CPU function.
void setCloud(const PointCloud &cloud_arg)
Sets cloud for which octree is built.
shared_ptr< const Octree > ConstPtr
Definition: octree.hpp:70
void radiusSearch(const Queries &centers, const Indices &indices, float radius, int max_results, NeighborIndices &result) const
Performs batch radius search on GPU.
Octree()
Default constructor.
const PointCloud * cloud_
Definition: octree.hpp:90
void approxNearestSearchHost(const PointType &query, int &out_index, float &sqr_dist)
Performs approximate nearest neighbor search on CPU.
void radiusSearch(const Queries &centers, const Radiuses &radiuses, int max_results, NeighborIndices &result) const
Performs batch radius search on GPU.
void build()
Performs parallel octree building.
void radiusSearch(const Queries &centers, float radius, int max_results, NeighborIndices &result) const
Performs batch radius search on GPU.
Defines all the PCL implemented PointT point type structures.
Defines functions, macros and traits for allocating and using memory.
PCL_EXPORTS void bruteForceRadiusSearchGPU(const Octree::PointCloud &cloud, const Octree::PointType &query, float radius, DeviceArray< int > &result, DeviceArray< int > &buffer)
Performs brute force radius search on GPU.
Defines all the PCL and non-PCL macros used.
#define PCL_EXPORTS
Definition: pcl_macros.h:323
#define PCL_DEPRECATED(Major, Minor, Message)
macro for compatibility across compilers and help remove old deprecated items for the Major....
Definition: pcl_macros.h:156
A point structure representing Euclidean xyz coordinates.