Developer Documentation
 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 
58 public:
59 
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 
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 
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 
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_ */
size_t valence(const FaceHandle &_fh) const
Get valence of face (number of incident edges)
void set_cell(const CellHandle &_ch, const std::vector< HalfFaceHandle > &_hfs)
Set the half-faces of a cell.
virtual size_t n_cells() const
Get number of cells in mesh.
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.
FaceIter delete_face_core(const FaceHandle &_h)
Delete face from mesh.
virtual VertexHandle add_vertex()
Add abstract vertex.
const Face & face(const FaceHandle &_faceHandle) const
Get face with handle _faceHandle.
size_t valence(const CellHandle &_ch) const
Get valence of cell (number of incident faces)
size_t valence(const EdgeHandle &_eh) const
Get valence of edge (number of incident faces)
void resize_cprops(size_t _nc)
Change size of stored cell properties.
Edge halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get edge that corresponds to halfedge with handle _halfEdgeHandle.
virtual size_t n_vertices() const
Get number of vertices in mesh.
virtual EdgeHandle add_edge(const VertexHandle &_fromVertex, const VertexHandle &_toHandle, bool _allowDuplicates=false)
Add edge.
void resize_eprops(size_t _ne)
Change size of stored edge properties.
virtual CellIter delete_cell(const CellHandle &_h)
Delete cell from mesh.
virtual void clear(bool _clearProps=true)
Clear whole mesh.
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
virtual void collect_garbage()
Delete all entities that are marked as deleted.
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
EdgeIter delete_edge_core(const EdgeHandle &_h)
Delete edge from mesh.
CellIter delete_cell_range(const CellIter &_first, const CellIter &_last)
Delete range of cells.
const Cell & cell(const CellHandle &_cellHandle) const
Get cell with handle _cellHandle.
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
const Edge & edge(const EdgeHandle &_edgeHandle) const
Get edge with handle _edgeHandle.
virtual size_t n_edges() const
Get number of edges in mesh.
virtual EdgeIter delete_edge(const EdgeHandle &_h)
Delete edge from mesh.
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.
HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get previous halfedge within a halfface.
HalfFaceHandle halfface_extensive(const std::vector< VertexHandle > &_vs) const
void set_face(const FaceHandle &_fh, const std::vector< HalfEdgeHandle > &_hes)
Set the half-edges of a face.
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
Face opposite_halfface(const HalfFaceHandle &_halfFaceHandle) const
Get opposite halfface that corresponds to halfface with handle _halfFaceHandle.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
virtual FaceIter delete_face(const FaceHandle &_h)
Delete face from mesh.
void resize_fprops(size_t _nf)
Change size of stored face properties.
size_t valence(const VertexHandle &_vh) const
Get valence of vertex (number of incident edges)
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.
void set_edge(const EdgeHandle &_eh, const VertexHandle &_fromVertex, const VertexHandle &_toVertex)
Set the vertices of an edge.
bool bind(osg::GeometryPtr &_geo, Mesh &_mesh)
Definition: bindT.hh:106
CellIter delete_cell_core(const CellHandle &_h)
Delete cell from mesh.
virtual size_t n_halffaces() const
Get number of halffaces in mesh.
Edge opposite_halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle.
virtual VertexIter delete_vertex(const VertexHandle &_h)
Delete vertex from mesh.
VertexIter delete_vertex_core(const VertexHandle &_h)
Delete vertex from mesh.
void resize_vprops(size_t _nv)
Change size of stored vertex properties.
virtual size_t n_faces() const
Get number of faces in mesh.
virtual size_t n_halfedges() const
Get number of halfedges in mesh.