OpenMesh
Sqrt3T.hh
Go to the documentation of this file.
1 /* ========================================================================= *
2  * *
3  * OpenMesh *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openmesh.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenMesh. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39  * *
40  * ========================================================================= */
41 
42 
43 
48 //=============================================================================
49 //
50 // CLASS Sqrt3T
51 //
52 //=============================================================================
53 
54 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
55 #define OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
56 
57 
58 //== INCLUDES =================================================================
59 
60 #include <OpenMesh/Core/Mesh/Handles.hh>
61 #include <OpenMesh/Core/System/config.hh>
63 #if defined(_DEBUG) || defined(DEBUG)
64 // Makes life lot easier, when playing/messing around with low-level topology
65 // changing methods of OpenMesh
66 # include <OpenMesh/Tools/Utils/MeshCheckerT.hh>
67 # define ASSERT_CONSISTENCY( T, m ) \
68  assert(OpenMesh::Utils::MeshCheckerT<T>(m).check())
69 #else
70 # define ASSERT_CONSISTENCY( T, m )
71 #endif
72 // -------------------- STL
73 #include <vector>
74 #if defined(OM_CC_MIPS)
75 # include <math.h>
76 #else
77 # include <cmath>
78 #endif
79 
80 
81 //== NAMESPACE ================================================================
82 
83 namespace OpenMesh { // BEGIN_NS_OPENMESH
84 namespace Subdivider { // BEGIN_NS_DECIMATER
85 namespace Uniform { // BEGIN_NS_DECIMATER
86 
87 
88 //== CLASS DEFINITION =========================================================
89 
90 
97 template <typename MeshType, typename RealType = double>
98 class Sqrt3T : public SubdividerT< MeshType, RealType >
99 {
100 public:
101 
102  typedef RealType real_t;
103  typedef MeshType mesh_t;
105 
106  typedef std::pair< real_t, real_t > weight_t;
107  typedef std::vector< std::pair<real_t,real_t> > weights_t;
108 
109 public:
110 
111 
112  Sqrt3T(void) : parent_t(), _1over3( real_t(1.0/3.0) ), _1over27( real_t(1.0/27.0) )
113  { init_weights(); }
114 
115  Sqrt3T(MeshType &_m) : parent_t(_m), _1over3( real_t(1.0/3.0) ), _1over27( real_t(1.0/27.0) )
116  { init_weights(); }
117 
118  virtual ~Sqrt3T() {}
119 
120 
121 public:
122 
123 
124  const char *name() const { return "Uniform Sqrt3"; }
125 
126 
128  void init_weights(size_t _max_valence=50)
129  {
130  weights_.resize(_max_valence);
131  std::generate(weights_.begin(), weights_.end(), compute_weight());
132  }
133 
134 
135 protected:
136 
137 
138  bool prepare( MeshType& _m )
139  {
140  _m.request_edge_status();
141  _m.add_property( vp_pos_ );
142  _m.add_property( ep_nv_ );
143  _m.add_property( mp_gen_ );
144  _m.property( mp_gen_ ) = 0;
145 
146  return _m.has_edge_status() && vp_pos_.is_valid()
147  && ep_nv_.is_valid() && mp_gen_.is_valid();
148  }
149 
150 
151  bool cleanup( MeshType& _m )
152  {
153  _m.release_edge_status();
154  _m.remove_property( vp_pos_ );
155  _m.remove_property( ep_nv_ );
156  _m.remove_property( mp_gen_ );
157  return true;
158  }
159 
160  bool subdivide( MeshType& _m, size_t _n , const bool _update_points = true)
161  {
162 
164 
165  typename MeshType::VertexIter vit;
166  typename MeshType::VertexVertexIter vvit;
167  typename MeshType::EdgeIter eit;
168  typename MeshType::FaceIter fit;
169  typename MeshType::FaceVertexIter fvit;
170  typename MeshType::VertexHandle vh;
171  typename MeshType::HalfedgeHandle heh;
172  typename MeshType::Point pos(0,0,0), zero(0,0,0);
173  size_t &gen = _m.property( mp_gen_ );
174 
175  for (size_t l=0; l<_n; ++l)
176  {
177  // tag existing edges
178  for (eit=_m.edges_begin(); eit != _m.edges_end();++eit)
179  {
180  _m.status( *eit ).set_tagged( true );
181  if ( (gen%2) && _m.is_boundary(*eit) )
182  compute_new_boundary_points( _m, *eit ); // *) creates new vertices
183  }
184 
185  // do relaxation of old vertices, but store new pos in property vp_pos_
186 
187  for (vit=_m.vertices_begin(); vit!=_m.vertices_end(); ++vit)
188  {
189  if ( _m.is_boundary(*vit) )
190  {
191  if ( gen%2 )
192  {
193  heh = _m.halfedge_handle(*vit);
194  if (heh.is_valid()) // skip isolated newly inserted vertices *)
195  {
196  typename OpenMesh::HalfedgeHandle
197  prev_heh = _m.prev_halfedge_handle(heh);
198 
199  assert( _m.is_boundary(heh ) );
200  assert( _m.is_boundary(prev_heh) );
201 
202  pos = _m.point(_m.to_vertex_handle(heh));
203  pos += _m.point(_m.from_vertex_handle(prev_heh));
204  pos *= real_t(4.0);
205 
206  pos += real_t(19.0) * _m.point( *vit );
207  pos *= _1over27;
208 
209  _m.property( vp_pos_, *vit ) = pos;
210  }
211  }
212  else
213  _m.property( vp_pos_, *vit ) = _m.point( *vit );
214  }
215  else
216  {
217  size_t valence=0;
218 
219  pos = zero;
220  for ( vvit = _m.vv_iter(*vit); vvit.is_valid(); ++vvit)
221  {
222  pos += _m.point( *vvit );
223  ++valence;
224  }
225  pos *= weights_[ valence ].second;
226  pos += weights_[ valence ].first * _m.point(*vit);
227  _m.property( vp_pos_, *vit ) = pos;
228  }
229  }
230 
231  // insert new vertices, but store pos in vp_pos_
232  typename MeshType::FaceIter fend = _m.faces_end();
233  for (fit = _m.faces_begin();fit != fend; ++fit)
234  {
235  if ( (gen%2) && _m.is_boundary(*fit))
236  {
237  boundary_split( _m, *fit );
238  }
239  else
240  {
241  fvit = _m.fv_iter( *fit );
242  pos = _m.point( *fvit);
243  pos += _m.point(*(++fvit));
244  pos += _m.point(*(++fvit));
245  pos *= _1over3;
246  vh = _m.add_vertex( zero );
247  _m.property( vp_pos_, vh ) = pos;
248  _m.split( *fit, vh );
249  }
250  }
251 
252  // commit new positions (now iterating over all vertices)
253  for (vit=_m.vertices_begin();vit != _m.vertices_end(); ++vit)
254  _m.set_point(*vit, _m.property( vp_pos_, *vit ) );
255 
256  // flip old edges
257  for (eit=_m.edges_begin(); eit != _m.edges_end(); ++eit)
258  if ( _m.status( *eit ).tagged() && !_m.is_boundary( *eit ) )
259  _m.flip(*eit);
260 
261  // Now we have an consistent mesh!
262  ASSERT_CONSISTENCY( MeshType, _m );
263 
264  // increase generation by one
265  ++gen;
266  }
267  return true;
268  }
269 
270 private:
271 
274  struct compute_weight
275  {
276  compute_weight() : valence(-1) { }
277  weight_t operator() (void)
278  {
279 #if !defined(OM_CC_MIPS)
280  using std::cos;
281 #endif
282  if (++valence)
283  {
284  real_t alpha = real_t( (4.0-2.0*cos(2.0*M_PI / real_t(valence)) )/9.0 );
285  return weight_t( real_t(1)-alpha, alpha/real_t(valence) );
286  }
287  return weight_t(real_t(0.0), real_t(0.0) );
288  }
289  int valence;
290  };
291 
292 private:
293 
294  // Pre-compute location of new boundary points for odd generations
295  // and store them in the edge property ep_nv_;
296  void compute_new_boundary_points( MeshType& _m,
297  const typename MeshType::EdgeHandle& _eh)
298  {
299  assert( _m.is_boundary(_eh) );
300 
301  typename MeshType::HalfedgeHandle heh;
302  typename MeshType::VertexHandle vh1, vh2, vh3, vh4, vhl, vhr;
303  typename MeshType::Point zero(0,0,0), P1, P2, P3, P4;
304 
305  /*
306  // *---------*---------*
307  // / \ / \ / \
308  // / \ / \ / \
309  // / \ / \ / \
310  // / \ / \ / \
311  // *---------*--#---#--*---------*
312  //
313  // ^ ^ ^ ^ ^ ^
314  // P1 P2 pl pr P3 P4
315  */
316  // get halfedge pointing from P3 to P2 (outer boundary halfedge)
317 
318  heh = _m.halfedge_handle(_eh,
319  _m.is_boundary(_m.halfedge_handle(_eh,1)));
320 
321  assert( _m.is_boundary( _m.next_halfedge_handle( heh ) ) );
322  assert( _m.is_boundary( _m.prev_halfedge_handle( heh ) ) );
323 
324  vh1 = _m.to_vertex_handle( _m.next_halfedge_handle( heh ) );
325  vh2 = _m.to_vertex_handle( heh );
326  vh3 = _m.from_vertex_handle( heh );
327  vh4 = _m.from_vertex_handle( _m.prev_halfedge_handle( heh ));
328 
329  P1 = _m.point(vh1);
330  P2 = _m.point(vh2);
331  P3 = _m.point(vh3);
332  P4 = _m.point(vh4);
333 
334  vhl = _m.add_vertex(zero);
335  vhr = _m.add_vertex(zero);
336 
337  _m.property(vp_pos_, vhl ) = (P1 + real_t(16.0f) * P2 + real_t(10.0f) * P3) * _1over27;
338  _m.property(vp_pos_, vhr ) = ( real_t(10.0f) * P2 + real_t(16.0f) * P3 + P4) * _1over27;
339  _m.property(ep_nv_, _eh).first = vhl;
340  _m.property(ep_nv_, _eh).second = vhr;
341  }
342 
343 
344  void boundary_split( MeshType& _m, const typename MeshType::FaceHandle& _fh )
345  {
346  assert( _m.is_boundary(_fh) );
347 
348  typename MeshType::VertexHandle vhl, vhr;
349  typename MeshType::FaceEdgeIter fe_it;
350  typename MeshType::HalfedgeHandle heh;
351 
352  // find boundary edge
353  for( fe_it=_m.fe_iter( _fh ); fe_it.is_valid() && !_m.is_boundary( *fe_it ); ++fe_it ) {};
354 
355  // use precomputed, already inserted but not linked vertices
356  vhl = _m.property(ep_nv_, *fe_it).first;
357  vhr = _m.property(ep_nv_, *fe_it).second;
358 
359  /*
360  // *---------*---------*
361  // / \ / \ / \
362  // / \ / \ / \
363  // / \ / \ / \
364  // / \ / \ / \
365  // *---------*--#---#--*---------*
366  //
367  // ^ ^ ^ ^ ^ ^
368  // P1 P2 pl pr P3 P4
369  */
370  // get halfedge pointing from P2 to P3 (inner boundary halfedge)
371 
372  heh = _m.halfedge_handle(*fe_it,
373  _m.is_boundary(_m.halfedge_handle(*fe_it,0)));
374 
375  typename MeshType::HalfedgeHandle pl_P3;
376 
377  // split P2->P3 (heh) in P2->pl (heh) and pl->P3
378  boundary_split( _m, heh, vhl ); // split edge
379  pl_P3 = _m.next_halfedge_handle( heh ); // store next halfedge handle
380  boundary_split( _m, heh ); // split face
381 
382  // split pl->P3 in pl->pr and pr->P3
383  boundary_split( _m, pl_P3, vhr );
384  boundary_split( _m, pl_P3 );
385 
386  assert( _m.is_boundary( vhl ) && _m.halfedge_handle(vhl).is_valid() );
387  assert( _m.is_boundary( vhr ) && _m.halfedge_handle(vhr).is_valid() );
388  }
389 
390  void boundary_split(MeshType& _m,
391  const typename MeshType::HalfedgeHandle& _heh,
392  const typename MeshType::VertexHandle& _vh)
393  {
394  assert( _m.is_boundary( _m.edge_handle(_heh) ) );
395 
396  typename MeshType::HalfedgeHandle
397  heh(_heh),
398  opp_heh( _m.opposite_halfedge_handle(_heh) ),
399  new_heh, opp_new_heh;
400  typename MeshType::VertexHandle to_vh(_m.to_vertex_handle(heh));
401  typename MeshType::HalfedgeHandle t_heh;
402 
403  /*
404  * P5
405  * *
406  * /|\
407  * / \
408  * / \
409  * / \
410  * / \
411  * /_ heh new \
412  * *-----\*-----\*\-----*
413  * ^ ^ t_heh
414  * _vh to_vh
415  *
416  * P1 P2 P3 P4
417  */
418  // Re-Setting Handles
419 
420  // find halfedge point from P4 to P3
421  for(t_heh = heh;
422  _m.next_halfedge_handle(t_heh) != opp_heh;
423  t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
424  {}
425 
426  assert( _m.is_boundary( t_heh ) );
427 
428  new_heh = _m.new_edge( _vh, to_vh );
429  opp_new_heh = _m.opposite_halfedge_handle(new_heh);
430 
431  // update halfedge connectivity
432 
433  _m.set_next_halfedge_handle(t_heh, opp_new_heh); // P4-P3 -> P3-P2
434  // P2-P3 -> P3-P5
435  _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
436  _m.set_next_halfedge_handle(heh, new_heh); // P1-P2 -> P2-P3
437  _m.set_next_halfedge_handle(opp_new_heh, opp_heh); // P3-P2 -> P2-P1
438 
439  // both opposite halfedges point to same face
440  _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
441 
442  // let heh finally point to new inserted vertex
443  _m.set_vertex_handle(heh, _vh);
444 
445  // let heh and new_heh point to same face
446  _m.set_face_handle(new_heh, _m.face_handle(heh));
447 
448  // let opp_new_heh be the new outgoing halfedge for to_vh
449  // (replaces for opp_heh)
450  _m.set_halfedge_handle( to_vh, opp_new_heh );
451 
452  // let opp_heh be the outgoing halfedge for _vh
453  _m.set_halfedge_handle( _vh, opp_heh );
454  }
455 
456  void boundary_split( MeshType& _m,
457  const typename MeshType::HalfedgeHandle& _heh)
458  {
459  assert( _m.is_boundary( _m.opposite_halfedge_handle( _heh ) ) );
460 
461  typename MeshType::HalfedgeHandle
462  heh(_heh),
463  n_heh(_m.next_halfedge_handle(heh));
464 
465  typename MeshType::VertexHandle
466  to_vh(_m.to_vertex_handle(heh));
467 
468  typename MeshType::HalfedgeHandle
469  heh2(_m.new_edge(to_vh,
470  _m.to_vertex_handle(_m.next_halfedge_handle(n_heh)))),
471  heh3(_m.opposite_halfedge_handle(heh2));
472 
473  typename MeshType::FaceHandle
474  new_fh(_m.new_face()),
475  fh(_m.face_handle(heh));
476 
477  // Relink (half)edges
478 
479 #define set_next_heh set_next_halfedge_handle
480 #define next_heh next_halfedge_handle
481 
482  _m.set_face_handle(heh, new_fh);
483  _m.set_face_handle(heh2, new_fh);
484  _m.set_next_heh(heh2, _m.next_heh(_m.next_heh(n_heh)));
485  _m.set_next_heh(heh, heh2);
486  _m.set_face_handle( _m.next_heh(heh2), new_fh);
487 
488  // _m.set_face_handle( _m.next_heh(_m.next_heh(heh2)), new_fh);
489 
490  _m.set_next_heh(heh3, n_heh);
491  _m.set_next_heh(_m.next_halfedge_handle(n_heh), heh3);
492  _m.set_face_handle(heh3, fh);
493  // _m.set_face_handle(n_heh, fh);
494 
495  _m.set_halfedge_handle( fh, n_heh);
496  _m.set_halfedge_handle(new_fh, heh);
497 
498 #undef set_next_halfedge_handle
499 #undef next_halfedge_handle
500 
501  }
502 
503 private:
504 
505  weights_t weights_;
507  OpenMesh::EPropHandleT< std::pair< typename MeshType::VertexHandle,
508  typename MeshType::VertexHandle> > ep_nv_;
510 
511  const real_t _1over3;
512  const real_t _1over27;
513 };
514 
515 
516 //=============================================================================
517 } // END_NS_UNIFORM
518 } // END_NS_SUBDIVIDER
519 } // END_NS_OPENMESH
520 //=============================================================================
521 #endif // OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
522 //=============================================================================
Handle for a halfedge entity.
Definition: Handles.hh:127
bool prepare(MeshType &_m)
Prepare mesh, e.g. add properties.
Definition: Sqrt3T.hh:138
void init_weights(size_t _max_valence=50)
Pre-compute weights.
Definition: Sqrt3T.hh:128
bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide mesh _m _n times.
Definition: Sqrt3T.hh:160
Uniform Sqrt3 subdivision algorithm
Definition: Sqrt3T.hh:98
bool operator()(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide the mesh _m _n times.
Definition: SubdividerT.hh:122
bool cleanup(MeshType &_m)
Cleanup mesh after usage, e.g. remove added properties.
Definition: Sqrt3T.hh:151
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
Handle representing an edge property.
Definition: Property.hh:510
Abstract base class for uniform subdivision algorithms.
Definition: SubdividerT.hh:88
const char * name() const
Return name of subdivision algorithm.
Definition: Sqrt3T.hh:124
bool is_valid() const
The handle is valid iff the index is not negative.
Definition: Handles.hh:72

Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .