00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137 #ifndef __VCG_TRI_UPDATE_HOLE
00138 #define __VCG_TRI_UPDATE_HOLE
00139
00140 #include <wrap/callback.h>
00141 #include <vcg/math/base.h>
00142 #include <vcg/complex/trimesh/clean.h>
00143 #include <vcg/space/point3.h>
00144 #include <vector>
00145 #include <float.h>
00146
00147 namespace vcg {
00148 namespace tri {
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170 template<class MESH> class TrivialEar
00171 {
00172 public:
00173 typedef typename MESH::FaceType FaceType;
00174 typedef typename MESH::FacePointer FacePointer;
00175 typedef typename face::Pos<FaceType> PosType;
00176 typedef typename MESH::ScalarType ScalarType;
00177 typedef typename MESH::CoordType CoordType;
00178
00179 PosType e0;
00180 PosType e1;
00181 CoordType n;
00182 const char * Dump() {return 0;}
00183 const CoordType &cP(int i) const {return P(i);}
00184 const CoordType &P(int i) const {
00185 switch(i) {
00186 case 0 : return e0.v->cP();
00187 case 1 : return e1.v->cP();
00188 case 2 : return e0.VFlip()->cP();
00189 default: assert(0);
00190 }
00191 return e0.v->cP();
00192 }
00193
00194 ScalarType quality;
00195 ScalarType angle;
00196
00197 TrivialEar(){}
00198 TrivialEar(const PosType & ep)
00199 {
00200 e0=ep;
00201 assert(e0.IsBorder());
00202 e1=e0;
00203 e1.NextB();
00204 n=vcg::Normal<TrivialEar>(*this);
00205 ComputeQuality();
00206 ComputeAngle();
00207 }
00208
00210
00211
00212 void ComputeAngle()
00213 {
00214 angle=Angle(cP(2)-cP(0), cP(1)-cP(0));
00215 ScalarType flipAngle = n.dot(e0.v->N());
00216 if(flipAngle<0) angle = (2.0 *(float)M_PI) - angle;
00217 }
00218
00219 virtual inline bool operator < ( const TrivialEar & c ) const { return quality < c.quality; }
00220
00221 bool IsNull(){return e0.IsNull() || e1.IsNull();}
00222 void SetNull(){e0.SetNull();e1.SetNull();}
00223 virtual void ComputeQuality() { quality = QualityFace(*this) ; };
00224 bool IsUpToDate() {return ( e0.IsBorder() && e1.IsBorder());};
00225
00226 bool IsDegen(const int nonManifoldBit)
00227 {
00228 if(e0.VFlip()->IsUserBit(nonManifoldBit) && e1.V()->IsUserBit(nonManifoldBit))
00229 return true;
00230 else return false;
00231 }
00232 bool IsConcave() const {return(angle > (float)M_PI);}
00233
00234 virtual bool Close(PosType &np0, PosType &np1, FaceType * f)
00235 {
00236
00237 if(e0.f==e1.f) {
00238
00239 return false;
00240 }
00241
00242
00243 PosType ep=e0; ep.FlipV(); ep.NextB(); ep.FlipV();
00244 PosType en=e1; en.NextB();
00245
00246 (*f).V(0) = e0.VFlip();
00247 (*f).V(1) = e0.v;
00248 (*f).V(2) = e1.v;
00249 ComputeNormal(*f);
00250
00251 (*f).FFp(0) = e0.f;
00252 (*f).FFi(0) = e0.z;
00253 (*f).FFp(1) = e1.f;
00254 (*f).FFi(1) = e1.z;
00255 (*f).FFp(2) = f;
00256 (*f).FFi(2) = 2;
00257
00258 e0.f->FFp(e0.z)=f;
00259 e0.f->FFi(e0.z)=0;
00260
00261 e1.f->FFp(e1.z)=f;
00262 e1.f->FFi(e1.z)=1;
00263
00264
00265 if(ep==en)
00266 {
00267
00268 f->FFp(2)=en.f;
00269 f->FFi(2)=en.z;
00270 en.f->FFp(en.z)=f;
00271 en.f->FFi(en.z)=2;
00272 np0.SetNull();
00273 np1.SetNull();
00274 }
00275
00276 else if(ep.v==en.v)
00277 {
00278
00279 PosType enold=en;
00280 en.NextB();
00281 f->FFp(2)=enold.f;
00282 f->FFi(2)=enold.z;
00283 enold.f->FFp(enold.z)=f;
00284 enold.f->FFi(enold.z)=2;
00285 np0=ep;
00286 np1=en;
00287 }
00288
00289 else if(ep.VFlip()==e1.v)
00290 {
00291
00292 PosType epold=ep;
00293 ep.FlipV(); ep.NextB(); ep.FlipV();
00294 f->FFp(2)=epold.f;
00295 f->FFi(2)=epold.z;
00296 epold.f->FFp(epold.z)=f;
00297 epold.f->FFi(epold.z)=2;
00298 np0=ep;
00299 np1=en;
00300 }
00301 else
00302 {
00303 np0=ep;
00304 np1=PosType(f,2,e1.v);
00305 }
00306
00307 return true;
00308 }
00309 };
00310
00311
00312 template<class MESH> class MinimumWeightEar : public TrivialEar<MESH>
00313 {
00314 public:
00315 static float &DiedralWeight() { static float _dw=1.0; return _dw;}
00316 typedef TrivialEar<MESH> TE;
00317 typename MESH::ScalarType dihedralRad;
00318 typename MESH::ScalarType aspectRatio;
00319 const char * Dump() {
00320 static char buf[200];
00321 if(this->IsConcave()) sprintf(buf,"Dihedral -(deg) %6.2f Quality %6.2f\n",math::ToDeg(dihedralRad),aspectRatio);
00322 else sprintf(buf,"Dihedral (deg) %6.2f Quality %6.2f\n",math::ToDeg(dihedralRad),aspectRatio);
00323 return buf;
00324 }
00325
00326 MinimumWeightEar(){}
00327
00328 MinimumWeightEar(const typename face::Pos<typename MESH::FaceType>& ep) : TrivialEar<MESH>(ep)
00329 {
00330 ComputeQuality();
00331 }
00332
00333
00334
00335
00336
00337
00338
00339 virtual inline bool operator < ( const MinimumWeightEar & c ) const
00340 {
00341 if(TE::IsConcave() == c.IsConcave())
00342 {
00343 return (pow((float)dihedralRad,(float)DiedralWeight())/aspectRatio) > (pow((float)c.dihedralRad,(float)DiedralWeight())/c.aspectRatio);
00344 }
00345 if(TE::IsConcave()) return true;
00346
00347 return false;
00348 }
00349
00350
00351 virtual void ComputeQuality()
00352 {
00353
00354 typename MESH::CoordType n1=TE::e0.FFlip()->cN();
00355 typename MESH::CoordType n2=TE::e1.FFlip()->cN();
00356
00357 dihedralRad = std::max(Angle(TE::n,n1),Angle(TE::n,n2));
00358 aspectRatio = QualityFace(*this);
00359 }
00360
00361 };
00362
00363 template<class MESH> class SelfIntersectionEar : public MinimumWeightEar<MESH>
00364 {
00365 public:
00366 typedef typename MESH::FaceType FaceType;
00367 typedef typename MESH::FacePointer FacePointer;
00368 typedef typename face::Pos<FaceType> PosType;
00369 typedef typename MESH::ScalarType ScalarType;
00370 typedef typename MESH::CoordType CoordType;
00371
00372 static std::vector<FacePointer> &AdjacencyRing()
00373 {
00374 static std::vector<FacePointer> ar;
00375 return ar;
00376 }
00377
00378 SelfIntersectionEar(){}
00379 SelfIntersectionEar(const PosType & ep):MinimumWeightEar<MESH>(ep){}
00380
00381 virtual bool Close(PosType &np0, PosType &np1, FacePointer f)
00382 {
00383 PosType ep=this->e0; ep.FlipV(); ep.NextB(); ep.FlipV();
00384 PosType en=this->e1; en.NextB();
00385
00386 (*f).V(0) = this->e0.VFlip();
00387 (*f).V(1) = this->e0.v;
00388 (*f).V(2) = this->e1.v;
00389
00390 (*f).FFp(0) = this->e0.f;
00391 (*f).FFi(0) = this->e0.z;
00392 (*f).FFp(1) = this->e1.f;
00393 (*f).FFi(1) = this->e1.z;
00394 (*f).FFp(2) = f;
00395 (*f).FFi(2) = 2;
00396
00397 int a1, a2;
00398 a1= this->e0.z;
00399 a2= this->e1.z;
00400
00401 this->e0.f->FFp(this->e0.z)=f;
00402 this->e0.f->FFi(this->e0.z)=0;
00403
00404 this->e1.f->FFp(this->e1.z)=f;
00405 this->e1.f->FFi(this->e1.z)=1;
00406 typename std::vector< FacePointer >::iterator it;
00407 for(it = this->AdjacencyRing().begin();it!= this->AdjacencyRing().end();++it)
00408 {
00409 if(!(*it)->IsD())
00410 if( tri::Clean<MESH>::TestIntersection(&(*f),*it))
00411 {
00412 this->e0.f->FFp(this->e0.z)= this->e0.f;
00413 this->e0.f->FFi(this->e0.z)=a1;
00414
00415 this->e1.f->FFp(this->e1.z)= this->e1.f;
00416 this->e1.f->FFi(this->e1.z)=a2;
00417 return false;
00418 }
00419 }
00420
00421 this->e0.f->FFp(this->e0.z)= this->e0.f;
00422 this->e0.f->FFi(this->e0.z)=a1;
00423
00424 this->e1.f->FFp(this->e1.z)=this->e1.f;
00425 this->e1.f->FFi(this->e1.z)=a2;
00426
00427 bool ret=TrivialEar<MESH>::Close(np0,np1,f);
00428 if(ret) AdjacencyRing().push_back(f);
00429 return ret;
00430 }
00431 };
00432
00433
00434
00435
00436
00437
00438
00439 template <class MESH>
00440 class Hole
00441 {
00442 public:
00443 typedef typename MESH::VertexType VertexType;
00444 typedef typename MESH::VertexPointer VertexPointer;
00445 typedef typename MESH::ScalarType ScalarType;
00446 typedef typename MESH::FaceType FaceType;
00447 typedef typename MESH::FacePointer FacePointer;
00448 typedef typename MESH::FaceIterator FaceIterator;
00449 typedef typename MESH::CoordType CoordType;
00450 typedef typename vcg::Box3<ScalarType> Box3Type;
00451 typedef typename face::Pos<FaceType> PosType;
00452
00453 public:
00454
00455 class Info
00456 {
00457 public:
00458 Info(){}
00459 Info(PosType const &pHole, int const pHoleSize, Box3<ScalarType> &pHoleBB)
00460 {
00461 p=pHole;
00462 size=pHoleSize;
00463 bb=pHoleBB;
00464 }
00465
00466 PosType p;
00467 int size;
00468 Box3Type bb;
00469
00470 bool operator < (const Info & hh) const {return size < hh.size;}
00471
00472 ScalarType Perimeter()
00473 {
00474 ScalarType sum=0;
00475 PosType ip = p;
00476 do
00477 {
00478 sum+=Distance(ip.v->cP(),ip.VFlip()->cP());
00479 ip.NextB();
00480 }
00481 while (ip != p);
00482 return sum;
00483 }
00484
00485
00486
00487
00488
00489 bool CheckValidity()
00490 {
00491 if(!p.IsBorder())
00492 return false;
00493 PosType ip=p;ip.NextB();
00494 for(;ip!=p;ip.NextB())
00495 {
00496 if(!ip.IsBorder())
00497 return false;
00498 }
00499 return true;
00500 }
00501 };
00502
00503 template<class EAR>
00504 static void FillHoleEar(MESH &m, Info &h ,int UBIT, std::vector<FacePointer *> &app,std::vector<FaceType > *vf =0)
00505 {
00506
00507 FaceIterator f = tri::Allocator<MESH>::AddFaces(m, h.size-2, app);
00508 assert(h.p.f >= &*m.face.begin());
00509 assert(h.p.f <= &m.face.back());
00510 assert(h.p.IsBorder());
00511 std::vector< EAR > H;
00512 H.reserve(h.size);
00513 int nmBit= VertexType::NewBitFlag();
00514
00515
00516 PosType ip = h.p;
00517 do{
00518 ip.V()->ClearUserBit(nmBit);
00519 ip.V()->ClearV();
00520 ip.NextB();
00521 } while(ip!=h.p);
00522
00523 ip = h.p;
00524 do{
00525 if(!ip.V()->IsV())
00526 ip.V()->SetV();
00527 else ip.V()->SetUserBit(nmBit);
00528 ip.NextB();
00529 } while(ip!=h.p);
00530
00531 PosType fp = h.p;
00532 do{
00533 EAR app = EAR(fp);
00534 H.push_back( app );
00535
00536 fp.NextB();
00537 assert(fp.IsBorder());
00538 }while(fp!=h.p);
00539
00540 int cnt=h.size;
00541
00542 make_heap(H.begin(), H.end());
00543
00544
00545 while( cnt > 2 && !H.empty() )
00546 {
00547
00548 pop_heap(H.begin(), H.end());
00549 PosType ep0,ep1;
00550 EAR BestEar=H.back();
00551 H.pop_back();
00552 if(BestEar.IsUpToDate() && !BestEar.IsDegen(nmBit))
00553 {
00554 if((*f).HasPolyInfo()) (*f).Alloc(3);
00555 if(BestEar.Close(ep0,ep1,&*f))
00556 {
00557 if(!ep0.IsNull()){
00558 H.push_back(EAR(ep0));
00559 push_heap( H.begin(), H.end());
00560 }
00561 if(!ep1.IsNull()){
00562 H.push_back(EAR(ep1));
00563 push_heap( H.begin(), H.end());
00564 }
00565 --cnt;
00566 f->SetUserBit(UBIT);
00567 if(vf != 0) (*vf).push_back(*f);
00568 ++f;
00569 }
00570 }
00571 }
00572
00573 while(f!=m.face.end())
00574 {
00575 (*f).SetD();
00576 ++f;
00577 m.fn--;
00578 }
00579
00580 VertexType::DeleteBitFlag(nmBit);
00581 }
00582
00583 template<class EAR>
00584 static int EarCuttingFill(MESH &m, int sizeHole,bool Selected = false, CallBackPos *cb=0)
00585 {
00586 std::vector< Info > vinfo;
00587 int UBIT = GetInfo(m, Selected,vinfo);
00588
00589 typename std::vector<Info >::iterator ith;
00590
00591 int indCb=0;
00592 int holeCnt=0;
00593 std::vector<FacePointer *> vfp;
00594 for(ith = vinfo.begin(); ith!= vinfo.end(); ++ith)
00595 vfp.push_back( &(*ith).p.f );
00596
00597 for(ith = vinfo.begin(); ith!= vinfo.end(); ++ith)
00598 {
00599 indCb++;
00600 if(cb) (*cb)(indCb*10/vinfo.size(),"Closing Holes");
00601 if((*ith).size < sizeHole){
00602 holeCnt++;
00603 FillHoleEar< EAR >(m, *ith,UBIT,vfp);
00604 }
00605 }
00606
00607 FaceIterator fi;
00608 for(fi = m.face.begin(); fi!=m.face.end(); ++fi)
00609 {
00610 if(!(*fi).IsD())
00611 (*fi).ClearUserBit(UBIT);
00612 }
00613 return holeCnt;
00614 }
00615
00616
00617
00618 template<class EAR>
00619 static int EarCuttingIntersectionFill(MESH &m, int sizeHole, bool Selected = false, CallBackPos *cb=0)
00620 {
00621 std::vector<Info > vinfo;
00622 int UBIT = GetInfo(m, Selected,vinfo);
00623 std::vector<FaceType > vf;
00624 PosType sp;
00625 PosType ap;
00626 typename std::vector<Info >::iterator ith;
00627
00628
00629 std::vector<FacePointer *> vfpOrig;
00630 for(ith = vinfo.begin(); ith!= vinfo.end(); ++ith)
00631 vfpOrig.push_back( &(*ith).p.f );
00632
00633 int indCb=0;
00634 int holeCnt=0;
00635 for(ith = vinfo.begin(); ith!= vinfo.end(); ++ith)
00636 {
00637 indCb++;
00638 if(cb) (*cb)(indCb*10/vinfo.size(),"Closing Holes");
00639 if((*ith).size < sizeHole){
00640 std::vector<FacePointer *> vfp;
00641 holeCnt++;
00642 vfp=vfpOrig;
00643 EAR::AdjacencyRing().clear();
00644
00645 PosType ip = (*ith).p;
00646 do
00647 {
00648 PosType inp = ip;
00649 do
00650 {
00651 inp.FlipE();
00652 inp.FlipF();
00653 EAR::AdjacencyRing().push_back(inp.f);
00654 } while(!inp.IsBorder());
00655 ip.NextB();
00656 }while(ip != (*ith).p);
00657
00658 typename std::vector<FacePointer>::iterator fpi;
00659 for(fpi=EAR::AdjacencyRing().begin();fpi!=EAR::AdjacencyRing().end();++fpi)
00660 vfp.push_back( &*fpi );
00661
00662 FillHoleEar<EAR >(m, *ith,UBIT,vfp,&vf);
00663 EAR::AdjacencyRing().clear();
00664 }
00665 }
00666 FaceIterator fi;
00667 for(fi = m.face.begin(); fi!=m.face.end(); ++fi)
00668 {
00669 if(!(*fi).IsD())
00670 (*fi).ClearUserBit(UBIT);
00671 }
00672 return holeCnt;
00673 }
00674
00675
00676
00677 static int GetInfo(MESH &m,bool Selected ,std::vector<Info >& VHI)
00678 {
00679 FaceIterator fi;
00680 int UBIT = FaceType::LastBitFlag();
00681
00682 for(fi = m.face.begin(); fi!=m.face.end(); ++fi)
00683 {
00684 if(!(*fi).IsD())
00685 {
00686 if(Selected && !(*fi).IsS())
00687 {
00688
00689
00690 (*fi).SetUserBit(UBIT);
00691 }
00692 else
00693 {
00694 for(int j =0; j<3 ; ++j)
00695 {
00696 if( face::IsBorder(*fi,j) && !(*fi).IsUserBit(UBIT) )
00697 {
00698 (*fi).SetUserBit(UBIT);
00699 PosType sp(&*fi, j, (*fi).V(j));
00700 PosType fp=sp;
00701 int holesize=0;
00702
00703 Box3Type hbox;
00704 hbox.Add(sp.v->cP());
00705
00706 sp.f->SetUserBit(UBIT);
00707 do
00708 {
00709 sp.f->SetUserBit(UBIT);
00710 hbox.Add(sp.v->cP());
00711 ++holesize;
00712 sp.NextB();
00713 sp.f->SetUserBit(UBIT);
00714 assert(sp.IsBorder());
00715 }while(sp != fp);
00716
00717
00718 VHI.push_back( Info(sp,holesize,hbox) );
00719 }
00720 }
00721 }
00722 }
00723 }
00724 return UBIT;
00725 }
00726
00727
00728 class Weight
00729 {
00730 public:
00731
00732 Weight() { ang = 180; ar = FLT_MAX ;}
00733 Weight( float An, float Ar ) { ang=An ; ar= Ar;}
00734 ~Weight() {}
00735
00736 float angle() const { return ang; }
00737 float area() const { return ar; }
00738
00739 Weight operator+( const Weight & other ) const {return Weight( std::max( angle(), other.angle() ), area() + other.area());}
00740 bool operator<( const Weight & rhs ) const {return ( angle() < rhs.angle() ||(angle() == rhs.angle() && area() < rhs.area())); }
00741
00742 private:
00743 float ang;
00744 float ar;
00745 };
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758 static float ComputeDihedralAngle(CoordType p1,CoordType p2,CoordType p3,CoordType p4)
00759 {
00760 CoordType n1 = NormalizedNormal(p1,p3,p2);
00761 CoordType n2 = NormalizedNormal(p1,p2,p4);
00762 return math::ToDeg(AngleN(n1,n2));
00763 }
00764
00765 static bool existEdge(PosType pi,PosType pf)
00766 {
00767 PosType app = pi;
00768 PosType appF = pi;
00769 PosType tmp;
00770 assert(pi.IsBorder());
00771 appF.NextB();
00772 appF.FlipV();
00773 do
00774 {
00775 tmp = app;
00776 tmp.FlipV();
00777 if(tmp.v == pf.v)
00778 return true;
00779 app.FlipE();
00780 app.FlipF();
00781
00782 if(app == pi)return false;
00783 }while(app != appF);
00784 return false;
00785 }
00786
00787 static Weight computeWeight( int i, int j, int k,
00788 std::vector<PosType > pv,
00789 std::vector< std::vector< int > > v)
00790 {
00791 PosType pi = pv[i];
00792 PosType pj = pv[j];
00793 PosType pk = pv[k];
00794
00795
00796 if(existEdge(pi,pj) || existEdge(pj,pk)|| existEdge(pk,pi) )
00797 {
00798 return Weight();
00799 }
00800
00801
00802 if(v[i][j] == -1){return Weight();}
00803 if(v[j][k] == -1){return Weight();}
00804
00805
00806 float angle = 0.0f;
00807 PosType px;
00808 if(i + 1 == j)
00809 {
00810 px = pj;
00811 px.FlipE(); px.FlipV();
00812 angle = std::max<float>(angle , ComputeDihedralAngle(pi.v->P(), pj.v->P(), pk.v->P(), px.v->P()) );
00813 }
00814 else
00815 {
00816 angle = std::max<float>( angle, ComputeDihedralAngle(pi.v->P(),pj.v->P(), pk.v->P(), pv[ v[i][j] ].v->P()));
00817 }
00818
00819 if(j + 1 == k)
00820 {
00821 px = pk;
00822 px.FlipE(); px.FlipV();
00823 angle = std::max<float>(angle , ComputeDihedralAngle(pj.v->P(), pk.v->P(), pi.v->P(), px.v->P()) );
00824 }
00825 else
00826 {
00827 angle = std::max<float>( angle, ComputeDihedralAngle(pj.v->P(),pk.v->P(), pi.v->P(), pv[ v[j][k] ].v->P()));
00828 }
00829
00830 if( i == 0 && k == (int)v.size() - 1)
00831 {
00832 px = pi;
00833 px.FlipE(); px.FlipV();
00834 angle = std::max<float>(angle , ComputeDihedralAngle(pk.v->P(), pi.v->P(), pj.v->P(),px.v->P() ) );
00835 }
00836
00837 ScalarType area = ( (pj.v->P() - pi.v->P()) ^ (pk.v->P() - pi.v->P()) ).Norm() * 0.5;
00838
00839 return Weight(angle, area);
00840 }
00841
00842 static void calculateMinimumWeightTriangulation(MESH &m, FaceIterator f,std::vector<PosType > vv )
00843 {
00844 std::vector< std::vector< Weight > > w;
00845 std::vector< std::vector< int > > vi;
00846
00847
00848 int nv = vv.size();
00849
00850 w.clear();
00851 w.resize( nv, std::vector<Weight>( nv, Weight() ) );
00852
00853 vi.resize( nv, std::vector<int>( nv, 0 ) );
00854
00855
00856 for ( int i = 0; i < nv-1; ++i )
00857 w[i][i+1] = Weight( 0, 0 );
00858
00859
00860 for ( int j = 2; j < nv; ++j )
00861 {
00862 for ( int i = 0; i + j < nv; ++i )
00863 {
00864
00865 Weight minval;
00866
00867
00868 int minIndex = -1;
00869
00870
00871 for ( int m = i + 1; m < i + j; ++m )
00872 {
00873 Weight a = w[i][m];
00874 Weight b = w[m][i+j];
00875 Weight newval = a + b + computeWeight( i, m, i+j, vv, vi);
00876 if ( newval < minval )
00877 {
00878 minval = newval;
00879 minIndex = m;
00880 }
00881 }
00882 w[i][i+j] = minval;
00883 vi[i][i+j] = minIndex;
00884 }
00885 }
00886
00887
00888 int i, j;
00889 i=0; j=nv-1;
00890
00891 triangulate(m,f, i, j, vi, vv);
00892
00893 while(f!=m.face.end())
00894 {
00895 (*f).SetD();
00896 ++f;
00897 m.fn--;
00898 }
00899 }
00900
00901
00902 static void triangulate(MESH &m, FaceIterator &f,int i, int j,
00903 std::vector< std::vector<int> > vi, std::vector<PosType > vv)
00904 {
00905 if(i + 1 == j){return;}
00906 if(i==j)return;
00907
00908 int k = vi[i][j];
00909
00910 if(k == -1) return;
00911
00912
00913 f->V(0) = vv[i].v;
00914 f->V(1) = vv[k].v;
00915 f->V(2) = vv[j].v;
00916
00917 f++;
00918 triangulate(m,f,i,k,vi,vv);
00919 triangulate(m,f,k,j,vi,vv);
00920 }
00921
00922 static void MinimumWeightFill(MESH &m, int holeSize, bool Selected)
00923 {
00924 FaceIterator fi;
00925 std::vector<PosType > vvi;
00926 std::vector<FacePointer * > vfp;
00927
00928 std::vector<Info > vinfo;
00929 typename std::vector<Info >::iterator VIT;
00930 int UBIT = GetInfo(m, Selected,vinfo);
00931
00932 for(VIT = vinfo.begin(); VIT != vinfo.end();++VIT)
00933 {
00934 vvi.push_back(VIT->p);
00935 }
00936
00937 typename std::vector<PosType >::iterator ith;
00938 typename std::vector<PosType >::iterator ithn;
00939 typename std::vector<VertexPointer >::iterator itf;
00940
00941 std::vector<PosType > app;
00942 PosType ps;
00943 std::vector<FaceType > tr;
00944 std::vector<VertexPointer > vf;
00945
00946 for(ith = vvi.begin(); ith!= vvi.end(); ++ith)
00947 {
00948 tr.clear();
00949 vf.clear();
00950 app.clear();
00951 vfp.clear();
00952
00953 ps = *ith;
00954 getBoundHole(ps,app);
00955
00956 if(app.size() <= holeSize)
00957 {
00958 typename std::vector<PosType >::iterator itP;
00959 std::vector<FacePointer *> vfp;
00960
00961 for(ithn = vvi.begin(); ithn!= vvi.end(); ++ithn)
00962 vfp.push_back(&(ithn->f));
00963
00964 for(itP = app.begin (); itP != app.end ();++itP)
00965 vfp.push_back( &(*itP).f );
00966
00967
00968 FaceIterator f = tri::Allocator<MESH>::AddFaces(m, (app.size()-2) , vfp);
00969
00970 calculateMinimumWeightTriangulation(m,f, app);
00971 }
00972 }
00973
00974 }
00975
00976 static void getBoundHole (PosType sp,std::vector<PosType >&ret)
00977 {
00978 PosType fp = sp;
00979
00980 do
00981 {
00982 assert(fp.IsBorder());
00983 ret.push_back(fp);
00984 fp.NextB();
00985 }while(sp != fp);
00986 }
00987
00988 };
00989
00990 }
00991 }
00992 #endif
