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

Sqrt3T.hh

Go to the documentation of this file.
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.13 $
00027 //   $Date: 2004/01/20 14:41:57 $
00028 //                                                                            
00029 //=============================================================================
00030 
00035 //=============================================================================
00036 //
00037 //  CLASS Sqrt3T
00038 //
00039 //=============================================================================
00040 
00041 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
00042 #define OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
00043 
00044 
00045 //== INCLUDES =================================================================
00046 
00047 #include <OpenMesh/Core/System/config.hh>
00048 #include <OpenMesh/Tools/Subdivider/Uniform/SubdividerT.hh>
00049 #if defined(_DEBUG) || defined(DEBUG)
00050 // Makes life lot easier, when playing/messing around with low-level topology
00051 // changing methods of OpenMesh
00052 #  include <OpenMesh/Tools/Utils/MeshCheckerT.hh>
00053 #  define ASSERT_CONSISTENCY( T, m ) \
00054      assert(OpenMesh::Utils::MeshCheckerT<T>(m).check())
00055 #else
00056 #  define ASSERT_CONSISTENCY( T, m )
00057 #endif
00058 // -------------------- STL
00059 #include <vector>
00060 #if defined(OM_CC_MIPS)
00061 #  include <math.h>
00062 #else
00063 #  include <cmath>
00064 #endif
00065 
00066 
00067 //== NAMESPACE ================================================================
00068 
00069 namespace OpenMesh   { // BEGIN_NS_OPENMESH
00070 namespace Subdivider { // BEGIN_NS_DECIMATER
00071 namespace Uniform    { // BEGIN_NS_DECIMATER
00072 
00073 
00074 //== CLASS DEFINITION =========================================================
00075 
00076 
00079 template <typename MeshType, typename RealType = float>
00080 class Sqrt3T : public SubdividerT< MeshType, RealType >
00081 {
00082 public:
00083 
00084   typedef RealType                                real_t;
00085   typedef MeshType                                mesh_t;
00086   typedef SubdividerT< mesh_t, real_t >           parent_t;
00087 
00088   typedef std::pair< real_t, real_t >             weight_t;
00089   typedef std::vector< std::pair<real_t,real_t> > weights_t;
00090 
00091 public:
00092 
00093 
00094   Sqrt3T(void) : parent_t(), _1over3( 1.0/3.0 ), _1over27( 1.0/27.0 )
00095   { init_weights(); }
00096 
00097   Sqrt3T(MeshType &_m) : parent_t(_m), _1over3( 1.0/3.0 ), _1over27( 1.0/27.0 )
00098   { init_weights(); }
00099 
00100   virtual ~Sqrt3T() {}
00101 
00102 
00103 public:
00104 
00105 
00106   const char *name() const { return "Uniform Sqrt3"; }
00107 
00108   
00110   void init_weights(size_t _max_valence=50)
00111   {
00112     weights_.resize(_max_valence);
00113     std::generate(weights_.begin(), weights_.end(), compute_weight());
00114   }
00115 
00116 
00117 protected:
00118 
00119 
00120   bool prepare( MeshType& _m )
00121   {
00122     _m.request_edge_status();
00123     _m.add_property( vp_pos_ );
00124     _m.add_property( ep_nv_ );
00125     _m.add_property( mp_gen_ );
00126     _m.property( mp_gen_ ) = 0;
00127 
00128     return _m.has_edge_status() && vp_pos_.is_valid() 
00129       &&   ep_nv_.is_valid() && mp_gen_.is_valid();
00130   }
00131 
00132 
00133   bool cleanup( MeshType& _m )
00134   {
00135     _m.release_edge_status();
00136     _m.remove_property( vp_pos_ );
00137     _m.remove_property( ep_nv_ );
00138     _m.add_property( mp_gen_ );
00139     return true;
00140   }
00141 
00142 
00143   bool subdivide( MeshType& _m, size_t _n )
00144   {
00145     typename MeshType::VertexIter       vit;
00146     typename MeshType::VertexVertexIter vvit;
00147     typename MeshType::EdgeIter         eit;
00148     typename MeshType::FaceIter         fit;
00149     typename MeshType::FaceVertexIter   fvit;
00150     typename MeshType::VertexHandle     vh;
00151     typename MeshType::HalfedgeHandle   heh;
00152     typename MeshType::Point            pos(0,0,0), zero(0,0,0);
00153     size_t                            &gen = _m.property( mp_gen_ );
00154 
00155     for (size_t l=0; l<_n; ++l)
00156     {
00157       // tag existing edges
00158       for (eit=_m.edges_begin(); eit != _m.edges_end();++eit)
00159       {
00160         _m.status( eit ).set_tagged( true );
00161         if ( (gen%2) && _m.is_boundary(eit) )
00162           compute_new_boundary_points( _m, eit ); // *) creates new vertices
00163       }
00164 
00165       // do relaxation of old vertices, but store new pos in property vp_pos_
00166 
00167       for (vit=_m.vertices_begin(); vit!=_m.vertices_end(); ++vit)
00168       {
00169         if ( _m.is_boundary(vit) )
00170         {
00171           if ( gen%2 )
00172           {
00173             heh  = _m.halfedge_handle(vit);
00174             if (heh.is_valid()) // skip isolated newly inserted vertices *)
00175             {
00176               typename OpenMesh::HalfedgeHandle 
00177                 prev_heh = _m.prev_halfedge_handle(heh);
00178 
00179               assert( _m.is_boundary(heh     ) );
00180               assert( _m.is_boundary(prev_heh) );
00181             
00182               pos  = _m.point(_m.to_vertex_handle(heh));
00183               pos += _m.point(_m.from_vertex_handle(prev_heh));
00184               pos *= real_t(4.0);
00185 
00186               pos += real_t(19.0) * _m.point( vit );
00187               pos *= _1over27;
00188 
00189               _m.property( vp_pos_, vit ) = pos;
00190             }
00191           }
00192           else
00193             _m.property( vp_pos_, vit ) = _m.point( vit );
00194         }
00195         else
00196         {
00197           size_t valence=0;
00198 
00199           pos = zero;
00200           for ( vvit = _m.vv_iter(vit); vvit; ++vvit)
00201           {
00202             pos += _m.point( vvit );
00203             ++valence;
00204           }
00205           pos *= weights_[ valence ].second;
00206           pos += weights_[ valence ].first * _m.point(vit);
00207           _m.property( vp_pos_, vit ) =  pos;
00208         }
00209       }   
00210 
00211       // insert new vertices, but store pos in vp_pos_
00212       typename MeshType::FaceIter fend = _m.faces_end();
00213       for (fit = _m.faces_begin();fit != fend; ++fit)
00214       {
00215         if ( (gen%2) && _m.is_boundary(fit))
00216         {
00217           boundary_split( _m, fit );
00218         }
00219         else
00220         {
00221           fvit = _m.fv_iter( fit );        
00222           pos  = _m.point(  fvit);
00223           pos += _m.point(++fvit);
00224           pos += _m.point(++fvit);
00225           pos *= _1over3;
00226           vh   = _m.add_vertex( zero );
00227           _m.property( vp_pos_, vh ) = pos;
00228           _m.split( fit, vh );
00229         }
00230       }
00231 
00232       // commit new positions (now iterating over all vertices)
00233       for (vit=_m.vertices_begin();vit != _m.vertices_end(); ++vit)
00234         _m.set_point(vit, _m.property( vp_pos_, vit ) );
00235       
00236       // flip old edges
00237       for (eit=_m.edges_begin(); eit != _m.edges_end(); ++eit)
00238         if ( _m.status( eit ).tagged() && !_m.is_boundary( eit ) )
00239           _m.flip(eit);
00240 
00241       // Now we have an consistent mesh!
00242       ASSERT_CONSISTENCY( MeshType, _m );
00243 
00244       // increase generation by one
00245       ++gen;
00246     }
00247     return true;
00248   }
00249 
00250 private:
00251 
00254   struct compute_weight 
00255   {
00256     compute_weight() : valence(-1) { }    
00257     weight_t operator() (void) 
00258     { 
00259 #if !defined(OM_CC_MIPS)
00260       using std::cos;
00261 #endif
00262       if (++valence)
00263       {
00264         real_t alpha = (4.0-2.0*cos(2.0*M_PI / (double)valence))/9.0;
00265         return weight_t( real_t(1)-alpha, alpha/real_t(valence) );
00266       }
00267       return weight_t(0.0, 0.0);
00268     }    
00269     int valence;
00270   };
00271 
00272 private:
00273 
00274   // Pre-compute location of new boundary points for odd generations
00275   // and store them in the edge property ep_nv_;
00276   void compute_new_boundary_points( MeshType& _m, 
00277                                     const typename MeshType::EdgeHandle& _eh)
00278   {
00279     assert( _m.is_boundary(_eh) );
00280 
00281     typename MeshType::HalfedgeHandle heh;
00282     typename MeshType::VertexHandle   vh1, vh2, vh3, vh4, vhl, vhr;
00283     typename MeshType::Point          zero(0,0,0), P1, P2, P3, P4;
00284 
00285     /*
00286     //       *---------*---------*
00287     //      / \       / \       / \
00288     //     /   \     /   \     /   \
00289     //    /     \   /     \   /     \
00290     //   /       \ /       \ /       \
00291     //  *---------*--#---#--*---------*
00292     //                
00293     //  ^         ^  ^   ^  ^         ^
00294     //  P1        P2 pl  pr P3        P4
00295     */
00296     // get halfedge pointing from P3 to P2 (outer boundary halfedge)
00297 
00298     heh = _m.halfedge_handle(_eh, 
00299                              _m.is_boundary(_m.halfedge_handle(_eh,1)));
00300     
00301     assert( _m.is_boundary( _m.next_halfedge_handle( heh ) ) );
00302     assert( _m.is_boundary( _m.prev_halfedge_handle( heh ) ) );
00303 
00304     vh1 = _m.to_vertex_handle( _m.next_halfedge_handle( heh ) );
00305     vh2 = _m.to_vertex_handle( heh );
00306     vh3 = _m.from_vertex_handle( heh );
00307     vh4 = _m.from_vertex_handle( _m.prev_halfedge_handle( heh ));
00308     
00309     P1  = _m.point(vh1);
00310     P2  = _m.point(vh2);
00311     P3  = _m.point(vh3);
00312     P4  = _m.point(vh4);
00313     
00314     vhl = _m.add_vertex(zero);
00315     vhr = _m.add_vertex(zero);
00316 
00317     _m.property(vp_pos_, vhl ) = (P1 + 16.0f*P2 + 10.0f*P3) * _1over27;
00318     _m.property(vp_pos_, vhr ) = (10.0f*P2 + 16.0f*P3 + P4) * _1over27;
00319     _m.property(ep_nv_, _eh).first  = vhl;
00320     _m.property(ep_nv_, _eh).second = vhr; 
00321   }
00322 
00323 
00324   void boundary_split( MeshType& _m, const typename MeshType::FaceHandle& _fh )
00325   {
00326     assert( _m.is_boundary(_fh) );
00327 
00328     typename MeshType::VertexHandle     vhl, vhr;
00329     typename MeshType::FaceEdgeIter     fe_it;
00330     typename MeshType::HalfedgeHandle   heh;
00331 
00332     // find boundary edge
00333     for( fe_it=_m.fe_iter( _fh ); fe_it && !_m.is_boundary( fe_it ); ++fe_it );
00334 
00335     // use precomputed, already inserted but not linked vertices
00336     vhl = _m.property(ep_nv_, fe_it).first;
00337     vhr = _m.property(ep_nv_, fe_it).second;
00338 
00339     /*
00340     //       *---------*---------*
00341     //      / \       / \       / \
00342     //     /   \     /   \     /   \
00343     //    /     \   /     \   /     \
00344     //   /       \ /       \ /       \
00345     //  *---------*--#---#--*---------*
00346     //                
00347     //  ^         ^  ^   ^  ^         ^
00348     //  P1        P2 pl  pr P3        P4
00349     */
00350     // get halfedge pointing from P2 to P3 (inner boundary halfedge)
00351 
00352     heh = _m.halfedge_handle(fe_it, 
00353                              _m.is_boundary(_m.halfedge_handle(fe_it,0)));
00354 
00355     typename MeshType::HalfedgeHandle pl_P3;
00356 
00357     // split P2->P3 (heh) in P2->pl (heh) and pl->P3
00358     boundary_split( _m, heh, vhl );         // split edge
00359     pl_P3 = _m.next_halfedge_handle( heh ); // store next halfedge handle
00360     boundary_split( _m, heh );              // split face
00361 
00362     // split pl->P3 in pl->pr and pr->P3
00363     boundary_split( _m, pl_P3, vhr );
00364     boundary_split( _m, pl_P3 );
00365 
00366     assert( _m.is_boundary( vhl ) && _m.halfedge_handle(vhl).is_valid() );
00367     assert( _m.is_boundary( vhr ) && _m.halfedge_handle(vhr).is_valid() );
00368   }
00369 
00370   void boundary_split(MeshType& _m, 
00371                       const typename MeshType::HalfedgeHandle& _heh,
00372                       const typename MeshType::VertexHandle& _vh)
00373   {
00374     assert( _m.is_boundary( _m.edge_handle(_heh) ) );
00375 
00376     typename MeshType::HalfedgeHandle 
00377       heh(_heh),
00378       opp_heh( _m.opposite_halfedge_handle(_heh) ),
00379       new_heh, opp_new_heh;
00380     typename MeshType::VertexHandle   to_vh(_m.to_vertex_handle(heh));
00381     typename MeshType::HalfedgeHandle t_heh;
00382     
00383     /*
00384      *            P5
00385      *             *
00386      *            /|\
00387      *           /   \
00388      *          /     \
00389      *         /       \
00390      *        /         \
00391      *       /_ heh  new \
00392      *      *-----\*-----\*\-----*
00393      *             ^      ^ t_heh
00394      *            _vh     to_vh
00395      *
00396      *     P1     P2     P3     P4
00397      */
00398     // Re-Setting Handles
00399     
00400     // find halfedge point from P4 to P3
00401     for(t_heh = heh; 
00402         _m.next_halfedge_handle(t_heh) != opp_heh; 
00403         t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
00404     {}
00405     
00406     assert( _m.is_boundary( t_heh ) );
00407 
00408     new_heh     = _m.new_edge( _vh, to_vh );
00409     opp_new_heh = _m.opposite_halfedge_handle(new_heh);
00410 
00411     // update halfedge connectivity
00412 
00413     _m.set_next_halfedge_handle(t_heh,   opp_new_heh); // P4-P3 -> P3-P2
00414     // P2-P3 -> P3-P5
00415     _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));    
00416     _m.set_next_halfedge_handle(heh,         new_heh); // P1-P2 -> P2-P3
00417     _m.set_next_halfedge_handle(opp_new_heh, opp_heh); // P3-P2 -> P2-P1
00418 
00419     // both opposite halfedges point to same face
00420     _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
00421 
00422     // let heh finally point to new inserted vertex
00423     _m.set_vertex_handle(heh, _vh); 
00424 
00425     // let heh and new_heh point to same face
00426     _m.set_face_handle(new_heh, _m.face_handle(heh));
00427 
00428     // let opp_new_heh be the new outgoing halfedge for to_vh 
00429     // (replaces for opp_heh)
00430     _m.set_halfedge_handle( to_vh, opp_new_heh );
00431 
00432     // let opp_heh be the outgoing halfedge for _vh
00433     _m.set_halfedge_handle( _vh, opp_heh );
00434   }
00435 
00436   void boundary_split( MeshType& _m, 
00437                        const typename MeshType::HalfedgeHandle& _heh)
00438   {
00439     assert( _m.is_boundary( _m.opposite_halfedge_handle( _heh ) ) );
00440 
00441     typename MeshType::HalfedgeHandle 
00442       heh(_heh),
00443       n_heh(_m.next_halfedge_handle(heh));
00444 
00445     typename MeshType::VertexHandle   
00446       to_vh(_m.to_vertex_handle(heh));
00447 
00448     typename MeshType::HalfedgeHandle 
00449       heh2(_m.new_edge(to_vh,
00450                        _m.to_vertex_handle(_m.next_halfedge_handle(n_heh)))),
00451       heh3(_m.opposite_halfedge_handle(heh2));
00452 
00453     typename MeshType::FaceHandle
00454       new_fh(_m.new_face()),
00455       fh(_m.face_handle(heh));
00456     
00457     // Relink (half)edges    
00458 
00459 #define set_next_heh set_next_halfedge_handle
00460 #define next_heh next_halfedge_handle
00461 
00462     _m.set_face_handle(heh,  new_fh);
00463     _m.set_face_handle(heh2, new_fh);
00464     _m.set_next_heh(heh2, _m.next_heh(_m.next_heh(n_heh)));
00465     _m.set_next_heh(heh,  heh2);
00466     _m.set_face_handle( _m.next_heh(heh2), new_fh);
00467 
00468     // _m.set_face_handle( _m.next_heh(_m.next_heh(heh2)), new_fh);
00469 
00470     _m.set_next_heh(heh3,                           n_heh);
00471     _m.set_next_heh(_m.next_halfedge_handle(n_heh), heh3);
00472     _m.set_face_handle(heh3,  fh);
00473     // _m.set_face_handle(n_heh, fh);
00474 
00475     _m.set_halfedge_handle(    fh, n_heh);
00476     _m.set_halfedge_handle(new_fh, heh);
00477 
00478 #undef set_next_halfedge_handle
00479 #undef next_halfedge_handle
00480 
00481   }
00482 
00483 private:
00484 
00485   weights_t     weights_;
00486   OpenMesh::VPropHandleT< typename MeshType::Point >                    vp_pos_;
00487   OpenMesh::EPropHandleT< std::pair< typename MeshType::VertexHandle,
00488                                      typename MeshType::VertexHandle> > ep_nv_;
00489   OpenMesh::MPropHandleT< size_t >                                      mp_gen_;
00490 
00491   const real_t _1over3;
00492   const real_t _1over27;
00493 };
00494 
00495 
00496 //=============================================================================
00497 } // END_NS_UNIFORM
00498 } // END_NS_SUBDIVIDER
00499 } // END_NS_OPENMESH
00500 //=============================================================================
00501 #endif // OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
00502 //=============================================================================

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