Developer Documentation

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