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
71 CompareVectors::CompareVectors(double _epsilon) :
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>
93 int MeshFixing<MeshT>::add_vertex(const ACG::Vec3d& _p) {
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>
142 void MeshFixing<MeshT>::fix_topology()
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>
308 void MeshFixing<MeshT>::fix_orientation()
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>
381 bool MeshFixing<MeshT>::fix()
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 }
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:112
MeshFixing::fix_orientation
void fix_orientation()
Definition: MeshFixingT_impl.hh:308
OpenMesh::PolyMeshT::add_vertex
VertexHandle add_vertex(const Point &_p)
Alias for new_vertex(const Point&).
Definition: PolyMeshT.hh:235
MeshFixing::add_face
void add_face(const ACG::Vec3d &_p0, const ACG::Vec3d &_p1, const ACG::Vec3d &_p2)
Add a face to the fixing data.
Definition: MeshFixingT_impl.hh:99
MeshFixing
Fix a mesh.
Definition: MeshFixingT.hh:89
MeshFixing::neighbor
int neighbor(unsigned int _f, unsigned int _v0, unsigned int _v1)
Definition: MeshFixingT_impl.hh:271
MeshFixing::Face
Internal face type.
Definition: MeshFixingT.hh:131
MeshFixing::fix_topology
void fix_topology()
Fix the mesh topology.
Definition: MeshFixingT_impl.hh:142
OpenMesh::VectorT
Definition: Vector11T.hh:83
MeshFixing::Vertex
Internal vertex type.
Definition: MeshFixingT.hh:121
CompareVectors::operator()
bool operator()(const ACG::Vec3d &_v0, const ACG::Vec3d &_v1) const
comparison operator
Definition: MeshFixingT_impl.hh:76
CompareVectors::CompareVectors
CompareVectors(double _eps=FLT_MIN)
Constructor.
Definition: MeshFixingT_impl.hh:71
MeshFixing::add_vertex
int add_vertex(const ACG::Vec3d &_p)
Definition: MeshFixingT_impl.hh:93