50 #include <OpenMesh/Core/Mesh/PolyConnectivity.hh>
62 PolyConnectivity::HalfedgeHandle
68 if (to_vertex_handle(*voh_it) == _end_vh)
100 for (++vh_it; vh_it.is_valid(); ++vh_it)
113 set_halfedge_handle(_vh, *vh_it);
121 PolyConnectivity::FaceHandle
125 size_t i, ii, n(_vhs_size);
127 outer_next, outer_prev,
128 boundary_next, boundary_prev,
129 patch_start, patch_end;
133 if (edgeData_.size() < n)
136 next_cache_.resize(6*n);
139 size_t next_cache_count = 0;
145 for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
149 omerr() <<
"PolyMeshT::add_face: complex vertex\n";
154 edgeData_[i].halfedge_handle =
find_halfedge(_vertex_handles[i],
155 _vertex_handles[ii]);
156 edgeData_[i].is_new = !edgeData_[i].halfedge_handle.is_valid();
157 edgeData_[i].needs_adjust =
false;
159 if (!edgeData_[i].is_new && !
is_boundary(edgeData_[i].halfedge_handle))
161 omerr() <<
"PolyMeshT::add_face: complex edge\n";
167 for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
169 if (!edgeData_[i].is_new && !edgeData_[ii].is_new)
171 inner_prev = edgeData_[i].halfedge_handle;
172 inner_next = edgeData_[ii].halfedge_handle;
175 if (next_halfedge_handle(inner_prev) != inner_next)
181 outer_prev = opposite_halfedge_handle(inner_next);
182 outer_next = opposite_halfedge_handle(inner_prev);
183 boundary_prev = outer_prev;
186 opposite_halfedge_handle(next_halfedge_handle(boundary_prev));
188 boundary_next = next_halfedge_handle(boundary_prev);
191 if (boundary_prev == inner_prev)
193 omerr() <<
"PolyMeshT::add_face: patch re-linking failed\n";
201 patch_start = next_halfedge_handle(inner_prev);
202 patch_end = prev_halfedge_handle(inner_next);
212 next_cache_[next_cache_count++] = std::make_pair(boundary_prev, patch_start);
213 next_cache_[next_cache_count++] = std::make_pair(patch_end, boundary_next);
214 next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
220 for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
221 if (edgeData_[i].is_new)
222 edgeData_[i].halfedge_handle = new_edge(_vertex_handles[i], _vertex_handles[ii]);
226 set_halfedge_handle(fh, edgeData_[n-1].halfedge_handle);
229 for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
231 vh = _vertex_handles[ii];
233 inner_prev = edgeData_[i].halfedge_handle;
234 inner_next = edgeData_[ii].halfedge_handle;
239 if (edgeData_[i].is_new)
id |= 1;
240 if (edgeData_[ii].is_new)
id |= 2;
245 outer_prev = opposite_halfedge_handle(inner_next);
246 outer_next = opposite_halfedge_handle(inner_prev);
254 boundary_prev = prev_halfedge_handle(inner_next);
256 next_cache_[next_cache_count++] = std::make_pair(boundary_prev, outer_next);
257 set_halfedge_handle(vh, outer_next);
261 boundary_next = next_halfedge_handle(inner_prev);
263 next_cache_[next_cache_count++] = std::make_pair(outer_prev, boundary_next);
264 set_halfedge_handle(vh, boundary_next);
268 if (!halfedge_handle(vh).is_valid())
270 set_halfedge_handle(vh, outer_next);
271 next_cache_[next_cache_count++] = std::make_pair(outer_prev, outer_next);
275 boundary_next = halfedge_handle(vh);
276 boundary_prev = prev_halfedge_handle(boundary_next);
279 next_cache_[next_cache_count++] = std::make_pair(boundary_prev, outer_next);
280 next_cache_[next_cache_count++] = std::make_pair(outer_prev, boundary_next);
286 next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
288 else edgeData_[ii].needs_adjust = (halfedge_handle(vh) == inner_next);
292 set_face_handle(edgeData_[i].halfedge_handle, fh);
296 for (i = 0; i < next_cache_count; ++i)
297 set_next_halfedge_handle(next_cache_[i].first, next_cache_[i].second);
302 if (edgeData_[i].needs_adjust)
327 {
return add_face(&_vhandles.front(), _vhandles.size()); }
334 if (
status(edge_handle(v0v1)).deleted())
343 bool v0v1_triangle =
false;
344 bool v1v0_triangle =
false;
347 v0v1_triangle =
valence(face_handle(v0v1)) == 3;
350 v1v0_triangle =
valence(face_handle(v1v0)) == 3;
354 VertexHandle v_01_n = to_vertex_handle(next_halfedge_handle(v0v1));
357 VertexHandle v_10_n = to_vertex_handle(next_halfedge_handle(v1v0));
401 for (vv_it =
vv_iter(v0); vv_it.is_valid(); ++vv_it)
406 for (vv_it =
vv_iter(v1); vv_it.is_valid(); ++vv_it)
411 for (vv_it =
vv_iter(v0); vv_it.is_valid(); ++vv_it)
414 !(*vv_it == v_01_n && v0v1_triangle) &&
415 !(*vv_it == v_10_n && v1v0_triangle)
426 one = next_halfedge_handle(v0v1);
427 two = next_halfedge_handle(one);
429 one = opposite_halfedge_handle(one);
430 two = opposite_halfedge_handle(two);
432 if (face_handle(one) == face_handle(two) &&
valence(face_handle(one)) != 3)
441 one = next_halfedge_handle(v1v0);
442 two = next_halfedge_handle(one);
444 one = opposite_halfedge_handle(one);
445 two = opposite_halfedge_handle(two);
447 if (face_handle(one) == face_handle(two) &&
valence(face_handle(one)) != 3)
453 if (
status(*vv_it).
tagged() && v_01_n == v_10_n && v0v1_triangle && v1v0_triangle)
467 std::vector<FaceHandle> face_handles;
468 face_handles.reserve(8);
470 face_handles.push_back(*vf_it);
474 std::vector<FaceHandle>::iterator fh_it(face_handles.begin()),
475 fh_end(face_handles.end());
477 for (; fh_it!=
fh_end; ++fh_it)
487 FaceHandle fh0(face_handle(halfedge_handle(_eh, 0)));
488 FaceHandle fh1(face_handle(halfedge_handle(_eh, 1)));
497 if ( has_edge_status() )
503 if ( has_halfedge_status() ) {
522 std::vector<EdgeHandle> deleted_edges;
523 deleted_edges.reserve(3);
528 std::vector<VertexHandle> vhandles;
544 deleted_edges.push_back(edge_handle(hh));
546 vhandles.push_back(to_vertex_handle(hh));
553 if (!deleted_edges.empty())
555 std::vector<EdgeHandle>::iterator del_it(deleted_edges.begin()),
556 del_end(deleted_edges.end());
560 for (; del_it!=del_end; ++del_it)
562 h0 = halfedge_handle(*del_it, 0);
563 v0 = to_vertex_handle(h0);
564 next0 = next_halfedge_handle(h0);
565 prev0 = prev_halfedge_handle(h0);
567 h1 = halfedge_handle(*del_it, 1);
568 v1 = to_vertex_handle(h1);
569 next1 = next_halfedge_handle(h1);
570 prev1 = prev_halfedge_handle(h1);
573 set_next_halfedge_handle(prev0, next1);
574 set_next_halfedge_handle(prev1, next0);
577 if ( has_edge_status() )
584 if ( has_halfedge_status() ) {
590 if (halfedge_handle(v0) == h1)
595 if (_delete_isolated_vertices)
599 else set_halfedge_handle(v0, next0);
603 if (halfedge_handle(v1) == h0)
608 if (_delete_isolated_vertices)
612 else set_halfedge_handle(v1, next1);
618 std::vector<VertexHandle>::iterator v_it(vhandles.begin()),
619 v_end(vhandles.end());
620 for (; v_it!=v_end; ++v_it)
732 if (next_halfedge_handle(next_halfedge_handle(h1)) == h1)
734 if (next_halfedge_handle(next_halfedge_handle(o1)) == o1)
759 set_vertex_handle(*vih_it, vh);
763 set_next_halfedge_handle(hp, hn);
764 set_next_halfedge_handle(op, on);
768 if (fh.
is_valid()) set_halfedge_handle(fh, hn);
769 if (fo.
is_valid()) set_halfedge_handle(fo, on);
773 if (halfedge_handle(vh) == o) set_halfedge_handle(vh, hn);
800 assert ((next_halfedge_handle(h1) == h0) && (h1 != o0));
804 set_next_halfedge_handle(h1, next_halfedge_handle(o0));
805 set_next_halfedge_handle(prev_halfedge_handle(o0), h1);
809 set_face_handle(h1, fo);
818 if (fo.
is_valid() && halfedge_handle(fo) == o0)
820 set_halfedge_handle(fo, h1);
842 while (next_heh != heh0)
848 next_heh = next_halfedge_handle(next_heh);
856 std::set<FaceHandle> nb_fhs;
859 if (nb_fhs.find(*cff_it) == nb_fhs.end())
861 nb_fhs.insert(*cff_it);
872 PolyConnectivity::FaceHandle
882 FaceHandle rem_fh = face_handle(heh0), del_fh = face_handle(heh1);
883 if (!del_fh.is_valid())
885 std::swap(del_fh, rem_fh);
887 assert(del_fh.is_valid());
899 set_next_halfedge_handle(prev_heh0, next_heh1);
900 set_next_halfedge_handle(prev_heh1, next_heh0);
905 if (halfedge_handle(vh0) == heh1)
907 set_halfedge_handle(vh0, next_heh0);
909 if (halfedge_handle(vh1) == heh0)
911 set_halfedge_handle(vh1, next_heh1);
915 if (halfedge_handle(rem_fh) == heh0)
917 set_halfedge_handle(rem_fh, prev_heh1);
919 else if (halfedge_handle(rem_fh) == heh1)
921 set_halfedge_handle(rem_fh, prev_heh0);
925 set_face_handle(*fh_it, rem_fh);
937 assert_compile(
sizeof(Halfedge) ==
sizeof(Halfedge_with_prev));
939 assert(
status(_eh).deleted());
944 FaceHandle rem_fh = face_handle(heh0), del_fh = face_handle(heh1);
945 if (!del_fh.is_valid())
947 std::swap(del_fh, rem_fh);
949 assert(
status(del_fh).deleted());
959 set_next_halfedge_handle(prev_heh0, heh0);
960 set_prev_halfedge_handle(next_heh0, heh0);
962 set_next_halfedge_handle(prev_heh1, heh1);
963 set_prev_halfedge_handle(next_heh1, heh1);
967 set_face_handle(*fh_it, del_fh);
970 if (face_handle(halfedge_handle(rem_fh)) == del_fh)
972 if (halfedge_handle(rem_fh) == prev_heh0)
974 set_halfedge_handle(rem_fh, heh1);
978 assert(halfedge_handle(rem_fh) == prev_heh1);
979 set_halfedge_handle(rem_fh, heh0);
988 assert(face_handle(_prev_heh) == face_handle(_next_heh));
989 assert(next_halfedge_handle(_prev_heh) != _next_heh);
997 set_next_halfedge_handle(_prev_heh, heh0);
998 set_next_halfedge_handle(heh0, _next_heh);
999 set_next_halfedge_handle(prev_next_heh, heh1);
1000 set_next_halfedge_handle(heh1, next_prev_heh);
1004 set_halfedge_handle(new_fh, heh0);
1007 set_face_handle(*fh_it, new_fh);
1009 FaceHandle old_fh = face_handle(next_prev_heh);
1010 set_face_handle(heh1, old_fh);
1011 if (old_fh.
is_valid() && face_handle(halfedge_handle(old_fh)) == new_fh)
1013 set_halfedge_handle(old_fh, heh1);
1038 while (to_vertex_handle(next_halfedge_handle(next_heh)) != start_vh)
1043 set_halfedge_handle(new_fh, base_heh);
1045 HalfedgeHandle new_heh = new_edge(to_vertex_handle(next_heh), start_vh);
1047 set_next_halfedge_handle(base_heh, next_heh);
1048 set_next_halfedge_handle(next_heh, new_heh);
1049 set_next_halfedge_handle(new_heh, base_heh);
1051 set_face_handle(base_heh, new_fh);
1052 set_face_handle(next_heh, new_fh);
1053 set_face_handle(new_heh, new_fh);
1059 base_heh = opposite_halfedge_handle(new_heh);
1060 next_heh = next_next_heh;
1062 set_halfedge_handle(_fh, base_heh);
1064 set_next_halfedge_handle(base_heh, next_heh);
1065 set_next_halfedge_handle(next_halfedge_handle(next_heh), base_heh);
1067 set_face_handle(base_heh, _fh);
1078 for (; f_it!=f_end; ++f_it)
1090 set_next_halfedge_handle(hend, hold);
1091 set_face_handle(hold, fh);
1093 hold = opposite_halfedge_handle(hold);
1095 while (hh != hend) {
1100 set_halfedge_handle(fnew, hh);
1104 set_next_halfedge_handle(hnew, hold);
1105 set_next_halfedge_handle(hold, hh);
1106 set_next_halfedge_handle(hh, hnew);
1108 set_face_handle(hnew, fnew);
1109 set_face_handle(hold, fnew);
1110 set_face_handle(hh, fnew);
1112 hold = opposite_halfedge_handle(hnew);
1117 set_next_halfedge_handle(hold, hend);
1118 set_next_halfedge_handle(next_halfedge_handle(hend), hold);
1120 set_face_handle(hold, fh);
1122 set_halfedge_handle(vh, hold);
1175 set_vertex_handle(h1, _vh);
1178 set_next_halfedge_handle(new_e, h0);
1179 set_next_halfedge_handle(h1, opposite_halfedge_handle(new_e));
1181 set_next_halfedge_handle(ph0, new_e);
1182 set_next_halfedge_handle(opposite_halfedge_handle(new_e), nh1);
1192 set_face_handle(new_e, face_handle(h0));
1196 set_boundary(new_e);
1201 set_face_handle(opposite_halfedge_handle(new_e), face_handle(h1));
1205 set_boundary(opposite_halfedge_handle(new_e));
1208 set_halfedge_handle( _vh, h0 );
1211 if (halfedge_handle(vfrom) == h0)
1213 set_halfedge_handle(vfrom, new_e);
1226 EdgeHandle eh0 = edge_handle( next_halfedge_handle( halfedge_handle(_eh, 1) ) );
ConstVertexVertexIter cvv_iter(VertexHandle _vh) const
const vertex circulator
void collapse(HalfedgeHandle _heh)
void delete_vertex(VertexHandle _vh, bool _delete_isolated_vertices=true)
bool is_collapse_ok(HalfedgeHandle _he)
void split_edge_copy(EdgeHandle _eh, VertexHandle _vh)
HalfedgeIter halfedges_end()
End iterator for halfedges.
void split(FaceHandle _fh, VertexHandle _vh)
Face split (= 1-to-n split).
ConstFaceFaceIter cff_iter(FaceHandle _fh) const
const face - face circulator
Iterators::GenericIteratorT< This, This::VertexHandle, ArrayKernel,&ArrayKernel::has_vertex_status,&ArrayKernel::n_vertices > VertexIter
Linear iterator.
Iterators::GenericIteratorT< This, This::EdgeHandle, ArrayKernel,&ArrayKernel::has_edge_status,&ArrayKernel::n_edges > EdgeIter
Linear iterator.
HalfedgeIter halfedges_begin()
Begin iterator for halfedges.
FaceIter faces_end()
End iterator for faces.
ConstFaceEdgeIter cfe_iter(FaceHandle _fh) const
const face - edge circulator
void delete_edge(EdgeHandle _eh, bool _delete_isolated_vertices=true)
void set_deleted(bool _b)
set deleted
HalfedgeIter ConstHalfedgeIter
Linear iterator.
void split_copy(FaceHandle _fh, VertexHandle _vh)
Face split (= 1-to-n split).
const StatusInfo & status(VertexHandle _vh) const
Status Query API.
FaceHandle opposite_face_handle(HalfedgeHandle _heh) const
returns the face handle of the opposite halfedge
bool is_valid() const
The handle is valid iff the index is not equal to -1.
Handle for a halfedge entity.
HalfedgeHandle find_halfedge(VertexHandle _start_vh, VertexHandle _end_vh) const
Find halfedge from _vh0 to _vh1. Returns invalid handle if not found.
void set_tagged(bool _b)
set tagged
void copy_all_properties(VertexHandle _vh_from, VertexHandle _vh_to, bool _copyBuildIn=false)
bool is_manifold(VertexHandle _vh) const
Is (the mesh at) vertex _vh two-manifold ?
EdgeIter edges_begin()
Begin iterator for edges.
FaceIter faces_begin()
Begin iterator for faces.
bool is_simple_link(EdgeHandle _eh) const
static const VertexHandle InvalidVertexHandle
Invalid handle.
VertexFaceIter vf_iter(VertexHandle _vh)
vertex - face circulator
void reinsert_edge(EdgeHandle _eh)
HalfedgeHandle insert_edge(HalfedgeHandle _prev_heh, HalfedgeHandle _next_heh)
FaceIter ConstFaceIter
Linear iterator.
uint valence(VertexHandle _vh) const
Vertex valence.
bool tagged() const
is tagged ?
bool is_simply_connected(FaceHandle _fh) const
static const EdgeHandle InvalidEdgeHandle
Invalid handle.
VertexVertexIter vv_iter(VertexHandle _vh)
vertex - vertex circulator
void delete_face(FaceHandle _fh, bool _delete_isolated_vertices=true)
Handle for a vertex entity.
Iterators::GenericIteratorT< This, This::HalfedgeHandle, ArrayKernel,&ArrayKernel::has_halfedge_status,&ArrayKernel::n_halfedges > HalfedgeIter
Linear iterator.
void split_edge(EdgeHandle _eh, VertexHandle _vh)
VertexIter vertices_begin()
Begin iterator for vertices.
void triangulate()
triangulate the entire mesh
Handle for a edge entity.
VertexIter vertices_end()
End iterator for vertices.
void collapse_loop(HalfedgeHandle _hh)
Helper for halfedge collapse.
FaceHalfedgeIter fh_end(FaceHandle _fh)
face - halfedge circulator
bool deleted() const
is deleted ?
static const HalfedgeHandle InvalidHalfedgeHandle
Invalid handle.
Handle for a face entity.
bool is_boundary(HalfedgeHandle _heh) const
Check if the halfedge is at the boundary.
Iterators::GenericIteratorT< This, This::FaceHandle, ArrayKernel,&ArrayKernel::has_face_status,&ArrayKernel::n_faces > FaceIter
Linear iterator.
void adjust_outgoing_halfedge(VertexHandle _vh)
EdgeIter edges_end()
End iterator for edges.
ConstVertexOHalfedgeIter cvoh_iter(VertexHandle _vh) const
const vertex - outgoing halfedge circulator
FaceHalfedgeIter fh_iter(FaceHandle _fh)
face - halfedge circulator
VertexIter ConstVertexIter
Linear iterator.
static const FaceHandle InvalidFaceHandle
Invalid handle.
VertexIHalfedgeIter vih_iter(VertexHandle _vh)
vertex - incoming halfedge circulator
FaceHandle add_face(const std::vector< VertexHandle > &_vhandles)
Add and connect a new face.
void collapse_edge(HalfedgeHandle _hh)
Helper for halfedge collapse.
ConstFaceVertexIter cfv_iter(FaceHandle _fh) const
const face - vertex circulator
EdgeIter ConstEdgeIter
Linear iterator.
FaceHandle remove_edge(EdgeHandle _eh)