Point Cloud Library (PCL)  1.9.1-dev
mesh_base.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 #pragma once
42 
43 #include <vector>
44 
45 #include <pcl/geometry/boost.h>
46 #include <pcl/geometry/eigen.h>
47 #include <pcl/geometry/mesh_circulators.h>
48 #include <pcl/geometry/mesh_indices.h>
49 #include <pcl/geometry/mesh_elements.h>
50 #include <pcl/geometry/mesh_traits.h>
51 #include <pcl/point_cloud.h>
52 
53 ////////////////////////////////////////////////////////////////////////////////
54 // Global variables used during testing
55 ////////////////////////////////////////////////////////////////////////////////
56 
57 #ifdef PCL_GEOMETRY_MESH_BASE_TEST_DELETE_FACE_MANIFOLD_2
58 namespace pcl
59 {
60  namespace geometry
61  {
62  bool g_pcl_geometry_mesh_base_test_delete_face_manifold_2_success;
63  } // End namespace geometry
64 } // End namespace pcl
65 #endif
66 
67 ////////////////////////////////////////////////////////////////////////////////
68 // Forward declarations
69 ////////////////////////////////////////////////////////////////////////////////
70 
71 namespace pcl
72 {
73  namespace geometry
74  {
75  template <class MeshT>
76  class MeshIO;
77  } // End namespace geometry
78 } // End namespace pcl
79 
80 ////////////////////////////////////////////////////////////////////////////////
81 // MeshBase
82 ////////////////////////////////////////////////////////////////////////////////
83 
84 namespace pcl
85 {
86  namespace geometry
87  {
88  /** \brief Base class for the half-edge mesh.
89  * \tparam DerivedT Has to implement the method 'addFaceImpl'. Please have a look at pcl::geometry::TriangleMesh, pcl::geometry::QuadMesh and pcl::geometry::PolygonMesh.
90  * \tparam MeshTraitsT Please have a look at pcl::geometry::DefaultMeshTraits.
91  * \tparam MeshTagT Tag describing the type of the mesh, e.g. TriangleMeshTag, QuadMeshTag, PolygonMeshTag.
92  * \author Martin Saelzle
93  * \ingroup geometry
94  * \todo Add documentation
95  */
96  template <class DerivedT, class MeshTraitsT, class MeshTagT>
97  class MeshBase
98  {
99  public:
100 
102  typedef boost::shared_ptr <Self> Ptr;
103  typedef boost::shared_ptr <const Self> ConstPtr;
104 
105  typedef DerivedT Derived;
106 
107  // These have to be defined in the traits class.
108  typedef typename MeshTraitsT::VertexData VertexData;
109  typedef typename MeshTraitsT::HalfEdgeData HalfEdgeData;
110  typedef typename MeshTraitsT::EdgeData EdgeData;
111  typedef typename MeshTraitsT::FaceData FaceData;
112  typedef typename MeshTraitsT::IsManifold IsManifold;
113 
114  // Check if the mesh traits are defined correctly.
115  BOOST_CONCEPT_ASSERT ((boost::Convertible <IsManifold, bool>));
116 
117  typedef MeshTagT MeshTag;
118 
119  // Data
120  typedef boost::integral_constant <bool, !boost::is_same <VertexData , pcl::geometry::NoData>::value> HasVertexData;
121  typedef boost::integral_constant <bool, !boost::is_same <HalfEdgeData, pcl::geometry::NoData>::value> HasHalfEdgeData;
122  typedef boost::integral_constant <bool, !boost::is_same <EdgeData , pcl::geometry::NoData>::value> HasEdgeData;
123  typedef boost::integral_constant <bool, !boost::is_same <FaceData , pcl::geometry::NoData>::value> HasFaceData;
124 
129 
130  // Indices
135 
136  typedef std::vector <VertexIndex> VertexIndices;
137  typedef std::vector <HalfEdgeIndex> HalfEdgeIndices;
138  typedef std::vector <EdgeIndex> EdgeIndices;
139  typedef std::vector <FaceIndex> FaceIndices;
140 
141  // Circulators
150 
151  /** \brief Constructor. */
153  : vertex_data_cloud_ (),
154  half_edge_data_cloud_ (),
155  edge_data_cloud_ (),
156  face_data_cloud_ (),
157  vertices_ (),
158  half_edges_ (),
159  faces_ (),
160  inner_he_ (),
161  free_he_ (),
162  is_new_ (),
163  make_adjacent_ (),
164  is_boundary_ (),
165  delete_faces_vertex_ (),
166  delete_faces_face_ ()
167  {
168  }
169 
170  ////////////////////////////////////////////////////////////////////////
171  // addVertex / addFace / deleteVertex / deleteEdge / deleteFace / cleanUp
172  ////////////////////////////////////////////////////////////////////////
173 
174  /** \brief Add a vertex to the mesh.
175  * \param[in] vertex_data Data that is stored in the vertex. This is only added if the mesh has data associated with the vertices.
176  * \return Index to the new vertex.
177  */
178  inline VertexIndex
179  addVertex (const VertexData& vertex_data=VertexData ())
180  {
181  vertices_.push_back (Vertex ());
182  this->addData (vertex_data_cloud_, vertex_data, HasVertexData ());
183  return (VertexIndex (static_cast <int> (this->sizeVertices () - 1)));
184  }
185 
186  /** \brief Add a face to the mesh. Data is only added if it is associated with the elements. The last vertex is connected with the first one.
187  * \param[in] vertices Indices to the vertices of the new face.
188  * \param[in] face_data Data that is set for the face.
189  * \param[in] half_edge_data Data that is set for all added half-edges.
190  * \param[in] edge_data Data that is set for all added edges.
191  * \return Index to the new face. Failure is signaled by returning an invalid face index.
192  * \warning The vertices must be valid and unique (each vertex may be contained only once). Not complying with this requirement results in undefined behavior!
193  */
194  inline FaceIndex
195  addFace (const VertexIndices& vertices,
196  const FaceData& face_data = FaceData (),
197  const EdgeData& edge_data = EdgeData (),
198  const HalfEdgeData& half_edge_data = HalfEdgeData ())
199  {
200  // NOTE: The derived class has to implement addFaceImpl. If needed it can use the general method addFaceImplBase.
201  return (static_cast <Derived*> (this)->addFaceImpl (vertices, face_data, edge_data, half_edge_data));
202  }
203 
204  /** \brief Mark the given vertex and all connected half-edges and faces as deleted.
205  * \note Call cleanUp () to finally delete all mesh-elements.
206  */
207  void
208  deleteVertex (const VertexIndex& idx_vertex)
209  {
210  assert (this->isValid (idx_vertex));
211  if (this->isDeleted (idx_vertex)) return;
212 
213  delete_faces_vertex_.clear ();
214  FaceAroundVertexCirculator circ = this->getFaceAroundVertexCirculator (idx_vertex);
215  const FaceAroundVertexCirculator circ_end = circ;
216  do
217  {
218  if (circ.getTargetIndex ().isValid ()) // Check for boundary.
219  {
220  delete_faces_vertex_.push_back (circ.getTargetIndex ());
221  }
222  } while (++circ!=circ_end);
223 
224  for (FaceIndices::const_iterator it = delete_faces_vertex_.begin (); it!=delete_faces_vertex_.end (); ++it)
225  {
226  this->deleteFace (*it);
227  }
228  }
229 
230  /** \brief Mark the given half-edge, the opposite half-edge and the associated faces as deleted.
231  * \note Call cleanUp () to finally delete all mesh-elements.
232  */
233  void
234  deleteEdge (const HalfEdgeIndex& idx_he)
235  {
236  assert (this->isValid (idx_he));
237  if (this->isDeleted (idx_he)) return;
238 
239  HalfEdgeIndex opposite = this->getOppositeHalfEdgeIndex (idx_he);
240 
241  if (this->isBoundary (idx_he)) this->markDeleted (idx_he);
242  else this->deleteFace (this->getFaceIndex (idx_he));
243  if (this->isBoundary (opposite)) this->markDeleted (opposite);
244  else this->deleteFace (this->getFaceIndex (opposite));
245  }
246 
247  /** \brief Mark the given edge (both half-edges) and the associated faces as deleted.
248  * \note Call cleanUp () to finally delete all mesh-elements.
249  */
250  inline void
251  deleteEdge (const EdgeIndex& idx_edge)
252  {
253  assert (this->isValid (idx_edge));
254  this->deleteEdge (pcl::geometry::toHalfEdgeIndex (idx_edge));
255  assert (this->isDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, false))); // Bug in this class!
256  }
257 
258  /** \brief Mark the given face as deleted. More faces are deleted if the manifold mesh would become non-manifold.
259  * \note Call cleanUp () to finally delete all mesh-elements.
260  */
261  inline void
262  deleteFace (const FaceIndex& idx_face)
263  {
264  assert (this->isValid (idx_face));
265  if (this->isDeleted (idx_face)) return;
266 
267  this->deleteFace (idx_face, IsManifold ());
268  }
269 
270  /** \brief Removes all mesh elements and data that are marked as deleted.
271  * \note This removes all isolated vertices as well.
272  */
273  void
275  {
276  // Copy the non-deleted mesh elements and store the index to their new position
277  const VertexIndices new_vertex_indices =
278  this->remove <Vertices, VertexDataCloud, VertexIndices, HasVertexData>
279  (vertices_, vertex_data_cloud_);
280  const HalfEdgeIndices new_half_edge_indices =
281  this->remove <HalfEdges, HalfEdgeDataCloud, HalfEdgeIndices, HasHalfEdgeData>
282  (half_edges_, half_edge_data_cloud_);
283  const FaceIndices new_face_indices =
284  this->remove <Faces, FaceDataCloud, FaceIndices, HasFaceData>
285  (faces_, face_data_cloud_);
286 
287  // Remove deleted edge data
288  if (HasEdgeData::value)
289  {
290  auto it_ed_old = edge_data_cloud_.begin ();
291  auto it_ed_new = edge_data_cloud_.begin ();
292 
293  for (auto it_ind = new_half_edge_indices.cbegin (), it_ind_end = new_half_edge_indices.cend (); it_ind!=it_ind_end; it_ind+=2, ++it_ed_old)
294  {
295  if (it_ind->isValid ())
296  {
297  *it_ed_new++ = *it_ed_old;
298  }
299  }
300  edge_data_cloud_.resize (this->sizeEdges ());
301  }
302 
303  // Adjust the indices
304  for (VertexIterator it = vertices_.begin (); it!=vertices_.end (); ++it)
305  {
306  if (it->idx_outgoing_half_edge_.isValid ())
307  {
308  it->idx_outgoing_half_edge_ = new_half_edge_indices [it->idx_outgoing_half_edge_.get ()];
309  }
310  }
311 
312  for (HalfEdgeIterator it = half_edges_.begin (); it!=half_edges_.end (); ++it)
313  {
314  it->idx_terminating_vertex_ = new_vertex_indices [it->idx_terminating_vertex_.get ()];
315  it->idx_next_half_edge_ = new_half_edge_indices [it->idx_next_half_edge_.get ()];
316  it->idx_prev_half_edge_ = new_half_edge_indices [it->idx_prev_half_edge_.get ()];
317  if (it->idx_face_.isValid ())
318  {
319  it->idx_face_ = new_face_indices [it->idx_face_.get ()];
320  }
321  }
322 
323  for (FaceIterator it = faces_.begin (); it!=faces_.end (); ++it)
324  {
325  it->idx_inner_half_edge_ = new_half_edge_indices [it->idx_inner_half_edge_.get ()];
326  }
327  }
328 
329  ////////////////////////////////////////////////////////////////////////
330  // Vertex connectivity
331  ////////////////////////////////////////////////////////////////////////
332 
333  /** \brief Get the outgoing half-edge index to a given vertex. */
334  inline HalfEdgeIndex
335  getOutgoingHalfEdgeIndex (const VertexIndex& idx_vertex) const
336  {
337  assert (this->isValid (idx_vertex));
338  return (this->getVertex (idx_vertex).idx_outgoing_half_edge_);
339  }
340 
341  /** \brief Get the incoming half-edge index to a given vertex. */
342  inline HalfEdgeIndex
343  getIncomingHalfEdgeIndex (const VertexIndex& idx_vertex) const
344  {
345  assert (this->isValid (idx_vertex));
346  return (this->getOppositeHalfEdgeIndex (this->getOutgoingHalfEdgeIndex (idx_vertex)));
347  }
348 
349  ////////////////////////////////////////////////////////////////////////
350  // Half-edge connectivity
351  ////////////////////////////////////////////////////////////////////////
352 
353  /** \brief Get the terminating vertex index to a given half-edge. */
354  inline VertexIndex
355  getTerminatingVertexIndex (const HalfEdgeIndex& idx_half_edge) const
356  {
357  assert (this->isValid (idx_half_edge));
358  return (this->getHalfEdge (idx_half_edge).idx_terminating_vertex_);
359  }
360 
361  /** \brief Get the originating vertex index to a given half-edge. */
362  inline VertexIndex
363  getOriginatingVertexIndex (const HalfEdgeIndex& idx_half_edge) const
364  {
365  assert (this->isValid (idx_half_edge));
366  return (this->getTerminatingVertexIndex (this->getOppositeHalfEdgeIndex (idx_half_edge)));
367  }
368 
369  /** \brief Get the opposite half-edge index to a given half-edge. */
370  inline HalfEdgeIndex
371  getOppositeHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge) const
372  {
373  assert (this->isValid (idx_half_edge));
374  // Check if the index is even or odd and return the other index.
375  return (HalfEdgeIndex (idx_half_edge.get () & 1 ? idx_half_edge.get () - 1 : idx_half_edge.get () + 1));
376  }
377 
378  /** \brief Get the next half-edge index to a given half-edge. */
379  inline HalfEdgeIndex
380  getNextHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge) const
381  {
382  assert (this->isValid (idx_half_edge));
383  return (this->getHalfEdge (idx_half_edge).idx_next_half_edge_);
384  }
385 
386  /** \brief Get the previous half-edge index to a given half-edge. */
387  inline HalfEdgeIndex
388  getPrevHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge) const
389  {
390  assert (this->isValid (idx_half_edge));
391  return (this->getHalfEdge (idx_half_edge).idx_prev_half_edge_);
392  }
393 
394  /** \brief Get the face index to a given half-edge. */
395  inline FaceIndex
396  getFaceIndex (const HalfEdgeIndex& idx_half_edge) const
397  {
398  assert (this->isValid (idx_half_edge));
399  return (this->getHalfEdge (idx_half_edge).idx_face_);
400  }
401 
402  /** \brief Get the face index to a given half-edge. */
403  inline FaceIndex
404  getOppositeFaceIndex (const HalfEdgeIndex& idx_half_edge) const
405  {
406  assert (this->isValid (idx_half_edge));
407  return (this->getFaceIndex (this->getOppositeHalfEdgeIndex (idx_half_edge)));
408  }
409 
410  ////////////////////////////////////////////////////////////////////////
411  // Face connectivity
412  ////////////////////////////////////////////////////////////////////////
413 
414  /** \brief Get the inner half-edge index to a given face. */
415  inline HalfEdgeIndex
416  getInnerHalfEdgeIndex (const FaceIndex& idx_face) const
417  {
418  assert (this->isValid (idx_face));
419  return (this->getFace (idx_face).idx_inner_half_edge_);
420  }
421 
422  /** \brief Get the outer half-edge inex to a given face. */
423  inline HalfEdgeIndex
424  getOuterHalfEdgeIndex (const FaceIndex& idx_face) const
425  {
426  assert (this->isValid (idx_face));
427  return (this->getOppositeHalfEdgeIndex (this->getInnerHalfEdgeIndex (idx_face)));
428  }
429 
430  ////////////////////////////////////////////////////////////////////////
431  // Circulators
432  ////////////////////////////////////////////////////////////////////////
433 
434  /** \see pcl::geometry::VertexAroundVertexCirculator */
435  inline VertexAroundVertexCirculator
436  getVertexAroundVertexCirculator (const VertexIndex& idx_vertex) const
437  {
438  assert (this->isValid (idx_vertex));
439  return (VertexAroundVertexCirculator (idx_vertex, this));
440  }
441 
442  /** \see pcl::geometry::VertexAroundVertexCirculator */
443  inline VertexAroundVertexCirculator
444  getVertexAroundVertexCirculator (const HalfEdgeIndex& idx_outgoing_half_edge) const
445  {
446  assert (this->isValid (idx_outgoing_half_edge));
447  return (VertexAroundVertexCirculator (idx_outgoing_half_edge, this));
448  }
449 
450  /** \see pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator */
451  inline OutgoingHalfEdgeAroundVertexCirculator
452  getOutgoingHalfEdgeAroundVertexCirculator (const VertexIndex& idx_vertex) const
453  {
454  assert (this->isValid (idx_vertex));
455  return (OutgoingHalfEdgeAroundVertexCirculator (idx_vertex, this));
456  }
457 
458  /** \see pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator */
459  inline OutgoingHalfEdgeAroundVertexCirculator
460  getOutgoingHalfEdgeAroundVertexCirculator (const HalfEdgeIndex& idx_outgoing_half_edge) const
461  {
462  assert (this->isValid (idx_outgoing_half_edge));
463  return (OutgoingHalfEdgeAroundVertexCirculator (idx_outgoing_half_edge, this));
464  }
465 
466  /** \see pcl::geometry::IncomingHalfEdgeAroundVertexCirculator */
467  inline IncomingHalfEdgeAroundVertexCirculator
468  getIncomingHalfEdgeAroundVertexCirculator (const VertexIndex& idx_vertex) const
469  {
470  assert (this->isValid (idx_vertex));
471  return (IncomingHalfEdgeAroundVertexCirculator (idx_vertex, this));
472  }
473 
474  /** \see pcl::geometry::IncomingHalfEdgeAroundVertexCirculator */
475  inline IncomingHalfEdgeAroundVertexCirculator
476  getIncomingHalfEdgeAroundVertexCirculator (const HalfEdgeIndex& idx_incoming_half_edge) const
477  {
478  assert (this->isValid (idx_incoming_half_edge));
479  return (IncomingHalfEdgeAroundVertexCirculator (idx_incoming_half_edge, this));
480  }
481 
482  /** \see pcl::geometry::FaceAroundVertexCirculator */
483  inline FaceAroundVertexCirculator
484  getFaceAroundVertexCirculator (const VertexIndex& idx_vertex) const
485  {
486  assert (this->isValid (idx_vertex));
487  return (FaceAroundVertexCirculator (idx_vertex, this));
488  }
489 
490  /** \see pcl::geometry::FaceAroundVertexCirculator */
491  inline FaceAroundVertexCirculator
492  getFaceAroundVertexCirculator (const HalfEdgeIndex& idx_outgoing_half_edge) const
493  {
494  assert (this->isValid (idx_outgoing_half_edge));
495  return (FaceAroundVertexCirculator (idx_outgoing_half_edge, this));
496  }
497 
498  /** \see pcl::geometry::VertexAroundFaceCirculator */
499  inline VertexAroundFaceCirculator
500  getVertexAroundFaceCirculator (const FaceIndex& idx_face) const
501  {
502  assert (this->isValid (idx_face));
503  return (VertexAroundFaceCirculator (idx_face, this));
504  }
505 
506  /** \see pcl::geometry::VertexAroundFaceCirculator */
507  inline VertexAroundFaceCirculator
508  getVertexAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const
509  {
510  assert (this->isValid (idx_inner_half_edge));
511  return (VertexAroundFaceCirculator (idx_inner_half_edge, this));
512  }
513 
514  /** \see pcl::geometry::InnerHalfEdgeAroundFaceCirculator */
515  inline InnerHalfEdgeAroundFaceCirculator
516  getInnerHalfEdgeAroundFaceCirculator (const FaceIndex& idx_face) const
517  {
518  assert (this->isValid (idx_face));
519  return (InnerHalfEdgeAroundFaceCirculator (idx_face, this));
520  }
521 
522  /** \see pcl::geometry::InnerHalfEdgeAroundFaceCirculator */
523  inline InnerHalfEdgeAroundFaceCirculator
524  getInnerHalfEdgeAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const
525  {
526  assert (this->isValid (idx_inner_half_edge));
527  return (InnerHalfEdgeAroundFaceCirculator (idx_inner_half_edge, this));
528  }
529 
530  /** \see pcl::geometry::OuterHalfEdgeAroundFaceCirculator */
531  inline OuterHalfEdgeAroundFaceCirculator
532  getOuterHalfEdgeAroundFaceCirculator (const FaceIndex& idx_face) const
533  {
534  assert (this->isValid (idx_face));
535  return (OuterHalfEdgeAroundFaceCirculator (idx_face, this));
536  }
537 
538  /** \see pcl::geometry::OuterHalfEdgeAroundFaceCirculator */
539  inline OuterHalfEdgeAroundFaceCirculator
540  getOuterHalfEdgeAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const
541  {
542  assert (this->isValid (idx_inner_half_edge));
543  return (OuterHalfEdgeAroundFaceCirculator (idx_inner_half_edge, this));
544  }
545 
546  /** \see pcl::geometry::FaceAroundFaceCirculator */
547  inline FaceAroundFaceCirculator
548  getFaceAroundFaceCirculator (const FaceIndex& idx_face) const
549  {
550  assert (this->isValid (idx_face));
551  return (FaceAroundFaceCirculator (idx_face, this));
552  }
553 
554  /** \see pcl::geometry::FaceAroundFaceCirculator */
555  inline FaceAroundFaceCirculator
556  getFaceAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const
557  {
558  assert (this->isValid (idx_inner_half_edge));
559  return (FaceAroundFaceCirculator (idx_inner_half_edge, this));
560  }
561 
562  //////////////////////////////////////////////////////////////////////////
563  // isEqualTopology
564  //////////////////////////////////////////////////////////////////////////
565 
566  /** \brief Check if the other mesh has the same topology as this mesh. */
567  bool
568  isEqualTopology (const Self& other) const
569  {
570  if (this->sizeVertices () != other.sizeVertices ()) return (false);
571  if (this->sizeHalfEdges () != other.sizeHalfEdges ()) return (false);
572  if (this->sizeFaces () != other.sizeFaces ()) return (false);
573 
574  for (size_t i=0; i<this->sizeVertices (); ++i)
575  {
576  if (this->getOutgoingHalfEdgeIndex (VertexIndex (i)) !=
577  other.getOutgoingHalfEdgeIndex (VertexIndex (i))) return (false);
578  }
579 
580  for (size_t i=0; i<this->sizeHalfEdges (); ++i)
581  {
582  if (this->getTerminatingVertexIndex (HalfEdgeIndex (i)) !=
583  other.getTerminatingVertexIndex (HalfEdgeIndex (i))) return (false);
584 
585  if (this->getNextHalfEdgeIndex (HalfEdgeIndex (i)) !=
586  other.getNextHalfEdgeIndex (HalfEdgeIndex (i))) return (false);
587 
588  if (this->getPrevHalfEdgeIndex (HalfEdgeIndex (i)) !=
589  other.getPrevHalfEdgeIndex (HalfEdgeIndex (i))) return (false);
590 
591  if (this->getFaceIndex (HalfEdgeIndex (i)) !=
592  other.getFaceIndex (HalfEdgeIndex (i))) return (false);
593  }
594 
595  for (size_t i=0; i<this->sizeFaces (); ++i)
596  {
597  if (this->getInnerHalfEdgeIndex (FaceIndex (i)) !=
598  other.getInnerHalfEdgeIndex (FaceIndex (i))) return (false);
599  }
600 
601  return (true);
602  }
603 
604  ////////////////////////////////////////////////////////////////////////
605  // isValid
606  ////////////////////////////////////////////////////////////////////////
607 
608  /** \brief Check if the given vertex index is a valid index into the mesh. */
609  inline bool
610  isValid (const VertexIndex& idx_vertex) const
611  {
612  return (idx_vertex >= VertexIndex (0) && idx_vertex < VertexIndex (int (vertices_.size ())));
613  }
614 
615  /** \brief Check if the given half-edge index is a valid index into the mesh. */
616  inline bool
617  isValid (const HalfEdgeIndex& idx_he) const
618  {
619  return (idx_he >= HalfEdgeIndex (0) && idx_he < HalfEdgeIndex (half_edges_.size ()));
620  }
621 
622  /** \brief Check if the given edge index is a valid index into the mesh. */
623  inline bool
624  isValid (const EdgeIndex& idx_edge) const
625  {
626  return (idx_edge >= EdgeIndex (0) && idx_edge < EdgeIndex (half_edges_.size () / 2));
627  }
628 
629  /** \brief Check if the given face index is a valid index into the mesh. */
630  inline bool
631  isValid (const FaceIndex& idx_face) const
632  {
633  return (idx_face >= FaceIndex (0) && idx_face < FaceIndex (faces_.size ()));
634  }
635 
636  ////////////////////////////////////////////////////////////////////////
637  // isDeleted
638  ////////////////////////////////////////////////////////////////////////
639 
640  /** \brief Check if the given vertex is marked as deleted. */
641  inline bool
642  isDeleted (const VertexIndex& idx_vertex) const
643  {
644  assert (this->isValid (idx_vertex));
645  return (!this->getOutgoingHalfEdgeIndex (idx_vertex).isValid ());
646  }
647 
648  /** \brief Check if the given half-edge is marked as deleted. */
649  inline bool
650  isDeleted (const HalfEdgeIndex& idx_he) const
651  {
652  assert (this->isValid (idx_he));
653  return (!this->getTerminatingVertexIndex (idx_he).isValid ());
654  }
655 
656  /** \brief Check if the given edge (any of the two half-edges) is marked as deleted. */
657  inline bool
658  isDeleted (const EdgeIndex& idx_edge) const
659  {
660  assert (this->isValid (idx_edge));
661  return (this->isDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, true)) ||
662  this->isDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, false)));
663  }
664 
665  /** \brief Check if the given face is marked as deleted. */
666  inline bool
667  isDeleted (const FaceIndex& idx_face) const
668  {
669  assert (this->isValid (idx_face));
670  return (!this->getInnerHalfEdgeIndex (idx_face).isValid ());
671  }
672 
673  ////////////////////////////////////////////////////////////////////////
674  // isIsolated
675  ////////////////////////////////////////////////////////////////////////
676 
677  /** \brief Check if the given vertex is isolated (not connected to other elements). */
678  inline bool
679  isIsolated (const VertexIndex& idx_vertex) const
680  {
681  assert (this->isValid (idx_vertex));
682  return (!this->getOutgoingHalfEdgeIndex (idx_vertex).isValid ());
683  }
684 
685  ////////////////////////////////////////////////////////////////////////
686  // isBoundary
687  ////////////////////////////////////////////////////////////////////////
688 
689  /** \brief Check if the given vertex lies on the boundary. Isolated vertices are considered to be on the boundary. */
690  inline bool
691  isBoundary (const VertexIndex& idx_vertex) const
692  {
693  assert (this->isValid (idx_vertex));
694  if (this->isIsolated (idx_vertex)) return (true);
695  return (this->isBoundary (this->getOutgoingHalfEdgeIndex (idx_vertex)));
696  }
697 
698  /** \brief Check if the given half-edge lies on the bounddary. */
699  inline bool
700  isBoundary (const HalfEdgeIndex& idx_he) const
701  {
702  assert (this->isValid (idx_he));
703  return (!this->getFaceIndex (idx_he).isValid ());
704  }
705 
706  /** \brief Check if the given edge lies on the boundary (any of the two half-edges lies on the boundary. */
707  inline bool
708  isBoundary (const EdgeIndex& idx_edge) const
709  {
710  assert (this->isValid (idx_edge));
711  const HalfEdgeIndex& idx = pcl::geometry::toHalfEdgeIndex (idx_edge);
712  return (this->isBoundary (idx) || this->isBoundary (this->getOppositeHalfEdgeIndex (idx)));
713  }
714 
715  /** \brief Check if the given face lies on the boundary. There are two versions of this method, selected by the template parameter.
716  * \tparam CheckVerticesT Check if any vertex lies on the boundary (true) or check if any edge lies on the boundary (false).
717  */
718  template <bool CheckVerticesT> inline bool
719  isBoundary (const FaceIndex& idx_face) const
720  {
721  assert (this->isValid (idx_face));
722  return (this->isBoundary (idx_face, boost::integral_constant <bool, CheckVerticesT> ()));
723  }
724 
725  /** \brief Check if the given face lies on the boundary. This method uses isBoundary \c true which checks if any vertex lies on the boundary. */
726  inline bool
727  isBoundary (const FaceIndex& idx_face) const
728  {
729  assert (this->isValid (idx_face));
730  return (this->isBoundary (idx_face, boost::true_type ()));
731  }
732 
733  ////////////////////////////////////////////////////////////////////////
734  // isManifold
735  ////////////////////////////////////////////////////////////////////////
736 
737  /** \brief Check if the given vertex is manifold. Isolated vertices are manifold. */
738  inline bool
739  isManifold (const VertexIndex& idx_vertex) const
740  {
741  assert (this->isValid (idx_vertex));
742  if (this->isIsolated (idx_vertex)) return (true);
743  return (this->isManifold (idx_vertex, IsManifold ()));
744  }
745 
746  /** \brief Check if the mesh is manifold. */
747  inline bool
748  isManifold () const
749  {
750  return (this->isManifold (IsManifold ()));
751  }
752 
753  ////////////////////////////////////////////////////////////////////////
754  // size
755  ////////////////////////////////////////////////////////////////////////
756 
757  /** \brief Get the number of the vertices. */
758  inline size_t
759  sizeVertices () const
760  {
761  return (vertices_.size ());
762  }
763 
764  /** \brief Get the number of the half-edges. */
765  inline size_t
766  sizeHalfEdges () const
767  {
768  assert (half_edges_.size () % 2 == 0); // This would be a bug in the mesh.
769  return (half_edges_.size ());
770  }
771 
772  /** \brief Get the number of the edges. */
773  inline size_t
774  sizeEdges () const
775  {
776  assert (half_edges_.size () % 2 == 0); // This would be a bug in the mesh.
777  return (half_edges_.size () / 2);
778  }
779 
780  /** \brief Get the number of the faces. */
781  inline size_t
782  sizeFaces () const
783  {
784  return (faces_.size ());
785  }
786 
787  ////////////////////////////////////////////////////////////////////////
788  // empty
789  ////////////////////////////////////////////////////////////////////////
790 
791  /** \brief Check if the mesh is empty. */
792  inline bool
793  empty () const
794  {
795  return (this->emptyVertices () && this->emptyEdges () && this->emptyFaces ());
796  }
797 
798  /** \brief Check if the vertices are empty. */
799  inline bool
800  emptyVertices () const
801  {
802  return (vertices_.empty ());
803  }
804 
805  /** \brief Check if the edges are empty. */
806  inline bool
807  emptyEdges () const
808  {
809  return (half_edges_.empty ());
810  }
811 
812  /** \brief Check if the faces are empty. */
813  inline bool
814  emptyFaces () const
815  {
816  return (faces_.empty ());
817  }
818 
819  ////////////////////////////////////////////////////////////////////////
820  // reserve
821  ////////////////////////////////////////////////////////////////////////
822 
823  /** \brief Reserve storage space n vertices. */
824  inline void
825  reserveVertices (const size_t n)
826  {
827  vertices_.reserve (n);
828  this->reserveData (vertex_data_cloud_, n, HasVertexData ());
829  }
830 
831  /** \brief Reserve storage space for n edges (2*n storage space is reserved for the half-edges). */
832  inline void
833  reserveEdges (const size_t n)
834  {
835  half_edges_.reserve (2*n);
836  this->reserveData (half_edge_data_cloud_, 2*n, HasHalfEdgeData ());
837  this->reserveData (edge_data_cloud_ , n, HasEdgeData ());
838  }
839 
840  /** \brief Reserve storage space for n faces. */
841  inline void
842  reserveFaces (const size_t n)
843  {
844  faces_.reserve (n);
845  this->reserveData (face_data_cloud_, n, HasFaceData ());
846  }
847 
848  ////////////////////////////////////////////////////////////////////////
849  // resize
850  ////////////////////////////////////////////////////////////////////////
851 
852  /** \brief Resize the the vertices to n elements. */
853  inline void
854  resizeVertices (const size_t n, const VertexData& data = VertexData ())
855  {
856  vertices_.resize (n);
857  this->resizeData (vertex_data_cloud_, n, data, HasVertexData ());
858  }
859 
860  /** \brief Resize the edges to n elements (half-edges will hold 2*n elements). */
861  inline void
862  resizeEdges (const size_t n,
863  const EdgeData& edge_data = EdgeData (),
864  const HalfEdgeData he_data = HalfEdgeData ())
865  {
866  half_edges_.resize (2*n);
867  this->resizeData (half_edge_data_cloud_, 2*n, he_data , HasHalfEdgeData ());
868  this->resizeData (edge_data_cloud_ , n, edge_data, HasEdgeData ());
869  }
870 
871  /** \brief Resize the faces to n elements. */
872  inline void
873  resizeFaces (const size_t n, const FaceData& data = FaceData ())
874  {
875  faces_.resize (n);
876  this->resizeData (face_data_cloud_, n, data, HasFaceData ());
877  }
878 
879  ////////////////////////////////////////////////////////////////////////
880  // clear
881  ////////////////////////////////////////////////////////////////////////
882 
883  /** \brief Clear all mesh elements and data. */
884  void
885  clear ()
886  {
887  vertices_.clear ();
888  half_edges_.clear ();
889  faces_.clear ();
890 
891  this->clearData (vertex_data_cloud_ , HasVertexData ());
892  this->clearData (half_edge_data_cloud_, HasHalfEdgeData ());
893  this->clearData (edge_data_cloud_ , HasEdgeData ());
894  this->clearData (face_data_cloud_ , HasFaceData ());
895  }
896 
897  ////////////////////////////////////////////////////////////////////////
898  // get / set the vertex data cloud
899  ////////////////////////////////////////////////////////////////////////
900 
901  /** \brief Get access to the stored vertex data.
902  * \warning Please make sure to NOT add or remove elements from the cloud.
903  */
904  inline VertexDataCloud&
906  {
907  return (vertex_data_cloud_);
908  }
909 
910  /** \brief Get the stored vertex data. */
911  inline VertexDataCloud
913  {
914  return (vertex_data_cloud_);
915  }
916 
917  /** \brief Change the stored vertex data.
918  * \param[in] vertex_data_cloud The new vertex data. Must be the same as the current data.
919  * \return true if the cloud could be set.
920  */
921  inline bool
922  setVertexDataCloud (const VertexDataCloud& vertex_data_cloud)
923  {
924  if (vertex_data_cloud.size () == vertex_data_cloud_.size ())
925  {
926  vertex_data_cloud_ = vertex_data_cloud;
927  return (true);
928  }
929  else
930  {
931  return (false);
932  }
933  }
934 
935  ////////////////////////////////////////////////////////////////////////
936  // get / set the half-edge data cloud
937  ////////////////////////////////////////////////////////////////////////
938 
939  /** \brief Get access to the stored half-edge data.
940  * \warning Please make sure to NOT add or remove elements from the cloud.
941  */
942  inline HalfEdgeDataCloud&
944  {
945  return (half_edge_data_cloud_);
946  }
947 
948  /** \brief Get the stored half-edge data. */
949  inline HalfEdgeDataCloud
951  {
952  return (half_edge_data_cloud_);
953  }
954 
955  /** \brief Change the stored half-edge data.
956  * \param[in] half_edge_data_cloud The new half-edge data. Must be the same as the current data.
957  * \return true if the cloud could be set.
958  */
959  inline bool
960  setHalfEdgeDataCloud (const HalfEdgeDataCloud& half_edge_data_cloud)
961  {
962  if (half_edge_data_cloud.size () == half_edge_data_cloud_.size ())
963  {
964  half_edge_data_cloud_ = half_edge_data_cloud;
965  return (true);
966  }
967  else
968  {
969  return (false);
970  }
971  }
972 
973  ////////////////////////////////////////////////////////////////////////
974  // get / set the edge data cloud
975  ////////////////////////////////////////////////////////////////////////
976 
977  /** \brief Get access to the stored edge data.
978  * \warning Please make sure to NOT add or remove elements from the cloud.
979  */
980  inline EdgeDataCloud&
982  {
983  return (edge_data_cloud_);
984  }
985 
986  /** \brief Get the stored edge data. */
987  inline EdgeDataCloud
989  {
990  return (edge_data_cloud_);
991  }
992 
993  /** \brief Change the stored edge data.
994  * \param[in] edge_data_cloud The new edge data. Must be the same as the current data.
995  * \return true if the cloud could be set.
996  */
997  inline bool
998  setEdgeDataCloud (const EdgeDataCloud& edge_data_cloud)
999  {
1000  if (edge_data_cloud.size () == edge_data_cloud_.size ())
1001  {
1002  edge_data_cloud_ = edge_data_cloud;
1003  return (true);
1004  }
1005  else
1006  {
1007  return (false);
1008  }
1009  }
1010 
1011  ////////////////////////////////////////////////////////////////////////
1012  // get / set the face data cloud
1013  ////////////////////////////////////////////////////////////////////////
1014 
1015  /** \brief Get access to the stored face data.
1016  * \warning Please make sure to NOT add or remove elements from the cloud.
1017  */
1018  inline FaceDataCloud&
1020  {
1021  return (face_data_cloud_);
1022  }
1023 
1024  /** \brief Get the stored face data. */
1025  inline FaceDataCloud
1027  {
1028  return (face_data_cloud_);
1029  }
1030 
1031  /** \brief Change the stored face data.
1032  * \param[in] face_data_cloud The new face data. Must be the same as the current data.
1033  * \return true if the cloud could be set.
1034  */
1035  inline bool
1036  setFaceDataCloud (const FaceDataCloud& face_data_cloud)
1037  {
1038  if (face_data_cloud.size () == face_data_cloud_.size ())
1039  {
1040  face_data_cloud_ = face_data_cloud;
1041  return (true);
1042  }
1043  else
1044  {
1045  return (false);
1046  }
1047  }
1048 
1049  ////////////////////////////////////////////////////////////////////////
1050  // getVertexIndex / getHalfEdgeIndex / getEdgeIndex / getFaceIndex
1051  ////////////////////////////////////////////////////////////////////////
1052 
1053  /** \brief Get the index associated to the given vertex data.
1054  * \return Invalid index if the mesh does not have associated vertex data.
1055  */
1056  inline VertexIndex
1057  getVertexIndex (const VertexData& vertex_data) const
1058  {
1059  if (HasVertexData::value)
1060  {
1061  assert (&vertex_data >= &vertex_data_cloud_.front () && &vertex_data <= &vertex_data_cloud_.back ());
1062  return (VertexIndex (std::distance (&vertex_data_cloud_.front (), &vertex_data)));
1063  }
1064  else
1065  {
1066  return (VertexIndex ());
1067  }
1068  }
1069 
1070  /** \brief Get the index associated to the given half-edge data. */
1071  inline HalfEdgeIndex
1072  getHalfEdgeIndex (const HalfEdgeData& half_edge_data) const
1073  {
1074  if (HasHalfEdgeData::value)
1075  {
1076  assert (&half_edge_data >= &half_edge_data_cloud_.front () && &half_edge_data <= &half_edge_data_cloud_.back ());
1077  return (HalfEdgeIndex (std::distance (&half_edge_data_cloud_.front (), &half_edge_data)));
1078  }
1079  else
1080  {
1081  return (HalfEdgeIndex ());
1082  }
1083  }
1084 
1085  /** \brief Get the index associated to the given edge data. */
1086  inline EdgeIndex
1087  getEdgeIndex (const EdgeData& edge_data) const
1088  {
1089  if (HasEdgeData::value)
1090  {
1091  assert (&edge_data >= &edge_data_cloud_.front () && &edge_data <= &edge_data_cloud_.back ());
1092  return (EdgeIndex (std::distance (&edge_data_cloud_.front (), &edge_data)));
1093  }
1094  else
1095  {
1096  return (EdgeIndex ());
1097  }
1098  }
1099 
1100  /** \brief Get the index associated to the given face data. */
1101  inline FaceIndex
1102  getFaceIndex (const FaceData& face_data) const
1103  {
1104  if (HasFaceData::value)
1105  {
1106  assert (&face_data >= &face_data_cloud_.front () && &face_data <= &face_data_cloud_.back ());
1107  return (FaceIndex (std::distance (&face_data_cloud_.front (), &face_data)));
1108  }
1109  else
1110  {
1111  return (FaceIndex ());
1112  }
1113  }
1114 
1115  protected:
1116 
1117  ////////////////////////////////////////////////////////////////////////
1118  // Types
1119  ////////////////////////////////////////////////////////////////////////
1120 
1121  // Elements
1125 
1126  typedef std::vector <Vertex> Vertices;
1127  typedef std::vector <HalfEdge> HalfEdges;
1128  typedef std::vector <Face> Faces;
1129 
1130  typedef typename Vertices::iterator VertexIterator;
1131  typedef typename HalfEdges::iterator HalfEdgeIterator;
1132  typedef typename Faces::iterator FaceIterator;
1133 
1134  typedef typename Vertices::const_iterator VertexConstIterator;
1135  typedef typename HalfEdges::const_iterator HalfEdgeConstIterator;
1136  typedef typename Faces::const_iterator FaceConstIterator;
1137 
1138  /** \brief General implementation of addFace. */
1139  FaceIndex
1140  addFaceImplBase (const VertexIndices& vertices,
1141  const FaceData& face_data,
1142  const EdgeData& edge_data,
1143  const HalfEdgeData& half_edge_data)
1144  {
1145  const int n = static_cast<int> (vertices.size ());
1146  if (n < 3) return (FaceIndex ());
1147 
1148  // Check for topological errors
1149  inner_he_.resize (n);
1150  free_he_.resize (n);
1151  is_new_.resize (n);
1152  make_adjacent_.resize (n);
1153  for (int i=0; i<n; ++i)
1154  {
1155  if (!this->checkTopology1 (vertices [i], vertices [(i+1)%n], inner_he_ [i], is_new_ [i], IsManifold ()))
1156  {
1157  return (FaceIndex ());
1158  }
1159  }
1160  for (int i=0; i<n; ++i)
1161  {
1162  int j = (i+1)%n;
1163  if (!this->checkTopology2 (inner_he_ [i], inner_he_ [j], is_new_ [i], is_new_ [j], this->isIsolated (vertices [j]), make_adjacent_ [i], free_he_ [i], IsManifold ()))
1164  {
1165  return (FaceIndex ());
1166  }
1167  }
1168 
1169  // Reconnect the existing half-edges if needed
1170  if (!IsManifold::value)
1171  {
1172  for (int i=0; i<n; ++i)
1173  {
1174  if (make_adjacent_ [i])
1175  {
1176  this->makeAdjacent (inner_he_ [i], inner_he_ [(i+1)%n], free_he_ [i]);
1177  }
1178  }
1179  }
1180 
1181  // Add new half-edges if needed
1182  for (int i=0; i<n; ++i)
1183  {
1184  if (is_new_ [i])
1185  {
1186  inner_he_ [i] = this->addEdge (vertices [i], vertices [(i+1)%n], half_edge_data, edge_data);
1187  }
1188  }
1189 
1190  // Connect
1191  for (int i=0; i<n; ++i)
1192  {
1193  int j = (i+1)%n;
1194  if ( is_new_ [i] && is_new_ [j]) this->connectNewNew (inner_he_ [i], inner_he_ [j], vertices [j], IsManifold ());
1195  else if ( is_new_ [i] && !is_new_ [j]) this->connectNewOld (inner_he_ [i], inner_he_ [j], vertices [j]);
1196  else if (!is_new_ [i] && is_new_ [j]) this->connectOldNew (inner_he_ [i], inner_he_ [j], vertices [j]);
1197  else this->connectOldOld (inner_he_ [i], inner_he_ [j], vertices [j], IsManifold ());
1198  }
1199  return (this->connectFace (inner_he_, face_data));
1200  }
1201 
1202  ////////////////////////////////////////////////////////////////////////
1203  // addEdge
1204  ////////////////////////////////////////////////////////////////////////
1205 
1206  /** \brief Add an edge between the two given vertices and connect them with the vertices.
1207  * \param[in] idx_v_a The first vertex index
1208  * \param[in] idx_v_b The second vertex index
1209  * \param[in] he_data Data associated with the half-edges. This is only added if the mesh has data associated with the half-edges.
1210  * \param[in] edge_data Data associated with the edge. This is only added if the mesh has data associated with the edges.
1211  * \return Index to the half-edge from vertex a to vertex b.
1212  */
1213  HalfEdgeIndex
1214  addEdge (const VertexIndex& idx_v_a,
1215  const VertexIndex& idx_v_b,
1216  const HalfEdgeData& he_data,
1217  const EdgeData& edge_data)
1218  {
1219  half_edges_.push_back (HalfEdge (idx_v_b));
1220  half_edges_.push_back (HalfEdge (idx_v_a));
1221 
1222  this->addData (half_edge_data_cloud_, he_data , HasHalfEdgeData ());
1223  this->addData (half_edge_data_cloud_, he_data , HasHalfEdgeData ());
1224  this->addData (edge_data_cloud_ , edge_data, HasEdgeData ());
1225 
1226  return (HalfEdgeIndex (static_cast <int> (half_edges_.size () - 2)));
1227  }
1228 
1229  ////////////////////////////////////////////////////////////////////////
1230  // topology checks
1231  ////////////////////////////////////////////////////////////////////////
1232 
1233  /** \brief Check if the edge between the two vertices can be added.
1234  * \param[in] idx_v_a Index to the first vertex.
1235  * \param[in] idx_v_b Index to the second vertex.
1236  * \param[out] idx_he_ab Index to the half-edge ab if is_new_ab=false.
1237  * \param[out] is_new_ab true if the edge between the vertices exists already. Must be initialized with true!
1238  * \return true if the half-edge may be added.
1239  */
1240  bool
1241  checkTopology1 (const VertexIndex& idx_v_a,
1242  const VertexIndex& idx_v_b,
1243  HalfEdgeIndex& idx_he_ab,
1244  std::vector <bool>::reference is_new_ab,
1245  boost::true_type /*is_manifold*/) const
1246  {
1247  is_new_ab = true;
1248  if (this->isIsolated (idx_v_a)) return (true);
1249 
1250  idx_he_ab = this->getOutgoingHalfEdgeIndex (idx_v_a);
1251 
1252  if (!this->isBoundary (idx_he_ab)) return (false);
1253  if (this->getTerminatingVertexIndex (idx_he_ab) == idx_v_b) is_new_ab = false;
1254  return (true);
1255  }
1256 
1257  /** \brief Non manifold version of checkTopology1 */
1258  bool
1259  checkTopology1 (const VertexIndex& idx_v_a,
1260  const VertexIndex& idx_v_b,
1261  HalfEdgeIndex& idx_he_ab,
1262  std::vector <bool>::reference is_new_ab,
1263  boost::false_type /*is_manifold*/) const
1264  {
1265  is_new_ab = true;
1266  if (this->isIsolated (idx_v_a)) return (true);
1267  if (!this->isBoundary (this->getOutgoingHalfEdgeIndex (idx_v_a))) return (false);
1268 
1269  VertexAroundVertexCirculator circ = this->getVertexAroundVertexCirculator (this->getOutgoingHalfEdgeIndex (idx_v_a));
1270  const VertexAroundVertexCirculator circ_end = circ;
1271 
1272  do
1273  {
1274  if (circ.getTargetIndex () == idx_v_b)
1275  {
1276  idx_he_ab = circ.getCurrentHalfEdgeIndex ();
1277  if (!this->isBoundary (idx_he_ab)) return (false);
1278 
1279  is_new_ab = false;
1280  return (true);
1281  }
1282  } while (++circ!=circ_end);
1283 
1284  return (true);
1285  }
1286 
1287  /** \brief Check if the face may be added (mesh does not become non-manifold). */
1288  inline bool
1289  checkTopology2 (const HalfEdgeIndex& /*idx_he_ab*/,
1290  const HalfEdgeIndex& /*idx_he_bc*/,
1291  const bool is_new_ab,
1292  const bool is_new_bc,
1293  const bool is_isolated_b,
1294  std::vector <bool>::reference /*make_adjacent_ab_bc*/,
1295  HalfEdgeIndex& /*idx_free_half_edge*/,
1296  boost::true_type /*is_manifold*/) const
1297  {
1298  if (is_new_ab && is_new_bc && !is_isolated_b) return (false);
1299  else return (true);
1300  }
1301 
1302  /** \brief Check if the half-edge bc is the next half-edge of ab.
1303  * \param[in] idx_he_ab Index to the half-edge between the vertices a and b.
1304  * \param[in] idx_he_bc Index to the half-edge between the vertices b and c.
1305  * \param[in] is_new_ab Half-edge ab is new.
1306  * \param[in] is_new_bc Half-edge bc is new.
1307  * \param[out] make_adjacent_ab_bc Half-edges ab and bc need to be made adjacent.
1308  * \param[out] idx_free_half_edge Free half-edge (needed for makeAdjacent)
1309  * \return true if addFace may be continued.
1310  */
1311  inline bool
1312  checkTopology2 (const HalfEdgeIndex& idx_he_ab,
1313  const HalfEdgeIndex& idx_he_bc,
1314  const bool is_new_ab,
1315  const bool is_new_bc,
1316  const bool /*is_isolated_b*/,
1317  std::vector <bool>::reference make_adjacent_ab_bc,
1318  HalfEdgeIndex& idx_free_half_edge,
1319  boost::false_type /*is_manifold*/) const
1320  {
1321  if (is_new_ab || is_new_bc)
1322  {
1323  make_adjacent_ab_bc = false;
1324  return (true); // Make adjacent is only needed for two old half-edges
1325  }
1326 
1327  if (this->getNextHalfEdgeIndex (idx_he_ab) == idx_he_bc)
1328  {
1329  make_adjacent_ab_bc = false;
1330  return (true); // already adjacent
1331  }
1332 
1333  make_adjacent_ab_bc = true;
1334 
1335  // Find the next boundary half edge
1336  IncomingHalfEdgeAroundVertexCirculator circ = this->getIncomingHalfEdgeAroundVertexCirculator (this->getOppositeHalfEdgeIndex (idx_he_bc));
1337 
1338  do ++circ; while (!this->isBoundary (circ.getTargetIndex ()));
1339  idx_free_half_edge = circ.getTargetIndex ();
1340 
1341  // This would detach the faces around the vertex from each other.
1342  if (circ.getTargetIndex () == idx_he_ab) return (false);
1343  else return (true);
1344  }
1345 
1346  /** \brief Make the half-edges bc the next half-edge of ab.
1347  * \param[in] idx_he_ab Index to the half-edge between the vertices a and b.
1348  * \param[in] idx_he_bc Index to the half-edge between the vertices b and c.
1349  * \param[in, out] idx_free_half_edge Free half-edge needed to re-connect the half-edges around vertex b.
1350  */
1351  void
1352  makeAdjacent (const HalfEdgeIndex& idx_he_ab,
1353  const HalfEdgeIndex& idx_he_bc,
1354  HalfEdgeIndex& idx_free_half_edge)
1355  {
1356  // Re-link. No references!
1357  const HalfEdgeIndex idx_he_ab_next = this->getNextHalfEdgeIndex (idx_he_ab);
1358  const HalfEdgeIndex idx_he_bc_prev = this->getPrevHalfEdgeIndex (idx_he_bc);
1359  const HalfEdgeIndex idx_he_free_next = this->getNextHalfEdgeIndex (idx_free_half_edge);
1360 
1361  this->connectPrevNext (idx_he_ab, idx_he_bc);
1362  this->connectPrevNext (idx_free_half_edge, idx_he_ab_next);
1363  this->connectPrevNext (idx_he_bc_prev, idx_he_free_next);
1364  }
1365 
1366  ////////////////////////////////////////////////////////////////////////
1367  // connect
1368  ////////////////////////////////////////////////////////////////////////
1369 
1370  /** \brief Add a face to the mesh and connect it to the half-edges.
1371  * \param[in] inner_he Inner half-edges of the face.
1372  * \param[in] face_data Data that is stored in the face. This is only added if the mesh has data associated with the faces.
1373  * \return Index to the new face.
1374  */
1375  FaceIndex
1376  connectFace (const HalfEdgeIndices& inner_he,
1377  const FaceData& face_data)
1378  {
1379  faces_.push_back (Face (inner_he.back ()));
1380  this->addData (face_data_cloud_, face_data, HasFaceData ());
1381 
1382  const FaceIndex idx_face (static_cast <int> (this->sizeFaces () - 1));
1383 
1384  for (const auto &idx_half_edge : inner_he)
1385  {
1386  this->setFaceIndex (idx_half_edge, idx_face);
1387  }
1388 
1389  return (idx_face);
1390  }
1391 
1392  /** \brief Connect the next and prev indices of the two half-edges with each other. */
1393  inline void
1394  connectPrevNext (const HalfEdgeIndex& idx_he_ab,
1395  const HalfEdgeIndex& idx_he_bc)
1396  {
1397  this->setNextHalfEdgeIndex (idx_he_ab, idx_he_bc);
1398  this->setPrevHalfEdgeIndex (idx_he_bc, idx_he_ab);
1399  }
1400 
1401  /** \brief Both half-edges are new (manifold version). */
1402  void
1403  connectNewNew (const HalfEdgeIndex& idx_he_ab,
1404  const HalfEdgeIndex& idx_he_bc,
1405  const VertexIndex& idx_v_b,
1406  boost::true_type /*is_manifold*/)
1407  {
1408  const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab);
1409  const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc);
1410 
1411  this->connectPrevNext (idx_he_ab, idx_he_bc);
1412  this->connectPrevNext (idx_he_cb, idx_he_ba);
1413 
1414  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ba);
1415  }
1416 
1417  /** \brief Both half-edges are new (non-manifold version). */
1418  void
1419  connectNewNew (const HalfEdgeIndex& idx_he_ab,
1420  const HalfEdgeIndex& idx_he_bc,
1421  const VertexIndex& idx_v_b,
1422  boost::false_type /*is_manifold*/)
1423  {
1424  if (this->isIsolated (idx_v_b))
1425  {
1426  this->connectNewNew (idx_he_ab, idx_he_bc, idx_v_b, boost::true_type ());
1427  }
1428  else
1429  {
1430  const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab);
1431  const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc);
1432 
1433  // No references!
1434  const HalfEdgeIndex idx_he_b_out = this->getOutgoingHalfEdgeIndex (idx_v_b);
1435  const HalfEdgeIndex idx_he_b_out_prev = this->getPrevHalfEdgeIndex (idx_he_b_out);
1436 
1437  this->connectPrevNext (idx_he_ab, idx_he_bc);
1438  this->connectPrevNext (idx_he_cb, idx_he_b_out);
1439  this->connectPrevNext (idx_he_b_out_prev, idx_he_ba);
1440  }
1441  }
1442 
1443  /** \brief The first half-edge is new. */
1444  void
1445  connectNewOld (const HalfEdgeIndex& idx_he_ab,
1446  const HalfEdgeIndex& idx_he_bc,
1447  const VertexIndex& idx_v_b)
1448  {
1449  const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab);
1450  const HalfEdgeIndex idx_he_bc_prev = this->getPrevHalfEdgeIndex (idx_he_bc); // No reference!
1451 
1452  this->connectPrevNext (idx_he_ab, idx_he_bc);
1453  this->connectPrevNext (idx_he_bc_prev, idx_he_ba);
1454 
1455  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ba);
1456  }
1457 
1458  /** \brief The second half-edge is new. */
1459  void
1460  connectOldNew (const HalfEdgeIndex& idx_he_ab,
1461  const HalfEdgeIndex& idx_he_bc,
1462  const VertexIndex& idx_v_b)
1463  {
1464  const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc);
1465  const HalfEdgeIndex idx_he_ab_next = this->getNextHalfEdgeIndex (idx_he_ab); // No reference!
1466 
1467  this->connectPrevNext (idx_he_ab, idx_he_bc);
1468  this->connectPrevNext (idx_he_cb, idx_he_ab_next);
1469 
1470  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ab_next);
1471  }
1472 
1473  /** \brief Both half-edges are old (manifold version). */
1474  void
1475  connectOldOld (const HalfEdgeIndex& /*idx_he_ab*/,
1476  const HalfEdgeIndex& /*idx_he_bc*/,
1477  const VertexIndex& /*idx_v_b*/,
1478  boost::true_type /*is_manifold*/)
1479  {
1480  }
1481 
1482  /** \brief Both half-edges are old (non-manifold version). */
1483  void
1484  connectOldOld (const HalfEdgeIndex& /*idx_he_ab*/,
1485  const HalfEdgeIndex& idx_he_bc,
1486  const VertexIndex& idx_v_b,
1487  boost::false_type /*is_manifold*/)
1488  {
1489  const HalfEdgeIndex& idx_he_b_out = this->getOutgoingHalfEdgeIndex (idx_v_b);
1490 
1491  // The outgoing half edge MUST be a boundary half-edge (if there is one)
1492  if (idx_he_b_out == idx_he_bc) // he_bc is no longer on the boundary
1493  {
1494  OutgoingHalfEdgeAroundVertexCirculator circ = this->getOutgoingHalfEdgeAroundVertexCirculator (idx_he_b_out);
1495  const OutgoingHalfEdgeAroundVertexCirculator circ_end = circ;
1496 
1497  while (++circ!=circ_end)
1498  {
1499  if (this->isBoundary (circ.getTargetIndex ()))
1500  {
1501  this->setOutgoingHalfEdgeIndex (idx_v_b, circ.getTargetIndex ());
1502  return;
1503  }
1504  }
1505  }
1506  }
1507 
1508  ////////////////////////////////////////////////////////////////////////
1509  // addData
1510  ////////////////////////////////////////////////////////////////////////
1511 
1512  /** \brief Add mesh data. */
1513  template <class DataT>
1514  inline void
1515  addData (pcl::PointCloud <DataT>& cloud, const DataT& data, boost::true_type /*has_data*/)
1516  {
1517  cloud.push_back (data);
1518  }
1519 
1520  /** \brief Does nothing. */
1521  template <class DataT>
1522  inline void
1523  addData (pcl::PointCloud <DataT>& /*cloud*/, const DataT& /*data*/, boost::false_type /*has_data*/)
1524  {
1525  }
1526 
1527  ////////////////////////////////////////////////////////////////////////
1528  // deleteFace
1529  ////////////////////////////////////////////////////////////////////////
1530 
1531  /** \brief Manifold version of deleteFace. If the mesh becomes non-manifold due to the delete operation the faces around the non-manifold vertex are deleted until the mesh becomes manifold again. */
1532  void
1533  deleteFace (const FaceIndex& idx_face,
1534  boost::true_type /*is_manifold*/)
1535  {
1536  assert (this->isValid (idx_face));
1537  delete_faces_face_.clear ();
1538  delete_faces_face_.push_back (idx_face);
1539 
1540  while (!delete_faces_face_.empty ())
1541  {
1542  const FaceIndex idx_face_cur = delete_faces_face_.back ();
1543  delete_faces_face_.pop_back ();
1544 
1545  // This calls the non-manifold version of deleteFace, which will call the manifold version of reconnect.
1546  this->deleteFace (idx_face_cur, boost::false_type ());
1547  }
1548  }
1549 
1550  /** \brief Non-manifold version of deleteFace. */
1551  void
1552  deleteFace (const FaceIndex& idx_face,
1553  boost::false_type /*is_manifold*/)
1554  {
1555  assert (this->isValid (idx_face));
1556  if (this->isDeleted (idx_face)) return;
1557 
1558  // Store all half-edges in the face
1559  inner_he_.clear ();
1560  is_boundary_.clear ();
1561  InnerHalfEdgeAroundFaceCirculator circ = this->getInnerHalfEdgeAroundFaceCirculator (idx_face);
1562  const InnerHalfEdgeAroundFaceCirculator circ_end = circ;
1563  do
1564  {
1565  inner_he_.push_back (circ.getTargetIndex ());
1566  is_boundary_.push_back (this->isBoundary (this->getOppositeHalfEdgeIndex (circ.getTargetIndex ())));
1567  } while (++circ != circ_end);
1568  assert (inner_he_.size () >= 3); // Minimum should be a triangle.
1569 
1570  const int n = static_cast <int> (inner_he_.size ());
1571  int j;
1572 
1573  if (IsManifold::value)
1574  {
1575  for (int i=0; i<n; ++i)
1576  {
1577  j = (i+1)%n;
1578  this->reconnect (inner_he_ [i], inner_he_ [j], is_boundary_ [i], is_boundary_ [j]);
1579  }
1580  for (int i=0; i<n; ++i)
1581  {
1582  this->getHalfEdge (inner_he_ [i]).idx_face_.invalidate ();
1583  }
1584  }
1585  else
1586  {
1587  for (int i=0; i<n; ++i)
1588  {
1589  j = (i+1)%n;
1590  this->reconnect (inner_he_ [i], inner_he_ [j], is_boundary_ [i], is_boundary_ [j]);
1591  this->getHalfEdge (inner_he_ [i]).idx_face_.invalidate ();
1592  }
1593  }
1594 
1595  this->markDeleted (idx_face);
1596  }
1597 
1598  ////////////////////////////////////////////////////////////////////////
1599  // reconnect
1600  ////////////////////////////////////////////////////////////////////////
1601 
1602  /** \brief Deconnect the input half-edges from the mesh and adjust the indices of the connected half-edges. */
1603  void
1604  reconnect (const HalfEdgeIndex& idx_he_ab,
1605  const HalfEdgeIndex& idx_he_bc,
1606  const bool is_boundary_ba,
1607  const bool is_boundary_cb)
1608  {
1609  const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab);
1610  const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc);
1611  const VertexIndex idx_v_b = this->getTerminatingVertexIndex (idx_he_ab);
1612 
1613  if (is_boundary_ba && is_boundary_cb) // boundary - boundary
1614  {
1615  const HalfEdgeIndex& idx_he_cb_next = this->getNextHalfEdgeIndex (idx_he_cb);
1616 
1617  if (idx_he_cb_next == idx_he_ba) // Vertex b is isolated
1618  {
1619  this->markDeleted (idx_v_b);
1620  }
1621  else
1622  {
1623  this->connectPrevNext (this->getPrevHalfEdgeIndex (idx_he_ba), idx_he_cb_next);
1624  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_cb_next);
1625  }
1626 
1627  this->markDeleted (idx_he_ab);
1628  this->markDeleted (idx_he_ba);
1629  }
1630  else if (is_boundary_ba && !is_boundary_cb) // boundary - no boundary
1631  {
1632  this->connectPrevNext (this->getPrevHalfEdgeIndex (idx_he_ba), idx_he_bc);
1633  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_bc);
1634 
1635  this->markDeleted (idx_he_ab);
1636  this->markDeleted (idx_he_ba);
1637  }
1638  else if (!is_boundary_ba && is_boundary_cb) // no boundary - boundary
1639  {
1640  const HalfEdgeIndex& idx_he_cb_next = this->getNextHalfEdgeIndex (idx_he_cb);
1641  this->connectPrevNext (idx_he_ab, idx_he_cb_next);
1642  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_cb_next);
1643  }
1644  else // no boundary - no boundary
1645  {
1646  this->reconnectNBNB (idx_he_bc, idx_he_cb, idx_v_b, IsManifold ());
1647  }
1648  }
1649 
1650  /** \brief Both edges are not on the boundary. Manifold version. */
1651  void
1652  reconnectNBNB (const HalfEdgeIndex& idx_he_bc,
1653  const HalfEdgeIndex& idx_he_cb,
1654  const VertexIndex& idx_v_b,
1655  boost::true_type /*is_manifold*/)
1656  {
1657  if (this->isBoundary (idx_v_b))
1658  {
1659  // Deletion of this face makes the mesh non-manifold
1660  // -> delete the neighboring faces until it is manifold again
1661  IncomingHalfEdgeAroundVertexCirculator circ = this->getIncomingHalfEdgeAroundVertexCirculator (idx_he_cb);
1662 
1663  while (!this->isBoundary (circ.getTargetIndex ()))
1664  {
1665  delete_faces_face_.push_back (this->getFaceIndex ((circ++).getTargetIndex ()));
1666 
1667 #ifdef PCL_GEOMETRY_MESH_BASE_TEST_DELETE_FACE_MANIFOLD_2
1668  if (circ == this->getIncomingHalfEdgeAroundVertexCirculator (idx_he_cb)) // Abort infinity loop
1669  {
1670  // In a manifold mesh we can't invalidate the face while reconnecting!
1671  // See the implementation of
1672  // deleteFace (const FaceIndex& idx_face,
1673  // boost::false_type /*is_manifold*/)
1674  pcl::geometry::g_pcl_geometry_mesh_base_test_delete_face_manifold_2_success = false;
1675  return;
1676  }
1677 #endif
1678  }
1679  }
1680  else
1681  {
1682  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_bc);
1683  }
1684  }
1685 
1686  /** \brief Both edges are not on the boundary. Non-manifold version. */
1687  void
1688  reconnectNBNB (const HalfEdgeIndex& idx_he_bc,
1689  const HalfEdgeIndex& /*idx_he_cb*/,
1690  const VertexIndex& idx_v_b,
1691  boost::false_type /*is_manifold*/)
1692  {
1693  if (!this->isBoundary (idx_v_b))
1694  {
1695  this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_bc);
1696  }
1697  }
1698 
1699  ////////////////////////////////////////////////////////////////////////
1700  // markDeleted
1701  ////////////////////////////////////////////////////////////////////////
1702 
1703  /** \brief Mark the given vertex as deleted. */
1704  inline void
1705  markDeleted (const VertexIndex& idx_vertex)
1706  {
1707  assert (this->isValid (idx_vertex));
1708  this->getVertex (idx_vertex).idx_outgoing_half_edge_.invalidate ();
1709  }
1710 
1711  /** \brief Mark the given half-edge as deleted. */
1712  inline void
1713  markDeleted (const HalfEdgeIndex& idx_he)
1714  {
1715  assert (this->isValid (idx_he));
1716  this->getHalfEdge (idx_he).idx_terminating_vertex_.invalidate ();
1717  }
1718 
1719  /** \brief Mark the given edge (both half-edges) as deleted. */
1720  inline void
1721  markDeleted (const EdgeIndex& idx_edge)
1722  {
1723  assert (this->isValid (idx_edge));
1724  this->markDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, true));
1725  this->markDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, false));
1726  }
1727 
1728  /** \brief Mark the given face as deleted. */
1729  inline void
1730  markDeleted (const FaceIndex& idx_face)
1731  {
1732  assert (this->isValid (idx_face));
1733  this->getFace (idx_face).idx_inner_half_edge_.invalidate ();
1734  }
1735 
1736  ////////////////////////////////////////////////////////////////////////
1737  // For cleanUp
1738  ////////////////////////////////////////////////////////////////////////
1739 
1740  /** \brief Removes mesh elements and data that are marked as deleted from the container.
1741  * \tparam ElementContainerT e.g. std::vector <Vertex>
1742  * \tparam DataContainerT e.g. std::vector <VertexData>
1743  * \tparam IndexContainerT e.g. std::vector <VertexIndex>
1744  * \tparam HasDataT Integral constant specifying if the mesh has data associated with the elements.
1745  *
1746  * \param[in, out] elements Container for the mesh elements. Resized to the new size.
1747  * \param[in, out] data_cloud Container for the mesh data. Resized to the new size.
1748  * \return Container with the same size as the old input data. Holds the indices to the new elements for each non-deleted element and an invalid index if it is deleted.
1749  */
1750  template <class ElementContainerT, class DataContainerT, class IndexContainerT, class HasDataT> IndexContainerT
1751  remove (ElementContainerT& elements, DataContainerT& data_cloud)
1752  {
1753  typedef typename IndexContainerT::value_type Index;
1754  typedef typename ElementContainerT::value_type Element;
1755 
1756  if (HasDataT::value) assert (elements.size () == data_cloud.size ());
1757  else assert (data_cloud.empty ()); // Bug in this class!
1758 
1759  IndexContainerT new_indices (elements.size (), typename IndexContainerT::value_type ());
1760  Index ind_old (0), ind_new (0);
1761 
1762  typename ElementContainerT::const_iterator it_e_old = elements.begin ();
1763  typename ElementContainerT::iterator it_e_new = elements.begin ();
1764 
1765  typename DataContainerT::const_iterator it_d_old = data_cloud.begin ();
1766  typename DataContainerT::iterator it_d_new = data_cloud.begin ();
1767 
1768  typename IndexContainerT::iterator it_ind_new = new_indices.begin ();
1769  typename IndexContainerT::const_iterator it_ind_new_end = new_indices.end ();
1770 
1771  while (it_ind_new!=it_ind_new_end)
1772  {
1773  if (!this->isDeleted (ind_old))
1774  {
1775  *it_ind_new = ind_new++;
1776 
1777  // TODO: Test for self assignment?
1778  *it_e_new++ = *it_e_old;
1779  this->assignIf (it_d_old, it_d_new, HasDataT ());
1780  this->incrementIf ( it_d_new, HasDataT ());
1781  }
1782  ++ind_old;
1783  ++it_e_old;
1784  this->incrementIf (it_d_old, HasDataT ());
1785  ++it_ind_new;
1786  }
1787 
1788  elements.resize (ind_new.get (), Element ());
1789  if (HasDataT::value)
1790  {
1791  data_cloud.resize (ind_new.get ());
1792  }
1793  else if (it_d_old != data_cloud.begin () || it_d_new != data_cloud.begin ())
1794  {
1795  std::cerr << "TODO: Bug in MeshBase::remove!\n";
1796  assert (false);
1797  exit (EXIT_FAILURE);
1798  }
1799 
1800  return (new_indices);
1801  }
1802 
1803  /** \brief Increment the iterator. */
1804  template <class IteratorT> inline void
1805  incrementIf (IteratorT& it, boost::true_type /*has_data*/) const
1806  {
1807  ++it;
1808  }
1809 
1810  /** \brief Does nothing. */
1811  template <class IteratorT> inline void
1812  incrementIf (IteratorT& /*it*/, boost::false_type /*has_data*/) const
1813  {
1814  }
1815 
1816  /** \brief Assign the source iterator to the target iterator. */
1817  template <class ConstIteratorT, class IteratorT> inline void
1818  assignIf (const ConstIteratorT source, IteratorT target, boost::true_type /*has_data*/) const
1819  {
1820  *target = *source;
1821  }
1822 
1823  /** \brief Does nothing. */
1824  template <class ConstIteratorT, class IteratorT> inline void
1825  assignIf (const ConstIteratorT /*source*/, IteratorT /*target*/, boost::false_type /*has_data*/) const
1826  {
1827  }
1828 
1829  ////////////////////////////////////////////////////////////////////////
1830  // Vertex / Half-edge / Face connectivity
1831  ////////////////////////////////////////////////////////////////////////
1832 
1833  /** \brief Set the outgoing half-edge index to a given vertex. */
1834  inline void
1835  setOutgoingHalfEdgeIndex (const VertexIndex& idx_vertex, const HalfEdgeIndex& idx_outgoing_half_edge)
1836  {
1837  assert (this->isValid (idx_vertex));
1838  this->getVertex (idx_vertex).idx_outgoing_half_edge_ = idx_outgoing_half_edge;
1839  }
1840 
1841  /** \brief Set the terminating vertex index to a given half-edge. */
1842  inline void
1843  setTerminatingVertexIndex (const HalfEdgeIndex& idx_half_edge, const VertexIndex& idx_terminating_vertex)
1844  {
1845  assert (this->isValid (idx_half_edge));
1846  this->getHalfEdge (idx_half_edge).idx_terminating_vertex_ = idx_terminating_vertex;
1847  }
1848 
1849  /** \brief Set the next half_edge index to a given half-edge. */
1850  inline void
1851  setNextHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge, const HalfEdgeIndex& idx_next_half_edge)
1852  {
1853  assert (this->isValid (idx_half_edge));
1854  this->getHalfEdge (idx_half_edge).idx_next_half_edge_ = idx_next_half_edge;
1855  }
1856 
1857  /** \brief Set the previous half-edge index to a given half-edge. */
1858  inline void
1859  setPrevHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge,
1860  const HalfEdgeIndex& idx_prev_half_edge)
1861  {
1862  assert (this->isValid (idx_half_edge));
1863  this->getHalfEdge (idx_half_edge).idx_prev_half_edge_ = idx_prev_half_edge;
1864  }
1865 
1866  /** \brief Set the face index to a given half-edge. */
1867  inline void
1868  setFaceIndex (const HalfEdgeIndex& idx_half_edge, const FaceIndex& idx_face)
1869  {
1870  assert (this->isValid (idx_half_edge));
1871  this->getHalfEdge (idx_half_edge).idx_face_ = idx_face;
1872  }
1873 
1874  /** \brief Set the inner half-edge index to a given face. */
1875  inline void
1876  setInnerHalfEdgeIndex (const FaceIndex& idx_face, const HalfEdgeIndex& idx_inner_half_edge)
1877  {
1878  assert (this->isValid (idx_face));
1879  this->getFace (idx_face).idx_inner_half_edge_ = idx_inner_half_edge;
1880  }
1881 
1882  ////////////////////////////////////////////////////////////////////////
1883  // isBoundary / isManifold
1884  ////////////////////////////////////////////////////////////////////////
1885 
1886  /** \brief Check if any vertex of the face lies on the boundary. */
1887  bool
1888  isBoundary (const FaceIndex& idx_face, boost::true_type /*check_vertices*/) const
1889  {
1890  VertexAroundFaceCirculator circ = this->getVertexAroundFaceCirculator (idx_face);
1891  const VertexAroundFaceCirculator circ_end = circ;
1892 
1893  do
1894  {
1895  if (this->isBoundary (circ.getTargetIndex ()))
1896  {
1897  return (true);
1898  }
1899  } while (++circ!=circ_end);
1900 
1901  return (false);
1902  }
1903 
1904  /** \brief Check if any edge of the face lies on the boundary. */
1905  bool
1906  isBoundary (const FaceIndex& idx_face, boost::false_type /*check_vertices*/) const
1907  {
1908  OuterHalfEdgeAroundFaceCirculator circ = this->getOuterHalfEdgeAroundFaceCirculator (idx_face);
1909  const OuterHalfEdgeAroundFaceCirculator circ_end = circ;
1910 
1911  do
1912  {
1913  if (this->isBoundary (circ.getTargetIndex ()))
1914  {
1915  return (true);
1916  }
1917  } while (++circ!=circ_end);
1918 
1919  return (false);
1920  }
1921 
1922  /** \brief Always manifold. */
1923  inline bool
1924  isManifold (const VertexIndex&, boost::true_type /*is_manifold*/) const
1925  {
1926  return (true);
1927  }
1928 
1929  /** \brief Check if the given vertex is manifold. */
1930  bool
1931  isManifold (const VertexIndex& idx_vertex, boost::false_type /*is_manifold*/) const
1932  {
1933  OutgoingHalfEdgeAroundVertexCirculator circ = this->getOutgoingHalfEdgeAroundVertexCirculator (idx_vertex);
1934  const OutgoingHalfEdgeAroundVertexCirculator circ_end = circ;
1935 
1936  if (!this->isBoundary ((circ++).getTargetIndex ())) return (true);
1937  do
1938  {
1939  if (this->isBoundary (circ.getTargetIndex ())) return (false);
1940  } while (++circ != circ_end);
1941 
1942  return (true);
1943  }
1944 
1945  /** \brief Always manifold. */
1946  inline bool
1947  isManifold (boost::true_type /*is_manifold*/) const
1948  {
1949  return (true);
1950  }
1951 
1952  /** \brief Check if all vertices in the mesh are manifold. */
1953  bool
1954  isManifold (boost::false_type /*is_manifold*/) const
1955  {
1956  for (size_t i=0; i<this->sizeVertices (); ++i)
1957  {
1958  if (!this->isManifold (VertexIndex (i))) return (false);
1959  }
1960  return (true);
1961  }
1962 
1963  ////////////////////////////////////////////////////////////////////////
1964  // reserveData / resizeData / clearData
1965  ////////////////////////////////////////////////////////////////////////
1966 
1967  /** \brief Reserve storage space for the mesh data. */
1968  template <class DataCloudT> inline void
1969  reserveData (DataCloudT& cloud, const size_t n, boost::true_type /*has_data*/) const
1970  {
1971  cloud.reserve (n);
1972  }
1973 
1974  /** \brief Does nothing */
1975  template <class DataCloudT> inline void
1976  reserveData (DataCloudT& /*cloud*/, const size_t /*n*/, boost::false_type /*has_data*/) const
1977  {
1978  }
1979 
1980  /** \brief Resize the mesh data. */
1981  template <class DataCloudT> inline void
1982  resizeData (DataCloudT& /*data_cloud*/, const size_t n, const typename DataCloudT::value_type& data, boost::true_type /*has_data*/) const
1983  {
1984  data.resize (n, data);
1985  }
1986 
1987  /** \brief Does nothing. */
1988  template <class DataCloudT> inline void
1989  resizeData (DataCloudT& /*data_cloud*/, const size_t /*n*/, const typename DataCloudT::value_type& /*data*/, boost::false_type /*has_data*/) const
1990  {
1991  }
1992 
1993  /** \brief Clear the mesh data. */
1994  template <class DataCloudT> inline void
1995  clearData (DataCloudT& cloud, boost::true_type /*has_data*/) const
1996  {
1997  cloud.clear ();
1998  }
1999 
2000  /** \brief Does nothing. */
2001  template <class DataCloudT> inline void
2002  clearData (DataCloudT& /*cloud*/, boost::false_type /*has_data*/) const
2003  {
2004  }
2005 
2006  ////////////////////////////////////////////////////////////////////////
2007  // get / set Vertex
2008  ////////////////////////////////////////////////////////////////////////
2009 
2010  /** \brief Get the vertex for the given index. */
2011  inline Vertex&
2012  getVertex (const VertexIndex& idx_vertex)
2013  {
2014  assert (this->isValid (idx_vertex));
2015  return (vertices_ [idx_vertex.get ()]);
2016  }
2017 
2018  /** \brief Get the vertex for the given index. */
2019  inline Vertex
2020  getVertex (const VertexIndex& idx_vertex) const
2021  {
2022  assert (this->isValid (idx_vertex));
2023  return (vertices_ [idx_vertex.get ()]);
2024  }
2025 
2026  /** \brief Set the vertex at the given index. */
2027  inline void
2028  setVertex (const VertexIndex& idx_vertex, const Vertex& vertex)
2029  {
2030  assert (this->isValid (idx_vertex));
2031  vertices_ [idx_vertex.get ()] = vertex;
2032  }
2033 
2034  ////////////////////////////////////////////////////////////////////////
2035  // get / set HalfEdge
2036  ////////////////////////////////////////////////////////////////////////
2037 
2038  /** \brief Get the half-edge for the given index. */
2039  inline HalfEdge&
2040  getHalfEdge (const HalfEdgeIndex& idx_he)
2041  {
2042  assert (this->isValid (idx_he));
2043  return (half_edges_ [idx_he.get ()]);
2044  }
2045 
2046  /** \brief Get the half-edge for the given index. */
2047  inline HalfEdge
2048  getHalfEdge (const HalfEdgeIndex& idx_he) const
2049  {
2050  assert (this->isValid (idx_he));
2051  return (half_edges_ [idx_he.get ()]);
2052  }
2053 
2054  /** \brief Set the half-edge at the given index. */
2055  inline void
2056  setHalfEdge (const HalfEdgeIndex& idx_he, const HalfEdge& half_edge)
2057  {
2058  assert (this->isValid (idx_he));
2059  half_edges_ [idx_he.get ()] = half_edge;
2060  }
2061 
2062  ////////////////////////////////////////////////////////////////////////
2063  // get / set Face
2064  ////////////////////////////////////////////////////////////////////////
2065 
2066  /** \brief Get the face for the given index. */
2067  inline Face&
2068  getFace (const FaceIndex& idx_face)
2069  {
2070  assert (this->isValid (idx_face));
2071  return (faces_ [idx_face.get ()]);
2072  }
2073 
2074  /** \brief Get the face for the given index. */
2075  inline Face
2076  getFace (const FaceIndex& idx_face) const
2077  {
2078  assert (this->isValid (idx_face));
2079  return (faces_ [idx_face.get ()]);
2080  }
2081 
2082  /** \brief Set the face at the given index. */
2083  inline void
2084  setFace (const FaceIndex& idx_face, const Face& face)
2085  {
2086  assert (this->isValid (idx_face));
2087  faces_ [idx_face.get ()] = face;
2088  }
2089 
2090  private:
2091 
2092  ////////////////////////////////////////////////////////////////////////
2093  // Members
2094  ////////////////////////////////////////////////////////////////////////
2095 
2096  /** \brief Data stored for the vertices. */
2097  VertexDataCloud vertex_data_cloud_;
2098 
2099  /** \brief Data stored for the half-edges. */
2100  HalfEdgeDataCloud half_edge_data_cloud_;
2101 
2102  /** \brief Data stored for the edges. */
2103  EdgeDataCloud edge_data_cloud_;
2104 
2105  /** \brief Data stored for the faces. */
2106  FaceDataCloud face_data_cloud_;
2107 
2108  /** \brief Connectivity information for the vertices. */
2109  Vertices vertices_;
2110 
2111  /** \brief Connectivity information for the half-edges. */
2112  HalfEdges half_edges_;
2113 
2114  /** \brief Connectivity information for the faces. */
2115  Faces faces_;
2116 
2117  // NOTE: It is MUCH faster to store these variables permamently.
2118 
2119  /** \brief Storage for addFaceImplBase and deleteFace. */
2120  HalfEdgeIndices inner_he_;
2121 
2122  /** \brief Storage for addFaceImplBase. */
2123  HalfEdgeIndices free_he_;
2124 
2125  /** \brief Storage for addFaceImplBase. */
2126  std::vector <bool> is_new_;
2127 
2128  /** \brief Storage for addFaceImplBase. */
2129  std::vector <bool> make_adjacent_;
2130 
2131  /** \brief Storage for deleteFace. */
2132  std::vector <bool> is_boundary_;
2133 
2134  /** \brief Storage for deleteVertex. */
2135  FaceIndices delete_faces_vertex_;
2136 
2137  /** \brief Storage for deleteFace. */
2138  FaceIndices delete_faces_face_;
2139 
2140  public:
2141 
2142  template <class MeshT>
2144 
2145  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
2146  };
2147  } // End namespace geometry
2148 } // End namespace pcl
bool isBoundary(const FaceIndex &idx_face, boost::true_type) const
Check if any vertex of the face lies on the boundary.
Definition: mesh_base.h:1888
void markDeleted(const VertexIndex &idx_vertex)
Mark the given vertex as deleted.
Definition: mesh_base.h:1705
MeshBase< DerivedT, MeshTraitsT, MeshTagT > Self
Definition: mesh_base.h:101
std::vector< Vertex > Vertices
Definition: mesh_base.h:1126
void deleteFace(const FaceIndex &idx_face, boost::false_type)
Non-manifold version of deleteFace.
Definition: mesh_base.h:1552
void setPrevHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge, const HalfEdgeIndex &idx_prev_half_edge)
Set the previous half-edge index to a given half-edge.
Definition: mesh_base.h:1859
A vertex is a node in the mesh.
Definition: mesh_elements.h:69
pcl::geometry::HalfEdgeIndex HalfEdgeIndex
Definition: mesh_base.h:132
pcl::geometry::FaceAroundVertexCirculator< const Self > FaceAroundVertexCirculator
Definition: mesh_base.h:145
std::vector< FaceIndex > FaceIndices
Definition: mesh_base.h:139
size_t size() const
Definition: point_cloud.h:447
void clearData(DataCloudT &cloud, boost::true_type) const
Clear the mesh data.
Definition: mesh_base.h:1995
size_t sizeFaces() const
Get the number of the faces.
Definition: mesh_base.h:782
int get() const
Get the index.
Definition: mesh_indices.h:104
An edge is a connection between two vertices.
void resizeFaces(const size_t n, const FaceData &data=FaceData())
Resize the faces to n elements.
Definition: mesh_base.h:873
void connectOldNew(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, const VertexIndex &idx_v_b)
The second half-edge is new.
Definition: mesh_base.h:1460
VertexAroundFaceCirculator getVertexAroundFaceCirculator(const FaceIndex &idx_face) const
Definition: mesh_base.h:500
bool emptyVertices() const
Check if the vertices are empty.
Definition: mesh_base.h:800
FaceDataCloud & getFaceDataCloud()
Get access to the stored face data.
Definition: mesh_base.h:1019
size_t sizeEdges() const
Get the number of the edges.
Definition: mesh_base.h:774
MeshTraitsT::HalfEdgeData HalfEdgeData
Definition: mesh_base.h:109
boost::shared_ptr< Self > Ptr
Definition: mesh_base.h:102
VertexIndex getTerminatingVertexIndex(const HalfEdgeIndex &idx_half_edge) const
Get the terminating vertex index to a given half-edge.
Definition: mesh_base.h:355
pcl::geometry::VertexAroundVertexCirculator< const Self > VertexAroundVertexCirculator
Definition: mesh_base.h:142
void deleteEdge(const EdgeIndex &idx_edge)
Mark the given edge (both half-edges) and the associated faces as deleted.
Definition: mesh_base.h:251
VertexAroundFaceCirculator getVertexAroundFaceCirculator(const HalfEdgeIndex &idx_inner_half_edge) const
Definition: mesh_base.h:508
bool setHalfEdgeDataCloud(const HalfEdgeDataCloud &half_edge_data_cloud)
Change the stored half-edge data.
Definition: mesh_base.h:960
boost::integral_constant< bool,!boost::is_same< VertexData, pcl::geometry::NoData >::value > HasVertexData
Definition: mesh_base.h:120
std::vector< HalfEdge > HalfEdges
Definition: mesh_base.h:1127
VertexIndex getVertexIndex(const VertexData &vertex_data) const
Get the index associated to the given vertex data.
Definition: mesh_base.h:1057
void connectPrevNext(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc)
Connect the next and prev indices of the two half-edges with each other.
Definition: mesh_base.h:1394
bool isBoundary(const FaceIndex &idx_face, boost::false_type) const
Check if any edge of the face lies on the boundary.
Definition: mesh_base.h:1906
bool isValid(const EdgeIndex &idx_edge) const
Check if the given edge index is a valid index into the mesh.
Definition: mesh_base.h:624
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:44
HalfEdgeIndex getNextHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge) const
Get the next half-edge index to a given half-edge.
Definition: mesh_base.h:380
pcl::geometry::VertexIndex VertexIndex
Definition: mesh_base.h:131
pcl::geometry::EdgeIndex EdgeIndex
Definition: mesh_base.h:133
HalfEdgeIndex getOutgoingHalfEdgeIndex(const VertexIndex &idx_vertex) const
Get the outgoing half-edge index to a given vertex.
Definition: mesh_base.h:335
Circulates clockwise around a face and returns an index to the face of the outer half-edge (the targe...
void resizeEdges(const size_t n, const EdgeData &edge_data=EdgeData(), const HalfEdgeData he_data=HalfEdgeData())
Resize the edges to n elements (half-edges will hold 2*n elements).
Definition: mesh_base.h:862
bool isIsolated(const VertexIndex &idx_vertex) const
Check if the given vertex is isolated (not connected to other elements).
Definition: mesh_base.h:679
void setNextHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge, const HalfEdgeIndex &idx_next_half_edge)
Set the next half_edge index to a given half-edge.
Definition: mesh_base.h:1851
Circulates counter-clockwise around a vertex and returns an index to the incoming half-edge (the targ...
size_t sizeHalfEdges() const
Get the number of the half-edges.
Definition: mesh_base.h:766
InnerHalfEdgeAroundFaceCirculator getInnerHalfEdgeAroundFaceCirculator(const FaceIndex &idx_face) const
Definition: mesh_base.h:516
InnerHalfEdgeAroundFaceCirculator getInnerHalfEdgeAroundFaceCirculator(const HalfEdgeIndex &idx_inner_half_edge) const
Definition: mesh_base.h:524
void setInnerHalfEdgeIndex(const FaceIndex &idx_face, const HalfEdgeIndex &idx_inner_half_edge)
Set the inner half-edge index to a given face.
Definition: mesh_base.h:1876
void resizeData(DataCloudT &, const size_t n, const typename DataCloudT::value_type &data, boost::true_type) const
Resize the mesh data.
Definition: mesh_base.h:1982
boost::integral_constant< bool,!boost::is_same< HalfEdgeData, pcl::geometry::NoData >::value > HasHalfEdgeData
Definition: mesh_base.h:121
OuterHalfEdgeAroundFaceCirculator getOuterHalfEdgeAroundFaceCirculator(const HalfEdgeIndex &idx_inner_half_edge) const
Definition: mesh_base.h:540
void resizeVertices(const size_t n, const VertexData &data=VertexData())
Resize the the vertices to n elements.
Definition: mesh_base.h:854
void push_back(const PointT &pt)
Insert a new point in the cloud, at the end of the container.
Definition: point_cloud.h:479
VertexIndex getTargetIndex() const
Get the index to the target vertex.
MeshBase()
Constructor.
Definition: mesh_base.h:152
void reserveData(DataCloudT &, const size_t, boost::false_type) const
Does nothing.
Definition: mesh_base.h:1976
void setHalfEdge(const HalfEdgeIndex &idx_he, const HalfEdge &half_edge)
Set the half-edge at the given index.
Definition: mesh_base.h:2056
bool isManifold(const VertexIndex &idx_vertex, boost::false_type) const
Check if the given vertex is manifold.
Definition: mesh_base.h:1931
HalfEdgeIndex getCurrentHalfEdgeIndex() const
Get the half-edge that is currently stored in the circulator.
void deleteEdge(const HalfEdgeIndex &idx_he)
Mark the given half-edge, the opposite half-edge and the associated faces as deleted.
Definition: mesh_base.h:234
bool isValid(const FaceIndex &idx_face) const
Check if the given face index is a valid index into the mesh.
Definition: mesh_base.h:631
bool isDeleted(const FaceIndex &idx_face) const
Check if the given face is marked as deleted.
Definition: mesh_base.h:667
pcl::geometry::VertexAroundFaceCirculator< const Self > VertexAroundFaceCirculator
Definition: mesh_base.h:146
bool isManifold(const VertexIndex &, boost::true_type) const
Always manifold.
Definition: mesh_base.h:1924
void connectNewNew(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, const VertexIndex &idx_v_b, boost::false_type)
Both half-edges are new (non-manifold version).
Definition: mesh_base.h:1419
FaceIndex getTargetIndex() const
Get the index to the target face.
int get() const
Get the index.
Definition: mesh_indices.h:243
void reserveFaces(const size_t n)
Reserve storage space for n faces.
Definition: mesh_base.h:842
bool isValid(const HalfEdgeIndex &idx_he) const
Check if the given half-edge index is a valid index into the mesh.
Definition: mesh_base.h:617
HalfEdges::const_iterator HalfEdgeConstIterator
Definition: mesh_base.h:1135
size_t sizeVertices() const
Get the number of the vertices.
Definition: mesh_base.h:759
void resizeData(DataCloudT &, const size_t, const typename DataCloudT::value_type &, boost::false_type) const
Does nothing.
Definition: mesh_base.h:1989
void addData(pcl::PointCloud< DataT > &, const DataT &, boost::false_type)
Does nothing.
Definition: mesh_base.h:1523
bool isManifold(const VertexIndex &idx_vertex) const
Check if the given vertex is manifold.
Definition: mesh_base.h:739
void reconnectNBNB(const HalfEdgeIndex &idx_he_bc, const HalfEdgeIndex &idx_he_cb, const VertexIndex &idx_v_b, boost::true_type)
Both edges are not on the boundary.
Definition: mesh_base.h:1652
HalfEdgeIndex getIncomingHalfEdgeIndex(const VertexIndex &idx_vertex) const
Get the incoming half-edge index to a given vertex.
Definition: mesh_base.h:343
void connectOldOld(const HalfEdgeIndex &, const HalfEdgeIndex &idx_he_bc, const VertexIndex &idx_v_b, boost::false_type)
Both half-edges are old (non-manifold version).
Definition: mesh_base.h:1484
pcl::PointCloud< HalfEdgeData > HalfEdgeDataCloud
Definition: mesh_base.h:126
pcl::PointCloud< VertexData > VertexDataCloud
Definition: mesh_base.h:125
HalfEdgeIndex getOppositeHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge) const
Get the opposite half-edge index to a given half-edge.
Definition: mesh_base.h:371
EdgeDataCloud getEdgeDataCloud() const
Get the stored edge data.
Definition: mesh_base.h:988
Index used to access elements in the half-edge mesh.
Definition: mesh_indices.h:339
std::vector< Face > Faces
Definition: mesh_base.h:1128
void incrementIf(IteratorT &, boost::false_type) const
Does nothing.
Definition: mesh_base.h:1812
std::vector< HalfEdgeIndex > HalfEdgeIndices
Definition: mesh_base.h:137
Faces::const_iterator FaceConstIterator
Definition: mesh_base.h:1136
OutgoingHalfEdgeAroundVertexCirculator getOutgoingHalfEdgeAroundVertexCirculator(const VertexIndex &idx_vertex) const
Definition: mesh_base.h:452
MeshTraitsT::IsManifold IsManifold
Definition: mesh_base.h:112
VertexIndex addVertex(const VertexData &vertex_data=VertexData())
Add a vertex to the mesh.
Definition: mesh_base.h:179
void markDeleted(const EdgeIndex &idx_edge)
Mark the given edge (both half-edges) as deleted.
Definition: mesh_base.h:1721
pcl::geometry::HalfEdgeIndex toHalfEdgeIndex(const EdgeIndex &index, const bool get_first=true)
Convert the given edge index to a half-edge index.
Definition: mesh_indices.h:625
MeshTraitsT::EdgeData EdgeData
Definition: mesh_base.h:110
bool empty() const
Check if the mesh is empty.
Definition: mesh_base.h:793
FaceAroundFaceCirculator getFaceAroundFaceCirculator(const HalfEdgeIndex &idx_inner_half_edge) const
Definition: mesh_base.h:556
HalfEdge & getHalfEdge(const HalfEdgeIndex &idx_he)
Get the half-edge for the given index.
Definition: mesh_base.h:2040
HalfEdgeIndex getPrevHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge) const
Get the previous half-edge index to a given half-edge.
Definition: mesh_base.h:388
bool isBoundary(const VertexIndex &idx_vertex) const
Check if the given vertex lies on the boundary.
Definition: mesh_base.h:691
void makeAdjacent(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, HalfEdgeIndex &idx_free_half_edge)
Make the half-edges bc the next half-edge of ab.
Definition: mesh_base.h:1352
HalfEdgeIndex addEdge(const VertexIndex &idx_v_a, const VertexIndex &idx_v_b, const HalfEdgeData &he_data, const EdgeData &edge_data)
Add an edge between the two given vertices and connect them with the vertices.
Definition: mesh_base.h:1214
VertexAroundVertexCirculator getVertexAroundVertexCirculator(const HalfEdgeIndex &idx_outgoing_half_edge) const
Definition: mesh_base.h:444
void assignIf(const ConstIteratorT, IteratorT, boost::false_type) const
Does nothing.
Definition: mesh_base.h:1825
Face & getFace(const FaceIndex &idx_face)
Get the face for the given index.
Definition: mesh_base.h:2068
EdgeIndex getEdgeIndex(const EdgeData &edge_data) const
Get the index associated to the given edge data.
Definition: mesh_base.h:1087
Circulates counter-clockwise around a vertex and returns an index to the terminating vertex of the ou...
FaceIndex getFaceIndex(const HalfEdgeIndex &idx_half_edge) const
Get the face index to a given half-edge.
Definition: mesh_base.h:396
void connectOldOld(const HalfEdgeIndex &, const HalfEdgeIndex &, const VertexIndex &, boost::true_type)
Both half-edges are old (manifold version).
Definition: mesh_base.h:1475
void setFace(const FaceIndex &idx_face, const Face &face)
Set the face at the given index.
Definition: mesh_base.h:2084
void setOutgoingHalfEdgeIndex(const VertexIndex &idx_vertex, const HalfEdgeIndex &idx_outgoing_half_edge)
Set the outgoing half-edge index to a given vertex.
Definition: mesh_base.h:1835
VertexIndex getTargetIndex() const
Get the index to the target vertex.
Index used to access elements in the half-edge mesh.
Definition: mesh_indices.h:61
OuterHalfEdgeAroundFaceCirculator getOuterHalfEdgeAroundFaceCirculator(const FaceIndex &idx_face) const
Definition: mesh_base.h:532
void clear()
Clear all mesh elements and data.
Definition: mesh_base.h:885
FaceIndex getFaceIndex(const FaceData &face_data) const
Get the index associated to the given face data.
Definition: mesh_base.h:1102
Index used to access elements in the half-edge mesh.
Definition: mesh_indices.h:478
Circulates clockwise around a face and returns an index to the terminating vertex of the inner half-e...
void connectNewNew(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, const VertexIndex &idx_v_b, boost::true_type)
Both half-edges are new (manifold version).
Definition: mesh_base.h:1403
Vertex & getVertex(const VertexIndex &idx_vertex)
Get the vertex for the given index.
Definition: mesh_base.h:2012
void assignIf(const ConstIteratorT source, IteratorT target, boost::true_type) const
Assign the source iterator to the target iterator.
Definition: mesh_base.h:1818
bool isBoundary(const FaceIndex &idx_face) const
Check if the given face lies on the boundary.
Definition: mesh_base.h:727
void setTerminatingVertexIndex(const HalfEdgeIndex &idx_half_edge, const VertexIndex &idx_terminating_vertex)
Set the terminating vertex index to a given half-edge.
Definition: mesh_base.h:1843
bool isValid(const VertexIndex &idx_vertex) const
Check if the given vertex index is a valid index into the mesh.
Definition: mesh_base.h:610
Index used to access elements in the half-edge mesh.
Definition: mesh_indices.h:200
void reconnect(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, const bool is_boundary_ba, const bool is_boundary_cb)
Deconnect the input half-edges from the mesh and adjust the indices of the connected half-edges...
Definition: mesh_base.h:1604
FaceIndex addFaceImplBase(const VertexIndices &vertices, const FaceData &face_data, const EdgeData &edge_data, const HalfEdgeData &half_edge_data)
General implementation of addFace.
Definition: mesh_base.h:1140
FaceIndex connectFace(const HalfEdgeIndices &inner_he, const FaceData &face_data)
Add a face to the mesh and connect it to the half-edges.
Definition: mesh_base.h:1376
HalfEdgeDataCloud getHalfEdgeDataCloud() const
Get the stored half-edge data.
Definition: mesh_base.h:950
IncomingHalfEdgeAroundVertexCirculator getIncomingHalfEdgeAroundVertexCirculator(const VertexIndex &idx_vertex) const
Definition: mesh_base.h:468
bool isDeleted(const VertexIndex &idx_vertex) const
Check if the given vertex is marked as deleted.
Definition: mesh_base.h:642
IncomingHalfEdgeAroundVertexCirculator getIncomingHalfEdgeAroundVertexCirculator(const HalfEdgeIndex &idx_incoming_half_edge) const
Definition: mesh_base.h:476
Read / write the half-edge mesh from / to a file.
Definition: mesh_base.h:76
Circulates counter-clockwise around a vertex and returns an index to the outgoing half-edge (the targ...
void reserveVertices(const size_t n)
Reserve storage space n vertices.
Definition: mesh_base.h:825
boost::shared_ptr< const Self > ConstPtr
Definition: mesh_base.h:103
MeshTraitsT::FaceData FaceData
Definition: mesh_base.h:111
void deleteFace(const FaceIndex &idx_face, boost::true_type)
Manifold version of deleteFace.
Definition: mesh_base.h:1533
FaceIndex getOppositeFaceIndex(const HalfEdgeIndex &idx_half_edge) const
Get the face index to a given half-edge.
Definition: mesh_base.h:404
boost::integral_constant< bool,!boost::is_same< FaceData, pcl::geometry::NoData >::value > HasFaceData
Definition: mesh_base.h:123
FaceAroundFaceCirculator getFaceAroundFaceCirculator(const FaceIndex &idx_face) const
Definition: mesh_base.h:548
Vertex getVertex(const VertexIndex &idx_vertex) const
Get the vertex for the given index.
Definition: mesh_base.h:2020
std::vector< EdgeIndex > EdgeIndices
Definition: mesh_base.h:138
HalfEdgeIndex getTargetIndex() const
Get the index to the inner half-edge.
pcl::PointCloud< EdgeData > EdgeDataCloud
Definition: mesh_base.h:127
bool setEdgeDataCloud(const EdgeDataCloud &edge_data_cloud)
Change the stored edge data.
Definition: mesh_base.h:998
HalfEdgeDataCloud & getHalfEdgeDataCloud()
Get access to the stored half-edge data.
Definition: mesh_base.h:943
HalfEdgeIndex getTargetIndex() const
Get the index to the outer half-edge.
EdgeDataCloud & getEdgeDataCloud()
Get access to the stored edge data.
Definition: mesh_base.h:981
bool isDeleted(const HalfEdgeIndex &idx_he) const
Check if the given half-edge is marked as deleted.
Definition: mesh_base.h:650
pcl::geometry::FaceAroundFaceCirculator< const Self > FaceAroundFaceCirculator
Definition: mesh_base.h:149
pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator< const Self > OutgoingHalfEdgeAroundVertexCirculator
Definition: mesh_base.h:143
void reconnectNBNB(const HalfEdgeIndex &idx_he_bc, const HalfEdgeIndex &, const VertexIndex &idx_v_b, boost::false_type)
Both edges are not on the boundary.
Definition: mesh_base.h:1688
pcl::geometry::Face Face
Definition: mesh_base.h:1124
bool isBoundary(const HalfEdgeIndex &idx_he) const
Check if the given half-edge lies on the bounddary.
Definition: mesh_base.h:700
int get() const
Get the index.
Definition: mesh_indices.h:521
bool emptyEdges() const
Check if the edges are empty.
Definition: mesh_base.h:807
MeshTraitsT::VertexData VertexData
Definition: mesh_base.h:108
bool checkTopology1(const VertexIndex &idx_v_a, const VertexIndex &idx_v_b, HalfEdgeIndex &idx_he_ab, std::vector< bool >::reference is_new_ab, boost::true_type) const
Check if the edge between the two vertices can be added.
Definition: mesh_base.h:1241
boost::integral_constant< bool,!boost::is_same< EdgeData, pcl::geometry::NoData >::value > HasEdgeData
Definition: mesh_base.h:122
bool isManifold(boost::true_type) const
Always manifold.
Definition: mesh_base.h:1947
void cleanUp()
Removes all mesh elements and data that are marked as deleted.
Definition: mesh_base.h:274
bool isBoundary(const EdgeIndex &idx_edge) const
Check if the given edge lies on the boundary (any of the two half-edges lies on the boundary...
Definition: mesh_base.h:708
FaceIndex addFace(const VertexIndices &vertices, const FaceData &face_data=FaceData(), const EdgeData &edge_data=EdgeData(), const HalfEdgeData &half_edge_data=HalfEdgeData())
Add a face to the mesh.
Definition: mesh_base.h:195
bool isManifold(boost::false_type) const
Check if all vertices in the mesh are manifold.
Definition: mesh_base.h:1954
VertexDataCloud getVertexDataCloud() const
Get the stored vertex data.
Definition: mesh_base.h:912
bool isDeleted(const EdgeIndex &idx_edge) const
Check if the given edge (any of the two half-edges) is marked as deleted.
Definition: mesh_base.h:658
pcl::geometry::Vertex Vertex
Definition: mesh_base.h:1122
void addData(pcl::PointCloud< DataT > &cloud, const DataT &data, boost::true_type)
Add mesh data.
Definition: mesh_base.h:1515
FaceAroundVertexCirculator getFaceAroundVertexCirculator(const HalfEdgeIndex &idx_outgoing_half_edge) const
Definition: mesh_base.h:492
VertexDataCloud & getVertexDataCloud()
Get access to the stored vertex data.
Definition: mesh_base.h:905
void setFaceIndex(const HalfEdgeIndex &idx_half_edge, const FaceIndex &idx_face)
Set the face index to a given half-edge.
Definition: mesh_base.h:1868
A face is a closed loop of edges.
Circulates clockwise around a face and returns an index to the inner half-edge (the target)...
void deleteFace(const FaceIndex &idx_face)
Mark the given face as deleted.
Definition: mesh_base.h:262
bool checkTopology1(const VertexIndex &idx_v_a, const VertexIndex &idx_v_b, HalfEdgeIndex &idx_he_ab, std::vector< bool >::reference is_new_ab, boost::false_type) const
Non manifold version of checkTopology1.
Definition: mesh_base.h:1259
void reserveData(DataCloudT &cloud, const size_t n, boost::true_type) const
Reserve storage space for the mesh data.
Definition: mesh_base.h:1969
pcl::geometry::IncomingHalfEdgeAroundVertexCirculator< const Self > IncomingHalfEdgeAroundVertexCirculator
Definition: mesh_base.h:144
void markDeleted(const FaceIndex &idx_face)
Mark the given face as deleted.
Definition: mesh_base.h:1730
bool isEqualTopology(const Self &other) const
Check if the other mesh has the same topology as this mesh.
Definition: mesh_base.h:568
void connectNewOld(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, const VertexIndex &idx_v_b)
The first half-edge is new.
Definition: mesh_base.h:1445
Circulates clockwise around a face and returns an index to the outer half-edge (the target)...
Circulates counter-clockwise around a vertex and returns an index to the face of the outgoing half-ed...
pcl::geometry::InnerHalfEdgeAroundFaceCirculator< const Self > InnerHalfEdgeAroundFaceCirculator
Definition: mesh_base.h:147
FaceAroundVertexCirculator getFaceAroundVertexCirculator(const VertexIndex &idx_vertex) const
Definition: mesh_base.h:484
Base class for the half-edge mesh.
Definition: mesh_base.h:97
pcl::geometry::HalfEdge HalfEdge
Definition: mesh_base.h:1123
void incrementIf(IteratorT &it, boost::true_type) const
Increment the iterator.
Definition: mesh_base.h:1805
bool checkTopology2(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc, const bool is_new_ab, const bool is_new_bc, const bool, std::vector< bool >::reference make_adjacent_ab_bc, HalfEdgeIndex &idx_free_half_edge, boost::false_type) const
Check if the half-edge bc is the next half-edge of ab.
Definition: mesh_base.h:1312
bool isBoundary(const FaceIndex &idx_face) const
Check if the given face lies on the boundary.
Definition: mesh_base.h:719
VertexAroundVertexCirculator getVertexAroundVertexCirculator(const VertexIndex &idx_vertex) const
Definition: mesh_base.h:436
Vertices::const_iterator VertexConstIterator
Definition: mesh_base.h:1134
Face getFace(const FaceIndex &idx_face) const
Get the face for the given index.
Definition: mesh_base.h:2076
void deleteVertex(const VertexIndex &idx_vertex)
Mark the given vertex and all connected half-edges and faces as deleted.
Definition: mesh_base.h:208
pcl::PointCloud< FaceData > FaceDataCloud
Definition: mesh_base.h:128
void reserveEdges(const size_t n)
Reserve storage space for n edges (2*n storage space is reserved for the half-edges).
Definition: mesh_base.h:833
bool emptyFaces() const
Check if the faces are empty.
Definition: mesh_base.h:814
void markDeleted(const HalfEdgeIndex &idx_he)
Mark the given half-edge as deleted.
Definition: mesh_base.h:1713
VertexIndex getOriginatingVertexIndex(const HalfEdgeIndex &idx_half_edge) const
Get the originating vertex index to a given half-edge.
Definition: mesh_base.h:363
HalfEdgeIndex getHalfEdgeIndex(const HalfEdgeData &half_edge_data) const
Get the index associated to the given half-edge data.
Definition: mesh_base.h:1072
HalfEdgeIndex getInnerHalfEdgeIndex(const FaceIndex &idx_face) const
Get the inner half-edge index to a given face.
Definition: mesh_base.h:416
pcl::geometry::OuterHalfEdgeAroundFaceCirculator< const Self > OuterHalfEdgeAroundFaceCirculator
Definition: mesh_base.h:148
void clearData(DataCloudT &, boost::false_type) const
Does nothing.
Definition: mesh_base.h:2002
bool setFaceDataCloud(const FaceDataCloud &face_data_cloud)
Change the stored face data.
Definition: mesh_base.h:1036
HalfEdge getHalfEdge(const HalfEdgeIndex &idx_he) const
Get the half-edge for the given index.
Definition: mesh_base.h:2048
pcl::geometry::FaceIndex FaceIndex
Definition: mesh_base.h:134
HalfEdgeIndex getOuterHalfEdgeIndex(const FaceIndex &idx_face) const
Get the outer half-edge inex to a given face.
Definition: mesh_base.h:424
OutgoingHalfEdgeAroundVertexCirculator getOutgoingHalfEdgeAroundVertexCirculator(const HalfEdgeIndex &idx_outgoing_half_edge) const
Definition: mesh_base.h:460
HalfEdgeIndex getTargetIndex() const
Get the index to the incoming half-edge.
std::vector< VertexIndex > VertexIndices
Definition: mesh_base.h:136
bool checkTopology2(const HalfEdgeIndex &, const HalfEdgeIndex &, const bool is_new_ab, const bool is_new_bc, const bool is_isolated_b, std::vector< bool >::reference, HalfEdgeIndex &, boost::true_type) const
Check if the face may be added (mesh does not become non-manifold).
Definition: mesh_base.h:1289
void setVertex(const VertexIndex &idx_vertex, const Vertex &vertex)
Set the vertex at the given index.
Definition: mesh_base.h:2028
HalfEdgeIndex getTargetIndex() const
Get the index to the outgoing half-edge.
FaceDataCloud getFaceDataCloud() const
Get the stored face data.
Definition: mesh_base.h:1026
bool isManifold() const
Check if the mesh is manifold.
Definition: mesh_base.h:748
bool setVertexDataCloud(const VertexDataCloud &vertex_data_cloud)
Change the stored vertex data.
Definition: mesh_base.h:922