Point Cloud Library (PCL)  1.14.1
organized_fast_mesh.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2011, Dirk Holz, University of Bonn.
6  * Copyright (c) 2010-2011, Willow Garage, Inc.
7  *
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  *
14  * * Redistributions of source code must retain the above copyright
15  * notice, this list of conditions and the following disclaimer.
16  * * Redistributions in binary form must reproduce the above
17  * copyright notice, this list of conditions and the following
18  * disclaimer in the documentation and/or other materials provided
19  * with the distribution.
20  * * Neither the name of Willow Garage, Inc. nor the names of its
21  * contributors may be used to endorse or promote products derived
22  * from this software without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
30  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35  * POSSIBILITY OF SUCH DAMAGE.
36  *
37  * $Id$
38  *
39  */
40 
41 #pragma once
42 
43 #include <pcl/common/angles.h>
44 #include <pcl/common/point_tests.h> // for pcl::isFinite
45 #include <pcl/surface/reconstruction.h>
46 
47 
48 namespace pcl
49 {
50 
51  /** \brief Simple triangulation/surface reconstruction for organized point
52  * clouds. Neighboring points (pixels in image space) are connected to
53  * construct a triangular (or quad) mesh.
54  *
55  * \note If you use this code in any academic work, please cite:
56  * D. Holz and S. Behnke.
57  * Fast Range Image Segmentation and Smoothing using Approximate Surface Reconstruction and Region Growing.
58  * In Proceedings of the 12th International Conference on Intelligent Autonomous Systems (IAS),
59  * Jeju Island, Korea, June 26-29 2012.
60  * <a href="http://purl.org/holz/papers/holz_2012_ias.pdf">http://purl.org/holz/papers/holz_2012_ias.pdf</a>
61  *
62  * \author Dirk Holz, Radu B. Rusu
63  * \ingroup surface
64  */
65  template <typename PointInT>
66  class OrganizedFastMesh : public MeshConstruction<PointInT>
67  {
68  public:
69  using Ptr = shared_ptr<OrganizedFastMesh<PointInT> >;
70  using ConstPtr = shared_ptr<const OrganizedFastMesh<PointInT> >;
71 
74 
76 
77  using Polygons = std::vector<pcl::Vertices>;
78 
80  {
81  TRIANGLE_RIGHT_CUT, // _always_ "cuts" a quad from top left to bottom right
82  TRIANGLE_LEFT_CUT, // _always_ "cuts" a quad from top right to bottom left
83  TRIANGLE_ADAPTIVE_CUT, // "cuts" where possible and prefers larger differences in 'z' direction
84  QUAD_MESH // create a simple quad mesh
85  };
86 
87  /** \brief Constructor. Triangulation type defaults to \a QUAD_MESH. */
89  {
90  check_tree_ = false;
91  };
92 
93  /** \brief Destructor. */
94  ~OrganizedFastMesh () override = default;
95 
96  /** \brief Set a maximum edge length.
97  * Using not only the scalar \a a, but also \a b and \a c, allows for using a distance threshold in the form of:
98  * threshold(x) = c*x*x + b*x + a
99  * \param[in] a scalar coefficient of the (distance-dependent polynom) threshold
100  * \param[in] b linear coefficient of the (distance-dependent polynom) threshold
101  * \param[in] c quadratic coefficient of the (distance-dependent polynom) threshold
102  */
103  inline void
104  setMaxEdgeLength (float a, float b = 0.0f, float c = 0.0f)
105  {
106  max_edge_length_a_ = a;
107  max_edge_length_b_ = b;
108  max_edge_length_c_ = c;
109  max_edge_length_set_ = (max_edge_length_a_ + max_edge_length_b_ + max_edge_length_c_) > std::numeric_limits<float>::min();
110  };
111 
112  inline void
114  {
115  max_edge_length_set_ = false;
116  }
117 
118  /** \brief Set the edge length (in pixels) used for constructing the fixed mesh.
119  * \param[in] triangle_size edge length in pixels
120  * (Default: 1 = neighboring pixels are connected)
121  */
122  inline void
123  setTrianglePixelSize (int triangle_size)
124  {
125  setTrianglePixelSizeRows (triangle_size);
126  setTrianglePixelSizeColumns (triangle_size);
127  }
128 
129  /** \brief Set the edge length (in pixels) used for iterating over rows when constructing the fixed mesh.
130  * \param[in] triangle_size edge length in pixels
131  * (Default: 1 = neighboring pixels are connected)
132  */
133  inline void
134  setTrianglePixelSizeRows (int triangle_size)
135  {
136  triangle_pixel_size_rows_ = std::max (1, (triangle_size - 1));
137  }
138 
139  /** \brief Set the edge length (in pixels) used for iterating over columns when constructing the fixed mesh.
140  * \param[in] triangle_size edge length in pixels
141  * (Default: 1 = neighboring pixels are connected)
142  */
143  inline void
144  setTrianglePixelSizeColumns (int triangle_size)
145  {
146  triangle_pixel_size_columns_ = std::max (1, (triangle_size - 1));
147  }
148 
149  /** \brief Set the triangulation type (see \a TriangulationType)
150  * \param[in] type quad mesh, triangle mesh with fixed left, right cut,
151  * or adaptive cut (splits a quad w.r.t. the depth (z) of the points)
152  */
153  inline void
155  {
156  triangulation_type_ = type;
157  }
158 
159  /** \brief Set the viewpoint from where the input point cloud has been acquired.
160  * \param[in] viewpoint Vector containing the viewpoint coordinates (in the coordinate system of the data)
161  */
162  inline void setViewpoint (const Eigen::Vector3f& viewpoint)
163  {
164  viewpoint_ = viewpoint;
165  }
166 
167  /** \brief Get the viewpoint from where the input point cloud has been acquired. */
168  const inline Eigen::Vector3f& getViewpoint () const
169  {
170  return viewpoint_;
171  }
172 
173  /** \brief Store shadowed faces or not.
174  * \param[in] enable set to true to store shadowed faces
175  */
176  inline void
177  storeShadowedFaces (bool enable)
178  {
179  store_shadowed_faces_ = enable;
180  }
181 
182  /** \brief Set the angle tolerance used for checking whether or not an edge is occluded.
183  * Standard values are 5deg to 15deg (input in rad!). Set a value smaller than zero to
184  * disable the check for shadowed edges.
185  * \param[in] angle_tolerance Angle tolerance (in rad). Set a value <0 to disable.
186  */
187  inline void
188  setAngleTolerance(float angle_tolerance)
189  {
190  if (angle_tolerance > 0)
191  cos_angle_tolerance_ = std::abs (std::cos (angle_tolerance));
192  else
193  cos_angle_tolerance_ = -1.0f;
194  }
195 
196 
197  inline void setDistanceTolerance(float distance_tolerance, bool depth_dependent = false)
198  {
199  distance_tolerance_ = distance_tolerance;
200  if (distance_tolerance_ < 0)
201  return;
202 
203  distance_dependent_ = depth_dependent;
204  if (!distance_dependent_)
206  }
207 
208  /** \brief Use the points' depths (z-coordinates) instead of measured distances (points' distances to the viewpoint).
209  * \param[in] enable Set to true skips comptations and further speeds up computation by using depth instead of computing distance. false to disable. */
210  inline void useDepthAsDistance(bool enable)
211  {
212  use_depth_as_distance_ = enable;
213  }
214 
215  protected:
216  /** \brief max length of edge, scalar component */
217  float max_edge_length_a_{0.0f};
218  /** \brief max length of edge, scalar component */
219  float max_edge_length_b_{0.0f};
220  /** \brief max length of edge, scalar component */
221  float max_edge_length_c_{0.0f};
222  /** \brief flag whether or not edges are limited in length */
223  bool max_edge_length_set_{false};
224 
225  /** \brief flag whether or not max edge length is distance dependent. */
227 
228  /** \brief size of triangle edges (in pixels) for iterating over rows. */
230 
231  /** \brief size of triangle edges (in pixels) for iterating over columns*/
233 
234  /** \brief Type of meshing scheme (quads vs. triangles, left cut vs. right cut ... */
236 
237  /** \brief Viewpoint from which the point cloud has been acquired (in the same coordinate frame as the data). */
238  Eigen::Vector3f viewpoint_{Eigen::Vector3f::Zero ()};
239 
240  /** \brief Whether or not shadowed faces are stored, e.g., for exploration */
242 
243  /** \brief (Cosine of the) angle tolerance used when checking whether or not an edge between two points is shadowed. */
244  float cos_angle_tolerance_{std::abs (std::cos (pcl::deg2rad (12.5f)))};
245 
246  /** \brief distance tolerance for filtering out shadowed/occluded edges */
247  float distance_tolerance_{-1.0f};
248 
249  /** \brief flag whether or not \a distance_tolerance_ is distance dependent (multiplied by the squared distance to the point) or not. */
250  bool distance_dependent_{false};
251 
252  /** \brief flag whether or not the points' depths are used instead of measured distances (points' distances to the viewpoint).
253  This flag may be set using useDepthAsDistance(true) for (RGB-)Depth cameras to skip computations and gain additional speed up. */
255 
256 
257  /** \brief Perform the actual polygonal reconstruction.
258  * \param[out] polygons the resultant polygons
259  */
260  void
261  reconstructPolygons (std::vector<pcl::Vertices>& polygons);
262 
263  /** \brief Create the surface.
264  * \param[out] polygons the resultant polygons, as a set of vertices. The Vertices structure contains an array of point indices.
265  */
266  void
267  performReconstruction (std::vector<pcl::Vertices> &polygons) override;
268 
269  /** \brief Create the surface.
270  *
271  * Simply uses image indices to create an initial polygonal mesh for organized point clouds.
272  * \a indices_ are ignored!
273  *
274  * \param[out] output the resultant polygonal mesh
275  */
276  void
277  performReconstruction (pcl::PolygonMesh &output) override;
278 
279  /** \brief Add a new triangle to the current polygon mesh
280  * \param[in] a index of the first vertex
281  * \param[in] b index of the second vertex
282  * \param[in] c index of the third vertex
283  * \param[in] idx the index in the set of polygon vertices (assumes \a idx is valid in \a polygons)
284  * \param[out] polygons the polygon mesh to be updated
285  */
286  inline void
287  addTriangle (int a, int b, int c, int idx, std::vector<pcl::Vertices>& polygons)
288  {
289  assert (idx < static_cast<int> (polygons.size ()));
290  polygons[idx].vertices.resize (3);
291  polygons[idx].vertices[0] = a;
292  polygons[idx].vertices[1] = b;
293  polygons[idx].vertices[2] = c;
294  }
295 
296  /** \brief Add a new quad to the current polygon mesh
297  * \param[in] a index of the first vertex
298  * \param[in] b index of the second vertex
299  * \param[in] c index of the third vertex
300  * \param[in] d index of the fourth vertex
301  * \param[in] idx the index in the set of polygon vertices (assumes \a idx is valid in \a polygons)
302  * \param[out] polygons the polygon mesh to be updated
303  */
304  inline void
305  addQuad (int a, int b, int c, int d, int idx, std::vector<pcl::Vertices>& polygons)
306  {
307  assert (idx < static_cast<int> (polygons.size ()));
308  polygons[idx].vertices.resize (4);
309  polygons[idx].vertices[0] = a;
310  polygons[idx].vertices[1] = b;
311  polygons[idx].vertices[2] = c;
312  polygons[idx].vertices[3] = d;
313  }
314 
315  /** \brief Set (all) coordinates of a particular point to the specified value
316  * \param[in] point_index index of point
317  * \param[out] mesh to modify
318  * \param[in] value value to use when re-setting
319  * \param[in] field_x_idx the X coordinate of the point
320  * \param[in] field_y_idx the Y coordinate of the point
321  * \param[in] field_z_idx the Z coordinate of the point
322  */
323  inline void
324  resetPointData (const int &point_index, pcl::PolygonMesh &mesh, const float &value = 0.0f,
325  int field_x_idx = 0, int field_y_idx = 1, int field_z_idx = 2)
326  {
327  float new_value = value;
328  memcpy (&mesh.cloud.data[point_index * mesh.cloud.point_step + mesh.cloud.fields[field_x_idx].offset], &new_value, sizeof (float));
329  memcpy (&mesh.cloud.data[point_index * mesh.cloud.point_step + mesh.cloud.fields[field_y_idx].offset], &new_value, sizeof (float));
330  memcpy (&mesh.cloud.data[point_index * mesh.cloud.point_step + mesh.cloud.fields[field_z_idx].offset], &new_value, sizeof (float));
331  }
332 
333  /** \brief Check if a point is shadowed by another point
334  * \param[in] point_a the first point
335  * \param[in] point_b the second point
336  */
337  inline bool
338  isShadowed (const PointInT& point_a, const PointInT& point_b)
339  {
340  bool valid = true;
341 
342  Eigen::Vector3f dir_a = viewpoint_ - point_a.getVector3fMap ();
343  Eigen::Vector3f dir_b = point_b.getVector3fMap () - point_a.getVector3fMap ();
344  float distance_to_points = dir_a.norm ();
345  float distance_between_points = dir_b.norm ();
346 
347  if (cos_angle_tolerance_ > 0)
348  {
349  float cos_angle = dir_a.dot (dir_b) / (distance_to_points*distance_between_points);
350  if (std::isnan(cos_angle))
351  cos_angle = 1.0f;
352  bool check_angle = std::fabs (cos_angle) >= cos_angle_tolerance_;
353 
354  bool check_distance = true;
355  if (check_angle && (distance_tolerance_ > 0))
356  {
357  float dist_thresh = distance_tolerance_;
359  {
360  float d = distance_to_points;
362  d = std::max(point_a.z, point_b.z);
363  dist_thresh *= d*d;
364  dist_thresh *= dist_thresh; // distance_tolerance_ is already squared if distance_dependent_ is false.
365  }
366  check_distance = (distance_between_points > dist_thresh);
367  }
368  valid = !(check_angle && check_distance);
369  }
370 
371  // check if max. edge length is not exceeded
373  {
374  float dist = (use_depth_as_distance_ ? std::max(point_a.z, point_b.z) : distance_to_points);
375  float dist_thresh = max_edge_length_a_;
376  if (std::fabs(max_edge_length_b_) > std::numeric_limits<float>::min())
377  dist_thresh += max_edge_length_b_ * dist;
378  if (std::fabs(max_edge_length_c_) > std::numeric_limits<float>::min())
379  dist_thresh += max_edge_length_c_ * dist * dist;
380  valid = (distance_between_points <= dist_thresh);
381  }
382 
383  return !valid;
384  }
385 
386  /** \brief Check if a triangle is valid.
387  * \param[in] a index of the first vertex
388  * \param[in] b index of the second vertex
389  * \param[in] c index of the third vertex
390  */
391  inline bool
392  isValidTriangle (const int& a, const int& b, const int& c)
393  {
394  if (!pcl::isFinite ((*input_)[a])) return (false);
395  if (!pcl::isFinite ((*input_)[b])) return (false);
396  if (!pcl::isFinite ((*input_)[c])) return (false);
397  return (true);
398  }
399 
400  /** \brief Check if a triangle is shadowed.
401  * \param[in] a index of the first vertex
402  * \param[in] b index of the second vertex
403  * \param[in] c index of the third vertex
404  */
405  inline bool
406  isShadowedTriangle (const int& a, const int& b, const int& c)
407  {
408  if (isShadowed ((*input_)[a], (*input_)[b])) return (true);
409  if (isShadowed ((*input_)[b], (*input_)[c])) return (true);
410  if (isShadowed ((*input_)[c], (*input_)[a])) return (true);
411  return (false);
412  }
413 
414  /** \brief Check if a quad is valid.
415  * \param[in] a index of the first vertex
416  * \param[in] b index of the second vertex
417  * \param[in] c index of the third vertex
418  * \param[in] d index of the fourth vertex
419  */
420  inline bool
421  isValidQuad (const int& a, const int& b, const int& c, const int& d)
422  {
423  if (!pcl::isFinite ((*input_)[a])) return (false);
424  if (!pcl::isFinite ((*input_)[b])) return (false);
425  if (!pcl::isFinite ((*input_)[c])) return (false);
426  if (!pcl::isFinite ((*input_)[d])) return (false);
427  return (true);
428  }
429 
430  /** \brief Check if a triangle is shadowed.
431  * \param[in] a index of the first vertex
432  * \param[in] b index of the second vertex
433  * \param[in] c index of the third vertex
434  * \param[in] d index of the fourth vertex
435  */
436  inline bool
437  isShadowedQuad (const int& a, const int& b, const int& c, const int& d)
438  {
439  if (isShadowed ((*input_)[a], (*input_)[b])) return (true);
440  if (isShadowed ((*input_)[b], (*input_)[c])) return (true);
441  if (isShadowed ((*input_)[c], (*input_)[d])) return (true);
442  if (isShadowed ((*input_)[d], (*input_)[a])) return (true);
443  return (false);
444  }
445 
446  /** \brief Create a quad mesh.
447  * \param[out] polygons the resultant mesh
448  */
449  void
450  makeQuadMesh (std::vector<pcl::Vertices>& polygons);
451 
452  /** \brief Create a right cut mesh.
453  * \param[out] polygons the resultant mesh
454  */
455  void
456  makeRightCutMesh (std::vector<pcl::Vertices>& polygons);
457 
458  /** \brief Create a left cut mesh.
459  * \param[out] polygons the resultant mesh
460  */
461  void
462  makeLeftCutMesh (std::vector<pcl::Vertices>& polygons);
463 
464  /** \brief Create an adaptive cut mesh.
465  * \param[out] polygons the resultant mesh
466  */
467  void
468  makeAdaptiveCutMesh (std::vector<pcl::Vertices>& polygons);
469  };
470 }
471 
472 #ifdef PCL_NO_PRECOMPILE
473 #include <pcl/surface/impl/organized_fast_mesh.hpp>
474 #endif
void setTriangulationType(TriangulationType type)
Set the triangulation type (see TriangulationType)
void makeQuadMesh(std::vector< pcl::Vertices > &polygons)
Create a quad mesh.
void setDistanceTolerance(float distance_tolerance, bool depth_dependent=false)
bool isFinite(const PointT &pt)
Tests if the 3D components of a point are all finite param[in] pt point to be tested return true if f...
Definition: point_tests.h:55
std::vector<::pcl::PCLPointField > fields
shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:413
float deg2rad(float alpha)
Convert an angle from degrees to radians.
Definition: angles.hpp:67
bool check_tree_
A flag specifying whether or not the derived reconstruction algorithm needs the search object tree...
void resetPointData(const int &point_index, pcl::PolygonMesh &mesh, const float &value=0.0f, int field_x_idx=0, int field_y_idx=1, int field_z_idx=2)
Set (all) coordinates of a particular point to the specified value.
void makeAdaptiveCutMesh(std::vector< pcl::Vertices > &polygons)
Create an adaptive cut mesh.
Eigen::Vector3f viewpoint_
Viewpoint from which the point cloud has been acquired (in the same coordinate frame as the data)...
Simple triangulation/surface reconstruction for organized point clouds.
bool distance_dependent_
flag whether or not distance_tolerance_ is distance dependent (multiplied by the squared distance to ...
~OrganizedFastMesh() override=default
Destructor.
void setTrianglePixelSizeRows(int triangle_size)
Set the edge length (in pixels) used for iterating over rows when constructing the fixed mesh...
void setTrianglePixelSize(int triangle_size)
Set the edge length (in pixels) used for constructing the fixed mesh.
void makeLeftCutMesh(std::vector< pcl::Vertices > &polygons)
Create a left cut mesh.
void reconstructPolygons(std::vector< pcl::Vertices > &polygons)
Perform the actual polygonal reconstruction.
TriangulationType triangulation_type_
Type of meshing scheme (quads vs.
int triangle_pixel_size_rows_
size of triangle edges (in pixels) for iterating over rows.
void makeRightCutMesh(std::vector< pcl::Vertices > &polygons)
Create a right cut mesh.
float max_edge_length_a_
max length of edge, scalar component
void setAngleTolerance(float angle_tolerance)
Set the angle tolerance used for checking whether or not an edge is occluded.
typename pcl::PointCloud< PointInT >::Ptr PointCloudPtr
float max_edge_length_b_
max length of edge, scalar component
int triangle_pixel_size_columns_
size of triangle edges (in pixels) for iterating over columns
bool isValidTriangle(const int &a, const int &b, const int &c)
Check if a triangle is valid.
void setTrianglePixelSizeColumns(int triangle_size)
Set the edge length (in pixels) used for iterating over columns when constructing the fixed mesh...
bool isShadowedQuad(const int &a, const int &b, const int &c, const int &d)
Check if a triangle is shadowed.
bool isValidQuad(const int &a, const int &b, const int &c, const int &d)
Check if a quad is valid.
void setMaxEdgeLength(float a, float b=0.0f, float c=0.0f)
Set a maximum edge length.
void setViewpoint(const Eigen::Vector3f &viewpoint)
Set the viewpoint from where the input point cloud has been acquired.
float max_edge_length_c_
max length of edge, scalar component
float cos_angle_tolerance_
(Cosine of the) angle tolerance used when checking whether or not an edge between two points is shado...
MeshConstruction represents a base surface reconstruction class.
std::vector< std::uint8_t > data
void addQuad(int a, int b, int c, int d, int idx, std::vector< pcl::Vertices > &polygons)
Add a new quad to the current polygon mesh.
const Eigen::Vector3f & getViewpoint() const
Get the viewpoint from where the input point cloud has been acquired.
void useDepthAsDistance(bool enable)
Use the points' depths (z-coordinates) instead of measured distances (points' distances to the viewpo...
::pcl::PCLPointCloud2 cloud
Definition: PolygonMesh.h:20
void addTriangle(int a, int b, int c, int idx, std::vector< pcl::Vertices > &polygons)
Add a new triangle to the current polygon mesh.
shared_ptr< const OrganizedFastMesh< PointInT > > ConstPtr
shared_ptr< OrganizedFastMesh< PointInT > > Ptr
float distance_tolerance_
distance tolerance for filtering out shadowed/occluded edges
PointCloudConstPtr input_
The input point cloud dataset.
Definition: pcl_base.h:147
bool isShadowedTriangle(const int &a, const int &b, const int &c)
Check if a triangle is shadowed.
void storeShadowedFaces(bool enable)
Store shadowed faces or not.
void performReconstruction(std::vector< pcl::Vertices > &polygons) override
Create the surface.
std::vector< pcl::Vertices > Polygons
bool max_edge_length_set_
flag whether or not edges are limited in length
bool use_depth_as_distance_
flag whether or not the points' depths are used instead of measured distances (points' distances to t...
bool isShadowed(const PointInT &point_a, const PointInT &point_b)
Check if a point is shadowed by another point.
bool store_shadowed_faces_
Whether or not shadowed faces are stored, e.g., for exploration.
bool max_edge_length_dist_dependent_
flag whether or not max edge length is distance dependent.
OrganizedFastMesh()
Constructor.