OpenMesh

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

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PolyConnectivity.hh
1 /*===========================================================================*\
2 * *
3 * OpenMesh *
4 * Copyright (C) 2001-2012 by Computer Graphics Group, RWTH Aachen *
5 * www.openmesh.org *
6 * *
7 *---------------------------------------------------------------------------*
8 * This file is part of OpenMesh. *
9 * *
10 * OpenMesh is free software: you can redistribute it and/or modify *
11 * it under the terms of the GNU Lesser General Public License as *
12 * published by the Free Software Foundation, either version 3 of *
13 * the License, or (at your option) any later version with the *
14 * following exceptions: *
15 * *
16 * If other files instantiate templates or use macros *
17 * or inline functions from this file, or you compile this file and *
18 * link it with other files to produce an executable, this file does *
19 * not by itself cause the resulting executable to be covered by the *
20 * GNU Lesser General Public License. This exception does not however *
21 * invalidate any other reasons why the executable file might be *
22 * covered by the GNU Lesser General Public License. *
23 * *
24 * OpenMesh is distributed in the hope that it will be useful, *
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
27 * GNU Lesser General Public License for more details. *
28 * *
29 * You should have received a copy of the GNU LesserGeneral Public *
30 * License along with OpenMesh. If not, *
31 * see <http://www.gnu.org/licenses/>. *
32 * *
33 \*===========================================================================*/
34
35 /*===========================================================================*\
36 * *
37 * $Revision: 847 $ *
38 * $Date: 2013-07-23 16:23:12 +0200 (Di, 23. Jul 2013) $ *
39 * *
40 \*===========================================================================*/
41
42 #ifndef OPENMESH_POLYCONNECTIVITY_HH
43 #define OPENMESH_POLYCONNECTIVITY_HH
44
45 #include <OpenMesh/Core/Mesh/ArrayKernel.hh>
46 #include <OpenMesh/Core/Mesh/IteratorsT.hh>
47 #include <OpenMesh/Core/Mesh/CirculatorsT.hh>
48
49 namespace OpenMesh
50 {
51
54 class OPENMESHDLLEXPORT PolyConnectivity : public ArrayKernel
55 {
56 public:
58
59
60 static const VertexHandle InvalidVertexHandle;
62 static const HalfedgeHandle InvalidHalfedgeHandle;
64 static const EdgeHandle InvalidEdgeHandle;
66 static const FaceHandle InvalidFaceHandle;
68
69 typedef PolyConnectivity This;
70
71 //--- iterators ---
72
78
79 typedef Iterators::GenericIteratorT<This, This::VertexHandle, ArrayKernel, &This::has_vertex_status, &This::n_vertices> VertexIter;
80 typedef Iterators::GenericIteratorT<This, This::HalfedgeHandle, ArrayKernel, &This::has_halfedge_status, &This::n_halfedges> HalfedgeIter;
81 typedef Iterators::GenericIteratorT<This, This::EdgeHandle, ArrayKernel, &This::has_edge_status, &This::n_edges> EdgeIter;
82 typedef Iterators::GenericIteratorT<This, This::FaceHandle, ArrayKernel, &This::has_face_status, &This::n_faces> FaceIter;
83
84 typedef VertexIter ConstVertexIter;
85 typedef HalfedgeIter ConstHalfedgeIter;
86 typedef EdgeIter ConstEdgeIter;
87 typedef FaceIter ConstFaceIter;
89
90 //--- circulators ---
91
97
98 typedef Iterators::VertexVertexIterT<This> VertexVertexIter;
99 typedef Iterators::VertexOHalfedgeIterT<This> VertexOHalfedgeIter;
100 typedef Iterators::VertexIHalfedgeIterT<This> VertexIHalfedgeIter;
101 typedef Iterators::VertexEdgeIterT<This> VertexEdgeIter;
102 typedef Iterators::VertexFaceIterT<This> VertexFaceIter;
103 typedef Iterators::FaceVertexIterT<This> FaceVertexIter;
104 typedef Iterators::FaceHalfedgeIterT<This> FaceHalfedgeIter;
105 typedef Iterators::FaceEdgeIterT<This> FaceEdgeIter;
106 typedef Iterators::FaceFaceIterT<This> FaceFaceIter;
107
108 typedef Iterators::ConstVertexVertexIterT<This> ConstVertexVertexIter;
109 typedef Iterators::ConstVertexOHalfedgeIterT<This> ConstVertexOHalfedgeIter;
110 typedef Iterators::ConstVertexIHalfedgeIterT<This> ConstVertexIHalfedgeIter;
111 typedef Iterators::ConstVertexEdgeIterT<This> ConstVertexEdgeIter;
112 typedef Iterators::ConstVertexFaceIterT<This> ConstVertexFaceIter;
113 typedef Iterators::ConstFaceVertexIterT<This> ConstFaceVertexIter;
114 typedef Iterators::ConstFaceHalfedgeIterT<This> ConstFaceHalfedgeIter;
115 typedef Iterators::ConstFaceEdgeIterT<This> ConstFaceEdgeIter;
116 typedef Iterators::ConstFaceFaceIterT<This> ConstFaceFaceIter;
118
119 // --- shortcuts
120
125
126 typedef VertexHandle VHandle;
127 typedef HalfedgeHandle HHandle;
128 typedef EdgeHandle EHandle;
129 typedef FaceHandle FHandle;
130
131 typedef VertexIter VIter;
132 typedef HalfedgeIter HIter;
133 typedef EdgeIter EIter;
134 typedef FaceIter FIter;
135
136 typedef ConstVertexIter CVIter;
137 typedef ConstHalfedgeIter CHIter;
138 typedef ConstEdgeIter CEIter;
139 typedef ConstFaceIter CFIter;
140
141 typedef VertexVertexIter VVIter;
142 typedef VertexOHalfedgeIter VOHIter;
143 typedef VertexIHalfedgeIter VIHIter;
144 typedef VertexEdgeIter VEIter;
145 typedef VertexFaceIter VFIter;
146 typedef FaceVertexIter FVIter;
147 typedef FaceHalfedgeIter FHIter;
148 typedef FaceEdgeIter FEIter;
149 typedef FaceFaceIter FFIter;
150
151 typedef ConstVertexVertexIter CVVIter;
152 typedef ConstVertexOHalfedgeIter CVOHIter;
153 typedef ConstVertexIHalfedgeIter CVIHIter;
154 typedef ConstVertexEdgeIter CVEIter;
155 typedef ConstVertexFaceIter CVFIter;
156 typedef ConstFaceVertexIter CFVIter;
157 typedef ConstFaceHalfedgeIter CFHIter;
158 typedef ConstFaceEdgeIter CFEIter;
159 typedef ConstFaceFaceIter CFFIter;
161
162 public:
163
164 PolyConnectivity() {}
165 virtual ~PolyConnectivity() {}
166
167 inline static bool is_triangles()
168 { return false; }
169
172 inline void assign_connectivity(const PolyConnectivity& _other)
173 { ArrayKernel::assign_connectivity(_other); }
174
178
180 inline VertexHandle add_vertex()
181 { return new_vertex(); }
182
190 FaceHandle add_face(const std::vector<VertexHandle>& _vhandles);
191
192
202 FaceHandle add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2);
203
214 FaceHandle add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2, VertexHandle _vh3);
215
224 FaceHandle add_face(const VertexHandle* _vhandles, size_t _vhs_size);
225
227
229
230
235 bool is_collapse_ok(HalfedgeHandle _he);
236
237
243 void delete_vertex(VertexHandle _vh, bool _delete_isolated_vertices = true);
244
253 void delete_edge(EdgeHandle _eh, bool _delete_isolated_vertices=true);
254
265 void delete_face(FaceHandle _fh, bool _delete_isolated_vertices=true);
266
268
272
274 VertexIter vertices_begin();
276 ConstVertexIter vertices_begin() const;
278 VertexIter vertices_end();
280 ConstVertexIter vertices_end() const;
281
283 HalfedgeIter halfedges_begin();
285 ConstHalfedgeIter halfedges_begin() const;
287 HalfedgeIter halfedges_end();
289 ConstHalfedgeIter halfedges_end() const;
290
292 EdgeIter edges_begin();
294 ConstEdgeIter edges_begin() const;
296 EdgeIter edges_end();
298 ConstEdgeIter edges_end() const;
299
301 FaceIter faces_begin();
303 ConstFaceIter faces_begin() const;
305 FaceIter faces_end();
307 ConstFaceIter faces_end() const;
308
309 template<typename CONTAINER_TYPE, typename ITER_TYPE, ITER_TYPE (CONTAINER_TYPE::*begin_fn)(), ITER_TYPE (CONTAINER_TYPE::*end_fn)()>
310 class EntityRange {
311 public:
312 EntityRange(CONTAINER_TYPE &container) : container_(container) {}
313 ITER_TYPE begin() { return (container_.*begin_fn)(); }
314 ITER_TYPE end() { return (container_.*end_fn)(); }
315
316 private:
317 CONTAINER_TYPE &container_;
318 };
319 typedef EntityRange<const PolyConnectivity, PolyConnectivity::ConstVertexIter, &PolyConnectivity::vertices_begin, &PolyConnectivity::vertices_end> ConstVertexRange;
320 typedef EntityRange<const PolyConnectivity, PolyConnectivity::ConstHalfedgeIter, &PolyConnectivity::halfedges_begin, &PolyConnectivity::halfedges_end> ConstHalfedgeRange;
321 typedef EntityRange<const PolyConnectivity, PolyConnectivity::ConstEdgeIter, &PolyConnectivity::edges_begin, &PolyConnectivity::edges_end> ConstEdgeRange;
322 typedef EntityRange<const PolyConnectivity, PolyConnectivity::ConstFaceIter, &PolyConnectivity::faces_begin, &PolyConnectivity::faces_end> ConstFaceRange;
323
327 ConstVertexRange vertices() const { return ConstVertexRange(*this); }
328
332 ConstHalfedgeRange halfedges() const { return ConstHalfedgeRange(*this); }
333
337 ConstEdgeRange edges() const { return ConstEdgeRange(*this); }
338
342 ConstFaceRange faces() const { return ConstFaceRange(*this); }
344
345
346
350
352 VertexIter vertices_sbegin()
353 { return VertexIter(*this, VertexHandle(0), true); }
355 ConstVertexIter vertices_sbegin() const
356 { return ConstVertexIter(*this, VertexHandle(0), true); }
357
359 HalfedgeIter halfedges_sbegin()
360 { return HalfedgeIter(*this, HalfedgeHandle(0), true); }
362 ConstHalfedgeIter halfedges_sbegin() const
363 { return ConstHalfedgeIter(*this, HalfedgeHandle(0), true); }
364
366 EdgeIter edges_sbegin()
367 { return EdgeIter(*this, EdgeHandle(0), true); }
369 ConstEdgeIter edges_sbegin() const
370 { return ConstEdgeIter(*this, EdgeHandle(0), true); }
371
373 FaceIter faces_sbegin()
374 { return FaceIter(*this, FaceHandle(0), true); }
376 ConstFaceIter faces_sbegin() const
377 { return ConstFaceIter(*this, FaceHandle(0), true); }
378
380
381 //--- circulators ---
382
386
388 VertexVertexIter vv_iter(VertexHandle _vh)
389 { return VertexVertexIter(*this, _vh); }
391 VertexIHalfedgeIter vih_iter(VertexHandle _vh)
392 { return VertexIHalfedgeIter(*this, _vh); }
394 VertexOHalfedgeIter voh_iter(VertexHandle _vh)
395 { return VertexOHalfedgeIter(*this, _vh); }
397 VertexEdgeIter ve_iter(VertexHandle _vh)
398 { return VertexEdgeIter(*this, _vh); }
400 VertexFaceIter vf_iter(VertexHandle _vh)
401 { return VertexFaceIter(*this, _vh); }
402
404 ConstVertexVertexIter cvv_iter(VertexHandle _vh) const
405 { return ConstVertexVertexIter(*this, _vh); }
407 ConstVertexIHalfedgeIter cvih_iter(VertexHandle _vh) const
408 { return ConstVertexIHalfedgeIter(*this, _vh); }
410 ConstVertexOHalfedgeIter cvoh_iter(VertexHandle _vh) const
411 { return ConstVertexOHalfedgeIter(*this, _vh); }
413 ConstVertexEdgeIter cve_iter(VertexHandle _vh) const
414 { return ConstVertexEdgeIter(*this, _vh); }
416 ConstVertexFaceIter cvf_iter(VertexHandle _vh) const
417 { return ConstVertexFaceIter(*this, _vh); }
418
420 FaceVertexIter fv_iter(FaceHandle _fh)
421 { return FaceVertexIter(*this, _fh); }
423 FaceHalfedgeIter fh_iter(FaceHandle _fh)
424 { return FaceHalfedgeIter(*this, _fh); }
426 FaceEdgeIter fe_iter(FaceHandle _fh)
427 { return FaceEdgeIter(*this, _fh); }
429 FaceFaceIter ff_iter(FaceHandle _fh)
430 { return FaceFaceIter(*this, _fh); }
431
433 ConstFaceVertexIter cfv_iter(FaceHandle _fh) const
434 { return ConstFaceVertexIter(*this, _fh); }
436 ConstFaceHalfedgeIter cfh_iter(FaceHandle _fh) const
437 { return ConstFaceHalfedgeIter(*this, _fh); }
439 ConstFaceEdgeIter cfe_iter(FaceHandle _fh) const
440 { return ConstFaceEdgeIter(*this, _fh); }
442 ConstFaceFaceIter cff_iter(FaceHandle _fh) const
443 { return ConstFaceFaceIter(*this, _fh); }
444
445 // 'begin' circulators
446
448 VertexVertexIter vv_begin(VertexHandle _vh)
449 { return VertexVertexIter(*this, _vh); }
451 VertexIHalfedgeIter vih_begin(VertexHandle _vh)
452 { return VertexIHalfedgeIter(*this, _vh); }
454 VertexOHalfedgeIter voh_begin(VertexHandle _vh)
455 { return VertexOHalfedgeIter(*this, _vh); }
457 VertexEdgeIter ve_begin(VertexHandle _vh)
458 { return VertexEdgeIter(*this, _vh); }
460 VertexFaceIter vf_begin(VertexHandle _vh)
461 { return VertexFaceIter(*this, _vh); }
462
464 ConstVertexVertexIter cvv_begin(VertexHandle _vh) const
465 { return ConstVertexVertexIter(*this, _vh); }
467 ConstVertexIHalfedgeIter cvih_begin(VertexHandle _vh) const
468 { return ConstVertexIHalfedgeIter(*this, _vh); }
470 ConstVertexOHalfedgeIter cvoh_begin(VertexHandle _vh) const
471 { return ConstVertexOHalfedgeIter(*this, _vh); }
473 ConstVertexEdgeIter cve_begin(VertexHandle _vh) const
474 { return ConstVertexEdgeIter(*this, _vh); }
476 ConstVertexFaceIter cvf_begin(VertexHandle _vh) const
477 { return ConstVertexFaceIter(*this, _vh); }
478
480 FaceVertexIter fv_begin(FaceHandle _fh)
481 { return FaceVertexIter(*this, _fh); }
483 FaceHalfedgeIter fh_begin(FaceHandle _fh)
484 { return FaceHalfedgeIter(*this, _fh); }
486 FaceEdgeIter fe_begin(FaceHandle _fh)
487 { return FaceEdgeIter(*this, _fh); }
489 FaceFaceIter ff_begin(FaceHandle _fh)
490 { return FaceFaceIter(*this, _fh); }
491
493 ConstFaceVertexIter cfv_begin(FaceHandle _fh) const
494 { return ConstFaceVertexIter(*this, _fh); }
496 ConstFaceHalfedgeIter cfh_begin(FaceHandle _fh) const
497 { return ConstFaceHalfedgeIter(*this, _fh); }
499 ConstFaceEdgeIter cfe_begin(FaceHandle _fh) const
500 { return ConstFaceEdgeIter(*this, _fh); }
502 ConstFaceFaceIter cff_begin(FaceHandle _fh) const
503 { return ConstFaceFaceIter(*this, _fh); }
504
505 // 'end' circulators
506
508 VertexVertexIter vv_end(VertexHandle _vh)
509 { return VertexVertexIter(*this, _vh, true); }
511 VertexIHalfedgeIter vih_end(VertexHandle _vh)
512 { return VertexIHalfedgeIter(*this, _vh, true); }
514 VertexOHalfedgeIter voh_end(VertexHandle _vh)
515 { return VertexOHalfedgeIter(*this, _vh, true); }
517 VertexEdgeIter ve_end(VertexHandle _vh)
518 { return VertexEdgeIter(*this, _vh, true); }
520 VertexFaceIter vf_end(VertexHandle _vh)
521 { return VertexFaceIter(*this, _vh, true); }
522
524 ConstVertexVertexIter cvv_end(VertexHandle _vh) const
525 { return ConstVertexVertexIter(*this, _vh, true); }
527 ConstVertexIHalfedgeIter cvih_end(VertexHandle _vh) const
528 { return ConstVertexIHalfedgeIter(*this, _vh, true); }
530 ConstVertexOHalfedgeIter cvoh_end(VertexHandle _vh) const
531 { return ConstVertexOHalfedgeIter(*this, _vh, true); }
533 ConstVertexEdgeIter cve_end(VertexHandle _vh) const
534 { return ConstVertexEdgeIter(*this, _vh, true); }
536 ConstVertexFaceIter cvf_end(VertexHandle _vh) const
537 { return ConstVertexFaceIter(*this, _vh, true); }
538
540 FaceVertexIter fv_end(FaceHandle _fh)
541 { return FaceVertexIter(*this, _fh, true); }
543 FaceHalfedgeIter fh_end(FaceHandle _fh)
544 { return FaceHalfedgeIter(*this, _fh, true); }
546 FaceEdgeIter fe_end(FaceHandle _fh)
547 { return FaceEdgeIter(*this, _fh, true); }
549 FaceFaceIter ff_end(FaceHandle _fh)
550 { return FaceFaceIter(*this, _fh, true); }
551
553 ConstFaceVertexIter cfv_end(FaceHandle _fh) const
554 { return ConstFaceVertexIter(*this, _fh, true); }
556 ConstFaceHalfedgeIter cfh_end(FaceHandle _fh) const
557 { return ConstFaceHalfedgeIter(*this, _fh, true); }
559 ConstFaceEdgeIter cfe_end(FaceHandle _fh) const
560 { return ConstFaceEdgeIter(*this, _fh, true); }
562 ConstFaceFaceIter cff_end(FaceHandle _fh) const
563 { return ConstFaceFaceIter(*this, _fh, true); }
565
566
567 //===========================================================================
570 //===========================================================================
571
579 bool is_boundary(HalfedgeHandle _heh) const
580 { return ArrayKernel::is_boundary(_heh); }
581
590 bool is_boundary(EdgeHandle _eh) const
591 {
592 return (is_boundary(halfedge_handle(_eh, 0)) ||
593 is_boundary(halfedge_handle(_eh, 1)));
594 }
595
607 bool is_boundary(VertexHandle _vh) const
608 {
609 HalfedgeHandle heh(halfedge_handle(_vh));
610 return (!(heh.is_valid() && face_handle(heh).is_valid()));
611 }
612
622 bool is_boundary(FaceHandle _fh, bool _check_vertex=false) const;
623
634 bool is_manifold(VertexHandle _vh) const;
635
638 // --- shortcuts ---
639
641 inline FaceHandle opposite_face_handle(HalfedgeHandle _heh) const
642 { return face_handle(opposite_halfedge_handle(_heh)); }
643
644 // --- misc ---
645
649 void adjust_outgoing_halfedge(VertexHandle _vh);
650
652 HalfedgeHandle find_halfedge(VertexHandle _start_vh, VertexHandle _end_vh) const;
654 uint valence(VertexHandle _vh) const;
656 uint valence(FaceHandle _fh) const;
657
658 // --- connectivity operattions
659
674 void collapse(HalfedgeHandle _heh);
679 bool is_simple_link(EdgeHandle _eh) const;
684 bool is_simply_connected(FaceHandle _fh) const;
697 FaceHandle remove_edge(EdgeHandle _eh);
701 void reinsert_edge(EdgeHandle _eh);
711 HalfedgeHandle insert_edge(HalfedgeHandle _prev_heh, HalfedgeHandle _next_heh);
712
725 void split(FaceHandle _fh, VertexHandle _vh);
726
740 void split_copy(FaceHandle _fh, VertexHandle _vh);
741
755 void triangulate(FaceHandle _fh);
756
759 void triangulate();
760
771 void split_edge(EdgeHandle _eh, VertexHandle _vh);
772
784 void split_edge_copy(EdgeHandle _eh, VertexHandle _vh);
785
786
792
793 const Vertex& deref(VertexHandle _h) const { return vertex(_h); }
794 Vertex& deref(VertexHandle _h) { return vertex(_h); }
795 const Halfedge& deref(HalfedgeHandle _h) const { return halfedge(_h); }
796 Halfedge& deref(HalfedgeHandle _h) { return halfedge(_h); }
797 const Edge& deref(EdgeHandle _h) const { return edge(_h); }
798 Edge& deref(EdgeHandle _h) { return edge(_h); }
799 const Face& deref(FaceHandle _h) const { return face(_h); }
800 Face& deref(FaceHandle _h) { return face(_h); }
802
803 protected:
805 void collapse_edge(HalfedgeHandle _hh);
807 void collapse_loop(HalfedgeHandle _hh);
808
809
810
811 private: // Working storage for add_face()
812 struct AddFaceEdgeInfo
813 {
814 HalfedgeHandle halfedge_handle;
815 bool is_new;
816 bool needs_adjust;
817 };
818 std::vector<AddFaceEdgeInfo> edgeData_; //
819 std::vector<std::pair<HalfedgeHandle, HalfedgeHandle> > next_cache_; // cache for set_next_halfedge and vertex' set_halfedge
820 uint next_cache_count_;
821
822 };
823
824 }//namespace OpenMesh
825
826 #endif//OPENMESH_POLYCONNECTIVITY_HH