00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #ifndef __VCGLIB_CLEAN
00025 #define __VCGLIB_CLEAN
00026
00027
00028 #include <map>
00029 #include <algorithm>
00030 #include <stack>
00031
00032
00033 #include <vcg/simplex/face/pos.h>
00034 #include <vcg/simplex/face/topology.h>
00035 #include <vcg/complex/trimesh/base.h>
00036 #include <vcg/complex/trimesh/closest.h>
00037 #include <vcg/space/index/grid_static_ptr.h>
00038 #include <vcg/space/index/spatial_hashing.h>
00039 #include <vcg/complex/trimesh/allocate.h>
00040 #include <vcg/complex/trimesh/update/selection.h>
00041 #include <vcg/complex/trimesh/update/flag.h>
00042 #include <vcg/complex/trimesh/update/normal.h>
00043 #include <vcg/complex/trimesh/update/topology.h>
00044 #include <vcg/space/triangle3.h>
00045
00046
00047 namespace vcg {
00048 namespace tri{
00049 template <class ConnectedMeshType>
00050 class ConnectedIterator
00051 {
00052 public:
00053 typedef ConnectedMeshType MeshType;
00054 typedef typename MeshType::VertexType VertexType;
00055 typedef typename MeshType::VertexPointer VertexPointer;
00056 typedef typename MeshType::VertexIterator VertexIterator;
00057 typedef typename MeshType::ScalarType ScalarType;
00058 typedef typename MeshType::FaceType FaceType;
00059 typedef typename MeshType::FacePointer FacePointer;
00060 typedef typename MeshType::FaceIterator FaceIterator;
00061 typedef typename MeshType::ConstFaceIterator ConstFaceIterator;
00062 typedef typename MeshType::FaceContainer FaceContainer;
00063
00064
00065 public:
00066 void operator ++()
00067 {
00068 FacePointer fpt=sf.top();
00069 sf.pop();
00070 for(int j=0;j<3;++j)
00071 if( !face::IsBorder(*fpt,j) )
00072 {
00073 FacePointer l=fpt->FFp(j);
00074 if( !tri::IsMarked(*mp,l) )
00075 {
00076 tri::Mark(*mp,l);
00077 sf.push(l);
00078 }
00079 }
00080 }
00081
00082 void start(MeshType &m, FacePointer p)
00083 {
00084 mp=&m;
00085 while(!sf.empty()) sf.pop();
00086 UnMarkAll(m);
00087 assert(p);
00088 assert(!p->IsD());
00089 tri::Mark(m,p);
00090 sf.push(p);
00091 }
00092 bool completed() {
00093 return sf.empty();
00094 }
00095
00096 FacePointer operator *()
00097 {
00098 return sf.top();
00099 }
00100 private:
00101 std::stack<FacePointer> sf;
00102 MeshType *mp;
00103 };
00104
00105
00107
00109
00110 template <class CleanMeshType>
00111 class Clean
00112 {
00113
00114 public:
00115 typedef CleanMeshType MeshType;
00116 typedef typename MeshType::VertexType VertexType;
00117 typedef typename MeshType::VertexPointer VertexPointer;
00118 typedef typename MeshType::VertexIterator VertexIterator;
00119 typedef typename MeshType::ConstVertexIterator ConstVertexIterator;
00120 typedef typename MeshType::ScalarType ScalarType;
00121 typedef typename MeshType::FaceType FaceType;
00122 typedef typename MeshType::FacePointer FacePointer;
00123 typedef typename MeshType::FaceIterator FaceIterator;
00124 typedef typename MeshType::ConstFaceIterator ConstFaceIterator;
00125 typedef typename MeshType::FaceContainer FaceContainer;
00126 typedef typename vcg::Box3<ScalarType> Box3Type;
00127
00128 typedef GridStaticPtr<FaceType, ScalarType > TriMeshGrid;
00129 typedef Point3<ScalarType> Point3x;
00130
00131
00132
00133
00134
00135
00136
00137
00138 class RemoveDuplicateVert_Compare{
00139 public:
00140 inline bool operator()(VertexPointer const &a, VertexPointer const &b)
00141 {
00142 return (*a).cP() < (*b).cP();
00143 }
00144 };
00145
00146
00151 static int RemoveDuplicateVertex( MeshType & m, bool RemoveDegenerateFlag=true)
00152 {
00153 if(m.vert.size()==0 || m.vn==0) return 0;
00154
00155 std::map<VertexPointer, VertexPointer> mp;
00156 size_t i,j;
00157 VertexIterator vi;
00158 int deleted=0;
00159 int k=0;
00160 size_t num_vert = m.vert.size();
00161 std::vector<VertexPointer> perm(num_vert);
00162 for(vi=m.vert.begin(); vi!=m.vert.end(); ++vi, ++k)
00163 perm[k] = &(*vi);
00164
00165 RemoveDuplicateVert_Compare c_obj;
00166
00167 std::sort(perm.begin(),perm.end(),c_obj);
00168
00169 j = 0;
00170 i = j;
00171 mp[perm[i]] = perm[j];
00172 ++i;
00173 for(;i!=num_vert;)
00174 {
00175 if( (! (*perm[i]).IsD()) &&
00176 (! (*perm[j]).IsD()) &&
00177 (*perm[i]).P() == (*perm[j]).cP() )
00178 {
00179 VertexPointer t = perm[i];
00180 mp[perm[i]] = perm[j];
00181 ++i;
00182 Allocator<MeshType>::DeleteVertex(m,*t);
00183 deleted++;
00184 }
00185 else
00186 {
00187 j = i;
00188 ++i;
00189 }
00190 }
00191 FaceIterator fi;
00192 for(fi = m.face.begin(); fi!=m.face.end(); ++fi)
00193 if( !(*fi).IsD() )
00194 for(k = 0; k < 3; ++k)
00195 if( mp.find( (typename MeshType::VertexPointer)(*fi).V(k) ) != mp.end() )
00196 {
00197 (*fi).V(k) = &*mp[ (*fi).V(k) ];
00198 }
00199
00200 if(RemoveDegenerateFlag) RemoveDegenerateFace(m);
00201 return deleted;
00202 }
00203
00204 class SortedTriple
00205 {
00206 public:
00207 SortedTriple() {}
00208 SortedTriple(unsigned int v0, unsigned int v1, unsigned int v2,FacePointer _fp)
00209 {
00210 v[0]=v0;v[1]=v1;v[2]=v2;
00211 fp=_fp;
00212 std::sort(v,v+3);
00213 }
00214 bool operator < (const SortedTriple &p) const
00215 {
00216 return (v[2]!=p.v[2])?(v[2]<p.v[2]):
00217 (v[1]!=p.v[1])?(v[1]<p.v[1]):
00218 (v[0]<p.v[0]); }
00219
00220 bool operator == (const SortedTriple &s) const
00221 {
00222 if( (v[0]==s.v[0]) && (v[1]==s.v[1]) && (v[2]==s.v[2]) ) return true;
00223 return false;
00224 }
00225
00226 unsigned int v[3];
00227 FacePointer fp;
00228 };
00229
00230
00236 static int RemoveDuplicateFace( MeshType & m)
00237 {
00238 FaceIterator fi;
00239 std::vector<SortedTriple> fvec;
00240 for(fi=m.face.begin();fi!=m.face.end();++fi)
00241 if(!(*fi).IsD())
00242 {
00243 fvec.push_back(SortedTriple( tri::Index(m,(*fi).V(0)),
00244 tri::Index(m,(*fi).V(1)),
00245 tri::Index(m,(*fi).V(2)),
00246 &*fi));
00247 }
00248 assert (size_t(m.fn) == fvec.size());
00249
00250 std::sort(fvec.begin(),fvec.end());
00251 int total=0;
00252 for(size_t i=0;i<fvec.size()-1;++i)
00253 {
00254 if(fvec[i]==fvec[i+1])
00255 {
00256 total++;
00257 tri::Allocator<MeshType>::DeleteFace(m, *(fvec[i].fp) );
00258
00259 }
00260 }
00261 return total;
00262 }
00267 static int RemoveUnreferencedVertex( MeshType& m, bool DeleteVertexFlag=true)
00268 {
00269 FaceIterator fi;
00270 VertexIterator vi;
00271 int referredBit = VertexType::NewBitFlag();
00272
00273 int j;
00274 int deleted = 0;
00275
00276 for(vi=m.vert.begin();vi!=m.vert.end();++vi)
00277 (*vi).ClearUserBit(referredBit);
00278
00279 for(fi=m.face.begin();fi!=m.face.end();++fi)
00280 if( !(*fi).IsD() )
00281 for(j=0;j<3;++j)
00282 (*fi).V(j)->SetUserBit(referredBit);
00283
00284 for(vi=m.vert.begin();vi!=m.vert.end();++vi)
00285 if( (!(*vi).IsD()) && (!(*vi).IsUserBit(referredBit)))
00286 {
00287 if(DeleteVertexFlag) Allocator<MeshType>::DeleteVertex(m,*vi);
00288 ++deleted;
00289 }
00290 VertexType::DeleteBitFlag(referredBit);
00291 return deleted;
00292 }
00293
00298 static int RemoveDegenerateVertex(MeshType& m)
00299 {
00300 VertexIterator vi;
00301 int count_vd = 0;
00302
00303 for(vi=m.vert.begin(); vi!=m.vert.end();++vi)
00304 if(math::IsNAN( (*vi).P()[0]) ||
00305 math::IsNAN( (*vi).P()[1]) ||
00306 math::IsNAN( (*vi).P()[2]) )
00307 {
00308 count_vd++;
00309 Allocator<MeshType>::DeleteVertex(m,*vi);
00310 }
00311
00312 FaceIterator fi;
00313 int count_fd = 0;
00314
00315 for(fi=m.face.begin(); fi!=m.face.end();++fi)
00316 if(!(*fi).IsD())
00317 if( (*fi).V(0)->IsD() ||
00318 (*fi).V(1)->IsD() ||
00319 (*fi).V(2)->IsD() )
00320 {
00321 count_fd++;
00322 Allocator<MeshType>::DeleteFace(m,*fi);
00323 }
00324 return count_vd;
00325 }
00326
00335 static int RemoveDegenerateFace(MeshType& m)
00336 {
00337 FaceIterator fi;
00338 int count_fd = 0;
00339
00340 for(fi=m.face.begin(); fi!=m.face.end();++fi)
00341 if(!(*fi).IsD())
00342 {
00343 if((*fi).V(0) == (*fi).V(1) ||
00344 (*fi).V(0) == (*fi).V(2) ||
00345 (*fi).V(1) == (*fi).V(2) )
00346 {
00347 count_fd++;
00348 Allocator<MeshType>::DeleteFace(m,*fi);
00349 }
00350 }
00351 return count_fd;
00352 }
00353
00354 static int RemoveNonManifoldVertex(MeshType& m)
00355 {
00356
00357 CountNonManifoldVertexFF(m,true);
00358
00359 tri::UpdateSelection<MeshType>::FaceFromVertexLoose(m);
00360 int count_removed = 0;
00361 FaceIterator fi;
00362 for(fi=m.face.begin(); fi!=m.face.end();++fi)
00363 if(!(*fi).IsD() && (*fi).IsS())
00364 Allocator<MeshType>::DeleteFace(m,*fi);
00365 VertexIterator vi;
00366 for(vi=m.vert.begin(); vi!=m.vert.end();++vi)
00367 if(!(*vi).IsD() && (*vi).IsS()) {
00368 ++count_removed;
00369 Allocator<MeshType>::DeleteVertex(m,*vi);
00370 }
00371 return count_removed;
00372 }
00373
00374
00375 static int RemoveNonManifoldFace(MeshType& m)
00376 {
00377 FaceIterator fi;
00378 int count_fd = 0;
00379 std::vector<FacePointer> ToDelVec;
00380
00381 for(fi=m.face.begin(); fi!=m.face.end();++fi)
00382 if (!fi->IsD())
00383 {
00384 if ((!IsManifold(*fi,0))||
00385 (!IsManifold(*fi,1))||
00386 (!IsManifold(*fi,2)))
00387 ToDelVec.push_back(&*fi);
00388 }
00389
00390 for(size_t i=0;i<ToDelVec.size();++i)
00391 {
00392 if(!ToDelVec[i]->IsD())
00393 {
00394 FaceType &ff= *ToDelVec[i];
00395 if ((!IsManifold(ff,0))||
00396 (!IsManifold(ff,1))||
00397 (!IsManifold(ff,2)))
00398 {
00399 for(int j=0;j<3;++j)
00400 if(!face::IsBorder<FaceType>(ff,j))
00401 vcg::face::FFDetach<FaceType>(ff,j);
00402
00403 Allocator<MeshType>::DeleteFace(m,ff);
00404 count_fd++;
00405 }
00406 }
00407 }
00408 return count_fd;
00409 }
00410
00411
00412
00413
00414
00415
00416
00417 template<bool Selected>
00418 static int RemoveFaceOutOfRangeAreaSel(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)())
00419 {
00420 FaceIterator fi;
00421 int count_fd = 0;
00422 MinAreaThr*=2;
00423 MaxAreaThr*=2;
00424 for(fi=m.face.begin(); fi!=m.face.end();++fi)
00425 if(!(*fi).IsD())
00426 if(!Selected || (*fi).IsS())
00427 {
00428 const ScalarType doubleArea=DoubleArea<FaceType>(*fi);
00429 if((doubleArea<=MinAreaThr) || (doubleArea>=MaxAreaThr) )
00430 {
00431 Allocator<MeshType>::DeleteFace(m,*fi);
00432 count_fd++;
00433 }
00434 }
00435 return count_fd;
00436 }
00437
00438
00439 static int RemoveZeroAreaFace(MeshType& m) { return RemoveFaceOutOfRangeArea(m);}
00440
00441
00442 static int RemoveFaceOutOfRangeArea(MeshType& m, ScalarType MinAreaThr=0, ScalarType MaxAreaThr=(std::numeric_limits<ScalarType>::max)())
00443 {
00444 return RemoveFaceOutOfRangeAreaSel<false>(m,MinAreaThr,MaxAreaThr);
00445 }
00446
00450 static bool IsBitQuadOnly(const MeshType &m)
00451 {
00452 typedef typename MeshType::FaceType F;
00453 if (!m.HasPerFaceFlags()) return false;
00454 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
00455 unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
00456 if ( tmp != F::FAUX0 && tmp != F::FAUX1 && tmp != F::FAUX2) return false;
00457 }
00458 return true;
00459 }
00460
00461
00465 static bool IsBitTriOnly(const MeshType &m)
00466 {
00467 if (!m.HasPerFaceFlags()) return true;
00468 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) {
00469 if (
00470 !fi->IsD() && fi->IsAnyF()
00471 ) return false;
00472 }
00473 return true;
00474 }
00475
00476 static bool IsBitPolygonal(const MeshType &m){
00477 return !IsBitTriOnly(m);
00478 }
00479
00483 static bool IsBitTriQuadOnly(const MeshType &m)
00484 {
00485 typedef typename MeshType::FaceType F;
00486 if (!m.HasPerFaceFlags()) return false;
00487 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
00488 unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
00489 if ( tmp!=F::FAUX0 && tmp!=F::FAUX1 && tmp!=F::FAUX2 && tmp!=0 ) return false;
00490 }
00491 return true;
00492 }
00493
00497 static int CountBitQuads(const MeshType &m)
00498 {
00499 if (!m.HasPerFaceFlags()) return 0;
00500 typedef typename MeshType::FaceType F;
00501 int count=0;
00502 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
00503 unsigned int tmp = fi->Flags()&(F::FAUX0|F::FAUX1|F::FAUX2);
00504 if ( tmp==F::FAUX0 || tmp==F::FAUX1 || tmp==F::FAUX2) count++;
00505 }
00506 return count / 2;
00507 }
00508
00512 static int CountBitTris(const MeshType &m)
00513 {
00514 if (!m.HasPerFaceFlags()) return m.fn;
00515 int count=0;
00516 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
00517 if (!(fi->IsAnyF())) count++;
00518 }
00519 return count;
00520 }
00521
00525 static int CountBitPolygons(const MeshType &m)
00526 {
00527 if (!m.HasPerFaceFlags()) return m.fn;
00528 typedef typename MeshType::FaceType F;
00529 int count = 0;
00530 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD()) {
00531 if (fi->IsF(0)) count++;
00532 if (fi->IsF(1)) count++;
00533 if (fi->IsF(2)) count++;
00534 }
00535 return m.fn - count/2;
00536 }
00537
00549 static int CountBitLargePolygons(MeshType &m)
00550 {
00551
00552 UpdateFlags<MeshType>::VertexSetV(m);
00553
00554 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
00555 if (!fi->IsD())
00556 for(int i=0;i<3;++i) fi->V(i)->ClearV();
00557
00558
00559
00560 if (!m.HasPerFaceFlags()) return m.fn;
00561 typedef typename MeshType::FaceType F;
00562 int countE = 0;
00563 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
00564 if (!fi->IsD()) {
00565 for(int i=0;i<3;++i)
00566 {
00567 if (fi->IsF(i))
00568 countE++;
00569 else
00570 {
00571 fi->V0(i)->SetV();
00572 fi->V1(i)->SetV();
00573 }
00574 }
00575 }
00576
00577
00578 int countV = 0;
00579 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
00580 if (!vi->IsD() && !vi->IsV()) countV++;
00581
00582 return m.fn - countE/2 + countV ;
00583 }
00584
00585
00593 static bool HasConsistentPerFaceFauxFlag(const MeshType &m)
00594 {
00595 assert(m.HasPerFaceFlags());
00596 assert(m.HasFFTopology());
00597
00598 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
00599 if(!(*fi).IsD())
00600 for (int k=0; k<3; k++)
00601 if( fi->IsF(k) != fi->cFFp(k)->IsF(fi->cFFi(k)) ) {
00602 return false;
00603 }
00604
00605
00606
00607 return true;
00608 }
00609
00610 static bool HasConsistentEdges(const MeshType &m)
00611 {
00612 assert(m.HasPerFaceFlags());
00613
00614 for (ConstFaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
00615 if(!(*fi).IsD())
00616 for (int k=0; k<3; k++)
00617 {
00618 VertexType *v0=(*fi).V(0);
00619 VertexType *v1=(*fi).V(1);
00620 VertexType *v2=(*fi).V(2);
00621 if ((v0==v1)||(v0==v2)||(v1==v2))
00622 return false;
00623 }
00624
00625 return true;
00626 }
00627
00628
00629
00636 static int CountNonManifoldEdgeFF( MeshType & m, bool SelectFlag=false)
00637 {
00638 int nmfBit[3];
00639 nmfBit[0]= FaceType::NewBitFlag();
00640 nmfBit[1]= FaceType::NewBitFlag();
00641 nmfBit[2]= FaceType::NewBitFlag();
00642
00643
00644 UpdateFlags<MeshType>::FaceClear(m,nmfBit[0]+nmfBit[1]+nmfBit[2]);
00645
00646 if(SelectFlag){
00647 UpdateSelection<MeshType>::ClearVertex(m);
00648 UpdateSelection<MeshType>::ClearFace(m);
00649 }
00650 assert(tri::HasFFAdjacency(m));
00651
00652 int edgeCnt = 0;
00653 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
00654 {
00655 if (!fi->IsD())
00656 {
00657 for(int i=0;i<3;++i)
00658 if(!IsManifold(*fi,i))
00659 {
00660 if(!(*fi).IsUserBit(nmfBit[i]))
00661 {
00662 ++edgeCnt;
00663 if(SelectFlag)
00664 {
00665 (*fi).V0(i)->SetS();
00666 (*fi).V1(i)->SetS();
00667 }
00668
00669 face::Pos<FaceType> nmf(&*fi,i);
00670 do
00671 {
00672 if(SelectFlag) nmf.F()->SetS();
00673 nmf.F()->SetUserBit(nmfBit[nmf.E()]);
00674 nmf.NextF();
00675 }
00676 while(nmf.f != &*fi);
00677 }
00678 }
00679 }
00680 }
00681 return edgeCnt;
00682 }
00683
00688 static int CountNonManifoldVertexFF( MeshType & m, bool selectVert = true )
00689 {
00690 assert(tri::HasFFAdjacency(m));
00691 UpdateSelection<MeshType>::ClearVertex(m);
00692
00693 int nonManifoldCnt=0;
00694 SimpleTempData<typename MeshType::VertContainer, int > TD(m.vert,0);
00695
00696
00697 FaceIterator fi;
00698 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
00699 {
00700 TD[(*fi).V(0)]++;
00701 TD[(*fi).V(1)]++;
00702 TD[(*fi).V(2)]++;
00703 }
00704
00705 tri::UpdateFlags<MeshType>::VertexClearV(m);
00706
00707
00708 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
00709 {
00710 for(int i=0;i<3;++i)
00711 if (!IsManifold(*fi,i)) {
00712 (*fi).V0(i)->SetV();
00713 (*fi).V1(i)->SetV();
00714 }
00715 }
00716
00717
00718 for (fi = m.face.begin(); fi != m.face.end(); ++fi) if (!fi->IsD())
00719 {
00720 for(int i=0;i<3;i++) if(!(*fi).V(i)->IsV()){
00721 (*fi).V(i)->SetV();
00722 face::Pos<FaceType> pos(&(*fi),i);
00723
00724 int starSizeFF = pos.NumberOfIncidentFaces();
00725
00726 if (starSizeFF != TD[(*fi).V(i)])
00727 {
00728 if(selectVert) (*fi).V(i)->SetS();
00729 nonManifoldCnt++;
00730 }
00731 }
00732 }
00733 return nonManifoldCnt;
00734 }
00735
00736 static void CountEdges( MeshType & m, int &count_e, int &boundary_e )
00737 {
00738 count_e=0;
00739 boundary_e=0;
00740 UpdateFlags<MeshType>::FaceClearV(m);
00741 FaceIterator fi;
00742 vcg::face::Pos<FaceType> he;
00743 vcg::face::Pos<FaceType> hei;
00744 bool counted =false;
00745 for(fi=m.face.begin();fi!=m.face.end();fi++)
00746 {
00747 if(!((*fi).IsD()))
00748 {
00749 (*fi).SetV();
00750 count_e +=3;
00751 for(int j=0; j<3; j++)
00752 {
00753 if (face::IsBorder(*fi,j))
00754 boundary_e++;
00755 else if (IsManifold(*fi,j))
00756 {
00757 if((*fi).FFp(j)->IsV())
00758 count_e--;
00759 }
00760 else
00761 {
00762 hei.Set(&(*fi), j , fi->V(j));
00763 he=hei;
00764 he.NextF();
00765 while (he.f!=hei.f)
00766 {
00767 if (he.f->IsV())
00768 {
00769 counted=true;
00770 break;
00771 }
00772 else
00773 {
00774 he.NextF();
00775 }
00776 }
00777 if (counted)
00778 {
00779 count_e--;
00780 counted=false;
00781 }
00782 }
00783 }
00784 }
00785 }
00786 }
00787
00788
00789 static int CountHoles( MeshType & m)
00790 {
00791 int numholev=0;
00792 FaceIterator fi;
00793 FaceIterator gi;
00794 vcg::face::Pos<FaceType> he;
00795 vcg::face::Pos<FaceType> hei;
00796
00797 std::vector< std::vector<Point3x> > holes;
00798
00799 for(fi=m.face.begin();fi!=m.face.end();++fi)
00800 (*fi).ClearS();
00801 gi=m.face.begin(); fi=gi;
00802
00803 for(fi=m.face.begin();fi!=m.face.end();fi++)
00804 {
00805 for(int j=0;j<3;j++)
00806 {
00807 if(fi->V(j)->IsS()) continue;
00808
00809 if(face::IsBorder(*fi,j))
00810 {
00811 he.Set(&(*fi),j,fi->V(j));
00812 std::vector<Point3x> hole;
00813 hole.push_back(fi->P(j));
00814 numholev++;
00815 he.v->SetS();
00816 he.NextB();
00817
00818
00819 while(fi->V(j) != he.v)
00820 {
00821 Point3x newpoint = he.v->P();
00822 if(he.v->IsS())
00823 {
00824
00825 std::vector<Point3x> hole2;
00826 int index = static_cast<int>(find(hole.begin(),hole.end(),newpoint)
00827 - hole.begin());
00828 for(unsigned int i=index; i<hole.size(); i++)
00829 hole2.push_back(hole[i]);
00830
00831 hole.resize(index);
00832 if(hole2.size()!=0)
00833 holes.push_back(hole2);
00834 }
00835 hole.push_back(newpoint);
00836 numholev++;
00837 he.v->SetS();
00838 he.NextB();
00839 }
00840 holes.push_back(hole);
00841 }
00842 }
00843 }
00844 return static_cast<int>(holes.size());
00845 }
00846
00847
00848
00849
00850
00851 static int CountConnectedComponents(MeshType &m)
00852 {
00853 std::vector< std::pair<int,FacePointer> > CCV;
00854 return ConnectedComponents(m,CCV);
00855 }
00856
00857 static int ConnectedComponents(MeshType &m, std::vector< std::pair<int,FacePointer> > &CCV)
00858 {
00859 FaceIterator fi;
00860 FacePointer l;
00861 CCV.clear();
00862
00863 for(fi=m.face.begin();fi!=m.face.end();++fi)
00864 (*fi).ClearS();
00865
00866 int Compindex=0;
00867 std::stack<FacePointer> sf;
00868 FacePointer fpt=&*(m.face.begin());
00869 for(fi=m.face.begin();fi!=m.face.end();++fi)
00870 {
00871 if(!((*fi).IsD()) && !(*fi).IsS())
00872 {
00873 (*fi).SetS();
00874 CCV.push_back(std::make_pair(0,&*fi));
00875 sf.push(&*fi);
00876 while (!sf.empty())
00877 {
00878 fpt=sf.top();
00879 ++CCV.back().first;
00880 sf.pop();
00881 for(int j=0;j<3;++j)
00882 {
00883 if( !face::IsBorder(*fpt,j) )
00884 {
00885 l=fpt->FFp(j);
00886 if( !(*l).IsS() )
00887 {
00888 (*l).SetS();
00889 sf.push(l);
00890 }
00891 }
00892 }
00893 }
00894 Compindex++;
00895 }
00896 }
00897 assert(int(CCV.size())==Compindex);
00898 return Compindex;
00899 }
00900
00901
00933 static int MeshGenus(MeshType &m, int numholes, int numcomponents, int count_e)
00934 {
00935 int V = m.vn;
00936 int F = m.fn;
00937 int E = count_e;
00938 return -((V + F - E + numholes - 2 * numcomponents) / 2);
00939 }
00940
00952 static void IsRegularMesh(MeshType &m, bool &Regular, bool &Semiregular)
00953 {
00954
00955 assert(m.HasVFTopology());
00956
00957 Regular = true;
00958
00959 VertexIterator vi;
00960
00961
00962 for (vi = m.vert.begin(); vi != m.vert.end(); ++vi)
00963 {
00964 if (!vi->IsD())
00965 {
00966 face::Pos<FaceType> he((*vi).VFp(), &*vi);
00967 face::Pos<FaceType> ht = he;
00968
00969 int n=0;
00970 bool border=false;
00971 do
00972 {
00973 ++n;
00974 ht.NextE();
00975 if (ht.IsBorder())
00976 border=true;
00977 }
00978 while (ht != he);
00979
00980 if (border)
00981 n = n/2;
00982
00983 if ((n != 6)&&(!border && n != 4))
00984 {
00985 Regular = false;
00986 break;
00987 }
00988 }
00989 }
00990
00991 if (!Regular)
00992 Semiregular = false;
00993 else
00994 {
00995
00996 Semiregular = false;
00997 }
00998 }
00999
01000 static void IsOrientedMesh(MeshType &m, bool &Oriented, bool &Orientable)
01001 {
01002 assert(&Oriented != &Orientable);
01003
01004 assert(m.HasFFTopology());
01005
01006 Orientable = true;
01007 Oriented = true;
01008
01009
01010 FaceIterator fi;
01011 for (fi = m.face.begin(); fi != m.face.end(); ++fi)
01012 fi->ClearS();
01013
01014
01015 std::stack<FacePointer> faces;
01016
01017
01018 FacePointer fp,fpaux;
01019 int iaux;
01020 for (fi = m.face.begin(); fi != m.face.end(); ++fi)
01021 {
01022 if (!fi->IsD() && !fi->IsS())
01023 {
01024
01025 fi->SetS();
01026 faces.push(&(*fi));
01027
01028
01029 while (!faces.empty())
01030 {
01031 fp = faces.top();
01032 faces.pop();
01033
01034
01035 for (int j = 0; j < 3; j++)
01036 {
01037
01038 fpaux = fp->FFp(j);
01039 iaux = fp->FFi(j);
01040
01041 if (!fpaux->IsD() && fpaux != fp && face::IsManifold<FaceType>(*fp, j))
01042 {
01043 if (!CheckOrientation(*fpaux, iaux))
01044 {
01045 Oriented = false;
01046
01047 if (!fpaux->IsS())
01048 {
01049 face::SwapEdge<FaceType,true>(*fpaux, iaux);
01050 assert(CheckOrientation(*fpaux, iaux));
01051 }
01052 else
01053 {
01054 Orientable = false;
01055 break;
01056 }
01057 }
01058
01059
01060
01061 if (!fpaux->IsS())
01062 {
01063 fpaux->SetS();
01064 faces.push(fpaux);
01065 }
01066 }
01067 }
01068 }
01069 }
01070
01071 if (!Orientable) break;
01072 }
01073 }
01075 static void FlipMesh(MeshType &m, bool selected=false)
01076 {
01077 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi) if(!(*fi).IsD())
01078 if(!selected || (*fi).IsS())
01079 {
01080 face::SwapEdge<FaceType,false>((*fi), 0);
01081 if (HasPerWedgeTexCoord(m))
01082 std::swap((*fi).WT(0),(*fi).WT(1));
01083 }
01084 }
01085
01086
01087
01088 static int RemoveFaceFoldByFlip(MeshType &m, float normalThresholdDeg=175, bool repeat=true)
01089 {
01090 assert(m.HasFFTopology());
01091 assert(m.HasPerVertexMark());
01092
01093 int count, total = 0;
01094
01095 do {
01096 tri::UpdateTopology<MeshType>::FaceFace(m);
01097 tri::UnMarkAll(m);
01098 count = 0;
01099
01100 ScalarType NormalThrRad = math::ToRad(normalThresholdDeg);
01101 ScalarType eps = 0.0001;
01102
01103 for(FaceIterator fi=m.face.begin();fi!= m.face.end();++fi ) if(!(*fi).IsV())
01104 { Point3<ScalarType> NN = vcg::NormalizedNormal((*fi));
01105 if( vcg::Angle(NN,vcg::NormalizedNormal(*(*fi).FFp(0))) > NormalThrRad &&
01106 vcg::Angle(NN,vcg::NormalizedNormal(*(*fi).FFp(1))) > NormalThrRad &&
01107 vcg::Angle(NN,vcg::NormalizedNormal(*(*fi).FFp(2))) > NormalThrRad )
01108 {
01109 (*fi).SetS();
01110
01111
01112 for(int i=0;i<3;i++)
01113 {
01114 Point3<ScalarType> &p=(*fi).P2(i);
01115 Point3<ScalarType> L;
01116 bool ret = vcg::InterpolationParameters((*(*fi).FFp(i)),vcg::Normal(*(*fi).FFp(i)),p,L);
01117 if(ret && L[0]>eps && L[1]>eps && L[2]>eps)
01118 {
01119 (*fi).FFp(i)->SetS();
01120 (*fi).FFp(i)->SetV();
01121
01122 if(face::CheckFlipEdge<FaceType>( *fi, i )) {
01123 face::FlipEdge<FaceType>( *fi, i );
01124 ++count; ++total;
01125 }
01126 }
01127 }
01128 }
01129 }
01130
01131
01132 }
01133 while( repeat && count );
01134 return total;
01135 }
01136
01137
01138 static int RemoveTVertexByFlip(MeshType &m, float threshold=40, bool repeat=true)
01139 {
01140 assert(m.HasFFTopology());
01141 assert(m.HasPerVertexMark());
01142
01143 int count, total = 0;
01144
01145 do {
01146 tri::UpdateTopology<MeshType>::FaceFace(m);
01147 tri::UnMarkAll(m);
01148 count = 0;
01149
01150
01151 for(unsigned int index = 0 ; index < m.face.size(); ++index )
01152 {
01153 FacePointer f = &(m.face[index]); float sides[3]; Point3<float> dummy;
01154 sides[0] = Distance(f->P(0), f->P(1));
01155 sides[1] = Distance(f->P(1), f->P(2));
01156 sides[2] = Distance(f->P(2), f->P(0));
01157
01158 int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
01159 if( tri::IsMarked(m,f->V2(i) )) continue;
01160
01161 if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
01162 {
01163 tri::Mark(m,f->V2(i));
01164 if(face::CheckFlipEdge<FaceType>( *f, i )) {
01165
01166 FacePointer g = f->FFp(i); int k = f->FFi(i);
01167 Triangle3<float> t1(f->P(i), f->P1(i), f->P2(i)), t2(g->P(k), g->P1(k), g->P2(k)),
01168 t3(f->P(i), g->P2(k), f->P2(i)), t4(g->P(k), f->P2(i), g->P2(k));
01169
01170 if ( std::min( t1.QualityFace(), t2.QualityFace() ) < std::min( t3.QualityFace(), t4.QualityFace() ))
01171 {
01172 face::FlipEdge<FaceType>( *f, i );
01173 ++count; ++total;
01174 }
01175 }
01176
01177 }
01178 }
01179
01180
01181 }
01182 while( repeat && count );
01183 return total;
01184 }
01185
01186 static int RemoveTVertexByCollapse(MeshType &m, float threshold=40, bool repeat=true)
01187 {
01188 assert(tri::HasPerVertexMark(m));
01189
01190 int count, total = 0;
01191
01192 do {
01193 tri::UnMarkAll(m);
01194 count = 0;
01195
01196
01197 for(unsigned int index = 0 ; index < m.face.size(); ++index )
01198 {
01199 FacePointer f = &(m.face[index]); float sides[3]; Point3<float> dummy;
01200 sides[0] = Distance(f->P(0), f->P(1)); sides[1] = Distance(f->P(1), f->P(2)); sides[2] = Distance(f->P(2), f->P(0));
01201 int i = std::find(sides, sides+3, std::max( std::max(sides[0],sides[1]), sides[2])) - (sides);
01202 if( tri::IsMarked(m,f->V2(i) )) continue;
01203
01204 if( PSDist(f->P2(i),f->P(i),f->P1(i),dummy)*threshold <= sides[i] )
01205 {
01206 tri::Mark(m,f->V2(i));
01207
01208 int j = Distance(dummy,f->P(i))<Distance(dummy,f->P1(i))?i:(i+1)%3;
01209 f->P2(i) = f->P(j); tri::Mark(m,f->V(j));
01210 ++count; ++total;
01211 }
01212 }
01213
01214
01215 tri::Clean<MeshType>::RemoveDuplicateVertex(m);
01216 tri::Allocator<MeshType>::CompactFaceVector(m);
01217 tri::Allocator<MeshType>::CompactVertexVector(m);
01218 }
01219 while( repeat && count );
01220
01221 return total;
01222 }
01223
01224 static bool SelfIntersections(MeshType &m, std::vector<FaceType*> &ret)
01225 {
01226 assert(HasPerFaceMark(m));
01227 Box3< ScalarType> bbox;
01228 TriMeshGrid gM;
01229 ret.clear();
01230 FaceIterator fi;
01231 int referredBit = FaceType::NewBitFlag();
01232 tri::UpdateFlags<MeshType>::FaceClear(m,referredBit);
01233
01234 std::vector<FaceType*> inBox;
01235 gM.Set(m.face.begin(),m.face.end());
01236
01237 for(fi=m.face.begin();fi!=m.face.end();++fi) if(!(*fi).IsD())
01238 {
01239 (*fi).SetUserBit(referredBit);
01240 (*fi).GetBBox(bbox);
01241 vcg::tri::GetInBoxFace(m, gM, bbox,inBox);
01242 bool Intersected=false;
01243 typename std::vector<FaceType*>::iterator fib;
01244 for(fib=inBox.begin();fib!=inBox.end();++fib)
01245 {
01246 if(!(*fib)->IsUserBit(referredBit) && (*fib != &*fi) )
01247 if(TestIntersection(&*fi,*fib)){
01248 ret.push_back(*fib);
01249 if(!Intersected) {
01250 ret.push_back(&*fi);
01251 Intersected=true;
01252 }
01253 }
01254 }
01255 inBox.clear();
01256 }
01257
01258 FaceType::DeleteBitFlag(referredBit);
01259 return (ret.size()>0);
01260 }
01261
01265 static bool IsSizeConsistent(MeshType &m)
01266 {
01267 int DeletedVertexNum=0;
01268 for (VertexIterator vi = m.vert.begin(); vi != m.vert.end(); ++vi)
01269 if((*vi).IsD()) DeletedVertexNum++;
01270
01271 int DeletedFaceNum=0;
01272 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
01273 if((*fi).IsD()) DeletedFaceNum++;
01274
01275 if(size_t(m.vn+DeletedVertexNum) != m.vert.size()) return false;
01276 if(size_t(m.fn+DeletedFaceNum) != m.face.size()) return false;
01277
01278 return true;
01279 }
01280
01285 static bool IsFFAdjacencyConsistent(MeshType &m)
01286 {
01287 if(!HasFFAdjacency(m)) return false;
01288
01289 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
01290 if(!(*fi).IsD())
01291 {
01292 for(int i=0;i<3;++i)
01293 if(!FFCorrectness(*fi, i)) return false;
01294 }
01295 return true;
01296 }
01297
01301 static bool HasConsistentPerWedgeTexCoord(MeshType &m)
01302 {
01303 if(!HasPerWedgeTexCoord(m)) return false;
01304
01305 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
01306 if(!(*fi).IsD())
01307 { FaceType &f=(*fi);
01308 if( ! ( (f.WT(0).N() == f.WT(1).N()) && (f.WT(0).N() == (*fi).WT(2).N()) ) )
01309 return false;
01310
01311 if((*fi).WT(0).N() <0) return false;
01312 }
01313 return true;
01314 }
01315
01319 static bool HasZeroTexCoordFace(MeshType &m)
01320 {
01321 if(!HasPerWedgeTexCoord(m)) return false;
01322
01323 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
01324 if(!(*fi).IsD())
01325 {
01326 if( (*fi).WT(0).P() == (*fi).WT(1).P() && (*fi).WT(0).P() == (*fi).WT(2).P() ) return false;
01327 }
01328 return true;
01329 }
01330
01331
01338 static bool TestIntersection(FaceType *f0,FaceType *f1)
01339 {
01340 assert(f0!=f1);
01341 int sv = face::CountSharedVertex(f0,f1);
01342 if(sv==0) return (vcg::IntersectionTriangleTriangle<FaceType>((*f0),(*f1)));
01343
01344 if(sv==1)
01345 {
01346 int i0,i1; ScalarType t,a,b;
01347 face::SharedVertex(f0,f1,i0,i1);
01348 if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f0).V1(i0)->P(),(*f0).V2(i0)->P()), *f1, t, a, b) ) return true;
01349 if(vcg::IntersectionSegmentTriangle(Segment3<ScalarType>((*f1).V1(i1)->P(),(*f1).V2(i1)->P()), *f0, t, a, b) ) return true;
01350 }
01351 return false;
01352 }
01353
01354
01355
01359 static int MergeCloseVertex(MeshType &m, const ScalarType radius)
01360 {
01361 typedef vcg::SpatialHashTable<VertexType, ScalarType> SampleSHT;
01362 SampleSHT sht;
01363 tri::VertTmark<MeshType> markerFunctor;
01364 typedef vcg::vertex::PointDistanceFunctor<ScalarType> VDistFunct;
01365 std::vector<VertexType*> closests;
01366 int mergedCnt=0;
01367 Point3f closestPt;
01368 sht.Set(m.vert.begin(), m.vert.end());
01369 UpdateFlags<MeshType>::VertexClearV(m);
01370 for(VertexIterator viv = m.vert.begin(); viv!= m.vert.end(); ++viv)
01371 if(!(*viv).IsD() && !(*viv).IsV())
01372 {
01373 (*viv).SetV();
01374 Point3f p = viv->cP();
01375 Box3f bb(p-Point3f(radius,radius,radius),p+Point3f(radius,radius,radius));
01376 GridGetInBox(sht, markerFunctor, bb, closests);
01377
01378 for(size_t i=0; i<closests.size(); ++i)
01379 {
01380 float dist = Distance(p,closests[i]->cP());
01381 if(dist < radius && !closests[i]->IsV())
01382 {
01383 mergedCnt++;
01384 closests[i]->SetV();
01385 closests[i]->P()=p;
01386 }
01387 }
01388 }
01389
01390 RemoveDuplicateVertex(m,true);
01391 return mergedCnt;
01392 }
01393
01394
01395 static std::pair<int,int> RemoveSmallConnectedComponentsSize(MeshType &m, int maxCCSize)
01396 {
01397 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
01398 int TotalCC=ConnectedComponents(m, CCV);
01399 int DeletedCC=0;
01400
01401 ConnectedIterator<MeshType> ci;
01402 for(unsigned int i=0;i<CCV.size();++i)
01403 {
01404 std::vector<typename MeshType::FacePointer> FPV;
01405 if(CCV[i].first<maxCCSize)
01406 {
01407 DeletedCC++;
01408 for(ci.start(m,CCV[i].second);!ci.completed();++ci)
01409 FPV.push_back(*ci);
01410
01411 typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
01412 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
01413 Allocator<MeshType>::DeleteFace(m,(**fpvi));
01414 }
01415 }
01416 return std::make_pair<int,int>(TotalCC,DeletedCC);
01417 }
01418
01420
01421 static std::pair<int,int> RemoveSmallConnectedComponentsDiameter(MeshType &m, ScalarType maxDiameter)
01422 {
01423 std::vector< std::pair<int, typename MeshType::FacePointer> > CCV;
01424 int TotalCC=ConnectedComponents(m, CCV);
01425 int DeletedCC=0;
01426 tri::ConnectedIterator<MeshType> ci;
01427 for(unsigned int i=0;i<CCV.size();++i)
01428 {
01429 Box3f bb;
01430 std::vector<typename MeshType::FacePointer> FPV;
01431 for(ci.start(m,CCV[i].second);!ci.completed();++ci)
01432 {
01433 FPV.push_back(*ci);
01434 bb.Add((*ci)->P(0));
01435 bb.Add((*ci)->P(1));
01436 bb.Add((*ci)->P(2));
01437 }
01438 if(bb.Diag()<maxDiameter)
01439 {
01440 DeletedCC++;
01441 typename std::vector<typename MeshType::FacePointer>::iterator fpvi;
01442 for(fpvi=FPV.begin(); fpvi!=FPV.end(); ++fpvi)
01443 tri::Allocator<MeshType>::DeleteFace(m,(**fpvi));
01444 }
01445 }
01446 return std::make_pair<int,int>(TotalCC,DeletedCC);
01447 }
01448
01449 };
01452 }
01453 }
01454 #endif
