OpenMesh: src/OpenMesh/Core/Mesh/PolyConnectivity.hh Source File

00001 /*===========================================================================*\
00002  *                                                                           *
00003  *                               OpenMesh                                    *
00004  *      Copyright (C) 2001-2009 by Computer Graphics Group, RWTH Aachen      *
00005  *                           www.openmesh.org                                *
00006  *                                                                           *
00007  *---------------------------------------------------------------------------* 
00008  *  This file is part of OpenMesh.                                           *
00009  *                                                                           *
00010  *  OpenMesh is free software: you can redistribute it and/or modify         * 
00011  *  it under the terms of the GNU Lesser General Public License as           *
00012  *  published by the Free Software Foundation, either version 3 of           *
00013  *  the License, or (at your option) any later version with the              *
00014  *  following exceptions:                                                    *
00015  *                                                                           *
00016  *  If other files instantiate templates or use macros                       *
00017  *  or inline functions from this file, or you compile this file and         *
00018  *  link it with other files to produce an executable, this file does        *
00019  *  not by itself cause the resulting executable to be covered by the        *
00020  *  GNU Lesser General Public License. This exception does not however       *
00021  *  invalidate any other reasons why the executable file might be            *
00022  *  covered by the GNU Lesser General Public License.                        *
00023  *                                                                           *
00024  *  OpenMesh is distributed in the hope that it will be useful,              *
00025  *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
00026  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
00027  *  GNU Lesser General Public License for more details.                      *
00028  *                                                                           *
00029  *  You should have received a copy of the GNU LesserGeneral Public          *
00030  *  License along with OpenMesh.  If not,                                    *
00031  *  see <http://www.gnu.org/licenses/>.                                      *
00032  *                                                                           *
00033 \*===========================================================================*/ 
00034 
00035 /*===========================================================================*\
00036  *                                                                           *             
00037  *   $Revision: 254 $                                                         *
00038  *   $Date: 2009-12-10 11:04:59 +0100 (Do, 10. Dez 2009) $                   *
00039  *                                                                           *
00040 \*===========================================================================*/
00041 
00042 #ifndef OPENMESH_POLYCONNECTIVITY_HH
00043 #define OPENMESH_POLYCONNECTIVITY_HH
00044 
00045 #include <OpenMesh/Core/Mesh/ArrayKernel.hh>
00046 #include <OpenMesh/Core/Mesh/IteratorsT.hh>
00047 #include <OpenMesh/Core/Mesh/CirculatorsT.hh>
00048 
00049 namespace OpenMesh
00050 {
00051 
00054 class PolyConnectivity : public ArrayKernel
00055 {
00056 public:
00058 
00059 
00060   static const VertexHandle                           InvalidVertexHandle;
00062   static const HalfedgeHandle                         InvalidHalfedgeHandle;
00064   static const EdgeHandle                             InvalidEdgeHandle;
00066   static const FaceHandle                             InvalidFaceHandle;
00068 
00069   typedef PolyConnectivity                            This;
00070 
00071   //--- iterators ---
00072 
00078 
00079   typedef Iterators::VertexIterT<This>                VertexIter;
00080   typedef Iterators::HalfedgeIterT<This>              HalfedgeIter;
00081   typedef Iterators::EdgeIterT<This>                  EdgeIter;
00082   typedef Iterators::FaceIterT<This>                  FaceIter;
00083 
00084   typedef Iterators::ConstVertexIterT<This>           ConstVertexIter;
00085   typedef Iterators::ConstHalfedgeIterT<This>         ConstHalfedgeIter;
00086   typedef Iterators::ConstEdgeIterT<This>             ConstEdgeIter;
00087   typedef Iterators::ConstFaceIterT<This>             ConstFaceIter;
00089 
00090   //--- circulators ---
00091 
00097 
00098   typedef Iterators::VertexVertexIterT<This>          VertexVertexIter;
00099   typedef Iterators::VertexOHalfedgeIterT<This>       VertexOHalfedgeIter;
00100   typedef Iterators::VertexIHalfedgeIterT<This>       VertexIHalfedgeIter;
00101   typedef Iterators::VertexEdgeIterT<This>            VertexEdgeIter;
00102   typedef Iterators::VertexFaceIterT<This>            VertexFaceIter;
00103   typedef Iterators::FaceVertexIterT<This>            FaceVertexIter;
00104   typedef Iterators::FaceHalfedgeIterT<This>          FaceHalfedgeIter;
00105   typedef Iterators::FaceEdgeIterT<This>              FaceEdgeIter;
00106   typedef Iterators::FaceFaceIterT<This>              FaceFaceIter;
00107 
00108   typedef Iterators::ConstVertexVertexIterT<This>     ConstVertexVertexIter;
00109   typedef Iterators::ConstVertexOHalfedgeIterT<This>  ConstVertexOHalfedgeIter;
00110   typedef Iterators::ConstVertexIHalfedgeIterT<This>  ConstVertexIHalfedgeIter;
00111   typedef Iterators::ConstVertexEdgeIterT<This>       ConstVertexEdgeIter;
00112   typedef Iterators::ConstVertexFaceIterT<This>       ConstVertexFaceIter;
00113   typedef Iterators::ConstFaceVertexIterT<This>       ConstFaceVertexIter;
00114   typedef Iterators::ConstFaceHalfedgeIterT<This>     ConstFaceHalfedgeIter;
00115   typedef Iterators::ConstFaceEdgeIterT<This>         ConstFaceEdgeIter;
00116   typedef Iterators::ConstFaceFaceIterT<This>         ConstFaceFaceIter;
00118 
00119   // --- shortcuts
00120 
00125 
00126   typedef VertexHandle    VHandle;
00127   typedef HalfedgeHandle  HHandle;
00128   typedef EdgeHandle      EHandle;
00129   typedef FaceHandle      FHandle;
00130 
00131   typedef VertexIter    VIter;
00132   typedef HalfedgeIter  HIter;
00133   typedef EdgeIter      EIter;
00134   typedef FaceIter      FIter;
00135 
00136   typedef ConstVertexIter    CVIter;
00137   typedef ConstHalfedgeIter  CHIter;
00138   typedef ConstEdgeIter      CEIter;
00139   typedef ConstFaceIter      CFIter;
00140 
00141   typedef VertexVertexIter      VVIter;
00142   typedef VertexOHalfedgeIter   VOHIter;
00143   typedef VertexIHalfedgeIter   VIHIter;
00144   typedef VertexEdgeIter        VEIter;
00145   typedef VertexFaceIter        VFIter;
00146   typedef FaceVertexIter        FVIter;
00147   typedef FaceHalfedgeIter      FHIter;
00148   typedef FaceEdgeIter          FEIter;
00149   typedef FaceFaceIter          FFIter;
00150 
00151   typedef ConstVertexVertexIter      CVVIter;
00152   typedef ConstVertexOHalfedgeIter   CVOHIter;
00153   typedef ConstVertexIHalfedgeIter   CVIHIter;
00154   typedef ConstVertexEdgeIter        CVEIter;
00155   typedef ConstVertexFaceIter        CVFIter;
00156   typedef ConstFaceVertexIter        CFVIter;
00157   typedef ConstFaceHalfedgeIter      CFHIter;
00158   typedef ConstFaceEdgeIter          CFEIter;
00159   typedef ConstFaceFaceIter          CFFIter;
00161 
00162 public:
00163 
00164   PolyConnectivity()  {}
00165   virtual ~PolyConnectivity() {}
00166 
00167   inline static bool is_triangles()
00168   { return false; }
00169 
00172   inline void assign_connectivity(const PolyConnectivity& _other)
00173   { ArrayKernel::assign_connectivity(_other); }
00174   
00178 
00179   inline VertexHandle add_vertex()
00180   { return new_vertex(); }
00181 
00183   FaceHandle add_face(const std::vector<VertexHandle>& _vhandles)
00184   { return add_face(&_vhandles.front(), _vhandles.size()); }
00185   
00186   FaceHandle add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2)
00187   { 
00188     VertexHandle vhs[3] = { _vh0, _vh1, _vh2 };
00189     return add_face(vhs, 3); 
00190   }
00191   
00192   FaceHandle add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2, VertexHandle _vh3)
00193   { 
00194     VertexHandle vhs[4] = { _vh0, _vh1, _vh2, _vh3 };
00195     return add_face(vhs, 4); 
00196   }
00197   
00198   FaceHandle add_face(const VertexHandle* _vhandles, uint _vhs_size);
00200 
00202 
00203 
00209   void delete_vertex(VertexHandle _vh, bool _delete_isolated_vertices = true);
00210 
00219   void delete_edge(EdgeHandle _eh, bool _delete_isolated_vertices=true);
00220 
00231   void delete_face(FaceHandle _fh, bool _delete_isolated_vertices=true);
00232 
00234   
00238 
00240   VertexIter vertices_begin()
00241   { return VertexIter(*this, VertexHandle(0)); }
00243   ConstVertexIter vertices_begin() const
00244   { return ConstVertexIter(*this, VertexHandle(0)); }
00246   VertexIter vertices_end()
00247   { return VertexIter(*this, VertexHandle(n_vertices())); }
00249   ConstVertexIter vertices_end() const
00250   { return ConstVertexIter(*this, VertexHandle(n_vertices())); }
00251 
00253   HalfedgeIter halfedges_begin()
00254   { return HalfedgeIter(*this, HalfedgeHandle(0)); }
00256   ConstHalfedgeIter halfedges_begin() const
00257   { return ConstHalfedgeIter(*this, HalfedgeHandle(0)); }
00259   HalfedgeIter halfedges_end()
00260   { return HalfedgeIter(*this, HalfedgeHandle(n_halfedges())); }
00262   ConstHalfedgeIter halfedges_end() const
00263   { return ConstHalfedgeIter(*this, HalfedgeHandle(n_halfedges())); }
00264 
00266   EdgeIter edges_begin()
00267   { return EdgeIter(*this, EdgeHandle(0)); }
00269   ConstEdgeIter edges_begin() const
00270   { return ConstEdgeIter(*this, EdgeHandle(0)); }
00272   EdgeIter edges_end()
00273   { return EdgeIter(*this, EdgeHandle(n_edges())); }
00275   ConstEdgeIter edges_end() const
00276   { return ConstEdgeIter(*this, EdgeHandle(n_edges())); }
00277 
00279   FaceIter faces_begin()
00280   { return FaceIter(*this, FaceHandle(0)); }
00282   ConstFaceIter faces_begin() const
00283   { return ConstFaceIter(*this, FaceHandle(0)); }
00285   FaceIter faces_end()
00286   { return FaceIter(*this, FaceHandle(n_faces())); }
00288   ConstFaceIter faces_end() const
00289   { return ConstFaceIter(*this, FaceHandle(n_faces())); }
00290 
00292 
00293 
00294 
00298 
00300   VertexIter vertices_sbegin()
00301   { return VertexIter(*this, VertexHandle(0), true); }
00303   ConstVertexIter vertices_sbegin() const
00304   { return ConstVertexIter(*this, VertexHandle(0), true); }
00305 
00307   HalfedgeIter halfedges_sbegin()
00308   { return HalfedgeIter(*this, HalfedgeHandle(0), true); }
00310   ConstHalfedgeIter halfedges_sbegin() const
00311   { return ConstHalfedgeIter(*this, HalfedgeHandle(0), true); }
00312 
00314   EdgeIter edges_sbegin()
00315   { return EdgeIter(*this, EdgeHandle(0), true); }
00317   ConstEdgeIter edges_sbegin() const
00318   { return ConstEdgeIter(*this, EdgeHandle(0), true); }
00319 
00321   FaceIter faces_sbegin()
00322   { return FaceIter(*this, FaceHandle(0), true); }
00324   ConstFaceIter faces_sbegin() const
00325   { return ConstFaceIter(*this, FaceHandle(0), true); }
00326 
00328 
00329   //--- circulators ---
00330 
00334 
00336   VertexVertexIter vv_iter(VertexHandle _vh)
00337   { return VertexVertexIter(*this, _vh); }
00339   VertexIHalfedgeIter vih_iter(VertexHandle _vh)
00340   { return VertexIHalfedgeIter(*this, _vh); }
00342   VertexOHalfedgeIter voh_iter(VertexHandle _vh)
00343   { return VertexOHalfedgeIter(*this, _vh); }
00345   VertexEdgeIter ve_iter(VertexHandle _vh)
00346   { return VertexEdgeIter(*this, _vh); }
00348   VertexFaceIter vf_iter(VertexHandle _vh)
00349   { return VertexFaceIter(*this, _vh); }
00350 
00352   ConstVertexVertexIter cvv_iter(VertexHandle _vh) const
00353   { return ConstVertexVertexIter(*this, _vh); }
00355   ConstVertexIHalfedgeIter cvih_iter(VertexHandle _vh) const
00356   { return ConstVertexIHalfedgeIter(*this, _vh); }
00358   ConstVertexOHalfedgeIter cvoh_iter(VertexHandle _vh) const
00359   { return ConstVertexOHalfedgeIter(*this, _vh); }
00361   ConstVertexEdgeIter cve_iter(VertexHandle _vh) const
00362   { return ConstVertexEdgeIter(*this, _vh); }
00364   ConstVertexFaceIter cvf_iter(VertexHandle _vh) const
00365   { return ConstVertexFaceIter(*this, _vh); }
00366 
00368   FaceVertexIter fv_iter(FaceHandle _fh)
00369   { return FaceVertexIter(*this, _fh); }
00371   FaceHalfedgeIter fh_iter(FaceHandle _fh)
00372   { return FaceHalfedgeIter(*this, _fh); }
00374   FaceEdgeIter fe_iter(FaceHandle _fh)
00375   { return FaceEdgeIter(*this, _fh); }
00377   FaceFaceIter ff_iter(FaceHandle _fh)
00378   { return FaceFaceIter(*this, _fh); }
00379 
00381   ConstFaceVertexIter cfv_iter(FaceHandle _fh) const
00382   { return ConstFaceVertexIter(*this, _fh); }
00384   ConstFaceHalfedgeIter cfh_iter(FaceHandle _fh) const
00385   { return ConstFaceHalfedgeIter(*this, _fh); }
00387   ConstFaceEdgeIter cfe_iter(FaceHandle _fh) const
00388   { return ConstFaceEdgeIter(*this, _fh); }
00390   ConstFaceFaceIter cff_iter(FaceHandle _fh) const
00391   { return ConstFaceFaceIter(*this, _fh); }
00392   
00393   // 'begin' circulators
00394   
00396   VertexVertexIter vv_begin(VertexHandle _vh)
00397   { return VertexVertexIter(*this, _vh); }
00399   VertexIHalfedgeIter vih_begin(VertexHandle _vh)
00400   { return VertexIHalfedgeIter(*this, _vh); }
00402   VertexOHalfedgeIter voh_begin(VertexHandle _vh)
00403   { return VertexOHalfedgeIter(*this, _vh); }
00405   VertexEdgeIter ve_begin(VertexHandle _vh)
00406   { return VertexEdgeIter(*this, _vh); }
00408   VertexFaceIter vf_begin(VertexHandle _vh)
00409   { return VertexFaceIter(*this, _vh); }
00410 
00412   ConstVertexVertexIter cvv_begin(VertexHandle _vh) const
00413   { return ConstVertexVertexIter(*this, _vh); }
00415   ConstVertexIHalfedgeIter cvih_begin(VertexHandle _vh) const
00416   { return ConstVertexIHalfedgeIter(*this, _vh); }
00418   ConstVertexOHalfedgeIter cvoh_begin(VertexHandle _vh) const
00419   { return ConstVertexOHalfedgeIter(*this, _vh); }
00421   ConstVertexEdgeIter cve_begin(VertexHandle _vh) const
00422   { return ConstVertexEdgeIter(*this, _vh); }
00424   ConstVertexFaceIter cvf_begin(VertexHandle _vh) const
00425   { return ConstVertexFaceIter(*this, _vh); }
00426 
00428   FaceVertexIter fv_begin(FaceHandle _fh)
00429   { return FaceVertexIter(*this, _fh); }
00431   FaceHalfedgeIter fh_begin(FaceHandle _fh)
00432   { return FaceHalfedgeIter(*this, _fh); }
00434   FaceEdgeIter fe_begin(FaceHandle _fh)
00435   { return FaceEdgeIter(*this, _fh); }
00437   FaceFaceIter ff_begin(FaceHandle _fh)
00438   { return FaceFaceIter(*this, _fh); }
00439 
00441   ConstFaceVertexIter cfv_begin(FaceHandle _fh) const
00442   { return ConstFaceVertexIter(*this, _fh); }
00444   ConstFaceHalfedgeIter cfh_begin(FaceHandle _fh) const
00445   { return ConstFaceHalfedgeIter(*this, _fh); }
00447   ConstFaceEdgeIter cfe_begin(FaceHandle _fh) const
00448   { return ConstFaceEdgeIter(*this, _fh); }
00450   ConstFaceFaceIter cff_begin(FaceHandle _fh) const
00451   { return ConstFaceFaceIter(*this, _fh); }
00452   
00453   // 'end' circulators
00454   
00456   VertexVertexIter vv_end(VertexHandle _vh)
00457   { return VertexVertexIter(*this, _vh, true); }
00459   VertexIHalfedgeIter vih_end(VertexHandle _vh)
00460   { return VertexIHalfedgeIter(*this, _vh, true); }
00462   VertexOHalfedgeIter voh_end(VertexHandle _vh)
00463   { return VertexOHalfedgeIter(*this, _vh, true); }
00465   VertexEdgeIter ve_end(VertexHandle _vh)
00466   { return VertexEdgeIter(*this, _vh, true); }
00468   VertexFaceIter vf_end(VertexHandle _vh)
00469   { return VertexFaceIter(*this, _vh, true); }
00470 
00472   ConstVertexVertexIter cvv_end(VertexHandle _vh) const
00473   { return ConstVertexVertexIter(*this, _vh, true); }
00475   ConstVertexIHalfedgeIter cvih_end(VertexHandle _vh) const
00476   { return ConstVertexIHalfedgeIter(*this, _vh, true); }
00478   ConstVertexOHalfedgeIter cvoh_end(VertexHandle _vh) const
00479   { return ConstVertexOHalfedgeIter(*this, _vh, true); }
00481   ConstVertexEdgeIter cve_end(VertexHandle _vh) const
00482   { return ConstVertexEdgeIter(*this, _vh, true); }
00484   ConstVertexFaceIter cvf_end(VertexHandle _vh) const
00485   { return ConstVertexFaceIter(*this, _vh, true); }
00486 
00488   FaceVertexIter fv_end(FaceHandle _fh)
00489   { return FaceVertexIter(*this, _fh, true); }
00491   FaceHalfedgeIter fh_end(FaceHandle _fh)
00492   { return FaceHalfedgeIter(*this, _fh, true); }
00494   FaceEdgeIter fe_end(FaceHandle _fh)
00495   { return FaceEdgeIter(*this, _fh, true); }
00497   FaceFaceIter ff_end(FaceHandle _fh)
00498   { return FaceFaceIter(*this, _fh, true); }
00499 
00501   ConstFaceVertexIter cfv_end(FaceHandle _fh) const
00502   { return ConstFaceVertexIter(*this, _fh, true); }
00504   ConstFaceHalfedgeIter cfh_end(FaceHandle _fh) const
00505   { return ConstFaceHalfedgeIter(*this, _fh, true); }
00507   ConstFaceEdgeIter cfe_end(FaceHandle _fh) const
00508   { return ConstFaceEdgeIter(*this, _fh, true); }
00510   ConstFaceFaceIter cff_end(FaceHandle _fh) const
00511   { return ConstFaceFaceIter(*this, _fh, true); }
00513 
00517   bool is_boundary(HalfedgeHandle _heh) const
00518   { return ArrayKernel::is_boundary(_heh); }
00519 
00522   bool is_boundary(EdgeHandle _eh) const
00523   {
00524     return (is_boundary(halfedge_handle(_eh, 0)) ||
00525             is_boundary(halfedge_handle(_eh, 1)));
00526   }
00528   bool is_boundary(VertexHandle _vh) const
00529   {
00530     HalfedgeHandle heh(halfedge_handle(_vh));
00531     return (!(heh.is_valid() && face_handle(heh).is_valid()));
00532   }
00533 
00540   bool is_boundary(FaceHandle _fh, bool _check_vertex=false) const;
00542   bool is_manifold(VertexHandle _vh) const;
00544 
00545   // --- shortcuts ---
00546   
00548   inline FaceHandle opposite_face_handle(HalfedgeHandle _heh) const
00549   { return face_handle(opposite_halfedge_handle(_heh)); }
00550     
00551   // --- misc ---
00552 
00556   void adjust_outgoing_halfedge(VertexHandle _vh);
00558   HalfedgeHandle find_halfedge(VertexHandle _start_vh, VertexHandle _end_vh) const;
00560   uint valence(VertexHandle _vh) const;
00562   uint valence(FaceHandle _fh) const;
00563   
00564   // --- connectivity operattions 
00565     
00579   void collapse(HalfedgeHandle _heh);
00584   bool is_simple_link(EdgeHandle _eh) const;
00589   bool is_simply_connected(FaceHandle _fh) const;
00602   FaceHandle remove_edge(EdgeHandle _eh);
00606   void reinsert_edge(EdgeHandle _eh);
00616   HalfedgeHandle insert_edge(HalfedgeHandle _prev_heh, HalfedgeHandle _next_heh);
00617     
00619   void split(FaceHandle _fh, VertexHandle _vh);
00621   void triangulate(FaceHandle _fh);
00623   void triangulate();
00624   
00625 
00631 
00632   const Vertex&    deref(VertexHandle _h)   const { return vertex(_h); }
00633   Vertex&          deref(VertexHandle _h)         { return vertex(_h); }
00634   const Halfedge&  deref(HalfedgeHandle _h) const { return halfedge(_h); }
00635   Halfedge&        deref(HalfedgeHandle _h)       { return halfedge(_h); }
00636   const Edge&      deref(EdgeHandle _h)     const { return edge(_h); }
00637   Edge&            deref(EdgeHandle _h)           { return edge(_h); }
00638   const Face&      deref(FaceHandle _h)     const { return face(_h); }
00639   Face&            deref(FaceHandle _h)           { return face(_h); }
00641 
00642 protected:  
00644   void collapse_edge(HalfedgeHandle _hh);
00646   void collapse_loop(HalfedgeHandle _hh);
00647 };
00648 
00649 }//namespace OpenMesh
00650 
00651 #endif//OPENMESH_POLYCONNECTIVITY_HH