vcglib: topology.h Source File

00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2004                                                \/)\/    *
00006 * Visual Computing Lab                                            /\/|      *
00007 * ISTI - Italian National Research Council                           |      *
00008 *                                                                    \      *
00009 * All rights reserved.                                                      *
00010 *                                                                           *
00011 * This program is free software; you can redistribute it and/or modify      *   
00012 * it under the terms of the GNU General Public License as published by      *
00013 * the Free Software Foundation; either version 2 of the License, or         *
00014 * (at your option) any later version.                                       *
00015 *                                                                           *
00016 * This program is distributed in the hope that it will be useful,           *
00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020 * for more details.                                                         *
00021 *                                                                           *
00022 ****************************************************************************/
00023 
00024 #ifndef _VCG_FACE_TOPOLOGY
00025 #define _VCG_FACE_TOPOLOGY
00026 
00027 #include <vcg/simplex/face/pos.h>
00028 #include <vcg/complex/trimesh/allocate.h>
00029 #include <algorithm>
00030 
00031 namespace vcg {
00032 namespace face {
00035 
00040 template <class FaceType>
00041 inline bool IsManifold( FaceType const & f, const int j ) 
00042 {
00043   assert(f.cFFp(j) != 0); // never try to use this on uncomputed topology
00044   if(FaceType::HasFFAdjacency())
00045           return ( f.cFFp(j) == &f || &f == f.cFFp(j)->cFFp(f.cFFi(j)) );
00046   else 
00047     return true;
00048 }
00049 
00054 template <class FaceType>
00055 inline bool IsBorder(FaceType const & f,  const int j ) 
00056 {
00057   if(FaceType::HasFFAdjacency())
00058           return f.cFFp(j)==&f;
00059     //return f.IsBorder(j);
00060   
00061   assert(0);
00062   return true;
00063 }
00064 
00065 
00067 template <class FaceType>
00068 inline int BorderCount(FaceType const & f) 
00069 {
00070   if(FaceType::HasFFAdjacency())
00071   {
00072     int t = 0;
00073           if( IsBorder(f,0) ) ++t;
00074           if( IsBorder(f,1) ) ++t;
00075           if( IsBorder(f,2) ) ++t;
00076           return t;
00077   }
00078         else    return 3;
00079 }
00080 
00081 
00083 template <class FaceType>
00084 inline int ComplexSize(FaceType & f, const int e)
00085 {
00086   if(FaceType::HasFFAdjacency())
00087   {
00088     if(face::IsBorder<FaceType>(f,e))  return 1;
00089     if(face::IsManifold<FaceType>(f,e)) return 2;
00090                       
00091     // Non manifold case
00092     Pos< FaceType > fpos(&f,e); 
00093     int cnt=0;
00094     do
00095     {
00096                   fpos.NextF();
00097       assert(!fpos.IsBorder());
00098       assert(!fpos.IsManifold());
00099                   ++cnt;
00100           }
00101           while(fpos.f!=&f);
00102     assert (cnt>2);
00103           return cnt;
00104   }
00105   assert(0);
00106         return 2;
00107 }
00108 
00109 
00116 template <class FaceType>
00117 bool FFCorrectness(FaceType & f, const int e)
00118 {
00119   if(f.FFp(e)==0) return false;   // Not computed or inconsistent topology
00120 
00121   if(f.FFp(e)==&f) // Border
00122   {
00123    if(f.FFi(e)==e) return true;
00124    else return false;
00125   }
00126 
00127   if(f.FFp(e)->FFp(f.FFi(e))==&f) // plain two manifold 
00128   {
00129     if(f.FFp(e)->FFi(f.FFi(e))==e) return true;
00130     else return false;
00131   }
00132 
00133   // Non Manifold Case
00134   // all the faces must be connected in a loop.
00135 
00136   Pos< FaceType > curFace(&f,e);  // Build the half edge
00137         int cnt=0;
00138   do
00139         { 
00140                 if(curFace.IsManifold()) return false;  
00141                 if(curFace.IsBorder()) return false;
00142                 curFace.NextF();
00143                 cnt++;
00144     assert(cnt<100);
00145         }
00146   while ( curFace.f != &f);
00147   return true;
00148 }
00149 
00150 
00157 template <class FaceType>
00158 void FFDetachManifold(FaceType & f, const int e)
00159 {
00160     assert(FFCorrectness<FaceType>(f,e));
00161     assert(!IsBorder<FaceType>(f,e));  // Never try to detach a border edge!
00162     FaceType *ffp = f.FFp(e);
00163     //int ffi=f.FFp(e);
00164         int ffi=f.FFi(e);
00165 
00166     f.FFp(e)=&f;
00167     f.FFi(e)=e;
00168     ffp->FFp(ffi)=ffp;
00169     ffp->FFi(ffi)=ffi;
00170 
00171     f.SetB(e);
00172     f.ClearF(e);
00173     ffp->SetB(ffi);
00174     ffp->ClearF(ffi);
00175 
00176     assert(FFCorrectness<FaceType>(f,e));
00177     assert(FFCorrectness<FaceType>(*ffp,ffi));
00178 }
00179 
00187 template <class FaceType>
00188 void FFDetach(FaceType & f, const int e)
00189 {
00190     assert(FFCorrectness<FaceType>(f,e));
00191     assert(!IsBorder<FaceType>(f,e));  // Never try to detach a border edge!
00192     int complexity;
00193     assert(complexity=ComplexSize(f,e));
00194 
00195     Pos< FaceType > FirstFace(&f,e);  // Build the half edge
00196         Pos< FaceType > LastFace(&f,e);  // Build the half edge
00197         FirstFace.NextF(); 
00198     LastFace.NextF();
00199         int cnt=0;
00200 
00201     // then in case of non manifold face continue to advance LastFace
00202     // until I find it become the one that
00203     // preceed the face I want to erase
00204 
00205         while ( LastFace.f->FFp(LastFace.z) != &f)
00206         { 
00207         assert(ComplexSize(*LastFace.f,LastFace.z)==complexity);
00208                 assert(!LastFace.IsManifold());   // We enter in this loop only if we are on a non manifold edge
00209                 assert(!LastFace.IsBorder());
00210                 LastFace.NextF();
00211                 cnt++;
00212         assert(cnt<100);
00213         }
00214 
00215         assert(LastFace.f->FFp(LastFace.z)==&f);
00216     assert(f.FFp(e)== FirstFace.f);
00217 
00218         // Now we link the last one to the first one, skipping the face to be detached;
00219     LastFace.f->FFp(LastFace.z) = FirstFace.f;
00220     LastFace.f->FFi(LastFace.z) = FirstFace.z;
00221     assert(ComplexSize(*LastFace.f,LastFace.z)==complexity-1);
00222 
00223     // At the end selfconnect the chosen edge to make a border.
00224     f.FFp(e) = &f;
00225         f.FFi(e) = e;
00226     assert(ComplexSize(f,e)==1);
00227 
00228     assert(FFCorrectness<FaceType>(*LastFace.f,LastFace.z));
00229     assert(FFCorrectness<FaceType>(f,e));
00230 }
00231 
00232 
00239 template <class FaceType>
00240 void Attach(FaceType * &f, int z1, FaceType *&f2, int z2)
00241 {
00242         //typedef FEdgePosB< FACE_TYPE > ETYPE;
00243         Pos< FaceType > EPB(f2,z2);
00244         Pos< FaceType > TEPB;
00245         TEPB = EPB;
00246         EPB.NextF();
00247         while( EPB.f != f2)  //Alla fine del ciclo TEPB contiene la faccia che precede f2
00248         {
00249                 TEPB = EPB;
00250                 EPB.NextF();
00251         }
00252         //Salvo i dati di f1 prima di sovrascrivere
00253         FaceType *f1prec = f.FFp(z1);  
00254         int z1prec = f.FFi(z1);
00255         //Aggiorno f1
00256         f->FFp(z1) = TEPB.f->FFp(TEPB.z);  
00257         f->FFi(z1) = TEPB.f->FFi(TEPB.z);
00258         //Aggiorno la faccia che precede f2
00259         TEPB.f->FFp(TEPB.z) = f1prec;
00260         TEPB.f->FFi(TEPB.z) = z1prec;
00261 }
00262 
00263 
00264 template <class FaceType>
00265 void AssertAdj(FaceType & f)
00266 {
00267         assert(f.FFp(0)->FFp(f.FFi(0))==&f);
00268         assert(f.FFp(1)->FFp(f.FFi(1))==&f);
00269         assert(f.FFp(2)->FFp(f.FFi(2))==&f);
00270 
00271         assert(f.FFp(0)->FFi(f.FFi(0))==0);
00272         assert(f.FFp(1)->FFi(f.FFi(1))==1);
00273         assert(f.FFp(2)->FFi(f.FFi(2))==2); 
00274 }
00275 // Funzione di supporto usata da swap?
00276 //template <class FaceType>
00277 //inline void Nexts(  *&f, int &z )
00278 //{
00279 //    int t;
00280 //    t = z;
00281 //    z = (*f).Z(z);
00282 //    f = (*f).F(t);
00283 //}
00284 
00290 template <class FaceType>
00291 bool CheckOrientation(FaceType &f, int z)
00292 {
00293         if (IsBorder(f, z))
00294                 return true;
00295         else
00296         {
00297                 FaceType *g = f.FFp(z);
00298                 int gi = f.FFi(z);
00299                 if (f.V0(z) == g->V1(gi))
00300                         return true;
00301                 else
00302                         return false;
00303         }
00304 }
00305 
00306 
00311 template <class FaceType>
00312 void SwapEdge(FaceType &f, const int z) { SwapEdge<FaceType,true>(f,z); }
00313 
00314 template <class FaceType, bool UpdateTopology>
00315 void SwapEdge(FaceType &f, const int z)
00316 {
00317         // swap V0(z) with V1(z)
00318         std::swap(f.V0(z), f.V1(z));
00319 
00320         if(f.HasFFAdjacency() && UpdateTopology)
00321         {
00322                 // store information to preserve topology
00323                 int z1 = (z+1)%3;
00324                 int z2 = (z+2)%3;
00325                 FaceType *g1p = f.FFp(z1);
00326                 FaceType *g2p = f.FFp(z2);
00327                 int g1i = f.FFi(z1);
00328                 int g2i = f.FFi(z2);
00329 
00330                 // g0 face topology is not affected by the swap
00331 
00332                 if (g1p != &f)
00333                 {
00334                         g1p->FFi(g1i) = z2;
00335                         f.FFi(z2) = g1i;
00336                 }
00337                 else
00338                 {
00339                         f.FFi(z2) = z2;
00340                 }
00341 
00342                 if (g2p != &f)
00343                 {
00344                         g2p->FFi(g2i) = z1;
00345                         f.FFi(z1) = g2i;
00346                 }
00347                 else
00348                 {
00349                         f.FFi(z1) = z1;
00350                 }
00351 
00352                 // finalize swap
00353                 f.FFp(z1) = g2p;
00354                 f.FFp(z2) = g1p;
00355         }
00356 }
00357 
00363 template <class FaceType>
00364 static bool CheckFlipEdge(FaceType &f, int z)
00365 {
00366         if (z<0 || z>2)
00367                 return false;
00368 
00369         // boundary edges cannot be flipped
00370         if (face::IsBorder(f, z))
00371                 return false;
00372 
00373         FaceType *g = f.FFp(z);
00374         int              w = f.FFi(z);
00375 
00376         // check if the vertices of the edge are the same
00377         if (g->V(w)!=f.V1(z) || g->V1(w)!=f.V(z) )
00378                 return false;
00379 
00380         // check if the flipped edge is already present in the mesh
00381         typedef typename FaceType::VertexType VertexType;
00382         VertexType *f_v2 = f.V2(z);
00383         VertexType *g_v2 = g->V2(w);
00384         if (f_v2 == g_v2)
00385                 return false;
00386 
00387         vcg::face::Pos< FaceType > pos(&f, (z+2)%3, f.V2(z));
00388         do
00389         {
00390                 pos.NextE();
00391                 if (g_v2==pos.f->V1(pos.z))
00392                         return false;
00393         }
00394         while (&f!=pos.f);
00395 
00396         return true;
00397 }
00398 
00408 template <class FaceType>
00409 static void FlipEdge(FaceType &f, const int z)
00410 {       
00411         assert(z>=0);
00412         assert(z<3);
00413         assert( !IsBorder(f,z) );
00414         assert( face::IsManifold<FaceType>(f, z));
00415 
00416         FaceType *g = f.FFp(z);
00417         int              w = f.FFi(z);
00418         
00419         assert( g->V(w) == f.V1(z) );
00420         assert( g->V1(w)== f.V(z) );
00421         assert( g->V2(w)!= f.V(z) );
00422         assert( g->V2(w)!= f.V1(z) );
00423         assert( g->V2(w)!= f.V2(z) );
00424 
00425         f.V1(z) = g->V2(w);
00426         g->V1(w) = f.V2(z);
00427         
00428     f.FFp(z)                            = g->FFp((w+1)%3);
00429         f.FFi(z)                                = g->FFi((w+1)%3);
00430     g->FFp(w)                           = f.FFp((z+1)%3);
00431         g->FFi(w)                               = f.FFi((z+1)%3);
00432     f.FFp((z+1)%3)                              = g;
00433         f.FFi((z+1)%3)  = (w+1)%3;
00434     g->FFp((w+1)%3)                     = &f;
00435         g->FFi((w+1)%3) = (z+1)%3;
00436 
00437         if(f.FFp(z)==g)
00438         {
00439                 f.FFp(z) = &f;
00440                 f.FFi(z) = z;
00441         }
00442         else
00443         {
00444                 f.FFp(z)->FFp( f.FFi(z) ) = &f;
00445                 f.FFp(z)->FFi( f.FFi(z) ) = z;
00446         }
00447         if(g->FFp(w)==&f)
00448         {
00449                 g->FFp(w)=g;
00450                 g->FFi(w)=w;
00451         }
00452         else
00453         {
00454                 g->FFp(w)->FFp( g->FFi(w) ) = g;
00455                 g->FFp(w)->FFi( g->FFi(w) ) = w;
00456         }
00457 }
00458 
00459 
00460 // Stacca la faccia corrente dalla catena di facce incidenti sul vertice z, 
00461 // NOTA funziona SOLO per la topologia VF!!!
00462 // usata nelle classi di collapse
00463 template <class FaceType>
00464 void VFDetach(FaceType & f, int z)
00465 {
00466         if(f.V(z)->VFp()==&f )  //if it is the first face detach from the begin
00467         {
00468                 int fz = f.V(z)->VFi();
00469                 f.V(z)->VFp() = f.VFp(fz);
00470                 f.V(z)->VFi() = f.VFi(fz);
00471         }
00472         else  // scan the list of faces in order to finde the current face f to be detached
00473         {
00474     VFIterator<FaceType> x(f.V(z)->VFp(),f.V(z)->VFi());
00475     VFIterator<FaceType> y;
00476 
00477                 for(;;)
00478                 {
00479                         y = x;
00480                         ++x;
00481                         assert(x.f!=0);
00482                         if(x.f==&f) // found!
00483                         {
00484                                 y.f->VFp(y.z) = f.VFp(z);
00485                                 y.f->VFi(y.z) = f.VFi(z);
00486                                 break;
00487                         }
00488                 }
00489         }
00490 }
00491 
00493 template <class FaceType>
00494 void VFAppend(FaceType* & f, int z)
00495 {
00496         typename FaceType::VertexType *v = f->V(z);
00497         if (v->VFp()!=0)
00498         {
00499                 FaceType *f0=v->VFp();  
00500                 int z0=v->VFi();
00501                 //append
00502                 f->VFp(z)=f0;
00503                 f->VFi(z)=z0;
00504         }
00505         v->VFp()=f;
00506         v->VFi()=z;
00507 }
00508 
00516 template <class FaceType>
00517 void VVStarVF( typename FaceType::VertexType* vp, std::vector<typename FaceType::VertexType *> &starVec)
00518 {
00519         typedef typename FaceType::VertexType* VertexPointer;
00520         starVec.clear();
00521         face::VFIterator<FaceType> vfi(vp);
00522         while(!vfi.End())
00523                         {
00524                                 starVec.push_back(vfi.F()->V1(vfi.I()));
00525                                 starVec.push_back(vfi.F()->V2(vfi.I()));
00526                                 ++vfi;
00527                         }
00528                                 
00529         std::sort(starVec.begin(),starVec.end());
00530         typename std::vector<VertexPointer>::iterator new_end = std::unique(starVec.begin(),starVec.end());
00531         starVec.resize(new_end-starVec.begin());
00532 }
00533 
00540 template <class FaceType>
00541 bool ShareEdgeFF(FaceType *f0,FaceType *f1, int *i0=0, int *i1=0)
00542 {
00543   assert((!f0->IsD())&&(!f1->IsD()));
00544   for (int i=0;i<3;i++)
00545       if (f0->FFp(i)==f1)
00546       {
00547         if((i0!=0) && (i1!=0)) {
00548           *i0=i;
00549           *i1=f0->FFi(i);
00550         }
00551         return true;
00552       }
00553   return false;
00554 }
00555 
00561 template <class FaceType>
00562 int CountSharedVertex(FaceType *f0,FaceType *f1)
00563 {
00564   int sharedCnt=0;
00565   for (int i=0;i<3;i++)
00566       for (int j=0;j<3;j++)
00567           if (f0->V(i)==f1->V(j)) {
00568                   sharedCnt++;
00569               }
00570   return sharedCnt;
00571 }
00572 
00579 template <class FaceType>
00580 bool SharedVertex(FaceType *f0,FaceType *f1, int &i, int &j)
00581 {
00582   for (i=0;i<3;i++)
00583       for (j=0;j<3;j++)
00584           if (f0->V(i)==f1->V(j)) return true;
00585 
00586   return false;
00587 }
00588 
00589 
00591 }        // end namespace
00592 }        // end namespace
00593 
00594 #endif
00595