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