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