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