OpenMesh

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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