vcglib: halfedge_indexed.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 __VCGLIB_HALFEDGE_
00025 #define __VCGLIB_HALFEDGE_
00026 
00027 #include <vector>
00028 #include <vcg/complex/trimesh/allocate.h>
00029 #include <vcg/complex/trimesh/clean.h>
00030 #include <vcg/complex/trimesh/update/topology.h>
00031 #include <vcg/complex/trimesh/base.h>
00032 
00033 namespace vcg
00034 {
00035     namespace tri{
00037 
00039 
00041 
00045         template <class MeshType  >
00046                 class UpdateHalfEdges{
00047                 public:
00048             typedef typename MeshType::VertexType VertexType;
00049             typedef typename MeshType::VertexPointer VertexPointer;
00050             typedef typename MeshType::VertexIterator VertexIterator;
00051             typedef typename MeshType::HEdgePointer HEdgePointer;
00052             typedef typename MeshType::HEdgeType HEdgeType;
00053             typedef typename MeshType::EdgePointer EdgePointer;
00054             typedef typename MeshType::EdgeType EdgeType;
00055             typedef typename MeshType::EdgeIterator EdgeIterator;
00056             typedef typename MeshType::HEdgeIterator HEdgeIterator;
00057             typedef typename MeshType::FaceIterator FaceIterator;
00058             typedef typename MeshType::FaceType FaceType;
00059 
00060             struct VertexPairEdgePtr{
00061                 VertexPairEdgePtr(VertexPointer _v0,VertexPointer _v1,HEdgePointer _ep):v0(_v0),v1(_v1),ep(_ep){if(v0>v1) std::swap(v0,v1);}
00062                 const bool operator <(const VertexPairEdgePtr &o) const {return (v0 == o.v0)? (v1<o.v1):(v0<o.v0);}
00063                 const bool operator ==(const VertexPairEdgePtr &o) const {return (v0 == o.v0)&& (v1==o.v1);}
00064 
00065                 VertexPointer v0,v1;
00066                 HEdgePointer ep;
00067             };
00068             struct FacePtrInt{
00069                 FacePtrInt ( FaceType * _f,int _i):f(_f),i(_i){}
00070                 FaceType * f;
00071                 int i;
00072             };
00073 
00074             typedef std::vector<bool> BitVector;
00075 
00081             static void FromIndexed(MeshType & m){
00082                 assert(HasFVAdjacency(m));
00083                 assert(HasHOppAdjacency(m));
00084                 assert(HasHNextAdjacency(m));
00085                 assert(HasHEAdjacency(m));
00086 
00087                 typename MeshType::template PerFaceAttributeHandle<BitVector> flagVisited =
00088                         vcg::tri::Allocator<MeshType>::template AddPerFaceAttribute<BitVector>(m,"");
00089                 std::vector<FacePtrInt > borderEdges;
00090 
00091                 // allocate all new half edges
00092                 FaceIterator fi;
00093                 unsigned int n_edges = 0;
00094 
00095                 // count how many half edge to allocate
00096                 for(fi = m.face.begin(); fi != m.face.end(); ++fi) if(! (*fi).IsD())
00097                 {n_edges+=(*fi).VN();
00098                     for(int i = 0; i < (*fi).VN(); ++i)
00099                         if(vcg::face::IsBorder<FaceType>((*fi),(i)))
00100                             ++n_edges;
00101                 }
00102 
00103                 m.hedge.clear();
00104                 m.hn = 0;
00105 
00106                 // allocate the half edges
00107                 typename MeshType::HEdgeIterator ei = vcg::tri::Allocator<MeshType>::AddHEdges(m,n_edges);
00108 
00109 
00110                 std::vector<VertexPairEdgePtr> all;
00111                 int firstEdge = 0;
00112                 for(fi = m.face.begin(); fi != m.face.end(); ++fi)if(!(*fi).IsD()){
00113                     assert((*fi).VN()>2);
00114                     if(flagVisited[*fi].empty()) {flagVisited[*fi].resize((*fi).VN());}
00115 
00116                     for(int i  = 0; i < (*fi).VN(); ++i,++ei)
00117                     {
00118                         (*ei).HVp() = (*fi).V(i);
00119                         (*ei).HNp() = &m.hedge[firstEdge + (i +1) % (*fi).VN()];
00120                         if(MeshType::HEdgeType::HasHFAdjacency())
00121                             (*ei).HFp() = &(*fi);
00122                         if( MeshType::FaceType::HasFHAdjacency())
00123                             (*fi).FHp() = &(*ei);
00124                         if(MeshType::HEdgeType::HasHPrevAdjacency())
00125                             (*ei).HPp() = &m.hedge[firstEdge + (i +(*fi).VN()-1) % (*fi).VN()];
00126                         if(HasVHAdjacency(m))
00127                             (*ei).HVp()->VHp() = &(*ei);
00128                         all.push_back(VertexPairEdgePtr((*fi).V(i), (*fi).V((*fi).Next(i)),&(*ei)));// it will be used to link the hedges
00129 
00130                         if(  vcg::face::IsBorder<FaceType>((*fi),(i)))
00131                             borderEdges.push_back(FacePtrInt(&(*fi),i));
00132                     }
00133                     firstEdge += (*fi).VN();
00134                 }
00135 
00136                 // add all the border hedges
00137                 int borderLength;
00138                 typename std::vector<FacePtrInt >::iterator ebi;
00139                 for( ebi = borderEdges.begin(); ebi != borderEdges.end(); ++ebi)
00140                     if( !flagVisited[(*ebi).f][(*ebi).i])// not already inserted
00141                     {
00142 
00143                         borderLength = 0;
00144                         vcg::face::Pos<FaceType> bp((*ebi).f,(*ebi).i);
00145 
00146                         //FaceType * start = (*ebi).f;
00147                         VertexType * start = ((*ebi).f)->V((*ebi).i);
00148                         do{
00149                             all.push_back( VertexPairEdgePtr ( bp.f->V( bp.f->Next(bp.z) ),bp.f->V( bp.z ),&(*ei)));
00150                             (*ei).HVp() =  bp.f->V(bp.f->Next(bp.z)) ;
00151                             flagVisited[bp.f][bp.z] = true;
00152                             ++ei;
00153                             bp.NextB();
00154                             ++borderLength;
00155                         }while (bp.v != start);
00156                         //}while (bp.f != start);
00157 
00158 
00159                         // run over the border edges to link the adjacencies
00160                         for(int be = 0; be < borderLength; ++be)
00161                         {
00162                             if(MeshType::HEdgeType::HasHFAdjacency())
00163                                 m.hedge[firstEdge + be].HFp() = NULL;
00164 
00165                             if(MeshType::HEdgeType::HasHPrevAdjacency())
00166                                 m.hedge[firstEdge + be].HPp() = &m.hedge[firstEdge + (be +borderLength-1) % borderLength];
00167 
00168                             m.hedge[firstEdge + be].HNp() = &m.hedge[firstEdge + (be +1) % borderLength];
00169                         }
00170                         firstEdge+=borderLength;
00171                     }
00172 
00173                 vcg::tri::Allocator<MeshType>:: template DeletePerFaceAttribute<BitVector>(m,flagVisited );
00174 
00175                 std::sort(all.begin(),all.end());
00176                 assert(all.size() == n_edges);
00177 
00178                 for(unsigned int i = 0 ; i < all.size(); )
00179                     if(all[i]  == all[i+1])
00180                     {
00181                         all[i].ep->HOp()        = all[i+1].ep;
00182                         all[i+1].ep->HOp() = all[i].ep;
00183                         i+=2;
00184                     }
00185                     else
00186                     {
00187                         all[i].ep->HOp() = all[i].ep;
00188                         i+=1;
00189                     }
00190 
00191                 if(HasEHAdjacency(m) && HasHEAdjacency(m))
00192                 {
00193                     assert(m.edge.size() == 0 || m.edge.size() == n_edges/2);
00194 
00195                     if ( m.edge.size() == 0 )
00196                     {
00197                         m.en = 0;
00198                         // allocate the edges
00199                         typename MeshType::EdgeIterator edge_i = vcg::tri::Allocator<MeshType>::AddEdges(m,n_edges/2);
00200 
00201                         for(ei = m.hedge.begin(); ei != m.hedge.end(); ++ei)
00202                         {
00203                             if((*ei).HEp() == NULL)
00204                             {
00205                                                                 (*ei).HEp() = &(*edge_i);
00206                                 (*ei).HOp()->HEp() = &(*edge_i);
00207 
00208                                 (*edge_i).EHp() = &(*ei);
00209 
00210                                 ++edge_i;
00211                             }
00212                         }
00213 
00214                     }
00215                     else
00216                     {
00217                         assert(HasEVAdjacency(m));
00218 
00219                         //update edge relations
00220                         typename MeshType::EdgeIterator ei1;
00221                         for( ei1 = m.edge.begin(); ei1 != m.edge.end(); ++ei1 )
00222                             for( ei = m.hedge.begin(); ei != m.hedge.end(); ++ei )
00223                                 if ( ((*ei).HVp() == (*ei1).V(0))  && ((*ei).HOp()->HVp() == (*ei1).V(1)) )
00224                                 {
00225                             // EH
00226                             (*ei1).EHp() = &(*ei);
00227 
00228                             // HE
00229                             (*ei).HEp() = &(*ei1);
00230                             (*ei).HOp()->HEp() = &(*ei1);
00231 
00232                             break;
00233                         }
00234                     }
00235 
00236                 }
00237 
00238 
00239 
00240             }
00241 
00245             static bool CheckConsistency_FHp(MeshType &  m){
00246                 assert(MeshType::FaceType::HasFHAdjacency());
00247                 FaceIterator fi;
00248                 for(fi = m.face.begin(); fi != m.face.end(); ++fi)
00249                     if(!(*fi).IsD()){
00250                     if((*fi).FHp() <  &(*m.hedge.begin())) return false;
00251                     if((*fi).FHp() >  &(m.hedge.back())) return false;
00252                 }
00253                 return true;
00254             }
00255 
00259             static bool CheckConsistency(MeshType & m){
00260                 assert(MeshType::HEdgeType::HasHNextAdjacency());
00261                 assert(MeshType::HEdgeType::HasHOppAdjacency());
00262                 assert(MeshType::HEdgeType::HasHVAdjacency());
00263                 assert(MeshType::HEdgeType::HasHEAdjacency());
00264                 assert(MeshType::FaceType::HasFHAdjacency());
00265 
00266                 //bool hasHEF = ( MeshType::HEdgeType::HasHFAdjacency());
00267                 bool hasHP = ( MeshType::HEdgeType::HasHPrevAdjacency());
00268 
00269                 FaceIterator fi;
00270                 HEdgePointer ep,ep1;
00271                 int cnt = 0;
00272 
00273                 if( MeshType::HEdgeType::HasHFAdjacency() )
00274                 {
00275                     int iDb = 0;
00276                     for(fi = m.face.begin(); fi != m.face.end(); ++fi,++iDb)
00277                         if(!(*fi).IsD())
00278                         {
00279                         ep = ep1 = (*fi).FHp();
00280 
00281                         do{
00282                             if(ep->IsD())
00283                                 return false; // the hedge should not be connected, it has been deleted
00284                             if( ! ep->HFp())
00285                                 return false;
00286                             if(ep->HFp() != &(*fi))
00287                                 return false;// hedge is not pointing to the rigth face
00288                             ep = ep->HNp();
00289                             if(cnt++ > m.hn)
00290                                 return false; // hedges are ill connected (HENp())
00291 
00292                         }while(ep!=ep1);
00293 
00294                     }
00295                 }
00296 
00297                 HEdgePointer epPrev;
00298                 HEdgeIterator hi;
00299                 //bool extEdge ;
00300                 for( hi  = m.hedge.begin(); hi != m.hedge.end(); ++hi)
00301                     if(!(*hi).IsD())
00302                     {
00303                         //cnt = 0;
00304                         epPrev = ep = ep1 = &(*hi);
00305                         //do{
00306                         //extEdge = (ep->HFp()==NULL);
00307                         if(hasHP)
00308                         {
00309                             if( !ep->HPp())
00310                                 return false;
00311                             if( ep->HPp() == ep)
00312                                 return false; // the previous of an edge cannot be the edge itself
00313                             if( ep->HNp()->HPp() != ep)
00314                                 return false; // next and prev relation are not mutual
00315                             if( ep->HPp()->IsD())
00316                                 return false; //
00317                         }
00318 
00319                         if( ! ep->HOp() )
00320                             return false;
00321 
00322                         if( ep->HOp()  == ep)
00323                             return false; // opposite relation is not mutual
00324 
00325                         if( ep->HOp()->IsD())
00326                             return false;
00327 
00328                         if( ep->HOp()->HOp() != ep)
00329                             return false; // opposite relation is not mutual
00330 
00331                         if( HasHFAdjacency(m) )
00332                         {
00333                             if(ep->HFp())
00334                             {
00335                                 if( ep->HFp()->IsD())
00336                                     return false; // pointed face must not be deleted
00337                             }
00338                         }
00339 
00340                                                                                                 if( HasHEAdjacency(m) && (m.en!=0))
00341                         {
00342                             if( ! ep->HEp())
00343                                 return false; //halfedge must point to an edge
00344 
00345                             if( ep->HEp()->IsD())
00346                                 return false; // pointed edge must not be deleted
00347 
00348                             if(ep->HEp() != ep->HOp()->HEp())
00349                                 return false;   // he and opposite he must point to the same edge
00350 
00351                             if(ep->HEp()->EHp() != ep && ep->HEp()->EHp() != ep->HOp() )
00352                                 return false;   // halfedge points to an edge not pointing it or its opposite
00353 
00354                         }
00355 
00356 
00357                         if( !ep->HNp() )
00358                             return false;
00359 
00360                         if( ep->HNp() == ep )
00361                             return false; //  the next of an hedge cannot be the hedge itself
00362 
00363                         if( ep->HNp()->IsD())
00364                             return false; //
00365 
00366                                                                                                 if(hasHP)
00367                         if( ep->HNp()->HPp() != ep)
00368                             return false; //
00369 
00370                         if( HasHVAdjacency(m) )
00371                         {
00372                             if( ! ep->HVp() )
00373                                 return false; // halfedge must point to a vertex
00374 
00375                             if( ep->HVp()->IsD() )
00376                                 return false; // pointed vertex must not be deleted
00377 
00378                             if( HasVHAdjacency(m) )
00379                                 if( ! (ep->HVp()->VHp()) )
00380                                     return false; //  halfedge points to a vertex pointing NULL
00381 
00382                         }
00383 
00384 
00385                         ep = ep->HNp();
00386                         if( ep->HVp() != epPrev->HOp()->HVp())
00387                             return false;
00388 
00389                         epPrev = ep;
00390 
00391                         // if(cnt++ > m.hn)
00392                         //     return false; // edges are ill connected (HENp())
00393 
00394                         //}while(ep!=ep1);
00395                     }
00396 
00397                 if(HasEHAdjacency(m))
00398                     for(EdgeIterator ei  = m.edge.begin(); ei != m.edge.end(); ++ei)
00399                     {
00400                         if(!(*ei).IsD())
00401                         {
00402                             if( !(*ei).EHp())
00403                                 return false;   //edge must have a valid pointer to his halfedge
00404 
00405                             if( (*ei).EHp()->HEp() !=  &(*ei) )
00406                                 return false; // edge's halfedge must point to the edge itself
00407 
00408                             if( (*ei).EHp()->IsD())
00409                                 return false;
00410                         }
00411                     }
00412 
00413                 if(HasVHAdjacency(m))
00414                     for(VertexIterator vi  = m.vert.begin(); vi != m.vert.end(); ++vi)
00415                     {
00416                         if( !(*vi).IsD() )
00417                             if( (*vi).VHp() )
00418                             {
00419                                 if( (*vi).VHp()->HVp() !=  &(*vi) )
00420                                     return false;
00421                                 if( (*vi).VHp()->IsD())
00422                                     return false;
00423                             }
00424                     }
00425 
00426 
00427                 return true;
00428             }
00429 
00432         private:
00433             static void SetRelationsLoopFace(HEdgeType * e0, FaceType * f){
00434                 assert(HEdgeType::HasHNextAdjacency());
00435                 assert(FaceType::HasFHAdjacency());
00436 
00437                 HEdgeType *e = e0;
00438                 assert(e!=NULL);
00439                 do{ e->HFp() = f; e = e->HNp(); } while(e != e0);
00440                 f->FHp() = e0;
00441             }
00442 
00446             static void MergeFaces(FaceType *, FaceType *){}
00447 
00451             static HEdgeType *  PreviousEdge(HEdgeType * e0){
00452                 HEdgeType *  ep = e0;
00453                 do{
00454                     if(ep->HNp() == e0) return ep;
00455                     ep = ep->HNp();
00456                 }while(ep!=e0);
00457                 assert(0); // degenerate loop
00458                 return 0;
00459             }
00460 
00461         public:
00472             static void AddHEdge(MeshType &m, HEdgeType * e0, HEdgeType * e1){
00473                 HEdgeType *iii =e0->HNp();
00474                 assert(e1!=e0->HNp());
00475                 assert(e0!=e1->HNp());
00476                 HEdgePointer tmp;
00477                 bool hasP =  MeshType::HEdgeType::HasHPrevAdjacency();
00478                 assert(e0->HOp() != e1); // the hedge already exists
00479                 assert(e0!=e1->HNp());
00480 
00481                 std::vector<typename MeshType::HEdgePointer* > toUpdate;
00482                 toUpdate.push_back(&e0);
00483                 toUpdate.push_back(&e1);
00484                 HEdgeIterator ei0  = vcg::tri::Allocator<MeshType>::AddHEdges(m,2,toUpdate);
00485 
00486                 HEdgeIterator ei1 = ei0; ++ei1;
00487                 (*ei0).HNp() = e1;(*ei0).HVp() = e0->HVp();
00488                 (*ei1).HNp() = e0;(*ei1).HVp() = e1->HVp();
00489 
00490                 HEdgePointer e0_HEPp = 0,e1_HEPp = 0,ep =0;
00491                 if(hasP){
00492                     e0_HEPp = e0->HPp();
00493                     e1_HEPp = e1->HPp();
00494                 }else{// does not have pointer to previous, it must be computed
00495                     ep = e0;
00496                     do{
00497                         if(ep->HNp() == e0) e0_HEPp = ep;
00498                         if(ep->HNp() == e1) e1_HEPp = ep;
00499                         ep = ep->HNp();
00500                     }while(ep!=e0);
00501                 }
00502                 if(hasP){
00503                     (*ei0).HPp() = e0->HPp();
00504                     (*ei1).HPp() = e1->HPp();
00505                     e0->HPp() = &(*ei1);
00506                     e1->HPp() = &(*ei0);
00507                 }
00508                 e0_HEPp -> HNp() = &(*ei0);
00509                 e1_HEPp -> HNp() = &(*ei1);
00510 
00511                 (*ei0).HOp() = &(*ei1);
00512                 (*ei1).HOp() = &(*ei0);
00513 
00514 
00515                 if( HEdgeType::HasHFAdjacency() && FaceType::HasFHAdjacency()){
00516                     FaceIterator fi0  = vcg::tri::Allocator<MeshType>::AddFaces(m,1);
00517                     m.face.back().ImportLocal(*e0->HFp());
00518 
00519                     SetRelationsLoopFace(&(*ei0),e1->HFp());            // one loop to the old face
00520                     SetRelationsLoopFace(&(*ei1),&m.face.back());       // the other  to the new face
00521                 }
00522             }
00523 
00534             static void RemoveHEdge(MeshType &m, HEdgeType * e){
00535                 assert(MeshType::HEdgeType::HasHNextAdjacency());
00536                 assert(MeshType::HEdgeType::HasHOppAdjacency());
00537                 assert(MeshType::FaceType::HasFHAdjacency());
00538 
00539                 bool hasP =  MeshType::HEdgeType::HasHPrevAdjacency();
00540                 HEdgePointer e_HEPp,eO_HEPp;
00541 
00542                 if(hasP){
00543                     e_HEPp = e->HPp();
00544                     eO_HEPp = e->HOp()->HPp();
00545                 }else{
00546                     e_HEPp = PreviousEdge(e);
00547                     eO_HEPp = PreviousEdge(e->HOp());
00548                 }
00549 
00550                 assert(e_HEPp->HNp() == e);
00551                 assert(eO_HEPp->HNp() == e->HOp());
00552                 e_HEPp->HNp() = e->HOp()->HNp();
00553                 eO_HEPp->HNp() = e-> HNp();
00554 
00555                 if(hasP) {
00556                     e->HOp()->HNp()->HPp() = e_HEPp;
00557                     e->HNp()->HPp() = eO_HEPp;
00558 
00559                     e->HPp() = NULL;
00560                     e-> HOp()->HPp() = NULL;
00561                 }
00562 
00563 
00564                 // take care of the faces
00565                 if(MeshType::HEdgeType::HasHFAdjacency()){
00566                     MergeFaces(e_HEPp->HFp(),eO_HEPp->HFp());
00567                     vcg::tri::Allocator<MeshType>::DeleteFace(m,*eO_HEPp->HFp());
00568                     SetRelationsLoopFace(e_HEPp,e_HEPp->HFp());
00569 
00570                 }
00571                 vcg::tri::Allocator<MeshType>::DeleteHEdge(m,*e->HOp());
00572                 vcg::tri::Allocator<MeshType>::DeleteHEdge(m,*e);
00573 
00574             }
00575 
00576         };// end class
00577         template <class MeshType  >
00578                 struct UpdateIndexed{
00579             typedef typename MeshType::VertexType VertexType;
00580             typedef typename MeshType::VertexPointer VertexPointer;
00581             typedef typename MeshType::HEdgePointer HEdgePointer;
00582             typedef typename MeshType::HEdgeType HEdgeType;
00583             typedef typename MeshType::HEdgeIterator HEdgeIterator;
00584             typedef typename MeshType::FaceIterator FaceIterator;
00585             typedef typename MeshType::FaceType FaceType;
00586 
00587             struct VertexPairEdgePtr{
00588                 VertexPairEdgePtr(VertexPointer _v0,VertexPointer _v1,HEdgePointer _ep):v0(_v0),v1(_v1),ep(_ep){if(v0>v1) std::swap(v0,v1);}
00589                 const bool operator <(const VertexPairEdgePtr &o) const {return (v0 == o.v0)? (v1<o.v1):(v0<o.v0);}
00590                 const bool operator ==(const VertexPairEdgePtr &o) const {return (v0 == o.v0)&& (v1==o.v1);}
00591 
00592                 VertexPointer v0,v1;
00593                 HEdgePointer ep;
00594             };
00595 
00602             static void FromHalfEdges(  MeshType & m ){
00603                 assert(HasFVAdjacency(m));
00604                 assert(MeshType::HEdgeType::HasHNextAdjacency());
00605                 assert(MeshType::HEdgeType::HasHVAdjacency());
00606                 assert(MeshType::HEdgeType::HasHOppAdjacency());
00607                 assert(MeshType::FaceType::HasFHAdjacency());
00608                 bool hasHEF;
00609                 //bool createFace,hasHEF,hasFHE;
00610 
00611                 //                              typename MeshType::template PerHEdgeAttributeHandle<bool> hV = Allocator<MeshType>::template AddPerHEdgeAttribute<bool>(m,"");
00612 
00613 
00614                 typename MeshType::HEdgeIterator ei;
00615                 typename MeshType::FacePointer fp;
00616                 typename MeshType::FaceIterator fi;
00617                 typename MeshType::HEdgePointer ep,epF;
00618                 //int vi = 0;
00619                 vcg::SimpleTempData<typename MeshType::HEdgeContainer,bool> hV(m.hedge);
00620 
00621                 hasHEF = (MeshType::HEdgeType::HasHFAdjacency());
00622                 assert( !hasHEF || (hasHEF && m.fn>0));
00623 
00624                 // if the edgetype has the pointer to face
00625                 // it is assumed the the edget2face pointer (HEFp) are correct
00626                 // and the faces are allocated
00627                 for ( ei = m.hedge.begin(); ei != m.hedge.end(); ++ei)
00628                     if(!(*ei).IsD())                                                            // it has not been deleted
00629                         if(!hasHEF || ( hasHEF &&  (*ei).HFp()!=NULL))  // if it has a pointer to the face it is
00630                             // not null (i.e. it is not a border edge)
00631                             if(!hV[(*ei)] )                                                                     // it has not be visited yet
00632                             {
00633                     if(!hasHEF)// if it has
00634                         fp = &(* Allocator<MeshType>::AddFaces(m,1));
00635                     else
00636                         fp = (*ei).HFp();
00637 
00638                     ep = epF = &(*ei);
00639                     std::vector<VertexPointer> vpts;
00640                     do{vpts.push_back((*ep).HVp()); ep=ep->HNp();}while(ep!=epF);
00641                     //int idbg  =fp->VN();
00642                     if(fp->VN() != vpts.size()){
00643                         fp->Dealloc();
00644                         fp ->Alloc(vpts.size());
00645                     }
00646                     //int idbg1  =fp->VN();
00647                     for(unsigned int i  = 0; i < vpts.size();++i) fp ->V(i) = vpts[i];// set the pointer from face to vertex
00648 
00649                     hV[(*ei)] = true;
00650                 }
00651                 //Allocator<MeshType>::DeletePerHEdgeAttribute(m,hV);
00652             }
00653 
00654         };
00655     } // end namespace vcg
00656 }
00657 #endif // __VCGLIB_EDGE_SUPPORT