Developer Documentation

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
TriConnectivity.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$ *
45 * $Date$ *
46 * *
47 \*===========================================================================*/
48
49
50 // CLASS TriMeshT - IMPLEMENTATION
51
52 #include <OpenMesh/Core/Mesh/TriConnectivity.hh>
53
54 namespace OpenMesh
55 {
56
57 TriConnectivity::FaceHandle
58 TriConnectivity::add_face(const VertexHandle* _vertex_handles, size_t _vhs_size)
59 {
60 // need at least 3 vertices
61 if (_vhs_size < 3) return InvalidFaceHandle;
62
64 if (_vhs_size == 3)
65 return PolyConnectivity::add_face(_vertex_handles, _vhs_size);
66
68 else
69 {
70 //omlog() << "triangulating " << _vhs_size << "_gon\n";
71
72 VertexHandle vhandles[3];
73 vhandles[0] = _vertex_handles[0];
74
75 FaceHandle fh;
76 unsigned int i(1);
77 --_vhs_size;
78
79 while (i < _vhs_size)
80 {
81 vhandles[1] = _vertex_handles[i];
82 vhandles[2] = _vertex_handles[++i];
83 fh = PolyConnectivity::add_face(vhandles, 3);
84 }
85
86 return fh;
87 }
88 }
89
90 //-----------------------------------------------------------------------------
91
92 FaceHandle TriConnectivity::add_face(const std::vector<VertexHandle>& _vhandles)
93 {
94 return add_face(&_vhandles.front(), _vhandles.size());
95 }
96
97 //-----------------------------------------------------------------------------
98
99
100 FaceHandle TriConnectivity::add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2)
101 {
102 VertexHandle vhs[3] = { _vh0, _vh1, _vh2 };
103 return PolyConnectivity::add_face(vhs, 3);
104 }
105
106 //-----------------------------------------------------------------------------
107
108 bool TriConnectivity::is_collapse_ok(HalfedgeHandle v0v1)
109 {
110 // is the edge already deleted?
111 if ( status(edge_handle(v0v1)).deleted() )
112 return false;
113
114 HalfedgeHandle v1v0(opposite_halfedge_handle(v0v1));
115 VertexHandle v0(to_vertex_handle(v1v0));
116 VertexHandle v1(to_vertex_handle(v0v1));
117
118 // are vertices already deleted ?
119 if (status(v0).deleted() || status(v1).deleted())
120 return false;
121
122 VertexHandle vl, vr;
123 HalfedgeHandle h1, h2;
124
125 // the edges v1-vl and vl-v0 must not be both boundary edges
126 if (!is_boundary(v0v1))
127 {
128
129 h1 = next_halfedge_handle(v0v1);
130 h2 = next_halfedge_handle(h1);
131
132 vl = to_vertex_handle(h1);
133
134 if (is_boundary(opposite_halfedge_handle(h1)) &&
135 is_boundary(opposite_halfedge_handle(h2)))
136 {
137 return false;
138 }
139 }
140
141
142 // the edges v0-vr and vr-v1 must not be both boundary edges
143 if (!is_boundary(v1v0))
144 {
145
146 h1 = next_halfedge_handle(v1v0);
147 h2 = next_halfedge_handle(h1);
148
149 vr = to_vertex_handle(h1);
150
151 if (is_boundary(opposite_halfedge_handle(h1)) &&
152 is_boundary(opposite_halfedge_handle(h2)))
153 return false;
154 }
155
156 // if vl and vr are equal or both invalid -> fail
157 if (vl == vr) return false;
158
159 VertexVertexIter vv_it;
160
161 // test intersection of the one-rings of v0 and v1
162 for (vv_it = vv_iter(v0); vv_it.is_valid(); ++vv_it)
163 status(*vv_it).set_tagged(false);
164
165 for (vv_it = vv_iter(v1); vv_it.is_valid(); ++vv_it)
166 status(*vv_it).set_tagged(true);
167
168 for (vv_it = vv_iter(v0); vv_it.is_valid(); ++vv_it)
169 if (status(*vv_it).tagged() && *vv_it != vl && *vv_it != vr)
170 return false;
171
172
173 // edge between two boundary vertices should be a boundary edge
174 if ( is_boundary(v0) && is_boundary(v1) &&
175 !is_boundary(v0v1) && !is_boundary(v1v0))
176 return false;
177
178 // passed all tests
179 return true;
180 }
181
182 //-----------------------------------------------------------------------------
183 TriConnectivity::HalfedgeHandle
184 TriConnectivity::vertex_split(VertexHandle v0, VertexHandle v1,
185 VertexHandle vl, VertexHandle vr)
186 {
187 HalfedgeHandle v1vl, vlv1, vrv1, v0v1;
188
189 // build loop from halfedge v1->vl
190 if (vl.is_valid())
191 {
192 v1vl = find_halfedge(v1, vl);
193 assert(v1vl.is_valid());
194 vlv1 = insert_loop(v1vl);
195 }
196
197 // build loop from halfedge vr->v1
198 if (vr.is_valid())
199 {
200 vrv1 = find_halfedge(vr, v1);
201 assert(vrv1.is_valid());
202 insert_loop(vrv1);
203 }
204
205 // handle boundary cases
206 if (!vl.is_valid())
207 vlv1 = prev_halfedge_handle(halfedge_handle(v1));
208 if (!vr.is_valid())
209 vrv1 = prev_halfedge_handle(halfedge_handle(v1));
210
211
212 // split vertex v1 into edge v0v1
213 v0v1 = insert_edge(v0, vlv1, vrv1);
214
215
216 return v0v1;
217 }
218
219 //-----------------------------------------------------------------------------
220 TriConnectivity::HalfedgeHandle
221 TriConnectivity::insert_loop(HalfedgeHandle _hh)
222 {
223 HalfedgeHandle h0(_hh);
224 HalfedgeHandle o0(opposite_halfedge_handle(h0));
225
226 VertexHandle v0(to_vertex_handle(o0));
227 VertexHandle v1(to_vertex_handle(h0));
228
229 HalfedgeHandle h1 = new_edge(v1, v0);
230 HalfedgeHandle o1 = opposite_halfedge_handle(h1);
231
232 FaceHandle f0 = face_handle(h0);
233 FaceHandle f1 = new_face();
234
235 // halfedge -> halfedge
236 set_next_halfedge_handle(prev_halfedge_handle(h0), o1);
237 set_next_halfedge_handle(o1, next_halfedge_handle(h0));
238 set_next_halfedge_handle(h1, h0);
239 set_next_halfedge_handle(h0, h1);
240
241 // halfedge -> face
242 set_face_handle(o1, f0);
243 set_face_handle(h0, f1);
244 set_face_handle(h1, f1);
245
246 // face -> halfedge
247 set_halfedge_handle(f1, h0);
248 if (f0.is_valid())
249 set_halfedge_handle(f0, o1);
250
251
252 // vertex -> halfedge
253 adjust_outgoing_halfedge(v0);
254 adjust_outgoing_halfedge(v1);
255
256 return h1;
257 }
258
259 //-----------------------------------------------------------------------------
260 TriConnectivity::HalfedgeHandle
261 TriConnectivity::insert_edge(VertexHandle _vh, HalfedgeHandle _h0, HalfedgeHandle _h1)
262 {
263 assert(_h0.is_valid() && _h1.is_valid());
264
265 VertexHandle v0 = _vh;
266 VertexHandle v1 = to_vertex_handle(_h0);
267
268 assert( v1 == to_vertex_handle(_h1));
269
270 HalfedgeHandle v0v1 = new_edge(v0, v1);
271 HalfedgeHandle v1v0 = opposite_halfedge_handle(v0v1);
272
273
274
275 // vertex -> halfedge
276 set_halfedge_handle(v0, v0v1);
277 set_halfedge_handle(v1, v1v0);
278
279
280 // halfedge -> halfedge
281 set_next_halfedge_handle(v0v1, next_halfedge_handle(_h0));
282 set_next_halfedge_handle(_h0, v0v1);
283 set_next_halfedge_handle(v1v0, next_halfedge_handle(_h1));
284 set_next_halfedge_handle(_h1, v1v0);
285
286
287 // halfedge -> vertex
288 for (VertexIHalfedgeIter vih_it(vih_iter(v0)); vih_it.is_valid(); ++vih_it)
289 set_vertex_handle(*vih_it, v0);
290
291
292 // halfedge -> face
293 set_face_handle(v0v1, face_handle(_h0));
294 set_face_handle(v1v0, face_handle(_h1));
295
296
297 // face -> halfedge
298 if (face_handle(v0v1).is_valid())
299 set_halfedge_handle(face_handle(v0v1), v0v1);
300 if (face_handle(v1v0).is_valid())
301 set_halfedge_handle(face_handle(v1v0), v1v0);
302
303
304 // vertex -> halfedge
305 adjust_outgoing_halfedge(v0);
306 adjust_outgoing_halfedge(v1);
307
308
309 return v0v1;
310 }
311
312 //-----------------------------------------------------------------------------
313 bool TriConnectivity::is_flip_ok(EdgeHandle _eh) const
314 {
315 // boundary edges cannot be flipped
316 if (is_boundary(_eh)) return false;
317
318
319 HalfedgeHandle hh = halfedge_handle(_eh, 0);
320 HalfedgeHandle oh = halfedge_handle(_eh, 1);
321
322
323 // check if the flipped edge is already present
324 // in the mesh
325
326 VertexHandle ah = to_vertex_handle(next_halfedge_handle(hh));
327 VertexHandle bh = to_vertex_handle(next_halfedge_handle(oh));
328
329 if (ah == bh) // this is generally a bad sign !!!
330 return false;
331
332 for (ConstVertexVertexIter vvi(*this, ah); vvi.is_valid(); ++vvi)
333 if (*vvi == bh)
334 return false;
335
336 return true;
337 }
338
339 //-----------------------------------------------------------------------------
340 void TriConnectivity::flip(EdgeHandle _eh)
341 {
342 // CAUTION : Flipping a halfedge may result in
343 // a non-manifold mesh, hence check for yourself
344 // whether this operation is allowed or not!
345 assert(is_flip_ok(_eh));//let's make it sure it is actually checked
346 assert(!is_boundary(_eh));
347
348 HalfedgeHandle a0 = halfedge_handle(_eh, 0);
349 HalfedgeHandle b0 = halfedge_handle(_eh, 1);
350
351 HalfedgeHandle a1 = next_halfedge_handle(a0);
352 HalfedgeHandle a2 = next_halfedge_handle(a1);
353
354 HalfedgeHandle b1 = next_halfedge_handle(b0);
355 HalfedgeHandle b2 = next_halfedge_handle(b1);
356
357 VertexHandle va0 = to_vertex_handle(a0);
358 VertexHandle va1 = to_vertex_handle(a1);
359
360 VertexHandle vb0 = to_vertex_handle(b0);
361 VertexHandle vb1 = to_vertex_handle(b1);
362
363 FaceHandle fa = face_handle(a0);
364 FaceHandle fb = face_handle(b0);
365
366 set_vertex_handle(a0, va1);
367 set_vertex_handle(b0, vb1);
368
369 set_next_halfedge_handle(a0, a2);
370 set_next_halfedge_handle(a2, b1);
371 set_next_halfedge_handle(b1, a0);
372
373 set_next_halfedge_handle(b0, b2);
374 set_next_halfedge_handle(b2, a1);
375 set_next_halfedge_handle(a1, b0);
376
377 set_face_handle(a1, fb);
378 set_face_handle(b1, fa);
379
380 set_halfedge_handle(fa, a0);
381 set_halfedge_handle(fb, b0);
382
383 if (halfedge_handle(va0) == b0)
384 set_halfedge_handle(va0, a1);
385 if (halfedge_handle(vb0) == a0)
386 set_halfedge_handle(vb0, b1);
387 }
388
389
390 //-----------------------------------------------------------------------------
391
392 void TriConnectivity::split(EdgeHandle _eh, VertexHandle _vh)
393 {
394 HalfedgeHandle h0 = halfedge_handle(_eh, 0);
395 HalfedgeHandle o0 = halfedge_handle(_eh, 1);
396
397 VertexHandle v2 = to_vertex_handle(o0);
398
399 HalfedgeHandle e1 = new_edge(_vh, v2);
400 HalfedgeHandle t1 = opposite_halfedge_handle(e1);
401
402 FaceHandle f0 = face_handle(h0);
403 FaceHandle f3 = face_handle(o0);
404
405 set_halfedge_handle(_vh, h0);
406 set_vertex_handle(o0, _vh);
407
408 if (!is_boundary(h0))
409 {
410 HalfedgeHandle h1 = next_halfedge_handle(h0);
411 HalfedgeHandle h2 = next_halfedge_handle(h1);
412
413 VertexHandle v1 = to_vertex_handle(h1);
414
415 HalfedgeHandle e0 = new_edge(_vh, v1);
416 HalfedgeHandle t0 = opposite_halfedge_handle(e0);
417
418 FaceHandle f1 = new_face();
419 set_halfedge_handle(f0, h0);
420 set_halfedge_handle(f1, h2);
421
422 set_face_handle(h1, f0);
423 set_face_handle(t0, f0);
424 set_face_handle(h0, f0);
425
426 set_face_handle(h2, f1);
427 set_face_handle(t1, f1);
428 set_face_handle(e0, f1);
429
430 set_next_halfedge_handle(h0, h1);
431 set_next_halfedge_handle(h1, t0);
432 set_next_halfedge_handle(t0, h0);
433
434 set_next_halfedge_handle(e0, h2);
435 set_next_halfedge_handle(h2, t1);
436 set_next_halfedge_handle(t1, e0);
437 }
438 else
439 {
440 set_next_halfedge_handle(prev_halfedge_handle(h0), t1);
441 set_next_halfedge_handle(t1, h0);
442 // halfedge handle of _vh already is h0
443 }
444
445
446 if (!is_boundary(o0))
447 {
448 HalfedgeHandle o1 = next_halfedge_handle(o0);
449 HalfedgeHandle o2 = next_halfedge_handle(o1);
450
451 VertexHandle v3 = to_vertex_handle(o1);
452
453 HalfedgeHandle e2 = new_edge(_vh, v3);
454 HalfedgeHandle t2 = opposite_halfedge_handle(e2);
455
456 FaceHandle f2 = new_face();
457 set_halfedge_handle(f2, o1);
458 set_halfedge_handle(f3, o0);
459
460 set_face_handle(o1, f2);
461 set_face_handle(t2, f2);
462 set_face_handle(e1, f2);
463
464 set_face_handle(o2, f3);
465 set_face_handle(o0, f3);
466 set_face_handle(e2, f3);
467
468 set_next_halfedge_handle(e1, o1);
469 set_next_halfedge_handle(o1, t2);
470 set_next_halfedge_handle(t2, e1);
471
472 set_next_halfedge_handle(o0, e2);
473 set_next_halfedge_handle(e2, o2);
474 set_next_halfedge_handle(o2, o0);
475 }
476 else
477 {
478 set_next_halfedge_handle(e1, next_halfedge_handle(o0));
479 set_next_halfedge_handle(o0, e1);
480 set_halfedge_handle(_vh, e1);
481 }
482
483 if (halfedge_handle(v2) == h0)
484 set_halfedge_handle(v2, t1);
485 }
486
487 //-----------------------------------------------------------------------------
488
489 void TriConnectivity::split_copy(EdgeHandle _eh, VertexHandle _vh)
490 {
491 // Split the halfedge ( handle will be preserved)
492 split(_eh, _vh);
493
494 // Copy the properties of the original edge to all neighbor edges that
495 // have been created
496 for(VEIter ve_it = ve_iter(_vh); ve_it.is_valid(); ++ve_it)
497 copy_all_properties(_eh, *ve_it);
498 }
499
500 }// namespace OpenMesh
OpenMesh::TriConnectivity::is_flip_ok
bool is_flip_ok(EdgeHandle _eh) const
Check whether flipping _eh is topologically correct.
Definition: TriConnectivity.cc:313
OpenMesh::TriConnectivity::add_face
FaceHandle add_face(const VertexHandle *_vhandles, size_t _vhs_size)
Add a face with arbitrary valence to the triangle mesh.
Definition: TriConnectivity.cc:58
OpenMesh::TriConnectivity::flip
void flip(EdgeHandle _eh)
Definition: TriConnectivity.cc:340
OpenMesh
Definition: MeshItems.hh:64
OpenMesh::TriConnectivity::insert_loop
HalfedgeHandle insert_loop(HalfedgeHandle _hh)
Helper for vertex split.
Definition: TriConnectivity.cc:221
OpenMesh::TriConnectivity::split
void split(EdgeHandle _eh, VertexHandle _vh)
Edge split (= 2-to-4 split)
Definition: TriConnectivity.cc:392
OpenMesh::ArrayKernel::status
const StatusInfo & status(VertexHandle _vh) const
Status Query API.
Definition: ArrayKernel.hh:506
OpenMesh::BaseHandle::is_valid
bool is_valid() const
The handle is valid iff the index is not equal to -1.
Definition: Handles.hh:77
OpenMesh::HalfedgeHandle
Handle for a halfedge entity.
Definition: Handles.hh:132
OpenMesh::PolyConnectivity::find_halfedge
HalfedgeHandle find_halfedge(VertexHandle _start_vh, VertexHandle _end_vh) const
Find halfedge from _vh0 to _vh1. Returns invalid handle if not found.
Definition: PolyConnectivity.cc:63
OpenMesh::Attributes::StatusInfo::set_tagged
void set_tagged(bool _b)
set tagged
Definition: Status.hh:140
OpenMesh::BaseKernel::copy_all_properties
void copy_all_properties(VertexHandle _vh_from, VertexHandle _vh_to, bool _copyBuildIn=false)
Definition: BaseKernel.hh:476
OpenMesh::Attributes::StatusInfo::tagged
bool tagged() const
is tagged ?
Definition: Status.hh:138
OpenMesh::PolyConnectivity::vv_iter
VertexVertexIter vv_iter(VertexHandle _vh)
vertex - vertex circulator
Definition: PolyConnectivity.hh:576
OpenMesh::VertexHandle
Handle for a vertex entity.
Definition: Handles.hh:125
OpenMesh::TriConnectivity::vertex_split
HalfedgeHandle vertex_split(VertexHandle v0, VertexHandle v1, VertexHandle vl, VertexHandle vr)
Vertex Split: inverse operation to collapse().
Definition: TriConnectivity.cc:184
OpenMesh::EdgeHandle
Handle for a edge entity.
Definition: Handles.hh:139
OpenMesh::TriConnectivity::split_copy
void split_copy(EdgeHandle _eh, VertexHandle _vh)
Edge split (= 2-to-4 split)
Definition: TriConnectivity.cc:489
OpenMesh::FaceHandle
Handle for a face entity.
Definition: Handles.hh:146
OpenMesh::Iterators::GenericCirculatorT_DEPRECATED
Definition: CirculatorsT.hh:428
OpenMesh::PolyConnectivity::is_boundary
bool is_boundary(HalfedgeHandle _heh) const
Check if the halfedge is at the boundary.
Definition: PolyConnectivity.hh:1339
OpenMesh::PolyConnectivity::adjust_outgoing_halfedge
void adjust_outgoing_halfedge(VertexHandle _vh)
Definition: PolyConnectivity.cc:107
OpenMesh::TriConnectivity::is_collapse_ok
bool is_collapse_ok(HalfedgeHandle _heh)
Definition: TriConnectivity.cc:108
OpenMesh::TriConnectivity::insert_edge
HalfedgeHandle insert_edge(VertexHandle _vh, HalfedgeHandle _h0, HalfedgeHandle _h1)
Helper for vertex split.
Definition: TriConnectivity.cc:261
OpenMesh::PolyConnectivity::InvalidFaceHandle
static const FaceHandle InvalidFaceHandle
Invalid handle.
Definition: PolyConnectivity.hh:73
OpenMesh::PolyConnectivity::vih_iter
VertexIHalfedgeIter vih_iter(VertexHandle _vh)
vertex - incoming halfedge circulator
Definition: PolyConnectivity.hh:585
OpenMesh::PolyConnectivity::ve_iter
VertexEdgeIter ve_iter(VertexHandle _vh)
vertex - edge circulator
Definition: PolyConnectivity.hh:603
OpenMesh::PolyConnectivity::add_face
FaceHandle add_face(const std::vector< VertexHandle > &_vhandles)
Add and connect a new face.
Definition: PolyConnectivity.cc:326