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