24 #ifndef _VCG_FACE_TOPOLOGY
25 #define _VCG_FACE_TOPOLOGY
27 #include <vcg/simplex/face/pos.h>
38 template <
class FaceType>
39 inline bool IsManifold( FaceType
const & f,
const int j )
41 assert(f.cFFp(j) != 0);
42 if(FaceType::HasFFAdjacency())
43 return ( f.cFFp(j) == &f || &f == f.cFFp(j)->cFFp(f.cFFi(j)) );
52 template <
class FaceType>
53 inline bool IsBorder(FaceType
const & f,
const int j )
55 if(FaceType::HasFFAdjacency())
81 template <
class FaceType>
84 typedef typename FaceType::ScalarType ScalarType;
85 typedef typename FaceType::CoordType CoordType;
86 typedef typename FaceType::VertexType VertexType;
89 FaceType *f1 = f.FFp(i);
92 VertexType *vf0 = f0->V2(i0);
93 VertexType *vf1 = f1->V2(i1);
95 CoordType n0 = TriangleNormal(*f0).Normalize();
96 CoordType n1 = TriangleNormal(*f1).Normalize();
97 ScalarType off0 = n0*vf0->P();
98 ScalarType off1 = n1*vf1->P();
100 ScalarType dist01 = off0 - n0*vf1->P();
101 ScalarType dist10 = off1 - n1*vf0->P();
105 if(fabs(dist01) > fabs(dist10)) sign = dist01;
108 ScalarType angleRad=AngleN(n0,n1);
110 if(sign > 0 )
return angleRad;
111 else return -angleRad;
115 template <
class FaceType>
116 inline typename FaceType::ScalarType
WedgeAngleRad(FaceType & f,
const int i )
119 auto &P1=f.P(f.Next(i));
120 auto &P2=f.P(f.Prev(i));
121 return vcg::Angle(P2 - P0,P1 - P0);
125 template <
class FaceType>
128 if(FaceType::HasFFAdjacency())
141 template <
class FaceType>
144 if(FaceType::HasFFAdjacency())
146 if(face::IsBorder<FaceType>(f,e))
return 1;
147 if(face::IsManifold<FaceType>(f,e))
return 2;
150 Pos< FaceType > fpos(&f,e);
155 assert(!fpos.IsBorder());
156 assert(!fpos.IsManifold());
174 template <
class FaceType>
177 if(f.FFp(e)==0)
return false;
181 if(f.FFi(e)==e)
return true;
185 if(f.FFp(e)->FFp(f.FFi(e))==&f)
187 if(f.FFp(e)->FFi(f.FFi(e))==e)
return true;
194 Pos< FaceType > curFace(&f,e);
198 if(curFace.IsManifold())
return false;
199 if(curFace.IsBorder())
return false;
204 while ( curFace.f != &f);
216 template <
class FaceType>
219 assert(FFCorrectness<FaceType>(f,e));
220 assert(!IsBorder<FaceType>(f,e));
221 FaceType *ffp = f.FFp(e);
235 assert(FFCorrectness<FaceType>(f,e));
236 assert(FFCorrectness<FaceType>(*ffp,ffi));
246 template <
class FaceType>
249 assert(FFCorrectness<FaceType>(f,e));
250 assert(!IsBorder<FaceType>(f,e));
253 assert(complexity>0);
254 vcg::face::Pos<FaceType> FirstFace(&f,e);
255 vcg::face::Pos<FaceType> LastFace(&f,e);
264 while ( LastFace.f->FFp(LastFace.z) != &f)
266 assert(
ComplexSize(*LastFace.f,LastFace.z)==complexity);
267 assert(!LastFace.IsManifold());
268 assert(!LastFace.IsBorder());
274 assert(LastFace.f->FFp(LastFace.z)==&f);
275 assert(f.FFp(e)== FirstFace.f);
278 LastFace.f->FFp(LastFace.z) = FirstFace.f;
279 LastFace.f->FFi(LastFace.z) = FirstFace.z;
280 assert(
ComplexSize(*LastFace.f,LastFace.z)==complexity-1);
287 assert(FFCorrectness<FaceType>(*LastFace.f,LastFace.z));
288 assert(FFCorrectness<FaceType>(f,e));
299 template <
class FaceType>
300 void FFAttach(FaceType * f,
int z1, FaceType * f2,
int z2)
303 vcg::face::Pos< FaceType > EPB(f2,z2);
304 vcg::face::Pos< FaceType > TEPB;
313 FaceType *f1prec = f->FFp(z1);
314 int z1prec = f->FFi(z1);
318 assert(TEPB.f->FFp(TEPB.z) == f2);
320 f->FFp(z1) = TEPB.f->FFp(TEPB.z);
321 f->FFi(z1) = TEPB.f->FFi(TEPB.z);
324 TEPB.f->FFp(TEPB.z) = f1prec;
325 TEPB.f->FFi(TEPB.z) = z1prec;
327 assert(FFCorrectness<FaceType>(*f,z1));
328 assert(FFCorrectness<FaceType>(*TEPB.f, TEPB.z));
339 template <
class FaceType>
342 assert(IsBorder<FaceType>(*f1,z1) || f1->FFp(z1)==0);
343 assert(IsBorder<FaceType>(*f2,z2) || f2->FFp(z2)==0);
344 assert(f1->V0(z1) == f2->V0(z2) || f1->V0(z1) == f2->V1(z2));
345 assert(f1->V1(z1) == f2->V0(z2) || f1->V1(z1) == f2->V1(z2));
353 template <
class FaceType>
354 void FFSetBorder(FaceType * f1,
int z1)
356 assert(f1->FFp(z1)==0 ||
IsBorder(*f1,z1));
362 template <
class FaceType>
363 void AssertAdj(FaceType & f)
366 assert(f.FFp(0)->FFp(f.FFi(0))==&f);
367 assert(f.FFp(1)->FFp(f.FFi(1))==&f);
368 assert(f.FFp(2)->FFp(f.FFi(2))==&f);
370 assert(f.FFp(0)->FFi(f.FFi(0))==0);
371 assert(f.FFp(1)->FFi(f.FFi(1))==1);
372 assert(f.FFp(2)->FFi(f.FFi(2))==2);
380 template <
class FaceType>
387 FaceType *g = f.FFp(z);
389 if (f.V0(z) == g->V1(gi))
401 template <
class FaceType>
402 void SwapEdge(FaceType &f,
const int z) { SwapEdge<FaceType,true>(f,z); }
404 template <
class FaceType,
bool UpdateTopology>
405 void SwapEdge(FaceType &f,
const int z)
408 std::swap(f.V0(z), f.V1(z));
411 bool Faux1 = f.IsF((z+1)%3);
412 bool Faux2 = f.IsF((z+2)%3);
413 if(Faux1) f.SetF((z+2)%3);
else f.ClearF((z+2)%3);
414 if(Faux2) f.SetF((z+1)%3);
else f.ClearF((z+1)%3);
416 if(f.HasFFAdjacency() && UpdateTopology)
421 FaceType *g1p = f.FFp(z1);
422 FaceType *g2p = f.FFp(z2);
458 template <
class FaceType>
461 typedef typename FaceType::VertexType VertexType;
462 typedef typename vcg::face::Pos< FaceType > PosType;
464 VertexType *v0=f.V0(z);
465 VertexType *v1=f.V1(z);
469 std::vector<VertexType *>v0Vec;
470 std::vector<VertexType *>v1Vec;
473 std::set<VertexType *> v0set;
474 v0set.insert(v0Vec.begin(),v0Vec.end());
475 assert(v0set.size() == v0Vec.size());
477 for(
size_t i=0;i<v1Vec.size();++i)
478 if(v0set.find(v1Vec[i]) != v0set.end())
503 template <
class MeshType>
506 typedef typename MeshType::FaceType FaceType;
507 typedef typename MeshType::VertexType VertexType;
508 typedef typename vcg::face::Pos< FaceType > PosType;
511 FaceType *f1 = f.FFp(z);
514 VertexType *delV=f.V0(z);
515 VertexType *surV=f.V1(z);
518 PosType delPos(f0,delV);
519 std::vector<PosType> faceToBeChanged;
523 FaceType *f01= 0,*f02= 0,*f11= 0,*f12= 0;
524 int i01=-1, i02=-1, i11=-1, i12=-1;
526 bool f0Faux = f0->IsF((z0+1)%3) && f0->IsF((z0+2)%3);
527 bool f1Faux = f1->IsF((z1+1)%3) && f1->IsF((z1+2)%3);
535 for(
size_t i=0;i<faceToBeChanged.size();++i) {
536 assert(faceToBeChanged[i].V() == delV);
537 faceToBeChanged[i].F()->V(faceToBeChanged[i].VInd()) =surV;
543 if(f0Faux) {f01->SetF(i01); f02->SetF(i02);}
547 if(f1Faux) {f11->SetF(i11); f12->SetF(i12);}
573 template <
class FaceType>
576 typedef typename FaceType::VertexType VertexType;
577 typedef typename VertexType::CoordType CoordType;
579 VertexType *OldDiag0 = f.V0(z);
580 VertexType *OldDiag1 = f.V1(z);
582 VertexType *NewDiag0 = f.V2(z);
583 VertexType *NewDiag1 = f.FFp(z)->V2(f.FFi(z));
585 assert((NewDiag1 != NewDiag0) && (NewDiag1 != OldDiag0) && (NewDiag1 != OldDiag1));
587 CoordType oldN0 = Normal( NewDiag0->cP(),OldDiag0->cP(),OldDiag1->cP()).Normalize();
588 CoordType oldN1 = Normal( NewDiag1->cP(),OldDiag1->cP(),OldDiag0->cP()).Normalize();
589 CoordType newN0 = Normal( OldDiag0->cP(),NewDiag1->cP(),NewDiag0->cP()).Normalize();
590 CoordType newN1 = Normal( OldDiag1->cP(),NewDiag0->cP(),NewDiag1->cP()).Normalize();
591 if(AngleN(oldN0,newN0) > angleRad)
return false;
592 if(AngleN(oldN0,newN1) > angleRad)
return false;
593 if(AngleN(oldN1,newN0) > angleRad)
return false;
594 if(AngleN(oldN1,newN1) > angleRad)
return false;
605 template <
class FaceType>
608 typedef typename FaceType::VertexType VertexType;
609 typedef typename vcg::face::Pos< FaceType > PosType;
611 if (z<0 || z>2)
return false;
616 FaceType *g = f.FFp(z);
621 if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
626 VertexType *f_v2 = f.V2(z);
627 VertexType *g_v2 = g->V2(w);
630 if (f_v2 == g_v2)
return false;
635 PosType pos(&f, (z+2)%3, f_v2);
636 PosType startPos=pos;
640 if (g_v2 == pos.VFlip())
643 while (pos != startPos);
648 template <
class FaceType>
649 bool checkFlipEdgeNotManifold (FaceType &f,
const int z)
651 typedef typename FaceType::VertexType VertexType;
652 typedef typename vcg::face::Pos< FaceType > PosType;
653 if (z<0 || z>2)
return false;
658 FaceType *g = f.FFp(z);
663 if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
668 VertexType *f_v2 = f.V2(z);
669 VertexType *g_v2 = g->V2(w);
671 PosType pos(&f, (z+2)%3, f_v2);
672 PosType startPos=pos;
678 if (g_v2 == pos.VFlip())
681 while (pos != startPos);
711 template <
class FaceType>
717 assert( face::IsManifold<FaceType>(f, z));
719 FaceType *g = f.FFp(z);
722 assert( g->V0(w) == f.V1(z) );
723 assert( g->V1(w) == f.V0(z) );
724 assert( g->V2(w) != f.V0(z) );
725 assert( g->V2(w) != f.V1(z) );
726 assert( g->V2(w) != f.V2(z) );
734 f.FFp(z) = g->FFp((w+1)%3);
735 f.FFi(z) = g->FFi((w+1)%3);
736 g->FFp(w) = f.FFp((z+1)%3);
737 g->FFi(w) = f.FFi((z+1)%3);
740 f.FFi((z+1)%3) = (w+1)%3;
741 g->FFp((w+1)%3) = &f;
742 g->FFi((w+1)%3) = (z+1)%3;
751 f.FFp(z)->FFp( f.FFi(z) ) = &f;
752 f.FFp(z)->FFi( f.FFi(z) ) = z;
761 g->FFp(w)->FFp( g->FFi(w) ) = g;
762 g->FFp(w)->FFi( g->FFi(w) ) = w;
790 template <
class FaceType>
796 assert( face::IsManifold<FaceType>(f, z));
798 FaceType *g = f.FFp(z);
801 assert( g->V0(w) == f.V1(z) );
802 assert( g->V1(w) == f.V0(z) );
803 assert( g->V2(w) != f.V0(z) );
804 assert( g->V2(w) != f.V1(z) );
805 assert( g->V2(w) != f.V2(z) );
807 int fi1 = f.FFi(f.Next(z));
808 FaceType* fp1 = f.FFp(f.Next(z));
810 int gi1 = g->FFi(g->Next(w));
811 FaceType* gp1 = g->FFp(g->Next(w));
834 template <
class FaceType>
835 void TriSplit(FaceType *fToSplit, FaceType *newf0, FaceType *newf1,
typename FaceType::VertexType *newVert)
837 typedef typename FaceType::VertexType VertexType;
839 VertexType *vp0 = fToSplit->V(0);
840 VertexType *vp1 = fToSplit->V(1);
841 VertexType *vp2 = fToSplit->V(2);
843 fToSplit->V(0) = vp0; fToSplit->V(1) = vp1; fToSplit->V(2) = newVert;
844 newf0->V(0) = vp1; newf0->V(1) = vp2; newf0->V(2) = newVert;
845 newf1->V(0) = vp2; newf1->V(1) = vp0; newf1->V(2) = newVert;
850 template <
class FaceType>
851 void VFDetach(FaceType & f)
861 template <
class FaceType>
862 void VFDetach(FaceType & f,
int z)
864 if(f.V(z)->VFp()==&f )
866 int fz = f.V(z)->VFi();
867 f.V(z)->VFp() = f.VFp(fz);
868 f.V(z)->VFi() = f.VFi(fz);
872 VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
873 VFIterator<FaceType> y;
882 y.f->VFp(y.z) = f.VFp(z);
883 y.f->VFi(y.z) = f.VFi(z);
891 template <
class FaceType>
894 typename FaceType::VertexType *v = f->V(z);
897 FaceType *f0=v->VFp();
915 template <
class FaceType>
916 void VVStarVF(
typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
918 typedef typename FaceType::VertexType* VertexPointer;
921 face::VFIterator<FaceType> vfi(vp);
924 const int vn = vfi.F()->VN();
925 starVec.push_back(vfi.F()->V1(vfi.I()));
926 starVec.push_back(vfi.F()->V((vfi.I()+vn-1)%vn));
930 std::sort(starVec.begin(),starVec.end());
931 typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
932 starVec.resize(new_end-starVec.begin());
943 template <
class FaceType>
946 std::vector<typename FaceType::VertexType *> &vertVec)
948 typedef typename FaceType::VertexType VertexType;
951 vcg::face::VVStarVF<FaceType>(vp,vertVec);
954 for (
int step=0;step<num_step-1;step++)
956 std::vector<VertexType *> toAdd;
957 for (
unsigned int i=0;i<vertVec.size();i++)
959 std::vector<VertexType *> Vtemp;
960 vcg::face::VVStarVF<FaceType>(vertVec[i],Vtemp);
961 toAdd.insert(toAdd.end(),Vtemp.begin(),Vtemp.end());
963 vertVec.insert(vertVec.end(),toAdd.begin(),toAdd.end());
964 std::sort(vertVec.begin(),vertVec.end());
965 typename std::vector<typename FaceType::VertexType *>::iterator new_end=std::unique(vertVec.begin(),vertVec.end());
966 int dist=distance(vertVec.begin(),new_end);
967 vertVec.resize(dist);
978 template <
class FaceType>
980 std::vector<FaceType *> &faceVec,
981 std::vector<int> &indexes)
987 face::VFIterator<FaceType> vfi(vp);
990 faceVec.push_back(vfi.F());
991 indexes.push_back(vfi.I());
1005 template <
class FaceType>
1007 std::vector<FaceType *> &faceVec,
1008 std::vector<int> &indVed)
1010 assert(fp->FFp(ei)!=0);
1017 faceVec.push_back(fpit);
1018 indVed.push_back(eit);
1019 FaceType *new_fpit = fpit->FFp(eit);
1020 int new_eit = fpit->FFi(eit);
1023 }
while(fpit != fp);
1033 template <
class FaceType>
1034 static void FFExtendedStarFF(FaceType *fp,
1036 std::vector<FaceType*> &faceVec)
1039 faceVec.push_back(fp);
1042 for (
int step=0;step<num_step;step++)
1044 std::vector<FaceType*> toAdd;
1045 for (
unsigned int i=0;i<faceVec.size();i++)
1047 FaceType *f=faceVec[i];
1048 for (
int k=0;k<3;k++)
1050 FaceType *f1=f->FFp(k);
1052 toAdd.push_back(f1);
1055 faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1056 std::sort(faceVec.begin(),faceVec.end());
1057 typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1058 int dist=distance(faceVec.begin(),new_end);
1059 faceVec.resize(dist);
1071 template <
class FaceType>
1074 std::vector<FaceType*> &faceVec)
1078 std::vector<int> indexes;
1079 vcg::face::VFStarVF<FaceType>(vp,faceVec,indexes);
1082 for (
int step=0;step<num_step;step++)
1084 std::vector<FaceType*> toAdd;
1085 for (
unsigned int i=0;i<faceVec.size();i++)
1087 FaceType *f=faceVec[i];
1088 for (
int k=0;k<3;k++)
1090 FaceType *f1=f->FFp(k);
1092 toAdd.push_back(f1);
1095 faceVec.insert(faceVec.end(),toAdd.begin(),toAdd.end());
1096 std::sort(faceVec.begin(),faceVec.end());
1097 typename std::vector<FaceType*>::iterator new_end=std::unique(faceVec.begin(),faceVec.end());
1098 int dist=distance(faceVec.begin(),new_end);
1099 faceVec.resize(dist);
1110 template <
class FaceType>
1112 std::vector<typename FaceType::VertexType *> &vertexVec)
1115 vertexVec.reserve(16);
1116 std::vector<Pos<FaceType> > posVec;
1118 for(
size_t i=0;i<posVec.size();++i)
1119 vertexVec.push_back(posVec[i].VFlip());
1130 template <
class FaceType>
1132 std::vector<typename FaceType::VertexType *> &vertexVec,
1136 vertexVec.reserve(16);
1137 std::vector<Pos<FaceType> > posVec;
1139 for(
size_t i=0;i<posVec.size();++i)
1140 vertexVec.push_back(posVec[i].VFlip());
1150 template <
class FaceType>
1152 std::vector<Pos<FaceType> > &posVec)
1156 bool foundBorder=
false;
1157 size_t firstBorderInd;
1158 Pos<FaceType> curPos=startPos;
1161 assert(curPos.IsManifold());
1162 if(curPos.IsBorder() && !foundBorder) {
1164 firstBorderInd = posVec.size();
1166 posVec.push_back(curPos);
1169 }
while(curPos!=startPos);
1174 size_t halfSize=posVec.size()/2;
1175 assert((posVec.size()%2)==0);
1176 posVec.erase(posVec.begin()+firstBorderInd+1+halfSize, posVec.end());
1177 posVec.erase(posVec.begin(),posVec.begin()+firstBorderInd+1);
1178 assert(posVec.size()==halfSize);
1190 template <
class FaceType>
1192 std::vector<Pos<FaceType> > &posVec,
1196 const auto & pos = posVec[0];
1197 if (ccw != (pos.VFlip() == pos.F()->V(pos.F()->Prev(pos.VInd()))))
1199 std::reverse(posVec.begin(), posVec.end());
1212 template <
class FaceType>
1214 std::vector<FaceType*> &faceVec,
1215 std::vector<int> &edgeVec)
1217 std::vector<Pos<FaceType> > posVec;
1221 faceVec.reserve(16);
1222 edgeVec.reserve(16);
1223 for(
size_t i=0;i<posVec.size();++i)
1225 faceVec.push_back(posVec[i].F());
1226 edgeVec.push_back(posVec[i].E());
1236 template <
class FaceType>
1239 assert((!f0->IsD())&&(!f1->IsD()));
1240 for (
int i=0;i<3;i++)
1243 if((i0!=0) && (i1!=0)) {
1257 template <
class FaceType>
1261 for (
int i=0;i<3;i++)
1262 for (
int j=0;j<3;j++)
1263 if (f0->V(i)==f1->V(j)) {
1275 template <
class FaceType>
1280 if (f0->V(i)==f1->V(j))
return true;
1292 template <
class FaceType>
1297 if( ( f0->V0(i)==f1->V0(j) || f0->V0(i)==f1->V1(j) ) &&
1298 ( f0->V1(i)==f1->V0(j) || f0->V1(i)==f1->V1(j) ) )
1310 template <
class FaceType>
1312 typename FaceType::VertexType *v1,
1318 std::vector<FaceType*> faces0;
1319 std::vector<FaceType*> faces1;
1320 std::vector<int> index0;
1321 std::vector<int> index1;
1322 VFStarVF<FaceType>(v0,faces0,index0);
1323 VFStarVF<FaceType>(v1,faces1,index1);
1325 std::sort(faces0.begin(),faces0.end());
1326 std::sort(faces1.begin(),faces1.end());
1327 std::vector<FaceType*> Intersection;
1328 std::set_intersection(faces0.begin(),faces0.end(),faces1.begin(),faces1.end(),std::back_inserter(Intersection));
1329 if (Intersection.size()<2)
return false;
1330 assert(Intersection.size()==2);