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

- File List
- File Members

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