Main Page   Modules   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

ArrayKernelT.hh

00001 //=============================================================================
00002 //                                                                            
00003 //                               OpenMesh                                     
00004 //        Copyright (C) 2003 by Computer Graphics Group, RWTH Aachen          
00005 //                           www.openmesh.org                                 
00006 //                                                                            
00007 //-----------------------------------------------------------------------------
00008 //                                                                            
00009 //                                License                                     
00010 //                                                                            
00011 //   This library is free software; you can redistribute it and/or modify it 
00012 //   under the terms of the GNU Library General Public License as published  
00013 //   by the Free Software Foundation, version 2.                             
00014 //                                                                             
00015 //   This library is distributed in the hope that it will be useful, but       
00016 //   WITHOUT ANY WARRANTY; without even the implied warranty of                
00017 //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         
00018 //   Library General Public License for more details.                          
00019 //                                                                            
00020 //   You should have received a copy of the GNU Library General Public         
00021 //   License along with this library; if not, write to the Free Software       
00022 //   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 
00023 //                                                                            
00024 //-----------------------------------------------------------------------------
00025 //                                                                            
00026 //   $Revision: 1.11 $
00027 //   $Date: 2004/01/08 15:51:04 $
00028 //                                                                            
00029 //=============================================================================
00030 
00031 
00032 //=============================================================================
00033 //
00034 //  CLASS ArrayKernelT
00035 //
00036 //=============================================================================
00037 
00038 
00039 #ifndef OPENMESH_ARRAY_KERNEL_HH
00040 #define OPENMESH_ARRAY_KERNEL_HH
00041 
00042 
00043 //== INCLUDES =================================================================
00044 
00045 
00046 #include <OpenMesh/Core/System/config.h>
00047 #include <OpenMesh/Core/Mesh/Kernels/Common/AttribKernelT.hh>
00048 #include <OpenMesh/Core/Utils/GenProg.hh>
00049 #include <vector>
00050 
00051 
00052 
00053 //== NAMESPACES ===============================================================
00054 
00055 
00056 namespace OpenMesh {
00057 
00058 
00059 //== CLASS DEFINITION =========================================================
00060 
00061 
00078 template <class AttribKernel, class FinalMeshItems>
00079 class ArrayKernelT : public AttribKernel
00080 {
00081 public:
00082   
00083   typedef ArrayKernelT<AttribKernel, FinalMeshItems>  This;
00084   typedef AttribKernel                                Base;
00085 
00086   // attributes
00087   typedef typename Base::HasPrevHalfedge              HasPrevHalfedge;
00088 
00089   // item types
00090   typedef typename FinalMeshItems::Vertex             Vertex;
00091   typedef typename FinalMeshItems::Halfedge           Halfedge;
00092   typedef typename FinalMeshItems::Edge               Edge;
00093   typedef typename FinalMeshItems::Face               Face;
00094   typedef typename FinalMeshItems::Point              Point;
00095   typedef typename FinalMeshItems::Scalar             Scalar;
00096 
00097   // handles
00098   typedef OpenMesh::VertexHandle       VertexHandle;    
00099   typedef OpenMesh::HalfedgeHandle     HalfedgeHandle;  
00100   typedef OpenMesh::EdgeHandle         EdgeHandle;      
00101   typedef OpenMesh::FaceHandle         FaceHandle;      
00102 
00103 
00104 
00105   // --- constructor/destructor ---
00106 
00107 
00108   ArrayKernelT() {}
00109   ~ArrayKernelT() { clear(); }
00110 
00111 
00112 
00113   // --- handle -> item ---
00114 
00115   VertexHandle handle(const Vertex& _v) const  { 
00116     return VertexHandle(&_v - &vertices_.front());
00117   }
00118 
00119   HalfedgeHandle handle(const Halfedge& _he) const {
00120     unsigned int eh(((char*)&edges_.front() - (char*)&_he) % sizeof(Edge));
00121     assert((&_he == &edges_[eh].halfedges_[0]) || 
00122            (&_he == &edges_[eh].halfedges_[1]));
00123     return ((&_he == &edges_[eh].halfedges_[0]) ? 
00124             HalfedgeHandle(eh<<1) : 
00125             HalfedgeHandle((eh<<1)+1));
00126   }
00127 
00128   EdgeHandle handle(const Edge& _e) const {
00129     return EdgeHandle(&_e - &edges_.front());
00130   }
00131 
00132   FaceHandle handle(const Face& _f) const {
00133     return FaceHandle(&_f - &faces_.front());
00134   }
00135 
00136 
00137 
00138 #define SIGNED(x) signed( (x) )
00139 
00140 
00141   // --- item -> handle ---
00142   
00143   const Vertex& vertex(VertexHandle _vh) const { 
00144     assert(_vh.idx() >= 0 && _vh.idx() < SIGNED(n_vertices())); 
00145     return vertices_[_vh.idx()];
00146   }
00147 
00148   Vertex& vertex(VertexHandle _vh) { 
00149     assert(_vh.idx() >= 0 && _vh.idx() < SIGNED(n_vertices())); 
00150     return vertices_[_vh.idx()];
00151   }
00152 
00153 
00154   const Halfedge& halfedge(HalfedgeHandle _heh) const { 
00155     assert(_heh.idx() >= 0 && _heh.idx() < SIGNED(n_edges()*2));
00156     return edges_[_heh.idx() >> 1].halfedges_[_heh.idx() & 1];
00157   }
00158 
00159   Halfedge& halfedge(HalfedgeHandle _heh) { 
00160     assert(_heh.idx() >= 0 && _heh.idx() < SIGNED(n_edges())*2);
00161     return edges_[_heh.idx() >> 1].halfedges_[_heh.idx() & 1];
00162   }
00163 
00164 
00165   const Edge& edge(EdgeHandle _eh) const { 
00166     assert(_eh.idx() >= 0 && _eh.idx() < SIGNED(n_edges()));
00167     return edges_[_eh.idx()];
00168   }
00169 
00170   Edge& edge(EdgeHandle _eh) { 
00171     assert(_eh.idx() >= 0 && _eh.idx() < SIGNED(n_edges()));
00172     return edges_[_eh.idx()];
00173   }
00174 
00175 
00176   const Face& face(FaceHandle _fh) const { 
00177     assert(_fh.idx() >= 0 && _fh.idx() < SIGNED(n_faces()));
00178     return faces_[_fh.idx()]; 
00179   }
00180 
00181   Face& face(FaceHandle _fh) { 
00182     assert(_fh.idx() >= 0 && _fh.idx() < SIGNED(n_faces()));
00183     return faces_[_fh.idx()]; 
00184   }
00185 
00186 #undef SIGNED
00187 
00188 
00189 
00190   // --- get i'th items ---
00191 
00192   VertexHandle vertex_handle(unsigned int _i) const {
00193     return (_i < n_vertices()) ? handle( vertices_[_i] ) : VertexHandle();
00194   }
00195  
00196   HalfedgeHandle halfedge_handle(unsigned int _i) const {
00197     return (_i < n_halfedges()) ? halfedge_handle(edge_handle(_i/2), _i%2) : HalfedgeHandle();
00198   }
00199 
00200   EdgeHandle edge_handle(unsigned int _i) const {
00201     return (_i < n_edges()) ? handle(edges_[_i]) : EdgeHandle();
00202   }
00203 
00204   FaceHandle face_handle(unsigned int _i) const {
00205     return (_i < n_faces()) ? handle(faces_[_i]) : FaceHandle();
00206   }
00207 
00208 
00209   // --- add new items ---
00210 
00211   void reserve( unsigned int _n_vertices,
00212                 unsigned int _n_edges,
00213                 unsigned int _n_faces ) {
00214     vertices_.reserve(_n_vertices);
00215     edges_.reserve(_n_edges);  
00216     faces_.reserve(_n_faces);
00217 
00218     vprops_reserve(_n_vertices);
00219     hprops_reserve(_n_edges*2);
00220     eprops_reserve(_n_edges);
00221     fprops_reserve(_n_faces);
00222   }
00223 
00224 
00225 public:
00226 
00227   VertexHandle new_vertex() {    
00228     vertices_.push_back(Vertex());
00229     vprops_resize(n_vertices());
00230 
00231     return handle(vertices_.back());
00232   }
00233 
00234 
00235   VertexHandle new_vertex(const Point& _p) {
00236     vertices_.push_back(Vertex());
00237     vprops_resize(n_vertices());
00238 
00239     VertexHandle vh(handle(vertices_.back()));
00240     set_point(vh, _p);
00241     return vh;
00242   }
00243 
00244 
00245   HalfedgeHandle new_edge(VertexHandle _start_vertex_handle, 
00246                           VertexHandle _end_vertex_handle) 
00247   {
00248     edges_.push_back(Edge());
00249     eprops_resize(n_edges());
00250     hprops_resize(n_halfedges());
00251 
00252     EdgeHandle eh(handle(edges_.back()));
00253     HalfedgeHandle heh0(halfedge_handle(eh, 0));
00254     HalfedgeHandle heh1(halfedge_handle(eh, 1));
00255     set_vertex_handle(heh0, _end_vertex_handle);
00256     set_vertex_handle(heh1, _start_vertex_handle);
00257     return heh0;
00258   }
00259 
00260 
00261   FaceHandle new_face() {
00262     faces_.push_back(Face());
00263     fprops_resize(n_faces());
00264     return handle(faces_.back());
00265   }
00266 
00267   FaceHandle new_face(const Face& _f) {
00268     faces_.push_back(_f);
00269     fprops_resize(n_faces());
00270     return handle(faces_.back());
00271   }
00272 
00273 public:
00274 
00275 
00276   
00277   // --- deletion ---
00278 
00279   void garbage_collection(bool _v=true, bool _e=true, bool _f=true);
00280 
00281   void clear() {
00282     vertices_.clear();
00283     edges_.clear();
00284     faces_.clear();
00285 
00286     vprops_resize(0);
00287     eprops_resize(0);
00288     hprops_resize(0);
00289     fprops_resize(0);
00290   }
00291 
00292   void resize( unsigned int _n_vertices,
00293                unsigned int _n_edges,
00294                unsigned int _n_faces ) 
00295   {
00296     vertices_.resize(_n_vertices);
00297     edges_.resize(_n_edges);
00298     faces_.resize(_n_faces);
00299 
00300     vprops_resize(n_vertices());
00301     hprops_resize(n_halfedges());
00302     eprops_resize(n_edges());
00303     fprops_resize(n_faces());
00304   }
00305 
00306 
00307 
00308 
00309   // --- number of items ---
00310 
00311   unsigned int n_vertices()  const { return vertices_.size(); }
00312   unsigned int n_halfedges() const { return 2*edges_.size(); }
00313   unsigned int n_edges()     const { return edges_.size(); }
00314   unsigned int n_faces()     const { return faces_.size(); }
00315 
00316   bool vertices_empty()  const { return vertices_.empty(); }
00317   bool halfedges_empty() const { return edges_.empty(); }
00318   bool edges_empty()     const { return edges_.empty(); }
00319   bool faces_empty()     const { return faces_.empty(); }
00320 
00321 
00322 
00323 
00324 
00325   // --- vertex connectivity ---
00326 
00327   HalfedgeHandle halfedge_handle(VertexHandle _vh) const { 
00328     return vertex(_vh).halfedge_handle_; 
00329   }
00330 
00331   void set_halfedge_handle(VertexHandle _vh, HalfedgeHandle _heh) { 
00332     vertex(_vh).halfedge_handle_ = _heh;
00333   }
00334 
00335 
00336  
00337   // --- halfedge connectivity ---
00338 
00339 
00340   VertexHandle to_vertex_handle(HalfedgeHandle _heh) const { 
00341     return halfedge(_heh).vertex_handle_; 
00342   }
00343 
00344   VertexHandle from_vertex_handle(HalfedgeHandle _heh) const { 
00345     return to_vertex_handle(opposite_halfedge_handle(_heh));
00346   }
00347 
00348   void set_vertex_handle(HalfedgeHandle _heh, VertexHandle _vh) {
00349     halfedge(_heh).vertex_handle_ = _vh;  
00350   }
00351 
00352 
00353 
00354   FaceHandle face_handle(HalfedgeHandle _heh) const { 
00355     return halfedge(_heh).face_handle_; 
00356   }
00357 
00358   void set_face_handle(HalfedgeHandle _heh, FaceHandle _fh) { 
00359     halfedge(_heh).face_handle_ = _fh;  
00360   }
00361 
00362 
00363   HalfedgeHandle next_halfedge_handle(HalfedgeHandle _heh) const { 
00364     return halfedge(_heh).next_halfedge_handle_; 
00365   }
00366 
00367   void set_next_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _nheh) { 
00368     halfedge(_heh).next_halfedge_handle_ = _nheh;
00369     set_prev_halfedge_handle(_nheh, _heh);
00370   }
00371 
00372 
00373   void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh) {
00374     set_prev_halfedge_handle(_heh, _pheh, HasPrevHalfedge());
00375   }
00376 
00377   void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
00378                                 GenProg::True) { 
00379     halfedge(_heh).prev_halfedge_handle_ = _pheh;
00380   }
00381   void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
00382                                 GenProg::False) {}
00383 
00384 
00385   HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh) const { 
00386     return prev_halfedge_handle(_heh, HasPrevHalfedge() );
00387   }
00388 
00389   HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh,
00390                                       GenProg::True) const { 
00391     return halfedge(_heh).prev_halfedge_handle_; 
00392   }
00393 
00394   HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh, 
00395                                       GenProg::False) const {
00396     HalfedgeHandle  heh(_heh);
00397     HalfedgeHandle  next_heh(next_halfedge_handle(heh));
00398     while (next_heh != _heh) {
00399       heh = next_heh;
00400       next_heh = next_halfedge_handle(next_heh);
00401     }
00402     return heh;
00403   }
00404 
00405 
00406   HalfedgeHandle opposite_halfedge_handle(HalfedgeHandle _heh) const { 
00407     return HalfedgeHandle((_heh.idx() & 1) ? _heh.idx()-1 : _heh.idx()+1);
00408   }
00409 
00410 
00411   HalfedgeHandle ccw_rotated_halfedge_handle(HalfedgeHandle _heh) const {
00412     return opposite_halfedge_handle(prev_halfedge_handle(_heh));
00413   }
00414 
00415 
00416   HalfedgeHandle cw_rotated_halfedge_handle(HalfedgeHandle _heh) const {
00417     return next_halfedge_handle(opposite_halfedge_handle(_heh));
00418   }
00419 
00420 
00421 
00422   // --- edge connectivity ---
00423 
00424 
00425   HalfedgeHandle halfedge_handle(EdgeHandle _eh, unsigned int _i) const {
00426     assert(_i<=1);
00427     return HalfedgeHandle((_eh.idx() << 1) + _i);
00428   }
00429   
00430 
00431   EdgeHandle edge_handle(HalfedgeHandle _heh) const {
00432     return EdgeHandle(_heh.idx() >> 1);
00433   }
00434 
00435 
00436 
00437   // --- face connectivity ---
00438 
00439 
00440   HalfedgeHandle halfedge_handle(FaceHandle _fh) const { 
00441     return face(_fh).halfedge_handle_; 
00442   }
00443 
00444   void set_halfedge_handle(FaceHandle _fh, HalfedgeHandle _heh) { 
00445     face(_fh).halfedge_handle_ = _heh;
00446   }
00447 
00448 
00449 
00450 private:
00451 
00452   // iterators
00453   typedef std::vector<Vertex>                         VertexContainer;
00454   typedef std::vector<Edge>                           EdgeContainer;
00455   typedef std::vector<Face>                           FaceContainer;
00456   typedef typename VertexContainer::iterator          KernelVertexIter;
00457   typedef typename VertexContainer::const_iterator    KernelConstVertexIter;
00458   typedef typename EdgeContainer::iterator            KernelEdgeIter;
00459   typedef typename EdgeContainer::const_iterator      KernelConstEdgeIter;
00460   typedef typename FaceContainer::iterator            KernelFaceIter;
00461   typedef typename FaceContainer::const_iterator      KernelConstFaceIter;
00462 
00463 
00464   KernelVertexIter vertices_begin()             { return vertices_.begin(); }
00465   KernelConstVertexIter vertices_begin() const  { return vertices_.begin(); }
00466   KernelVertexIter vertices_end()               { return vertices_.end(); }
00467   KernelConstVertexIter vertices_end() const    { return vertices_.end(); }
00468 
00469   KernelEdgeIter edges_begin()                  { return edges_.begin(); }
00470   KernelConstEdgeIter edges_begin() const       { return edges_.begin(); }
00471   KernelEdgeIter edges_end()                    { return edges_.end(); }
00472   KernelConstEdgeIter edges_end() const         { return edges_.end(); }
00473 
00474   KernelFaceIter faces_begin()                  { return faces_.begin(); }
00475   KernelConstFaceIter faces_begin() const       { return faces_.begin(); }
00476   KernelFaceIter faces_end()                    { return faces_.end(); }
00477   KernelConstFaceIter faces_end() const         { return faces_.end(); }
00478 
00479 
00480 private:
00481 
00482   VertexContainer    vertices_;
00483   EdgeContainer      edges_;
00484   FaceContainer      faces_;
00485 };
00486 
00487 
00488 //-----------------------------------------------------------------------------
00489 
00490 
00491 template <class AttribKernel, class FinalMeshItems>
00492 void
00493 ArrayKernelT<AttribKernel, FinalMeshItems>::
00494 garbage_collection(bool _v, bool _e, bool _f)
00495 {
00496   int            i, i0, i1,
00497                  nV(n_vertices()), 
00498                  nE(n_edges()), 
00499                  nH(2*n_edges()), 
00500                  nF(n_faces());
00501 
00502   std::vector<VertexHandle>    vh_map;
00503   std::vector<HalfedgeHandle>  hh_map;
00504   std::vector<FaceHandle>      fh_map;
00505 
00506   // setup handle mapping:
00507   // on 1st pos is an invalid handle, all others are hence shifted by 1
00508 
00509   vh_map.reserve(nV+1);
00510   for (i=-1; i<nV; ++i) vh_map.push_back(VertexHandle(i));
00511 
00512   hh_map.reserve(nH+1);
00513   for (i=-1; i<nH; ++i) hh_map.push_back(HalfedgeHandle(i));
00514 
00515   fh_map.reserve(nF+1);
00516   for (i=-1; i<nF; ++i) fh_map.push_back(FaceHandle(i));
00517 
00518 
00519 
00520   // remove deleted vertices
00521   if (_v && n_vertices() > 0)
00522   {
00523     i0=0;  i1=nV-1;
00524     
00525     while (1)
00526     {
00527       // find 1st deleted and last un-deleted
00528       while (!status(VertexHandle(i0)).deleted() && i0 < i1)  ++i0;
00529       while ( status(VertexHandle(i1)).deleted() && i0 < i1)  --i1;
00530       if (i0 >= i1) break;
00531 
00532       // swap
00533       std::swap(vertices_[i0], vertices_[i1]);
00534       std::swap(vh_map[i0+1],  vh_map[i1+1]);
00535       vprops_swap(i0, i1);
00536     };
00537 
00538     vertices_.resize(status(VertexHandle(i0)).deleted() ? i0 : i0+1);
00539     vprops_resize(n_vertices());
00540   }
00541 
00542 
00543   // remove deleted edges
00544   if (_e && n_edges() > 0)
00545   {
00546     i0=0;  i1=nE-1;
00547     
00548     while (1)
00549     {
00550       // find 1st deleted and last un-deleted
00551       while (!status(EdgeHandle(i0)).deleted() && i0 < i1)  ++i0;
00552       while ( status(EdgeHandle(i1)).deleted() && i0 < i1)  --i1;
00553       if (i0 >= i1) break;
00554 
00555       // swap
00556       std::swap(edges_[i0], edges_[i1]);
00557       std::swap(hh_map[2*i0+1], hh_map[2*i1+1]);
00558       std::swap(hh_map[2*i0+2], hh_map[2*i1+2]);
00559       eprops_swap(i0, i1);
00560       hprops_swap(2*i0,   2*i1);
00561       hprops_swap(2*i0+1, 2*i1+1);
00562     };
00563 
00564     edges_.resize(status(EdgeHandle(i0)).deleted() ? i0 : i0+1);
00565     eprops_resize(n_edges());
00566     hprops_resize(n_halfedges());
00567   }
00568 
00569 
00570   // remove deleted faces
00571   if (_f && n_faces() > 0)
00572   {
00573     i0=0;  i1=nF-1;
00574     
00575     while (1)
00576     {
00577       // find 1st deleted and last un-deleted
00578       while (!status(FaceHandle(i0)).deleted() && i0 < i1)  ++i0;
00579       while ( status(FaceHandle(i1)).deleted() && i0 < i1)  --i1;
00580       if (i0 >= i1) break;
00581 
00582       // swap
00583       std::swap(faces_[i0],   faces_[i1]);
00584       std::swap(fh_map[i0+1], fh_map[i1+1]);
00585       fprops_swap(i0, i1);
00586     };
00587 
00588     faces_.resize(status(FaceHandle(i0)).deleted() ? i0 : i0+1);
00589     fprops_resize(n_faces());
00590   }
00591 
00592 
00593   // update handles of vertices
00594   if (_e)
00595   {
00596     KernelVertexIter v_it(vertices_begin()), v_end(vertices_end());
00597     VertexHandle     vh;
00598 
00599     for (; v_it!=v_end; ++v_it)
00600     {
00601       vh = handle(*v_it);
00602       set_halfedge_handle(vh, hh_map[halfedge_handle(vh).idx()+1]);
00603     }
00604   }
00605 
00606 
00607   // update handles of halfedges
00608   KernelEdgeIter  e_it(edges_begin()), e_end(edges_end());
00609   HalfedgeHandle  hh;
00610 
00611   for (; e_it!=e_end; ++e_it)
00612   {
00613     hh = halfedge_handle(handle(*e_it), 0);
00614     set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()+1]);
00615     set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()+1]);
00616     set_face_handle(hh, fh_map[face_handle(hh).idx()+1]);
00617 
00618     hh = halfedge_handle(handle(*e_it), 1);
00619     set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()+1]);
00620     set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()+1]);
00621     set_face_handle(hh, fh_map[face_handle(hh).idx()+1]);
00622   }
00623 
00624 
00625   // update handles of faces
00626   if (_e)
00627   {
00628     KernelFaceIter  f_it(faces_begin()), f_end(faces_end());
00629     FaceHandle      fh;
00630 
00631     for (; f_it!=f_end; ++f_it)
00632     {
00633       fh = handle(*f_it);
00634       set_halfedge_handle(fh, hh_map[halfedge_handle(fh).idx()+1]);
00635     }
00636   }
00637 
00638 }
00639 
00640 
00641 //=============================================================================
00642 } // namespace OpenMesh
00643 //=============================================================================
00644 #endif // OPENMESH_ARRAY_KERNEL_HH defined
00645 //=============================================================================

acg pic Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .