vcglib: halfedge_topology.h Source File

00001 #ifndef VCG_HEDGE_TOPOLOGY
00002 #define VCG_HEDGE_TOPOLOGY
00003 
00004 #include <vcg/connectors/halfedge_pos.h>
00005 #include <vcg/complex/trimesh/allocate.h>
00006 
00007 #include <vector>
00008 #include <algorithm>
00009 
00010 using namespace std;
00011 using namespace vcg::hedge;
00012 using namespace vcg::tri;
00013 
00014 namespace vcg
00015 {
00016     namespace tri
00017     {
00022         template <class MeshType> class HalfEdgeTopology
00023         {
00024             public:
00025 
00026                 typedef typename MeshType::VertexPointer VertexPointer;
00027                 typedef typename MeshType::EdgePointer EdgePointer;
00028                 typedef typename MeshType::HEdgePointer HEdgePointer;
00029                 typedef typename MeshType::FacePointer FacePointer;
00030 
00031                 typedef typename MeshType::VertexIterator VertexIterator;
00032                 typedef typename MeshType::EdgeIterator EdgeIterator;
00033                 typedef typename MeshType::HEdgeIterator HEdgeIterator;
00034                 typedef typename MeshType::FaceIterator FaceIterator;
00035 
00046                 static VertexPointer edge_collapse_quad(MeshType &m, EdgePointer ep, VertexPointer vp)
00047                 {
00048                     assert(vp);
00049                     assert(ep);
00050                     assert(MeshType::EdgeType::HasEHAdjacency());
00051                     assert(MeshType::HEdgeType::HasHEAdjacency());
00052                     assert(MeshType::HEdgeType::HasHVAdjacency());
00053                     assert(ep->EHp()->HVp() == vp || ep->EHp()->HOp()->HVp() == vp);
00054                     assert(ep->EHp()->HFp()->VN() == 4);
00055                     assert(ep->EHp()->HOp()->HFp()->VN() == 4);
00056 
00057                     VertexPointer vp_opp = ep->EHp()->HOp()->HVp();
00058 
00059                     VertexPointer vp_rot = vertex_rotate( m, vp );
00060 
00061                     assert(vp_rot == vp);
00062 
00063                     FacePointer fp;
00064 
00065                     //retrieve right face
00066                     Pos<MeshType> p(vp->VHp(),true);
00067 
00068                     while(p.HE()->HNp->HOp()->HVp() != vp_opp)
00069                     {
00070                         p.FlipE();
00071                         p.FlipF();
00072                     }
00073 
00074                     fp = p.F();
00075 
00076 
00077                     return diagonal_collapse( m, fp, vp );
00078 
00079                 }
00080 
00091                 static VertexPointer diagonal_collapse(MeshType &m, FacePointer fp, VertexPointer vp)
00092                 {
00093 
00094                     assert(MeshType::VertexType::HasVHAdjacency());
00095                     assert(MeshType::EdgeType::HasEHAdjacency());
00096                     assert(MeshType::FaceType::HasFHAdjacency());
00097                     assert(MeshType::HEdgeType::HasHVAdjacency());
00098                     assert(MeshType::HEdgeType::HasHEAdjacency());
00099                     assert(MeshType::HEdgeType::HasHFAdjacency());
00100                     assert(MeshType::HEdgeType::HasHOppAdjacency());
00101                     assert(MeshType::HEdgeType::HasHPrevAdjacency());
00102 
00103                     assert(fp);
00104                     assert(fp->FHp());
00105                     assert(fp->VN() == 4);
00106 
00107                     if( !can_remove_face(fp) )
00108                         return NULL;
00109 
00110                     HEdgePointer hp;
00111 
00112                     vector<VertexPointer> vps = getVertices(fp);
00113                     VertexPointer opp_vert = NULL;
00114 
00115                     for(unsigned int i = 0; i< vps.size(); i++)
00116                         if(vps[i] == vp)
00117                             opp_vert = vps[(i+2)%vps.size()];
00118 
00119                     assert(opp_vert);
00120 
00121                     if( fp->FHp()->HVp() == vp || fp->FHp()->HVp() == opp_vert)
00122                         hp = fp->FHp();
00123                     else
00124                         hp = fp->FHp()->HNp();
00125 
00126                     vector<HEdgePointer> hps = getHEdges(fp,hp);
00127 
00128                     int edge_cnt = 0;
00129 
00130                     if(hps[0]->HOp()->HFp() || hps[1]->HOp()->HFp())
00131                         edge_cnt++;
00132                     if(hps[2]->HOp()->HFp() || hps[3]->HOp()->HFp())
00133                         edge_cnt++;
00134 
00135                     VertexIterator vi;
00136 
00137                     if(edge_cnt > 0)
00138                     {
00139                         typename Allocator<MeshType>::template PointerUpdater<VertexPointer> puv;
00140 
00141                         if(m.vert.empty())
00142                             puv.oldBase = 0;
00143                         else
00144                         {
00145                             puv.oldBase = &*(m.vert.begin());
00146                             puv.oldEnd = &m.vert.back()+1;
00147                         }
00148 
00149                         vi = Allocator<MeshType>::AddVertices(m,1);
00150 
00151                         EdgeIterator ei = Allocator<MeshType>::AddEdges(m,edge_cnt);
00152 
00153                         puv.newBase = &*(m.vert.begin());
00154                         puv.newEnd = &m.vert.back()+1;
00155 
00156                         if( puv.NeedUpdate() )
00157                         {
00158                             puv.Update(vp);
00159                             puv.Update(opp_vert);
00160                             for(typename vector<VertexPointer>::iterator vpi = vps.begin(); vpi != vps.end(); ++vpi)
00161                                 puv.Update(*vpi);
00162                         }
00163 
00164                         typename Allocator<MeshType>::template PointerUpdater<HEdgePointer> puh;
00165 
00166                         if(m.hedge.empty())
00167                             puh.oldBase = 0;
00168                         else
00169                         {
00170                             puh.oldBase = &*(m.hedge.begin());
00171                             puh.oldEnd = &m.hedge.back()+1;
00172                         }
00173 
00174                         HEdgeIterator hi = Allocator<MeshType>::AddHEdges(m,2*edge_cnt);
00175 
00176                         puh.newBase = &*(m.hedge.begin());
00177                         puh.newEnd = &m.hedge.back()+1;
00178 
00179                         if( puh.NeedUpdate() )
00180                             for(typename vector<HEdgePointer>::iterator hpi = hps.begin(); hpi != hps.end(); ++hpi)
00181                                     puh.Update(*hpi);
00182 
00183 
00184 
00185                         HEdgeIterator hi1 = hi;
00186                         HEdgeIterator hi2 = hi;
00187                         ++hi2;
00188 
00189                         (*vi).VHp() = &(*hi1);
00190 
00191                         change_vertex( hps[0]->HVp(), &(*vi));
00192                         change_vertex( hps[2]->HVp(), &(*vi));
00193 
00194                         for( int count = 0; count < 2; count++ )
00195                         {
00196 
00197                             int i = 2*count;
00198 
00199                             FacePointer fp1 = hps[i+1]->HOp()->HFp();
00200                             FacePointer fp2 = hps[i]->HOp()->HFp();
00201 
00202                             if( fp1 || fp2 )
00203                             {
00204 
00205                                 // HOp
00206                                 (*hi1).HOp() = &(*hi2);
00207                                 (*hi2).HOp() = &(*hi1);
00208 
00209                                 // EH
00210                                 (*ei).EHp() = &(*hi1);
00211 
00212                                 // HE
00213                                 (*hi1).HEp() = &(*ei);
00214                                 (*hi2).HEp() = &(*ei);
00215 
00216                                 // HV
00217                                 (*hi1).HVp() = &(*vi);
00218                                 (*hi2).HVp() = hps[i+1]->HVp();
00219 
00220                                 // FH
00221                                 if( fp1 && ( fp1->FHp() == hps[i+1]->HOp() ) )
00222                                     fp1->FHp() = &(*hi1);
00223 
00224                                 if( fp2 && ( fp2->FHp() == hps[i]->HOp() ) )
00225                                     fp2->FHp() = &(*hi2);
00226 
00227                                 //HF
00228                                 (*hi1).HFp() = fp1;
00229                                 (*hi2).HFp() = fp2;
00230 
00231                                 //HNp
00232                                 (*hi1).HNp() = hps[i+1]->HOp()->HNp();
00233                                 (*hi2).HNp() = hps[i]->HOp()->HNp();
00234 
00235                                 (*hi1).HNp()->HPp() = &(*hi1);
00236                                 (*hi2).HNp()->HPp() = &(*hi2);
00237 
00238                                 //HPp
00239                                 (*hi1).HPp() = hps[i+1]->HOp()->HPp();
00240                                 (*hi2).HPp() = hps[i]->HOp()->HPp();
00241 
00242                                 (*hi1).HPp()->HNp() = &(*hi1);
00243                                 (*hi2).HPp()->HNp() = &(*hi2);
00244 
00245                                 //VH
00246                                 VertexPointer tmp = hps[i+1]->HVp();
00247                                 if( tmp->VHp() == hps[i+1] ||  tmp->VHp() == hps[i]->HOp() )
00248                                     tmp->VHp() = &(*hi2);
00249 
00250                                 ++ei;
00251 
00252                                 ++hi1;
00253                                 ++hi1;
00254 
00255                                 ++hi2;
00256                                 ++hi2;
00257 
00258                             }
00259                             else
00260                             {
00261                                 hps[i+1]->HOp()->HPp()->HNp() = hps[i]->HOp()->HNp();
00262                                 hps[i]->HOp()->HNp()->HPp() = hps[i+1]->HOp()->HPp();
00263 
00264                                 hps[i+1]->HVp()->VHp() = NULL;
00265                             }
00266 
00267 
00268                         }
00269 
00270                     }
00271 
00272 
00273                     Allocator<MeshType>::DeleteFace(m, *(fp) );
00274                     Allocator<MeshType>::DeleteVertex(m, *(vp) );
00275                     Allocator<MeshType>::DeleteVertex(m, *(opp_vert) );
00276 
00277                     for(typename vector<HEdgePointer>::iterator hpi = hps.begin(); hpi != hps.end(); ++hpi)
00278                     {
00279                         if(! (*hpi)->HEp()->IsD() )
00280                             Allocator<MeshType>::DeleteEdge(m, *((*hpi)->HEp()) );
00281 
00282                         if(! (*hpi)->IsD())
00283                         {
00284                             Allocator<MeshType>::DeleteHEdge(m, *(*hpi) );
00285                             Allocator<MeshType>::DeleteHEdge(m, *((*hpi)->HOp()) );
00286                         }
00287                     }
00288 
00289                     if(edge_cnt > 0)
00290                         return &(*vi);
00291 
00292                     for(typename vector<VertexPointer>::iterator vpi = vps.begin(); vpi != vps.end(); ++vpi)
00293                         if(!(*vpi)->IsD())
00294                             Allocator<MeshType>::DeleteVertex(m, *(*vpi) );
00295 
00296                     return NULL;
00297                 }
00298 
00307                 static FacePointer doublet_remove(MeshType &m, VertexPointer vp)
00308                 {
00309                     assert(vp);
00310 
00311                     HEdgePointer hp = vp->VHp();
00312 
00313                     assert(hp);
00314 
00315                     FacePointer fp1 = hp->HFp();
00316                     FacePointer fp2 = hp->HOp()->HFp();
00317 
00318                     // check if face is a doublet
00319 
00320                     assert( fp1 );
00321                     assert( fp1 == hp->HPp()->HFp() );
00322 
00323                     assert( fp2 );
00324                     assert( fp2 == hp->HOp()->HNp()->HFp() );
00325 
00326                     assert( hp->HOp()->HNp()->HOp() == hp->HPp() );
00327 
00328                     assert( fp1->VN() == 4);
00329                     assert( fp2->VN() == 4);
00330 
00331                     // end of check
00332 
00333                     vector<VertexPointer> vert_face1 = getVertices(fp1, hp);
00334                     vector<VertexPointer> vert_face2 = getVertices(fp2, hp->HOp()->HNp());
00335 
00336                     remove_face_unsafe(m, fp1 );
00337                     remove_face_unsafe(m, fp2 );
00338 
00339                     Allocator<MeshType>::DeleteVertex(m, *vp);
00340 
00341 
00342                     vector<VertexPointer> new_face_vert;
00343 
00344                     new_face_vert.push_back( vert_face1[1] );
00345                     new_face_vert.push_back( vert_face1[2] );
00346                     new_face_vert.push_back( vert_face1[3] );
00347                     new_face_vert.push_back( vert_face2[2] );
00348 
00349                     return add_face_unsafe(m, new_face_vert );
00350 
00351                 }
00352 
00361                 static EdgePointer singlet_remove(MeshType &m, VertexPointer vp)
00362                 {
00363                     assert( vp );
00364 
00365                     HEdgePointer hp = vp->VHp();
00366                     assert( hp );
00367 
00368                     FacePointer fp1 = hp->HFp();
00369                     FacePointer fp2 = hp->HOp()->HFp();
00370 
00371                     assert( fp1 && fp2 && fp1 == fp2 ); // the faces pointed by the halfedges must be the same
00372 
00373                     HEdgePointer hp1 = hp->HNp()->HOp();
00374                     HEdgePointer hp2 = hp->HNp()->HNp()->HOp();
00375 
00376                     // pointers to the near faces
00377                     FacePointer fp3 = hp1->HFp();
00378                     FacePointer fp4 = hp2->HFp();
00379 
00380                     Allocator<MeshType>::DeleteFace( m, *fp1 );
00381 
00382                     Allocator<MeshType>::DeleteEdge( m, *(hp->HEp()) );
00383 
00384                     Allocator<MeshType>::DeleteHEdge( m, *hp );
00385                     Allocator<MeshType>::DeleteHEdge( m, *(hp->HOp()) );
00386 
00387                     Allocator<MeshType>::DeleteVertex(m, *(vp) );
00388 
00389                     Allocator<MeshType>::DeleteEdge(m, *(hp1->HEp()) );
00390                     Allocator<MeshType>::DeleteEdge(m, *(hp2->HEp()) );
00391 
00392                     Allocator<MeshType>::DeleteHEdge( m, *(hp1->HOp()) );
00393                     Allocator<MeshType>::DeleteHEdge( m, *(hp2->HOp()) );
00394 
00395                     if(!fp3 && !fp4) // there are no faces, nothing has to be created
00396                     {
00397                         Allocator<MeshType>::DeleteHEdge( m, *hp1 );
00398                         Allocator<MeshType>::DeleteHEdge( m, *hp2 );
00399 
00400                         return NULL;
00401                     }
00402 
00403                     EdgeIterator ei = Allocator<MeshType>::AddEdges(m,1);
00404 
00405                     (*ei).EHp() = hp1;
00406 
00407                     hp1->HEp() = &(*ei);
00408                     hp2->HEp() = &(*ei);
00409 
00410                     hp1->HOp() = hp2;
00411                     hp2->HOp() = hp1;
00412 
00413                     return &(*ei);
00414 
00415                 }
00416 
00426                 static EdgePointer edge_rotate(MeshType &m, EdgePointer ep, bool cw)
00427                 {
00428                     assert( MeshType::EdgeType::HasEHAdjacency() );
00429                     assert( MeshType::HEdgeType::HasHFAdjacency() );
00430                     assert( MeshType::HEdgeType::HasHOppAdjacency() );
00431                     assert( MeshType::FaceType::HasFHAdjacency() );
00432 
00433                     assert( ep->EHp()->HFp() );
00434 
00435                     assert( ep->EHp()->HFp()->VN() == 4 );
00436 
00437                     assert( ep->EHp()->HOp()->HFp() );
00438                     assert( ep->EHp()->HOp()->HFp()->VN() == 4 );
00439 
00440                     FacePointer fp1 = ep->EHp()->HFp();
00441                     FacePointer fp2 = ep->EHp()->HOp()->HFp();
00442 
00443                     vector<VertexPointer> old_face1 = getVertices( fp1, ep->EHp() );
00444                     vector<VertexPointer> old_face2 = getVertices( fp2, ep->EHp()->HOp() );
00445 
00446                     remove_face_unsafe(m, fp1);
00447                     remove_face_unsafe(m, fp2);
00448 
00449                     vector<VertexPointer> new_face1;
00450                     vector<VertexPointer> new_face2;
00451 
00452                     if(cw)
00453                     {
00454                         new_face1.push_back( old_face1[3] );
00455                         new_face1.push_back( old_face2[3] );
00456                         new_face1.push_back( old_face1[1] );
00457                         new_face1.push_back( old_face1[2] );
00458 
00459                         new_face2.push_back( old_face2[3] );
00460                         new_face2.push_back( old_face1[3] );
00461                         new_face2.push_back( old_face2[1] );
00462                         new_face2.push_back( old_face2[2] );
00463 
00464                     }
00465                     else
00466                     {
00467                         new_face1.push_back( old_face1[2] );
00468                         new_face1.push_back( old_face1[3] );
00469                         new_face1.push_back( old_face1[0] );
00470                         new_face1.push_back( old_face2[2] );
00471 
00472                         new_face2.push_back( old_face2[2] );
00473                         new_face2.push_back( old_face2[3] );
00474                         new_face2.push_back( old_face2[0] );
00475                         new_face2.push_back( old_face1[2] );
00476                     }
00477 
00478                     fp1 = add_face_unsafe(m, new_face1);
00479                     fp2 = add_face_unsafe(m, new_face2);
00480 
00481 
00482                     // retrieve inserted edge
00483                     Pos<MeshType> p1( fp1->FHp(), true);
00484 
00485                     while( p1.HE()->HOp()->HFp() != fp2 )
00486                     {
00487                         p1.FlipV();
00488                         p1.FlipE();
00489                     }
00490 
00491                     return p1.E();
00492 
00493                 }
00494 
00503                 static VertexPointer vertex_rotate(MeshType &m, VertexPointer vp)
00504                 {
00505 
00506                     assert(MeshType::VertexType::HasVHAdjacency());
00507 
00508                     vector<FacePointer> old_faces;
00509 
00510                     typedef vector<VertexPointer> vert_vect;
00511                     vector< vert_vect > old_face_verts;
00512 
00513                     assert( vp->VHp() );
00514 
00515                     Pos<MeshType> p(vp->VHp(), true);
00516 
00517                     HEdgePointer hep = p.HE();
00518 
00519                     do
00520                     {
00521                         assert( p.F() );
00522                         assert( p.F()->VN() == 4);
00523 
00524                         old_faces.push_back(p.F());
00525 
00526                         old_face_verts.push_back( getVertices( p.F(), p.HE() ) );
00527 
00528                         p.FlipE();
00529                         p.FlipF();
00530 
00531                     }while(p.HE() != hep);
00532 
00533                     assert( old_faces.size() == old_face_verts.size() );
00534 
00535                     int size = old_faces.size();
00536 
00537                     vector<vert_vect> new_face_verts;
00538 
00539                     for(int i = 0; i < size; i++)
00540                     {
00541                         new_face_verts.push_back(vector<VertexPointer>());
00542 
00543                         new_face_verts.back().push_back( old_face_verts[i][0] );
00544                         new_face_verts.back().push_back( old_face_verts[i][2] );
00545                         new_face_verts.back().push_back( old_face_verts[i][3] );
00546                         new_face_verts.back().push_back( old_face_verts[(i+1)%size][2] );
00547 
00548                     }
00549 
00550                     for(typename vector<FacePointer>::iterator fi = old_faces.begin(); fi != old_faces.end(); ++fi)
00551                         remove_face_unsafe( m, *fi );
00552 
00553                     for(typename vector<vert_vect>::iterator vi = new_face_verts.begin(); vi != new_face_verts.end(); ++vi)
00554                         add_face_unsafe(m, *vi);
00555 
00556                     return vp;
00557 
00558                 }
00559 
00569                 static VertexPointer edge_collapse(MeshType &m, EdgePointer ep, VertexPointer vp)
00570                 {
00571 
00572                     assert(MeshType::EdgeType::HasEHAdjacency());
00573                     assert(MeshType::VertexType::HasVHAdjacency());
00574                     assert(MeshType::HEdgeType::HasHOppAdjacency());
00575                     assert(MeshType::HEdgeType::HasHVAdjacency());
00576                     assert(MeshType::HEdgeType::HasHPrevAdjacency());
00577 
00578                     if( ep->EHp()->HFp() )
00579                         assert(ep->EHp()->HFp()->VN() > 3);
00580 
00581                     if( ep->EHp()->HOp()->HFp())
00582                         assert(ep->EHp()->HOp()->HFp()->VN() > 3);
00583 
00584                     assert(ep->EHp()->HFp() || ep->EHp()->HOp()->HFp());
00585                     assert(ep->EHp()->HVp() == vp || ep->EHp()->HOp()->HVp() == vp);
00586 
00587 
00588                     HEdgePointer he = ep->EHp();
00589                     HEdgePointer hopp = he->HOp();
00590 
00591                     VertexPointer vp1;
00592 
00593                     if( he->HVp() == vp )
00594                         vp1 = hopp->HVp();
00595                     else
00596                         vp1 = he->HVp();
00597 
00598                     change_vertex( vp, vp1);
00599 
00600                     //HP
00601                     he->HNp()->HPp() = he->HPp();
00602                     hopp->HNp()->HPp() = hopp->HPp();
00603 
00604                     //HN
00605                     he->HPp()->HNp() = he->HNp();
00606                     hopp->HPp()->HNp() = hopp->HNp();
00607 
00608                     //FH
00609                     if( he->HFp() )
00610                         if( he->HFp()->FHp() == he )
00611                             he->HFp()->FHp() = he->HNp();
00612 
00613                     if( hopp->HFp() )
00614                         if( hopp->HFp()->FHp() == hopp )
00615                             hopp->HFp()->FHp() = hopp->HNp();
00616 
00617                     // VH
00618                     if( vp1->VHp() == hopp )
00619                         vp1->VHp() = hopp->HNp();
00620 
00621                     Allocator<MeshType>::DeleteEdge(m,*ep);
00622                     Allocator<MeshType>::DeleteHEdge(m,*he);
00623                     Allocator<MeshType>::DeleteHEdge(m,*hopp);
00624                     Allocator<MeshType>::DeleteVertex(m,*vp);
00625 
00626                     return vp1;
00627 
00628                 }
00629 
00638                 static FacePointer add_face(MeshType &m, vector<VertexPointer> &vps)
00639                 {
00640 
00641                     assert(MeshType::VertexType::HasVHAdjacency());
00642                     assert(MeshType::EdgeType::HasEHAdjacency());
00643                     assert(MeshType::HEdgeType::HasHVAdjacency());
00644                     assert(MeshType::HEdgeType::HasHEAdjacency());
00645                     assert(MeshType::HEdgeType::HasHFAdjacency());
00646                     assert(MeshType::HEdgeType::HasHOppAdjacency());
00647                     assert(MeshType::HEdgeType::HasHPrevAdjacency());
00648 
00649                     unsigned int size = vps.size();
00650 
00651                     assert(size >= 3); //there must be at least 3 vertices
00652 
00653                     for(unsigned int i = 0; i< size; i++)
00654                     {
00655                         // all vertices must be different
00656                         assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
00657                     }
00658 
00659                     vector<HEdgePointer> hps;
00660 
00661                     while(hps.size() < size)
00662                         if( !can_add_hedge(vps, hps) )
00663                             return NULL;
00664 
00665                     vector<bool> non_manifold_vertices(size, false);
00666                     return add_face_unsafe( m,vps, hps, non_manifold_vertices );
00667 
00668                 }
00669 
00679                 static bool remove_face(MeshType &m, FacePointer fp)
00680                 {
00681 
00682                     assert(MeshType::VertexType::HasVHAdjacency());
00683                     assert(MeshType::EdgeType::HasEHAdjacency());
00684                     assert(MeshType::FaceType::HasFHAdjacency());
00685                     assert(MeshType::HEdgeType::HasHVAdjacency());
00686                     assert(MeshType::HEdgeType::HasHEAdjacency());
00687                     assert(MeshType::HEdgeType::HasHFAdjacency());
00688                     assert(MeshType::HEdgeType::HasHOppAdjacency());
00689                     assert(MeshType::HEdgeType::HasHPrevAdjacency());
00690 
00691                     if( can_remove_face(fp) )
00692                     {
00693                         remove_face_unsafe(m, fp);
00694                         return true;
00695                     }
00696 
00697                     return false;
00698                 }
00699 
00700             protected:
00701 
00710                 static FacePointer add_face_unsafe(MeshType &m, vector<VertexPointer> &vps)
00711                 {
00712                     unsigned int size = vps.size();
00713 
00714                     vector<HEdgePointer> hps;
00715                     vector<bool> non_manifold_vertices;
00716 
00717                     while(hps.size() < size)
00718                     {
00719                         if( can_add_hedge(vps, hps) )
00720                             non_manifold_vertices.push_back( false );
00721                         else
00722                             non_manifold_vertices.push_back( hps.back() == NULL );
00723                     }
00724 
00725                     return add_face_unsafe(m,vps,hps, non_manifold_vertices);
00726                 }
00727 
00737                 static FacePointer add_face_unsafe(MeshType &m, vector<VertexPointer> &vps, vector<HEdgePointer> &hps, vector<bool> &non_manifold_vertices)
00738                 {
00739 
00740                     assert(MeshType::VertexType::HasVHAdjacency());
00741                     assert(MeshType::EdgeType::HasEHAdjacency());
00742                     assert(MeshType::HEdgeType::HasHVAdjacency());
00743                     assert(MeshType::HEdgeType::HasHEAdjacency());
00744                     assert(MeshType::HEdgeType::HasHFAdjacency());
00745                     assert(MeshType::HEdgeType::HasHOppAdjacency());
00746                     assert(MeshType::HEdgeType::HasHPrevAdjacency());
00747 
00748                     unsigned int size = vps.size();
00749 
00750                     assert(size >= 3); //there must be at least 3 vertices
00751 
00752 //                    for(unsigned int i = 0; i< size; i++)
00753 //                    {
00754 //                        // all vertices must be different
00755 //                        assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
00756 //                    }
00757 
00758                     HEdgeIterator hi;
00759 
00760                     assert(hps.size() == size);
00761 
00762                     HEdgePointer nullPointer = NULL;
00763                     int edge_n = count(hps.begin(), hps.end(), nullPointer);
00764 
00765                     FaceIterator fi = Allocator<MeshType>::AddFaces(m,1);
00766                     m.face.back().Alloc( size );
00767 
00768                     if(edge_n > 0)
00769                     {
00770                         (*fi).SetD();
00771 
00772                         EdgeIterator ei = Allocator<MeshType>::AddEdges(m,edge_n);
00773 
00774                         for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1)
00775                             (*ei1).SetD();
00776 
00777                         typename Allocator<MeshType>::template PointerUpdater<HEdgePointer> pu;
00778 
00779                         if(m.hedge.empty())
00780                             pu.oldBase = 0;
00781                         else
00782                         {
00783                             pu.oldBase = &*(m.hedge.begin());
00784                             pu.oldEnd = &m.hedge.back()+1;
00785                         }
00786 
00787                         hi = Allocator<MeshType>::AddHEdges(m,2*edge_n);
00788 
00789                         pu.newBase = &*(m.hedge.begin());
00790                         pu.newEnd = &m.hedge.back()+1;
00791 
00792 
00793                         //undelete face
00794                         (*fi).ClearD();
00795 
00796                         //undelete edges
00797                         for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1)
00798                             (*ei1).ClearD();
00799 
00800 
00801                         HEdgeIterator hi1 = hi;
00802                         HEdgeIterator hi2 = hi;
00803 
00804                         ++hi2;
00805 
00806 
00807                         for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1, ++hi1, ++hi2)
00808                         {
00809                             // EH
00810                             (*ei1).EHp() = &(*hi1);
00811 
00812                             // HE
00813                             (*hi1).HEp() = &(*ei1);
00814                             (*hi2).HEp() = &(*ei1);
00815 
00816                             //HO
00817                             (*hi1).HOp() = &(*hi2);
00818                             (*hi2).HOp() = &(*hi1);
00819 
00820                             // HF
00821                             (*hi1).HFp() = &(*fi);
00822 
00823                             ++hi1;
00824                             ++hi2;
00825                         }
00826 
00827                         // update hedge pointers (if needed)
00828                         if( pu.NeedUpdate() )
00829                             for(typename vector<HEdgePointer>::iterator hpsi = hps.begin(); hpsi != hps.end(); ++hpsi)
00830                             {
00831                                 if((*hpsi))
00832                                     pu.Update(*hpsi);
00833                             }
00834 
00835 
00836 
00837                     }
00838 
00839                     vector<HEdgePointer> hps1;
00840 
00841                     for(unsigned int i = 0; i < size; i++)
00842                     {
00843                         if(hps[i] == NULL)
00844                         {
00845                             hps1.push_back(&(*hi));
00846                             ++hi;
00847                             ++hi;
00848                         }
00849                         else
00850                             hps1.push_back(hps[i]);
00851                     }
00852 
00853 
00854                     assert( hps1.size() == size );
00855 
00856 
00857                     for(unsigned int i = 0; i < size; i++)
00858                     {
00859 
00860                         int next = (i+1)%size;
00861 
00862                         // hedge already exisitng
00863                         if(hps[i])
00864                         {
00865                             hps1[i]->HFp() = &(*fi);
00866 
00867                             // next hedge was disconnected
00868                             if(!hps[next])
00869                             {
00870 
00871                                 hps1[next]->HOp()->HNp() = hps1[i]->HNp();
00872 
00873                                 hps1[i]->HNp()->HPp() = hps1[next]->HOp();
00874 
00875                                 hps1[i]->HNp() = hps1[next];
00876 
00877                                 hps1[next]->HPp() = hps1[i];
00878                             }
00879                         }
00880 
00881                         // hedge wasn't existing, vertex was disconnected
00882                         else
00883                         {
00884                             //HV
00885                             hps1[i]->HVp() = vps[i];
00886                             hps1[i]->HOp()->HVp() = vps[next];
00887 
00888 
00889                             hps1[i]->HNp() = hps1[next];
00890 
00891                             // next hedge was existing (vertex was disconnected)
00892                             if(hps[next])
00893                             {
00894                                 hps1[i]->HOp()->HPp() = hps1[next]->HPp();
00895                                 hps1[next]->HPp()->HNp() = hps1[i]->HOp();
00896                             }
00897 
00898                             //vertex was detached
00899                             else
00900                             {
00901                                 // after face insertion vertex will become non-manifold
00902                                 if(non_manifold_vertices[next])
00903                                 {
00904                                     Pos<MeshType> p(vps[next]->VHp(), true);
00905 
00906                                     while(p.F())
00907                                     {
00908 
00909                                         p.FlipE();
00910                                         p.FlipF();
00911 
00912                                         if(p.HE() == vps[next]->VHp())
00913                                             assert(0); //can't add a connection, there is no space
00914                                     }
00915 
00916 
00917                                     p.HE()->HPp()->HNp() = hps1[i]->HOp();
00918                                     hps1[i]->HOp()->HPp() = p.HE()->HPp();
00919 
00920                                     p.HE()->HPp() = hps1[next]->HOp();
00921                                     hps1[next]->HOp()->HNp() = p.HE();
00922 
00923                                 }
00924                                 else
00925                                 {
00926                                     hps1[i]->HOp()->HPp() = hps1[next]->HOp();
00927                                     hps1[next]->HOp()->HNp() = hps1[i]->HOp();
00928                                 }
00929 
00930                             }
00931 
00932 
00933                             hps1[next]->HPp() = hps1[i];
00934 
00935                             //VH
00936                             if( !vps[i]->VHp())
00937                                 vps[i]->VHp() = hps1[i];
00938                         }
00939                     }
00940 
00941                     //FH
00942                     (*fi).FHp() = hps1.front();
00943 
00944                     return &(*fi);
00945 
00946                 }
00947 
00955                 static void remove_face_unsafe (MeshType &m, FacePointer fp)
00956                 {
00957 
00958                     vector<HEdgePointer> hps = getHEdges(fp);
00959 
00960                     int size = hps.size();
00961 
00962                     for( int i = 0; i< size; i++ )
00963                     {
00964                         if( hps[i]->HOp()->HFp() )
00965                         {
00966                             hps[i]->HFp() = NULL;
00967 
00968                             if( !hps[(i+size-1)%size]->HOp()->HFp() )
00969                             {
00970                                 // HP
00971                                 hps[i]->HPp() = hps[(i+size-1)%size]->HOp()->HPp();
00972                                 hps[(i+size-1)%size]->HOp()->HPp()->HNp() = hps[i];
00973                             }
00974 
00975                             if( !hps[(i+1)%size]->HOp()->HFp() )
00976                             {
00977                                 // HN
00978                                 hps[i]->HNp() = hps[(i+1)%size]->HOp()->HNp();
00979                                 hps[(i+1)%size]->HOp()->HNp()->HPp() = hps[i];
00980                             }
00981                         }
00982                         else
00983                         {
00984                             Allocator<MeshType>::DeleteHEdge( m, *hps[i] );
00985                             Allocator<MeshType>::DeleteHEdge( m, *(hps[i]->HOp()) );
00986                             Allocator<MeshType>::DeleteEdge( m, *(hps[i]->HEp()) );
00987 
00988 
00989                             if( !hps[(i+size-1)%size]->HOp()->HFp() )
00990                             {
00991                                 hps[i]->HOp()->HNp()->HPp() = hps[(i+size-1)%size]->HOp()->HPp();
00992                                 hps[(i+size-1)%size]->HOp()->HPp()->HNp() = hps[i]->HOp()->HNp();
00993                             }
00994 
00995                         }
00996 
00997                     }
00998 
00999                     for( int i = 0; i< size; i++ )
01000                     {
01001                         if( hps[i]->HVp()->VHp()->IsD() )
01002                         {
01003                             if( !hps[i]->IsD() )
01004                                 hps[i]->HVp()->VHp() = hps[i];
01005 
01006                             else if( !hps[(i+size-1)%size]->IsD() )
01007                                 hps[i]->HVp()->VHp() = hps[(i+size-1)%size]->HOp();
01008 
01009                             else //search for a hedge (hedge can be found only if the vertex is non-manifold)
01010                             {
01011                                 bool manifold = true;
01012 
01013                                 Pos<MeshType> p(hps[i]->HVp()->VHp(), true);
01014 
01015                                 p.HE()->SetV();
01016 
01017                                 p.FlipE();
01018                                 p.FlipF();
01019 
01020                                 while( !p.HE()->IsV() )
01021                                 {
01022                                     if( !p.HE()->IsD() )
01023                                     {
01024                                         manifold = false;
01025                                         hps[i]->HVp()->VHp() = p.HE();
01026                                         break;
01027                                     }
01028 
01029                                     p.FlipE();
01030                                     p.FlipF();
01031                                 }
01032 
01033                                 p.HE()->ClearV();
01034 
01035                                 if(manifold)
01036                                     hps[i]->HVp()->VHp() = NULL;
01037 
01038                             }
01039                         }
01040 
01041                     }
01042                     Allocator<MeshType>::DeleteFace(m,*fp);
01043 
01044                 }
01045 
01056                 static bool can_add_hedge( vector<VertexPointer> &vps, vector<HEdgePointer> &hps )
01057                 {
01058 
01059                     unsigned int i = hps.size();
01060 
01061                     assert( i < vps.size() );
01062 
01063                     HEdgePointer he = vps[i]->VHp();
01064 
01065                     if(!he) //vertex is detached
01066                     {
01067                         hps.push_back(NULL);
01068                         return true;
01069                     }
01070                     else
01071                     {
01072                         bool disconnected = false;
01073 
01074                         bool hasEdge = false;
01075 
01076                         unsigned int size = vps.size();
01077 
01078                         Pos<MeshType> p(he, false);
01079 
01080                         he->SetV();
01081 
01082                         while(p.V() != vps[(i+1)%size])
01083                         {
01084                             if(!hasEdge)
01085                                 hasEdge= ( find( vps.begin(), vps.end(), p.V()) != (vps.end() ) );
01086 
01087                             p.FlipV();
01088 
01089                             p.FlipE();
01090                             p.FlipF();
01091 
01092                             p.FlipV();
01093 
01094                             if(p.HE()->IsV())
01095                             {
01096                                 disconnected = true;
01097                                 break;
01098                             }
01099 
01100                         }
01101 
01102                         he->ClearV();
01103 
01104                         if(disconnected) // edge does not exist
01105                         {
01106                             hps.push_back(NULL);
01107 
01108                             // if hasEdge is false after inserting the face there will be a non-manifold vertex
01109                             return hasEdge;
01110                         }
01111 
01112                         else //edge already existing
01113                         {
01114                             // try to insert consecutve hedges if they will belong to the new face
01115                             while( (p.V() ==  vps[(i+1)%size])  && (i < size) )
01116                             {
01117                                 hps.push_back( p.HE() );
01118 
01119                                 if(p.HE()->HFp() != NULL)
01120                                     return false;
01121 
01122                                 i++;
01123                                 p.FlipE();
01124                                 p.FlipV();
01125                             }
01126                             return true;
01127                         }
01128                     }
01129                 }
01130 
01139                 static bool can_remove_face(FacePointer fp)
01140                 {
01141 
01142                     Pos<MeshType> p(fp->FHp(), true);
01143 
01144                     do
01145                     {
01146                         vector<FacePointer> incident_faces = get_incident_faces( p.V() );
01147 
01148                         unsigned int size = incident_faces.size();
01149 
01150                         if(size > 2)
01151                         {
01152                             for(unsigned int i = 0; i < size; i++)
01153                             {
01154                                 if(incident_faces[i] == NULL)
01155                                     if(incident_faces[(i+1)%size] != fp && incident_faces[((i+size)-1)%size] != fp )
01156                                         return false;
01157                             }
01158                         }
01159 
01160                         p.FlipV();
01161                         p.FlipE();
01162 
01163                     }while( p.HE() != fp->FHp() );
01164 
01165                     return true;
01166                 }
01167 
01176                 static vector<VertexPointer> getVertices(FacePointer fp, HEdgePointer starting_he = NULL)
01177                 {
01178                     if(starting_he)
01179                         assert( starting_he->HFp() == fp );
01180                     else
01181                         starting_he = fp->FHp();
01182 
01183                     Pos<MeshType> p( starting_he, true );
01184 
01185                     vector<VertexPointer> ret;
01186 
01187                     if( fp )
01188                     {
01189                         do
01190                         {
01191                             ret.push_back( p.V() );
01192 
01193                             p.FlipV();
01194                             p.FlipE();
01195 
01196                         }while(p.HE() != starting_he);
01197                     }
01198                     return ret;
01199 
01200                 }
01201 
01210                 static vector<HEdgePointer> getHEdges(FacePointer fp, HEdgePointer starting_he = NULL)
01211                 {
01212                     if(starting_he)
01213                         assert( starting_he->HFp() == fp );
01214                     else
01215                         starting_he = fp->FHp();
01216 
01217                     Pos<MeshType> p( starting_he, true );
01218 
01219                     vector<HEdgePointer> ret;
01220 
01221                     if( fp )
01222                     {
01223                         do
01224                         {
01225                             ret.push_back( p.HE() );
01226 
01227                             p.FlipV();
01228                             p.FlipE();
01229 
01230                         }while(p.HE() != starting_he);
01231                     }
01232                     return ret;
01233 
01234                 }
01235 
01244                 static vector<FacePointer> get_incident_faces(VertexPointer vp, HEdgePointer starting_he = NULL)
01245                 {
01246                     assert(vp);
01247 
01248                     if(starting_he)
01249                         assert( starting_he->HVp() == vp );
01250                     else
01251                         starting_he = vp->VHp();
01252 
01253                     Pos<MeshType> p( starting_he, true );
01254 
01255                     vector<FacePointer> ret;
01256 
01257                     do
01258                     {
01259                         ret.push_back( p.F() );
01260 
01261                         p.FlipE();
01262                         p.FlipF();
01263 
01264                     }while(p.HE() != starting_he);
01265 
01266                     return ret;
01267 
01268                 }
01269 
01277                 static void change_vertex(VertexPointer old_vp, VertexPointer new_vp)
01278                 {
01279                     assert(old_vp);
01280                     assert(new_vp);
01281                     assert(old_vp != new_vp);
01282 
01283                     Pos<MeshType> p(old_vp->VHp(),true);
01284 
01285                     p.HE()->SetV();
01286 
01287                     do
01288                     {
01289                         p.HE()->HVp() = new_vp;
01290 
01291                         p.FlipE();
01292                         p.FlipF();
01293 
01294                     }while( !p.HE()->IsV() );
01295 
01296                     p.HE()->ClearV();
01297 
01298                     if( !new_vp->VHp() )
01299                         new_vp->VHp() = old_vp->VHp();
01300 
01301                 }
01302 
01303             };
01304 
01305     }
01306 }
01307 
01308 #endif // VCG_HEDGE_TOPOLOGY
01309