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

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