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
TopologyKernel.hh
1 /*===========================================================================*\
2 * *
3 * OpenVolumeMesh *
4 * Copyright (C) 2011 by Computer Graphics Group, RWTH Aachen *
5 * www.openvolumemesh.org *
6 * *
7 *---------------------------------------------------------------------------*
8 * This file is part of OpenVolumeMesh. *
9 * *
10 * OpenVolumeMesh 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 * OpenVolumeMesh 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 OpenVolumeMesh. If not, *
31 * see <http://www.gnu.org/licenses/>. *
32 * *
33 \*===========================================================================*/
34
35 /*===========================================================================*\
36 * *
37 * $Revision$ *
38 * $Date$ *
39 * $LastChangedBy$ *
40 * *
41 \*===========================================================================*/
42
43 #ifndef TOPOLOGYKERNEL_HH_
44 #define TOPOLOGYKERNEL_HH_
45
46 #include <cassert>
47 #include <set>
48 #include <vector>
49
50 #include "BaseEntities.hh"
51 #include "OpenVolumeMeshHandle.hh"
52 #include "ResourceManager.hh"
53 #include "Iterators.hh"
54
55 namespace OpenVolumeMesh {
56
57 class TopologyKernel : public ResourceManager {
58 public:
59
60 TopologyKernel();
61 virtual ~TopologyKernel();
62
63 /*
64 * Defines and constants
65 */
66
67 static const VertexHandle InvalidVertexHandle;
68 static const EdgeHandle InvalidEdgeHandle;
69 static const FaceHandle InvalidFaceHandle;
70 static const CellHandle InvalidCellHandle;
71 static const HalfEdgeHandle InvalidHalfEdgeHandle;
72 static const HalfFaceHandle InvalidHalfFaceHandle;
73
74 typedef OpenVolumeMeshEdge Edge;
75 typedef OpenVolumeMeshFace Face;
76 typedef OpenVolumeMeshCell Cell;
77
78 // Add StatusAttrib to list of friend classes
79 // since it provides a garbage collection
80 // that needs access to some protected methods
81 friend class StatusAttrib;
82
83 //=====================================================================
84 // Iterators
85 //=====================================================================
86
87 friend class VertexOHalfEdgeIter;
88 friend class HalfEdgeHalfFaceIter;
89 friend class VertexCellIter;
90 friend class HalfEdgeCellIter;
91 friend class CellVertexIter;
92 friend class CellCellIter;
93 friend class HalfFaceVertexIter;
94 friend class BoundaryHalfFaceHalfFaceIter;
95 friend class BoundaryFaceIter;
96 friend class VertexIter;
97 friend class EdgeIter;
98 friend class HalfEdgeIter;
99 friend class FaceIter;
100 friend class HalfFaceIter;
101 friend class CellIter;
102
103 /*
104 * Circulators
105 */
106
107 protected:
108 template <class Circulator>
109 static Circulator make_end_circulator(const Circulator& _circ)
110 {
111 Circulator end = _circ;
112 if (end.valid()) {
113 end.lap(_circ.max_laps());
114 end.valid(false);
115 }
116 return end;
117 }
118
119 public:
120
121 VertexOHalfEdgeIter voh_iter(const VertexHandle& _h, int _max_laps = 1) const {
122 return VertexOHalfEdgeIter(_h, this, _max_laps);
123 }
124
125 std::pair<VertexOHalfEdgeIter, VertexOHalfEdgeIter> outgoing_halfedges(const VertexHandle& _h, int _max_laps = 1) const {
126 VertexOHalfEdgeIter begin = voh_iter(_h, _max_laps);
127 return std::make_pair(begin, make_end_circulator(begin));
128 }
129
130 HalfEdgeHalfFaceIter hehf_iter(const HalfEdgeHandle& _h, int _max_laps = 1) const {
131 return HalfEdgeHalfFaceIter(_h, this, _max_laps);
132 }
133
134 std::pair<HalfEdgeHalfFaceIter, HalfEdgeHalfFaceIter> halfedge_halffaces(const HalfEdgeHandle& _h, int _max_laps = 1) const {
135 HalfEdgeHalfFaceIter begin = hehf_iter(_h, _max_laps);
136 return std::make_pair(begin, make_end_circulator(begin));
137 }
138
139 VertexCellIter vc_iter(const VertexHandle& _h, int _max_laps = 1) const {
140 return VertexCellIter(_h, this, _max_laps);
141 }
142
143 std::pair<VertexCellIter, VertexCellIter> vertex_cells(const VertexHandle& _h, int _max_laps = 1){
144 VertexCellIter begin = vc_iter(_h, _max_laps);
145 return std::make_pair(begin, make_end_circulator(begin));
146 }
147
148 HalfEdgeCellIter hec_iter(const HalfEdgeHandle& _h, int _max_laps = 1) const {
149 return HalfEdgeCellIter(_h, this, _max_laps);
150 }
151
152 std::pair<HalfEdgeCellIter, HalfEdgeCellIter> halfedge_cells(const HalfEdgeHandle& _h, int _max_laps = 1){
153 HalfEdgeCellIter begin = hec_iter(_h, _max_laps);
154 return std::make_pair(begin, make_end_circulator(begin));
155 }
156
157 CellVertexIter cv_iter(const CellHandle& _h, int _max_laps = 1) const {
158 return CellVertexIter(_h, this, _max_laps);
159 }
160
161 std::pair<CellVertexIter, CellVertexIter> cell_vertices(const CellHandle& _h, int _max_laps = 1) const {
162 CellVertexIter begin = cv_iter(_h, _max_laps);
163 return std::make_pair(begin, make_end_circulator(begin));
164 }
165
166 CellCellIter cc_iter(const CellHandle& _h, int _max_laps = 1) const {
167 return CellCellIter(_h, this, _max_laps);
168 }
169
170 std::pair<CellCellIter, CellCellIter> cell_cells(const CellHandle& _h, int _max_laps = 1) const {
171 CellCellIter begin = cc_iter(_h, _max_laps);
172 return std::make_pair(begin, make_end_circulator(begin));
173 }
174
175 HalfFaceVertexIter hfv_iter(const HalfFaceHandle& _h, int _max_laps = 1) const {
176 return HalfFaceVertexIter(_h, this, _max_laps);
177 }
178
179 std::pair<HalfFaceVertexIter, HalfFaceVertexIter> halfface_vertices(const HalfFaceHandle& _h, int _max_laps = 1) const {
180 HalfFaceVertexIter begin = hfv_iter(_h, _max_laps);
181 return std::make_pair(begin, make_end_circulator(begin));
182 }
183
184 BoundaryHalfFaceHalfFaceIter bhfhf_iter(const HalfFaceHandle& _ref_h, int _max_laps = 1) const {
185 return BoundaryHalfFaceHalfFaceIter(_ref_h, this, _max_laps);
186 }
187
188 std::pair<BoundaryHalfFaceHalfFaceIter, BoundaryHalfFaceHalfFaceIter> boundary_halfface_halffaces(const HalfFaceHandle& _h, int _max_laps = 1) const {
189 BoundaryHalfFaceHalfFaceIter begin = bhfhf_iter(_h, _max_laps);
190 return std::make_pair(begin, make_end_circulator(begin));
191 }
192
193 /*
194 * Iterators
195 */
196
197 BoundaryFaceIter bf_iter() const {
198 return BoundaryFaceIter(this);
199 }
200
201 VertexIter v_iter() const {
202 return VertexIter(this);
203 }
204
205 VertexIter vertices_begin() const {
206 return VertexIter(this, VertexHandle(0));
207 }
208
209 VertexIter vertices_end() const {
210 return VertexIter(this, VertexHandle(n_vertices()));
211 }
212
213 std::pair<VertexIter, VertexIter> vertices() const {
214 return std::make_pair(vertices_begin(), vertices_end());
215 }
216
217 EdgeIter e_iter() const {
218 return EdgeIter(this);
219 }
220
221 EdgeIter edges_begin() const {
222 return EdgeIter(this, EdgeHandle(0));
223 }
224
225 EdgeIter edges_end() const {
226 return EdgeIter(this, EdgeHandle(edges_.size()));
227 }
228
229 std::pair<EdgeIter, EdgeIter> edges() const {
230 return std::make_pair(edges_begin(), edges_end());
231 }
232
233 HalfEdgeIter he_iter() const {
234 return HalfEdgeIter(this);
235 }
236
237 HalfEdgeIter halfedges_begin() const {
238 return HalfEdgeIter(this, HalfEdgeHandle(0));
239 }
240
241 HalfEdgeIter halfedges_end() const {
242 return HalfEdgeIter(this, HalfEdgeHandle(edges_.size() * 2));
243 }
244
245 std::pair<HalfEdgeIter, HalfEdgeIter> halfedges() const {
246 return std::make_pair(halfedges_begin(), halfedges_end());
247 }
248
249 FaceIter f_iter() const {
250 return FaceIter(this);
251 }
252
253 FaceIter faces_begin() const {
254 return FaceIter(this, FaceHandle(0));
255 }
256
257 FaceIter faces_end() const {
258 return FaceIter(this, FaceHandle(faces_.size()));
259 }
260
261 std::pair<FaceIter, FaceIter> faces() const {
262 return std::make_pair(faces_begin(), faces_end());
263 }
264
265 HalfFaceIter hf_iter() const {
266 return HalfFaceIter(this);
267 }
268
269 HalfFaceIter halffaces_begin() const {
270 return HalfFaceIter(this, HalfFaceHandle(0));
271 }
272
273 HalfFaceIter halffaces_end() const {
274 return HalfFaceIter(this, HalfFaceHandle(faces_.size() * 2));
275 }
276
277 std::pair<HalfFaceIter, HalfFaceIter> halffaces() const {
278 return std::make_pair(halffaces_begin(), halffaces_end());
279 }
280
281 CellIter c_iter() const {
282 return CellIter(this);
283 }
284
285 CellIter cells_begin() const {
286 return CellIter(this, CellHandle(0));
287 }
288
289 CellIter cells_end() const {
290 return CellIter(this, CellHandle(cells_.size()));
291 }
292
293 std::pair<CellIter, CellIter> cells() const {
294 return std::make_pair(cells_begin(), cells_end());
295 }
296
297 /*
298 * Virtual functions with implementation
299 */
300
302 virtual size_t n_vertices() const { return n_vertices_; }
304 virtual size_t n_edges() const { return edges_.size(); }
306 virtual size_t n_halfedges() const { return edges_.size() * 2u; }
308 virtual size_t n_faces() const { return faces_.size(); }
310 virtual size_t n_halffaces() const { return faces_.size() * 2u; }
312 virtual size_t n_cells() const { return cells_.size(); }
313
314 int genus() const {
315
316 int g = (1 - (n_vertices() -
317 n_edges() +
318 n_faces() -
319 n_cells()));
320
321 if(g % 2 == 0) return (g / 2);
322
323 // An error occured
324 // The mesh might not be manifold
325 return -1;
326 }
327
328 private:
329
330 // Cache total vertex number
331 size_t n_vertices_;
332
333 public:
334
336 virtual VertexHandle add_vertex();
337
338 //=======================================================================
339
341 virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
342
350 virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
351
353 virtual FaceHandle add_face(const std::vector<VertexHandle>& _vertices);
354
362 virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
363
365 void set_edge(const EdgeHandle& _eh, const VertexHandle& _fromVertex, const VertexHandle& _toVertex);
366
368 void set_face(const FaceHandle& _fh, const std::vector<HalfEdgeHandle>& _hes);
369
371 void set_cell(const CellHandle& _ch, const std::vector<HalfFaceHandle>& _hfs);
372
373 /*
374 * Non-virtual functions
375 */
376
378 const Edge& edge(const EdgeHandle& _edgeHandle) const;
379
381 const Face& face(const FaceHandle& _faceHandle) const;
382
384 const Cell& cell(const CellHandle& _cellHandle) const;
385
387 Edge& edge(const EdgeHandle& _edgeHandle);
388
390 Face& face(const FaceHandle& _faceHandle);
391
393 Cell& cell(const CellHandle& _cellHandle);
394
396 Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
397
399 Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
400
402 Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
403
405 Face opposite_halfface(const HalfFaceHandle& _halfFaceHandle) const;
406
408 HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
409
413 HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
414
418 HalfFaceHandle halfface_extensive(const std::vector<VertexHandle>& _vs) const;
419
423 HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
424
426 HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
427
429 HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
430
432 inline size_t valence(const VertexHandle& _vh) const {
433 assert(has_vertex_bottom_up_incidences());
434 assert(_vh.is_valid() && (size_t)_vh.idx() < outgoing_hes_per_vertex_.size());
435
436 return outgoing_hes_per_vertex_[_vh.idx()].size();
437 }
438
440 inline size_t valence(const EdgeHandle& _eh) const {
441 assert(has_edge_bottom_up_incidences());
442 assert(_eh.is_valid() && (size_t)_eh.idx() < edges_.size());
443 assert((size_t)halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
444
445 return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
446 }
447
449 inline size_t valence(const FaceHandle& _fh) const {
450 assert(_fh.is_valid() && (size_t)_fh.idx() < faces_.size());
451
452 return face(_fh).halfedges().size();
453 }
454
456 inline size_t valence(const CellHandle& _ch) const {
457 assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
458
459 return cell(_ch).halffaces().size();
460 }
461
462 //=====================================================================
463 // Delete entities
464 //=====================================================================
465
466 public:
467
468 virtual VertexIter delete_vertex(const VertexHandle& _h);
469
470 virtual EdgeIter delete_edge(const EdgeHandle& _h);
471
472 virtual FaceIter delete_face(const FaceHandle& _h);
473
474 virtual CellIter delete_cell(const CellHandle& _h);
475
476 virtual void collect_garbage();
477
478
479 virtual bool is_deleted(const VertexHandle& _h) const { return vertex_deleted_[_h.idx()]; }
480 virtual bool is_deleted(const EdgeHandle& _h) const { return edge_deleted_[_h.idx()]; }
481 virtual bool is_deleted(const HalfEdgeHandle& _h) const { return edge_deleted_[_h.idx()/2]; }
482 virtual bool is_deleted(const FaceHandle& _h) const { return face_deleted_[_h.idx()]; }
483 virtual bool is_deleted(const HalfFaceHandle& _h) const { return face_deleted_[_h.idx()/2]; }
484 virtual bool is_deleted(const CellHandle& _h) const { return cell_deleted_[_h.idx()]; }
485
486 private:
487
488 template <class ContainerT>
489 void get_incident_edges(const ContainerT& _vs, std::set<EdgeHandle>& _es) const;
490
491 template <class ContainerT>
492 void get_incident_faces(const ContainerT& _es, std::set<FaceHandle>& _fs) const;
493
494 template <class ContainerT>
495 void get_incident_cells(const ContainerT& _fs, std::set<CellHandle>& _cs) const;
496
497 VertexIter delete_vertex_core(const VertexHandle& _h);
498
499 EdgeIter delete_edge_core(const EdgeHandle& _h);
500
501 FaceIter delete_face_core(const FaceHandle& _h);
502
503 CellIter delete_cell_core(const CellHandle& _h);
504
505 protected:
506
507 virtual void swap_cells(CellHandle _h1, CellHandle _h2);
508
509 virtual void swap_faces(FaceHandle _h1, FaceHandle _h2);
510
511 virtual void swap_edges(EdgeHandle _h1, EdgeHandle _h2);
512
513 virtual void swap_vertices(VertexHandle _h1, VertexHandle _h2);
514
515 virtual void delete_multiple_vertices(const std::vector<bool>& _tag);
516
517 virtual void delete_multiple_edges(const std::vector<bool>& _tag);
518
519 virtual void delete_multiple_faces(const std::vector<bool>& _tag);
520
521 virtual void delete_multiple_cells(const std::vector<bool>& _tag);
522
523 class EdgeCorrector {
524 public:
525 EdgeCorrector(const std::vector<int>& _newIndices) :
526 newIndices_(_newIndices) {}
527
528 void operator()(Edge& _edge) {
529 _edge.set_from_vertex(VertexHandle(newIndices_[_edge.from_vertex().idx()]));
530 _edge.set_to_vertex(VertexHandle(newIndices_[_edge.to_vertex().idx()]));
531 }
532 private:
533 const std::vector<int>& newIndices_;
534 };
535
536 class FaceCorrector {
537 public:
538 FaceCorrector(const std::vector<int>& _newIndices) :
539 newIndices_(_newIndices) {}
540
541 void operator()(Face& _face) {
542 std::vector<HalfEdgeHandle> hes = _face.halfedges();
543 for(std::vector<HalfEdgeHandle>::iterator he_it = hes.begin(),
544 he_end = hes.end(); he_it != he_end; ++he_it) {
545
546 EdgeHandle eh = edge_handle(*he_it);
547 unsigned char opp = (he_it->idx() - halfedge_handle(eh, 0).idx());
548 *he_it = halfedge_handle(newIndices_[eh.idx()], opp);
549 }
550 _face.set_halfedges(hes);
551 }
552 private:
553 const std::vector<int>& newIndices_;
554 };
555
556 class CellCorrector {
557 public:
558 CellCorrector(const std::vector<int>& _newIndices) :
559 newIndices_(_newIndices) {}
560
561 void operator()(Cell& _cell) {
562 std::vector<HalfFaceHandle> hfs = _cell.halffaces();
563 for(std::vector<HalfFaceHandle>::iterator hf_it = hfs.begin(),
564 hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {
565
566 FaceHandle fh = face_handle(*hf_it);
567 unsigned char opp = (hf_it->idx() - halfface_handle(fh, 0).idx());
568 *hf_it = halfface_handle(newIndices_[fh.idx()], opp);
569 }
570 _cell.set_halffaces(hfs);
571 }
572 private:
573 const std::vector<int>& newIndices_;
574 };
575
576 public:
577
586 CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);
587
588 public:
589
591 virtual void clear(bool _clearProps = true) {
592
593 edges_.clear();
594 faces_.clear();
595 cells_.clear();
596 vertex_deleted_.clear();
597 edge_deleted_.clear();
598 face_deleted_.clear();
599 cell_deleted_.clear();
600 outgoing_hes_per_vertex_.clear();
601 incident_hfs_per_he_.clear();
602 incident_cell_per_hf_.clear();
603 n_vertices_ = 0;
604
605 if(_clearProps) {
606
607 // Delete all property data
608 clear_vertex_props();
609 clear_edge_props();
610 clear_halfedge_props();
611 clear_face_props();
612 clear_halfface_props();
613 clear_cell_props();
614 clear_mesh_props();
615
616 } else {
617 // Resize props
618 resize_vprops(0u);
619 resize_eprops(0u);
620 resize_fprops(0u);
621 resize_cprops(0u);
622 }
623 }
624
625 //=====================================================================
626 // Bottom-up Incidences
627 //=====================================================================
628
629 public:
630
631 void enable_bottom_up_incidences(bool _enable = true) {
632
633 enable_vertex_bottom_up_incidences(_enable);
634 enable_edge_bottom_up_incidences(_enable);
635 enable_face_bottom_up_incidences(_enable);
636 }
637
638 void enable_vertex_bottom_up_incidences(bool _enable = true) {
639
640 if(_enable && !v_bottom_up_) {
641 // Vertex bottom-up incidences have to be
642 // recomputed for the whole mesh
643 compute_vertex_bottom_up_incidences();
644 }
645
646 if(!_enable) {
647 outgoing_hes_per_vertex_.clear();
648 }
649
650 v_bottom_up_ = _enable;
651 }
652
653 void enable_edge_bottom_up_incidences(bool _enable = true) {
654
655 if(_enable && !e_bottom_up_) {
656 // Edge bottom-up incidences have to be
657 // recomputed for the whole mesh
658 compute_edge_bottom_up_incidences();
659
660 if(f_bottom_up_) {
661 #if defined(__clang_major__) && (__clang_major__ >= 5)
662 for(EdgeIter e_it = edges_begin(), e_end = edges_end();
663 e_it != e_end; ++e_it) {
664 reorder_incident_halffaces(*e_it);
665 }
666 #else
667 std::for_each(edges_begin(), edges_end(),
668 fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
669 #endif
670 }
671 }
672
673 if(!_enable) {
674 incident_hfs_per_he_.clear();
675 }
676
677 e_bottom_up_ = _enable;
678 }
679
680 void enable_face_bottom_up_incidences(bool _enable = true) {
681
682 bool updateOrder = false;
683 if(_enable && !f_bottom_up_) {
684 // Face bottom-up incidences have to be
685 // recomputed for the whole mesh
686 compute_face_bottom_up_incidences();
687
688 updateOrder = true;
689 }
690
691 if(!_enable) {
692 incident_cell_per_hf_.clear();
693 }
694
695 f_bottom_up_ = _enable;
696
697 if(updateOrder) {
698 if(e_bottom_up_) {
699 #if defined(__clang_major__) && (__clang_major__ >= 5)
700 for(EdgeIter e_it = edges_begin(), e_end = edges_end();
701 e_it != e_end; ++e_it) {
702 reorder_incident_halffaces(*e_it);
703 }
704 #else
705 std::for_each(edges_begin(), edges_end(),
706 fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
707 #endif
708 }
709 }
710 }
711
712 bool has_full_bottom_up_incidences() const {
713 return (has_vertex_bottom_up_incidences() &&
714 has_edge_bottom_up_incidences() &&
715 has_face_bottom_up_incidences());
716 }
717
718 bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
719
720 bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
721
722 bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
723
724
725 void enable_deferred_deletion(bool _enable = true);
726 bool deferred_deletion_enabled() const { return deferred_deletion; }
727
728
729 void enable_fast_deletion(bool _enable = true) { fast_deletion = _enable; }
730 bool fast_deletion_enabled() const { return fast_deletion; }
731
732
733 protected:
734
735 void compute_vertex_bottom_up_incidences();
736
737 void compute_edge_bottom_up_incidences();
738
739 void compute_face_bottom_up_incidences();
740
741 void reorder_incident_halffaces(const EdgeHandle& _eh);
742
743 // Outgoing halfedges per vertex
744 std::vector<std::vector<HalfEdgeHandle> > outgoing_hes_per_vertex_;
745
746 // Incident halffaces per (directed) halfedge
747 std::vector<std::vector<HalfFaceHandle> > incident_hfs_per_he_;
748
749 // Incident cell (at most one) per halfface
750 std::vector<CellHandle> incident_cell_per_hf_;
751
752 private:
753 bool v_bottom_up_;
754
755 bool e_bottom_up_;
756
757 bool f_bottom_up_;
758
759 bool deferred_deletion;
760
761 bool fast_deletion;
762
763 //=====================================================================
764 // Connectivity
765 //=====================================================================
766
767 public:
768
775 HalfFaceHandle adjacent_halfface_in_cell(const HalfFaceHandle& _halfFaceHandle, const HalfEdgeHandle& _halfEdgeHandle) const;
776
778 CellHandle incident_cell(const HalfFaceHandle& _halfFaceHandle) const;
779
780 bool is_boundary(const HalfFaceHandle& _halfFaceHandle) const {
781
782 assert(_halfFaceHandle.is_valid() && (size_t)_halfFaceHandle.idx() < faces_.size() * 2u);
783 assert(has_face_bottom_up_incidences());
784 assert((size_t)_halfFaceHandle.idx() < incident_cell_per_hf_.size());
785 return incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle;
786 }
787
788 bool is_boundary(const FaceHandle& _faceHandle) const {
789 assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
790 assert(has_face_bottom_up_incidences());
791 return is_boundary(halfface_handle(_faceHandle, 0)) ||
792 is_boundary(halfface_handle(_faceHandle, 1));
793 }
794
795 bool is_boundary(const EdgeHandle& _edgeHandle) const {
796 assert(has_edge_bottom_up_incidences());
797 assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());
798
799 for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(halfedge_handle(_edgeHandle, 0));
800 hehf_it.valid(); ++hehf_it) {
801 if(is_boundary(face_handle(*hehf_it))) {
802 return true;
803 }
804 }
805 return false;
806 }
807
808 bool is_boundary(const HalfEdgeHandle& _halfedgeHandle) const {
809 assert(has_edge_bottom_up_incidences());
810 assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);
811
812 for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(_halfedgeHandle);
813 hehf_it.valid(); ++hehf_it) {
814 if(is_boundary(face_handle(*hehf_it))) {
815 return true;
816 }
817 }
818 return false;
819 }
820
821 bool is_boundary(const VertexHandle& _vertexHandle) const {
822 assert(has_vertex_bottom_up_incidences());
823 assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() < n_vertices());
824
825 for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
826 if(is_boundary(*voh_it)) return true;
827 }
828 return false;
829 }
830
831 size_t n_vertices_in_cell(const CellHandle& _ch) const {
832 assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
833
834 std::set<VertexHandle> vertices;
835 std::vector<HalfFaceHandle> hfs = cell(_ch).halffaces();
836 for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin();
837 hf_it != hfs.end(); ++hf_it) {
838 std::vector<HalfEdgeHandle> hes = halfface(*hf_it).halfedges();
839 for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin();
840 he_it != hes.end(); ++he_it) {
841 vertices.insert(halfedge(*he_it).to_vertex());
842 }
843 }
844 return vertices.size();
845 }
846
847 //=========================================================================
848
849 /*
850 * Non-virtual functions
851 */
852
853 Edge opposite_halfedge(const Edge& _edge) const {
854 return Edge(_edge.to_vertex(), _edge.from_vertex());
855 }
856
857 Face opposite_halfface(const Face& _face) const {
858 std::vector<HalfEdgeHandle> opp_halfedges;
859 for(std::vector<HalfEdgeHandle>::const_iterator it = _face.halfedges().begin(); it
860 != _face.halfedges().end(); ++it) {
861 opp_halfedges.insert(opp_halfedges.begin(), opposite_halfedge_handle(*it));
862 }
863
864 return Face(opp_halfedges);
865 }
866
867 /*
868 * Static functions
869 */
870
872 static inline HalfEdgeHandle halfedge_handle(const EdgeHandle& _h, const unsigned char _subIdx) {
873 // Is handle in range?
874 assert(_h.is_valid());
875 assert(_subIdx < 2);
876 // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
877 return HalfEdgeHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
878 }
879
881 static inline HalfFaceHandle halfface_handle(const FaceHandle& _h, const unsigned char _subIdx) {
882 // Is handle in range?
883 assert(_h.is_valid());
884 assert(_subIdx < 2);
885 // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
886 return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
887 }
888
890 static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
891 // Is handle in range?
892 assert(_h.is_valid());
893 // if(_h.idx() < 0) return InvalidEdgeHandle;
894 return EdgeHandle((int)(_h.idx() / 2));
895 }
896
897 static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
898 // Is handle in range?
899 assert(_h.is_valid());
900 // if(_h.idx() < 0) return InvalidFaceHandle;
901 return FaceHandle((int)(_h.idx() / 2));
902 }
903
904 static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
905 // Is handle in range?
906 assert(_h.is_valid());
907 // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
908
909 // Is handle even?
910 if(_h.idx() % 2 == 0) {
911 return HalfEdgeHandle(_h.idx() + 1);
912 }
913 return HalfEdgeHandle(_h.idx() - 1);
914 }
915
916 static inline HalfFaceHandle opposite_halfface_handle(const HalfFaceHandle& _h) {
917 // Is handle in range?
918 assert(_h.is_valid());
919 // if(_h.idx() < 0) return InvalidHalfFaceHandle;
920
921 // Is handle even?
922 if(_h.idx() % 2 == 0) {
923 return HalfFaceHandle(_h.idx() + 1);
924 }
925 return HalfFaceHandle(_h.idx() - 1);
926 }
927
928 protected:
929
930 // List of edges
931 std::vector<Edge> edges_;
932
933 // List of faces
934 std::vector<Face> faces_;
935
936 // List of cells
937 std::vector<Cell> cells_;
938
939 std::vector<bool> vertex_deleted_;
940 std::vector<bool> edge_deleted_;
941 std::vector<bool> face_deleted_;
942 std::vector<bool> cell_deleted_;
943
944 };
945
946 }
947
948 #endif /* TOPOLOGYKERNEL_HH_ */
OpenVolumeMesh::TopologyKernel::valence
size_t valence(const FaceHandle &_fh) const
Get valence of face (number of incident edges)
Definition: TopologyKernel.hh:449
OpenVolumeMesh::VertexCellIter
Definition: Iterators.hh:334
OpenVolumeMesh::TopologyKernel::set_cell
void set_cell(const CellHandle &_ch, const std::vector< HalfFaceHandle > &_hfs)
Set the half-faces of a cell.
Definition: TopologyKernel.cc:554
OpenVolumeMesh::ResourceManager
Definition: ResourceManager.hh:76
OpenVolumeMesh::TopologyKernel::n_cells
virtual size_t n_cells() const
Get number of cells in mesh.
Definition: TopologyKernel.hh:312
OpenVolumeMesh::TopologyKernel::adjacent_halfface_in_cell
HalfFaceHandle adjacent_halfface_in_cell(const HalfFaceHandle &_halfFaceHandle, const HalfEdgeHandle &_halfEdgeHandle) const
Get halfface that is adjacent (w.r.t. a common halfedge) within the same cell.
Definition: TopologyKernel.cc:2259
OpenVolumeMesh::EdgeHandle
Definition: OpenVolumeMeshHandle.hh:99
OpenVolumeMesh::TopologyKernel::delete_face_core
FaceIter delete_face_core(const FaceHandle &_h)
Delete face from mesh.
Definition: TopologyKernel.cc:1194
OpenVolumeMesh::TopologyKernel::add_vertex
virtual VertexHandle add_vertex()
Add abstract vertex.
Definition: TopologyKernel.cc:76
OpenVolumeMesh::TopologyKernel::face
const Face & face(const FaceHandle &_faceHandle) const
Get face with handle _faceHandle.
Definition: TopologyKernel.cc:1990
OpenVolumeMesh::TopologyKernel::valence
size_t valence(const CellHandle &_ch) const
Get valence of cell (number of incident faces)
Definition: TopologyKernel.hh:456
OpenVolumeMesh::CellHandle
Definition: OpenVolumeMeshHandle.hh:101
OpenVolumeMesh::CellCellIter
Definition: Iterators.hh:510
OpenVolumeMesh::TopologyKernel::valence
size_t valence(const EdgeHandle &_eh) const
Get valence of edge (number of incident faces)
Definition: TopologyKernel.hh:440
OpenVolumeMesh::FaceHandle
Definition: OpenVolumeMeshHandle.hh:100
OpenVolumeMesh::StatusAttrib
Definition: StatusAttrib.hh:57
OpenVolumeMesh::ResourceManager::resize_cprops
void resize_cprops(size_t _nc)
Change size of stored cell properties.
Definition: ResourceManager.cc:79
OpenVolumeMesh::TopologyKernel::halfedge
Edge halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get edge that corresponds to halfedge with handle _halfEdgeHandle.
Definition: TopologyKernel.cc:2047
OpenVolumeMesh::OpenVolumeMeshEdge
Definition: BaseEntities.hh:52
OpenVolumeMesh::HalfFaceIter
Definition: Iterators.hh:902
OpenVolumeMesh::BoundaryHalfFaceHalfFaceIter
Definition: Iterators.hh:626
OpenVolumeMesh::TopologyKernel::n_vertices
virtual size_t n_vertices() const
Get number of vertices in mesh.
Definition: TopologyKernel.hh:302
OpenVolumeMesh::TopologyKernel::add_edge
virtual EdgeHandle add_edge(const VertexHandle &_fromVertex, const VertexHandle &_toHandle, bool _allowDuplicates=false)
Add edge.
Definition: TopologyKernel.cc:96
OpenVolumeMesh::VertexIter
Definition: Iterators.hh:686
OpenVolumeMesh::ResourceManager::resize_eprops
void resize_eprops(size_t _ne)
Change size of stored edge properties.
Definition: ResourceManager.cc:67
OpenVolumeMesh::EdgeIter
Definition: Iterators.hh:740
OpenVolumeMesh::TopologyKernel::delete_cell
virtual CellIter delete_cell(const CellHandle &_h)
Delete cell from mesh.
Definition: TopologyKernel.cc:711
OpenVolumeMesh::TopologyKernel::clear
virtual void clear(bool _clearProps=true)
Clear whole mesh.
Definition: TopologyKernel.hh:591
OpenVolumeMesh::TopologyKernel::incident_cell
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
Definition: TopologyKernel.cc:2302
OpenVolumeMesh::TopologyKernel::collect_garbage
virtual void collect_garbage()
Delete all entities that are marked as deleted.
Definition: TopologyKernel.cc:719
OpenVolumeMesh::HalfEdgeIter
Definition: Iterators.hh:794
OpenVolumeMesh::TopologyKernel::add_cell
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
Definition: TopologyKernel.cc:377
OpenVolumeMesh::CellVertexIter
Definition: Iterators.hh:452
OpenVolumeMesh::TopologyKernel::delete_edge_core
EdgeIter delete_edge_core(const EdgeHandle &_h)
Delete edge from mesh.
Definition: TopologyKernel.cc:1011
OpenVolumeMesh::TopologyKernel::delete_cell_range
CellIter delete_cell_range(const CellIter &_first, const CellIter &_last)
Delete range of cells.
Definition: TopologyKernel.cc:1952
OpenVolumeMesh::TopologyKernel::cell
const Cell & cell(const CellHandle &_cellHandle) const
Get cell with handle _cellHandle.
Definition: TopologyKernel.cc:2001
OpenVolumeMesh::HalfFaceHandle
Definition: OpenVolumeMeshHandle.hh:103
OpenVolumeMesh::BoundaryFaceIter
Definition: Iterators.hh:1010
OpenVolumeMesh::TopologyKernel::halfface
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
Definition: TopologyKernel.cc:2064
OpenVolumeMesh::TopologyKernel::edge
const Edge & edge(const EdgeHandle &_edgeHandle) const
Get edge with handle _edgeHandle.
Definition: TopologyKernel.cc:1979
OpenVolumeMesh::TopologyKernel::n_edges
virtual size_t n_edges() const
Get number of edges in mesh.
Definition: TopologyKernel.hh:304
OpenVolumeMesh::OpenVolumeMeshCell
Definition: BaseEntities.hh:119
OpenVolumeMesh::TopologyKernel::delete_edge
virtual EdgeIter delete_edge(const EdgeHandle &_h)
Delete edge from mesh.
Definition: TopologyKernel.cc:641
OpenVolumeMesh::TopologyKernel::halfedge_handle
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.
Definition: TopologyKernel.hh:872
OpenVolumeMesh::TopologyKernel::prev_halfedge_in_halfface
HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get previous halfedge within a halfface.
Definition: TopologyKernel.cc:2238
OpenVolumeMesh::TopologyKernel::halfface_extensive
HalfFaceHandle halfface_extensive(const std::vector< VertexHandle > &_vs) const
Definition: TopologyKernel.cc:2150
OpenVolumeMesh::TopologyKernel::set_face
void set_face(const FaceHandle &_fh, const std::vector< HalfEdgeHandle > &_hes)
Set the half-edges of a face.
Definition: TopologyKernel.cc:514
OpenVolumeMesh::TopologyKernel
Definition: TopologyKernel.hh:57
OpenVolumeMesh::TopologyKernel::halfface_handle
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
Definition: TopologyKernel.hh:881
OpenVolumeMesh::TopologyKernel::edge_handle
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
Definition: TopologyKernel.hh:890
OpenVolumeMesh::HalfEdgeHalfFaceIter
Definition: Iterators.hh:276
OpenVolumeMesh::VertexOHalfEdgeIter
Definition: Iterators.hh:215
OpenVolumeMesh::TopologyKernel::opposite_halfface
Face opposite_halfface(const HalfFaceHandle &_halfFaceHandle) const
Get opposite halfface that corresponds to halfface with handle _halfFaceHandle.
Definition: TopologyKernel.cc:2098
OpenVolumeMesh::TopologyKernel::add_face
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
Definition: TopologyKernel.cc:161
OpenVolumeMesh::TopologyKernel::delete_face
virtual FaceIter delete_face(const FaceHandle &_h)
Delete face from mesh.
Definition: TopologyKernel.cc:682
OpenVolumeMesh::HalfEdgeHandle
Definition: OpenVolumeMeshHandle.hh:102
OpenVolumeMesh::ResourceManager::resize_fprops
void resize_fprops(size_t _nf)
Change size of stored face properties.
Definition: ResourceManager.cc:73
OpenVolumeMesh::TopologyKernel::valence
size_t valence(const VertexHandle &_vh) const
Get valence of vertex (number of incident edges)
Definition: TopologyKernel.hh:432
OpenVolumeMesh::FaceIter
Definition: Iterators.hh:848
OpenVolumeMesh::TopologyKernel::next_halfedge_in_halfface
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.
Definition: TopologyKernel.cc:2218
OpenVolumeMesh::VertexHandle
Definition: OpenVolumeMeshHandle.hh:98
OpenVolumeMesh::OpenVolumeMeshFace
Definition: BaseEntities.hh:90
OpenVolumeMesh::TopologyKernel::set_edge
void set_edge(const EdgeHandle &_eh, const VertexHandle &_fromVertex, const VertexHandle &_toVertex)
Set the vertices of an edge.
Definition: TopologyKernel.cc:483
OpenMesh::Kernel_OSG::bind
bool bind(osg::GeometryPtr &_geo, Mesh &_mesh)
Definition: bindT.hh:106
OpenVolumeMesh::CellIter
Definition: Iterators.hh:956
OpenVolumeMesh::TopologyKernel::delete_cell_core
CellIter delete_cell_core(const CellHandle &_h)
Delete cell from mesh.
Definition: TopologyKernel.cc:1362
OpenVolumeMesh::HalfEdgeCellIter
Definition: Iterators.hh:390
OpenVolumeMesh::TopologyKernel::n_halffaces
virtual size_t n_halffaces() const
Get number of halffaces in mesh.
Definition: TopologyKernel.hh:310
OpenVolumeMesh::TopologyKernel::CellCorrector
Definition: TopologyKernel.hh:556
OpenVolumeMesh::TopologyKernel::FaceCorrector
Definition: TopologyKernel.hh:536
OpenVolumeMesh
Definition: ColorAttrib.hh:53
OpenVolumeMesh::HalfFaceVertexIter
Definition: Iterators.hh:568
OpenVolumeMesh::TopologyKernel::opposite_halfedge
Edge opposite_halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle.
Definition: TopologyKernel.cc:2081
OpenVolumeMesh::TopologyKernel::delete_vertex
virtual VertexIter delete_vertex(const VertexHandle &_h)
Delete vertex from mesh.
Definition: TopologyKernel.cc:591
OpenVolumeMesh::TopologyKernel::delete_vertex_core
VertexIter delete_vertex_core(const VertexHandle &_h)
Delete vertex from mesh.
Definition: TopologyKernel.cc:907
OpenVolumeMesh::ResourceManager::resize_vprops
void resize_vprops(size_t _nv)
Change size of stored vertex properties.
Definition: ResourceManager.cc:62
OpenVolumeMesh::TopologyKernel::n_faces
virtual size_t n_faces() const
Get number of faces in mesh.
Definition: TopologyKernel.hh:308
OpenVolumeMesh::TopologyKernel::n_halfedges
virtual size_t n_halfedges() const
Get number of halfedges in mesh.
Definition: TopologyKernel.hh:306
OpenVolumeMesh::TopologyKernel::EdgeCorrector
Definition: TopologyKernel.hh:523