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