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  * $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 
101 {
102  VertexHandle vhs[3] = { _vh0, _vh1, _vh2 };
103  return PolyConnectivity::add_face(vhs, 3);
104 }
105 
106 //-----------------------------------------------------------------------------
107 
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 //-----------------------------------------------------------------------------
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 //-----------------------------------------------------------------------------
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
255 
256  return h1;
257 }
258 
259 //-----------------------------------------------------------------------------
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
307 
308 
309  return v0v1;
310 }
311 
312 //-----------------------------------------------------------------------------
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 //-----------------------------------------------------------------------------
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 
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 
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
HalfedgeHandle vertex_split(VertexHandle v0, VertexHandle v1, VertexHandle vl, VertexHandle vr)
Vertex Split: inverse operation to collapse().
void split_copy(EdgeHandle _eh, VertexHandle _vh)
Edge split (= 2-to-4 split)
void adjust_outgoing_halfedge(VertexHandle _vh)
void flip(EdgeHandle _eh)
HalfedgeHandle insert_edge(VertexHandle _vh, HalfedgeHandle _h0, HalfedgeHandle _h1)
Helper for vertex split.
bool is_boundary(HalfedgeHandle _heh) const
Check if the halfedge is at the boundary.
VertexVertexIter vv_iter(VertexHandle _vh)
vertex - vertex circulator
bool is_flip_ok(EdgeHandle _eh) const
Check whether flipping _eh is topologically correct.
VertexEdgeIter ve_iter(VertexHandle _vh)
vertex - edge circulator
Handle for a edge entity.
Definition: Handles.hh:139
void split(EdgeHandle _eh, VertexHandle _vh)
Edge split (= 2-to-4 split)
HalfedgeHandle find_halfedge(VertexHandle _start_vh, VertexHandle _end_vh) const
Find halfedge from _vh0 to _vh1. Returns invalid handle if not found.
HalfedgeHandle insert_loop(HalfedgeHandle _hh)
Helper for vertex split.
bool is_valid() const
The handle is valid iff the index is not equal to -1.
Definition: Handles.hh:77
FaceHandle add_face(const std::vector< VertexHandle > &_vhandles)
Add and connect a new face.
bool tagged() const
is tagged ?
Definition: Status.hh:138
const StatusInfo & status(VertexHandle _vh) const
Status Query API.
Definition: ArrayKernel.hh:506
Handle for a halfedge entity.
Definition: Handles.hh:132
static const FaceHandle InvalidFaceHandle
Invalid handle.
Handle for a vertex entity.
Definition: Handles.hh:125
FaceHandle add_face(const VertexHandle *_vhandles, size_t _vhs_size)
Add a face with arbitrary valence to the triangle mesh.
VertexIHalfedgeIter vih_iter(VertexHandle _vh)
vertex - incoming halfedge circulator
Handle for a face entity.
Definition: Handles.hh:146
void copy_all_properties(VertexHandle _vh_from, VertexHandle _vh_to, bool _copyBuildIn=false)
Definition: BaseKernel.hh:516
bool is_collapse_ok(HalfedgeHandle _heh)
void set_tagged(bool _b)
set tagged
Definition: Status.hh:140