OpenMesh

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

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Sqrt3T.hh
Go to the documentation of this file.
1 /*===========================================================================*\
2 * *
3 * OpenMesh *
4 * Copyright (C) 2001-2014 by Computer Graphics Group, RWTH Aachen *
5 * www.openmesh.org *
6 * *
7 *---------------------------------------------------------------------------*
8 * This file is part of OpenMesh. *
9 * *
10 * OpenMesh is free software: you can redistribute it and/or modify *
11 * it under the terms of the GNU Lesser General Public License as *
12 * published by the Free Software Foundation, either version 3 of *
13 * the License, or (at your option) any later version with the *
14 * following exceptions: *
15 * *
16 * If other files instantiate templates or use macros *
17 * or inline functions from this file, or you compile this file and *
18 * link it with other files to produce an executable, this file does *
19 * not by itself cause the resulting executable to be covered by the *
20 * GNU Lesser General Public License. This exception does not however *
21 * invalidate any other reasons why the executable file might be *
22 * covered by the GNU Lesser General Public License. *
23 * *
24 * OpenMesh is distributed in the hope that it will be useful, *
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
27 * GNU Lesser General Public License for more details. *
28 * *
29 * You should have received a copy of the GNU LesserGeneral Public *
30 * License along with OpenMesh. If not, *
31 * see <http://www.gnu.org/licenses/>. *
32 * *
33 \*===========================================================================*/
34
35 /*===========================================================================*\
36 * *
37 * $Revision: 990 $ *
38 * $Date: 2014-02-05 10:01:07 +0100 (Mi, 05. Feb 2014) $ *
39 * *
40 \*===========================================================================*/
41
46 //=============================================================================
47 //
48 // CLASS Sqrt3T
49 //
50 //=============================================================================
51
52 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
53 #define OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
54
55
56 //== INCLUDES =================================================================
57
58 #include <OpenMesh/Core/Mesh/Handles.hh>
59 #include <OpenMesh/Core/System/config.hh>
60 #include <OpenMesh/Tools/Subdivider/Uniform/SubdividerT.hh>
61 #if defined(_DEBUG) || defined(DEBUG)
62 // Makes life lot easier, when playing/messing around with low-level topology
63 // changing methods of OpenMesh
64 # include <OpenMesh/Tools/Utils/MeshCheckerT.hh>
65 # define ASSERT_CONSISTENCY( T, m ) \
66 assert(OpenMesh::Utils::MeshCheckerT<T>(m).check())
67 #else
68 # define ASSERT_CONSISTENCY( T, m )
69 #endif
70 // -------------------- STL
71 #include <vector>
72 #if defined(OM_CC_MIPS)
73 # include <math.h>
74 #else
75 # include <cmath>
76 #endif
77
78
79 //== NAMESPACE ================================================================
80
81 namespace OpenMesh { // BEGIN_NS_OPENMESH
82 namespace Subdivider { // BEGIN_NS_DECIMATER
83 namespace Uniform { // BEGIN_NS_DECIMATER
84
85
86 //== CLASS DEFINITION =========================================================
87
88
95 template <typename MeshType, typename RealType = float>
96 class Sqrt3T : public SubdividerT< MeshType, RealType >
97 {
98 public:
99
100 typedef RealType real_t;
101 typedef MeshType mesh_t;
102 typedef SubdividerT< mesh_t, real_t > parent_t;
103
104 typedef std::pair< real_t, real_t > weight_t;
105 typedef std::vector< std::pair<real_t,real_t> > weights_t;
106
107 public:
108
109
110 Sqrt3T(void) : parent_t(), _1over3( real_t(1.0/3.0) ), _1over27( real_t(1.0/27.0) )
111 { init_weights(); }
112
113 Sqrt3T(MeshType &_m) : parent_t(_m), _1over3( real_t(1.0/3.0) ), _1over27( real_t(1.0/27.0) )
114 { init_weights(); }
115
116 virtual ~Sqrt3T() {}
117
118
119 public:
120
121
122 const char *name() const { return "Uniform Sqrt3"; }
123
124
126 void init_weights(size_t _max_valence=50)
127 {
128 weights_.resize(_max_valence);
129 std::generate(weights_.begin(), weights_.end(), compute_weight());
130 }
131
132
133 protected:
134
135
136 bool prepare( MeshType& _m )
137 {
138 _m.request_edge_status();
139 _m.add_property( vp_pos_ );
140 _m.add_property( ep_nv_ );
141 _m.add_property( mp_gen_ );
142 _m.property( mp_gen_ ) = 0;
143
144 return _m.has_edge_status() && vp_pos_.is_valid()
145 && ep_nv_.is_valid() && mp_gen_.is_valid();
146 }
147
148
149 bool cleanup( MeshType& _m )
150 {
151 _m.release_edge_status();
152 _m.remove_property( vp_pos_ );
153 _m.remove_property( ep_nv_ );
154 _m.remove_property( mp_gen_ );
155 return true;
156 }
157
158 bool subdivide( MeshType& _m, size_t _n , const bool _update_points = true)
159 {
160
162
163 typename MeshType::VertexIter vit;
164 typename MeshType::VertexVertexIter vvit;
165 typename MeshType::EdgeIter eit;
166 typename MeshType::FaceIter fit;
167 typename MeshType::FaceVertexIter fvit;
168 typename MeshType::VertexHandle vh;
169 typename MeshType::HalfedgeHandle heh;
170 typename MeshType::Point pos(0,0,0), zero(0,0,0);
171 size_t &gen = _m.property( mp_gen_ );
172
173 for (size_t l=0; l<_n; ++l)
174 {
175 // tag existing edges
176 for (eit=_m.edges_begin(); eit != _m.edges_end();++eit)
177 {
178 _m.status( *eit ).set_tagged( true );
179 if ( (gen%2) && _m.is_boundary(*eit) )
180 compute_new_boundary_points( _m, *eit ); // *) creates new vertices
181 }
182
183 // do relaxation of old vertices, but store new pos in property vp_pos_
184
185 for (vit=_m.vertices_begin(); vit!=_m.vertices_end(); ++vit)
186 {
187 if ( _m.is_boundary(*vit) )
188 {
189 if ( gen%2 )
190 {
191 heh = _m.halfedge_handle(*vit);
192 if (heh.is_valid()) // skip isolated newly inserted vertices *)
193 {
194 typename OpenMesh::HalfedgeHandle
195 prev_heh = _m.prev_halfedge_handle(heh);
196
197 assert( _m.is_boundary(heh ) );
198 assert( _m.is_boundary(prev_heh) );
199
200 pos = _m.point(_m.to_vertex_handle(heh));
201 pos += _m.point(_m.from_vertex_handle(prev_heh));
202 pos *= real_t(4.0);
203
204 pos += real_t(19.0) * _m.point( *vit );
205 pos *= _1over27;
206
207 _m.property( vp_pos_, *vit ) = pos;
208 }
209 }
210 else
211 _m.property( vp_pos_, *vit ) = _m.point( *vit );
212 }
213 else
214 {
215 size_t valence=0;
216
217 pos = zero;
218 for ( vvit = _m.vv_iter(*vit); vvit.is_valid(); ++vvit)
219 {
220 pos += _m.point( *vvit );
221 ++valence;
222 }
223 pos *= weights_[ valence ].second;
224 pos += weights_[ valence ].first * _m.point(*vit);
225 _m.property( vp_pos_, *vit ) = pos;
226 }
227 }
228
229 // insert new vertices, but store pos in vp_pos_
230 typename MeshType::FaceIter fend = _m.faces_end();
231 for (fit = _m.faces_begin();fit != fend; ++fit)
232 {
233 if ( (gen%2) && _m.is_boundary(*fit))
234 {
235 boundary_split( _m, *fit );
236 }
237 else
238 {
239 fvit = _m.fv_iter( *fit );
240 pos = _m.point( *fvit);
241 pos += _m.point(*(++fvit));
242 pos += _m.point(*(++fvit));
243 pos *= _1over3;
244 vh = _m.add_vertex( zero );
245 _m.property( vp_pos_, vh ) = pos;
246 _m.split( *fit, vh );
247 }
248 }
249
250 // commit new positions (now iterating over all vertices)
251 for (vit=_m.vertices_begin();vit != _m.vertices_end(); ++vit)
252 _m.set_point(*vit, _m.property( vp_pos_, *vit ) );
253
254 // flip old edges
255 for (eit=_m.edges_begin(); eit != _m.edges_end(); ++eit)
256 if ( _m.status( *eit ).tagged() && !_m.is_boundary( *eit ) )
257 _m.flip(*eit);
258
259 // Now we have an consistent mesh!
260 ASSERT_CONSISTENCY( MeshType, _m );
261
262 // increase generation by one
263 ++gen;
264 }
265 return true;
266 }
267
268 private:
269
272 struct compute_weight
273 {
274 compute_weight() : valence(-1) { }
275 weight_t operator() (void)
276 {
277 #if !defined(OM_CC_MIPS)
278 using std::cos;
279 #endif
280 if (++valence)
281 {
282 real_t alpha = real_t( (4.0-2.0*cos(2.0*M_PI / real_t(valence)) )/9.0 );
283 return weight_t( real_t(1)-alpha, alpha/real_t(valence) );
284 }
285 return weight_t(real_t(0.0), real_t(0.0) );
286 }
287 int valence;
288 };
289
290 private:
291
292 // Pre-compute location of new boundary points for odd generations
293 // and store them in the edge property ep_nv_;
294 void compute_new_boundary_points( MeshType& _m,
295 const typename MeshType::EdgeHandle& _eh)
296 {
297 assert( _m.is_boundary(_eh) );
298
299 typename MeshType::HalfedgeHandle heh;
300 typename MeshType::VertexHandle vh1, vh2, vh3, vh4, vhl, vhr;
301 typename MeshType::Point zero(0,0,0), P1, P2, P3, P4;
302
303 /*
304 // *---------*---------*
305 // / \ / \ / \
306 // / \ / \ / \
307 // / \ / \ / \
308 // / \ / \ / \
309 // *---------*--#---#--*---------*
310 //
311 // ^ ^ ^ ^ ^ ^
312 // P1 P2 pl pr P3 P4
313 */
314 // get halfedge pointing from P3 to P2 (outer boundary halfedge)
315
316 heh = _m.halfedge_handle(_eh,
317 _m.is_boundary(_m.halfedge_handle(_eh,1)));
318
319 assert( _m.is_boundary( _m.next_halfedge_handle( heh ) ) );
320 assert( _m.is_boundary( _m.prev_halfedge_handle( heh ) ) );
321
322 vh1 = _m.to_vertex_handle( _m.next_halfedge_handle( heh ) );
323 vh2 = _m.to_vertex_handle( heh );
324 vh3 = _m.from_vertex_handle( heh );
325 vh4 = _m.from_vertex_handle( _m.prev_halfedge_handle( heh ));
326
327 P1 = _m.point(vh1);
328 P2 = _m.point(vh2);
329 P3 = _m.point(vh3);
330 P4 = _m.point(vh4);
331
332 vhl = _m.add_vertex(zero);
333 vhr = _m.add_vertex(zero);
334
335 _m.property(vp_pos_, vhl ) = (P1 + real_t(16.0f) * P2 + real_t(10.0f) * P3) * _1over27;
336 _m.property(vp_pos_, vhr ) = ( real_t(10.0f) * P2 + real_t(16.0f) * P3 + P4) * _1over27;
337 _m.property(ep_nv_, _eh).first = vhl;
338 _m.property(ep_nv_, _eh).second = vhr;
339 }
340
341
342 void boundary_split( MeshType& _m, const typename MeshType::FaceHandle& _fh )
343 {
344 assert( _m.is_boundary(_fh) );
345
346 typename MeshType::VertexHandle vhl, vhr;
347 typename MeshType::FaceEdgeIter fe_it;
348 typename MeshType::HalfedgeHandle heh;
349
350 // find boundary edge
351 for( fe_it=_m.fe_iter( _fh ); fe_it.is_valid() && !_m.is_boundary( *fe_it ); ++fe_it ) {};
352
353 // use precomputed, already inserted but not linked vertices
354 vhl = _m.property(ep_nv_, *fe_it).first;
355 vhr = _m.property(ep_nv_, *fe_it).second;
356
357 /*
358 // *---------*---------*
359 // / \ / \ / \
360 // / \ / \ / \
361 // / \ / \ / \
362 // / \ / \ / \
363 // *---------*--#---#--*---------*
364 //
365 // ^ ^ ^ ^ ^ ^
366 // P1 P2 pl pr P3 P4
367 */
368 // get halfedge pointing from P2 to P3 (inner boundary halfedge)
369
370 heh = _m.halfedge_handle(*fe_it,
371 _m.is_boundary(_m.halfedge_handle(*fe_it,0)));
372
373 typename MeshType::HalfedgeHandle pl_P3;
374
375 // split P2->P3 (heh) in P2->pl (heh) and pl->P3
376 boundary_split( _m, heh, vhl ); // split edge
377 pl_P3 = _m.next_halfedge_handle( heh ); // store next halfedge handle
378 boundary_split( _m, heh ); // split face
379
380 // split pl->P3 in pl->pr and pr->P3
381 boundary_split( _m, pl_P3, vhr );
382 boundary_split( _m, pl_P3 );
383
384 assert( _m.is_boundary( vhl ) && _m.halfedge_handle(vhl).is_valid() );
385 assert( _m.is_boundary( vhr ) && _m.halfedge_handle(vhr).is_valid() );
386 }
387
388 void boundary_split(MeshType& _m,
389 const typename MeshType::HalfedgeHandle& _heh,
390 const typename MeshType::VertexHandle& _vh)
391 {
392 assert( _m.is_boundary( _m.edge_handle(_heh) ) );
393
394 typename MeshType::HalfedgeHandle
395 heh(_heh),
396 opp_heh( _m.opposite_halfedge_handle(_heh) ),
397 new_heh, opp_new_heh;
398 typename MeshType::VertexHandle to_vh(_m.to_vertex_handle(heh));
399 typename MeshType::HalfedgeHandle t_heh;
400
401 /*
402 * P5
403 * *
404 * /|\
405 * / \
406 * / \
407 * / \
408 * / \
409 * /_ heh new \
410 * *-----\*-----\*\-----*
411 * ^ ^ t_heh
412 * _vh to_vh
413 *
414 * P1 P2 P3 P4
415 */
416 // Re-Setting Handles
417
418 // find halfedge point from P4 to P3
419 for(t_heh = heh;
420 _m.next_halfedge_handle(t_heh) != opp_heh;
421 t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
422 {}
423
424 assert( _m.is_boundary( t_heh ) );
425
426 new_heh = _m.new_edge( _vh, to_vh );
427 opp_new_heh = _m.opposite_halfedge_handle(new_heh);
428
429 // update halfedge connectivity
430
431 _m.set_next_halfedge_handle(t_heh, opp_new_heh); // P4-P3 -> P3-P2
432 // P2-P3 -> P3-P5
433 _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
434 _m.set_next_halfedge_handle(heh, new_heh); // P1-P2 -> P2-P3
435 _m.set_next_halfedge_handle(opp_new_heh, opp_heh); // P3-P2 -> P2-P1
436
437 // both opposite halfedges point to same face
438 _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
439
440 // let heh finally point to new inserted vertex
441 _m.set_vertex_handle(heh, _vh);
442
443 // let heh and new_heh point to same face
444 _m.set_face_handle(new_heh, _m.face_handle(heh));
445
446 // let opp_new_heh be the new outgoing halfedge for to_vh
447 // (replaces for opp_heh)
448 _m.set_halfedge_handle( to_vh, opp_new_heh );
449
450 // let opp_heh be the outgoing halfedge for _vh
451 _m.set_halfedge_handle( _vh, opp_heh );
452 }
453
454 void boundary_split( MeshType& _m,
455 const typename MeshType::HalfedgeHandle& _heh)
456 {
457 assert( _m.is_boundary( _m.opposite_halfedge_handle( _heh ) ) );
458
459 typename MeshType::HalfedgeHandle
460 heh(_heh),
461 n_heh(_m.next_halfedge_handle(heh));
462
463 typename MeshType::VertexHandle
464 to_vh(_m.to_vertex_handle(heh));
465
466 typename MeshType::HalfedgeHandle
467 heh2(_m.new_edge(to_vh,
468 _m.to_vertex_handle(_m.next_halfedge_handle(n_heh)))),
469 heh3(_m.opposite_halfedge_handle(heh2));
470
471 typename MeshType::FaceHandle
472 new_fh(_m.new_face()),
473 fh(_m.face_handle(heh));
474
475 // Relink (half)edges
476
477 #define set_next_heh set_next_halfedge_handle
478 #define next_heh next_halfedge_handle
479
480 _m.set_face_handle(heh, new_fh);
481 _m.set_face_handle(heh2, new_fh);
482 _m.set_next_heh(heh2, _m.next_heh(_m.next_heh(n_heh)));
483 _m.set_next_heh(heh, heh2);
484 _m.set_face_handle( _m.next_heh(heh2), new_fh);
485
486 // _m.set_face_handle( _m.next_heh(_m.next_heh(heh2)), new_fh);
487
488 _m.set_next_heh(heh3, n_heh);
489 _m.set_next_heh(_m.next_halfedge_handle(n_heh), heh3);
490 _m.set_face_handle(heh3, fh);
491 // _m.set_face_handle(n_heh, fh);
492
493 _m.set_halfedge_handle( fh, n_heh);
494 _m.set_halfedge_handle(new_fh, heh);
495
496 #undef set_next_halfedge_handle
497 #undef next_halfedge_handle
498
499 }
500
501 private:
502
503 weights_t weights_;
504 OpenMesh::VPropHandleT< typename MeshType::Point > vp_pos_;
505 OpenMesh::EPropHandleT< std::pair< typename MeshType::VertexHandle,
506 typename MeshType::VertexHandle> > ep_nv_;
507 OpenMesh::MPropHandleT< size_t > mp_gen_;
508
509 const real_t _1over3;
510 const real_t _1over27;
511 };
512
513
514 //=============================================================================
515 } // END_NS_UNIFORM
516 } // END_NS_SUBDIVIDER
517 } // END_NS_OPENMESH
518 //=============================================================================
519 #endif // OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
520 //=============================================================================
OpenMesh::MPropHandleT< size_t >
OpenMesh::Subdivider::Uniform::Sqrt3T
Uniform Sqrt3 subdivision algorithm
Definition: Sqrt3T.hh:96
OpenMesh::Subdivider::Uniform::Sqrt3T::cleanup
bool cleanup(MeshType &_m)
Cleanup mesh after usage, e.g. remove added properties.
Definition: Sqrt3T.hh:149
OpenMesh::BaseHandle::is_valid
bool is_valid() const
The handle is valid iff the index is not equal to -1.
Definition: Handles.hh:70
OpenMesh::Subdivider::Uniform::Sqrt3T::prepare
bool prepare(MeshType &_m)
Prepare mesh, e.g. add properties.
Definition: Sqrt3T.hh:136
OpenMesh::Subdivider::Uniform::SubdividerT
Abstract base class for uniform subdivision algorithms.
Definition: SubdividerT.hh:87
OpenMesh::Subdivider::Uniform::Sqrt3T::init_weights
void init_weights(size_t _max_valence=50)
Pre-compute weights.
Definition: Sqrt3T.hh:126
OpenMesh::VPropHandleT< typename MeshType::Point >
OpenMesh::EPropHandleT
Handle representing an edge property.
Definition: Property.hh:504
OpenMesh::Subdivider::Uniform::SubdividerT::operator()
bool operator()(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide the mesh _m _n times.
Definition: SubdividerT.hh:121
OpenMesh::Subdivider::Uniform::Sqrt3T::subdivide
bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide mesh _m _n times.
Definition: Sqrt3T.hh:158
OpenMesh::Subdivider::Uniform::Sqrt3T::name
const char * name() const
Return name of subdivision algorithm.
Definition: Sqrt3T.hh:122
SubdividerT.hh
OpenMesh::HalfedgeHandle
Handle for a halfedge entity.
Definition: Handles.hh:121