- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# Tools/Subdivider/Uniform/Sqrt3T.hh

Go to the documentation of this file.

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