00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00035
00036
00037
00038
00039
00040
00041 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
00042 #define OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
00043
00044
00045
00046
00047 #include <OpenMesh/Core/System/config.hh>
00048 #include <OpenMesh/Tools/Subdivider/Uniform/SubdividerT.hh>
00049 #if defined(_DEBUG) || defined(DEBUG)
00050
00051
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
00059 #include <vector>
00060 #if defined(OM_CC_MIPS)
00061 # include <math.h>
00062 #else
00063 # include <cmath>
00064 #endif
00065
00066
00067
00068
00069 namespace OpenMesh {
00070 namespace Subdivider {
00071 namespace Uniform {
00072
00073
00074
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
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 );
00163 }
00164
00165
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())
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
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
00233 for (vit=_m.vertices_begin();vit != _m.vertices_end(); ++vit)
00234 _m.set_point(vit, _m.property( vp_pos_, vit ) );
00235
00236
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
00242 ASSERT_CONSISTENCY( MeshType, _m );
00243
00244
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
00275
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
00295
00296
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
00333 for( fe_it=_m.fe_iter( _fh ); fe_it && !_m.is_boundary( fe_it ); ++fe_it );
00334
00335
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
00349
00350
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
00358 boundary_split( _m, heh, vhl );
00359 pl_P3 = _m.next_halfedge_handle( heh );
00360 boundary_split( _m, heh );
00361
00362
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
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
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
00412
00413 _m.set_next_halfedge_handle(t_heh, opp_new_heh);
00414
00415 _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
00416 _m.set_next_halfedge_handle(heh, new_heh);
00417 _m.set_next_halfedge_handle(opp_new_heh, opp_heh);
00418
00419
00420 _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
00421
00422
00423 _m.set_vertex_handle(heh, _vh);
00424
00425
00426 _m.set_face_handle(new_heh, _m.face_handle(heh));
00427
00428
00429
00430 _m.set_halfedge_handle( to_vh, opp_new_heh );
00431
00432
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
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
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
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 }
00498 }
00499 }
00500
00501 #endif // OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
00502