57class TopologyKernel :
public ResourceManager {
61 virtual ~TopologyKernel();
81 friend class StatusAttrib;
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;
108 template <
class Circulator>
109 static Circulator make_end_circulator(
const Circulator& _circ)
111 Circulator end = _circ;
113 end.lap(_circ.max_laps());
121 VertexOHalfEdgeIter voh_iter(
const VertexHandle& _h,
int _max_laps = 1)
const {
122 return VertexOHalfEdgeIter(_h,
this, _max_laps);
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));
130 HalfEdgeHalfFaceIter hehf_iter(
const HalfEdgeHandle& _h,
int _max_laps = 1)
const {
131 return HalfEdgeHalfFaceIter(_h,
this, _max_laps);
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));
139 VertexCellIter vc_iter(
const VertexHandle& _h,
int _max_laps = 1)
const {
140 return VertexCellIter(_h,
this, _max_laps);
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));
148 HalfEdgeCellIter hec_iter(
const HalfEdgeHandle& _h,
int _max_laps = 1)
const {
149 return HalfEdgeCellIter(_h,
this, _max_laps);
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));
157 CellVertexIter cv_iter(
const CellHandle& _h,
int _max_laps = 1)
const {
158 return CellVertexIter(_h,
this, _max_laps);
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));
166 CellCellIter cc_iter(
const CellHandle& _h,
int _max_laps = 1)
const {
167 return CellCellIter(_h,
this, _max_laps);
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));
175 HalfFaceVertexIter hfv_iter(
const HalfFaceHandle& _h,
int _max_laps = 1)
const {
176 return HalfFaceVertexIter(_h,
this, _max_laps);
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));
184 BoundaryHalfFaceHalfFaceIter bhfhf_iter(
const HalfFaceHandle& _ref_h,
int _max_laps = 1)
const {
185 return BoundaryHalfFaceHalfFaceIter(_ref_h,
this, _max_laps);
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));
197 BoundaryFaceIter bf_iter()
const {
198 return BoundaryFaceIter(
this);
201 VertexIter v_iter()
const {
202 return VertexIter(
this);
205 VertexIter vertices_begin()
const {
209 VertexIter vertices_end()
const {
213 std::pair<VertexIter, VertexIter> vertices()
const {
214 return std::make_pair(vertices_begin(), vertices_end());
217 EdgeIter e_iter()
const {
218 return EdgeIter(
this);
221 EdgeIter edges_begin()
const {
225 EdgeIter edges_end()
const {
226 return EdgeIter(
this,
EdgeHandle(edges_.size()));
229 std::pair<EdgeIter, EdgeIter> edges()
const {
230 return std::make_pair(edges_begin(), edges_end());
233 HalfEdgeIter he_iter()
const {
234 return HalfEdgeIter(
this);
237 HalfEdgeIter halfedges_begin()
const {
241 HalfEdgeIter halfedges_end()
const {
245 std::pair<HalfEdgeIter, HalfEdgeIter> halfedges()
const {
246 return std::make_pair(halfedges_begin(), halfedges_end());
249 FaceIter f_iter()
const {
250 return FaceIter(
this);
253 FaceIter faces_begin()
const {
257 FaceIter faces_end()
const {
258 return FaceIter(
this,
FaceHandle(faces_.size()));
261 std::pair<FaceIter, FaceIter> faces()
const {
262 return std::make_pair(faces_begin(), faces_end());
265 HalfFaceIter hf_iter()
const {
266 return HalfFaceIter(
this);
269 HalfFaceIter halffaces_begin()
const {
273 HalfFaceIter halffaces_end()
const {
277 std::pair<HalfFaceIter, HalfFaceIter> halffaces()
const {
278 return std::make_pair(halffaces_begin(), halffaces_end());
281 CellIter c_iter()
const {
282 return CellIter(
this);
285 CellIter cells_begin()
const {
289 CellIter cells_end()
const {
290 return CellIter(
this,
CellHandle(cells_.size()));
293 std::pair<CellIter, CellIter> cells()
const {
294 return std::make_pair(cells_begin(), cells_end());
304 virtual size_t n_edges()
const {
return edges_.size(); }
308 virtual size_t n_faces()
const {
return faces_.size(); }
312 virtual size_t n_cells()
const {
return cells_.size(); }
321 if(g % 2 == 0)
return (g / 2);
341 virtual EdgeHandle
add_edge(
const VertexHandle& _fromVertex,
const VertexHandle& _toHandle,
bool _allowDuplicates =
false);
350 virtual FaceHandle
add_face(
const std::vector<HalfEdgeHandle>& _halfedges,
bool _topologyCheck =
false);
353 virtual FaceHandle
add_face(
const std::vector<VertexHandle>& _vertices);
362 virtual CellHandle
add_cell(
const std::vector<HalfFaceHandle>& _halffaces,
bool _topologyCheck =
false);
365 void set_edge(
const EdgeHandle& _eh,
const VertexHandle& _fromVertex,
const VertexHandle& _toVertex);
368 void set_face(
const FaceHandle& _fh,
const std::vector<HalfEdgeHandle>& _hes);
371 void set_cell(
const CellHandle& _ch,
const std::vector<HalfFaceHandle>& _hfs);
378 const Edge&
edge(
const EdgeHandle& _edgeHandle)
const;
381 const Face&
face(
const FaceHandle& _faceHandle)
const;
384 const Cell&
cell(
const CellHandle& _cellHandle)
const;
387 Edge&
edge(
const EdgeHandle& _edgeHandle);
390 Face&
face(
const FaceHandle& _faceHandle);
393 Cell&
cell(
const CellHandle& _cellHandle);
396 Edge
halfedge(
const HalfEdgeHandle& _halfEdgeHandle)
const;
399 Face
halfface(
const HalfFaceHandle& _halfFaceHandle)
const;
408 HalfEdgeHandle
halfedge(
const VertexHandle& _vh1,
const VertexHandle& _vh2)
const;
413 HalfFaceHandle
halfface(
const std::vector<VertexHandle>& _vs)
const;
423 HalfFaceHandle
halfface(
const std::vector<HalfEdgeHandle>& _hes)
const;
433 assert(has_vertex_bottom_up_incidences());
434 assert(_vh.is_valid() && (
size_t)_vh.idx() < outgoing_hes_per_vertex_.size());
436 return outgoing_hes_per_vertex_[_vh.idx()].size();
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());
450 assert(_fh.is_valid() && (
size_t)_fh.idx() < faces_.size());
452 return face(_fh).halfedges().size();
457 assert(_ch.is_valid() && (
size_t)_ch.idx() < cells_.size());
459 return cell(_ch).halffaces().size();
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()]; }
488 template <
class ContainerT>
489 void get_incident_edges(
const ContainerT& _vs, std::set<EdgeHandle>& _es)
const;
491 template <
class ContainerT>
492 void get_incident_faces(
const ContainerT& _es, std::set<FaceHandle>& _fs)
const;
494 template <
class ContainerT>
495 void get_incident_cells(
const ContainerT& _fs, std::set<CellHandle>& _cs)
const;
497 VertexIter delete_vertex_core(
const VertexHandle& _h);
499 EdgeIter delete_edge_core(
const EdgeHandle& _h);
501 FaceIter delete_face_core(
const FaceHandle& _h);
503 CellIter delete_cell_core(
const CellHandle& _h);
507 virtual void swap_cells(CellHandle _h1, CellHandle _h2);
509 virtual void swap_faces(FaceHandle _h1, FaceHandle _h2);
511 virtual void swap_edges(EdgeHandle _h1, EdgeHandle _h2);
513 virtual void swap_vertices(VertexHandle _h1, VertexHandle _h2);
515 virtual void delete_multiple_vertices(
const std::vector<bool>& _tag);
517 virtual void delete_multiple_edges(
const std::vector<bool>& _tag);
519 virtual void delete_multiple_faces(
const std::vector<bool>& _tag);
521 virtual void delete_multiple_cells(
const std::vector<bool>& _tag);
523 class EdgeCorrector {
525 EdgeCorrector(
const std::vector<int>& _newIndices) :
526 newIndices_(_newIndices) {}
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()]));
533 const std::vector<int>& newIndices_;
536 class FaceCorrector {
538 FaceCorrector(
const std::vector<int>& _newIndices) :
539 newIndices_(_newIndices) {}
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) {
550 _face.set_halfedges(hes);
553 const std::vector<int>& newIndices_;
556 class CellCorrector {
558 CellCorrector(
const std::vector<int>& _newIndices) :
559 newIndices_(_newIndices) {}
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) {
570 _cell.set_halffaces(hfs);
573 const std::vector<int>& newIndices_;
591 virtual void clear(
bool _clearProps =
true) {
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();
608 clear_vertex_props();
610 clear_halfedge_props();
612 clear_halfface_props();
631 void enable_bottom_up_incidences(
bool _enable =
true) {
633 enable_vertex_bottom_up_incidences(_enable);
634 enable_edge_bottom_up_incidences(_enable);
635 enable_face_bottom_up_incidences(_enable);
638 void enable_vertex_bottom_up_incidences(
bool _enable =
true) {
640 if(_enable && !v_bottom_up_) {
643 compute_vertex_bottom_up_incidences();
647 outgoing_hes_per_vertex_.clear();
650 v_bottom_up_ = _enable;
653 void enable_edge_bottom_up_incidences(
bool _enable =
true) {
655 if(_enable && !e_bottom_up_) {
658 compute_edge_bottom_up_incidences();
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);
667 std::for_each(edges_begin(), edges_end(),
668 fun::bind(&TopologyKernel::reorder_incident_halffaces,
this, fun::placeholders::_1));
674 incident_hfs_per_he_.clear();
677 e_bottom_up_ = _enable;
680 void enable_face_bottom_up_incidences(
bool _enable =
true) {
682 bool updateOrder =
false;
683 if(_enable && !f_bottom_up_) {
686 compute_face_bottom_up_incidences();
692 incident_cell_per_hf_.clear();
695 f_bottom_up_ = _enable;
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);
705 std::for_each(edges_begin(), edges_end(),
706 fun::bind(&TopologyKernel::reorder_incident_halffaces,
this, fun::placeholders::_1));
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());
718 bool has_vertex_bottom_up_incidences()
const {
return v_bottom_up_; }
720 bool has_edge_bottom_up_incidences()
const {
return e_bottom_up_; }
722 bool has_face_bottom_up_incidences()
const {
return f_bottom_up_; }
725 void enable_deferred_deletion(
bool _enable =
true);
726 bool deferred_deletion_enabled()
const {
return deferred_deletion; }
729 void enable_fast_deletion(
bool _enable =
true) { fast_deletion = _enable; }
730 bool fast_deletion_enabled()
const {
return fast_deletion; }
735 void compute_vertex_bottom_up_incidences();
737 void compute_edge_bottom_up_incidences();
739 void compute_face_bottom_up_incidences();
741 void reorder_incident_halffaces(
const EdgeHandle& _eh);
744 std::vector<std::vector<HalfEdgeHandle> > outgoing_hes_per_vertex_;
747 std::vector<std::vector<HalfFaceHandle> > incident_hfs_per_he_;
750 std::vector<CellHandle> incident_cell_per_hf_;
759 bool deferred_deletion;
775 HalfFaceHandle
adjacent_halfface_in_cell(
const HalfFaceHandle& _halfFaceHandle,
const HalfEdgeHandle& _halfEdgeHandle)
const;
778 CellHandle
incident_cell(
const HalfFaceHandle& _halfFaceHandle)
const;
780 bool is_boundary(
const HalfFaceHandle& _halfFaceHandle)
const {
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;
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());
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());
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))) {
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);
812 for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(_halfedgeHandle);
813 hehf_it.valid(); ++hehf_it) {
814 if(is_boundary(face_handle(*hehf_it))) {
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());
825 for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
826 if(is_boundary(*voh_it))
return true;
831 size_t n_vertices_in_cell(
const CellHandle& _ch)
const {
832 assert(_ch.is_valid() && (
size_t)_ch.idx() < cells_.size());
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());
844 return vertices.size();
854 return Edge(_edge.to_vertex(), _edge.from_vertex());
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));
864 return Face(opp_halfedges);
874 assert(_h.is_valid());
883 assert(_h.is_valid());
892 assert(_h.is_valid());
899 assert(_h.is_valid());
904 static inline HalfEdgeHandle opposite_halfedge_handle(
const HalfEdgeHandle& _h) {
906 assert(_h.is_valid());
910 if(_h.idx() % 2 == 0) {
911 return HalfEdgeHandle(_h.idx() + 1);
913 return HalfEdgeHandle(_h.idx() - 1);
916 static inline HalfFaceHandle opposite_halfface_handle(
const HalfFaceHandle& _h) {
918 assert(_h.is_valid());
922 if(_h.idx() % 2 == 0) {
923 return HalfFaceHandle(_h.idx() + 1);
925 return HalfFaceHandle(_h.idx() - 1);
931 std::vector<Edge> edges_;
934 std::vector<Face> faces_;
937 std::vector<Cell> cells_;
939 std::vector<bool> vertex_deleted_;
940 std::vector<bool> edge_deleted_;
941 std::vector<bool> face_deleted_;
942 std::vector<bool> cell_deleted_;