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