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