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