Developer Documentation
MeshFixingT_impl.hh
1 
2 /*===========================================================================*\
3  * *
4  * OpenMesh *
5  * Copyright (c) 2001-2015, RWTH-Aachen University *
6  * Department of Computer Graphics and Multimedia *
7  * All rights reserved. *
8  * www.openflipper.org *
9  * *
10  *---------------------------------------------------------------------------*
11  * This file is part of OpenFlipper. *
12  *---------------------------------------------------------------------------*
13  * *
14  * Redistribution and use in source and binary forms, with or without *
15  * modification, are permitted provided that the following conditions *
16  * are met: *
17  * *
18  * 1. Redistributions of source code must retain the above copyright notice, *
19  * this list of conditions and the following disclaimer. *
20  * *
21  * 2. Redistributions in binary form must reproduce the above copyright *
22  * notice, this list of conditions and the following disclaimer in the *
23  * documentation and/or other materials provided with the distribution. *
24  * *
25  * 3. Neither the name of the copyright holder nor the names of its *
26  * contributors may be used to endorse or promote products derived from *
27  * this software without specific prior written permission. *
28  * *
29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
31  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
32  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
33  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
34  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
35  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
36  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
37  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
38  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
39  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
40  * *
41  \*===========================================================================*/
42 
43 /*===========================================================================*\
44  * *
45  * $Revision$ *
46  * $Date$ *
47  * *
48  \*===========================================================================*/
49 
53 //=============================================================================
54 //
55 // CLASS MeshFixing - IMPLEMENTATION
56 //
57 //=============================================================================
58 
59 #define OPENMESH_MESHFIXING_CC
60 
61 //== INCLUDES =================================================================
62 
63 #include "MeshFixingT.hh"
64 
65 //== NAMESPACE ===============================================================
66 
67 
68 //== IMPLEMENTATION ==========================================================
69 
70 
72  epsilon_(_epsilon * _epsilon)
73 {
74 }
75 
76 bool CompareVectors::operator()(const ACG::Vec3d& _v0, const ACG::Vec3d& _v1) const
77 {
78  if ((_v0 - _v1).sqrnorm() <= epsilon_)
79  return false;
80  else
81  return _v0 < _v1;
82 }
83 
84 template<class MeshT>
85 MeshFixing<MeshT>::MeshFixing(MeshT& _mesh, double _epsilon ) :
86 mesh_(_mesh),
87 vmap_(CompareVectors(_epsilon))
88 {
89 }
90 
91 
92 template<class MeshT>
94  vertices_.push_back( Vertex(_p) );
95  return vertices_.size()-1;
96 }
97 
98 template<class MeshT>
99 void MeshFixing<MeshT>::add_face(const ACG::Vec3d& _p0, const ACG::Vec3d& _p1, const ACG::Vec3d& _p2) {
100  ACG::Vec3d p[3] = {_p0, _p1, _p2 };
101  int v[3];
102  MapIter it;
103 
104 
105  // map points to vertices
106  for (unsigned int i=0; i<3; ++i) {
107 
108  // Try to find the vertex in the map
109  it = vmap_.find(p[i]);
110 
111  // Add the vertex to the map, if it is new
112  // (Out of the epsilon range! )
113  if ( it == vmap_.end() ) {
114  v[i] = add_vertex( p[i] );
115  vmap_[p[i]] = v[i];
116  } else
117  v[i] = it->second;
118  }
119 
120 
121  // Don't add degenerate faces, as we could already skip them here
122  if (v[0]==v[1] || v[0]==v[2] || v[1]==v[2])
123  return;
124 
125 
126  // add face
127  faces_.push_back( Face(v[0], v[1], v[2]) );
128 
129  unsigned int newFace = faces_.size()- 1;
130  for (unsigned int i = 0; i < 3; ++i)
131  vertices_[v[i]].faces.push_back( newFace );
132 
133 }
134 
141 template<class MeshT>
143 {
144  int component;
145 
146  const unsigned int numberOfVertices = vertices_.size();
147 
148  // Iterate over all vertices
149  for (unsigned int v = 0; v < numberOfVertices; ++v) {
150 
151  // Get reference to the vector of associated faces at the current vertex
152  const std::vector<unsigned int>& vfaces = vertices_[v].faces;
153  std::vector<unsigned int>::const_iterator f_it, f_end(vfaces.end());
154  std::vector<unsigned int> todo;
155 
156  todo.reserve(vfaces.size());
157 
158  // Reset components to which each face connected to this vertex belongs
159  for (f_it = vfaces.begin(); f_it != f_end; ++f_it)
160  faces_[*f_it].component = -1;
161 
162  // Find the components
163  for (component = 0;; ++component) {
164 
165  // Find one face, that is not yet flagged with a component
166  for (f_it = vfaces.begin(); f_it != f_end; ++f_it) {
167 
168  if (faces_[*f_it].component == -1) {
169 
170  // Add component as seed to the list
171  todo.push_back(*f_it);
172 
173  // Mark the current face with the right component
174  faces_[*f_it].component = component;
175 
176  // Found, so don't continue
177  break;
178  }
179 
180  }
181 
182  // No components found anymore
183  if (f_it == f_end)
184  break;
185 
186  // Grow from the seed face until no more connected faces where found
187  while (!todo.empty()) {
188 
189  // Get next element from the todo list
190  const unsigned int currentFace = todo.back();
191  todo.pop_back();
192 
193  // Go over all vertices of the current face
194  for (unsigned int i = 0; i < 3; ++i) {
195 
196  // If the vertex of the face is not equal to the current iteration vertex
197  if (faces_[currentFace].v[i] != v) {
198 
199  // Found neighbor?
200  const int neighbourFace = neighbor(currentFace, v, faces_[currentFace].v[i]);
201  if ( neighbourFace != -1) {
202 
203  // Tag it with the right component and push it to the list of todos
204  if (faces_[neighbourFace].component == -1) {
205  faces_[neighbourFace].component = component;
206  todo.push_back(neighbourFace);
207  }
208 
209  }
210  }
211  }
212  }
213  }
214 
215  // Now we separate the components at the current vertex
216  for (int c = 1; c < component; ++c) {
217 
218  // Duplicate the point to achieve the separation
219  const ACG::Vec3d p = vertices_[v].p;
220  unsigned int newVertex = add_vertex(p);
221 
222  // Possible relocation of vertices_ so we need to update the references!
223  std::vector<unsigned int>& vfaces = vertices_[v].faces;
224  std::vector<unsigned int>::iterator f_it, f_end(vfaces.end());
225 
226  // Update the face indices of the current component
227  bool finished = false;
228  while (!finished) {
229  finished = true;
230 
231  for (f_it = vfaces.begin(), f_end = vfaces.end(); f_it != f_end; ++f_it) {
232 
233  // If the face belongs to the current component
234 
235  if (faces_[*f_it].component == c) {
236 
237  // Iterate over its vertices
238  for (unsigned int i = 0; i < 3; ++i) {
239 
240  // Relink to the new vertex by updating the face and pushing it in as new
241  if (faces_[*f_it].v[i] == v) {
242  faces_[*f_it].v[i] = newVertex;
243  vertices_[newVertex].faces.push_back(*f_it);
244  finished = false;
245  }
246 
247  }
248 
249  // Erase the old one
250  vfaces.erase(f_it);
251  break;
252  }
253  }
254  }
255  }
256 
257  }
258 }
259 
260 //-----------------------------------------------------------------------------
261 
262 
270 template<class MeshT>
271 int MeshFixing<MeshT>::neighbor(unsigned int _f, unsigned int _v0, unsigned int _v1)
272 {
273  // Get the list of faces at vertex _v0
274  const std::vector<unsigned int>& v0faces = vertices_[_v0].faces;
275  std::vector<unsigned int>::const_iterator f_it, f_end = v0faces.end();
276 
277 
278  int neighborFace = -1;
279 
280  // Iterate over all associated faces at the current vertex
281  for (f_it = v0faces.begin(); f_it != f_end; ++f_it) {
282 
283  // if the face associated at this vertex is not equal to the face we are analyzing
284  if (*f_it != _f) {
285 
286  // Iterate over all vertices of this face
287  for (unsigned int j = 0; j < 3; ++j)
288 
289  // If this face is adjacent to the vertex we are analyzing
290  if (faces_[*f_it].v[j] == _v1) {
291 
292  if (neighborFace != -1)
293  return -1;
294  else
295  neighborFace = *f_it;
296 
297  }
298  }
299  }
300 
301  return neighborFace;
302 }
303 
307 template<class MeshT>
309 {
310  // We need faces to work on!
311  if (faces_.empty()) return;
312 
313  int fh = 0;
314 
315  std::vector<int> todo;
316  todo.reserve( (int) sqrt( (double) faces_.size()) );
317 
318  const unsigned int faceCount = faces_.size();
319 
320  // Reset components of all faces
321  for (unsigned int i = 0; i < faceCount; ++i)
322  faces_[i].component = -1;
323 
324 
325  // Iterate over all components
326  for (int component = 0;; ++component) {
327 
328  unsigned int start = 0 ;
329 
330  // Find one seed triangle in this component
331  for (; start < faceCount; ++start) {
332 
333  // Found an untagged face == new component?
334  if (faces_[start].component == -1) {
335  fh = start;
336  todo.push_back(fh);
337  faces_[fh].component = component;
338  break;
339  }
340 
341  }
342 
343  // No more Components!
344  if (start == faceCount)
345  break;
346 
347  // Flood fill the current component, while fixing the orientation
348  while (!todo.empty()) {
349 
350  // Get the next face to work on
351  fh = todo.back();
352  todo.pop_back();
353 
354  // Find neighbors of the current face
355  for (unsigned int i = 0; i < 3; ++i) {
356  unsigned int i0 = faces_[fh].v[i];
357  unsigned int i1 = faces_[fh].v[(i + 1) % 3];
358 
359  int neighborFace = neighbor(fh, i0, i1);
360  if (neighborFace != -1 && faces_[neighborFace].component == -1) {
361 
362  int nextVertex = 0;
363  for (nextVertex = 0; nextVertex < 3; ++nextVertex)
364  if (faces_[neighborFace].v[nextVertex] == i1)
365  break;
366 
367  // If the orientation is incorrect, we have to flip it!
368  if (faces_[neighborFace].v[(nextVertex + 2) % 3] == i0)
369  std::swap(faces_[neighborFace].v[1], faces_[neighborFace].v[2]);
370 
371  faces_[neighborFace].component = component;
372  todo.push_back(neighborFace);
373  }
374  }
375 
376  }
377  }
378 }
379 
380 template<class MeshT>
382 {
383 
384  // Maximal number of steps:
385  // _mesh.n_faces() + // add face
386  // (_fix_topology ? _mesh.n_vertices() : 0) + // non-manifold
387  // (_fix_orientation ? _mesh.n_faces() : 0) + // orientation
388  // _mesh.n_faces(), // copy output
389 
390 
391  typename MeshT::FaceVertexIter fv_it;
392 
393  std::cerr << "Setup data structure" << std::endl;
394 
395  // add faces
396  for (typename MeshT::FaceIter f_it = mesh_.faces_begin(); f_it != mesh_.faces_end(); ++f_it)
397  {
398  fv_it = mesh_.fv_iter(*f_it);
399  const ACG::Vec3d p0 = mesh_.point( *(fv_it) );
400  const ACG::Vec3d p1 = mesh_.point(*(++fv_it));
401  const ACG::Vec3d p2 = mesh_.point(*(++fv_it));
402 
403  add_face(p0, p1, p2);
404 
405  }
406 
407 
408 
409  std::cerr << "Fix topology" << std::endl;
410  //fix_topology();
411 
412  std::cerr << "Fix orientation" << std::endl;
413 
414  fix_orientation();
415 
416  std::cerr << "Copy back to mesh" << std::endl;
417 
418  // Remove all primitives but keep the properties
419  mesh_.clean();
420 
421  // Copy back to the target mesh
422  unsigned int vertexCount(vertices_.size());
423  unsigned int faceCount(faces_.size());
424 
425 
426  std::vector<typename MeshT::VertexHandle> vh;
427  typename MeshT::VertexHandle v0, v1, v2;
428  typename MeshT::FaceHandle fh;
429  bool ok = true;
430 
431 
432  // Add all vertices back to the mesh
433  vh.resize(vertexCount);
434  for (unsigned int i = 0; i < vertexCount; ++i)
435  vh[i] = mesh_.add_vertex((typename TriMesh::Point) vertices_[i].p);
436 
437  // Add all faces back to mesh
438  for (unsigned int i = 0; i < faceCount; ++i) {
439 
440  // try to add face
441  if (!(fh = mesh_.add_face(vh[faces_[i].v[0]], vh[faces_[i].v[1]], vh[faces_[i].v[2]])).is_valid()) {
442  // fails -> add isolated face
443  v0 = mesh_.add_vertex((typename MeshT::Point) vertices_[faces_[i].v[0]].p);
444  v1 = mesh_.add_vertex((typename MeshT::Point) vertices_[faces_[i].v[1]].p);
445  v2 = mesh_.add_vertex((typename MeshT::Point) vertices_[faces_[i].v[2]].p);
446  fh = mesh_.add_face(v0, v1, v2);
447  ok = false;
448  }
449 
450  }
451 
452  return ok;
453 }
void fix_orientation()
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:112
bool operator()(const ACG::Vec3d &_v0, const ACG::Vec3d &_v1) const
comparison operator
Fix a mesh.
Definition: MeshFixingT.hh:89
int neighbor(unsigned int _f, unsigned int _v0, unsigned int _v1)
void fix_topology()
Fix the mesh topology.
SmartVertexHandle add_vertex(const Point &_p)
Definition: PolyMeshT.hh:245
int add_vertex(const ACG::Vec3d &_p)
Internal vertex type.
Definition: MeshFixingT.hh:121
CompareVectors(double _eps=FLT_MIN)
Constructor.
Internal face type.
Definition: MeshFixingT.hh:131
void add_face(const ACG::Vec3d &_p0, const ACG::Vec3d &_p1, const ACG::Vec3d &_p2)
Add a face to the fixing data.