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