Point Cloud Library (PCL)
1.7.0
|
00001 /* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Point Cloud Library (PCL) - www.pointclouds.org 00005 * Copyright (c) 2009-2012, Willow Garage, Inc. 00006 * Copyright (c) 2012-, Open Perception, Inc. 00007 * 00008 * All rights reserved. 00009 * 00010 * Redistribution and use in source and binary forms, with or without 00011 * modification, are permitted provided that the following conditions 00012 * are met: 00013 * 00014 * * Redistributions of source code must retain the above copyright 00015 * notice, this list of conditions and the following disclaimer. 00016 * * Redistributions in binary form must reproduce the above 00017 * copyright notice, this list of conditions and the following 00018 * disclaimer in the documentation and/or other materials provided 00019 * with the distribution. 00020 * * Neither the name of the copyright holder(s) nor the names of its 00021 * contributors may be used to endorse or promote products derived 00022 * from this software without specific prior written permission. 00023 * 00024 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00025 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00026 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00027 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00028 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00029 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 00030 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 00031 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00032 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00033 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 00034 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00035 * POSSIBILITY OF SUCH DAMAGE. 00036 * 00037 * $Id$ 00038 * 00039 */ 00040 00041 #ifndef PCL_GEOMETRY_MESH_BASE_H 00042 #define PCL_GEOMETRY_MESH_BASE_H 00043 00044 #include <vector> 00045 00046 #include <pcl/geometry/boost.h> 00047 #include <pcl/geometry/eigen.h> 00048 #include <pcl/geometry/mesh_circulators.h> 00049 #include <pcl/geometry/mesh_indices.h> 00050 #include <pcl/geometry/mesh_elements.h> 00051 #include <pcl/geometry/mesh_traits.h> 00052 #include <pcl/point_cloud.h> 00053 00054 //////////////////////////////////////////////////////////////////////////////// 00055 // Global variables used during testing 00056 //////////////////////////////////////////////////////////////////////////////// 00057 00058 #ifdef PCL_GEOMETRY_MESH_BASE_TEST_DELETE_FACE_MANIFOLD_2 00059 namespace pcl 00060 { 00061 namespace geometry 00062 { 00063 bool g_pcl_geometry_mesh_base_test_delete_face_manifold_2_success; 00064 } // End namespace geometry 00065 } // End namespace pcl 00066 #endif 00067 00068 //////////////////////////////////////////////////////////////////////////////// 00069 // Forward declarations 00070 //////////////////////////////////////////////////////////////////////////////// 00071 00072 namespace pcl 00073 { 00074 namespace geometry 00075 { 00076 template <class MeshT> 00077 class MeshIO; 00078 } // End namespace geometry 00079 } // End namespace pcl 00080 00081 //////////////////////////////////////////////////////////////////////////////// 00082 // MeshBase 00083 //////////////////////////////////////////////////////////////////////////////// 00084 00085 namespace pcl 00086 { 00087 namespace geometry 00088 { 00089 /** \brief Base class for the half-edge mesh. 00090 * \tparam DerivedT Has to implement the method 'addFaceImpl'. Please have a look at pcl::geometry::TriangleMesh, pcl::geometry::QuadMesh and pcl::geometry::PolygonMesh. 00091 * \tparam MeshTraitsT Please have a look at pcl::geometry::DefaultMeshTraits. 00092 * \tparam MeshTagT Tag describing the type of the mesh, e.g. TriangleMeshTag, QuadMeshTag, PolygonMeshTag. 00093 * \author Martin Saelzle 00094 * \ingroup geometry 00095 * \todo Add documentation 00096 */ 00097 template <class DerivedT, class MeshTraitsT, class MeshTagT> 00098 class MeshBase 00099 { 00100 public: 00101 00102 typedef MeshBase <DerivedT, MeshTraitsT, MeshTagT> Self; 00103 typedef boost::shared_ptr <Self> Ptr; 00104 typedef boost::shared_ptr <const Self> ConstPtr; 00105 00106 typedef DerivedT Derived; 00107 00108 // These have to be defined in the traits class. 00109 typedef typename MeshTraitsT::VertexData VertexData; 00110 typedef typename MeshTraitsT::HalfEdgeData HalfEdgeData; 00111 typedef typename MeshTraitsT::EdgeData EdgeData; 00112 typedef typename MeshTraitsT::FaceData FaceData; 00113 typedef typename MeshTraitsT::IsManifold IsManifold; 00114 00115 // Check if the mesh traits are defined correctly. 00116 BOOST_CONCEPT_ASSERT ((boost::Convertible <IsManifold, bool>)); 00117 00118 typedef MeshTagT MeshTag; 00119 00120 // Data 00121 typedef boost::integral_constant <bool, !boost::is_same <VertexData , pcl::geometry::NoData>::value> HasVertexData; 00122 typedef boost::integral_constant <bool, !boost::is_same <HalfEdgeData, pcl::geometry::NoData>::value> HasHalfEdgeData; 00123 typedef boost::integral_constant <bool, !boost::is_same <EdgeData , pcl::geometry::NoData>::value> HasEdgeData; 00124 typedef boost::integral_constant <bool, !boost::is_same <FaceData , pcl::geometry::NoData>::value> HasFaceData; 00125 00126 typedef pcl::PointCloud <VertexData> VertexDataCloud; 00127 typedef pcl::PointCloud <HalfEdgeData> HalfEdgeDataCloud; 00128 typedef pcl::PointCloud <EdgeData> EdgeDataCloud; 00129 typedef pcl::PointCloud <FaceData> FaceDataCloud; 00130 00131 // Indices 00132 typedef pcl::geometry::VertexIndex VertexIndex; 00133 typedef pcl::geometry::HalfEdgeIndex HalfEdgeIndex; 00134 typedef pcl::geometry::EdgeIndex EdgeIndex; 00135 typedef pcl::geometry::FaceIndex FaceIndex; 00136 00137 typedef std::vector <VertexIndex> VertexIndices; 00138 typedef std::vector <HalfEdgeIndex> HalfEdgeIndices; 00139 typedef std::vector <EdgeIndex> EdgeIndices; 00140 typedef std::vector <FaceIndex> FaceIndices; 00141 00142 // Circulators 00143 typedef pcl::geometry::VertexAroundVertexCirculator <const Self> VertexAroundVertexCirculator; 00144 typedef pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator <const Self> OutgoingHalfEdgeAroundVertexCirculator; 00145 typedef pcl::geometry::IncomingHalfEdgeAroundVertexCirculator <const Self> IncomingHalfEdgeAroundVertexCirculator; 00146 typedef pcl::geometry::FaceAroundVertexCirculator <const Self> FaceAroundVertexCirculator; 00147 typedef pcl::geometry::VertexAroundFaceCirculator <const Self> VertexAroundFaceCirculator; 00148 typedef pcl::geometry::InnerHalfEdgeAroundFaceCirculator <const Self> InnerHalfEdgeAroundFaceCirculator; 00149 typedef pcl::geometry::OuterHalfEdgeAroundFaceCirculator <const Self> OuterHalfEdgeAroundFaceCirculator; 00150 typedef pcl::geometry::FaceAroundFaceCirculator <const Self> FaceAroundFaceCirculator; 00151 00152 /** \brief Constructor. */ 00153 MeshBase () 00154 : vertex_data_cloud_ (), 00155 half_edge_data_cloud_ (), 00156 edge_data_cloud_ (), 00157 face_data_cloud_ (), 00158 vertices_ (), 00159 half_edges_ (), 00160 faces_ (), 00161 inner_he_ (), 00162 free_he_ (), 00163 is_new_ (), 00164 make_adjacent_ (), 00165 is_boundary_ (), 00166 delete_faces_vertex_ (), 00167 delete_faces_face_ () 00168 { 00169 } 00170 00171 //////////////////////////////////////////////////////////////////////// 00172 // addVertex / addFace / deleteVertex / deleteEdge / deleteFace / cleanUp 00173 //////////////////////////////////////////////////////////////////////// 00174 00175 /** \brief Add a vertex to the mesh. 00176 * \param[in] vertex_data Data that is stored in the vertex. This is only added if the mesh has data associated with the vertices. 00177 * \return Index to the new vertex. 00178 */ 00179 inline VertexIndex 00180 addVertex (const VertexData& vertex_data=VertexData ()) 00181 { 00182 vertices_.push_back (Vertex ()); 00183 this->addData (vertex_data_cloud_, vertex_data, HasVertexData ()); 00184 return (VertexIndex (static_cast <int> (this->sizeVertices () - 1))); 00185 } 00186 00187 /** \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. 00188 * \param[in] vertices Indices to the vertices of the new face. 00189 * \param[in] face_data Data that is set for the face. 00190 * \param[in] half_edge_data Data that is set for all added half-edges. 00191 * \param[in] edge_data Data that is set for all added edges. 00192 * \return Index to the new face. Failure is signaled by returning an invalid face index. 00193 * \warning The vertices must be valid and unique (each vertex may be contained only once). Not complying with this requirement results in undefined behavior! 00194 */ 00195 inline FaceIndex 00196 addFace (const VertexIndices& vertices, 00197 const FaceData& face_data = FaceData (), 00198 const EdgeData& edge_data = EdgeData (), 00199 const HalfEdgeData& half_edge_data = HalfEdgeData ()) 00200 { 00201 // NOTE: The derived class has to implement addFaceImpl. If needed it can use the general method addFaceImplBase. 00202 return (static_cast <Derived*> (this)->addFaceImpl (vertices, face_data, edge_data, half_edge_data)); 00203 } 00204 00205 /** \brief Mark the given vertex and all connected half-edges and faces as deleted. 00206 * \note Call cleanUp () to finally delete all mesh-elements. 00207 */ 00208 void 00209 deleteVertex (const VertexIndex& idx_vertex) 00210 { 00211 assert (this->isValid (idx_vertex)); 00212 if (this->isDeleted (idx_vertex)) return; 00213 00214 delete_faces_vertex_.clear (); 00215 FaceAroundVertexCirculator circ = this->getFaceAroundVertexCirculator (idx_vertex); 00216 const FaceAroundVertexCirculator circ_end = circ; 00217 do 00218 { 00219 if (circ.getTargetIndex ().isValid ()) // Check for boundary. 00220 { 00221 delete_faces_vertex_.push_back (circ.getTargetIndex ()); 00222 } 00223 } while (++circ!=circ_end); 00224 00225 for (FaceIndices::const_iterator it = delete_faces_vertex_.begin (); it!=delete_faces_vertex_.end (); ++it) 00226 { 00227 this->deleteFace (*it); 00228 } 00229 } 00230 00231 /** \brief Mark the given half-edge, the opposite half-edge and the associated faces as deleted. 00232 * \note Call cleanUp () to finally delete all mesh-elements. 00233 */ 00234 void 00235 deleteEdge (const HalfEdgeIndex& idx_he) 00236 { 00237 assert (this->isValid (idx_he)); 00238 if (this->isDeleted (idx_he)) return; 00239 00240 HalfEdgeIndex opposite = this->getOppositeHalfEdgeIndex (idx_he); 00241 00242 if (this->isBoundary (idx_he)) this->markDeleted (idx_he); 00243 else this->deleteFace (this->getFaceIndex (idx_he)); 00244 if (this->isBoundary (opposite)) this->markDeleted (opposite); 00245 else this->deleteFace (this->getFaceIndex (opposite)); 00246 } 00247 00248 /** \brief Mark the given edge (both half-edges) and the associated faces as deleted. 00249 * \note Call cleanUp () to finally delete all mesh-elements. 00250 */ 00251 inline void 00252 deleteEdge (const EdgeIndex& idx_edge) 00253 { 00254 assert (this->isValid (idx_edge)); 00255 this->deleteEdge (pcl::geometry::toHalfEdgeIndex (idx_edge)); 00256 assert (this->isDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, false))); // Bug in this class! 00257 } 00258 00259 /** \brief Mark the given face as deleted. More faces are deleted if the manifold mesh would become non-manifold. 00260 * \note Call cleanUp () to finally delete all mesh-elements. 00261 */ 00262 inline void 00263 deleteFace (const FaceIndex& idx_face) 00264 { 00265 assert (this->isValid (idx_face)); 00266 if (this->isDeleted (idx_face)) return; 00267 00268 this->deleteFace (idx_face, IsManifold ()); 00269 } 00270 00271 /** \brief Removes all mesh elements and data that are marked as deleted. 00272 * \note This removes all isolated vertices as well. 00273 */ 00274 void 00275 cleanUp () 00276 { 00277 // Copy the non-deleted mesh elements and store the index to their new position 00278 const VertexIndices new_vertex_indices = 00279 this->remove <Vertices, VertexDataCloud, VertexIndices, HasVertexData> 00280 (vertices_, vertex_data_cloud_); 00281 const HalfEdgeIndices new_half_edge_indices = 00282 this->remove <HalfEdges, HalfEdgeDataCloud, HalfEdgeIndices, HasHalfEdgeData> 00283 (half_edges_, half_edge_data_cloud_); 00284 const FaceIndices new_face_indices = 00285 this->remove <Faces, FaceDataCloud, FaceIndices, HasFaceData> 00286 (faces_, face_data_cloud_); 00287 00288 // Remove deleted edge data 00289 if (HasEdgeData::value) 00290 { 00291 typename EdgeDataCloud::const_iterator it_ed_old = edge_data_cloud_.begin (); 00292 typename EdgeDataCloud::iterator it_ed_new = edge_data_cloud_.begin (); 00293 00294 HalfEdgeIndices::const_iterator it_ind = new_half_edge_indices.begin (); 00295 HalfEdgeIndices::const_iterator it_ind_end = new_half_edge_indices.end (); 00296 00297 for (; it_ind!=it_ind_end; it_ind+=2, ++it_ed_old) 00298 { 00299 if (it_ind->isValid ()) 00300 { 00301 *it_ed_new++ = *it_ed_old; 00302 } 00303 } 00304 edge_data_cloud_.resize (this->sizeEdges ()); 00305 } 00306 00307 // Adjust the indices 00308 for (VertexIterator it = vertices_.begin (); it!=vertices_.end (); ++it) 00309 { 00310 if (it->idx_outgoing_half_edge_.isValid ()) 00311 { 00312 it->idx_outgoing_half_edge_ = new_half_edge_indices [it->idx_outgoing_half_edge_.get ()]; 00313 } 00314 } 00315 00316 for (HalfEdgeIterator it = half_edges_.begin (); it!=half_edges_.end (); ++it) 00317 { 00318 it->idx_terminating_vertex_ = new_vertex_indices [it->idx_terminating_vertex_.get ()]; 00319 it->idx_next_half_edge_ = new_half_edge_indices [it->idx_next_half_edge_.get ()]; 00320 it->idx_prev_half_edge_ = new_half_edge_indices [it->idx_prev_half_edge_.get ()]; 00321 if (it->idx_face_.isValid ()) 00322 { 00323 it->idx_face_ = new_face_indices [it->idx_face_.get ()]; 00324 } 00325 } 00326 00327 for (FaceIterator it = faces_.begin (); it!=faces_.end (); ++it) 00328 { 00329 it->idx_inner_half_edge_ = new_half_edge_indices [it->idx_inner_half_edge_.get ()]; 00330 } 00331 } 00332 00333 //////////////////////////////////////////////////////////////////////// 00334 // Vertex connectivity 00335 //////////////////////////////////////////////////////////////////////// 00336 00337 /** \brief Get the outgoing half-edge index to a given vertex. */ 00338 inline HalfEdgeIndex 00339 getOutgoingHalfEdgeIndex (const VertexIndex& idx_vertex) const 00340 { 00341 assert (this->isValid (idx_vertex)); 00342 return (this->getVertex (idx_vertex).idx_outgoing_half_edge_); 00343 } 00344 00345 /** \brief Get the incoming half-edge index to a given vertex. */ 00346 inline HalfEdgeIndex 00347 getIncomingHalfEdgeIndex (const VertexIndex& idx_vertex) const 00348 { 00349 assert (this->isValid (idx_vertex)); 00350 return (this->getOppositeHalfEdgeIndex (this->getOutgoingHalfEdgeIndex (idx_vertex))); 00351 } 00352 00353 //////////////////////////////////////////////////////////////////////// 00354 // Half-edge connectivity 00355 //////////////////////////////////////////////////////////////////////// 00356 00357 /** \brief Get the terminating vertex index to a given half-edge. */ 00358 inline VertexIndex 00359 getTerminatingVertexIndex (const HalfEdgeIndex& idx_half_edge) const 00360 { 00361 assert (this->isValid (idx_half_edge)); 00362 return (this->getHalfEdge (idx_half_edge).idx_terminating_vertex_); 00363 } 00364 00365 /** \brief Get the originating vertex index to a given half-edge. */ 00366 inline VertexIndex 00367 getOriginatingVertexIndex (const HalfEdgeIndex& idx_half_edge) const 00368 { 00369 assert (this->isValid (idx_half_edge)); 00370 return (this->getTerminatingVertexIndex (this->getOppositeHalfEdgeIndex (idx_half_edge))); 00371 } 00372 00373 /** \brief Get the opposite half-edge index to a given half-edge. */ 00374 inline HalfEdgeIndex 00375 getOppositeHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge) const 00376 { 00377 assert (this->isValid (idx_half_edge)); 00378 // Check if the index is even or odd and return the other index. 00379 return (HalfEdgeIndex (idx_half_edge.get () & 1 ? idx_half_edge.get () - 1 : idx_half_edge.get () + 1)); 00380 } 00381 00382 /** \brief Get the next half-edge index to a given half-edge. */ 00383 inline HalfEdgeIndex 00384 getNextHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge) const 00385 { 00386 assert (this->isValid (idx_half_edge)); 00387 return (this->getHalfEdge (idx_half_edge).idx_next_half_edge_); 00388 } 00389 00390 /** \brief Get the previous half-edge index to a given half-edge. */ 00391 inline HalfEdgeIndex 00392 getPrevHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge) const 00393 { 00394 assert (this->isValid (idx_half_edge)); 00395 return (this->getHalfEdge (idx_half_edge).idx_prev_half_edge_); 00396 } 00397 00398 /** \brief Get the face index to a given half-edge. */ 00399 inline FaceIndex 00400 getFaceIndex (const HalfEdgeIndex& idx_half_edge) const 00401 { 00402 assert (this->isValid (idx_half_edge)); 00403 return (this->getHalfEdge (idx_half_edge).idx_face_); 00404 } 00405 00406 /** \brief Get the face index to a given half-edge. */ 00407 inline FaceIndex 00408 getOppositeFaceIndex (const HalfEdgeIndex& idx_half_edge) const 00409 { 00410 assert (this->isValid (idx_half_edge)); 00411 return (this->getFaceIndex (this->getOppositeHalfEdgeIndex (idx_half_edge))); 00412 } 00413 00414 //////////////////////////////////////////////////////////////////////// 00415 // Face connectivity 00416 //////////////////////////////////////////////////////////////////////// 00417 00418 /** \brief Get the inner half-edge index to a given face. */ 00419 inline HalfEdgeIndex 00420 getInnerHalfEdgeIndex (const FaceIndex& idx_face) const 00421 { 00422 assert (this->isValid (idx_face)); 00423 return (this->getFace (idx_face).idx_inner_half_edge_); 00424 } 00425 00426 /** \brief Get the outer half-edge inex to a given face. */ 00427 inline HalfEdgeIndex 00428 getOuterHalfEdgeIndex (const FaceIndex& idx_face) const 00429 { 00430 assert (this->isValid (idx_face)); 00431 return (this->getOppositeHalfEdgeIndex (this->getInnerHalfEdgeIndex (idx_face))); 00432 } 00433 00434 //////////////////////////////////////////////////////////////////////// 00435 // Circulators 00436 //////////////////////////////////////////////////////////////////////// 00437 00438 /** \see pcl::geometry::VertexAroundVertexCirculator */ 00439 inline VertexAroundVertexCirculator 00440 getVertexAroundVertexCirculator (const VertexIndex& idx_vertex) const 00441 { 00442 assert (this->isValid (idx_vertex)); 00443 return (VertexAroundVertexCirculator (idx_vertex, this)); 00444 } 00445 00446 /** \see pcl::geometry::VertexAroundVertexCirculator */ 00447 inline VertexAroundVertexCirculator 00448 getVertexAroundVertexCirculator (const HalfEdgeIndex& idx_outgoing_half_edge) const 00449 { 00450 assert (this->isValid (idx_outgoing_half_edge)); 00451 return (VertexAroundVertexCirculator (idx_outgoing_half_edge, this)); 00452 } 00453 00454 /** \see pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator */ 00455 inline OutgoingHalfEdgeAroundVertexCirculator 00456 getOutgoingHalfEdgeAroundVertexCirculator (const VertexIndex& idx_vertex) const 00457 { 00458 assert (this->isValid (idx_vertex)); 00459 return (OutgoingHalfEdgeAroundVertexCirculator (idx_vertex, this)); 00460 } 00461 00462 /** \see pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator */ 00463 inline OutgoingHalfEdgeAroundVertexCirculator 00464 getOutgoingHalfEdgeAroundVertexCirculator (const HalfEdgeIndex& idx_outgoing_half_edge) const 00465 { 00466 assert (this->isValid (idx_outgoing_half_edge)); 00467 return (OutgoingHalfEdgeAroundVertexCirculator (idx_outgoing_half_edge, this)); 00468 } 00469 00470 /** \see pcl::geometry::IncomingHalfEdgeAroundVertexCirculator */ 00471 inline IncomingHalfEdgeAroundVertexCirculator 00472 getIncomingHalfEdgeAroundVertexCirculator (const VertexIndex& idx_vertex) const 00473 { 00474 assert (this->isValid (idx_vertex)); 00475 return (IncomingHalfEdgeAroundVertexCirculator (idx_vertex, this)); 00476 } 00477 00478 /** \see pcl::geometry::IncomingHalfEdgeAroundVertexCirculator */ 00479 inline IncomingHalfEdgeAroundVertexCirculator 00480 getIncomingHalfEdgeAroundVertexCirculator (const HalfEdgeIndex& idx_incoming_half_edge) const 00481 { 00482 assert (this->isValid (idx_incoming_half_edge)); 00483 return (IncomingHalfEdgeAroundVertexCirculator (idx_incoming_half_edge, this)); 00484 } 00485 00486 /** \see pcl::geometry::FaceAroundVertexCirculator */ 00487 inline FaceAroundVertexCirculator 00488 getFaceAroundVertexCirculator (const VertexIndex& idx_vertex) const 00489 { 00490 assert (this->isValid (idx_vertex)); 00491 return (FaceAroundVertexCirculator (idx_vertex, this)); 00492 } 00493 00494 /** \see pcl::geometry::FaceAroundVertexCirculator */ 00495 inline FaceAroundVertexCirculator 00496 getFaceAroundVertexCirculator (const HalfEdgeIndex& idx_outgoing_half_edge) const 00497 { 00498 assert (this->isValid (idx_outgoing_half_edge)); 00499 return (FaceAroundVertexCirculator (idx_outgoing_half_edge, this)); 00500 } 00501 00502 /** \see pcl::geometry::VertexAroundFaceCirculator */ 00503 inline VertexAroundFaceCirculator 00504 getVertexAroundFaceCirculator (const FaceIndex& idx_face) const 00505 { 00506 assert (this->isValid (idx_face)); 00507 return (VertexAroundFaceCirculator (idx_face, this)); 00508 } 00509 00510 /** \see pcl::geometry::VertexAroundFaceCirculator */ 00511 inline VertexAroundFaceCirculator 00512 getVertexAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const 00513 { 00514 assert (this->isValid (idx_inner_half_edge)); 00515 return (VertexAroundFaceCirculator (idx_inner_half_edge, this)); 00516 } 00517 00518 /** \see pcl::geometry::InnerHalfEdgeAroundFaceCirculator */ 00519 inline InnerHalfEdgeAroundFaceCirculator 00520 getInnerHalfEdgeAroundFaceCirculator (const FaceIndex& idx_face) const 00521 { 00522 assert (this->isValid (idx_face)); 00523 return (InnerHalfEdgeAroundFaceCirculator (idx_face, this)); 00524 } 00525 00526 /** \see pcl::geometry::InnerHalfEdgeAroundFaceCirculator */ 00527 inline InnerHalfEdgeAroundFaceCirculator 00528 getInnerHalfEdgeAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const 00529 { 00530 assert (this->isValid (idx_inner_half_edge)); 00531 return (InnerHalfEdgeAroundFaceCirculator (idx_inner_half_edge, this)); 00532 } 00533 00534 /** \see pcl::geometry::OuterHalfEdgeAroundFaceCirculator */ 00535 inline OuterHalfEdgeAroundFaceCirculator 00536 getOuterHalfEdgeAroundFaceCirculator (const FaceIndex& idx_face) const 00537 { 00538 assert (this->isValid (idx_face)); 00539 return (OuterHalfEdgeAroundFaceCirculator (idx_face, this)); 00540 } 00541 00542 /** \see pcl::geometry::OuterHalfEdgeAroundFaceCirculator */ 00543 inline OuterHalfEdgeAroundFaceCirculator 00544 getOuterHalfEdgeAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const 00545 { 00546 assert (this->isValid (idx_inner_half_edge)); 00547 return (OuterHalfEdgeAroundFaceCirculator (idx_inner_half_edge, this)); 00548 } 00549 00550 /** \see pcl::geometry::FaceAroundFaceCirculator */ 00551 inline FaceAroundFaceCirculator 00552 getFaceAroundFaceCirculator (const FaceIndex& idx_face) const 00553 { 00554 assert (this->isValid (idx_face)); 00555 return (FaceAroundFaceCirculator (idx_face, this)); 00556 } 00557 00558 /** \see pcl::geometry::FaceAroundFaceCirculator */ 00559 inline FaceAroundFaceCirculator 00560 getFaceAroundFaceCirculator (const HalfEdgeIndex& idx_inner_half_edge) const 00561 { 00562 assert (this->isValid (idx_inner_half_edge)); 00563 return (FaceAroundFaceCirculator (idx_inner_half_edge, this)); 00564 } 00565 00566 ////////////////////////////////////////////////////////////////////////// 00567 // isEqualTopology 00568 ////////////////////////////////////////////////////////////////////////// 00569 00570 /** \brief Check if the other mesh has the same topology as this mesh. */ 00571 bool 00572 isEqualTopology (const Self& other) const 00573 { 00574 if (this->sizeVertices () != other.sizeVertices ()) return (false); 00575 if (this->sizeHalfEdges () != other.sizeHalfEdges ()) return (false); 00576 if (this->sizeFaces () != other.sizeFaces ()) return (false); 00577 00578 for (unsigned int i=0; i<this->sizeVertices (); ++i) 00579 { 00580 if (this->getOutgoingHalfEdgeIndex (VertexIndex (i)) != 00581 other.getOutgoingHalfEdgeIndex (VertexIndex (i))) return (false); 00582 } 00583 00584 for (unsigned int i=0; i<this->sizeHalfEdges (); ++i) 00585 { 00586 if (this->getTerminatingVertexIndex (HalfEdgeIndex (i)) != 00587 other.getTerminatingVertexIndex (HalfEdgeIndex (i))) return (false); 00588 00589 if (this->getNextHalfEdgeIndex (HalfEdgeIndex (i)) != 00590 other.getNextHalfEdgeIndex (HalfEdgeIndex (i))) return (false); 00591 00592 if (this->getPrevHalfEdgeIndex (HalfEdgeIndex (i)) != 00593 other.getPrevHalfEdgeIndex (HalfEdgeIndex (i))) return (false); 00594 00595 if (this->getFaceIndex (HalfEdgeIndex (i)) != 00596 other.getFaceIndex (HalfEdgeIndex (i))) return (false); 00597 } 00598 00599 for (unsigned int i=0; i<this->sizeFaces (); ++i) 00600 { 00601 if (this->getInnerHalfEdgeIndex (FaceIndex (i)) != 00602 other.getInnerHalfEdgeIndex (FaceIndex (i))) return (false); 00603 } 00604 00605 return (true); 00606 } 00607 00608 //////////////////////////////////////////////////////////////////////// 00609 // isValid 00610 //////////////////////////////////////////////////////////////////////// 00611 00612 /** \brief Check if the given vertex index is a valid index into the mesh. */ 00613 inline bool 00614 isValid (const VertexIndex& idx_vertex) const 00615 { 00616 return (idx_vertex >= VertexIndex (0) && idx_vertex < VertexIndex (int (vertices_.size ()))); 00617 } 00618 00619 /** \brief Check if the given half-edge index is a valid index into the mesh. */ 00620 inline bool 00621 isValid (const HalfEdgeIndex& idx_he) const 00622 { 00623 return (idx_he >= HalfEdgeIndex (0) && idx_he < HalfEdgeIndex (half_edges_.size ())); 00624 } 00625 00626 /** \brief Check if the given edge index is a valid index into the mesh. */ 00627 inline bool 00628 isValid (const EdgeIndex& idx_edge) const 00629 { 00630 return (idx_edge >= EdgeIndex (0) && idx_edge < EdgeIndex (half_edges_.size () / 2)); 00631 } 00632 00633 /** \brief Check if the given face index is a valid index into the mesh. */ 00634 inline bool 00635 isValid (const FaceIndex& idx_face) const 00636 { 00637 return (idx_face >= FaceIndex (0) && idx_face < FaceIndex (faces_.size ())); 00638 } 00639 00640 //////////////////////////////////////////////////////////////////////// 00641 // isDeleted 00642 //////////////////////////////////////////////////////////////////////// 00643 00644 /** \brief Check if the given vertex is marked as deleted. */ 00645 inline bool 00646 isDeleted (const VertexIndex& idx_vertex) const 00647 { 00648 assert (this->isValid (idx_vertex)); 00649 return (!this->getOutgoingHalfEdgeIndex (idx_vertex).isValid ()); 00650 } 00651 00652 /** \brief Check if the given half-edge is marked as deleted. */ 00653 inline bool 00654 isDeleted (const HalfEdgeIndex& idx_he) const 00655 { 00656 assert (this->isValid (idx_he)); 00657 return (!this->getTerminatingVertexIndex (idx_he).isValid ()); 00658 } 00659 00660 /** \brief Check if the given edge (any of the two half-edges) is marked as deleted. */ 00661 inline bool 00662 isDeleted (const EdgeIndex& idx_edge) const 00663 { 00664 assert (this->isValid (idx_edge)); 00665 return (this->isDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, true)) || 00666 this->isDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, false))); 00667 } 00668 00669 /** \brief Check if the given face is marked as deleted. */ 00670 inline bool 00671 isDeleted (const FaceIndex& idx_face) const 00672 { 00673 assert (this->isValid (idx_face)); 00674 return (!this->getInnerHalfEdgeIndex (idx_face).isValid ()); 00675 } 00676 00677 //////////////////////////////////////////////////////////////////////// 00678 // isIsolated 00679 //////////////////////////////////////////////////////////////////////// 00680 00681 /** \brief Check if the given vertex is isolated (not connected to other elements). */ 00682 inline bool 00683 isIsolated (const VertexIndex& idx_vertex) const 00684 { 00685 assert (this->isValid (idx_vertex)); 00686 return (!this->getOutgoingHalfEdgeIndex (idx_vertex).isValid ()); 00687 } 00688 00689 //////////////////////////////////////////////////////////////////////// 00690 // isBoundary 00691 //////////////////////////////////////////////////////////////////////// 00692 00693 /** \brief Check if the given vertex lies on the boundary. Isolated vertices are considered to be on the boundary. */ 00694 inline bool 00695 isBoundary (const VertexIndex& idx_vertex) const 00696 { 00697 assert (this->isValid (idx_vertex)); 00698 if (this->isIsolated (idx_vertex)) return (true); 00699 return (this->isBoundary (this->getOutgoingHalfEdgeIndex (idx_vertex))); 00700 } 00701 00702 /** \brief Check if the given half-edge lies on the bounddary. */ 00703 inline bool 00704 isBoundary (const HalfEdgeIndex& idx_he) const 00705 { 00706 assert (this->isValid (idx_he)); 00707 return (!this->getFaceIndex (idx_he).isValid ()); 00708 } 00709 00710 /** \brief Check if the given edge lies on the boundary (any of the two half-edges lies on the boundary. */ 00711 inline bool 00712 isBoundary (const EdgeIndex& idx_edge) const 00713 { 00714 assert (this->isValid (idx_edge)); 00715 const HalfEdgeIndex& idx = pcl::geometry::toHalfEdgeIndex (idx_edge); 00716 return (this->isBoundary (idx) || this->isBoundary (this->getOppositeHalfEdgeIndex (idx))); 00717 } 00718 00719 /** \brief Check if the given face lies on the boundary. There are two versions of this method, selected by the template parameter. 00720 * \tparam CheckVerticesT Check if any vertex lies on the boundary (true) or check if any edge lies on the boundary (false). 00721 */ 00722 template <bool CheckVerticesT> inline bool 00723 isBoundary (const FaceIndex& idx_face) const 00724 { 00725 assert (this->isValid (idx_face)); 00726 return (this->isBoundary (idx_face, boost::integral_constant <bool, CheckVerticesT> ())); 00727 } 00728 00729 /** \brief Check if the given face lies on the boundary. This method uses isBoundary <true> which checks if any vertex lies on the boundary. */ 00730 inline bool 00731 isBoundary (const FaceIndex& idx_face) const 00732 { 00733 assert (this->isValid (idx_face)); 00734 return (this->isBoundary (idx_face, boost::true_type ())); 00735 } 00736 00737 //////////////////////////////////////////////////////////////////////// 00738 // isManifold 00739 //////////////////////////////////////////////////////////////////////// 00740 00741 /** \brief Check if the given vertex is manifold. Isolated vertices are manifold. */ 00742 inline bool 00743 isManifold (const VertexIndex& idx_vertex) const 00744 { 00745 assert (this->isValid (idx_vertex)); 00746 if (this->isIsolated (idx_vertex)) return (true); 00747 return (this->isManifold (idx_vertex, IsManifold ())); 00748 } 00749 00750 /** \brief Check if the mesh is manifold. */ 00751 inline bool 00752 isManifold () const 00753 { 00754 return (this->isManifold (IsManifold ())); 00755 } 00756 00757 //////////////////////////////////////////////////////////////////////// 00758 // size 00759 //////////////////////////////////////////////////////////////////////// 00760 00761 /** \brief Get the number of the vertices. */ 00762 inline size_t 00763 sizeVertices () const 00764 { 00765 return (vertices_.size ()); 00766 } 00767 00768 /** \brief Get the number of the half-edges. */ 00769 inline size_t 00770 sizeHalfEdges () const 00771 { 00772 assert (half_edges_.size () % 2 == 0); // This would be a bug in the mesh. 00773 return (half_edges_.size ()); 00774 } 00775 00776 /** \brief Get the number of the edges. */ 00777 inline size_t 00778 sizeEdges () const 00779 { 00780 assert (half_edges_.size () % 2 == 0); // This would be a bug in the mesh. 00781 return (half_edges_.size () / 2); 00782 } 00783 00784 /** \brief Get the number of the faces. */ 00785 inline size_t 00786 sizeFaces () const 00787 { 00788 return (faces_.size ()); 00789 } 00790 00791 //////////////////////////////////////////////////////////////////////// 00792 // empty 00793 //////////////////////////////////////////////////////////////////////// 00794 00795 /** \brief Check if the mesh is empty. */ 00796 inline bool 00797 empty () const 00798 { 00799 return (this->emptyVertices () && this->emptyEdges () && this->emptyFaces ()); 00800 } 00801 00802 /** \brief Check if the vertices are empty. */ 00803 inline bool 00804 emptyVertices () const 00805 { 00806 return (vertices_.empty ()); 00807 } 00808 00809 /** \brief Check if the edges are empty. */ 00810 inline bool 00811 emptyEdges () const 00812 { 00813 return (half_edges_.empty ()); 00814 } 00815 00816 /** \brief Check if the faces are empty. */ 00817 inline bool 00818 emptyFaces () const 00819 { 00820 return (faces_.empty ()); 00821 } 00822 00823 //////////////////////////////////////////////////////////////////////// 00824 // reserve 00825 //////////////////////////////////////////////////////////////////////// 00826 00827 /** \brief Reserve storage space n vertices. */ 00828 inline void 00829 reserveVertices (const size_t n) 00830 { 00831 vertices_.reserve (n); 00832 this->reserveData (vertex_data_cloud_, n, HasVertexData ()); 00833 } 00834 00835 /** \brief Reserve storage space for n edges (2*n storage space is reserved for the half-edges). */ 00836 inline void 00837 reserveEdges (const size_t n) 00838 { 00839 half_edges_.reserve (2*n); 00840 this->reserveData (half_edge_data_cloud_, 2*n, HasHalfEdgeData ()); 00841 this->reserveData (edge_data_cloud_ , n, HasEdgeData ()); 00842 } 00843 00844 /** \brief Reserve storage space for n faces. */ 00845 inline void 00846 reserveFaces (const size_t n) 00847 { 00848 faces_.reserve (n); 00849 this->reserveData (face_data_cloud_, n, HasFaceData ()); 00850 } 00851 00852 //////////////////////////////////////////////////////////////////////// 00853 // resize 00854 //////////////////////////////////////////////////////////////////////// 00855 00856 /** \brief Resize the the vertices to n elements. */ 00857 inline void 00858 resizeVertices (const size_t n, const VertexData& data = VertexData ()) 00859 { 00860 vertices_.resize (n); 00861 this->resizeData (vertex_data_cloud_, n, data, HasVertexData ()); 00862 } 00863 00864 /** \brief Resize the edges to n elements (half-edges will hold 2*n elements). */ 00865 inline void 00866 resizeEdges (const size_t n, 00867 const EdgeData& edge_data = EdgeData (), 00868 const HalfEdgeData he_data = HalfEdgeData ()) 00869 { 00870 half_edges_.resize (2*n); 00871 this->resizeData (half_edge_data_cloud_, 2*n, he_data , HasHalfEdgeData ()); 00872 this->resizeData (edge_data_cloud_ , n, edge_data, HasEdgeData ()); 00873 } 00874 00875 /** \brief Resize the faces to n elements. */ 00876 inline void 00877 resizeFaces (const size_t n, const FaceData& data = FaceData ()) 00878 { 00879 faces_.resize (n); 00880 this->resizeData (face_data_cloud_, n, data, HasFaceData ()); 00881 } 00882 00883 //////////////////////////////////////////////////////////////////////// 00884 // clear 00885 //////////////////////////////////////////////////////////////////////// 00886 00887 /** \brief Clear all mesh elements and data. */ 00888 void 00889 clear () 00890 { 00891 vertices_.clear (); 00892 half_edges_.clear (); 00893 faces_.clear (); 00894 00895 this->clearData (vertex_data_cloud_ , HasVertexData ()); 00896 this->clearData (half_edge_data_cloud_, HasHalfEdgeData ()); 00897 this->clearData (edge_data_cloud_ , HasEdgeData ()); 00898 this->clearData (face_data_cloud_ , HasFaceData ()); 00899 } 00900 00901 //////////////////////////////////////////////////////////////////////// 00902 // get / set the vertex data cloud 00903 //////////////////////////////////////////////////////////////////////// 00904 00905 /** \brief Get access to the stored vertex data. 00906 * \warning Please make sure to NOT add or remove elements from the cloud. 00907 */ 00908 inline VertexDataCloud& 00909 getVertexDataCloud () 00910 { 00911 return (vertex_data_cloud_); 00912 } 00913 00914 /** \brief Get the stored vertex data. */ 00915 inline VertexDataCloud 00916 getVertexDataCloud () const 00917 { 00918 return (vertex_data_cloud_); 00919 } 00920 00921 /** \brief Change the stored vertex data. 00922 * \param[in] vertex_data_cloud The new vertex data. Must be the same as the current data. 00923 * \return true if the cloud could be set. 00924 */ 00925 inline bool 00926 setVertexDataCloud (const VertexDataCloud& vertex_data_cloud) 00927 { 00928 if (vertex_data_cloud.size () == vertex_data_cloud_.size ()) 00929 { 00930 vertex_data_cloud_ = vertex_data_cloud; 00931 return (true); 00932 } 00933 else 00934 { 00935 return (false); 00936 } 00937 } 00938 00939 //////////////////////////////////////////////////////////////////////// 00940 // get / set the half-edge data cloud 00941 //////////////////////////////////////////////////////////////////////// 00942 00943 /** \brief Get access to the stored half-edge data. 00944 * \warning Please make sure to NOT add or remove elements from the cloud. 00945 */ 00946 inline HalfEdgeDataCloud& 00947 getHalfEdgeDataCloud () 00948 { 00949 return (half_edge_data_cloud_); 00950 } 00951 00952 /** \brief Get the stored half-edge data. */ 00953 inline HalfEdgeDataCloud 00954 getHalfEdgeDataCloud () const 00955 { 00956 return (half_edge_data_cloud_); 00957 } 00958 00959 /** \brief Change the stored half-edge data. 00960 * \param[in] half_edge_data_cloud The new half-edge data. Must be the same as the current data. 00961 * \return true if the cloud could be set. 00962 */ 00963 inline bool 00964 setHalfEdgeDataCloud (const HalfEdgeDataCloud& half_edge_data_cloud) 00965 { 00966 if (half_edge_data_cloud.size () == half_edge_data_cloud_.size ()) 00967 { 00968 half_edge_data_cloud_ = half_edge_data_cloud; 00969 return (true); 00970 } 00971 else 00972 { 00973 return (false); 00974 } 00975 } 00976 00977 //////////////////////////////////////////////////////////////////////// 00978 // get / set the edge data cloud 00979 //////////////////////////////////////////////////////////////////////// 00980 00981 /** \brief Get access to the stored edge data. 00982 * \warning Please make sure to NOT add or remove elements from the cloud. 00983 */ 00984 inline EdgeDataCloud& 00985 getEdgeDataCloud () 00986 { 00987 return (edge_data_cloud_); 00988 } 00989 00990 /** \brief Get the stored edge data. */ 00991 inline EdgeDataCloud 00992 getEdgeDataCloud () const 00993 { 00994 return (edge_data_cloud_); 00995 } 00996 00997 /** \brief Change the stored edge data. 00998 * \param[in] edge_data_cloud The new edge data. Must be the same as the current data. 00999 * \return true if the cloud could be set. 01000 */ 01001 inline bool 01002 setEdgeDataCloud (const EdgeDataCloud& edge_data_cloud) 01003 { 01004 if (edge_data_cloud.size () == edge_data_cloud_.size ()) 01005 { 01006 edge_data_cloud_ = edge_data_cloud; 01007 return (true); 01008 } 01009 else 01010 { 01011 return (false); 01012 } 01013 } 01014 01015 //////////////////////////////////////////////////////////////////////// 01016 // get / set the face data cloud 01017 //////////////////////////////////////////////////////////////////////// 01018 01019 /** \brief Get access to the stored face data. 01020 * \warning Please make sure to NOT add or remove elements from the cloud. 01021 */ 01022 inline FaceDataCloud& 01023 getFaceDataCloud () 01024 { 01025 return (face_data_cloud_); 01026 } 01027 01028 /** \brief Get the stored face data. */ 01029 inline FaceDataCloud 01030 getFaceDataCloud () const 01031 { 01032 return (face_data_cloud_); 01033 } 01034 01035 /** \brief Change the stored face data. 01036 * \param[in] face_data_cloud The new face data. Must be the same as the current data. 01037 * \return true if the cloud could be set. 01038 */ 01039 inline bool 01040 setFaceDataCloud (const FaceDataCloud& face_data_cloud) 01041 { 01042 if (face_data_cloud.size () == face_data_cloud_.size ()) 01043 { 01044 face_data_cloud_ = face_data_cloud; 01045 return (true); 01046 } 01047 else 01048 { 01049 return (false); 01050 } 01051 } 01052 01053 //////////////////////////////////////////////////////////////////////// 01054 // getVertexIndex / getHalfEdgeIndex / getEdgeIndex / getFaceIndex 01055 //////////////////////////////////////////////////////////////////////// 01056 01057 /** \brief Get the index associated to the given vertex data. 01058 * \return Invalid index if the mesh does not have associated vertex data. 01059 */ 01060 inline VertexIndex 01061 getVertexIndex (const VertexData& vertex_data) const 01062 { 01063 if (HasVertexData::value) 01064 { 01065 assert (&vertex_data >= &vertex_data_cloud_.front () && &vertex_data <= &vertex_data_cloud_.back ()); 01066 return (VertexIndex (std::distance (&vertex_data_cloud_.front (), &vertex_data))); 01067 } 01068 else 01069 { 01070 return (VertexIndex ()); 01071 } 01072 } 01073 01074 /** \brief Get the index associated to the given half-edge data. */ 01075 inline HalfEdgeIndex 01076 getHalfEdgeIndex (const HalfEdgeData& half_edge_data) const 01077 { 01078 if (HasHalfEdgeData::value) 01079 { 01080 assert (&half_edge_data >= &half_edge_data_cloud_.front () && &half_edge_data <= &half_edge_data_cloud_.back ()); 01081 return (HalfEdgeIndex (std::distance (&half_edge_data_cloud_.front (), &half_edge_data))); 01082 } 01083 else 01084 { 01085 return (HalfEdgeIndex ()); 01086 } 01087 } 01088 01089 /** \brief Get the index associated to the given edge data. */ 01090 inline EdgeIndex 01091 getEdgeIndex (const EdgeData& edge_data) const 01092 { 01093 if (HasEdgeData::value) 01094 { 01095 assert (&edge_data >= &edge_data_cloud_.front () && &edge_data <= &edge_data_cloud_.back ()); 01096 return (EdgeIndex (std::distance (&edge_data_cloud_.front (), &edge_data))); 01097 } 01098 else 01099 { 01100 return (EdgeIndex ()); 01101 } 01102 } 01103 01104 /** \brief Get the index associated to the given face data. */ 01105 inline FaceIndex 01106 getFaceIndex (const FaceData& face_data) const 01107 { 01108 if (HasFaceData::value) 01109 { 01110 assert (&face_data >= &face_data_cloud_.front () && &face_data <= &face_data_cloud_.back ()); 01111 return (FaceIndex (std::distance (&face_data_cloud_.front (), &face_data))); 01112 } 01113 else 01114 { 01115 return (FaceIndex ()); 01116 } 01117 } 01118 01119 protected: 01120 01121 //////////////////////////////////////////////////////////////////////// 01122 // Types 01123 //////////////////////////////////////////////////////////////////////// 01124 01125 // Elements 01126 typedef pcl::geometry::Vertex Vertex; 01127 typedef pcl::geometry::HalfEdge HalfEdge; 01128 typedef pcl::geometry::Face Face; 01129 01130 typedef std::vector <Vertex> Vertices; 01131 typedef std::vector <HalfEdge> HalfEdges; 01132 typedef std::vector <Face> Faces; 01133 01134 typedef typename Vertices::iterator VertexIterator; 01135 typedef typename HalfEdges::iterator HalfEdgeIterator; 01136 typedef typename Faces::iterator FaceIterator; 01137 01138 typedef typename Vertices::const_iterator VertexConstIterator; 01139 typedef typename HalfEdges::const_iterator HalfEdgeConstIterator; 01140 typedef typename Faces::const_iterator FaceConstIterator; 01141 01142 /** \brief General implementation of addFace. */ 01143 FaceIndex 01144 addFaceImplBase (const VertexIndices& vertices, 01145 const FaceData& face_data, 01146 const EdgeData& edge_data, 01147 const HalfEdgeData& half_edge_data) 01148 { 01149 const int n = static_cast<int> (vertices.size ()); 01150 if (n < 3) return (FaceIndex ()); 01151 01152 // Check for topological errors 01153 inner_he_.resize (n); 01154 free_he_.resize (n); 01155 is_new_.resize (n); 01156 make_adjacent_.resize (n); 01157 int i, j; 01158 for (i=0; i<n; ++i) 01159 { 01160 if (!this->checkTopology1 (vertices [i], vertices [(i+1)%n], inner_he_ [i], is_new_ [i], IsManifold ())) 01161 { 01162 return (FaceIndex ()); 01163 } 01164 } 01165 for (i=0; i<n; ++i) 01166 { 01167 j = (i+1)%n; 01168 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 ())) 01169 { 01170 return (FaceIndex ()); 01171 } 01172 } 01173 01174 // Reconnect the existing half-edges if needed 01175 if (!IsManifold::value) 01176 { 01177 for (i=0; i<n; ++i) 01178 { 01179 if (make_adjacent_ [i]) 01180 { 01181 this->makeAdjacent (inner_he_ [i], inner_he_ [(i+1)%n], free_he_ [i]); 01182 } 01183 } 01184 } 01185 01186 // Add new half-edges if needed 01187 for (i=0; i<n; ++i) 01188 { 01189 if (is_new_ [i]) 01190 { 01191 inner_he_ [i] = this->addEdge (vertices [i], vertices [(i+1)%n], half_edge_data, edge_data); 01192 } 01193 } 01194 01195 // Connect 01196 for (i=0; i<n; ++i) 01197 { 01198 j = (i+1)%n; 01199 if ( is_new_ [i] && is_new_ [j]) this->connectNewNew (inner_he_ [i], inner_he_ [j], vertices [j], IsManifold ()); 01200 else if ( is_new_ [i] && !is_new_ [j]) this->connectNewOld (inner_he_ [i], inner_he_ [j], vertices [j]); 01201 else if (!is_new_ [i] && is_new_ [j]) this->connectOldNew (inner_he_ [i], inner_he_ [j], vertices [j]); 01202 else this->connectOldOld (inner_he_ [i], inner_he_ [j], vertices [j], IsManifold ()); 01203 } 01204 return (this->connectFace (inner_he_, face_data)); 01205 } 01206 01207 //////////////////////////////////////////////////////////////////////// 01208 // addEdge 01209 //////////////////////////////////////////////////////////////////////// 01210 01211 /** \brief Add an edge between the two given vertices and connect them with the vertices. 01212 * \param[in] idx_v_a The first vertex index 01213 * \param[in] idx_v_b The second vertex index 01214 * \param[in] he_data Data associated with the half-edges. This is only added if the mesh has data associated with the half-edges. 01215 * \param[in] edge_data Data associated with the edge. This is only added if the mesh has data associated with the edges. 01216 * \return Index to the half-edge from vertex a to vertex b. 01217 */ 01218 HalfEdgeIndex 01219 addEdge (const VertexIndex& idx_v_a, 01220 const VertexIndex& idx_v_b, 01221 const HalfEdgeData& he_data, 01222 const EdgeData& edge_data) 01223 { 01224 half_edges_.push_back (HalfEdge (idx_v_b)); 01225 half_edges_.push_back (HalfEdge (idx_v_a)); 01226 01227 this->addData (half_edge_data_cloud_, he_data , HasHalfEdgeData ()); 01228 this->addData (half_edge_data_cloud_, he_data , HasHalfEdgeData ()); 01229 this->addData (edge_data_cloud_ , edge_data, HasEdgeData ()); 01230 01231 return (HalfEdgeIndex (static_cast <int> (half_edges_.size () - 2))); 01232 } 01233 01234 //////////////////////////////////////////////////////////////////////// 01235 // topology checks 01236 //////////////////////////////////////////////////////////////////////// 01237 01238 /** \brief Check if the edge between the two vertices can be added. 01239 * \param[in] idx_v_a Index to the first vertex. 01240 * \param[in] idx_v_b Index to the second vertex. 01241 * \param[out] idx_he_ab Index to the half-edge ab if is_new_ab=false. 01242 * \param[out] is_new_ab true if the edge between the vertices exists already. Must be initialized with true! 01243 * \return true if the half-edge may be added. 01244 */ 01245 bool 01246 checkTopology1 (const VertexIndex& idx_v_a, 01247 const VertexIndex& idx_v_b, 01248 HalfEdgeIndex& idx_he_ab, 01249 std::vector <bool>::reference is_new_ab, 01250 boost::true_type /*is_manifold*/) const 01251 { 01252 is_new_ab = true; 01253 if (this->isIsolated (idx_v_a)) return (true); 01254 01255 idx_he_ab = this->getOutgoingHalfEdgeIndex (idx_v_a); 01256 01257 if (!this->isBoundary (idx_he_ab)) return (false); 01258 if (this->getTerminatingVertexIndex (idx_he_ab) == idx_v_b) is_new_ab = false; 01259 return (true); 01260 } 01261 01262 /** \brief Non manifold version of checkTopology1 */ 01263 bool 01264 checkTopology1 (const VertexIndex& idx_v_a, 01265 const VertexIndex& idx_v_b, 01266 HalfEdgeIndex& idx_he_ab, 01267 std::vector <bool>::reference is_new_ab, 01268 boost::false_type /*is_manifold*/) const 01269 { 01270 is_new_ab = true; 01271 if (this->isIsolated (idx_v_a)) return (true); 01272 if (!this->isBoundary (this->getOutgoingHalfEdgeIndex (idx_v_a))) return (false); 01273 01274 VertexAroundVertexCirculator circ = this->getVertexAroundVertexCirculator (this->getOutgoingHalfEdgeIndex (idx_v_a)); 01275 const VertexAroundVertexCirculator circ_end = circ; 01276 01277 do 01278 { 01279 if (circ.getTargetIndex () == idx_v_b) 01280 { 01281 idx_he_ab = circ.getCurrentHalfEdgeIndex (); 01282 if (!this->isBoundary (idx_he_ab)) return (false); 01283 01284 is_new_ab = false; 01285 return (true); 01286 } 01287 } while (++circ!=circ_end); 01288 01289 return (true); 01290 } 01291 01292 /** \brief Check if the face may be added (mesh does not become non-manifold). */ 01293 inline bool 01294 checkTopology2 (const HalfEdgeIndex& /*idx_he_ab*/, 01295 const HalfEdgeIndex& /*idx_he_bc*/, 01296 const bool is_new_ab, 01297 const bool is_new_bc, 01298 const bool is_isolated_b, 01299 std::vector <bool>::reference /*make_adjacent_ab_bc*/, 01300 HalfEdgeIndex& /*idx_free_half_edge*/, 01301 boost::true_type /*is_manifold*/) const 01302 { 01303 if (is_new_ab && is_new_bc && !is_isolated_b) return (false); 01304 else return (true); 01305 } 01306 01307 /** \brief Check if the half-edge bc is the next half-edge of ab. 01308 * \param[in] idx_he_ab Index to the half-edge between the vertices a and b. 01309 * \param[in] idx_ha_bc Index to the half-edge between the vertices b and c. 01310 * \param[in] is_new_ab Half-edge ab is new. 01311 * \param[in] is_new_bc Half-edge bc is new. 01312 * \param[out] make_adjacent_ab_bc Half-edges ab and bc need to be made adjacent. 01313 * \param[out] idx_free_half_edge Free half-edge (needed for makeAdjacent) 01314 * \return true if addFace may be continued. 01315 */ 01316 inline bool 01317 checkTopology2 (const HalfEdgeIndex& idx_he_ab, 01318 const HalfEdgeIndex& idx_he_bc, 01319 const bool is_new_ab, 01320 const bool is_new_bc, 01321 const bool /*is_isolated_b*/, 01322 std::vector <bool>::reference make_adjacent_ab_bc, 01323 HalfEdgeIndex& idx_free_half_edge, 01324 boost::false_type /*is_manifold*/) const 01325 { 01326 if (is_new_ab || is_new_bc) 01327 { 01328 make_adjacent_ab_bc = false; 01329 return (true); // Make adjacent is only needed for two old half-edges 01330 } 01331 01332 if (this->getNextHalfEdgeIndex (idx_he_ab) == idx_he_bc) 01333 { 01334 make_adjacent_ab_bc = false; 01335 return (true); // already adjacent 01336 } 01337 01338 make_adjacent_ab_bc = true; 01339 01340 // Find the next boundary half edge 01341 IncomingHalfEdgeAroundVertexCirculator circ = this->getIncomingHalfEdgeAroundVertexCirculator (this->getOppositeHalfEdgeIndex (idx_he_bc)); 01342 01343 do ++circ; while (!this->isBoundary (circ.getTargetIndex ())); 01344 idx_free_half_edge = circ.getTargetIndex (); 01345 01346 // This would detach the faces around the vertex from each other. 01347 if (circ.getTargetIndex () == idx_he_ab) return (false); 01348 else return (true); 01349 } 01350 01351 /** \brief Make the half-edges bc the next half-edge of ab. 01352 * \param[in] idx_he_ab Index to the half-edge between the vertices a and b. 01353 * \param[in] idx_ha_bc Index to the half-edge between the vertices b and c. 01354 * \param[in, out] idx_free_half_edge Free half-edge needed to re-connect the half-edges around vertex b. 01355 */ 01356 void 01357 makeAdjacent (const HalfEdgeIndex& idx_he_ab, 01358 const HalfEdgeIndex& idx_he_bc, 01359 HalfEdgeIndex& idx_free_half_edge) 01360 { 01361 // Re-link. No references! 01362 const HalfEdgeIndex idx_he_ab_next = this->getNextHalfEdgeIndex (idx_he_ab); 01363 const HalfEdgeIndex idx_he_bc_prev = this->getPrevHalfEdgeIndex (idx_he_bc); 01364 const HalfEdgeIndex idx_he_free_next = this->getNextHalfEdgeIndex (idx_free_half_edge); 01365 01366 this->connectPrevNext (idx_he_ab, idx_he_bc); 01367 this->connectPrevNext (idx_free_half_edge, idx_he_ab_next); 01368 this->connectPrevNext (idx_he_bc_prev, idx_he_free_next); 01369 } 01370 01371 //////////////////////////////////////////////////////////////////////// 01372 // connect 01373 //////////////////////////////////////////////////////////////////////// 01374 01375 /** \brief Add a face to the mesh and connect it to the half-edges. 01376 * \param[in] inner_he Inner half-edges of the face. 01377 * \param[in] face_data Data that is stored in the face. This is only added if the mesh has data associated with the faces. 01378 * \return Index to the new face. 01379 */ 01380 FaceIndex 01381 connectFace (const HalfEdgeIndices& inner_he, 01382 const FaceData& face_data) 01383 { 01384 faces_.push_back (Face (inner_he.back ())); 01385 this->addData (face_data_cloud_, face_data, HasFaceData ()); 01386 01387 const FaceIndex idx_face (static_cast <int> (this->sizeFaces () - 1)); 01388 01389 for (HalfEdgeIndices::const_iterator it=inner_he.begin (); it!=inner_he.end (); ++it) 01390 { 01391 this->setFaceIndex (*it, idx_face); 01392 } 01393 01394 return (idx_face); 01395 } 01396 01397 /** \brief Connect the next and prev indices of the two half-edges with each other. */ 01398 inline void 01399 connectPrevNext (const HalfEdgeIndex& idx_he_ab, 01400 const HalfEdgeIndex& idx_he_bc) 01401 { 01402 this->setNextHalfEdgeIndex (idx_he_ab, idx_he_bc); 01403 this->setPrevHalfEdgeIndex (idx_he_bc, idx_he_ab); 01404 } 01405 01406 /** \brief Both half-edges are new (manifold version). */ 01407 void 01408 connectNewNew (const HalfEdgeIndex& idx_he_ab, 01409 const HalfEdgeIndex& idx_he_bc, 01410 const VertexIndex& idx_v_b, 01411 boost::true_type /*is_manifold*/) 01412 { 01413 const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab); 01414 const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc); 01415 01416 this->connectPrevNext (idx_he_ab, idx_he_bc); 01417 this->connectPrevNext (idx_he_cb, idx_he_ba); 01418 01419 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ba); 01420 } 01421 01422 /** \brief Both half-edges are new (non-manifold version). */ 01423 void 01424 connectNewNew (const HalfEdgeIndex& idx_he_ab, 01425 const HalfEdgeIndex& idx_he_bc, 01426 const VertexIndex& idx_v_b, 01427 boost::false_type /*is_manifold*/) 01428 { 01429 if (this->isIsolated (idx_v_b)) 01430 { 01431 this->connectNewNew (idx_he_ab, idx_he_bc, idx_v_b, boost::true_type ()); 01432 } 01433 else 01434 { 01435 const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab); 01436 const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc); 01437 01438 // No references! 01439 const HalfEdgeIndex idx_he_b_out = this->getOutgoingHalfEdgeIndex (idx_v_b); 01440 const HalfEdgeIndex idx_he_b_out_prev = this->getPrevHalfEdgeIndex (idx_he_b_out); 01441 01442 this->connectPrevNext (idx_he_ab, idx_he_bc); 01443 this->connectPrevNext (idx_he_cb, idx_he_b_out); 01444 this->connectPrevNext (idx_he_b_out_prev, idx_he_ba); 01445 } 01446 } 01447 01448 /** \brief The first half-edge is new. */ 01449 void 01450 connectNewOld (const HalfEdgeIndex& idx_he_ab, 01451 const HalfEdgeIndex& idx_he_bc, 01452 const VertexIndex& idx_v_b) 01453 { 01454 const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab); 01455 const HalfEdgeIndex idx_he_bc_prev = this->getPrevHalfEdgeIndex (idx_he_bc); // No reference! 01456 01457 this->connectPrevNext (idx_he_ab, idx_he_bc); 01458 this->connectPrevNext (idx_he_bc_prev, idx_he_ba); 01459 01460 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ba); 01461 } 01462 01463 /** \brief The second half-edge is new. */ 01464 void 01465 connectOldNew (const HalfEdgeIndex& idx_he_ab, 01466 const HalfEdgeIndex& idx_he_bc, 01467 const VertexIndex& idx_v_b) 01468 { 01469 const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc); 01470 const HalfEdgeIndex idx_he_ab_next = this->getNextHalfEdgeIndex (idx_he_ab); // No reference! 01471 01472 this->connectPrevNext (idx_he_ab, idx_he_bc); 01473 this->connectPrevNext (idx_he_cb, idx_he_ab_next); 01474 01475 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_ab_next); 01476 } 01477 01478 /** \brief Both half-edges are old (manifold version). */ 01479 void 01480 connectOldOld (const HalfEdgeIndex& /*idx_he_ab*/, 01481 const HalfEdgeIndex& /*idx_he_bc*/, 01482 const VertexIndex& /*idx_v_b*/, 01483 boost::true_type /*is_manifold*/) 01484 { 01485 } 01486 01487 /** \brief Both half-edges are old (non-manifold version). */ 01488 void 01489 connectOldOld (const HalfEdgeIndex& /*idx_he_ab*/, 01490 const HalfEdgeIndex& idx_he_bc, 01491 const VertexIndex& idx_v_b, 01492 boost::false_type /*is_manifold*/) 01493 { 01494 const HalfEdgeIndex& idx_he_b_out = this->getOutgoingHalfEdgeIndex (idx_v_b); 01495 01496 // The outgoing half edge MUST be a boundary half-edge (if there is one) 01497 if (idx_he_b_out == idx_he_bc) // he_bc is no longer on the boundary 01498 { 01499 OutgoingHalfEdgeAroundVertexCirculator circ = this->getOutgoingHalfEdgeAroundVertexCirculator (idx_he_b_out); 01500 const OutgoingHalfEdgeAroundVertexCirculator circ_end = circ; 01501 01502 while (++circ!=circ_end) 01503 { 01504 if (this->isBoundary (circ.getTargetIndex ())) 01505 { 01506 this->setOutgoingHalfEdgeIndex (idx_v_b, circ.getTargetIndex ()); 01507 return; 01508 } 01509 } 01510 } 01511 } 01512 01513 //////////////////////////////////////////////////////////////////////// 01514 // addData 01515 //////////////////////////////////////////////////////////////////////// 01516 01517 /** \brief Add mesh data. */ 01518 template <class DataT> 01519 inline void 01520 addData (pcl::PointCloud <DataT>& cloud, const DataT& data, boost::true_type /*has_data*/) 01521 { 01522 cloud.push_back (data); 01523 } 01524 01525 /** \brief Does nothing. */ 01526 template <class DataT> 01527 inline void 01528 addData (pcl::PointCloud <DataT>& /*cloud*/, const DataT& /*data*/, boost::false_type /*has_data*/) 01529 { 01530 } 01531 01532 //////////////////////////////////////////////////////////////////////// 01533 // deleteFace 01534 //////////////////////////////////////////////////////////////////////// 01535 01536 /** \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. */ 01537 void 01538 deleteFace (const FaceIndex& idx_face, 01539 boost::true_type /*is_manifold*/) 01540 { 01541 assert (this->isValid (idx_face)); 01542 delete_faces_face_.clear (); 01543 delete_faces_face_.push_back (idx_face); 01544 01545 while (!delete_faces_face_.empty ()) 01546 { 01547 const FaceIndex idx_face_cur = delete_faces_face_.back (); 01548 delete_faces_face_.pop_back (); 01549 01550 // This calls the non-manifold version of deleteFace, which will call the manifold version of reconnect. 01551 this->deleteFace (idx_face_cur, boost::false_type ()); 01552 } 01553 } 01554 01555 /** \brief Non-manifold version of deleteFace. */ 01556 void 01557 deleteFace (const FaceIndex& idx_face, 01558 boost::false_type /*is_manifold*/) 01559 { 01560 assert (this->isValid (idx_face)); 01561 if (this->isDeleted (idx_face)) return; 01562 01563 // Store all half-edges in the face 01564 inner_he_.clear (); 01565 is_boundary_.clear (); 01566 InnerHalfEdgeAroundFaceCirculator circ = this->getInnerHalfEdgeAroundFaceCirculator (idx_face); 01567 const InnerHalfEdgeAroundFaceCirculator circ_end = circ; 01568 do 01569 { 01570 inner_he_.push_back (circ.getTargetIndex ()); 01571 is_boundary_.push_back (this->isBoundary (this->getOppositeHalfEdgeIndex (circ.getTargetIndex ()))); 01572 } while (++circ != circ_end); 01573 assert (inner_he_.size () >= 3); // Minimum should be a triangle. 01574 01575 const int n = static_cast <int> (inner_he_.size ()); 01576 int j; 01577 01578 if (IsManifold::value) 01579 { 01580 for (int i=0; i<n; ++i) 01581 { 01582 j = (i+1)%n; 01583 this->reconnect (inner_he_ [i], inner_he_ [j], is_boundary_ [i], is_boundary_ [j]); 01584 } 01585 for (int i=0; i<n; ++i) 01586 { 01587 this->getHalfEdge (inner_he_ [i]).idx_face_.invalidate (); 01588 } 01589 } 01590 else 01591 { 01592 for (int i=0; i<n; ++i) 01593 { 01594 j = (i+1)%n; 01595 this->reconnect (inner_he_ [i], inner_he_ [j], is_boundary_ [i], is_boundary_ [j]); 01596 this->getHalfEdge (inner_he_ [i]).idx_face_.invalidate (); 01597 } 01598 } 01599 01600 this->markDeleted (idx_face); 01601 } 01602 01603 //////////////////////////////////////////////////////////////////////// 01604 // reconnect 01605 //////////////////////////////////////////////////////////////////////// 01606 01607 /** \brief Deconnect the input half-edges from the mesh and adjust the indices of the connected half-edges. */ 01608 void 01609 reconnect (const HalfEdgeIndex& idx_he_ab, 01610 const HalfEdgeIndex& idx_he_bc, 01611 const bool is_boundary_ba, 01612 const bool is_boundary_cb) 01613 { 01614 const HalfEdgeIndex idx_he_ba = this->getOppositeHalfEdgeIndex (idx_he_ab); 01615 const HalfEdgeIndex idx_he_cb = this->getOppositeHalfEdgeIndex (idx_he_bc); 01616 const VertexIndex idx_v_b = this->getTerminatingVertexIndex (idx_he_ab); 01617 01618 if (is_boundary_ba && is_boundary_cb) // boundary - boundary 01619 { 01620 const HalfEdgeIndex& idx_he_cb_next = this->getNextHalfEdgeIndex (idx_he_cb); 01621 01622 if (idx_he_cb_next == idx_he_ba) // Vertex b is isolated 01623 { 01624 this->markDeleted (idx_v_b); 01625 } 01626 else 01627 { 01628 this->connectPrevNext (this->getPrevHalfEdgeIndex (idx_he_ba), idx_he_cb_next); 01629 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_cb_next); 01630 } 01631 01632 this->markDeleted (idx_he_ab); 01633 this->markDeleted (idx_he_ba); 01634 } 01635 else if (is_boundary_ba && !is_boundary_cb) // boundary - no boundary 01636 { 01637 this->connectPrevNext (this->getPrevHalfEdgeIndex (idx_he_ba), idx_he_bc); 01638 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_bc); 01639 01640 this->markDeleted (idx_he_ab); 01641 this->markDeleted (idx_he_ba); 01642 } 01643 else if (!is_boundary_ba && is_boundary_cb) // no boundary - boundary 01644 { 01645 const HalfEdgeIndex& idx_he_cb_next = this->getNextHalfEdgeIndex (idx_he_cb); 01646 this->connectPrevNext (idx_he_ab, idx_he_cb_next); 01647 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_cb_next); 01648 } 01649 else // no boundary - no boundary 01650 { 01651 this->reconnectNBNB (idx_he_bc, idx_he_cb, idx_v_b, IsManifold ()); 01652 } 01653 } 01654 01655 /** \brief Both edges are not on the boundary. Manifold version. */ 01656 void 01657 reconnectNBNB (const HalfEdgeIndex& idx_he_bc, 01658 const HalfEdgeIndex& idx_he_cb, 01659 const VertexIndex& idx_v_b, 01660 boost::true_type /*is_manifold*/) 01661 { 01662 if (this->isBoundary (idx_v_b)) 01663 { 01664 // Deletion of this face makes the mesh non-manifold 01665 // -> delete the neighboring faces until it is manifold again 01666 IncomingHalfEdgeAroundVertexCirculator circ = this->getIncomingHalfEdgeAroundVertexCirculator (idx_he_cb); 01667 01668 while (!this->isBoundary (circ.getTargetIndex ())) 01669 { 01670 delete_faces_face_.push_back (this->getFaceIndex ((circ++).getTargetIndex ())); 01671 01672 #ifdef PCL_GEOMETRY_MESH_BASE_TEST_DELETE_FACE_MANIFOLD_2 01673 if (circ == this->getIncomingHalfEdgeAroundVertexCirculator (idx_he_cb)) // Abort infinity loop 01674 { 01675 // In a manifold mesh we can't invalidate the face while reconnecting! 01676 // See the implementation of 01677 // deleteFace (const FaceIndex& idx_face, 01678 // boost::false_type /*is_manifold*/) 01679 pcl::geometry::g_pcl_geometry_mesh_base_test_delete_face_manifold_2_success = false; 01680 return; 01681 } 01682 #endif 01683 } 01684 } 01685 else 01686 { 01687 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_bc); 01688 } 01689 } 01690 01691 /** \brief Both edges are not on the boundary. Non-manifold version. */ 01692 void 01693 reconnectNBNB (const HalfEdgeIndex& idx_he_bc, 01694 const HalfEdgeIndex& /*idx_he_cb*/, 01695 const VertexIndex& idx_v_b, 01696 boost::false_type /*is_manifold*/) 01697 { 01698 if (!this->isBoundary (idx_v_b)) 01699 { 01700 this->setOutgoingHalfEdgeIndex (idx_v_b, idx_he_bc); 01701 } 01702 } 01703 01704 //////////////////////////////////////////////////////////////////////// 01705 // markDeleted 01706 //////////////////////////////////////////////////////////////////////// 01707 01708 /** \brief Mark the given vertex as deleted. */ 01709 inline void 01710 markDeleted (const VertexIndex& idx_vertex) 01711 { 01712 assert (this->isValid (idx_vertex)); 01713 this->getVertex (idx_vertex).idx_outgoing_half_edge_.invalidate (); 01714 } 01715 01716 /** \brief Mark the given half-edge as deleted. */ 01717 inline void 01718 markDeleted (const HalfEdgeIndex& idx_he) 01719 { 01720 assert (this->isValid (idx_he)); 01721 this->getHalfEdge (idx_he).idx_terminating_vertex_.invalidate (); 01722 } 01723 01724 /** \brief Mark the given edge (both half-edges) as deleted. */ 01725 inline void 01726 markDeleted (const EdgeIndex& idx_edge) 01727 { 01728 assert (this->isValid (idx_edge)); 01729 this->markDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, true)); 01730 this->markDeleted (pcl::geometry::toHalfEdgeIndex (idx_edge, false)); 01731 } 01732 01733 /** \brief Mark the given face as deleted. */ 01734 inline void 01735 markDeleted (const FaceIndex& idx_face) 01736 { 01737 assert (this->isValid (idx_face)); 01738 this->getFace (idx_face).idx_inner_half_edge_.invalidate (); 01739 } 01740 01741 //////////////////////////////////////////////////////////////////////// 01742 // For cleanUp 01743 //////////////////////////////////////////////////////////////////////// 01744 01745 /** \brief Removes mesh elements and data that are marked as deleted from the container. 01746 * \IndexContainerT e.g. std::vector <VertexIndex> 01747 * \ElementContainerT e.g. std::vector <Vertex> 01748 * \DataContainerT e.g. std::vector <VertexData> 01749 * \HasDataT Integral constant specifying if the mesh has data associated with the elements. 01750 * \param[in, out] elements Container for the mesh elements. Resized to the new size. 01751 * \param[in, out] data_cloud Container for the mesh data. Resized to the new size. 01752 * \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. 01753 */ 01754 template <class ElementContainerT, class DataContainerT, class IndexContainerT, class HasDataT> IndexContainerT 01755 remove (ElementContainerT& elements, DataContainerT& data_cloud) 01756 { 01757 typedef typename IndexContainerT::value_type Index; 01758 typedef typename ElementContainerT::value_type Element; 01759 01760 if (HasDataT::value) assert (elements.size () == data_cloud.size ()); 01761 else assert (data_cloud.empty ()); // Bug in this class! 01762 01763 IndexContainerT new_indices (elements.size (), typename IndexContainerT::value_type ()); 01764 Index ind_old (0), ind_new (0); 01765 01766 typename ElementContainerT::const_iterator it_e_old = elements.begin (); 01767 typename ElementContainerT::iterator it_e_new = elements.begin (); 01768 01769 typename DataContainerT::const_iterator it_d_old = data_cloud.begin (); 01770 typename DataContainerT::iterator it_d_new = data_cloud.begin (); 01771 01772 typename IndexContainerT::iterator it_ind_new = new_indices.begin (); 01773 typename IndexContainerT::const_iterator it_ind_new_end = new_indices.end (); 01774 01775 while (it_ind_new!=it_ind_new_end) 01776 { 01777 if (!this->isDeleted (ind_old)) 01778 { 01779 *it_ind_new = ind_new++; 01780 01781 // TODO: Test for self assignment? 01782 *it_e_new++ = *it_e_old; 01783 this->assignIf (it_d_old, it_d_new, HasDataT ()); 01784 this->incrementIf ( it_d_new, HasDataT ()); 01785 } 01786 ++ind_old; 01787 ++it_e_old; 01788 this->incrementIf (it_d_old, HasDataT ()); 01789 ++it_ind_new; 01790 } 01791 01792 elements.resize (ind_new.get (), Element ()); 01793 if (HasDataT::value) 01794 { 01795 data_cloud.resize (ind_new.get ()); 01796 } 01797 else if (it_d_old != data_cloud.begin () || it_d_new != data_cloud.begin ()) 01798 { 01799 std::cerr << "TODO: Bug in MeshBase::remove!\n"; 01800 assert (false); 01801 exit (EXIT_FAILURE); 01802 } 01803 01804 return (new_indices); 01805 } 01806 01807 /** \brief Increment the iterator. */ 01808 template <class IteratorT> inline void 01809 incrementIf (IteratorT& it, boost::true_type /*has_data*/) const 01810 { 01811 ++it; 01812 } 01813 01814 /** \brief Does nothing. */ 01815 template <class IteratorT> inline void 01816 incrementIf (IteratorT& /*it*/, boost::false_type /*has_data*/) const 01817 { 01818 } 01819 01820 /** \brief Assign the source iterator to the target iterator. */ 01821 template <class ConstIteratorT, class IteratorT> inline void 01822 assignIf (const ConstIteratorT source, IteratorT target, boost::true_type /*has_data*/) const 01823 { 01824 *target = *source; 01825 } 01826 01827 /** \brief Does nothing. */ 01828 template <class ConstIteratorT, class IteratorT> inline void 01829 assignIf (const ConstIteratorT /*source*/, IteratorT /*target*/, boost::false_type /*has_data*/) const 01830 { 01831 } 01832 01833 //////////////////////////////////////////////////////////////////////// 01834 // Vertex / Half-edge / Face connectivity 01835 //////////////////////////////////////////////////////////////////////// 01836 01837 /** \brief Set the outgoing half-edge index to a given vertex. */ 01838 inline void 01839 setOutgoingHalfEdgeIndex (const VertexIndex& idx_vertex, const HalfEdgeIndex& idx_outgoing_half_edge) 01840 { 01841 assert (this->isValid (idx_vertex)); 01842 this->getVertex (idx_vertex).idx_outgoing_half_edge_ = idx_outgoing_half_edge; 01843 } 01844 01845 /** \brief Set the terminating vertex index to a given half-edge. */ 01846 inline void 01847 setTerminatingVertexIndex (const HalfEdgeIndex& idx_half_edge, const VertexIndex& idx_terminating_vertex) 01848 { 01849 assert (this->isValid (idx_half_edge)); 01850 this->getHalfEdge (idx_half_edge).idx_terminating_vertex_ = idx_terminating_vertex; 01851 } 01852 01853 /** \brief Set the next half_edge index to a given half-edge. */ 01854 inline void 01855 setNextHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge, const HalfEdgeIndex& idx_next_half_edge) 01856 { 01857 assert (this->isValid (idx_half_edge)); 01858 this->getHalfEdge (idx_half_edge).idx_next_half_edge_ = idx_next_half_edge; 01859 } 01860 01861 /** \brief Set the previous half-edge index to a given half-edge. */ 01862 inline void 01863 setPrevHalfEdgeIndex (const HalfEdgeIndex& idx_half_edge, 01864 const HalfEdgeIndex& idx_prev_half_edge) 01865 { 01866 assert (this->isValid (idx_half_edge)); 01867 this->getHalfEdge (idx_half_edge).idx_prev_half_edge_ = idx_prev_half_edge; 01868 } 01869 01870 /** \brief Set the face index to a given half-edge. */ 01871 inline void 01872 setFaceIndex (const HalfEdgeIndex& idx_half_edge, const FaceIndex& idx_face) 01873 { 01874 assert (this->isValid (idx_half_edge)); 01875 this->getHalfEdge (idx_half_edge).idx_face_ = idx_face; 01876 } 01877 01878 /** \brief Set the inner half-edge index to a given face. */ 01879 inline void 01880 setInnerHalfEdgeIndex (const FaceIndex& idx_face, const HalfEdgeIndex& idx_inner_half_edge) 01881 { 01882 assert (this->isValid (idx_face)); 01883 this->getFace (idx_face).idx_inner_half_edge_ = idx_inner_half_edge; 01884 } 01885 01886 //////////////////////////////////////////////////////////////////////// 01887 // isBoundary / isManifold 01888 //////////////////////////////////////////////////////////////////////// 01889 01890 /** \brief Check if any vertex of the face lies on the boundary. */ 01891 bool 01892 isBoundary (const FaceIndex& idx_face, boost::true_type /*check_vertices*/) const 01893 { 01894 VertexAroundFaceCirculator circ = this->getVertexAroundFaceCirculator (idx_face); 01895 const VertexAroundFaceCirculator circ_end = circ; 01896 01897 do 01898 { 01899 if (this->isBoundary (circ.getTargetIndex ())) 01900 { 01901 return (true); 01902 } 01903 } while (++circ!=circ_end); 01904 01905 return (false); 01906 } 01907 01908 /** \brief Check if any edge of the face lies on the boundary. */ 01909 bool 01910 isBoundary (const FaceIndex& idx_face, boost::false_type /*check_vertices*/) const 01911 { 01912 OuterHalfEdgeAroundFaceCirculator circ = this->getOuterHalfEdgeAroundFaceCirculator (idx_face); 01913 const OuterHalfEdgeAroundFaceCirculator circ_end = circ; 01914 01915 do 01916 { 01917 if (this->isBoundary (circ.getTargetIndex ())) 01918 { 01919 return (true); 01920 } 01921 } while (++circ!=circ_end); 01922 01923 return (false); 01924 } 01925 01926 /** \brief Always manifold. */ 01927 inline bool 01928 isManifold (const VertexIndex&, boost::true_type /*is_manifold*/) const 01929 { 01930 return (true); 01931 } 01932 01933 /** \brief Check if the given vertex is manifold. */ 01934 bool 01935 isManifold (const VertexIndex& idx_vertex, boost::false_type /*is_manifold*/) const 01936 { 01937 OutgoingHalfEdgeAroundVertexCirculator circ = this->getOutgoingHalfEdgeAroundVertexCirculator (idx_vertex); 01938 const OutgoingHalfEdgeAroundVertexCirculator circ_end = circ; 01939 01940 if (!this->isBoundary ((circ++).getTargetIndex ())) return (true); 01941 do 01942 { 01943 if (this->isBoundary (circ.getTargetIndex ())) return (false); 01944 } while (++circ != circ_end); 01945 01946 return (true); 01947 } 01948 01949 /** \brief Always manifold. */ 01950 inline bool 01951 isManifold (boost::true_type /*is_manifold*/) const 01952 { 01953 return (true); 01954 } 01955 01956 /** \brief Check if all vertices in the mesh are manifold. */ 01957 bool 01958 isManifold (boost::false_type /*is_manifold*/) const 01959 { 01960 for (unsigned int i=0; i<this->sizeVertices (); ++i) 01961 { 01962 if (!this->isManifold (VertexIndex (i))) return (false); 01963 } 01964 return (true); 01965 } 01966 01967 //////////////////////////////////////////////////////////////////////// 01968 // reserveData / resizeData / clearData 01969 //////////////////////////////////////////////////////////////////////// 01970 01971 /** \brief Reserve storage space for the mesh data. */ 01972 template <class DataCloudT> inline void 01973 reserveData (DataCloudT& cloud, const size_t n, boost::true_type /*has_data*/) const 01974 { 01975 cloud.reserve (n); 01976 } 01977 01978 /** \brief Does nothing */ 01979 template <class DataCloudT> inline void 01980 reserveData (DataCloudT& /*cloud*/, const size_t /*n*/, boost::false_type /*has_data*/) const 01981 { 01982 } 01983 01984 /** \brief Resize the mesh data. */ 01985 template <class DataCloudT> inline void 01986 resizeData (DataCloudT& data_cloud, const size_t n, const typename DataCloudT::value_type& data, boost::true_type /*has_data*/) const 01987 { 01988 data.resize (n, data); 01989 } 01990 01991 /** \brief Does nothing. */ 01992 template <class DataCloudT> inline void 01993 resizeData (DataCloudT& /*data_cloud*/, const size_t /*n*/, const typename DataCloudT::value_type& /*data*/, boost::false_type /*has_data*/) const 01994 { 01995 } 01996 01997 /** \brief Clear the mesh data. */ 01998 template <class DataCloudT> inline void 01999 clearData (DataCloudT& cloud, boost::true_type /*has_data*/) const 02000 { 02001 cloud.clear (); 02002 } 02003 02004 /** \brief Does nothing. */ 02005 template <class DataCloudT> inline void 02006 clearData (DataCloudT& /*cloud*/, boost::false_type /*has_data*/) const 02007 { 02008 } 02009 02010 //////////////////////////////////////////////////////////////////////// 02011 // get / set Vertex 02012 //////////////////////////////////////////////////////////////////////// 02013 02014 /** \brief Get the vertex for the given index. */ 02015 inline Vertex& 02016 getVertex (const VertexIndex& idx_vertex) 02017 { 02018 assert (this->isValid (idx_vertex)); 02019 return (vertices_ [idx_vertex.get ()]); 02020 } 02021 02022 /** \brief Get the vertex for the given index. */ 02023 inline Vertex 02024 getVertex (const VertexIndex& idx_vertex) const 02025 { 02026 assert (this->isValid (idx_vertex)); 02027 return (vertices_ [idx_vertex.get ()]); 02028 } 02029 02030 /** \brief Set the vertex at the given index. */ 02031 inline void 02032 setVertex (const VertexIndex& idx_vertex, const Vertex& vertex) 02033 { 02034 assert (this->isValid (idx_vertex)); 02035 vertices_ [idx_vertex.get ()] = vertex; 02036 } 02037 02038 //////////////////////////////////////////////////////////////////////// 02039 // get / set HalfEdge 02040 //////////////////////////////////////////////////////////////////////// 02041 02042 /** \brief Get the half-edge for the given index. */ 02043 inline HalfEdge& 02044 getHalfEdge (const HalfEdgeIndex& idx_he) 02045 { 02046 assert (this->isValid (idx_he)); 02047 return (half_edges_ [idx_he.get ()]); 02048 } 02049 02050 /** \brief Get the half-edge for the given index. */ 02051 inline HalfEdge 02052 getHalfEdge (const HalfEdgeIndex& idx_he) const 02053 { 02054 assert (this->isValid (idx_he)); 02055 return (half_edges_ [idx_he.get ()]); 02056 } 02057 02058 /** \brief Set the half-edge at the given index. */ 02059 inline void 02060 setHalfEdge (const HalfEdgeIndex& idx_he, const HalfEdge& half_edge) 02061 { 02062 assert (this->isValid (idx_he)); 02063 half_edges_ [idx_he.get ()] = half_edge; 02064 } 02065 02066 //////////////////////////////////////////////////////////////////////// 02067 // get / set Face 02068 //////////////////////////////////////////////////////////////////////// 02069 02070 /** \brief Get the face for the given index. */ 02071 inline Face& 02072 getFace (const FaceIndex& idx_face) 02073 { 02074 assert (this->isValid (idx_face)); 02075 return (faces_ [idx_face.get ()]); 02076 } 02077 02078 /** \brief Get the face for the given index. */ 02079 inline Face 02080 getFace (const FaceIndex& idx_face) const 02081 { 02082 assert (this->isValid (idx_face)); 02083 return (faces_ [idx_face.get ()]); 02084 } 02085 02086 /** \brief Set the face at the given index. */ 02087 inline void 02088 setFace (const FaceIndex& idx_face, const Face& face) 02089 { 02090 assert (this->isValid (idx_face)); 02091 faces_ [idx_face.get ()] = face; 02092 } 02093 02094 private: 02095 02096 //////////////////////////////////////////////////////////////////////// 02097 // Members 02098 //////////////////////////////////////////////////////////////////////// 02099 02100 /** \brief Data stored for the vertices. */ 02101 VertexDataCloud vertex_data_cloud_; 02102 02103 /** \brief Data stored for the half-edges. */ 02104 HalfEdgeDataCloud half_edge_data_cloud_; 02105 02106 /** \brief Data stored for the edges. */ 02107 EdgeDataCloud edge_data_cloud_; 02108 02109 /** \brief Data stored for the faces. */ 02110 FaceDataCloud face_data_cloud_; 02111 02112 /** \brief Connectivity information for the vertices. */ 02113 Vertices vertices_; 02114 02115 /** \brief Connectivity information for the half-edges. */ 02116 HalfEdges half_edges_; 02117 02118 /** \brief Connectivity information for the faces. */ 02119 Faces faces_; 02120 02121 // NOTE: It is MUCH faster to store these variables permamently. 02122 02123 /** \brief Storage for addFaceImplBase and deleteFace. */ 02124 HalfEdgeIndices inner_he_; 02125 02126 /** \brief Storage for addFaceImplBase. */ 02127 HalfEdgeIndices free_he_; 02128 02129 /** \brief Storage for addFaceImplBase. */ 02130 std::vector <bool> is_new_; 02131 02132 /** \brief Storage for addFaceImplBase. */ 02133 std::vector <bool> make_adjacent_; 02134 02135 /** \brief Storage for deleteFace. */ 02136 std::vector <bool> is_boundary_; 02137 02138 /** \brief Storage for deleteVertex. */ 02139 FaceIndices delete_faces_vertex_; 02140 02141 /** \brief Storage for deleteFace. */ 02142 FaceIndices delete_faces_face_; 02143 02144 public: 02145 02146 template <class MeshT> 02147 friend class pcl::geometry::MeshIO; 02148 02149 EIGEN_MAKE_ALIGNED_OPERATOR_NEW 02150 }; 02151 } // End namespace geometry 02152 } // End namespace pcl 02153 02154 #endif // PCL_GEOMETRY_MESH_BASE_H