| 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
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>
61 #include <OpenMesh/Tools/Subdivider/Uniform/SubdividerT.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;
97 typedef SubdividerT< mesh_t, real_t > parent_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
211 struct compute_weight
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
456 OpenMesh::VPropHandleT< typename mesh_t::Point > vp_pos_;
457 OpenMesh::EPropHandleT< typename mesh_t::Point > ep_pos_;
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 //=============================================================================
OpenMesh::Subdivider::Uniform::LoopT::subdivide
bool subdivide(mesh_t &_m, size_t _n, const bool _update_points=true)
Subdivide mesh _m _n times.
Definition: LoopT.hh:149
OpenMesh::VPropHandleT< typename mesh_t::Point >
OpenMesh::PolyMeshT::Normal
Kernel::Normal Normal
Normal type.
Definition: PolyMeshT.hh:114
OpenMesh::Subdivider::Uniform::LoopT::init_weights
void init_weights(size_t _max_valence=50)
Pre-compute weights.
Definition: LoopT.hh:123
OpenMesh::Subdivider::Uniform::LoopT
Uniform Loop subdivision algorithm.
Definition: LoopT.hh:91
OpenMesh::Subdivider::Uniform::LoopT::prepare
bool prepare(mesh_t &_m)
Prepare mesh, e.g. add properties.
Definition: LoopT.hh:133
SubdividerT.hh
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:136
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:122
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::PolyMeshT::VertexVertexIter
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:162
OpenMesh::EPropHandleT< typename mesh_t::Point >
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:112
OpenMesh::Subdivider::Uniform::SubdividerT
Abstract base class for uniform subdivision algorithms.
Definition: SubdividerT.hh:88
OpenMesh::Subdivider::Uniform::LoopT::name
const char * name() const
Return name of subdivision algorithm.
Definition: LoopT.hh:119
OpenMesh::Utils::MeshCheckerT
Check integrity of mesh.
Definition: MeshCheckerT.hh:73
OpenMesh::Subdivider::Uniform::LoopT::cleanup
bool cleanup(mesh_t &_m)
Cleanup mesh after usage, e.g. remove added properties.
Definition: LoopT.hh:141
OpenMesh::vector_cast
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