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

LoopT.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.16 $
00027 //   $Date: 2004/01/20 14:41:57 $
00028 //                                                                            
00029 //=============================================================================
00030 
00035 //=============================================================================
00036 //
00037 //  CLASS LoopT
00038 //
00039 //=============================================================================
00040 
00041 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_LOOPT_HH
00042 #define OPENMESH_SUBDIVIDER_UNIFORM_LOOPT_HH
00043 
00044 
00045 //== INCLUDES =================================================================
00046 
00047 #include <OpenMesh/Core/System/config.hh>
00048 #include <OpenMesh/Tools/Subdivider/Uniform/SubdividerT.hh>
00049 #include <OpenMesh/Core/Utils/vector_cast.hh>
00050 // -------------------- STL
00051 #include <vector>
00052 #if defined(OM_CC_MIPS)
00053 #  include <math.h>
00054 #else
00055 #  include <cmath>
00056 #endif
00057 
00058 
00059 //== NAMESPACE ================================================================
00060 
00061 namespace OpenMesh   { // BEGIN_NS_OPENMESH
00062 namespace Subdivider { // BEGIN_NS_DECIMATER
00063 namespace Uniform    { // BEGIN_NS_DECIMATER
00064 
00065 
00066 //== CLASS DEFINITION =========================================================
00067 
00070 template <typename MeshType, typename RealType = float>
00071 class LoopT : public SubdividerT<MeshType, RealType>
00072 {
00073 public:
00074 
00075   typedef RealType                                real_t;
00076   typedef MeshType                                mesh_t;
00077   typedef SubdividerT< mesh_t, real_t >           parent_t;
00078 
00079   typedef std::pair< real_t, real_t >             weight_t;
00080   typedef std::vector< std::pair<real_t,real_t> > weights_t;
00081 
00082 public:
00083 
00084 
00085   LoopT(void) : parent_t(), _1over8( 1.0/8.0 ), _3over8( 3.0/8.0 )
00086   { init_weights(); }
00087 
00088 
00089   LoopT( mesh_t& _m ) : parent_t(_m), _1over8( 1.0/8.0 ), _3over8( 3.0/8.0 )
00090   { init_weights(); }
00091 
00092 
00093   ~LoopT() {}
00094 
00095 
00096 public:
00097 
00098 
00099   const char *name() const { return "Uniform Loop"; }
00100 
00101 
00103   void init_weights(size_t _max_valence=50)
00104   {
00105     weights_.resize(_max_valence);
00106     std::generate(weights_.begin(), weights_.end(), compute_weight());
00107   }
00108 
00109 
00110 protected:
00111 
00112   
00113   bool prepare( mesh_t& _m )
00114   {
00115     _m.add_property( vp_pos_ );
00116     _m.add_property( ep_pos_ );
00117     return true;
00118   }
00119   
00120 
00121   bool cleanup( mesh_t& _m )
00122   {
00123     _m.remove_property( vp_pos_ );
00124     _m.remove_property( ep_pos_ );
00125     return true;
00126   }
00127 
00128 
00129   bool subdivide( mesh_t& _m, size_t _n)
00130   {
00131     typename mesh_t::FaceIter   fit, f_end;
00132     typename mesh_t::EdgeIter   eit, e_end;
00133     typename mesh_t::VertexIter vit;
00134     
00135     // Do _n subdivisions
00136     for (size_t i=0; i < _n; ++i) 
00137     {
00138       // compute new positions for old vertices
00139       for ( vit  = _m.vertices_begin();
00140             vit != _m.vertices_end(); ++vit)
00141         smooth( _m, vit.handle() );
00142       
00143       
00144       // Compute position for new vertices and store them in the edge property
00145       for (eit=_m.edges_begin(); eit != _m.edges_end(); ++eit)
00146         compute_midpoint( _m, eit.handle() );
00147       
00148       
00149       // Split each edge at midpoint and store precomputed positions (stored in
00150       // edge property ep_pos_) in the vertex property vp_pos_;
00151       
00152       // Attention! Creating new edges, hence make sure the loop ends correctly.
00153       e_end = _m.edges_end(); 
00154       for (eit=_m.edges_begin(); eit != e_end; ++eit)
00155         split_edge(_m, eit.handle() );
00156       
00157       
00158       // Commit changes in topology and reconsitute consistency
00159       
00160       // Attention! Creating new faces, hence make sure the loop ends correctly.
00161       f_end   = _m.faces_end();
00162       for (fit = _m.faces_begin(); fit != f_end; ++fit) 
00163         split_face(_m, fit.handle() );
00164       
00165       
00166       // Commit changes in geometry
00167       for ( vit  = _m.vertices_begin();
00168             vit != _m.vertices_end(); ++vit)
00169         _m.set_point(vit, _m.property( vp_pos_, vit ) );
00170       
00171 #if defined(_DEBUG) || defined(DEBUG)
00172       // Now we have an consistent mesh!
00173       assert( OpenMesh::Utils::MeshCheckerT<mesh_t>(_m).check() );
00174 #endif
00175     }
00176 
00177     return true;
00178   }
00179 
00180 private:
00181 
00184   struct compute_weight 
00185   {
00186     compute_weight() : valence(-1) { }    
00187     weight_t operator() (void) 
00188     { 
00189 #if !defined(OM_CC_MIPS)
00190       using std::cos;
00191 #endif
00192       //              1
00193       // alpha(n) = ---- * (40 - ( 3 + 2 cos( 2 Pi / n ) )² )
00194       //             64
00195       
00196       if (++valence)
00197       {
00198         double   inv_v  = 1.0/double(valence);
00199         double   t      = (3.0 + 2.0 * cos( 2.0 * M_PI * inv_v) );
00200         double   alpha  = (40.0 - t * t)/64.0;
00201         
00202         return weight_t( 1.0-alpha, inv_v*alpha);
00203       }                
00204       return weight_t(0.0, 0.0);
00205     }
00206     int valence;
00207   };
00208 
00209 private: // topological modifiers
00210 
00211   void split_face(mesh_t& _m, const typename mesh_t::FaceHandle& _fh)
00212   {
00213     typename mesh_t::HalfedgeHandle 
00214       heh1(_m.halfedge_handle(_fh)),
00215       heh2(_m.next_halfedge_handle(_m.next_halfedge_handle(heh1))),
00216       heh3(_m.next_halfedge_handle(_m.next_halfedge_handle(heh2)));
00217 
00218     // Cutting off every corner of the 6_gon
00219     corner_cutting( _m, heh1 );
00220     corner_cutting( _m, heh2 );
00221     corner_cutting( _m, heh3 );
00222   }
00223 
00224 
00225   void corner_cutting(mesh_t& _m, const typename mesh_t::HalfedgeHandle& _he)
00226   {
00227     // Define Halfedge Handles
00228     typename mesh_t::HalfedgeHandle 
00229       heh1(_he),
00230       heh5(heh1),
00231       heh6(_m.next_halfedge_handle(heh1));
00232 
00233     // Cycle around the polygon to find correct Halfedge
00234     for (; _m.next_halfedge_handle(_m.next_halfedge_handle(heh5)) != heh1; 
00235          heh5 = _m.next_halfedge_handle(heh5))
00236     {}
00237 
00238     typename mesh_t::VertexHandle
00239       vh1 = _m.to_vertex_handle(heh1),
00240       vh2 = _m.to_vertex_handle(heh5);
00241 
00242     typename mesh_t::HalfedgeHandle 
00243       heh2(_m.next_halfedge_handle(heh5)),
00244       heh3(_m.new_edge( vh1, vh2)),
00245       heh4(_m.opposite_halfedge_handle(heh3));
00246 
00247     /* Intermediate result
00248      *
00249      *            *
00250      *         5 /|\
00251      *          /_  \
00252      *    vh2> *     *
00253      *        /|\3   |\
00254      *       /_  \|4   \
00255      *      *----\*----\*
00256      *          1 ^   6
00257      *            vh1 (adjust_outgoing halfedge!)
00258      */
00259 
00260     // Old and new Face
00261     typename mesh_t::FaceHandle     fh_old(_m.face_handle(heh6));
00262     typename mesh_t::FaceHandle     fh_new(_m.new_face());
00263 
00264 
00265     // Re-Set Handles around old Face
00266     _m.set_next_halfedge_handle(heh4, heh6);
00267     _m.set_next_halfedge_handle(heh5, heh4);
00268 
00269     _m.set_face_handle(heh4, fh_old);
00270     _m.set_face_handle(heh5, fh_old);
00271     _m.set_face_handle(heh6, fh_old);
00272     _m.set_halfedge_handle(fh_old, heh4);
00273 
00274     // Re-Set Handles around new Face
00275     _m.set_next_halfedge_handle(heh1, heh3);
00276     _m.set_next_halfedge_handle(heh3, heh2);
00277 
00278     _m.set_face_handle(heh1, fh_new);
00279     _m.set_face_handle(heh2, fh_new);
00280     _m.set_face_handle(heh3, fh_new);
00281 
00282     _m.set_halfedge_handle(fh_new, heh1);
00283   }
00284 
00285 
00286   void split_edge(mesh_t& _m, const typename mesh_t::EdgeHandle& _eh)
00287   {
00288     typename mesh_t::HalfedgeHandle 
00289       heh     = _m.halfedge_handle(_eh, 0),
00290       opp_heh = _m.halfedge_handle(_eh, 1);
00291 
00292     typename mesh_t::HalfedgeHandle new_heh, opp_new_heh, t_heh;
00293     typename mesh_t::VertexHandle   vh;
00294     typename mesh_t::VertexHandle   vh1(_m.to_vertex_handle(heh));
00295     typename mesh_t::Point          zero(0,0,0);
00296 
00297     // new vertex
00298     vh                = _m.new_vertex( zero );
00299 
00300     // memorize position, will be set later
00301     _m.property( vp_pos_, vh ) = _m.property( ep_pos_, _eh );
00302 
00303     
00304     // Re-link mesh entities
00305     if (_m.is_boundary(_eh)) 
00306     {
00307       for (t_heh = heh; 
00308            _m.next_halfedge_handle(t_heh) != opp_heh; 
00309            t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh))) 
00310       {}
00311     } 
00312     else 
00313     {
00314       for (t_heh = _m.next_halfedge_handle(opp_heh); 
00315            _m.next_halfedge_handle(t_heh) != opp_heh; 
00316            t_heh = _m.next_halfedge_handle(t_heh) ) 
00317       {}
00318     }
00319 
00320     new_heh     = _m.new_edge(vh, vh1);
00321     opp_new_heh = _m.opposite_halfedge_handle(new_heh);
00322 
00323     _m.set_next_halfedge_handle(t_heh, opp_new_heh);
00324     _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
00325     _m.set_next_halfedge_handle(heh, new_heh);
00326     _m.set_next_halfedge_handle(opp_new_heh, opp_heh);
00327 
00328     if (_m.face_handle(opp_heh).is_valid()) 
00329     {
00330       _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
00331       _m.set_halfedge_handle(_m.face_handle(opp_new_heh), opp_new_heh);
00332     }
00333 
00334     _m.set_vertex_handle( heh, vh ); 
00335     _m.set_face_handle( new_heh, _m.face_handle(heh) );
00336     _m.set_halfedge_handle( vh, new_heh);
00337     _m.set_halfedge_handle( _m.face_handle(heh), heh );
00338     _m.set_halfedge_handle( vh1, opp_new_heh );
00339 
00340     // Never forget this, when playing with the topology
00341     _m.adjust_outgoing_halfedge( vh );
00342     _m.adjust_outgoing_halfedge( vh1 );
00343   }
00344 
00345 private: // geometry helper
00346 
00347   void compute_midpoint(mesh_t& _m, const typename mesh_t::EdgeHandle& _eh) 
00348   {
00349 #define V( X ) vector_cast< typename mesh_t::Normal >( X )
00350     typename mesh_t::HalfedgeHandle heh, opp_heh;
00351 
00352     heh      = _m.halfedge_handle( _eh, 0);
00353     opp_heh  = _m.halfedge_handle( _eh, 1);
00354 
00355     typename mesh_t::Point          
00356       pos(_m.point(_m.to_vertex_handle(heh)));
00357 
00358     pos += V( _m.point(_m.to_vertex_handle(opp_heh)) );
00359 
00360     // boundary edge: just average vertex positions
00361     if (_m.is_boundary(_eh) )
00362     {
00363       pos *= 0.5;
00364     }
00365     else // inner edge: add neighbouring Vertices to sum
00366     {
00367       pos *= real_t(3.0);
00368       pos += V(_m.point(_m.to_vertex_handle(_m.next_halfedge_handle(heh))));
00369       pos += V(_m.point(_m.to_vertex_handle(_m.next_halfedge_handle(opp_heh))));
00370       pos *= _1over8;
00371     } 
00372     _m.property( ep_pos_, _eh ) = pos;
00373 #undef V
00374   }
00375 
00376 
00377   void smooth(mesh_t& _m, const typename mesh_t::VertexHandle& _vh)
00378   {
00379     typename mesh_t::Point            pos(0.0,0.0,0.0);
00380 
00381     if (_m.is_boundary(_vh)) // if boundary: Point 1-6-1
00382     {
00383       typename mesh_t::HalfedgeHandle heh, prev_heh;
00384       heh      = _m.halfedge_handle( _vh );
00385 
00386       if ( heh.is_valid() )
00387       {
00388         assert( _m.is_boundary( _m.edge_handle( heh ) ) ); 
00389 
00390         prev_heh = _m.prev_halfedge_handle( heh );        
00391         
00392         typename mesh_t::VertexHandle 
00393           to_vh   = _m.to_vertex_handle( heh ), 
00394           from_vh = _m.from_vertex_handle( prev_heh );
00395 
00396         // ( v_l + 6 v + v_r ) / 8
00397         pos  = _m.point( _vh );
00398         pos *= real_t(6.0);        
00399         pos += vector_cast< typename mesh_t::Normal >( _m.point( to_vh ) );
00400         pos += vector_cast< typename mesh_t::Normal >( _m.point( from_vh ) );
00401         pos *= _1over8;
00402 
00403       }
00404       else
00405         return;
00406     } 
00407     else // inner vertex: (1-a) * p + a/n * Sum q, q in one-ring of p
00408     {
00409       typedef typename mesh_t::Normal   Vec;
00410       typename mesh_t::VertexVertexIter vvit;
00411       size_t                            valence(0);
00412     
00413       // Calculate Valence and sum up neighbour points
00414       for (vvit=_m.vv_iter(_vh); vvit; ++vvit) {
00415         ++valence;
00416         pos += vector_cast< Vec >( _m.point(vvit) );
00417       }
00418       pos *= weights_[valence].second; // alpha(n)/n * Sum q, q in one-ring of p
00419       pos += weights_[valence].first 
00420            * vector_cast<Vec>(_m.point(_vh)); // + (1-a)*p
00421     }
00422 
00423     _m.property( vp_pos_, _vh ) = pos;      
00424   }
00425 
00426 private: // data
00427 
00428   OpenMesh::VPropHandleT< typename mesh_t::Point > vp_pos_;
00429   OpenMesh::EPropHandleT< typename mesh_t::Point > ep_pos_;
00430 
00431   weights_t     weights_;
00432 
00433   const real_t _1over8;
00434   const real_t _3over8;
00435 
00436 };
00437 
00438 
00439 //=============================================================================
00440 } // END_NS_UNIFORM
00441 } // END_NS_SUBDIVIDER
00442 } // END_NS_OPENMESH
00443 //=============================================================================
00444 #endif // OPENMESH_SUBDIVIDER_UNIFORM_COMPOSITELOOPT_HH defined
00445 //=============================================================================

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