65 #ifndef SP_MODIFIED_BUTTERFLY_H 66 #define SP_MODIFIED_BUTTERFLY_H 69 #include <OpenMesh/Core/Utils/vector_cast.hh> 70 #include <OpenMesh/Core/Utils/Property.hh> 73 #if defined(OM_CC_MIPS) 83 namespace Subdivider {
98 template <
typename MeshType,
typename RealType =
float>
103 typedef RealType real_t;
104 typedef MeshType mesh_t;
107 typedef std::vector< std::vector<real_t> > weights_t;
108 typedef std::vector<real_t> weight_t;
127 const char *
name()
const {
return "Uniform Spectral"; }
133 weights.resize(_max_valence);
136 weights[3].resize(4);
137 weights[3][0] = real_t(5.0)/12;
138 weights[3][1] = real_t(-1.0)/12;
139 weights[3][2] = real_t(-1.0)/12;
140 weights[3][3] = real_t(3.0)/4;
142 weights[4].resize(5);
143 weights[4][0] = real_t(3.0)/8;
145 weights[4][2] = real_t(-1.0)/8;
147 weights[4][4] = real_t(3.0)/4;
149 for(
unsigned int K = 5; K<_max_valence; ++K)
151 weights[K].resize(K+1);
153 real_t invK = 1.0/real_t(K);
155 for(
unsigned int j=0; j<K; ++j)
157 weights[K][j] = (0.25 + cos(2.0*M_PI*j*invK) + 0.5*cos(4.0*M_PI*j*invK))*invK;
158 sum += weights[K][j];
160 weights[K][K] = (real_t)1.0 - sum;
170 _m.add_property( vp_pos_ );
171 _m.add_property( ep_pos_ );
178 _m.remove_property( vp_pos_ );
179 _m.remove_property( ep_pos_ );
184 bool subdivide( MeshType& _m,
size_t _n ,
const bool _update_points =
true)
189 typename mesh_t::FaceIter fit, f_end;
190 typename mesh_t::EdgeIter eit, e_end;
191 typename mesh_t::VertexIter vit;
194 for (
size_t i=0; i < _n; ++i)
198 typename mesh_t::VertexIter initialVerticesEnd = _m.vertices_end();
199 for ( vit = _m.vertices_begin(); vit != initialVerticesEnd; ++vit)
200 _m.property( vp_pos_, *vit ) = _m.point(*vit);
203 for (eit=_m.edges_begin(); eit != _m.edges_end(); ++eit)
204 compute_midpoint( _m, *eit );
211 e_end = _m.edges_end();
212 for (eit=_m.edges_begin(); eit != e_end; ++eit)
213 split_edge(_m, *eit );
219 f_end = _m.faces_end();
220 for (fit = _m.faces_begin(); fit != f_end; ++fit)
221 split_face(_m, *fit );
225 for ( vit = _m.vertices_begin();
226 vit != _m.vertices_end(); ++vit)
227 _m.set_point(*vit, _m.property( vp_pos_, *vit ) );
229 #if defined(_DEBUG) || defined(DEBUG) 240 void split_face(mesh_t& _m,
const typename mesh_t::FaceHandle& _fh)
242 typename mesh_t::HalfedgeHandle
243 heh1(_m.halfedge_handle(_fh)),
244 heh2(_m.next_halfedge_handle(_m.next_halfedge_handle(heh1))),
245 heh3(_m.next_halfedge_handle(_m.next_halfedge_handle(heh2)));
248 corner_cutting( _m, heh1 );
249 corner_cutting( _m, heh2 );
250 corner_cutting( _m, heh3 );
254 void corner_cutting(mesh_t& _m,
const typename mesh_t::HalfedgeHandle& _he)
257 typename mesh_t::HalfedgeHandle
260 heh6(_m.next_halfedge_handle(heh1));
263 for (; _m.next_halfedge_handle(_m.next_halfedge_handle(heh5)) != heh1;
264 heh5 = _m.next_halfedge_handle(heh5))
268 vh1 = _m.to_vertex_handle(heh1),
269 vh2 = _m.to_vertex_handle(heh5);
271 typename mesh_t::HalfedgeHandle
272 heh2(_m.next_halfedge_handle(heh5)),
273 heh3(_m.new_edge( vh1, vh2)),
274 heh4(_m.opposite_halfedge_handle(heh3));
290 typename mesh_t::FaceHandle fh_old(_m.face_handle(heh6));
291 typename mesh_t::FaceHandle fh_new(_m.new_face());
295 _m.set_next_halfedge_handle(heh4, heh6);
296 _m.set_next_halfedge_handle(heh5, heh4);
298 _m.set_face_handle(heh4, fh_old);
299 _m.set_face_handle(heh5, fh_old);
300 _m.set_face_handle(heh6, fh_old);
301 _m.set_halfedge_handle(fh_old, heh4);
304 _m.set_next_halfedge_handle(heh1, heh3);
305 _m.set_next_halfedge_handle(heh3, heh2);
307 _m.set_face_handle(heh1, fh_new);
308 _m.set_face_handle(heh2, fh_new);
309 _m.set_face_handle(heh3, fh_new);
311 _m.set_halfedge_handle(fh_new, heh1);
315 void split_edge(mesh_t& _m,
const typename mesh_t::EdgeHandle& _eh)
317 typename mesh_t::HalfedgeHandle
318 heh = _m.halfedge_handle(_eh, 0),
319 opp_heh = _m.halfedge_handle(_eh, 1);
321 typename mesh_t::HalfedgeHandle new_heh, opp_new_heh, t_heh;
327 vh = _m.new_vertex( zero );
330 _m.property( vp_pos_, vh ) = _m.property( ep_pos_, _eh );
334 if (_m.is_boundary(_eh))
337 _m.next_halfedge_handle(t_heh) != opp_heh;
338 t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
343 for (t_heh = _m.next_halfedge_handle(opp_heh);
344 _m.next_halfedge_handle(t_heh) != opp_heh;
345 t_heh = _m.next_halfedge_handle(t_heh) )
349 new_heh = _m.new_edge(vh, vh1);
350 opp_new_heh = _m.opposite_halfedge_handle(new_heh);
351 _m.set_vertex_handle( heh, vh );
353 _m.set_next_halfedge_handle(t_heh, opp_new_heh);
354 _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
355 _m.set_next_halfedge_handle(heh, new_heh);
356 _m.set_next_halfedge_handle(opp_new_heh, opp_heh);
358 if (_m.face_handle(opp_heh).is_valid())
360 _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
361 _m.set_halfedge_handle(_m.face_handle(opp_new_heh), opp_new_heh);
364 _m.set_face_handle( new_heh, _m.face_handle(heh) );
365 _m.set_halfedge_handle( vh, new_heh);
366 _m.set_halfedge_handle( _m.face_handle(heh), heh );
367 _m.set_halfedge_handle( vh1, opp_new_heh );
370 _m.adjust_outgoing_halfedge( vh );
371 _m.adjust_outgoing_halfedge( vh1 );
376 void compute_midpoint(mesh_t& _m,
const typename mesh_t::EdgeHandle& _eh)
378 typename mesh_t::HalfedgeHandle heh, opp_heh;
380 heh = _m.halfedge_handle( _eh, 0);
381 opp_heh = _m.halfedge_handle( _eh, 1);
389 if (_m.is_boundary(_eh) )
392 pos += _m.point(a_1);
395 if(_m.is_boundary(heh))
397 tpos = _m.point(_m.to_vertex_handle(_m.next_halfedge_handle(heh)));
398 tpos += _m.point(_m.to_vertex_handle(_m.opposite_halfedge_handle(_m.prev_halfedge_handle(heh))));
402 assert(_m.is_boundary(opp_heh));
403 tpos = _m.point(_m.to_vertex_handle(_m.next_halfedge_handle(opp_heh)));
404 tpos += _m.point(_m.to_vertex_handle(_m.opposite_halfedge_handle(_m.prev_halfedge_handle(opp_heh))));
411 int valence_a_0 = _m.valence(a_0);
412 int valence_a_1 = _m.valence(a_1);
413 assert(valence_a_0>2);
414 assert(valence_a_1>2);
416 if( (valence_a_0==6 && valence_a_1==6) || (_m.is_boundary(a_0) && valence_a_1==6) || (_m.is_boundary(a_1) && valence_a_0==6) || (_m.is_boundary(a_0) && _m.is_boundary(a_1)) )
418 real_t alpha = real_t(1.0/2);
419 real_t beta = real_t(1.0/8);
420 real_t gamma = real_t(-1.0/16);
424 typename mesh_t::HalfedgeHandle t_he;
426 t_he = _m.next_halfedge_handle(_m.opposite_halfedge_handle(heh));
427 b_0 = _m.to_vertex_handle(t_he);
428 if(!_m.is_boundary(_m.opposite_halfedge_handle(t_he)))
430 t_he = _m.next_halfedge_handle(_m.opposite_halfedge_handle(t_he));
431 c_0 = _m.to_vertex_handle(t_he);
434 t_he = _m.opposite_halfedge_handle(_m.prev_halfedge_handle(heh));
435 b_1 = _m.to_vertex_handle(t_he);
436 if(!_m.is_boundary(t_he))
438 t_he = _m.opposite_halfedge_handle(_m.prev_halfedge_handle(t_he));
439 c_1 = _m.to_vertex_handle(t_he);
442 t_he = _m.next_halfedge_handle(_m.opposite_halfedge_handle(opp_heh));
443 assert(b_1.idx()==_m.to_vertex_handle(t_he).idx());
444 if(!_m.is_boundary(_m.opposite_halfedge_handle(t_he)))
446 t_he = _m.next_halfedge_handle(_m.opposite_halfedge_handle(t_he));
447 c_2 = _m.to_vertex_handle(t_he);
450 t_he = _m.opposite_halfedge_handle(_m.prev_halfedge_handle(opp_heh));
451 assert(b_0==_m.to_vertex_handle(t_he));
452 if(!_m.is_boundary(t_he))
454 t_he = _m.opposite_halfedge_handle(_m.prev_halfedge_handle(t_he));
455 c_3 = _m.to_vertex_handle(t_he);
460 assert(a_0.is_valid());
461 assert(a_1.is_valid());
462 assert(b_0.is_valid());
463 assert(b_1.is_valid());
467 pos += _m.point(a_1);
471 tpos += _m.point(b_1);
477 pc_0 = _m.point(c_0);
480 pc_0 = _m.point(a_1) + _m.point(b_0) - _m.point(a_0);
483 pc_1 = _m.point(c_1);
486 pc_1 = _m.point(a_1) + _m.point(b_1) - _m.point(a_0);
489 pc_2 = _m.point(c_2);
492 pc_2 = _m.point(a_0) + _m.point(b_1) - _m.point(a_1);
495 pc_3 = _m.point(c_3);
498 pc_3 = _m.point(a_0) + _m.point(b_0) - _m.point(a_1);
509 double normFactor = 0.0;
511 if(valence_a_0!=6 && !_m.is_boundary(a_0))
513 assert((
int)weights[valence_a_0].size()==valence_a_0+1);
514 typename mesh_t::HalfedgeHandle t_he = opp_heh;
515 for(
int i = 0; i < valence_a_0 ; t_he=_m.next_halfedge_handle(_m.opposite_halfedge_handle(t_he)), ++i)
517 pos += weights[valence_a_0][i] * _m.point(_m.to_vertex_handle(t_he));
519 assert(t_he==opp_heh);
522 pos += weights[valence_a_0][valence_a_0] * _m.point(a_0);
526 if(valence_a_1!=6 && !_m.is_boundary(a_1))
528 assert((
int)weights[valence_a_1].size()==valence_a_1+1);
529 typename mesh_t::HalfedgeHandle t_he = heh;
530 for(
int i = 0; i < valence_a_1 ; t_he=_m.next_halfedge_handle(_m.opposite_halfedge_handle(t_he)), ++i)
532 pos += weights[valence_a_1][i] * _m.point(_m.to_vertex_handle(t_he));
536 pos += weights[valence_a_1][valence_a_1] * _m.point(a_1);
540 assert(normFactor>0.1);
546 _m.property( ep_pos_, _eh ) = pos;
Modified Butterfly subdivision algorithm.
Definition: ModifiedButterFlyT.hh:99
bool prepare(mesh_t &_m)
Prepare mesh, e.g. add properties.
Definition: ModifiedButterFlyT.hh:168
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139
Abstract base class for uniform subdivision algorithms.
Definition: SubdividerT.hh:94
bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide mesh _m _n times.
Definition: ModifiedButterFlyT.hh:184
bool cleanup(mesh_t &_m)
Cleanup mesh after usage, e.g. remove added properties.
Definition: ModifiedButterFlyT.hh:176
void init_weights(size_t _max_valence=30)
Pre-compute weights.
Definition: ModifiedButterFlyT.hh:131
const char * name() const
Return name of subdivision algorithm.
Definition: ModifiedButterFlyT.hh:127
Check integrity of mesh.
Definition: MeshCheckerT.hh:78
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:115
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:64