Point Cloud Library (PCL)  1.7.0
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 ();
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 */
441  {
442  assert (this->isValid (idx_vertex));
443  return (VertexAroundVertexCirculator (idx_vertex, this));
444  }
445 
446  /** \see pcl::geometry::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 */
457  {
458  assert (this->isValid (idx_vertex));
459  return (OutgoingHalfEdgeAroundVertexCirculator (idx_vertex, this));
460  }
461 
462  /** \see pcl::geometry::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 */
473  {
474  assert (this->isValid (idx_vertex));
475  return (IncomingHalfEdgeAroundVertexCirculator (idx_vertex, this));
476  }
477 
478  /** \see pcl::geometry::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 */
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 */
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 */
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 */
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 */
521  {
522  assert (this->isValid (idx_face));
523  return (InnerHalfEdgeAroundFaceCirculator (idx_face, this));
524  }
525 
526  /** \see pcl::geometry::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 */
537  {
538  assert (this->isValid (idx_face));
539  return (OuterHalfEdgeAroundFaceCirculator (idx_face, this));
540  }
541 
542  /** \see pcl::geometry::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 */
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 */
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 <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  */
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 
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_ha_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
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_ha_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  {
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 ();
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
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  * \IndexContainerT e.g. std::vector <VertexIndex>
1747  * \ElementContainerT e.g. std::vector <Vertex>
1748  * \DataContainerT e.g. std::vector <VertexData>
1749  * \HasDataT Integral constant specifying if the mesh has data associated with the elements.
1750  * \param[in, out] elements Container for the mesh elements. Resized to the new size.
1751  * \param[in, out] data_cloud Container for the mesh data. Resized to the new size.
1752  * \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.
1753  */
1754  template <class ElementContainerT, class DataContainerT, class IndexContainerT, class HasDataT> IndexContainerT
1755  remove (ElementContainerT& elements, DataContainerT& data_cloud)
1756  {
1757  typedef typename IndexContainerT::value_type Index;
1758  typedef typename ElementContainerT::value_type Element;
1759 
1760  if (HasDataT::value) assert (elements.size () == data_cloud.size ());
1761  else assert (data_cloud.empty ()); // Bug in this class!
1762 
1763  IndexContainerT new_indices (elements.size (), typename IndexContainerT::value_type ());
1764  Index ind_old (0), ind_new (0);
1765 
1766  typename ElementContainerT::const_iterator it_e_old = elements.begin ();
1767  typename ElementContainerT::iterator it_e_new = elements.begin ();
1768 
1769  typename DataContainerT::const_iterator it_d_old = data_cloud.begin ();
1770  typename DataContainerT::iterator it_d_new = data_cloud.begin ();
1771 
1772  typename IndexContainerT::iterator it_ind_new = new_indices.begin ();
1773  typename IndexContainerT::const_iterator it_ind_new_end = new_indices.end ();
1774 
1775  while (it_ind_new!=it_ind_new_end)
1776  {
1777  if (!this->isDeleted (ind_old))
1778  {
1779  *it_ind_new = ind_new++;
1780 
1781  // TODO: Test for self assignment?
1782  *it_e_new++ = *it_e_old;
1783  this->assignIf (it_d_old, it_d_new, HasDataT ());
1784  this->incrementIf ( it_d_new, HasDataT ());
1785  }
1786  ++ind_old;
1787  ++it_e_old;
1788  this->incrementIf (it_d_old, HasDataT ());
1789  ++it_ind_new;
1790  }
1791 
1792  elements.resize (ind_new.get (), Element ());
1793  if (HasDataT::value)
1794  {
1795  data_cloud.resize (ind_new.get ());
1796  }
1797  else if (it_d_old != data_cloud.begin () || it_d_new != data_cloud.begin ())
1798  {
1799  std::cerr << "TODO: Bug in MeshBase::remove!\n";
1800  assert (false);
1801  exit (EXIT_FAILURE);
1802  }
1803 
1804  return (new_indices);
1805  }
1806 
1807  /** \brief Increment the iterator. */
1808  template <class IteratorT> inline void
1809  incrementIf (IteratorT& it, boost::true_type /*has_data*/) const
1810  {
1811  ++it;
1812  }
1813 
1814  /** \brief Does nothing. */
1815  template <class IteratorT> inline void
1816  incrementIf (IteratorT& /*it*/, boost::false_type /*has_data*/) const
1817  {
1818  }
1819 
1820  /** \brief Assign the source iterator to the target iterator. */
1821  template <class ConstIteratorT, class IteratorT> inline void
1822  assignIf (const ConstIteratorT source, IteratorT target, boost::true_type /*has_data*/) const
1823  {
1824  *target = *source;
1825  }
1826 
1827  /** \brief Does nothing. */
1828  template <class ConstIteratorT, class IteratorT> inline void
1829  assignIf (const ConstIteratorT /*source*/, IteratorT /*target*/, boost::false_type /*has_data*/) const
1830  {
1831  }
1832 
1833  ////////////////////////////////////////////////////////////////////////
1834  // Vertex / Half-edge / Face connectivity
1835  ////////////////////////////////////////////////////////////////////////
1836 
1837  /** \brief Set the outgoing half-edge index to a given vertex. */
1838  inline void
1839  setOutgoingHalfEdgeIndex (const VertexIndex& idx_vertex, const HalfEdgeIndex& idx_outgoing_half_edge)
1840  {
1841  assert (this->isValid (idx_vertex));
1842  this->getVertex (idx_vertex).idx_outgoing_half_edge_ = idx_outgoing_half_edge;
1843  }
1844 
1845  /** \brief Set the terminating vertex index to a given half-edge. */
1846  inline void
1847  setTerminatingVertexIndex (const HalfEdgeIndex& idx_half_edge, const VertexIndex& idx_terminating_vertex)
1848  {
1849  assert (this->isValid (idx_half_edge));
1850  this->getHalfEdge (idx_half_edge).idx_terminating_vertex_ = idx_terminating_vertex;
1851  }
1852 
1853  /** \brief Set the next half_edge index to a given half-edge. */
1854  inline void
1855  setNextHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge, const HalfEdgeIndex& idx_next_half_edge)
1856  {
1857  assert (this->isValid (idx_half_edge));
1858  this->getHalfEdge (idx_half_edge).idx_next_half_edge_ = idx_next_half_edge;
1859  }
1860 
1861  /** \brief Set the previous half-edge index to a given half-edge. */
1862  inline void
1863  setPrevHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge,
1864  const HalfEdgeIndex& idx_prev_half_edge)
1865  {
1866  assert (this->isValid (idx_half_edge));
1867  this->getHalfEdge (idx_half_edge).idx_prev_half_edge_ = idx_prev_half_edge;
1868  }
1869 
1870  /** \brief Set the face index to a given half-edge. */
1871  inline void
1872  setFaceIndex (const HalfEdgeIndex& idx_half_edge, const FaceIndex& idx_face)
1873  {
1874  assert (this->isValid (idx_half_edge));
1875  this->getHalfEdge (idx_half_edge).idx_face_ = idx_face;
1876  }
1877 
1878  /** \brief Set the inner half-edge index to a given face. */
1879  inline void
1880  setInnerHalfEdgeIndex (const FaceIndex& idx_face, const HalfEdgeIndex& idx_inner_half_edge)
1881  {
1882  assert (this->isValid (idx_face));
1883  this->getFace (idx_face).idx_inner_half_edge_ = idx_inner_half_edge;
1884  }
1885 
1886  ////////////////////////////////////////////////////////////////////////
1887  // isBoundary / isManifold
1888  ////////////////////////////////////////////////////////////////////////
1889 
1890  /** \brief Check if any vertex of the face lies on the boundary. */
1891  bool
1892  isBoundary (const FaceIndex& idx_face, boost::true_type /*check_vertices*/) const
1893  {
1895  const VertexAroundFaceCirculator circ_end = circ;
1896 
1897  do
1898  {
1899  if (this->isBoundary (circ.getTargetIndex ()))
1900  {
1901  return (true);
1902  }
1903  } while (++circ!=circ_end);
1904 
1905  return (false);
1906  }
1907 
1908  /** \brief Check if any edge of the face lies on the boundary. */
1909  bool
1910  isBoundary (const FaceIndex& idx_face, boost::false_type /*check_vertices*/) const
1911  {
1913  const OuterHalfEdgeAroundFaceCirculator circ_end = circ;
1914 
1915  do
1916  {
1917  if (this->isBoundary (circ.getTargetIndex ()))
1918  {
1919  return (true);
1920  }
1921  } while (++circ!=circ_end);
1922 
1923  return (false);
1924  }
1925 
1926  /** \brief Always manifold. */
1927  inline bool
1928  isManifold (const VertexIndex&, boost::true_type /*is_manifold*/) const
1929  {
1930  return (true);
1931  }
1932 
1933  /** \brief Check if the given vertex is manifold. */
1934  bool
1935  isManifold (const VertexIndex& idx_vertex, boost::false_type /*is_manifold*/) const
1936  {
1938  const OutgoingHalfEdgeAroundVertexCirculator circ_end = circ;
1939 
1940  if (!this->isBoundary ((circ++).getTargetIndex ())) return (true);
1941  do
1942  {
1943  if (this->isBoundary (circ.getTargetIndex ())) return (false);
1944  } while (++circ != circ_end);
1945 
1946  return (true);
1947  }
1948 
1949  /** \brief Always manifold. */
1950  inline bool
1951  isManifold (boost::true_type /*is_manifold*/) const
1952  {
1953  return (true);
1954  }
1955 
1956  /** \brief Check if all vertices in the mesh are manifold. */
1957  bool
1958  isManifold (boost::false_type /*is_manifold*/) const
1959  {
1960  for (unsigned int i=0; i<this->sizeVertices (); ++i)
1961  {
1962  if (!this->isManifold (VertexIndex (i))) return (false);
1963  }
1964  return (true);
1965  }
1966 
1967  ////////////////////////////////////////////////////////////////////////
1968  // reserveData / resizeData / clearData
1969  ////////////////////////////////////////////////////////////////////////
1970 
1971  /** \brief Reserve storage space for the mesh data. */
1972  template <class DataCloudT> inline void
1973  reserveData (DataCloudT& cloud, const size_t n, boost::true_type /*has_data*/) const
1974  {
1975  cloud.reserve (n);
1976  }
1977 
1978  /** \brief Does nothing */
1979  template <class DataCloudT> inline void
1980  reserveData (DataCloudT& /*cloud*/, const size_t /*n*/, boost::false_type /*has_data*/) const
1981  {
1982  }
1983 
1984  /** \brief Resize the mesh data. */
1985  template <class DataCloudT> inline void
1986  resizeData (DataCloudT& data_cloud, const size_t n, const typename DataCloudT::value_type& data, boost::true_type /*has_data*/) const
1987  {
1988  data.resize (n, data);
1989  }
1990 
1991  /** \brief Does nothing. */
1992  template <class DataCloudT> inline void
1993  resizeData (DataCloudT& /*data_cloud*/, const size_t /*n*/, const typename DataCloudT::value_type& /*data*/, boost::false_type /*has_data*/) const
1994  {
1995  }
1996 
1997  /** \brief Clear the mesh data. */
1998  template <class DataCloudT> inline void
1999  clearData (DataCloudT& cloud, boost::true_type /*has_data*/) const
2000  {
2001  cloud.clear ();
2002  }
2003 
2004  /** \brief Does nothing. */
2005  template <class DataCloudT> inline void
2006  clearData (DataCloudT& /*cloud*/, boost::false_type /*has_data*/) const
2007  {
2008  }
2009 
2010  ////////////////////////////////////////////////////////////////////////
2011  // get / set Vertex
2012  ////////////////////////////////////////////////////////////////////////
2013 
2014  /** \brief Get the vertex for the given index. */
2015  inline Vertex&
2016  getVertex (const VertexIndex& idx_vertex)
2017  {
2018  assert (this->isValid (idx_vertex));
2019  return (vertices_ [idx_vertex.get ()]);
2020  }
2021 
2022  /** \brief Get the vertex for the given index. */
2023  inline Vertex
2024  getVertex (const VertexIndex& idx_vertex) const
2025  {
2026  assert (this->isValid (idx_vertex));
2027  return (vertices_ [idx_vertex.get ()]);
2028  }
2029 
2030  /** \brief Set the vertex at the given index. */
2031  inline void
2032  setVertex (const VertexIndex& idx_vertex, const Vertex& vertex)
2033  {
2034  assert (this->isValid (idx_vertex));
2035  vertices_ [idx_vertex.get ()] = vertex;
2036  }
2037 
2038  ////////////////////////////////////////////////////////////////////////
2039  // get / set HalfEdge
2040  ////////////////////////////////////////////////////////////////////////
2041 
2042  /** \brief Get the half-edge for the given index. */
2043  inline HalfEdge&
2044  getHalfEdge (const HalfEdgeIndex& idx_he)
2045  {
2046  assert (this->isValid (idx_he));
2047  return (half_edges_ [idx_he.get ()]);
2048  }
2049 
2050  /** \brief Get the half-edge for the given index. */
2051  inline HalfEdge
2052  getHalfEdge (const HalfEdgeIndex& idx_he) const
2053  {
2054  assert (this->isValid (idx_he));
2055  return (half_edges_ [idx_he.get ()]);
2056  }
2057 
2058  /** \brief Set the half-edge at the given index. */
2059  inline void
2060  setHalfEdge (const HalfEdgeIndex& idx_he, const HalfEdge& half_edge)
2061  {
2062  assert (this->isValid (idx_he));
2063  half_edges_ [idx_he.get ()] = half_edge;
2064  }
2065 
2066  ////////////////////////////////////////////////////////////////////////
2067  // get / set Face
2068  ////////////////////////////////////////////////////////////////////////
2069 
2070  /** \brief Get the face for the given index. */
2071  inline Face&
2072  getFace (const FaceIndex& idx_face)
2073  {
2074  assert (this->isValid (idx_face));
2075  return (faces_ [idx_face.get ()]);
2076  }
2077 
2078  /** \brief Get the face for the given index. */
2079  inline Face
2080  getFace (const FaceIndex& idx_face) const
2081  {
2082  assert (this->isValid (idx_face));
2083  return (faces_ [idx_face.get ()]);
2084  }
2085 
2086  /** \brief Set the face at the given index. */
2087  inline void
2088  setFace (const FaceIndex& idx_face, const Face& face)
2089  {
2090  assert (this->isValid (idx_face));
2091  faces_ [idx_face.get ()] = face;
2092  }
2093 
2094  private:
2095 
2096  ////////////////////////////////////////////////////////////////////////
2097  // Members
2098  ////////////////////////////////////////////////////////////////////////
2099 
2100  /** \brief Data stored for the vertices. */
2101  VertexDataCloud vertex_data_cloud_;
2102 
2103  /** \brief Data stored for the half-edges. */
2104  HalfEdgeDataCloud half_edge_data_cloud_;
2105 
2106  /** \brief Data stored for the edges. */
2107  EdgeDataCloud edge_data_cloud_;
2108 
2109  /** \brief Data stored for the faces. */
2110  FaceDataCloud face_data_cloud_;
2111 
2112  /** \brief Connectivity information for the vertices. */
2113  Vertices vertices_;
2114 
2115  /** \brief Connectivity information for the half-edges. */
2116  HalfEdges half_edges_;
2117 
2118  /** \brief Connectivity information for the faces. */
2119  Faces faces_;
2120 
2121  // NOTE: It is MUCH faster to store these variables permamently.
2122 
2123  /** \brief Storage for addFaceImplBase and deleteFace. */
2124  HalfEdgeIndices inner_he_;
2125 
2126  /** \brief Storage for addFaceImplBase. */
2127  HalfEdgeIndices free_he_;
2128 
2129  /** \brief Storage for addFaceImplBase. */
2130  std::vector <bool> is_new_;
2131 
2132  /** \brief Storage for addFaceImplBase. */
2133  std::vector <bool> make_adjacent_;
2134 
2135  /** \brief Storage for deleteFace. */
2136  std::vector <bool> is_boundary_;
2137 
2138  /** \brief Storage for deleteVertex. */
2139  FaceIndices delete_faces_vertex_;
2140 
2141  /** \brief Storage for deleteFace. */
2142  FaceIndices delete_faces_face_;
2143 
2144  public:
2145 
2146  template <class MeshT>
2148 
2149  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
2150  };
2151  } // End namespace geometry
2152 } // End namespace pcl
2153 
2154 #endif // PCL_GEOMETRY_MESH_BASE_H