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