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   History
00025 
00026 $Log: not supported by cvs2svn $
00027 Revision 1.20  2008/04/04 10:27:34  cignoni
00028 minor changes to the topology correctness checks
00029 
00030 Revision 1.19  2007/05/29 00:07:06  ponchio
00031 VFi++ -> ++VFi
00032 
00033 Revision 1.18  2006/02/27 19:26:14  spinelli
00034 minor bug in Face-Face topology loop fixed
00035 
00036 Revision 1.17  2006/02/27 11:56:48  spinelli
00037 minor bug in Face-Face topology loop fixed
00038 
00039 Revision 1.16  2005/11/10 15:36:42  cignoni
00040 Added clarifying comment in an assert
00041 
00042 Revision 1.15  2004/10/20 07:33:10  cignoni
00043 removed FaceBorderFlags (already present in update/flags.h)
00044 
00045 Revision 1.14  2004/10/18 17:10:22  ganovelli
00046 added  ::FaceBorderFLags
00047 
00048 Revision 1.13  2004/10/01 15:58:00  ponchio
00049 Added include <vector>
00050 
00051 Revision 1.12  2004/09/09 13:02:12  ponchio
00052 Linux compatible path in #include
00053 
00054 Revision 1.11  2004/08/07 16:18:20  pietroni
00055 addet testFFTopology and testVFTopology functions used to test the rispective topology....
00056 
00057 Revision 1.10  2004/07/15 11:35:08  ganovelli
00058 Vfb to VFp
00059 
00060 Revision 1.9  2004/07/15 00:13:39  cignoni
00061 Better doxigen documentation
00062 
00063 Revision 1.8  2004/06/02 16:42:44  ganovelli
00064 typename for gcc compilation
00065 
00066 Revision 1.7  2004/06/02 16:28:22  ganovelli
00067 minor changes (swap =>> math::Swap)
00068 
00069 Revision 1.6  2004/05/10 15:23:43  cignoni
00070 Changed a FV -> VF in VertexFace topology computation
00071 
00072 Revision 1.5  2004/05/06 15:24:38  pietroni
00073 changed names to topology functions
00074 
00075 Revision 1.4  2004/03/31 14:44:43  cignoni
00076 Added Vertex-Face Topology
00077 
00078 Revision 1.3  2004/03/12 15:22:19  cignoni
00079 Written some documentation and added to the trimes doxygen module
00080 
00081 Revision 1.2  2004/03/05 21:49:21  cignoni
00082 First working version for face face
00083 
00084 Revision 1.1  2004/03/04 00:53:24  cignoni
00085 Initial commit
00086 
00087 
00088 ****************************************************************************/
00089 #ifndef __VCG_TRI_UPDATE_TOPOLOGY
00090 #define __VCG_TRI_UPDATE_TOPOLOGY
00091 #include <algorithm>
00092 #include <vector>
00093 #include <vcg/simplex/face/pos.h>
00094 #include <vcg/complex/trimesh/base.h>
00095 namespace vcg {
00096 namespace tri {
00098 
00100 
00102 
00103 template <class UpdateMeshType>
00104 class UpdateTopology
00105 {
00106 
00107 public:
00108 typedef UpdateMeshType MeshType; 
00109 typedef typename MeshType::VertexType     VertexType;
00110 typedef typename MeshType::VertexPointer  VertexPointer;
00111 typedef typename MeshType::VertexIterator VertexIterator;
00112 typedef typename MeshType::FaceType       FaceType;
00113 typedef typename MeshType::FacePointer    FacePointer;
00114 typedef typename MeshType::FaceIterator   FaceIterator;
00115 
00116 
00118 
00120 
00124 class PEdge
00125 {
00126 public:
00127         
00128         VertexPointer  v[2];            // the two Vertex pointer are ordered!
00129         FacePointer    f;                 // the face where this edge belong
00130         int      z;                                   // index in [0..2] of the edge of the face
00131 
00132   PEdge() {}
00133 
00134 void Set( FacePointer  pf, const int nz )
00135 {
00136         assert(pf!=0);
00137         assert(nz>=0);
00138         assert(nz<pf->VN());
00139         
00140         v[0] = pf->V(nz);
00141         v[1] = pf->V(pf->Next(nz));
00142         assert(v[0] != v[1]); // The face pointed by 'f' is Degenerate (two coincident vertexes)
00143 
00144         if( v[0] > v[1] ) math::Swap(v[0],v[1]);
00145         f    = pf;
00146         z    = nz;
00147 }
00148 
00149 inline bool operator <  ( const PEdge & pe ) const
00150 {
00151         if( v[0]<pe.v[0] ) return true;
00152         else if( v[0]>pe.v[0] ) return false;
00153         else return v[1] < pe.v[1];
00154 }
00155 
00156 inline bool operator == ( const PEdge & pe ) const
00157 {
00158         return v[0]==pe.v[0] && v[1]==pe.v[1];
00159 }
00160 
00161 };
00162 
00163 // Fill a vector with all the edges of the mesh.
00164 // each edge is stored in the vector the number of times that it appears in the mesh, with the referring face. 
00165 // optionally it can skip the faux edges (to retrieve only the real edges of a triangulated polygonal mesh)
00166 
00167 static void FillEdgeVector(MeshType &m, std::vector<PEdge> &e, bool includeFauxEdge=true)
00168 {
00169         FaceIterator pf;
00170         typename std::vector<PEdge>::iterator p;
00171         
00172         // Alloco il vettore ausiliario
00173         //e.resize(m.fn*3);                     
00174         FaceIterator fi;
00175         int n_edges = 0;
00176         for(fi = m.face.begin(); fi != m.face.end(); ++fi) if(! (*fi).IsD()) n_edges+=(*fi).VN();
00177         e.resize(n_edges);
00178         
00179         p = e.begin();
00180         for(pf=m.face.begin();pf!=m.face.end();++pf)            
00181                 if( ! (*pf).IsD() )
00182                         for(int j=0;j<(*pf).VN();++j)
00183                         if(includeFauxEdge || !(*pf).IsF(j))
00184                                 {
00185                                         (*p).Set(&(*pf),j);
00186                                         ++p;
00187                                 }
00188                         
00189         if(includeFauxEdge) assert(p==e.end());
00190         else e.resize(p-e.begin());
00191 }
00192 
00193 static void FillUniqueEdgeVector(MeshType &m, std::vector<PEdge> &Edges, bool includeFauxEdge=true)
00194 {
00195         FillEdgeVector(m,Edges,includeFauxEdge);
00196         sort(Edges.begin(), Edges.end());               // Lo ordino per vertici
00197 
00198         typename std::vector< PEdge>::iterator newEnd = std::unique(Edges.begin(), Edges.end());
00199         typename std::vector<PEdge>::iterator   ei;
00200 
00201         Edges.resize(newEnd-Edges.begin());
00202 }
00203 
00205 static void FaceFace(MeshType &m)
00206 {
00207         assert(HasFFAdjacency(m));
00208         if( m.fn == 0 ) return;
00209 
00210   std::vector<PEdge> e;
00211   FillEdgeVector(m,e);
00212         sort(e.begin(), e.end());                                                       // Lo ordino per vertici
00213 
00214         int ne = 0;                                                                                     // Numero di edge reali
00215 
00216         typename std::vector<PEdge>::iterator pe,ps;
00217         ps = e.begin();pe=e.begin();
00218         //for(ps = e.begin(),pe=e.begin();pe<=e.end();++pe)     // Scansione vettore ausiliario
00219         do
00220         {
00221                 if( pe==e.end() || !(*pe == *ps) )                                      // Trovo blocco di edge uguali
00222                 {
00223                         typename std::vector<PEdge>::iterator q,q_next;
00224                         for (q=ps;q<pe-1;++q)                                           // Scansione facce associate
00225                         {
00226                                 assert((*q).z>=0);
00227                                 //assert((*q).z< 3);
00228                                 q_next = q;
00229                                 ++q_next;
00230                                 assert((*q_next).z>=0);
00231                                 assert((*q_next).z< (*q_next).f->VN());
00232                                 (*q).f->FFp(q->z) = (*q_next).f;                                // Collegamento in lista delle facce
00233                                 (*q).f->FFi(q->z) = (*q_next).z;
00234                         }
00235                         assert((*q).z>=0);
00236                         assert((*q).z< (*q).f->VN());
00237                         (*q).f->FFp((*q).z) = ps->f;
00238                         (*q).f->FFi((*q).z) = ps->z;
00239                         ps = pe;
00240                         ++ne;                                                                           // Aggiorno il numero di edge
00241                 }
00242                 if(pe==e.end()) break;
00243                 ++pe;
00244         } while(true);
00245 }
00246 
00247 
00249 
00253 static void VertexFace(MeshType &m)
00254 {
00255   if(!m.HasVFTopology()) return;                
00256 
00257         VertexIterator vi;
00258         FaceIterator fi;
00259 
00260         for(vi=m.vert.begin();vi!=m.vert.end();++vi)
00261         {
00262                 (*vi).VFp() = 0;
00263                 (*vi).VFi() = 0;
00264         }
00265 
00266         for(fi=m.face.begin();fi!=m.face.end();++fi)
00267         if( ! (*fi).IsD() )
00268         {
00269                 for(int j=0;j<(*fi).VN();++j)
00270                 {
00271                         (*fi).VFp(j) = (*fi).V(j)->VFp();
00272                         (*fi).VFi(j) = (*fi).V(j)->VFi();
00273                         (*fi).V(j)->VFp() = &(*fi);
00274                         (*fi).V(j)->VFi() = j;
00275                 }
00276         }
00277 }
00278 
00279 
00281 
00283 
00287 class PEdgeTex
00288 {
00289 public:
00290         
00291         typename FaceType::TexCoordType  v[2];          // the two Vertex pointer are ordered!
00292         FacePointer    f;                 // the face where this edge belong
00293         int      z;                                   // index in [0..2] of the edge of the face
00294 
00295   PEdgeTex() {}
00296 
00297 void Set( FacePointer  pf, const int nz )
00298 {
00299         assert(pf!=0);
00300         assert(nz>=0);
00301         assert(nz<3);
00302         
00303         v[0] = pf->WT(nz);
00304         v[1] = pf->WT(pf->Next(nz));
00305         assert(v[0] != v[1]); // The face pointed by 'f' is Degenerate (two coincident vertexes)
00306 
00307     if( v[1] < v[0] ) std::swap(v[0],v[1]);
00308         f    = pf;
00309         z    = nz;
00310 }
00311 
00312 inline bool operator <  ( const PEdgeTex & pe ) const
00313 {
00314         if( v[0]<pe.v[0] ) return true;
00315         else if( pe.v[0]<v[0] ) return false;
00316         else return v[1] < pe.v[1];
00317 }
00318 inline bool operator == ( const PEdgeTex & pe ) const
00319 {
00320         return (v[0]==pe.v[0]) && (v[1]==pe.v[1]);
00321 }
00322 inline bool operator != ( const PEdgeTex & pe ) const
00323 {
00324         return (v[0]!=pe.v[0]) || (v[1]!=pe.v[1]);
00325 }
00326 
00327 };
00328 
00329 
00331 
00336 static void FaceFaceFromTexCoord(MeshType &m)
00337 {
00338 //  assert(HasFFTopology(m));
00339         assert(HasPerWedgeTexCoord(m));
00340         
00341   std::vector<PEdgeTex> e;
00342         FaceIterator pf;
00343         typename std::vector<PEdgeTex>::iterator p;
00344 
00345         if( m.fn == 0 ) return;
00346 
00347 //      e.resize(m.fn*3);                                                               // Alloco il vettore ausiliario
00348         FaceIterator fi;
00349         int n_edges = 0;
00350         for(fi = m.face.begin(); fi != m.face.end(); ++fi) if(! (*fi).IsD()) n_edges+=(*fi).VN();
00351         e.resize(n_edges);
00352 
00353         p = e.begin();
00354         for(pf=m.face.begin();pf!=m.face.end();++pf)                    // Lo riempio con i dati delle facce
00355                 if( ! (*pf).IsD() )
00356                         for(int j=0;j<(*pf).VN();++j)
00357                         {
00358                                 if( (*pf).WT(j) != (*pf).WT((*pf).Next(j)))
00359                                          {
00360                                                 (*p).Set(&(*pf),j);
00361                                                 ++p;
00362                                          }
00363                         }
00364         
00365         e.resize(p-e.begin());   // remove from the end of the edge vector the unitiailized ones
00366         assert(p==e.end());
00367         sort(e.begin(), e.end());               
00368 
00369         int ne = 0;                                                                                     // number of real edges
00370         typename std::vector<PEdgeTex>::iterator pe,ps;
00371         ps = e.begin();pe=e.begin();
00372         //for(ps = e.begin(),pe=e.begin();pe<=e.end();++pe)     // Scansione vettore ausiliario
00373         do
00374         {
00375                 if( pe==e.end() || (*pe) != (*ps) )                                     // Trovo blocco di edge uguali
00376                 {
00377                         typename std::vector<PEdgeTex>::iterator q,q_next;
00378                         for (q=ps;q<pe-1;++q)                                           // Scansione facce associate
00379                         {
00380                                 assert((*q).z>=0);
00381                                 assert((*q).z< 3);
00382                                 q_next = q;
00383                                 ++q_next;
00384                                 assert((*q_next).z>=0);
00385                                 assert((*q_next).z< (*q_next).f->VN());
00386                                 (*q).f->FFp(q->z) = (*q_next).f;                                // Collegamento in lista delle facce
00387                                 (*q).f->FFi(q->z) = (*q_next).z;
00388                         }
00389                         assert((*q).z>=0);
00390                         assert((*q).z< (*q).f->VN());
00391                         (*q).f->FFp((*q).z) = ps->f;
00392                         (*q).f->FFi((*q).z) = ps->z;
00393                         ps = pe;
00394                         ++ne;                                                                           // Aggiorno il numero di edge
00395                 }
00396                 if(pe==e.end()) break;
00397                 ++pe;
00398         } while(true);
00399 }
00400 
00401 
00402 
00403 
00404 
00406 static void TestVertexFace(MeshType &m)
00407 {
00408         SimpleTempData<typename MeshType::VertContainer, int > numVertex(m.vert,0);
00409 
00410         if(!m.HasVFTopology()) return;          
00411         
00412         FaceIterator fi;
00413         for(fi=m.face.begin();fi!=m.face.end();++fi)
00414         {
00415                 if (!(*fi).IsD())
00416                 {
00417                         numVertex[(*fi).V0(0)]++;
00418                         numVertex[(*fi).V1(0)]++;
00419                         numVertex[(*fi).V2(0)]++;
00420                 }
00421         }
00422 
00423         VertexIterator vi;
00424         vcg::face::VFIterator<FaceType> VFi;
00425 
00426         for(vi=m.vert.begin();vi!=m.vert.end();++vi)
00427         {
00428                 if (!vi->IsD())
00429                 if(vi->VFp()!=0) // unreferenced vertices MUST have VF == 0;
00430                 {
00431                         int num=0;
00432                         assert(vi->VFp() >= &*m.face.begin());
00433                         assert(vi->VFp() <= &m.face.back());
00434                         VFi.f=vi->VFp();
00435                         VFi.z=vi->VFi();
00436                         while (!VFi.End())
00437                         {
00438                                 num++;
00439                                 assert(!VFi.F()->IsD());
00440                                 assert((VFi.F()->V(VFi.I()))==&(*vi));
00441                                 ++VFi;
00442                         }
00443                         int num1=numVertex[&(*vi)];
00444                         assert(num==num1);
00445                         /*assert(num>1);*/
00446                 }
00447         }
00448 }
00449 
00451 static void TestFaceFace(MeshType &m)
00452 {
00453         if(!m.HasFFTopology()) return;          
00454 
00455   for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
00456         {
00457     if (!fi->IsD())
00458                 {
00459       for (int i=0;i<(*fi).VN();i++)
00460                         {
00461         FaceType *ffpi=fi->FFp(i);
00462         int e=fi->FFi(i);
00463         //invariant property of FF topology for two manifold meshes
00464         assert(ffpi->FFp(e) == &(*fi));
00465         assert(ffpi->FFi(e) == i);
00466 
00467         // Test that the two faces shares the same edge
00468         // Vertices of the i-th edges of the first face
00469         VertexPointer v0i= fi->V0(i);
00470         VertexPointer v1i= fi->V1(i);
00471         // Vertices of the corresponding edge on the other face
00472         VertexPointer ffv0i= ffpi->V0(e);
00473         VertexPointer ffv1i= ffpi->V1(e);
00474 
00475         assert( (ffv0i==v0i) || (ffv0i==v1i) );
00476         assert( (ffv1i==v0i) || (ffv1i==v1i) );
00477                         }
00478                         
00479                 }
00480         }
00481 }
00482 
00483 }; // end class
00484 
00485 }       // End namespace
00486 }       // End namespace
00487 
00488 
00489 #endif