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