| OpenMesh

CatmullClarkT_impl.hh
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 // CLASS CatmullClarkT - IMPLEMENTATION
45 //
46 //=============================================================================
47
48 #define OPENMESH_SUBDIVIDER_UNIFORM_CATMULLCLARK_CC
49
50 //== INCLUDES =================================================================
51
52 #include "CatmullClarkT.hh"
53 #include <OpenMesh/Tools/Utils/MeshCheckerT.hh>
54
55 //== NAMESPACES ===============================================================
56
57 namespace OpenMesh { // BEGIN_NS_OPENMESH
58 namespace Subdivider { // BEGIN_NS_SUBVIDER
59 namespace Uniform { // BEGIN_NS_UNIFORM
60
61 //== IMPLEMENTATION ==========================================================
62
63 template <typename MeshType, typename RealType>
64 bool
65 CatmullClarkT< MeshType, RealType >::prepare( MeshType& _m )
66 {
67 _m.add_property( vp_pos_ );
68 _m.add_property( ep_pos_ );
69 _m.add_property( fp_pos_ );
70 _m.add_property( creaseWeights_ );
71
72 // initialize all weights to 0 (= smooth edge)
73 for( EdgeIter e_it = _m.edges_begin(); e_it != _m.edges_end(); ++e_it)
74 _m.property(creaseWeights_, *e_it ) = 0.0;
75
76 return true;
77 }
78
79 //-----------------------------------------------------------------------------
80
81 template <typename MeshType, typename RealType>
82 bool
83 CatmullClarkT<MeshType,RealType>::cleanup( MeshType& _m )
84 {
85 _m.remove_property( vp_pos_ );
86 _m.remove_property( ep_pos_ );
87 _m.remove_property( fp_pos_ );
88 _m.remove_property( creaseWeights_ );
89 return true;
90 }
91
92 //-----------------------------------------------------------------------------
93
94 template <typename MeshType, typename RealType>
95 bool
96 CatmullClarkT<MeshType,RealType>::subdivide( MeshType& _m , size_t _n , const bool _update_points)
97 {
98 // Do _n subdivisions
99 for ( size_t i = 0; i < _n; ++i)
100 {
101
102 // Compute face centroid
103 FaceIter f_itr = _m.faces_begin();
104 FaceIter f_end = _m.faces_end();
105 for ( ; f_itr != f_end; ++f_itr)
106 {
107 Point centroid;
108 _m.calc_face_centroid( *f_itr, centroid);
109 _m.property( fp_pos_, *f_itr ) = centroid;
110 }
111
112 // Compute position for new (edge-) vertices and store them in the edge property
113 EdgeIter e_itr = _m.edges_begin();
114 EdgeIter e_end = _m.edges_end();
115 for ( ; e_itr != e_end; ++e_itr)
116 compute_midpoint( _m, *e_itr, _update_points );
117
118 // position updates activated?
119 if(_update_points)
120 {
121 // compute new positions for old vertices
122 VertexIter v_itr = _m.vertices_begin();
123 VertexIter v_end = _m.vertices_end();
124 for ( ; v_itr != v_end; ++v_itr)
125 update_vertex( _m, *v_itr );
126
127 // Commit changes in geometry
128 v_itr = _m.vertices_begin();
129 for ( ; v_itr != v_end; ++v_itr)
130 _m.set_point(*v_itr, _m.property( vp_pos_, *v_itr ) );
131 }
132
133 // Split each edge at midpoint stored in edge property ep_pos_;
134 // Attention! Creating new edges, hence make sure the loop ends correctly.
135 e_itr = _m.edges_begin();
136 for ( ; e_itr != e_end; ++e_itr)
137 split_edge( _m, *e_itr );
138
139 // Commit changes in topology and reconsitute consistency
140 // Attention! Creating new faces, hence make sure the loop ends correctly.
141 f_itr = _m.faces_begin();
142 for ( ; f_itr != f_end; ++f_itr)
143 split_face( _m, *f_itr);
144
145
146 #if defined(_DEBUG) || defined(DEBUG)
147 // Now we have an consistent mesh!
148 assert( OpenMesh::Utils::MeshCheckerT<MeshType>(_m).check() );
149 #endif
150 }
151
152 _m.update_normals();
153
154 return true;
155 }
156
157 //-----------------------------------------------------------------------------
158
159 template <typename MeshType, typename RealType>
160 void
161 CatmullClarkT<MeshType,RealType>::split_face( MeshType& _m, const FaceHandle& _fh)
162 {
163 /*
164 Split an n-gon into n quads by connecting
165 each vertex of fh to vh.
166
167 - _fh will remain valid (it will become one of the quads)
168 - the halfedge handles of the new quads will
169 point to the old halfedges
170 */
171
172 // Since edges already refined (valence*2)
173 size_t valence = _m.valence(_fh)/2;
174
175 // new mesh vertex from face centroid
176 VertexHandle vh = _m.add_vertex(_m.property( fp_pos_, _fh ));
177
178 HalfedgeHandle hend = _m.halfedge_handle(_fh);
179 HalfedgeHandle hh = _m.next_halfedge_handle(hend);
180
181 HalfedgeHandle hold = _m.new_edge(_m.to_vertex_handle(hend), vh);
182
183 _m.set_next_halfedge_handle(hend, hold);
184 _m.set_face_handle(hold, _fh);
185
186 hold = _m.opposite_halfedge_handle(hold);
187
188 for(size_t i = 1; i < valence; i++)
189 {
190 HalfedgeHandle hnext = _m.next_halfedge_handle(hh);
191
192 FaceHandle fnew = _m.new_face();
193
194 _m.set_halfedge_handle(fnew, hh);
195
196 HalfedgeHandle hnew = _m.new_edge(_m.to_vertex_handle(hnext), vh);
197
198 _m.set_face_handle(hnew, fnew);
199 _m.set_face_handle(hold, fnew);
200 _m.set_face_handle(hh, fnew);
201 _m.set_face_handle(hnext, fnew);
202
203 _m.set_next_halfedge_handle(hnew, hold);
204 _m.set_next_halfedge_handle(hold, hh);
205 _m.set_next_halfedge_handle(hh, hnext);
206 hh = _m.next_halfedge_handle(hnext);
207 _m.set_next_halfedge_handle(hnext, hnew);
208
209 hold = _m.opposite_halfedge_handle(hnew);
210 }
211
212 _m.set_next_halfedge_handle(hold, hh);
213 _m.set_next_halfedge_handle(hh, hend);
214 hh = _m.next_halfedge_handle(hend);
215 _m.set_next_halfedge_handle(hend, hh);
216 _m.set_next_halfedge_handle(hh, hold);
217
218 _m.set_face_handle(hold, _fh);
219
220 _m.set_halfedge_handle(vh, hold);
221 }
222
223 //-----------------------------------------------------------------------------
224
225 template <typename MeshType, typename RealType>
226 void
227 CatmullClarkT<MeshType,RealType>::split_edge( MeshType& _m, const EdgeHandle& _eh)
228 {
229 HalfedgeHandle heh = _m.halfedge_handle(_eh, 0);
230 HalfedgeHandle opp_heh = _m.halfedge_handle(_eh, 1);
231
232 HalfedgeHandle new_heh, opp_new_heh, t_heh;
233 VertexHandle vh;
234 VertexHandle vh1( _m.to_vertex_handle(heh));
235 Point zero(0,0,0);
236
237 // new vertex
238 vh = _m.new_vertex( zero );
239 _m.set_point( vh, _m.property( ep_pos_, _eh ) );
240
241 // Re-link mesh entities
242 if (_m.is_boundary(_eh))
243 {
244 for (t_heh = heh;
245 _m.next_halfedge_handle(t_heh) != opp_heh;
246 t_heh = _m.opposite_halfedge_handle(_m.next_halfedge_handle(t_heh)))
247 {}
248 }
249 else
250 {
251 for (t_heh = _m.next_halfedge_handle(opp_heh);
252 _m.next_halfedge_handle(t_heh) != opp_heh;
253 t_heh = _m.next_halfedge_handle(t_heh) )
254 {}
255 }
256
257 new_heh = _m.new_edge(vh, vh1);
258 opp_new_heh = _m.opposite_halfedge_handle(new_heh);
259 _m.set_vertex_handle( heh, vh );
260
261 _m.set_next_halfedge_handle(t_heh, opp_new_heh);
262 _m.set_next_halfedge_handle(new_heh, _m.next_halfedge_handle(heh));
263 _m.set_next_halfedge_handle(heh, new_heh);
264 _m.set_next_halfedge_handle(opp_new_heh, opp_heh);
265
266 if (_m.face_handle(opp_heh).is_valid())
267 {
268 _m.set_face_handle(opp_new_heh, _m.face_handle(opp_heh));
269 _m.set_halfedge_handle(_m.face_handle(opp_new_heh), opp_new_heh);
270 }
271
272 if( _m.face_handle(heh).is_valid())
273 {
274 _m.set_face_handle( new_heh, _m.face_handle(heh) );
275 _m.set_halfedge_handle( _m.face_handle(heh), heh );
276 }
277
278 _m.set_halfedge_handle( vh, new_heh);
279 _m.set_halfedge_handle( vh1, opp_new_heh );
280
281 // Never forget this, when playing with the topology
282 _m.adjust_outgoing_halfedge( vh );
283 _m.adjust_outgoing_halfedge( vh1 );
284 }
285
286 //-----------------------------------------------------------------------------
287
288 template <typename MeshType, typename RealType>
289 void
290 CatmullClarkT<MeshType,RealType>::compute_midpoint( MeshType& _m, const EdgeHandle& _eh, const bool _update_points)
291 {
292 HalfedgeHandle heh, opp_heh;
293
294 heh = _m.halfedge_handle( _eh, 0);
295 opp_heh = _m.halfedge_handle( _eh, 1);
296
297 Point pos( _m.point( _m.to_vertex_handle( heh)));
298
299 pos += _m.point( _m.to_vertex_handle( opp_heh));
300
301 // boundary edge: just average vertex positions
302 // this yields the [1/2 1/2] mask
303 if (_m.is_boundary(_eh) || !_update_points)
304 {
305 pos *= static_cast<RealType>(0.5);
306 }
307 // else if (_m.status(_eh).selected() )
308 // {
309 // pos *= 0.5; // change this
310 // }
311
312 else // inner edge: add neighbouring Vertices to sum
313 // this yields the [1/16 1/16; 3/8 3/8; 1/16 1/16] mask
314 {
315 pos += _m.property(fp_pos_, _m.face_handle(heh));
316 pos += _m.property(fp_pos_, _m.face_handle(opp_heh));
317 pos *= static_cast<RealType>(0.25);
318 }
319 _m.property( ep_pos_, _eh ) = pos;
320 }
321
322 //-----------------------------------------------------------------------------
323
324 template <typename MeshType, typename RealType>
325 void
326 CatmullClarkT<MeshType,RealType>::update_vertex( MeshType& _m, const VertexHandle& _vh)
327 {
328 Point pos(0.0,0.0,0.0);
329
330 // TODO boundary, Extraordinary Vertex and Creased Surfaces
331 // see "A Factored Approach to Subdivision Surfaces"
332 // http://faculty.cs.tamu.edu/schaefer/research/tutorial.pdf
333 // and http://www.cs.utah.edu/~lacewell/subdeval
334 if ( _m.is_boundary( _vh))
335 {
336 Normal Vec;
337 pos = _m.point(_vh);
338 VertexEdgeIter ve_itr;
339 for ( ve_itr = _m.ve_iter( _vh); ve_itr.is_valid(); ++ve_itr)
340 if ( _m.is_boundary( *ve_itr))
341 pos += _m.property( ep_pos_, *ve_itr);
342 pos /= static_cast<typename vector_traits<typename MeshType::Point>::value_type>(3.0);
343 }
344 else // inner vertex
345 {
346 /* For each (non boundary) vertex V, introduce a new vertex whose
347 position is F/n + 2E/n + (n-3)V/n where F is the average of
348 the new face vertices of all faces adjacent to the old vertex
349 V, E is the average of the midpoints of all edges incident
350 on the old vertex V, and n is the number of edges incident on
351 the vertex.
352 */
353
354 /*
355 Normal Vec;
356 VertexEdgeIter ve_itr;
357 double valence(0.0);
358
359 // R = Calculate Valence and sum of edge midpoints
360 for ( ve_itr = _m.ve_iter( _vh); ve_itr; ++ve_itr)
361 {
362 valence+=1.0;
363 pos += _m.property(ep_pos_, *ve_itr);
364 }
365 pos /= valence*valence;
366 */
367
368 RealType valence(0.0);
369 VOHIter voh_it = _m.voh_iter( _vh );
370 for( ; voh_it.is_valid(); ++voh_it )
371 {
372 pos += _m.point( _m.to_vertex_handle( *voh_it ) );
373 valence+=1.0;
374 }
375 pos /= valence*valence;
376
377 VertexFaceIter vf_itr;
378 Point Q(0, 0, 0);
379
380 for ( vf_itr = _m.vf_iter( _vh); vf_itr.is_valid(); ++vf_itr) //, neigboring_faces += 1.0 )
381 {
382 Q += _m.property(fp_pos_, *vf_itr);
383 }
384
385 Q /= valence*valence;//neigboring_faces;
386
387 pos += _m.point(_vh) * (valence - RealType(2.0) )/valence + Q;
388 // pos = vector_cast<Vec>(_m.point(_vh));
389 }
390
391 _m.property( vp_pos_, _vh ) = pos;
392 }
393
394 //-----------------------------------------------------------------------------
395
396 //=============================================================================
397 } // END_NS_UNIFORM
398 } // END_NS_SUBDIVIDER
399 } // END_NS_OPENMESH
400 //=============================================================================
OpenMesh::Subdivider::Uniform::CatmullClarkT::prepare
virtual bool prepare(MeshType &_m)
Initialize properties and weights.
Definition: CatmullClarkT_impl.hh:65
OpenMesh::Subdivider::Uniform::CatmullClarkT
Based on code from Leon Kos, CAD lab, Mech.Eng., University of Ljubljana, Slovenia (http://www...
Definition: CatmullClarkT.hh:85
OpenMesh::Subdivider::Uniform::CatmullClarkT::cleanup
virtual bool cleanup(MeshType &_m)
Remove properties and weights.
Definition: CatmullClarkT_impl.hh:83
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::Subdivider::Uniform::CatmullClarkT::subdivide
virtual bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true)
Execute n subdivision steps.
Definition: CatmullClarkT_impl.hh:96
CatmullClarkT.hh
OpenMesh::Utils::MeshCheckerT
Check integrity of mesh.
Definition: MeshCheckerT.hh:73
OpenMesh::vector_traits::value_type
T::value_type value_type
Type of the scalar value.
Definition: vector_traits.hh:94