Point Cloud Library (PCL)  1.7.0
triangle_mesh.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2009-2012, Willow Garage, Inc.
6  * Copyright (c) 2012-, Open Perception, 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 the copyright holder(s) 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 #ifndef PCL_GEOMETRY_TRIANGLE_MESH_H
42 #define PCL_GEOMETRY_TRIANGLE_MESH_H
43 
44 #include <utility>
45 
46 #include <pcl/geometry/mesh_base.h>
47 
48 namespace pcl
49 {
50  namespace geometry
51  {
52  /** \brief Tag describing the type of the mesh. */
53  struct TriangleMeshTag {};
54 
55  /** \brief Half-edge mesh that can only store triangles.
56  * \tparam MeshTraitsT Please have a look at pcl::geometry::DefaultMeshTraits.
57  * \author Martin Saelzle
58  * \ingroup geometry
59  */
60  template <class MeshTraitsT>
61  class TriangleMesh : public pcl::geometry::MeshBase <TriangleMesh <MeshTraitsT>, MeshTraitsT, TriangleMeshTag>
62  {
63  public:
64 
66 
68  typedef boost::shared_ptr <Self> Ptr;
69  typedef boost::shared_ptr <const Self> ConstPtr;
70 
71  typedef typename Base::VertexData VertexData;
72  typedef typename Base::HalfEdgeData HalfEdgeData;
73  typedef typename Base::EdgeData EdgeData;
74  typedef typename Base::FaceData FaceData;
75  typedef typename Base::IsManifold IsManifold;
76  typedef typename Base::MeshTag MeshTag;
77 
80  typedef typename Base::HasEdgeData HasEdgeData;
81  typedef typename Base::HasFaceData HasFaceData;
82 
87 
88  // Indices
89  typedef typename Base::VertexIndex VertexIndex;
91  typedef typename Base::EdgeIndex EdgeIndex;
92  typedef typename Base::FaceIndex FaceIndex;
93  typedef std::pair <FaceIndex, FaceIndex> FaceIndexPair;
94 
97  typedef typename Base::EdgeIndices EdgeIndices;
98  typedef typename Base::FaceIndices FaceIndices;
99 
100  // Circulators
109 
110  /** \brief Constructor. */
112  : Base (),
113  add_triangle_ (3),
114  inner_he_atp_ (4),
115  is_new_atp_ (4)
116  {
117  }
118 
119  /** \brief The base method of addFace is hidden because of the overloads in this class. */
120  using Base::addFace;
121 
122  /** \brief Add a triangle to the mesh. Data is only added if it is associated with the elements. The last vertex is connected with the first one.
123  * \param[in] idx_v_0 Index to the first vertex.
124  * \param[in] idx_v_1 Index to the second vertex.
125  * \param[in] idx_v_2 Index to the third vertex.
126  * \param[in] face_data Data that is set for the face.
127  * \param[in] half_edge_data Data that is set for all added half-edges.
128  * \param[in] edge_data Data that is set for all added edges.
129  * \return Index to the new face. Failure is signaled by returning an invalid face index.
130  * \warning The vertices must be valid and unique (each vertex may be contained only once). Not complying with this requirement results in undefined behavior!
131  */
132  inline FaceIndex
133  addFace (const VertexIndex& idx_v_0,
134  const VertexIndex& idx_v_1,
135  const VertexIndex& idx_v_2,
136  const FaceData& face_data = FaceData (),
137  const EdgeData& edge_data = EdgeData (),
138  const HalfEdgeData& half_edge_data = HalfEdgeData ())
139  {
140  add_triangle_ [0] = idx_v_0;
141  add_triangle_ [1] = idx_v_1;
142  add_triangle_ [2] = idx_v_2;
143 
144  return (this->addFaceImplBase (add_triangle_, face_data, edge_data, half_edge_data));
145  }
146 
147  /** \brief Add two triangles for the four given input vertices. When using a manifold triangle mesh it is not possible to connect two bounded regions without going through a non-manifold intermediate step. This method first tries to add the triangles individually and if this fails connects the whole configuration at once (if possible).
148  * \param[in] vertices Indices to the vertices of the new face. (The size must be equal to four).
149  * \param[in] face_data Data that is set for the face.
150  * \param[in] half_edge_data Data that is set for all added half-edges.
151  * \param[in] edge_data Data that is set for all added edges.
152  * \return Pair of face indices. The first index is valid if one triangle was added. Both indices are valid if two triangles were added.
153  * \warning The vertices must be valid and unique (each vertex may be contained only once). Not complying with this requirement results in undefined behavior!
154  */
156  addTrianglePair (const VertexIndices& vertices,
157  const FaceData& face_data = FaceData (),
158  const EdgeData& edge_data = EdgeData (),
159  const HalfEdgeData& half_edge_data = HalfEdgeData ())
160  {
161  if (vertices.size () != 4)
162  {
163  return (std::make_pair (FaceIndex (), FaceIndex ()));
164  }
165  else
166  {
167  return (this->addTrianglePair (vertices [0], vertices [1], vertices [2], vertices [3], face_data, edge_data, half_edge_data));
168  }
169  }
170 
171  /** \brief Add two triangles for the four given input vertices. When using a manifold triangle mesh it is not possible to connect two bounded regions without going through a non-manifold intermediate step. This method first tries to add the triangles individually and if this fails connects the whole configuration at once (if possible).
172  * \param[in] idx_v_0 Index to the first vertex.
173  * \param[in] idx_v_1 Index to the second vertex.
174  * \param[in] idx_v_2 Index to the third vertex.
175  * \param[in] idx_v_3 Index to the fourth vertex.
176  * \param[in] face_data Data that is set for the face.
177  * \param[in] half_edge_data Data that is set for all added half-edges.
178  * \param[in] edge_data Data that is set for all added edges.
179  * \return Pair of face indices. The first index is valid if one triangle was added. Both indices are valid if two triangles were added.
180  * \warning The vertices must be valid and unique (each vertex may be contained only once). Not complying with this requirement results in undefined behavior!
181  */
182  inline FaceIndexPair
183  addTrianglePair (const VertexIndex& idx_v_0,
184  const VertexIndex& idx_v_1,
185  const VertexIndex& idx_v_2,
186  const VertexIndex& idx_v_3,
187  const FaceData& face_data = FaceData (),
188  const EdgeData& edge_data = EdgeData (),
189  const HalfEdgeData& half_edge_data = HalfEdgeData ())
190  {
191  // Try to add two faces
192  // 3 - 2
193  // | / |
194  // 0 - 1
195  FaceIndex idx_face_0 = this->addFace (idx_v_0, idx_v_1, idx_v_2, face_data);
196  FaceIndex idx_face_1 = this->addFace (idx_v_0, idx_v_2, idx_v_3, face_data);
197 
198  if (idx_face_0.isValid ())
199  {
200  return (std::make_pair (idx_face_0, idx_face_1));
201  }
202  else if (idx_face_1.isValid ())
203  {
204  idx_face_0 = this->addFace (idx_v_0, idx_v_1, idx_v_2, face_data); // might be possible to add now
205  return (std::make_pair (idx_face_1, idx_face_0));
206  }
207 
208  // Try to add two faces
209  // 3 - 2
210  // | \ |
211  // 0 - 1
212  idx_face_0 = this->addFace (idx_v_1, idx_v_2, idx_v_3, face_data);
213  idx_face_1 = this->addFace (idx_v_0, idx_v_1, idx_v_3, face_data);
214 
215  if (idx_face_0.isValid ())
216  {
217  return (std::make_pair (idx_face_0, idx_face_1));
218  }
219  else if (idx_face_1.isValid ())
220  {
221  idx_face_0 = this->addFace (idx_v_1, idx_v_2, idx_v_3, face_data); // might be possible to add now
222  return (std::make_pair (idx_face_1, idx_face_0));
223  }
224 
225  if (!IsManifold::value)
226  {
227  return (std::make_pair (FaceIndex (), FaceIndex ()));
228  }
229 
230  // Check manifoldness
231  if (!Base::checkTopology1 (idx_v_0,idx_v_1, inner_he_atp_ [0], is_new_atp_ [0], IsManifold ()) ||
232  !Base::checkTopology1 (idx_v_1,idx_v_2, inner_he_atp_ [1], is_new_atp_ [1], IsManifold ()) ||
233  !Base::checkTopology1 (idx_v_2,idx_v_3, inner_he_atp_ [2], is_new_atp_ [2], IsManifold ()) ||
234  !Base::checkTopology1 (idx_v_3,idx_v_0, inner_he_atp_ [3], is_new_atp_ [3], IsManifold ()))
235  {
236  return (std::make_pair (FaceIndex (), FaceIndex ()));
237  }
238 
239  // Connect the triangle pair
240  if (!is_new_atp_ [0] && is_new_atp_ [1] && !is_new_atp_ [2] && is_new_atp_ [3])
241  {
242  return (this->connectTrianglePair (inner_he_atp_ [0], inner_he_atp_ [2], idx_v_0, idx_v_1, idx_v_2, idx_v_3, face_data, edge_data, half_edge_data));
243  }
244  else if (is_new_atp_ [0] && !is_new_atp_ [1] && is_new_atp_ [2] && !is_new_atp_ [3])
245  {
246  return (this->connectTrianglePair (inner_he_atp_ [1], inner_he_atp_ [3], idx_v_1, idx_v_2, idx_v_3, idx_v_0, face_data, edge_data, half_edge_data));
247  }
248  else
249  {
250  return (std::make_pair (FaceIndex (), FaceIndex ()));
251  }
252  }
253 
254  private:
255 
256  // NOTE: Can't use the typedef of Base as a friend.
257  friend class pcl::geometry::MeshBase <TriangleMesh <MeshTraitsT>, MeshTraitsT, pcl::geometry::TriangleMeshTag>;
258 
259  /** \brief addFace for the triangular mesh. */
260  inline FaceIndex
261  addFaceImpl (const VertexIndices& vertices,
262  const FaceData& face_data,
263  const EdgeData& edge_data,
264  const HalfEdgeData& half_edge_data)
265  {
266  if (vertices.size () == 3)
267  return (this->addFaceImplBase (vertices, face_data, edge_data, half_edge_data));
268  else
269  return (FaceIndex ());
270  }
271 
272  /** \brief Connect the triangles a-b-c and a-c-d. The edges a-b and c-d must be old and the edges b-c and d-a must be new. */
273  // d - c
274  // | / |
275  // a - b
277  connectTrianglePair (const HalfEdgeIndex& idx_he_ab,
278  const HalfEdgeIndex& idx_he_cd,
279  const VertexIndex& idx_v_a,
280  const VertexIndex& idx_v_b,
281  const VertexIndex& idx_v_c,
282  const VertexIndex& idx_v_d,
283  const FaceData& face_data,
284  const EdgeData& edge_data,
285  const HalfEdgeData& he_data)
286  {
287  // Add new half-edges
288  const HalfEdgeIndex idx_he_bc = Base::addEdge (idx_v_b, idx_v_c, he_data, edge_data);
289  const HalfEdgeIndex idx_he_da = Base::addEdge (idx_v_d, idx_v_a, he_data, edge_data);
290  const HalfEdgeIndex idx_he_ca = Base::addEdge (idx_v_c, idx_v_a, he_data, edge_data);
291 
292  const HalfEdgeIndex idx_he_cb = Base::getOppositeHalfEdgeIndex (idx_he_bc);
293  const HalfEdgeIndex idx_he_ad = Base::getOppositeHalfEdgeIndex (idx_he_da);
294  const HalfEdgeIndex idx_he_ac = Base::getOppositeHalfEdgeIndex (idx_he_ca);
295 
296  // Get the existing half-edges
297  const HalfEdgeIndex idx_he_ab_prev = Base::getPrevHalfEdgeIndex (idx_he_ab); // No reference!
298  const HalfEdgeIndex idx_he_ab_next = Base::getNextHalfEdgeIndex (idx_he_ab); // No reference!
299 
300  const HalfEdgeIndex idx_he_cd_prev = Base::getPrevHalfEdgeIndex (idx_he_cd); // No reference!
301  const HalfEdgeIndex idx_he_cd_next = Base::getNextHalfEdgeIndex (idx_he_cd); // No reference!
302 
303  // Connect the outer half-edges
304  Base::connectPrevNext (idx_he_ab_prev, idx_he_ad );
305  Base::connectPrevNext (idx_he_ad , idx_he_cd_next);
306  Base::connectPrevNext (idx_he_cd_prev, idx_he_cb );
307  Base::connectPrevNext (idx_he_cb , idx_he_ab_next);
308 
309  // Connect the inner half-edges
310  Base::connectPrevNext (idx_he_ab, idx_he_bc);
311  Base::connectPrevNext (idx_he_bc, idx_he_ca);
312  Base::connectPrevNext (idx_he_ca, idx_he_ab);
313 
314  Base::connectPrevNext (idx_he_ac, idx_he_cd);
315  Base::connectPrevNext (idx_he_cd, idx_he_da);
316  Base::connectPrevNext (idx_he_da, idx_he_ac);
317 
318  // Connect the vertices to the boundary half-edges
319  Base::setOutgoingHalfEdgeIndex (idx_v_a, idx_he_ad );
320  Base::setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ab_next);
321  Base::setOutgoingHalfEdgeIndex (idx_v_c, idx_he_cb );
322  Base::setOutgoingHalfEdgeIndex (idx_v_d, idx_he_cd_next);
323 
324  // Add and connect the faces
325  HalfEdgeIndices inner_he_abc; inner_he_abc.reserve (3);
326  inner_he_abc.push_back (idx_he_ab);
327  inner_he_abc.push_back (idx_he_bc);
328  inner_he_abc.push_back (idx_he_ca);
329 
330  HalfEdgeIndices inner_he_acd; inner_he_acd.reserve (3);
331  inner_he_acd.push_back (idx_he_ac);
332  inner_he_acd.push_back (idx_he_cd);
333  inner_he_acd.push_back (idx_he_da);
334 
335  const FaceIndex idx_f_abc = Base::connectFace (inner_he_abc, face_data);
336  const FaceIndex idx_f_acd = Base::connectFace (inner_he_acd, face_data);
337 
338  return (std::make_pair (idx_f_abc, idx_f_acd));
339  }
340 
341  ////////////////////////////////////////////////////////////////////////
342  // Members
343  ////////////////////////////////////////////////////////////////////////
344 
345  /** \brief Storage for adding a triangle. */
346  VertexIndices add_triangle_;
347 
348  /** \brief Storage for addTrianglePair. */
349  HalfEdgeIndices inner_he_atp_;
350 
351  /** \brief Storage for addTrianglePair. */
352  std::vector <bool> is_new_atp_;
353 
354  public:
355 
356  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
357  };
358  } // End namespace geom
359 } // End namespace pcl
360 
361 #endif // PCL_GEOMETRY_TRIANGLE_MESH_H