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