43 #ifndef TOPOLOGYKERNEL_HH_
44 #define TOPOLOGYKERNEL_HH_
50 #include "BaseEntities.hh"
51 #include "OpenVolumeMeshHandle.hh"
52 #include "ResourceManager.hh"
53 #include "Iterators.hh"
108 template <
class Circulator>
109 static Circulator make_end_circulator(
const Circulator& _circ)
111 Circulator end = _circ;
113 end.lap(_circ.max_laps());
125 std::pair<VertexOHalfEdgeIter, VertexOHalfEdgeIter> outgoing_halfedges(
const VertexHandle& _h,
int _max_laps = 1)
const {
127 return std::make_pair(begin, make_end_circulator(begin));
134 std::pair<HalfEdgeHalfFaceIter, HalfEdgeHalfFaceIter> halfedge_halffaces(
const HalfEdgeHandle& _h,
int _max_laps = 1)
const {
136 return std::make_pair(begin, make_end_circulator(begin));
143 std::pair<VertexCellIter, VertexCellIter> vertex_cells(
const VertexHandle& _h,
int _max_laps = 1){
145 return std::make_pair(begin, make_end_circulator(begin));
152 std::pair<HalfEdgeCellIter, HalfEdgeCellIter> halfedge_cells(
const HalfEdgeHandle& _h,
int _max_laps = 1){
154 return std::make_pair(begin, make_end_circulator(begin));
161 std::pair<CellVertexIter, CellVertexIter> cell_vertices(
const CellHandle& _h,
int _max_laps = 1)
const {
163 return std::make_pair(begin, make_end_circulator(begin));
170 std::pair<CellCellIter, CellCellIter> cell_cells(
const CellHandle& _h,
int _max_laps = 1)
const {
172 return std::make_pair(begin, make_end_circulator(begin));
179 std::pair<HalfFaceVertexIter, HalfFaceVertexIter> halfface_vertices(
const HalfFaceHandle& _h,
int _max_laps = 1)
const {
181 return std::make_pair(begin, make_end_circulator(begin));
188 std::pair<BoundaryHalfFaceHalfFaceIter, BoundaryHalfFaceHalfFaceIter> boundary_halfface_halffaces(
const HalfFaceHandle& _h,
int _max_laps = 1)
const {
190 return std::make_pair(begin, make_end_circulator(begin));
213 std::pair<VertexIter, VertexIter> vertices()
const {
214 return std::make_pair(vertices_begin(), vertices_end());
229 std::pair<EdgeIter, EdgeIter> edges()
const {
230 return std::make_pair(edges_begin(), edges_end());
245 std::pair<HalfEdgeIter, HalfEdgeIter> halfedges()
const {
246 return std::make_pair(halfedges_begin(), halfedges_end());
261 std::pair<FaceIter, FaceIter> faces()
const {
262 return std::make_pair(faces_begin(), faces_end());
277 std::pair<HalfFaceIter, HalfFaceIter> halffaces()
const {
278 return std::make_pair(halffaces_begin(), halffaces_end());
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;
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);
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_;
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_;
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_;
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)
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.