OpenMesh
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
LoopT.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: 995 $ *
38  * $Date: 2014-02-12 15:29:15 +0100 (Mi, 12 Feb 2014) $ *
39  * *
40 \*===========================================================================*/
41 
46 //=============================================================================
47 //
48 // CLASS LoopT
49 //
50 //=============================================================================
51 
52 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_LOOPT_HH
53 #define OPENMESH_SUBDIVIDER_UNIFORM_LOOPT_HH
54 
55 
56 //== INCLUDES =================================================================
57 
58 #include <OpenMesh/Core/System/config.hh>
60 #include <OpenMesh/Core/Utils/vector_cast.hh>
61 #include <OpenMesh/Core/Utils/Property.hh>
62 // -------------------- STL
63 #include <vector>
64 #if defined(OM_CC_MIPS)
65 # include <math.h>
66 #else
67 # include <cmath>
68 #endif
69 
70 
71 //== NAMESPACE ================================================================
72 
73 namespace OpenMesh { // BEGIN_NS_OPENMESH
74 namespace Subdivider { // BEGIN_NS_DECIMATER
75 namespace Uniform { // BEGIN_NS_DECIMATER
76 
77 
78 //== CLASS DEFINITION =========================================================
79 
88 template <typename MeshType, typename RealType = float>
89 class LoopT : public SubdividerT<MeshType, RealType>
90 {
91 public:
92 
93  typedef RealType real_t;
94  typedef MeshType mesh_t;
96 
97  typedef std::pair< real_t, real_t > weight_t;
98  typedef std::vector< std::pair<real_t,real_t> > weights_t;
99 
100 public:
101 
102 
103  LoopT(void) : parent_t(), _1over8( 1.0/8.0 ), _3over8( 3.0/8.0 )
104  { init_weights(); }
105 
106 
107  LoopT( mesh_t& _m ) : parent_t(_m), _1over8( 1.0/8.0 ), _3over8( 3.0/8.0 )
108  { init_weights(); }
109 
110 
111  ~LoopT() {}
112 
113 
114 public:
115 
116 
117  const char *name() const { return "Uniform Loop"; }
118 
119 
121  void init_weights(size_t _max_valence=50)
122  {
123  weights_.resize(_max_valence);
124  std::generate(weights_.begin(), weights_.end(), compute_weight());
125  }
126 
127 
128 protected:
129 
130 
131  bool prepare( mesh_t& _m )
132  {
133  _m.add_property( vp_pos_ );
134  _m.add_property( ep_pos_ );
135  return true;
136  }
137 
138 
139  bool cleanup( mesh_t& _m )
140  {
141  _m.remove_property( vp_pos_ );
142  _m.remove_property( ep_pos_ );
143  return true;
144  }
145 
146 
147  bool subdivide( mesh_t& _m, size_t _n, const bool _update_points = true)
148  {
149 
151 
152  typename mesh_t::FaceIter fit, f_end;
153  typename mesh_t::EdgeIter eit, e_end;
154  typename mesh_t::VertexIter vit;
155 
156  // Do _n subdivisions
157  for (size_t i=0; i < _n; ++i)
158  {
159 
160  if(_update_points) {
161  // compute new positions for old vertices
162  for (vit = _m.vertices_begin(); vit != _m.vertices_end(); ++vit) {
163  smooth(_m, *vit);
164  }
165  }
166 
167  // Compute position for new vertices and store them in the edge property
168  for (eit=_m.edges_begin(); eit != _m.edges_end(); ++eit)
169  compute_midpoint( _m, *eit );
170 
171  // Split each edge at midpoint and store precomputed positions (stored in
172  // edge property ep_pos_) in the vertex property vp_pos_;
173 
174  // Attention! Creating new edges, hence make sure the loop ends correctly.
175  e_end = _m.edges_end();
176  for (eit=_m.edges_begin(); eit != e_end; ++eit)
177  split_edge(_m, *eit );
178 
179 
180  // Commit changes in topology and reconsitute consistency
181 
182  // Attention! Creating new faces, hence make sure the loop ends correctly.
183  f_end = _m.faces_end();
184  for (fit = _m.faces_begin(); fit != f_end; ++fit)
185  split_face(_m, *fit );
186 
187  if(_update_points) {
188  // Commit changes in geometry
189  for ( vit = _m.vertices_begin();
190  vit != _m.vertices_end(); ++vit) {
191  _m.set_point(*vit, _m.property( vp_pos_, *vit ) );
192  }
193  }
194 
195 
196 #if defined(_DEBUG) || defined(DEBUG)
197  // Now we have an consistent mesh!
198  assert( OpenMesh::Utils::MeshCheckerT<mesh_t>(_m).check() );
199 #endif
200  }
201 
202  return true;
203  }
204 
205 private:
206 
209  struct compute_weight
210  {
211  compute_weight() : valence(-1) { }
212  weight_t operator() (void)
213  {
214 #if !defined(OM_CC_MIPS)
215  using std::cos;
216 #endif
217  // 1
218  // alpha(n) = ---- * (40 - ( 3 + 2 cos( 2 Pi / n ) )� )
219  // 64
220 
221  if (++valence)
222  {
223  double inv_v = 1.0/double(valence);
224  double t = (3.0 + 2.0 * cos( 2.0 * M_PI * inv_v) );
225  double alpha = (40.0 - t * t)/64.0;
226 
227  return weight_t( 1.0-alpha, inv_v*alpha);
228  }
229  return weight_t(0.0, 0.0);
230  }
231  int valence;
232  };
233 
234 private: // topological modifiers
235 
236  void split_face(mesh_t& _m, const typename mesh_t::FaceHandle& _fh)
237  {
238  typename mesh_t::HalfedgeHandle
239  heh1(_m.halfedge_handle(_fh)),
240  heh2(_m.next_halfedge_handle(_m.next_halfedge_handle(heh1))),
241  heh3(_m.next_halfedge_handle(_m.next_halfedge_handle(heh2)));
242 
243  // Cutting off every corner of the 6_gon
244  corner_cutting( _m, heh1 );
245  corner_cutting( _m, heh2 );
246  corner_cutting( _m, heh3 );
247  }
248 
249 
250  void corner_cutting(mesh_t& _m, const typename mesh_t::HalfedgeHandle& _he)
251  {
252  // Define Halfedge Handles
253  typename mesh_t::HalfedgeHandle
254  heh1(_he),
255  heh5(heh1),
256  heh6(_m.next_halfedge_handle(heh1));
257 
258  // Cycle around the polygon to find correct Halfedge
259  for (; _m.next_halfedge_handle(_m.next_halfedge_handle(heh5)) != heh1;
260  heh5 = _m.next_halfedge_handle(heh5))
261  {}
262 
263  typename mesh_t::VertexHandle
264  vh1 = _m.to_vertex_handle(heh1),
265  vh2 = _m.to_vertex_handle(heh5);
266 
267  typename mesh_t::HalfedgeHandle
268  heh2(_m.next_halfedge_handle(heh5)),
269  heh3(_m.new_edge( vh1, vh2)),
270  heh4(_m.opposite_halfedge_handle(heh3));
271 
272  /* Intermediate result
273  *
274  * *
275  * 5 /|\
276  * /_ \
277  * vh2> * *
278  * /|\3 |\
279  * /_ \|4 \
280  * *----\*----\*
281  * 1 ^ 6
282  * vh1 (adjust_outgoing halfedge!)
283  */
284 
285  // Old and new Face
286  typename mesh_t::FaceHandle fh_old(_m.face_handle(heh6));
287  typename mesh_t::FaceHandle fh_new(_m.new_face());
288 
289 
290  // Re-Set Handles around old Face
291  _m.set_next_halfedge_handle(heh4, heh6);
292  _m.set_next_halfedge_handle(heh5, heh4);
293 
294  _m.set_face_handle(heh4, fh_old);
295  _m.set_face_handle(heh5, fh_old);
296  _m.set_face_handle(heh6, fh_old);
297  _m.set_halfedge_handle(fh_old, heh4);
298 
299  // Re-Set Handles around new Face
300  _m.set_next_halfedge_handle(heh1, heh3);
301  _m.set_next_halfedge_handle(heh3, heh2);
302 
303  _m.set_face_handle(heh1, fh_new);
304  _m.set_face_handle(heh2, fh_new);
305  _m.set_face_handle(heh3, fh_new);
306 
307  _m.set_halfedge_handle(fh_new, heh1);
308  }
309 
310 
311  void split_edge(mesh_t& _m, const typename mesh_t::EdgeHandle& _eh)
312  {
313  typename mesh_t::HalfedgeHandle
314  heh = _m.halfedge_handle(_eh, 0),
315  opp_heh = _m.halfedge_handle(_eh, 1);
316 
317  typename mesh_t::HalfedgeHandle new_heh, opp_new_heh, t_heh;
318  typename mesh_t::VertexHandle vh;
319  typename mesh_t::VertexHandle vh1(_m.to_vertex_handle(heh));
320  typename mesh_t::Point midP(_m.point(_m.to_vertex_handle(heh)));
321  midP += _m.point(_m.to_vertex_handle(opp_heh));
322  midP *= 0.5;
323 
324  // new vertex
325  vh = _m.new_vertex( midP );
326 
327  // memorize position, will be set later
328  _m.property( vp_pos_, vh ) = _m.property( ep_pos_, _eh );
329 
330 
331  // Re-link mesh entities
332  if (_m.is_boundary(_eh))
333  {
334  for (t_heh = heh;
335  _m.next_halfedge_handle(t_heh) != opp_heh;
336  t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
337  {}
338  }
339  else
340  {
341  for (t_heh = _m.next_halfedge_handle(opp_heh);
342  _m.next_halfedge_handle(t_heh) != opp_heh;
343  t_heh = _m.next_halfedge_handle(t_heh) )
344  {}
345  }
346 
347  new_heh = _m.new_edge(vh, vh1);
348  opp_new_heh = _m.opposite_halfedge_handle(new_heh);
349  _m.set_vertex_handle( heh, vh );
350 
351  _m.set_next_halfedge_handle(t_heh, opp_new_heh);
352  _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
353  _m.set_next_halfedge_handle(heh, new_heh);
354  _m.set_next_halfedge_handle(opp_new_heh, opp_heh);
355 
356  if (_m.face_handle(opp_heh).is_valid())
357  {
358  _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
359  _m.set_halfedge_handle(_m.face_handle(opp_new_heh), opp_new_heh);
360  }
361 
362  _m.set_face_handle( new_heh, _m.face_handle(heh) );
363  _m.set_halfedge_handle( vh, new_heh);
364  _m.set_halfedge_handle( _m.face_handle(heh), heh );
365  _m.set_halfedge_handle( vh1, opp_new_heh );
366 
367  // Never forget this, when playing with the topology
368  _m.adjust_outgoing_halfedge( vh );
369  _m.adjust_outgoing_halfedge( vh1 );
370  }
371 
372 private: // geometry helper
373 
374  void compute_midpoint(mesh_t& _m, const typename mesh_t::EdgeHandle& _eh)
375  {
376 #define V( X ) vector_cast< typename mesh_t::Normal >( X )
377  typename mesh_t::HalfedgeHandle heh, opp_heh;
378 
379  heh = _m.halfedge_handle( _eh, 0);
380  opp_heh = _m.halfedge_handle( _eh, 1);
381 
382  typename mesh_t::Point
383  pos(_m.point(_m.to_vertex_handle(heh)));
384 
385  pos += V( _m.point(_m.to_vertex_handle(opp_heh)) );
386 
387  // boundary edge: just average vertex positions
388  if (_m.is_boundary(_eh) )
389  {
390  pos *= 0.5;
391  }
392  else // inner edge: add neighbouring Vertices to sum
393  {
394  pos *= real_t(3.0);
395  pos += V(_m.point(_m.to_vertex_handle(_m.next_halfedge_handle(heh))));
396  pos += V(_m.point(_m.to_vertex_handle(_m.next_halfedge_handle(opp_heh))));
397  pos *= _1over8;
398  }
399  _m.property( ep_pos_, _eh ) = pos;
400 #undef V
401  }
402 
403  void smooth(mesh_t& _m, const typename mesh_t::VertexHandle& _vh)
404  {
405  typename mesh_t::Point pos(0.0,0.0,0.0);
406 
407  if (_m.is_boundary(_vh) ) // if boundary: Point 1-6-1
408  {
409  typename mesh_t::HalfedgeHandle heh, prev_heh;
410  heh = _m.halfedge_handle( _vh );
411 
412  if ( heh.is_valid() )
413  {
414  assert( _m.is_boundary( _m.edge_handle( heh ) ) );
415 
416  prev_heh = _m.prev_halfedge_handle( heh );
417 
418  typename mesh_t::VertexHandle
419  to_vh = _m.to_vertex_handle( heh ),
420  from_vh = _m.from_vertex_handle( prev_heh );
421 
422  // ( v_l + 6 v + v_r ) / 8
423  pos = _m.point( _vh );
424  pos *= real_t(6.0);
425  pos += vector_cast< typename mesh_t::Normal >( _m.point( to_vh ) );
426  pos += vector_cast< typename mesh_t::Normal >( _m.point( from_vh ) );
427  pos *= _1over8;
428 
429  }
430  else
431  return;
432  }
433  else // inner vertex: (1-a) * p + a/n * Sum q, q in one-ring of p
434  {
435  typedef typename mesh_t::Normal Vec;
436  typename mesh_t::VertexVertexIter vvit;
437  size_t valence(0);
438 
439  // Calculate Valence and sum up neighbour points
440  for (vvit=_m.vv_iter(_vh); vvit.is_valid(); ++vvit) {
441  ++valence;
442  pos += vector_cast< Vec >( _m.point(*vvit) );
443  }
444  pos *= weights_[valence].second; // alpha(n)/n * Sum q, q in one-ring of p
445  pos += weights_[valence].first
446  * vector_cast<Vec>(_m.point(_vh)); // + (1-a)*p
447  }
448 
449  _m.property( vp_pos_, _vh ) = pos;
450  }
451 
452 private: // data
453 
456 
457  weights_t weights_;
458 
459  const real_t _1over8;
460  const real_t _3over8;
461 
462 };
463 
464 
465 //=============================================================================
466 } // END_NS_UNIFORM
467 } // END_NS_SUBDIVIDER
468 } // END_NS_OPENMESH
469 //=============================================================================
470 #endif // OPENMESH_SUBDIVIDER_UNIFORM_COMPOSITELOOPT_HH defined
471 //=============================================================================
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:158
bool operator()(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide the mesh _m _n times.
Definition: SubdividerT.hh:121
Check integrity of mesh.
Definition: MeshCheckerT.hh:71
void init_weights(size_t _max_valence=50)
Pre-compute weights.
Definition: LoopT.hh:121
vector_caster< dst_t, src_t >::return_type vector_cast(const src_t &_src)
Cast vector type to another vector type by copying the vector elements.
Definition: vector_cast.hh:170
Kernel::Normal Normal
Normal type.
Definition: PolyMeshT.hh:110
bool cleanup(mesh_t &_m)
Cleanup mesh after usage, e.g. remove added properties.
Definition: LoopT.hh:139
VertexHandle new_vertex()
Uses default copy and assignment operator.
Definition: PolyMeshT.hh:189
bool subdivide(mesh_t &_m, size_t _n, const bool _update_points=true)
Subdivide mesh _m _n times.
Definition: LoopT.hh:147
Abstract base class for uniform subdivision algorithms.
Definition: SubdividerT.hh:87
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:132
const char * name() const
Return name of subdivision algorithm.
Definition: LoopT.hh:117
Triangle mesh based on the ArrayKernel.
Definition: TriMesh_ArrayKernelT.hh:91
bool prepare(mesh_t &_m)
Prepare mesh, e.g. add properties.
Definition: LoopT.hh:131
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:108
Uniform Loop subdivision algorithm.
Definition: LoopT.hh:89

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