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
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
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 //=============================================================================
virtual bool prepare(MeshType &_m)
Initialize properties and weights.
Definition: CatmullClarkT_impl.hh:65
Based on code from Leon Kos, CAD lab, Mech.Eng., University of Ljubljana, Slovenia (http://www...
Definition: CatmullClarkT.hh:85
virtual bool cleanup(MeshType &_m)
Remove properties and weights.
Definition: CatmullClarkT_impl.hh:83
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
virtual bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true)
Execute n subdivision steps.
Definition: CatmullClarkT_impl.hh:96
Check integrity of mesh.
Definition: MeshCheckerT.hh:73
T::value_type value_type
Type of the scalar value.
Definition: vector_traits.hh:94

Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .