43 #ifndef TOPOLOGYKERNEL_HH_
44 #define TOPOLOGYKERNEL_HH_
50 #include "BaseEntities.hh"
51 #include "OpenVolumeMeshHandle.hh"
52 #include "ResourceManager.hh"
53 #include "Iterators.hh"
110 template <
class Circulator>
111 static Circulator make_end_circulator(
const Circulator& _circ)
113 Circulator end = _circ;
115 end.lap(_circ.max_laps());
127 std::pair<VertexOHalfEdgeIter, VertexOHalfEdgeIter> outgoing_halfedges(
const VertexHandle& _h,
int _max_laps = 1)
const {
129 return std::make_pair(begin, make_end_circulator(begin));
136 std::pair<VertexVertexIter, VertexVertexIter> vertex_vertices(
const VertexHandle& _h,
int _max_laps = 1)
const {
138 return std::make_pair(begin, make_end_circulator(begin));
145 std::pair<HalfEdgeHalfFaceIter, HalfEdgeHalfFaceIter> halfedge_halffaces(
const HalfEdgeHandle& _h,
int _max_laps = 1)
const {
147 return std::make_pair(begin, make_end_circulator(begin));
154 std::pair<VertexFaceIter, VertexFaceIter> vertex_faces(
const VertexHandle& _h,
int _max_laps = 1)
const {
156 return std::make_pair(begin, make_end_circulator(begin));
163 std::pair<VertexCellIter, VertexCellIter> vertex_cells(
const VertexHandle& _h,
int _max_laps = 1)
const {
165 return std::make_pair(begin, make_end_circulator(begin));
172 std::pair<HalfEdgeCellIter, HalfEdgeCellIter> halfedge_cells(
const HalfEdgeHandle& _h,
int _max_laps = 1)
const {
174 return std::make_pair(begin, make_end_circulator(begin));
181 std::pair<CellVertexIter, CellVertexIter> cell_vertices(
const CellHandle& _h,
int _max_laps = 1)
const {
183 return std::make_pair(begin, make_end_circulator(begin));
190 std::pair<CellCellIter, CellCellIter> cell_cells(
const CellHandle& _h,
int _max_laps = 1)
const {
192 return std::make_pair(begin, make_end_circulator(begin));
199 std::pair<HalfFaceVertexIter, HalfFaceVertexIter> halfface_vertices(
const HalfFaceHandle& _h,
int _max_laps = 1)
const {
201 return std::make_pair(begin, make_end_circulator(begin));
208 std::pair<BoundaryHalfFaceHalfFaceIter, BoundaryHalfFaceHalfFaceIter> boundary_halfface_halffaces(
const HalfFaceHandle& _h,
int _max_laps = 1)
const {
210 return std::make_pair(begin, make_end_circulator(begin));
233 std::pair<VertexIter, VertexIter> vertices()
const {
234 return std::make_pair(vertices_begin(), vertices_end());
249 std::pair<EdgeIter, EdgeIter> edges()
const {
250 return std::make_pair(edges_begin(), edges_end());
265 std::pair<HalfEdgeIter, HalfEdgeIter> halfedges()
const {
266 return std::make_pair(halfedges_begin(), halfedges_end());
281 std::pair<FaceIter, FaceIter> faces()
const {
282 return std::make_pair(faces_begin(), faces_end());
297 std::pair<HalfFaceIter, HalfFaceIter> halffaces()
const {
298 return std::make_pair(halffaces_begin(), halffaces_end());
313 std::pair<CellIter, CellIter> cells()
const {
314 return std::make_pair(cells_begin(), cells_end());
324 virtual size_t n_edges()
const {
return edges_.size(); }
328 virtual size_t n_faces()
const {
return faces_.size(); }
332 virtual size_t n_cells()
const {
return cells_.size(); }
341 if(g % 2 == 0)
return (g / 2);
361 virtual EdgeHandle
add_edge(
const VertexHandle& _fromVertex,
const VertexHandle& _toHandle,
bool _allowDuplicates =
false);
370 virtual FaceHandle
add_face(
const std::vector<HalfEdgeHandle>& _halfedges,
bool _topologyCheck =
false);
373 virtual FaceHandle
add_face(
const std::vector<VertexHandle>& _vertices);
382 virtual CellHandle
add_cell(
const std::vector<HalfFaceHandle>& _halffaces,
bool _topologyCheck =
false);
385 void set_edge(
const EdgeHandle& _eh,
const VertexHandle& _fromVertex,
const VertexHandle& _toVertex);
388 void set_face(
const FaceHandle& _fh,
const std::vector<HalfEdgeHandle>& _hes);
391 void set_cell(
const CellHandle& _ch,
const std::vector<HalfFaceHandle>& _hfs);
398 const Edge&
edge(
const EdgeHandle& _edgeHandle)
const;
401 const Face&
face(
const FaceHandle& _faceHandle)
const;
404 const Cell&
cell(
const CellHandle& _cellHandle)
const;
407 Edge&
edge(
const EdgeHandle& _edgeHandle);
410 Face&
face(
const FaceHandle& _faceHandle);
413 Cell&
cell(
const CellHandle& _cellHandle);
416 Edge
halfedge(
const HalfEdgeHandle& _halfEdgeHandle)
const;
419 Face
halfface(
const HalfFaceHandle& _halfFaceHandle)
const;
428 HalfEdgeHandle
halfedge(
const VertexHandle& _vh1,
const VertexHandle& _vh2)
const;
433 HalfFaceHandle
halfface(
const std::vector<VertexHandle>& _vs)
const;
443 HalfFaceHandle
halfface(
const std::vector<HalfEdgeHandle>& _hes)
const;
453 assert(has_vertex_bottom_up_incidences());
454 assert(_vh.is_valid() && (size_t)_vh.idx() < outgoing_hes_per_vertex_.size());
456 return outgoing_hes_per_vertex_[_vh.idx()].size();
461 assert(has_edge_bottom_up_incidences());
462 assert(_eh.is_valid() && (size_t)_eh.idx() < edges_.size());
463 assert((
size_t)
halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
470 assert(_fh.is_valid() && (size_t)_fh.idx() < faces_.size());
472 return face(_fh).halfedges().size();
477 assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
479 return cell(_ch).halffaces().size();
499 virtual bool is_deleted(
const VertexHandle& _h)
const {
return vertex_deleted_[_h.idx()]; }
500 virtual bool is_deleted(
const EdgeHandle& _h)
const {
return edge_deleted_[_h.idx()]; }
501 virtual bool is_deleted(
const HalfEdgeHandle& _h)
const {
return edge_deleted_[_h.idx()/2]; }
502 virtual bool is_deleted(
const FaceHandle& _h)
const {
return face_deleted_[_h.idx()]; }
503 virtual bool is_deleted(
const HalfFaceHandle& _h)
const {
return face_deleted_[_h.idx()/2]; }
504 virtual bool is_deleted(
const CellHandle& _h)
const {
return cell_deleted_[_h.idx()]; }
508 template <
class ContainerT>
509 void get_incident_edges(
const ContainerT& _vs, std::set<EdgeHandle>& _es)
const;
511 template <
class ContainerT>
512 void get_incident_faces(
const ContainerT& _es, std::set<FaceHandle>& _fs)
const;
514 template <
class ContainerT>
515 void get_incident_cells(
const ContainerT& _fs, std::set<CellHandle>& _cs)
const;
527 virtual void swap_cells(CellHandle _h1, CellHandle _h2);
529 virtual void swap_faces(FaceHandle _h1, FaceHandle _h2);
531 virtual void swap_edges(EdgeHandle _h1, EdgeHandle _h2);
533 virtual void swap_vertices(VertexHandle _h1, VertexHandle _h2);
535 virtual void delete_multiple_vertices(
const std::vector<bool>& _tag);
537 virtual void delete_multiple_edges(
const std::vector<bool>& _tag);
539 virtual void delete_multiple_faces(
const std::vector<bool>& _tag);
541 virtual void delete_multiple_cells(
const std::vector<bool>& _tag);
546 newIndices_(_newIndices) {}
548 void operator()(Edge& _edge) {
549 _edge.set_from_vertex(
VertexHandle(newIndices_[_edge.from_vertex().idx()]));
550 _edge.set_to_vertex(
VertexHandle(newIndices_[_edge.to_vertex().idx()]));
553 const std::vector<int>& newIndices_;
559 newIndices_(_newIndices) {}
561 void operator()(Face& _face) {
562 std::vector<HalfEdgeHandle> hes = _face.halfedges();
563 for(std::vector<HalfEdgeHandle>::iterator he_it = hes.begin(),
564 he_end = hes.end(); he_it != he_end; ++he_it) {
570 _face.set_halfedges(hes);
573 const std::vector<int>& newIndices_;
579 newIndices_(_newIndices) {}
581 void operator()(Cell& _cell) {
582 std::vector<HalfFaceHandle> hfs = _cell.halffaces();
583 for(std::vector<HalfFaceHandle>::iterator hf_it = hfs.begin(),
584 hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {
590 _cell.set_halffaces(hfs);
593 const std::vector<int>& newIndices_;
611 virtual void clear(
bool _clearProps =
true) {
616 vertex_deleted_.clear();
617 edge_deleted_.clear();
618 face_deleted_.clear();
619 cell_deleted_.clear();
620 outgoing_hes_per_vertex_.clear();
621 incident_hfs_per_he_.clear();
622 incident_cell_per_hf_.clear();
628 clear_vertex_props();
630 clear_halfedge_props();
632 clear_halfface_props();
651 void enable_bottom_up_incidences(
bool _enable =
true) {
653 enable_vertex_bottom_up_incidences(_enable);
654 enable_edge_bottom_up_incidences(_enable);
655 enable_face_bottom_up_incidences(_enable);
658 void enable_vertex_bottom_up_incidences(
bool _enable =
true) {
660 if(_enable && !v_bottom_up_) {
663 compute_vertex_bottom_up_incidences();
667 outgoing_hes_per_vertex_.clear();
670 v_bottom_up_ = _enable;
673 void enable_edge_bottom_up_incidences(
bool _enable =
true) {
675 if(_enable && !e_bottom_up_) {
678 compute_edge_bottom_up_incidences();
681 #if defined(__clang_major__) && (__clang_major__ >= 5)
682 for(EdgeIter e_it = edges_begin(), e_end = edges_end();
683 e_it != e_end; ++e_it) {
684 reorder_incident_halffaces(*e_it);
687 std::for_each(edges_begin(), edges_end(),
688 fun::bind(&TopologyKernel::reorder_incident_halffaces,
this, fun::placeholders::_1));
694 incident_hfs_per_he_.clear();
697 e_bottom_up_ = _enable;
700 void enable_face_bottom_up_incidences(
bool _enable =
true) {
702 bool updateOrder =
false;
703 if(_enable && !f_bottom_up_) {
706 compute_face_bottom_up_incidences();
712 incident_cell_per_hf_.clear();
715 f_bottom_up_ = _enable;
719 #if defined(__clang_major__) && (__clang_major__ >= 5)
720 for(EdgeIter e_it = edges_begin(), e_end = edges_end();
721 e_it != e_end; ++e_it) {
722 reorder_incident_halffaces(*e_it);
725 std::for_each(edges_begin(), edges_end(),
726 fun::bind(&TopologyKernel::reorder_incident_halffaces,
this, fun::placeholders::_1));
732 bool has_full_bottom_up_incidences()
const {
733 return (has_vertex_bottom_up_incidences() &&
734 has_edge_bottom_up_incidences() &&
735 has_face_bottom_up_incidences());
738 bool has_vertex_bottom_up_incidences()
const {
return v_bottom_up_; }
740 bool has_edge_bottom_up_incidences()
const {
return e_bottom_up_; }
742 bool has_face_bottom_up_incidences()
const {
return f_bottom_up_; }
745 void enable_deferred_deletion(
bool _enable =
true);
746 bool deferred_deletion_enabled()
const {
return deferred_deletion; }
749 void enable_fast_deletion(
bool _enable =
true) { fast_deletion = _enable; }
750 bool fast_deletion_enabled()
const {
return fast_deletion; }
755 void compute_vertex_bottom_up_incidences();
757 void compute_edge_bottom_up_incidences();
759 void compute_face_bottom_up_incidences();
761 void reorder_incident_halffaces(
const EdgeHandle& _eh);
764 std::vector<std::vector<HalfEdgeHandle> > outgoing_hes_per_vertex_;
767 std::vector<std::vector<HalfFaceHandle> > incident_hfs_per_he_;
770 std::vector<CellHandle> incident_cell_per_hf_;
779 bool deferred_deletion;
795 HalfFaceHandle
adjacent_halfface_in_cell(
const HalfFaceHandle& _halfFaceHandle,
const HalfEdgeHandle& _halfEdgeHandle)
const;
798 CellHandle
incident_cell(
const HalfFaceHandle& _halfFaceHandle)
const;
800 bool is_boundary(
const HalfFaceHandle& _halfFaceHandle)
const {
802 assert(_halfFaceHandle.is_valid() && (size_t)_halfFaceHandle.idx() < faces_.size() * 2u);
803 assert(has_face_bottom_up_incidences());
804 assert((
size_t)_halfFaceHandle.idx() < incident_cell_per_hf_.size());
805 return incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle;
808 bool is_boundary(
const FaceHandle& _faceHandle)
const {
809 assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
810 assert(has_face_bottom_up_incidences());
815 bool is_boundary(
const EdgeHandle& _edgeHandle)
const {
816 assert(has_edge_bottom_up_incidences());
817 assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());
819 for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(
halfedge_handle(_edgeHandle, 0));
820 hehf_it.valid(); ++hehf_it) {
821 if(is_boundary(face_handle(*hehf_it))) {
828 bool is_boundary(
const HalfEdgeHandle& _halfedgeHandle)
const {
829 assert(has_edge_bottom_up_incidences());
830 assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);
832 for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(_halfedgeHandle);
833 hehf_it.valid(); ++hehf_it) {
834 if(is_boundary(face_handle(*hehf_it))) {
841 bool is_boundary(
const VertexHandle& _vertexHandle)
const {
842 assert(has_vertex_bottom_up_incidences());
843 assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() <
n_vertices());
845 for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
846 if(is_boundary(*voh_it))
return true;
851 size_t n_vertices_in_cell(
const CellHandle& _ch)
const {
852 assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
854 std::set<VertexHandle> vertices;
855 std::vector<HalfFaceHandle> hfs =
cell(_ch).halffaces();
856 for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin();
857 hf_it != hfs.end(); ++hf_it) {
858 std::vector<HalfEdgeHandle> hes =
halfface(*hf_it).halfedges();
859 for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin();
860 he_it != hes.end(); ++he_it) {
861 vertices.insert(
halfedge(*he_it).to_vertex());
864 return vertices.size();
874 return Edge(_edge.to_vertex(), _edge.from_vertex());
878 std::vector<HalfEdgeHandle> opp_halfedges;
879 for(std::vector<HalfEdgeHandle>::const_iterator it = _face.halfedges().begin(); it
880 != _face.halfedges().end(); ++it) {
881 opp_halfedges.insert(opp_halfedges.begin(), opposite_halfedge_handle(*it));
884 return Face(opp_halfedges);
894 assert(_h.is_valid());
903 assert(_h.is_valid());
912 assert(_h.is_valid());
919 assert(_h.is_valid());
924 static inline HalfEdgeHandle opposite_halfedge_handle(
const HalfEdgeHandle& _h) {
926 assert(_h.is_valid());
930 if(_h.idx() % 2 == 0) {
931 return HalfEdgeHandle(_h.idx() + 1);
933 return HalfEdgeHandle(_h.idx() - 1);
936 static inline HalfFaceHandle opposite_halfface_handle(
const HalfFaceHandle& _h) {
938 assert(_h.is_valid());
942 if(_h.idx() % 2 == 0) {
943 return HalfFaceHandle(_h.idx() + 1);
945 return HalfFaceHandle(_h.idx() - 1);
948 bool inline needs_garbage_collection()
const {
949 return needs_garbage_collection_;
955 std::vector<Edge> edges_;
958 std::vector<Face> faces_;
961 std::vector<Cell> cells_;
963 std::vector<bool> vertex_deleted_;
964 std::vector<bool> edge_deleted_;
965 std::vector<bool> face_deleted_;
966 std::vector<bool> cell_deleted_;
967 bool needs_garbage_collection_;
virtual size_t n_halffaces() const
Get number of halffaces in mesh.
virtual void collect_garbage()
Delete all entities that are marked as deleted.
virtual size_t n_cells() const
Get number of cells in mesh.
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
virtual EdgeIter delete_edge(const EdgeHandle &_h)
Delete edge from mesh.
size_t valence(const EdgeHandle &_eh) const
Get valence of edge (number of incident faces)
Edge opposite_halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle.
size_t valence(const CellHandle &_ch) const
Get valence of cell (number of incident faces)
void set_cell(const CellHandle &_ch, const std::vector< HalfFaceHandle > &_hfs)
Set the half-faces of a 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.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
void resize_cprops(size_t _nc)
Change size of stored cell properties.
FaceIter delete_face_core(const FaceHandle &_h)
Delete face from mesh.
size_t valence(const FaceHandle &_fh) const
Get valence of face (number of incident edges)
const Edge & edge(const EdgeHandle &_edgeHandle) const
Get edge with handle _edgeHandle.
size_t valence(const VertexHandle &_vh) const
Get valence of vertex (number of incident edges)
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
virtual size_t n_edges() const
Get number of edges in mesh.
virtual size_t n_vertices() const
Get number of vertices in mesh.
HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get previous halfedge within a halfface.
void resize_fprops(size_t _nf)
Change size of stored face properties.
HalfFaceHandle halfface_extensive(const std::vector< VertexHandle > &_vs) const
void resize_vprops(size_t _nv)
Change size of stored vertex properties.
virtual VertexHandle add_vertex()
Add abstract vertex.
void resize_eprops(size_t _ne)
Change size of stored edge properties.
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
void set_face(const FaceHandle &_fh, const std::vector< HalfEdgeHandle > &_hes)
Set the half-edges of a face.
virtual size_t n_halfedges() const
Get number of halfedges in mesh.
const Face & face(const FaceHandle &_faceHandle) const
Get face with handle _faceHandle.
Face opposite_halfface(const HalfFaceHandle &_halfFaceHandle) const
Get opposite halfface that corresponds to halfface with handle _halfFaceHandle.
virtual void clear(bool _clearProps=true)
Clear whole mesh.
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.
virtual CellIter delete_cell(const CellHandle &_h)
Delete cell from mesh.
CellIter delete_cell_range(const CellIter &_first, const CellIter &_last)
Delete range of cells.
EdgeIter delete_edge_core(const EdgeHandle &_h)
Delete edge from mesh.
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.
bool bind(osg::GeometryPtr &_geo, Mesh &_mesh)
virtual size_t n_faces() const
Get number of faces in mesh.
virtual EdgeHandle add_edge(const VertexHandle &_fromVertex, const VertexHandle &_toHandle, bool _allowDuplicates=false)
Add edge.
VertexIter delete_vertex_core(const VertexHandle &_h)
Delete vertex from mesh.
virtual FaceIter delete_face(const FaceHandle &_h)
Delete face from mesh.
virtual VertexIter delete_vertex(const VertexHandle &_h)
Delete vertex from mesh.
const Cell & cell(const CellHandle &_cellHandle) const
Get cell with handle _cellHandle.
Edge halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get edge that corresponds to halfedge with handle _halfEdgeHandle.
CellIter delete_cell_core(const CellHandle &_h)
Delete cell from mesh.
void set_edge(const EdgeHandle &_eh, const VertexHandle &_fromVertex, const VertexHandle &_toVertex)
Set the vertices of an edge.