| OpenMesh

Sqrt3T.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 Sqrt3T
51 //
52 //=============================================================================
53
54 #ifndef OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
55 #define OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
56
57
58 //== INCLUDES =================================================================
59
60 #include <OpenMesh/Core/Mesh/Handles.hh>
61 #include <OpenMesh/Core/System/config.hh>
62 #include <OpenMesh/Tools/Subdivider/Uniform/SubdividerT.hh>
63 #if defined(_DEBUG) || defined(DEBUG)
64 // Makes life lot easier, when playing/messing around with low-level topology
65 // changing methods of OpenMesh
66 # include <OpenMesh/Tools/Utils/MeshCheckerT.hh>
67 # define ASSERT_CONSISTENCY( T, m ) \
68 assert(OpenMesh::Utils::MeshCheckerT<T>(m).check())
69 #else
70 # define ASSERT_CONSISTENCY( T, m )
71 #endif
72 // -------------------- STL
73 #include <vector>
74 #if defined(OM_CC_MIPS)
75 # include <math.h>
76 #else
77 # include <cmath>
78 #endif
79
80
81 //== NAMESPACE ================================================================
82
83 namespace OpenMesh { // BEGIN_NS_OPENMESH
84 namespace Subdivider { // BEGIN_NS_DECIMATER
85 namespace Uniform { // BEGIN_NS_DECIMATER
86
87
88 //== CLASS DEFINITION =========================================================
89
90
97 template <typename MeshType, typename RealType = double>
98 class Sqrt3T : public SubdividerT< MeshType, RealType >
99 {
100 public:
101
102 typedef RealType real_t;
103 typedef MeshType mesh_t;
104 typedef SubdividerT< mesh_t, real_t > parent_t;
105
106 typedef std::pair< real_t, real_t > weight_t;
107 typedef std::vector< std::pair<real_t,real_t> > weights_t;
108
109 public:
110
111
112 Sqrt3T(void) : parent_t(), _1over3( real_t(1.0/3.0) ), _1over27( real_t(1.0/27.0) )
113 { init_weights(); }
114
115 explicit Sqrt3T(MeshType &_m) : parent_t(_m), _1over3( real_t(1.0/3.0) ), _1over27( real_t(1.0/27.0) )
116 { init_weights(); }
117
118 virtual ~Sqrt3T() {}
119
120
121 public:
122
123
124 const char *name() const override { return "Uniform Sqrt3"; }
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( MeshType& _m ) override
139 {
140 _m.request_edge_status();
141 _m.add_property( vp_pos_ );
142 _m.add_property( ep_nv_ );
143 _m.add_property( mp_gen_ );
144 _m.property( mp_gen_ ) = 0;
145
146 return _m.has_edge_status() && vp_pos_.is_valid()
147 && ep_nv_.is_valid() && mp_gen_.is_valid();
148 }
149
150
151 bool cleanup( MeshType& _m ) override
152 {
153 _m.release_edge_status();
154 _m.remove_property( vp_pos_ );
155 _m.remove_property( ep_nv_ );
156 _m.remove_property( mp_gen_ );
157 return true;
158 }
159
160 bool subdivide( MeshType& _m, size_t _n , const bool _update_points = true) override
161 {
162
164
165 typename MeshType::Point pos(0,0,0), zero(0,0,0);
166 size_t &gen = _m.property( mp_gen_ );
167
168 for (size_t l=0; l<_n; ++l)
169 {
170 // tag existing edges
171 for (auto eh : _m.edges())
172 {
173 _m.status( eh ).set_tagged( true );
174 if ( (gen%2) && _m.is_boundary(eh) )
175 compute_new_boundary_points( _m, eh ); // *) creates new vertices
176 }
177
178 // do relaxation of old vertices, but store new pos in property vp_pos_
179
180 for (auto vh : _m.vertices())
181 {
182 if ( _m.is_boundary(vh) )
183 {
184 if ( gen%2 )
185 {
186 auto heh = _m.halfedge_handle(vh);
187 if (heh.is_valid()) // skip isolated newly inserted vertices *)
188 {
189 auto prev_heh = _m.prev_halfedge_handle(heh);
190
191 assert( _m.is_boundary(heh ) );
192 assert( _m.is_boundary(prev_heh) );
193
194 pos = _m.point(_m.to_vertex_handle(heh));
195 pos += _m.point(_m.from_vertex_handle(prev_heh));
196 pos *= real_t(4.0);
197
198 pos += real_t(19.0) * _m.point( vh );
199 pos *= _1over27;
200
201 _m.property( vp_pos_, vh ) = pos;
202 }
203 }
204 else
205 _m.property( vp_pos_, vh ) = _m.point( vh );
206 }
207 else
208 {
209 size_t valence=0;
210
211 pos = zero;
212 for ( auto vvh : _m.vv_range(vh))
213 {
214 pos += _m.point( vvh );
215 ++valence;
216 }
217 pos *= weights_[ valence ].second;
218 pos += weights_[ valence ].first * _m.point(vh);
219 _m.property( vp_pos_, vh ) = pos;
220 }
221 }
222
223 // insert new vertices, but store pos in vp_pos_
224 for (auto fh : _m.faces())
225 {
226 if ( (gen%2) && _m.is_boundary(fh))
227 {
228 boundary_split( _m, fh );
229 }
230 else
231 {
232 auto fvit = _m.fv_iter( fh );
233 pos = _m.point( *fvit);
234 pos += _m.point(*(++fvit));
235 pos += _m.point(*(++fvit));
236 pos *= _1over3;
237 auto vh = _m.add_vertex( zero );
238 _m.property( vp_pos_, vh ) = pos;
239 _m.split( fh, vh );
240 }
241 }
242
243 // commit new positions (now iterating over all vertices)
244 for (auto vh : _m.vertices())
245 _m.set_point(vh, _m.property( vp_pos_, vh ) );
246
247 // flip old edges
248 for (auto eh : _m.edges())
249 if ( _m.status( eh ).tagged() && !_m.is_boundary( eh ) )
250 _m.flip(eh);
251
252 // Now we have an consistent mesh!
253 ASSERT_CONSISTENCY( MeshType, _m );
254
255 // increase generation by one
256 ++gen;
257 }
258 return true;
259 }
260
261 private:
262
265 struct compute_weight
266 {
267 compute_weight() : valence(-1) { }
268 weight_t operator() (void)
269 {
270 #if !defined(OM_CC_MIPS)
271 using std::cos;
272 #endif
273 if (++valence)
274 {
275 real_t alpha = real_t( (4.0-2.0*cos(2.0*M_PI / real_t(valence)) )/9.0 );
276 return weight_t( real_t(1)-alpha, alpha/real_t(valence) );
277 }
278 return weight_t(real_t(0.0), real_t(0.0) );
279 }
280 int valence;
281 };
282
283 private:
284
285 // Pre-compute location of new boundary points for odd generations
286 // and store them in the edge property ep_nv_;
287 void compute_new_boundary_points( MeshType& _m,
288 const typename MeshType::EdgeHandle& _eh)
289 {
290 assert( _m.is_boundary(_eh) );
291
292 typename MeshType::HalfedgeHandle heh;
293 typename MeshType::VertexHandle vh1, vh2, vh3, vh4, vhl, vhr;
294 typename MeshType::Point zero(0,0,0), P1, P2, P3, P4;
295
296 /*
297 // *---------*---------*
298 // / \ / \ / \
299 // / \ / \ / \
300 // / \ / \ / \
301 // / \ / \ / \
302 // *---------*--#---#--*---------*
303 //
304 // ^ ^ ^ ^ ^ ^
305 // P1 P2 pl pr P3 P4
306 */
307 // get halfedge pointing from P3 to P2 (outer boundary halfedge)
308
309 heh = _m.halfedge_handle(_eh,
310 _m.is_boundary(_m.halfedge_handle(_eh,1)));
311
312 assert( _m.is_boundary( _m.next_halfedge_handle( heh ) ) );
313 assert( _m.is_boundary( _m.prev_halfedge_handle( heh ) ) );
314
315 vh1 = _m.to_vertex_handle( _m.next_halfedge_handle( heh ) );
316 vh2 = _m.to_vertex_handle( heh );
317 vh3 = _m.from_vertex_handle( heh );
318 vh4 = _m.from_vertex_handle( _m.prev_halfedge_handle( heh ));
319
320 P1 = _m.point(vh1);
321 P2 = _m.point(vh2);
322 P3 = _m.point(vh3);
323 P4 = _m.point(vh4);
324
325 vhl = _m.add_vertex(zero);
326 vhr = _m.add_vertex(zero);
327
328 _m.property(vp_pos_, vhl ) = (P1 + real_t(16.0f) * P2 + real_t(10.0f) * P3) * _1over27;
329 _m.property(vp_pos_, vhr ) = ( real_t(10.0f) * P2 + real_t(16.0f) * P3 + P4) * _1over27;
330 _m.property(ep_nv_, _eh).first = vhl;
331 _m.property(ep_nv_, _eh).second = vhr;
332 }
333
334
335 void boundary_split( MeshType& _m, const typename MeshType::FaceHandle& _fh )
336 {
337 assert( _m.is_boundary(_fh) );
338
339 typename MeshType::VertexHandle vhl, vhr;
340 typename MeshType::FaceEdgeIter fe_it;
341 typename MeshType::HalfedgeHandle heh;
342
343 // find boundary edge
344 for( fe_it=_m.fe_iter( _fh ); fe_it.is_valid() && !_m.is_boundary( *fe_it ); ++fe_it ) {};
345
346 // use precomputed, already inserted but not linked vertices
347 vhl = _m.property(ep_nv_, *fe_it).first;
348 vhr = _m.property(ep_nv_, *fe_it).second;
349
350 /*
351 // *---------*---------*
352 // / \ / \ / \
353 // / \ / \ / \
354 // / \ / \ / \
355 // / \ / \ / \
356 // *---------*--#---#--*---------*
357 //
358 // ^ ^ ^ ^ ^ ^
359 // P1 P2 pl pr P3 P4
360 */
361 // get halfedge pointing from P2 to P3 (inner boundary halfedge)
362
363 heh = _m.halfedge_handle(*fe_it,
364 _m.is_boundary(_m.halfedge_handle(*fe_it,0)));
365
366 typename MeshType::HalfedgeHandle pl_P3;
367
368 // split P2->P3 (heh) in P2->pl (heh) and pl->P3
369 boundary_split( _m, heh, vhl ); // split edge
370 pl_P3 = _m.next_halfedge_handle( heh ); // store next halfedge handle
371 boundary_split( _m, heh ); // split face
372
373 // split pl->P3 in pl->pr and pr->P3
374 boundary_split( _m, pl_P3, vhr );
375 boundary_split( _m, pl_P3 );
376
377 assert( _m.is_boundary( vhl ) && _m.halfedge_handle(vhl).is_valid() );
378 assert( _m.is_boundary( vhr ) && _m.halfedge_handle(vhr).is_valid() );
379 }
380
381 void boundary_split(MeshType& _m,
382 const typename MeshType::HalfedgeHandle& _heh,
383 const typename MeshType::VertexHandle& _vh)
384 {
385 assert( _m.is_boundary( _m.edge_handle(_heh) ) );
386
387 typename MeshType::HalfedgeHandle
388 heh(_heh),
389 opp_heh( _m.opposite_halfedge_handle(_heh) ),
390 new_heh, opp_new_heh;
391 typename MeshType::VertexHandle to_vh(_m.to_vertex_handle(heh));
392 typename MeshType::HalfedgeHandle t_heh;
393
394 /*
395 * P5
396 * *
397 * /|\
398 * / \
399 * / \
400 * / \
401 * / \
402 * /_ heh new \
403 * *-----\*-----\*\-----*
404 * ^ ^ t_heh
405 * _vh to_vh
406 *
407 * P1 P2 P3 P4
408 */
409 // Re-Setting Handles
410
411 // find halfedge point from P4 to P3
412 for(t_heh = heh;
413 _m.next_halfedge_handle(t_heh) != opp_heh;
414 t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
415 {}
416
417 assert( _m.is_boundary( t_heh ) );
418
419 new_heh = _m.new_edge( _vh, to_vh );
420 opp_new_heh = _m.opposite_halfedge_handle(new_heh);
421
422 // update halfedge connectivity
423
424 _m.set_next_halfedge_handle(t_heh, opp_new_heh); // P4-P3 -> P3-P2
425 // P2-P3 -> P3-P5
426 _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
427 _m.set_next_halfedge_handle(heh, new_heh); // P1-P2 -> P2-P3
428 _m.set_next_halfedge_handle(opp_new_heh, opp_heh); // P3-P2 -> P2-P1
429
430 // both opposite halfedges point to same face
431 _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
432
433 // let heh finally point to new inserted vertex
434 _m.set_vertex_handle(heh, _vh);
435
436 // let heh and new_heh point to same face
437 _m.set_face_handle(new_heh, _m.face_handle(heh));
438
439 // let opp_new_heh be the new outgoing halfedge for to_vh
440 // (replaces for opp_heh)
441 _m.set_halfedge_handle( to_vh, opp_new_heh );
442
443 // let opp_heh be the outgoing halfedge for _vh
444 _m.set_halfedge_handle( _vh, opp_heh );
445 }
446
447 void boundary_split( MeshType& _m,
448 const typename MeshType::HalfedgeHandle& _heh)
449 {
450 assert( _m.is_boundary( _m.opposite_halfedge_handle( _heh ) ) );
451
452 typename MeshType::HalfedgeHandle
453 heh(_heh),
454 n_heh(_m.next_halfedge_handle(heh));
455
456 typename MeshType::VertexHandle
457 to_vh(_m.to_vertex_handle(heh));
458
459 typename MeshType::HalfedgeHandle
460 heh2(_m.new_edge(to_vh,
461 _m.to_vertex_handle(_m.next_halfedge_handle(n_heh)))),
462 heh3(_m.opposite_halfedge_handle(heh2));
463
464 typename MeshType::FaceHandle
465 new_fh(_m.new_face()),
466 fh(_m.face_handle(heh));
467
468 // Relink (half)edges
469
470 #define set_next_heh set_next_halfedge_handle
471 #define next_heh next_halfedge_handle
472
473 _m.set_face_handle(heh, new_fh);
474 _m.set_face_handle(heh2, new_fh);
475 _m.set_next_heh(heh2, _m.next_heh(_m.next_heh(n_heh)));
476 _m.set_next_heh(heh, heh2);
477 _m.set_face_handle( _m.next_heh(heh2), new_fh);
478
479 // _m.set_face_handle( _m.next_heh(_m.next_heh(heh2)), new_fh);
480
481 _m.set_next_heh(heh3, n_heh);
482 _m.set_next_heh(_m.next_halfedge_handle(n_heh), heh3);
483 _m.set_face_handle(heh3, fh);
484 // _m.set_face_handle(n_heh, fh);
485
486 _m.set_halfedge_handle( fh, n_heh);
487 _m.set_halfedge_handle(new_fh, heh);
488
489 #undef set_next_halfedge_handle
490 #undef next_halfedge_handle
491
492 }
493
494 private:
495
496 weights_t weights_;
497 OpenMesh::VPropHandleT< typename MeshType::Point > vp_pos_;
498 OpenMesh::EPropHandleT< std::pair< typename MeshType::VertexHandle,
499 typename MeshType::VertexHandle> > ep_nv_;
500 OpenMesh::MPropHandleT< size_t > mp_gen_;
501
502 const real_t _1over3;
503 const real_t _1over27;
504 };
505
506
507 //=============================================================================
508 } // END_NS_UNIFORM
509 } // END_NS_SUBDIVIDER
510 } // END_NS_OPENMESH
511 //=============================================================================
512 #endif // OPENMESH_SUBDIVIDER_UNIFORM_SQRT3T_HH
513 //=============================================================================
OpenMesh::VPropHandleT< typename MeshType::Point >
OpenMesh::Subdivider::Uniform::Sqrt3T::prepare
bool prepare(MeshType &_m) override
Prepare mesh, e.g. add properties.
Definition: Sqrt3T.hh:138
OpenMesh::BaseHandle::is_valid
bool is_valid() const
The handle is valid iff the index is not negative.
Definition: Handles.hh:72
OpenMesh::Subdivider::Uniform::Sqrt3T::subdivide
bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true) override
Subdivide mesh _m _n times.
Definition: Sqrt3T.hh:160
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::EPropHandleT
Handle representing an edge property.
Definition: Property.hh:514
OpenMesh::Subdivider::Uniform::Sqrt3T::cleanup
bool cleanup(MeshType &_m) override
Cleanup mesh after usage, e.g. remove added properties.
Definition: Sqrt3T.hh:151
OpenMesh::Subdivider::Uniform::Sqrt3T
Uniform Sqrt3 subdivision algorithm
Definition: Sqrt3T.hh:98
OpenMesh::Subdivider::Uniform::SubdividerT
Abstract base class for uniform subdivision algorithms.
Definition: SubdividerT.hh:88
OpenMesh::MPropHandleT< size_t >
OpenMesh::Subdivider::Uniform::Sqrt3T::init_weights
void init_weights(size_t _max_valence=50)
Pre-compute weights.
Definition: Sqrt3T.hh:128
SubdividerT.hh
OpenMesh::Subdivider::Uniform::Sqrt3T::name
const char * name() const override
Return name of subdivision algorithm.
Definition: Sqrt3T.hh:124
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59