Point Cloud Library (PCL)  1.12.0
ear_clipping.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2010, 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  * $Id$
35  *
36  */
37 
38 #pragma once
39 
40 #include <pcl/point_types.h>
41 #include <pcl/surface/processing.h>
42 
43 namespace pcl
44 {
45 
46  /** \brief The ear clipping triangulation algorithm.
47  * The code is inspired by Flavien Brebion implementation, which is
48  * in n^3 and does not handle holes.
49  * \author Nicolas Burrus
50  * \ingroup surface
51  */
53  {
54  public:
55  using Ptr = shared_ptr<EarClipping>;
56  using ConstPtr = shared_ptr<const EarClipping>;
57 
60  /** \brief Empty constructor */
62  {
63  };
64 
65  protected:
66  /** \brief a Pointer to the point cloud data. */
68 
69  /** \brief This method should get called before starting the actual computation. */
70  bool
71  initCompute () override;
72 
73  /** \brief The actual surface reconstruction method.
74  * \param[out] output the output polygonal mesh
75  */
76  void
77  performProcessing (pcl::PolygonMesh &output) override;
78 
79  /** \brief Triangulate one polygon.
80  * \param[in] vertices the set of vertices
81  * \param[out] output the resultant polygonal mesh
82  */
83  void
84  triangulate (const Vertices& vertices, PolygonMesh& output);
85 
86  /** \brief Compute the signed area of a polygon.
87  * \param[in] vertices the vertices representing the polygon
88  */
89  float
90  area (const Indices& vertices);
91 
92  /** \brief Compute the signed area of a polygon.
93  * \param[in] vertices the vertices representing the polygon
94  */
95  template <typename T = pcl::index_t, std::enable_if_t<!std::is_same<T, std::uint32_t>::value, pcl::index_t> = 0>
96  PCL_DEPRECATED(1, 14, "This method creates a useless copy of the vertices vector. Use area method which accepts Indices instead")
97  float
98  area (const std::vector<std::uint32_t>& vertices)
99  {
100  return area(Indices (vertices.cbegin(), vertices.cend()));
101  }
102 
103  /** \brief Check if the triangle (u,v,w) is an ear.
104  * \param[in] u the first triangle vertex
105  * \param[in] v the second triangle vertex
106  * \param[in] w the third triangle vertex
107  * \param[in] vertices a set of input vertices
108  */
109  bool
110  isEar (int u, int v, int w, const Indices& vertices);
111 
112  /** \brief Check if the triangle (u,v,w) is an ear.
113  * \param[in] u the first triangle vertex
114  * \param[in] v the second triangle vertex
115  * \param[in] w the third triangle vertex
116  * \param[in] vertices a set of input vertices
117  */
118  template <typename T = pcl::index_t, std::enable_if_t<!std::is_same<T, std::uint32_t>::value, pcl::index_t> = 0>
119  PCL_DEPRECATED(1, 14, "This method creates a useless copy of the vertices vector. Use isEar method which accepts Indices instead")
120  bool
121  isEar (int u, int v, int w, const std::vector<std::uint32_t>& vertices)
122  {
123  return isEar(u, v, w, Indices (vertices.cbegin(), vertices.cend()));
124  }
125 
126  /** \brief Check if p is inside the triangle (u,v,w).
127  * \param[in] u the first triangle vertex
128  * \param[in] v the second triangle vertex
129  * \param[in] w the third triangle vertex
130  * \param[in] p the point to check
131  */
132  bool
133  isInsideTriangle (const Eigen::Vector3f& u,
134  const Eigen::Vector3f& v,
135  const Eigen::Vector3f& w,
136  const Eigen::Vector3f& p);
137 
138  /** \brief Compute the cross product between 2D vectors.
139  * \param[in] p1 the first 2D vector
140  * \param[in] p2 the first 2D vector
141  */
142  float
143  crossProduct (const Eigen::Vector2f& p1, const Eigen::Vector2f& p2) const
144  {
145  return p1[0]*p2[1] - p1[1]*p2[0];
146  }
147 
148  };
149 
150 }
The ear clipping triangulation algorithm.
Definition: ear_clipping.h:53
float area(const Indices &vertices)
Compute the signed area of a polygon.
void triangulate(const Vertices &vertices, PolygonMesh &output)
Triangulate one polygon.
void performProcessing(pcl::PolygonMesh &output) override
The actual surface reconstruction method.
bool initCompute() override
This method should get called before starting the actual computation.
shared_ptr< EarClipping > Ptr
Definition: ear_clipping.h:55
bool isInsideTriangle(const Eigen::Vector3f &u, const Eigen::Vector3f &v, const Eigen::Vector3f &w, const Eigen::Vector3f &p)
Check if p is inside the triangle (u,v,w).
pcl::PointCloud< pcl::PointXYZ >::Ptr points_
a Pointer to the point cloud data.
Definition: ear_clipping.h:63
bool isEar(int u, int v, int w, const Indices &vertices)
Check if the triangle (u,v,w) is an ear.
shared_ptr< const EarClipping > ConstPtr
Definition: ear_clipping.h:56
float crossProduct(const Eigen::Vector2f &p1, const Eigen::Vector2f &p2) const
Compute the cross product between 2D vectors.
Definition: ear_clipping.h:143
EarClipping()
Empty constructor.
Definition: ear_clipping.h:61
MeshProcessing represents the base class for mesh processing algorithms.
Definition: processing.h:95
virtual bool initCompute()
Initialize computation.
pcl::PolygonMeshConstPtr input_mesh_
Input polygonal mesh.
Definition: processing.h:147
shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:413
Defines all the PCL implemented PointT point type structures.
detail::int_type_t< detail::index_type_size, detail::index_type_signed > index_t
Type used for an index in PCL.
Definition: types.h:112
IndicesAllocator<> Indices
Type used for indices in PCL.
Definition: types.h:133
#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
Describes a set of vertices in a polygon mesh, by basically storing an array of indices.
Definition: Vertices.h:15