00001 #ifndef VCG_HEDGE_TOPOLOGY
00002 #define VCG_HEDGE_TOPOLOGY
00003
00004 #include <vcg/connectors/halfedge_pos.h>
00005
00006 using namespace std;
00007 using namespace vcg::hedge;
00008 using namespace vcg::tri;
00009
00010 namespace vcg
00011 {
00012 namespace tri
00013 {
00014
00019 template <class MeshType> class HalfEdgeTopology
00020 {
00021 public:
00022
00023 typedef typename MeshType::VertexPointer VertexPointer;
00024 typedef typename MeshType::EdgePointer EdgePointer;
00025 typedef typename MeshType::HEdgePointer HEdgePointer;
00026 typedef typename MeshType::FacePointer FacePointer;
00027
00028 typedef typename MeshType::VertexIterator VertexIterator;
00029 typedef typename MeshType::EdgeIterator EdgeIterator;
00030 typedef typename MeshType::HEdgeIterator HEdgeIterator;
00031 typedef typename MeshType::FaceIterator FaceIterator;
00032
00033
00044 static VertexPointer edge_collapse_quad(MeshType &m, HEdgePointer hp, VertexPointer vp)
00045 {
00046 assert(vp);
00047 assert(hp);
00048 assert(MeshType::HEdgeType::HasHVAdjacency());
00049 assert(hp->HVp() == vp || hp->HOp()->HVp() == vp);
00050 assert(hp->HFp()->VN() == 4);
00051 assert(hp->HOp()->HFp()->VN() == 4);
00052
00053
00054 VertexPointer vp_opp;
00055 FacePointer fp;
00056
00057 if( hp->HVp() == vp )
00058 hp = hp->HOp();
00059
00060
00061 vp_opp = hp->HVp();
00062 fp = hp->HFp();
00063
00064 VertexPointer vp_rot = vertex_rotate_quad( vp );
00065
00066 assert(vp_rot == vp);
00067
00068 return diagonal_collapse_quad( m, fp, vp );
00069 }
00070
00081 static VertexPointer diagonal_collapse_quad(MeshType &m, FacePointer fp, VertexPointer vp)
00082 {
00083
00084 assert(MeshType::VertexType::HasVHAdjacency());
00085 assert(MeshType::FaceType::HasFHAdjacency());
00086 assert(MeshType::HEdgeType::HasHVAdjacency());
00087 assert(MeshType::HEdgeType::HasHFAdjacency());
00088 assert(MeshType::HEdgeType::HasHOppAdjacency());
00089 assert(MeshType::HEdgeType::HasHPrevAdjacency());
00090
00091 assert(fp);
00092 assert(fp->FHp());
00093 assert(fp->VN() == 4);
00094 assert(!fp->IsD());
00095
00096 assert( !has_doublet_quad(fp) );
00097 assert(!is_singlet_quad(fp));
00098
00099 bool HasHE = MeshType::HEdgeType::HasHEAdjacency();
00100 bool HasEH = MeshType::EdgeType::HasEHAdjacency();
00101
00102 HEdgePointer hp;
00103
00104 vector<VertexPointer> vps = getVertices(fp);
00105
00106 assert(vps.size()==4);
00107
00108 for(unsigned int i = 0; i< vps.size(); i++)
00109 {
00110
00111 assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
00112 }
00113
00114 hp = fp->FHp();
00115
00116 while(hp->HVp() != vp)
00117 hp= hp->HNp();
00118
00119 vector<HEdgePointer> hps = getHEdges(fp,hp);
00120
00121 assert(vp == hps[0]->HVp());
00122
00123 VertexPointer opposite_vertex = hps[2]->HVp();
00124
00125 vp->P() = (vp->P() + opposite_vertex->P() )/2;
00126 change_vertex(opposite_vertex, vp);
00127
00128 hps[0]->HOp()->HOp()=hps[1]->HOp();
00129 hps[1]->HOp()->HOp()=hps[0]->HOp();
00130
00131 hps[2]->HOp()->HOp()=hps[3]->HOp();
00132 hps[3]->HOp()->HOp()=hps[2]->HOp();
00133
00134 for(int i=0; i<4; i++)
00135 {
00136 if(hps[i]->HVp()->VHp() == hps[i])
00137 hps[i]->HVp()->VHp() = hps[(i+4-1)%4]->HOp();
00138 }
00139
00140 if(HasHE)
00141 {
00142 hps[1]->HOp()->HEp()=hps[0]->HEp();
00143 hps[3]->HOp()->HEp()=hps[2]->HEp();
00144 }
00145
00146 if(HasEH && HasHE)
00147 {
00148 for(int i=0; i<3; i+=2)
00149 {
00150 if(hps[i]->HEp()->EHp() == hps[i])
00151 hps[i]->HEp()->EHp() = hps[i]->HOp();
00152 }
00153 }
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 bool b[2];
00167
00168 b[0] = (hps[0]->HOp()->HFp() == NULL && hps[1]->HOp()->HFp() == NULL);
00169 b[1] = (hps[2]->HOp()->HFp() == NULL && hps[3]->HOp()->HFp() == NULL);
00170
00171 for( int i=0, j=0; i < 4; i+=2, j++ )
00172 {
00173 if(b[j])
00174 {
00175 if(HasHE)
00176 Allocator<MeshType>::DeleteEdge(m, *(hps[i]->HEp()) );
00177
00178 Allocator<MeshType>::DeleteHEdge(m, *(hps[i]->HOp()) );
00179 Allocator<MeshType>::DeleteHEdge(m, *(hps[i+1]->HOp()) );
00180
00181 hps[i+1]->HVp()->VHp() = NULL;
00182
00183 if(!b[(j+1)%2])
00184 {
00185 hps[i]->HOp()->HNp()->HPp() = hps[i+1]->HOp()->HPp();
00186 hps[i+1]->HOp()->HPp()->HNp() = hps[i]->HOp()->HNp();
00187
00188 if(vp->VHp() == hps[i+1]->HOp())
00189 vp->VHp() = hps[(i+3)%4]->HOp();
00190 }
00191
00192 else
00193 vp->VHp() = NULL;
00194
00195 }
00196 }
00197
00198
00199 Allocator<MeshType>::DeleteFace(m, *(fp) );
00200 Allocator<MeshType>::DeleteVertex(m, *(opposite_vertex) );
00201 if(HasHE)
00202 {
00203 Allocator<MeshType>::DeleteEdge(m, *(hps[1]->HEp()) );
00204 Allocator<MeshType>::DeleteEdge(m, *(hps[3]->HEp()) );
00205 }
00206 Allocator<MeshType>::DeleteHEdge(m, *(hps[0]) );
00207 Allocator<MeshType>::DeleteHEdge(m, *(hps[1]) );
00208 Allocator<MeshType>::DeleteHEdge(m, *(hps[2]) );
00209 Allocator<MeshType>::DeleteHEdge(m, *(hps[3]) );
00210
00211 return vp;
00212
00213 }
00214
00223 static FacePointer doublet_remove_quad(MeshType &m, VertexPointer vp)
00224 {
00225 assert(vp);
00226
00227 HEdgePointer hp = vp->VHp();
00228
00229 assert(hp);
00230
00231 FacePointer fp1 = hp->HFp();
00232 FacePointer fp2 = hp->HOp()->HFp();
00233
00234 assert(!is_singlet_quad(fp1));
00235 assert(!is_singlet_quad(fp2));
00236
00237
00238 assert( fp1 );
00239 assert( fp2 );
00240
00241 assert( hp->HOp()->HNp()->HOp() == hp->HPp() );
00242
00243 assert( fp1->VN() == 4);
00244 assert( fp2->VN() == 4);
00245
00246
00247
00248 hp->HNp()->HPp() = hp->HOp()->HPp();
00249 hp->HOp()->HPp()->HNp() = hp->HNp();
00250
00251 hp->HPp()->HPp()->HNp() = hp->HOp()->HNp()->HNp();
00252 hp->HOp()->HNp()->HNp()->HPp() = hp->HPp()->HPp();
00253
00254
00255 if( hp->HOp()->HVp()->VHp() == hp->HOp() )
00256 hp->HOp()->HVp()->VHp() = hp->HNp();
00257
00258 if( hp->HPp()->HVp()->VHp() == hp->HPp() )
00259 hp->HPp()->HVp()->VHp() = hp->HPp()->HPp()->HNp();
00260
00261
00262 hp->HNp()->HPp()->HFp() = fp1;
00263 hp->HOp()->HNp()->HNp()->HFp() = fp1;
00264
00265 if(fp1->FHp() == hp || fp1->FHp() == hp->HPp())
00266 fp1->FHp() = hp->HNp();
00267
00268
00269 Allocator<MeshType>::DeleteVertex(m, *vp);
00270 if(MeshType::HEdgeType::HasHEAdjacency())
00271 {
00272 Allocator<MeshType>::DeleteEdge(m, *(hp->HEp()) );
00273 Allocator<MeshType>::DeleteEdge(m, *(hp->HPp()->HEp()) );
00274 }
00275 Allocator<MeshType>::DeleteHEdge(m, *hp );
00276 Allocator<MeshType>::DeleteHEdge(m, *(hp->HOp()) );
00277 Allocator<MeshType>::DeleteHEdge(m, *(hp->HPp()) );
00278 Allocator<MeshType>::DeleteHEdge(m, *(hp->HPp()->HOp()) );
00279 Allocator<MeshType>::DeleteFace(m, *fp2 );
00280
00281
00282 return fp1;
00283
00284
00285 }
00286
00287
00296 static HEdgePointer singlet_remove_quad(MeshType &m, FacePointer fp)
00297 {
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311 assert( is_singlet_quad(fp) );
00312
00313 bool HasHE = MeshType::HEdgeType::HasHEAdjacency();
00314 bool HasEH = MeshType::EdgeType::HasEHAdjacency();
00315
00316 vector<HEdgePointer> ext_hedges;
00317
00318 vector<HEdgePointer> int_hedges = getHEdges(fp);
00319
00320 Allocator<MeshType>::DeleteFace( m, *(fp) );
00321
00322 for(typename vector<HEdgePointer>::iterator hi = int_hedges.begin(); hi != int_hedges.end();++hi)
00323 {
00324
00325 if((*hi)->HOp()->HFp() != fp)
00326 ext_hedges.push_back((*hi)->HOp());
00327
00328 else if(vertex_valence((*hi)->HVp()) == 1)
00329 {
00330 Allocator<MeshType>::DeleteVertex( m, *((*hi)->HVp()) );
00331 if(HasHE)
00332 Allocator<MeshType>::DeleteEdge( m, *((*hi)->HEp()) );
00333 }
00334
00335 }
00336
00337 for(typename vector<HEdgePointer>::iterator hi = int_hedges.begin(); hi != int_hedges.end();++hi)
00338 Allocator<MeshType>::DeleteHEdge( m, *(*hi) );
00339
00340 assert(ext_hedges.size() == 2);
00341
00342
00343 if(ext_hedges[0]->HFp() || ext_hedges[1]->HFp())
00344 {
00345 ext_hedges[0]->HOp() = ext_hedges[1];
00346 ext_hedges[1]->HOp() = ext_hedges[0];
00347
00348 if(HasHE)
00349 {
00350 Allocator<MeshType>::DeleteEdge( m, *(ext_hedges[1]->HEp()) );
00351
00352 ext_hedges[1]->HEp() = ext_hedges[0]->HEp();
00353
00354 if(HasEH)
00355 ext_hedges[0]->HEp()->EHp() = ext_hedges[0];
00356 }
00357
00358 ext_hedges[0]->HVp()->VHp() = ext_hedges[0];
00359 ext_hedges[1]->HVp()->VHp() = ext_hedges[1];
00360
00361 return ext_hedges[0];
00362 }
00363
00364 else
00365 {
00366 ext_hedges[0]->HVp()->VHp() = NULL;
00367 ext_hedges[1]->HVp()->VHp() = NULL;
00368
00369 if(HasHE)
00370 {
00371 Allocator<MeshType>::DeleteEdge( m, *( ext_hedges[0]->HEp()) );
00372 Allocator<MeshType>::DeleteEdge( m, *( ext_hedges[1]->HEp()) );
00373 }
00374 Allocator<MeshType>::DeleteHEdge( m, *( ext_hedges[0]) );
00375 Allocator<MeshType>::DeleteHEdge( m, *( ext_hedges[1]) );
00376
00377 return NULL;
00378 }
00379
00380 }
00381
00382
00391 static HEdgePointer edge_rotate_quad(HEdgePointer hp, bool cw)
00392 {
00393
00394 assert( MeshType::HEdgeType::HasHFAdjacency() );
00395 assert( MeshType::HEdgeType::HasHOppAdjacency() );
00396 assert( MeshType::FaceType::HasFHAdjacency() );
00397
00398
00399 FacePointer fp1 = hp->HFp();
00400 FacePointer fp2 = hp->HOp()->HFp();
00401
00402
00403 assert( fp1 );
00404 assert( fp1->VN() == 4 );
00405
00406 assert( fp2 );
00407 assert( fp2->VN() == 4 );
00408
00409 assert(!is_singlet_quad(fp1));
00410 assert(!is_singlet_quad(fp2));
00411
00412 assert(!has_doublet_quad(fp1));
00413 assert(!has_doublet_quad(fp2));
00414
00415 vector<FacePointer> fps;
00416 typedef vector<HEdgePointer> hedge_vect;
00417 vector<hedge_vect> hps;
00418
00419 fps.push_back(fp1);
00420 fps.push_back(fp2);
00421
00422
00423 hps.push_back( getHEdges( fp1, hp ) );
00424 hps.push_back( getHEdges( fp2, hp->HOp() ) );
00425
00426
00427 for(int i=0; i< 2; i++)
00428 {
00429
00430 int j = (i+1)%2;
00431
00432
00433 hps[i][1]->HPp() = hps[j][3];
00434 hps[j][3]->HNp() = hps[i][1];
00435
00436 if(hps[j][0]->HVp()->VHp() == hps[j][0])
00437 hps[j][0]->HVp()->VHp() = hps[i][1];
00438
00439 if(cw)
00440 {
00441 hps[i][0]->HNp() = hps[j][3];
00442 hps[j][3]->HPp() = hps[i][0];
00443
00444 hps[j][2]->HNp() = hps[j][0];
00445 hps[j][0]->HPp() = hps[j][2];
00446
00447 hps[j][0]->HVp() = hps[j][3]->HVp();
00448
00449 hps[j][3]->HFp() = fps[i];
00450
00451 if(fps[j]->FHp() == hps[j][3])
00452 fps[j]->FHp() = hps[j][0];
00453 }
00454 else
00455 {
00456 hps[i][0]->HNp() = hps[i][2];
00457 hps[i][2]->HPp() = hps[i][0];
00458
00459 hps[i][1]->HNp() = hps[j][0];
00460 hps[j][0]->HPp() = hps[i][1];
00461
00462 hps[j][0]->HVp() = hps[i][2]->HVp();
00463
00464 hps[i][1]->HFp() = fps[j];
00465
00466 if(fps[i]->FHp() == hps[i][1])
00467 fps[i]->FHp() = hps[i][0];
00468 }
00469
00470 }
00471
00472 return hp;
00473
00474 }
00475
00476
00477
00485 static VertexPointer vertex_rotate_quad(VertexPointer vp)
00486 {
00487
00488 assert(MeshType::VertexType::HasVHAdjacency());
00489 assert( vp->VHp() );
00490
00491 Pos<MeshType> p(vp->VHp(), true);
00492
00493 HEdgePointer hep = p.HE();
00494
00495 typedef vector<HEdgePointer> hedge_vect;
00496 vector<hedge_vect> hedges;
00497
00498 do
00499 {
00500 assert( p.F() );
00501 assert( p.F()->VN() == 4);
00502
00503 hedges.push_back(getHEdges(p.F(), p.HE()));
00504
00505 p.FlipE();
00506 p.FlipF();
00507
00508 }while(p.HE() != hep);
00509
00510
00511 int size = hedges.size();
00512
00513 for(int i=0; i< size; i++)
00514 {
00515 hedges[i][0]->HNp() = hedges[i][2];
00516 hedges[i][2]->HPp() = hedges[i][0];
00517
00518 assert(hedges[i][0]->HOp() == hedges[(i+size-1)%size][3]);
00519
00520 hedges[i][2]->HNp() = hedges[(i+1)%size][1];
00521 hedges[(i+1)%size][1]->HPp() = hedges[i][2];
00522
00523 hedges[(i+1)%size][1]->HNp() = hedges[i][3];
00524 hedges[i][3]->HPp() = hedges[(i+1)%size][1];
00525
00526 hedges[(i+1)%size][1]->HFp() = hedges[i][3]->HFp();
00527
00528 if(hedges[i][3]->HVp()->VHp() == hedges[i][3])
00529 hedges[i][3]->HVp()->VHp() = hedges[(i+1)%size][1];
00530
00531 hedges[i][3]->HVp() = hedges[(i+1)%size][2]->HVp();
00532
00533 if(hedges[i][0]->HFp()->FHp() == hedges[i][1])
00534 hedges[i][0]->HFp()->FHp() = hedges[i][0];
00535
00536 }
00537 return vp;
00538
00539 }
00540
00541
00551 static VertexPointer edge_collapse(MeshType &m, HEdgePointer hp, VertexPointer vp)
00552 {
00553
00554 assert(MeshType::VertexType::HasVHAdjacency());
00555 assert(MeshType::HEdgeType::HasHOppAdjacency());
00556 assert(MeshType::HEdgeType::HasHVAdjacency());
00557 assert(MeshType::HEdgeType::HasHPrevAdjacency());
00558
00559 if( hp->HFp() )
00560 assert(hp->HFp()->VN() > 3);
00561
00562 if( hp->HOp()->HFp())
00563 assert(hp->HOp()->HFp()->VN() > 3);
00564
00565 assert(hp->HFp() || hp->HOp()->HFp());
00566 assert(hp->HVp() == vp || hp->HOp()->HVp() == vp);
00567
00568
00569 HEdgePointer hopp = hp->HOp();
00570
00571 VertexPointer vp1;
00572
00573 if( hp->HVp() == vp )
00574 vp1 = hopp->HVp();
00575 else
00576 vp1 = hp->HVp();
00577
00578 change_vertex( vp, vp1);
00579
00580
00581 hp->HNp()->HPp() = hp->HPp();
00582 hopp->HNp()->HPp() = hopp->HPp();
00583
00584
00585 hp->HPp()->HNp() = hp->HNp();
00586 hopp->HPp()->HNp() = hopp->HNp();
00587
00588
00589 if( hp->HFp() )
00590 if( hp->HFp()->FHp() == hp )
00591 hp->HFp()->FHp() = hp->HNp();
00592
00593 if( hopp->HFp() )
00594 if( hopp->HFp()->FHp() == hopp )
00595 hopp->HFp()->FHp() = hopp->HNp();
00596
00597
00598 if( vp1->VHp() == hopp )
00599 vp1->VHp() = hopp->HNp();
00600
00601 if(HasHEAdjacency(m))
00602 Allocator<MeshType>::DeleteEdge(m,*(hp->HEp()));
00603 Allocator<MeshType>::DeleteHEdge(m,*hp);
00604 Allocator<MeshType>::DeleteHEdge(m,*hopp);
00605 Allocator<MeshType>::DeleteVertex(m,*vp);
00606
00607 return vp1;
00608
00609 }
00610
00619 static FacePointer add_face(MeshType &m, vector<VertexPointer> &vps)
00620 {
00621
00622 assert(MeshType::VertexType::HasVHAdjacency());
00623 assert(MeshType::HEdgeType::HasHVAdjacency());
00624 assert(MeshType::HEdgeType::HasHFAdjacency());
00625 assert(MeshType::HEdgeType::HasHOppAdjacency());
00626 assert(MeshType::HEdgeType::HasHPrevAdjacency());
00627
00628 unsigned int size = vps.size();
00629
00630 assert(size >= 3);
00631
00632 for(unsigned int i = 0; i< size; i++)
00633 {
00634
00635 assert( count(vps.begin(), vps.end(), vps[i]) == 1 );
00636 }
00637
00638 vector<HEdgePointer> hps;
00639
00640 while(hps.size() < size)
00641 if( !can_add_hedge(vps, hps) )
00642 return NULL;
00643
00644 vector<bool> non_manifold_vertices(size, false);
00645
00646 return add_face_unsafe( m,vps, hps, non_manifold_vertices);
00647
00648 }
00649
00659 static bool remove_face(MeshType &m, FacePointer fp)
00660 {
00661
00662 assert(MeshType::VertexType::HasVHAdjacency());
00663 assert(MeshType::FaceType::HasFHAdjacency());
00664 assert(MeshType::HEdgeType::HasHVAdjacency());
00665 assert(MeshType::HEdgeType::HasHFAdjacency());
00666 assert(MeshType::HEdgeType::HasHOppAdjacency());
00667 assert(MeshType::HEdgeType::HasHPrevAdjacency());
00668
00669 if( can_remove_face(fp) )
00670 {
00671 remove_face_unsafe(m, fp);
00672 return true;
00673 }
00674
00675 return false;
00676 }
00677
00678 protected:
00679
00688 static FacePointer add_face_unsafe(MeshType &m, vector<VertexPointer> &vps)
00689 {
00690 unsigned int size = vps.size();
00691
00692 vector<HEdgePointer> hps;
00693 vector<bool> non_manifold_vertices;
00694
00695 while(hps.size() < size)
00696 {
00697 if( can_add_hedge(vps, hps) )
00698 non_manifold_vertices.push_back( false );
00699 else
00700 non_manifold_vertices.push_back( hps.back() == NULL );
00701 }
00702
00703 return add_face_unsafe(m,vps,hps, non_manifold_vertices);
00704 }
00705
00706
00717 static FacePointer add_face_unsafe(MeshType &m, vector<VertexPointer> &vps, vector<HEdgePointer> &hps, vector<bool> &non_manifold_vertices)
00718 {
00719
00720 assert(MeshType::VertexType::HasVHAdjacency());
00721 assert(MeshType::HEdgeType::HasHVAdjacency());
00722 assert(MeshType::HEdgeType::HasHFAdjacency());
00723 assert(MeshType::HEdgeType::HasHOppAdjacency());
00724 assert(MeshType::HEdgeType::HasHPrevAdjacency());
00725
00726 unsigned int size = vps.size();
00727
00728 assert(size >= 3);
00729
00730
00731
00732
00733
00734
00735
00736 bool HasHE = MeshType::HEdgeType::HasHEAdjacency();
00737 bool HasEH = MeshType::EdgeType::HasEHAdjacency();
00738
00739 HEdgeIterator hi;
00740
00741 assert(hps.size() == size);
00742
00743 HEdgePointer nullPointer = NULL;
00744 int edge_n = count(hps.begin(), hps.end(), nullPointer);
00745
00746 FacePointer fp;
00747
00748 FaceIterator fi = Allocator<MeshType>::AddFaces(m,1);
00749 (*fi).Alloc( size );
00750 fp = &(*fi);
00751
00752 if(edge_n > 0)
00753 {
00754
00755 EdgeIterator ei;
00756
00757 fp->SetD();
00758
00759 if(HasEH || HasHE)
00760 {
00761 ei = Allocator<MeshType>::AddEdges(m,edge_n);
00762 for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1)
00763 (*ei1).SetD();
00764 }
00765
00766 typename Allocator<MeshType>::template PointerUpdater<HEdgePointer> pu;
00767
00768 if(m.hedge.empty())
00769 pu.oldBase = 0;
00770 else
00771 {
00772 pu.oldBase = &*(m.hedge.begin());
00773 pu.oldEnd = &m.hedge.back()+1;
00774 }
00775
00776 hi = Allocator<MeshType>::AddHEdges(m,2*edge_n);
00777
00778 pu.newBase = &*(m.hedge.begin());
00779 pu.newEnd = &m.hedge.back()+1;
00780
00781
00782 fp->ClearD();
00783
00784
00785 for(EdgeIterator ei1 = ei; ei1 != m.edge.end(); ++ei1)
00786 (*ei1).ClearD();
00787
00788
00789 if( pu.NeedUpdate() )
00790 for(typename vector<HEdgePointer>::iterator hpsi = hps.begin(); hpsi != hps.end(); ++hpsi)
00791 {
00792 if((*hpsi))
00793 pu.Update(*hpsi);
00794 }
00795
00796
00797 HEdgeIterator hi1 = hi;
00798 HEdgeIterator hi2 = hi;
00799
00800 ++hi2;
00801
00802 EdgeIterator ei1 = ei;
00803
00804 for(; hi2 != m.hedge.end(); ++hi1, ++hi2)
00805 {
00806
00807 if(HasEH)
00808 (*ei1).EHp() = &(*hi1);
00809
00810
00811 if(HasHE)
00812 {
00813 (*hi1).HEp() = &(*ei1);
00814 (*hi2).HEp() = &(*ei1);
00815 }
00816
00817
00818 (*hi1).HOp() = &(*hi2);
00819 (*hi2).HOp() = &(*hi1);
00820
00821
00822 (*hi1).HFp() = fp;
00823
00824 ++hi1;
00825 ++hi2;
00826 }
00827 }
00828
00829 vector<HEdgePointer> hps1;
00830
00831 for(unsigned int i = 0; i < size; i++)
00832 {
00833 if(hps[i] == NULL)
00834 {
00835 hps1.push_back(&(*hi));
00836 ++hi;
00837 ++hi;
00838 }
00839 else
00840 hps1.push_back(hps[i]);
00841 }
00842
00843 assert( hps1.size() == size );
00844
00845 for(unsigned int i = 0; i < size; i++)
00846 {
00847
00848 int next = (i+1)%size;
00849
00850
00851 if(hps[i])
00852 {
00853 hps1[i]->HFp() = fp;
00854
00855
00856 if(!hps[next])
00857 {
00858
00859 hps1[next]->HOp()->HNp() = hps1[i]->HNp();
00860
00861 hps1[i]->HNp()->HPp() = hps1[next]->HOp();
00862
00863 hps1[i]->HNp() = hps1[next];
00864
00865 hps1[next]->HPp() = hps1[i];
00866 }
00867 }
00868
00869
00870 else
00871 {
00872
00873 hps1[i]->HVp() = vps[i];
00874 hps1[i]->HOp()->HVp() = vps[next];
00875
00876
00877 hps1[i]->HNp() = hps1[next];
00878
00879
00880 if(hps[next])
00881 {
00882 hps1[i]->HOp()->HPp() = hps1[next]->HPp();
00883 hps1[next]->HPp()->HNp() = hps1[i]->HOp();
00884 }
00885
00886
00887 else
00888 {
00889
00890 if(non_manifold_vertices[next])
00891 {
00892 Pos<MeshType> p(vps[next]->VHp(), true);
00893
00894 while(p.F())
00895 {
00896
00897 p.FlipE();
00898 p.FlipF();
00899
00900 if(p.HE() == vps[next]->VHp())
00901 assert(0);
00902 }
00903
00904
00905 p.HE()->HPp()->HNp() = hps1[i]->HOp();
00906 hps1[i]->HOp()->HPp() = p.HE()->HPp();
00907
00908 p.HE()->HPp() = hps1[next]->HOp();
00909 hps1[next]->HOp()->HNp() = p.HE();
00910
00911 }
00912 else
00913 {
00914 hps1[i]->HOp()->HPp() = hps1[next]->HOp();
00915 hps1[next]->HOp()->HNp() = hps1[i]->HOp();
00916 }
00917
00918 }
00919
00920
00921 hps1[next]->HPp() = hps1[i];
00922
00923
00924 if( !vps[i]->VHp())
00925 vps[i]->VHp() = hps1[i];
00926 }
00927 }
00928
00929
00930 fp->FHp() = hps1.front();
00931
00932 return fp;
00933
00934 }
00935
00943 static void remove_face_unsafe (MeshType &m, FacePointer fp)
00944 {
00945
00946 vector<HEdgePointer> hps = getHEdges(fp);
00947
00948 int size = hps.size();
00949
00950 for( int i = 0; i< size; i++ )
00951 {
00952 if( hps[i]->HOp()->HFp() )
00953 {
00954 hps[i]->HFp() = NULL;
00955
00956 if( !hps[(i+size-1)%size]->HOp()->HFp() )
00957 {
00958
00959 hps[i]->HPp() = hps[(i+size-1)%size]->HOp()->HPp();
00960 hps[(i+size-1)%size]->HOp()->HPp()->HNp() = hps[i];
00961 }
00962
00963 if( !hps[(i+1)%size]->HOp()->HFp() )
00964 {
00965
00966 hps[i]->HNp() = hps[(i+1)%size]->HOp()->HNp();
00967 hps[(i+1)%size]->HOp()->HNp()->HPp() = hps[i];
00968 }
00969 }
00970 else
00971 {
00972 Allocator<MeshType>::DeleteHEdge( m, *hps[i] );
00973 Allocator<MeshType>::DeleteHEdge( m, *(hps[i]->HOp()) );
00974
00975 if(MeshType::HEdgeType::HasHEAdjacency())
00976 Allocator<MeshType>::DeleteEdge( m, *(hps[i]->HEp()) );
00977
00978 if( !hps[(i+size-1)%size]->HOp()->HFp() )
00979 {
00980 hps[i]->HOp()->HNp()->HPp() = hps[(i+size-1)%size]->HOp()->HPp();
00981 hps[(i+size-1)%size]->HOp()->HPp()->HNp() = hps[i]->HOp()->HNp();
00982 }
00983
00984 }
00985
00986 }
00987
00988 for( int i = 0; i< size; i++ )
00989 {
00990 if( hps[i]->HVp()->VHp()->IsD() )
00991 {
00992 if( !hps[i]->IsD() )
00993 hps[i]->HVp()->VHp() = hps[i];
00994
00995 else if( !hps[(i+size-1)%size]->IsD() )
00996 hps[i]->HVp()->VHp() = hps[(i+size-1)%size]->HOp();
00997
00998 else
00999 {
01000 bool manifold = true;
01001
01002 Pos<MeshType> p(hps[i]->HVp()->VHp(), true);
01003
01004 p.HE()->SetV();
01005
01006 p.FlipE();
01007 p.FlipF();
01008
01009 while( !p.HE()->IsV() )
01010 {
01011 if( !p.HE()->IsD() )
01012 {
01013 manifold = false;
01014 hps[i]->HVp()->VHp() = p.HE();
01015 break;
01016 }
01017
01018 p.FlipE();
01019 p.FlipF();
01020 }
01021
01022 p.HE()->ClearV();
01023
01024 if(manifold)
01025 hps[i]->HVp()->VHp() = NULL;
01026
01027 }
01028 }
01029
01030 }
01031
01032 Allocator<MeshType>::DeleteFace(m,*fp);
01033
01034 }
01035
01046 static bool can_add_hedge( vector<VertexPointer> &vps, vector<HEdgePointer> &hps )
01047 {
01048
01049 unsigned int i = hps.size();
01050
01051 assert( i < vps.size() );
01052
01053 HEdgePointer he = vps[i]->VHp();
01054
01055 if(!he)
01056 {
01057 hps.push_back(NULL);
01058 return true;
01059 }
01060 else
01061 {
01062 bool disconnected = false;
01063
01064 bool hasEdge = false;
01065
01066 unsigned int size = vps.size();
01067
01068 Pos<MeshType> p(he, false);
01069
01070 he->SetV();
01071
01072 while(p.V() != vps[(i+1)%size])
01073 {
01074 if(!hasEdge)
01075 hasEdge= ( find( vps.begin(), vps.end(), p.V()) != (vps.end() ) );
01076
01077 p.FlipV();
01078
01079 p.FlipE();
01080 p.FlipF();
01081
01082 p.FlipV();
01083
01084 if(p.HE()->IsV())
01085 {
01086 disconnected = true;
01087 break;
01088 }
01089
01090 }
01091
01092 he->ClearV();
01093
01094 if(disconnected)
01095 {
01096 hps.push_back(NULL);
01097
01098
01099 return hasEdge;
01100 }
01101
01102 else
01103 {
01104
01105 while( (p.V() == vps[(i+1)%size]) && (i < size) )
01106 {
01107 hps.push_back( p.HE() );
01108
01109 if(p.HE()->HFp() != NULL)
01110 return false;
01111
01112 i++;
01113 p.FlipE();
01114 p.FlipV();
01115 }
01116 return true;
01117 }
01118 }
01119 }
01120
01121 public:
01130 static bool can_remove_face(FacePointer fp)
01131 {
01132
01133 assert(fp);
01134 assert(!fp->IsD());
01135
01136 Pos<MeshType> p(fp->FHp(), true);
01137
01138 do
01139 {
01140 vector<FacePointer> incident_faces = get_incident_faces( p.V() );
01141
01142 unsigned int size = incident_faces.size();
01143
01144 if(size > 2)
01145 {
01146 for(unsigned int i = 0; i < size; i++)
01147 {
01148 if(incident_faces[i] == NULL)
01149 if(incident_faces[(i+1)%size] != fp && incident_faces[((i+size)-1)%size] != fp )
01150 return false;
01151 }
01152 }
01153
01154 p.FlipV();
01155 p.FlipE();
01156
01157 }while( p.HE() != fp->FHp() );
01158
01159 return true;
01160 }
01161
01170 static bool check_diagonal_collapse_quad(HEdgePointer hp)
01171 {
01172
01173 assert(hp);
01174 assert(hp->HFp());
01175 assert(hp->HFp()->VN() == 4);
01176 assert(!hp->IsD());
01177
01178 vector<FacePointer> faces;
01179
01180 HEdgePointer hopp = hp->HNp()->HNp();
01181 vector<FacePointer> faces1 = get_incident_faces(hp->HVp(), hp);
01182 vector<FacePointer> faces2 = get_incident_faces(hp->HNp()->HNp()->HVp(), hopp);
01183
01184 faces.assign(faces1.begin()+1, faces1.end());
01185 faces.assign(faces2.begin()+1, faces2.end());
01186
01187
01188
01189
01190 unsigned int size = faces.size();
01191 bool null_face = false;
01192
01193
01194
01195 if(size > 2)
01196 {
01197 for(unsigned int i = 0; i < size; i++)
01198 {
01199 if(faces[i] == NULL)
01200 {
01201 if(faces[(i+1)%size] != NULL && faces[((i+size)-1)%size] != NULL )
01202 {
01203 if(null_face)
01204 return false;
01205
01206 null_face=true;
01207 }
01208 }
01209 }
01210 }
01211
01212
01213
01214
01215
01216
01217 set<VertexPointer> set1;
01218 set<VertexPointer> set2;
01219
01220 vector<VertexPointer> vect1 = getVertices(hp->HVp());
01221 vector<VertexPointer> vect2 = getVertices(hp->HNp()->HNp()->HVp());
01222
01223 set1.insert(vect1.begin(), vect1.end());
01224 set2.insert(vect2.begin(), vect2.end());
01225
01226 size = vect1.size();
01227 if(vect2.size() < size)
01228 size = vect2.size();
01229
01230 vector<VertexPointer> intersection(size);
01231
01232 typename vector<VertexPointer>::iterator it;
01233 it = set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), intersection.begin());
01234
01235 size = it- intersection.begin();
01236
01237 assert( size >= 2 );
01238
01239 return (size==2);
01240
01241
01242
01243 }
01244
01254 static bool is_nonManifold_vertex(MeshType &m, VertexPointer vp)
01255 {
01256 assert(vp);
01257 assert(!vp->IsD());
01258
01259 set<HEdgePointer> set1;
01260 for(HEdgeIterator hi = m.hedge.begin(); hi != m.hedge.end(); ++hi)
01261 {
01262 if(!(*hi).IsD() && (*hi).HVp() == vp)
01263 set1.insert(&(*hi));
01264 }
01265
01266
01267 vector<HEdgePointer> vect2 = get_incident_hedges(vp);
01268
01269 set<HEdgePointer> set2;
01270 set2.insert(vect2.begin(), vect2.end());
01271
01272 return !equal(set1.begin(), set1.end(), set2.begin());
01273
01274 }
01275
01284 static bool is_nonManifold_vertex(VertexPointer vp)
01285 {
01286 assert(vp);
01287 assert(!vp->IsD());
01288
01289 vector<FacePointer> faces = get_incident_faces(vp);
01290
01291 unsigned int size = faces.size();
01292 int null_count = 0;
01293
01294 if(size > 2)
01295 {
01296 for(unsigned int i = 0; i < size; i++)
01297 {
01298 if(faces[i] == NULL)
01299 {
01300 if(null_count > 0)
01301 return true;
01302 else
01303 null_count++;
01304 }
01305 }
01306 }
01307
01308 return false;
01309
01310 }
01311
01319 static VertexPointer opp_vert(HEdgePointer hp)
01320 {
01321 return hp->HOp()->HVp();
01322 }
01323
01331 static vector<VertexPointer> getVertices(VertexPointer vp)
01332 {
01333 assert(vp);
01334 assert(!vp->IsD());
01335
01336 HEdgePointer hp = vp->VHp();
01337
01338 vector<VertexPointer> ret;
01339
01340 if( !hp )
01341 return ret;
01342
01343 Pos<MeshType> p(hp);
01344
01345 do
01346 {
01347 if(p.F())
01348 {
01349 assert(!p.F()->IsD());
01350
01351 ret.push_back( opp_vert( p.HE() ) );
01352
01353 ret.push_back( opp_vert( p.HE()->HNp() ) );
01354
01355
01356 }
01357 p.FlipE();
01358 p.FlipF();
01359
01360 }while( p.HE() != hp);
01361
01362 return ret;
01363 }
01364
01365
01373 static set<FacePointer> getFaces(VertexPointer vp)
01374 {
01375 assert(vp);
01376 assert(!vp->IsD());
01377
01378 set<FacePointer> ret;
01379
01380 vector<VertexPointer> vertices = getVertices(vp);
01381
01382 for(typename vector<VertexPointer>::iterator vi = vertices.begin(); vi!= vertices.end(); ++vi)
01383 {
01384 vector<FacePointer> incident_faces = get_incident_faces(*vi);
01385 ret.insert(incident_faces.begin(), incident_faces.end());
01386 }
01387
01388 return ret;
01389
01390 }
01391
01392
01401 static bool is_singlet_quad(FacePointer fp)
01402 {
01403 assert(fp);
01404 assert(fp->FHp());
01405 assert(!fp->IsD());
01406
01407 Pos<MeshType> p( fp->FHp() );
01408
01409 do
01410 {
01411 if( vertex_valence(p.V()) == 1 )
01412 return true;
01413
01414 p.FlipV();
01415 p.FlipE();
01416
01417 }while(p.HE() != fp->FHp());
01418
01419 return false;
01420
01421 }
01422
01431 static vector<VertexPointer> getVertices(FacePointer fp, HEdgePointer starting_he = NULL)
01432 {
01433 assert(fp);
01434 assert(!fp->IsD());
01435
01436 if(!starting_he)
01437 starting_he = fp->FHp();
01438
01439 assert( starting_he->HFp() == fp );
01440
01441 Pos<MeshType> p( starting_he, true );
01442
01443 vector<VertexPointer> ret;
01444
01445
01446 do
01447 {
01448 assert(!(p.V()->IsD()));
01449
01450 ret.push_back( p.V() );
01451
01452 p.FlipV();
01453 p.FlipE();
01454
01455 assert(ret.size() <= (unsigned int)(fp->VN()));
01456
01457 }while(p.HE() != starting_he);
01458
01459 return ret;
01460
01461 }
01462
01463 protected:
01472 static vector<HEdgePointer> getHEdges(FacePointer fp, HEdgePointer starting_he = NULL)
01473 {
01474 assert(fp);
01475 assert(!fp->IsD());
01476
01477 if(starting_he)
01478 assert( starting_he->HFp() == fp );
01479 else
01480 starting_he = fp->FHp();
01481
01482 Pos<MeshType> p( starting_he, true );
01483
01484 vector<HEdgePointer> ret;
01485
01486 do
01487 {
01488 ret.push_back( p.HE() );
01489
01490 p.FlipV();
01491 p.FlipE();
01492
01493 assert(ret.size() <= (unsigned int) (fp->VN()));
01494
01495 }while(p.HE() != starting_he);
01496
01497 return ret;
01498
01499 }
01500
01501 public:
01502
01511 static vector<FacePointer> get_incident_faces(VertexPointer vp, HEdgePointer starting_he = NULL)
01512 {
01513 assert(vp);
01514 assert(!vp->IsD());
01515
01516 if(starting_he)
01517 assert( starting_he->HVp() == vp );
01518 else
01519 starting_he = vp->VHp();
01520
01521 vector<FacePointer> ret;
01522
01523 if(!starting_he)
01524 return ret;
01525
01526 Pos<MeshType> p( starting_he, true );
01527
01528 do
01529 {
01530 ret.push_back( p.F() );
01531
01532 p.FlipE();
01533 p.FlipF();
01534
01535 }while(p.HE() != starting_he);
01536
01537 return ret;
01538
01539 }
01540
01541
01542 static vector<FacePointer> get_adjacent_faces(FacePointer fp)
01543 {
01544 assert(fp);
01545 assert(!fp->IsD());
01546
01547 vector<FacePointer> ret;
01548
01549 Pos<MeshType> p( fp->FHp() );
01550 assert(p.F() == fp);
01551
01552 do
01553 {
01554 p.FlipF();
01555 ret.push_back( p.F() );
01556 p.FlipF();
01557
01558 p.FlipV();
01559 p.FlipE();
01560
01561 } while(p.HE() != fp->FHp());
01562
01563 return ret;
01564
01565 }
01566
01575 static vector<HEdgePointer> get_incident_hedges(VertexPointer vp, HEdgePointer starting_he = NULL)
01576 {
01577 assert(vp);
01578 assert(!vp->IsD());
01579
01580 if(starting_he)
01581 assert( starting_he->HVp() == vp );
01582 else
01583 starting_he = vp->VHp();
01584
01585 vector<HEdgePointer> ret;
01586
01587 if(!starting_he)
01588 return ret;
01589
01590 Pos<MeshType> p( starting_he, true );
01591
01592 do
01593 {
01594 assert(!p.HE()->IsD());
01595
01596 ret.push_back( p.HE() );
01597
01598 p.FlipE();
01599 p.FlipF();
01600
01601
01602 }while(p.HE() != starting_he);
01603
01604 return ret;
01605
01606 }
01607
01616 static bool has_doublet_quad(FacePointer fp)
01617 {
01618 return ( !find_doublet_hedges_quad(fp).empty() );
01619 }
01620
01628 static vector<HEdgePointer> find_doublet_hedges_quad(FacePointer fp)
01629 {
01630 assert(fp);
01631 assert(fp->FHp());
01632 assert(!fp->IsD());
01633
01634 vector<HEdgePointer> ret;
01635
01636 Pos<MeshType> p( fp->FHp(), true );
01637
01638 do
01639 {
01640
01641 if(vertex_valence(p.V()) == 2 && !isBorderVertex(p.V()))
01642 ret.push_back(p.HE());
01643
01644 assert(ret.size() <= 4);
01645
01646 p.FlipV();
01647 p.FlipE();
01648
01649 }while(p.HE() != fp->FHp());
01650
01651 return ret;
01652
01653 }
01654
01663 static bool isBorderVertex(VertexPointer vp)
01664 {
01665 assert(vp);
01666 assert(!vp->IsD());
01667
01668 if( !(vp->VHp()) )
01669 return true;
01670
01671 Pos<MeshType> p( vp->VHp() );
01672
01673 do
01674 {
01675 if(!p.F())
01676 return true;
01677
01678 p.FlipE();
01679 p.FlipF();
01680
01681 }while(p.HE() != vp->VHp());
01682
01683 return false;
01684 }
01685
01693 static int vertex_valence(VertexPointer vp)
01694 {
01695 assert(vp);
01696 assert(!vp->IsD());
01697
01698 if( !(vp->VHp()) )
01699 return 0;
01700
01701 int ret = 0;
01702
01703 Pos<MeshType> p( vp->VHp() );
01704
01705 do
01706 {
01707 assert(!p.HE()->IsD());
01708 ret++;
01709
01710 p.FlipE();
01711 p.FlipF();
01712
01713 }while(p.HE() != vp->VHp());
01714
01715 return ret;
01716 }
01717
01725 protected:
01726 static void change_vertex(VertexPointer old_vp, VertexPointer new_vp)
01727 {
01728 assert(old_vp);
01729 assert(new_vp);
01730 assert(old_vp != new_vp);
01731 assert(!old_vp->IsD());
01732
01733 Pos<MeshType> p(old_vp->VHp(),true);
01734
01735 p.HE()->SetV();
01736
01737 do
01738 {
01739 p.HE()->HVp() = new_vp;
01740
01741 p.FlipE();
01742 p.FlipF();
01743
01744 }while( !p.HE()->IsV() );
01745
01746 p.HE()->ClearV();
01747
01748 if( !new_vp->VHp() )
01749 new_vp->VHp() = old_vp->VHp();
01750
01751 }
01752
01753 };
01754
01755 }
01756 }
01757
01758 #endif // VCG_HEDGE_TOPOLOGY
01759