vcglib: tri_edge_flip.h Source File

00001 /****************************************************************************
00002  * VCGLib                                                            o o     *
00003  * Visual and Computer Graphics Library                            o     o   *
00004  *                                                                _   O  _   *
00005  * Copyright(C) 2004                                                \/)\/    *
00006  * Visual Computing Lab                                            /\/|      *
00007  * ISTI - Italian National Research Council                           |      *
00008  *                                                                    \      *
00009  * All rights reserved.                                                      *
00010  *                                                                           *
00011  * This program is free software; you can redistribute it and/or modify      *
00012  * it under the terms of the GNU General Public License as published by      *
00013  * the Free Software Foundation; either version 2 of the License, or         *
00014  * (at your option) any later version.                                       *
00015  *                                                                           *
00016  * This program is distributed in the hope that it will be useful,           *
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019  * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020  * for more details.                                                         *
00021  *                                                                           *
00022  ****************************************************************************/
00023 
00024 #ifndef __VCG_DECIMATION_TRIFLIP
00025 #define __VCG_DECIMATION_TRIFLIP
00026 
00027 #include <vcg/complex/local_optimization.h>
00028 #include <vcg/simplex/face/topology.h>
00029 #include <vcg/space/triangle3.h>
00030 
00031 namespace vcg
00032 {
00033 namespace tri
00034 {
00036 /* @{ */
00037 
00047 template <class TRIMESH_TYPE, class MYTYPE,
00048             typename TRIMESH_TYPE::ScalarType (*QualityFunc)(
00049                         Point3<typename TRIMESH_TYPE::ScalarType> const & p0,
00050                         Point3<typename TRIMESH_TYPE::ScalarType> const & p1, 
00051                         Point3<typename TRIMESH_TYPE::ScalarType> const & p2) = Quality>
00052 class PlanarEdgeFlip :
00053         public LocalOptimization< TRIMESH_TYPE>::LocModType
00054 {
00055 protected:
00056         typedef typename TRIMESH_TYPE::FaceType FaceType;
00057         typedef typename TRIMESH_TYPE::FacePointer FacePointer;
00058         typedef typename TRIMESH_TYPE::FaceIterator FaceIterator;
00059         typedef typename TRIMESH_TYPE::VertexType VertexType;
00060         typedef typename TRIMESH_TYPE::ScalarType ScalarType;
00061         typedef typename TRIMESH_TYPE::VertexPointer VertexPointer;
00062         typedef typename TRIMESH_TYPE::CoordType CoordType;
00063         typedef vcg::face::Pos<FaceType> PosType;
00064         typedef typename LocalOptimization<TRIMESH_TYPE>::HeapElem HeapElem;
00065         typedef typename LocalOptimization<TRIMESH_TYPE>::HeapType HeapType;
00066 
00070         PosType _pos;
00071 
00075         ScalarType _priority;
00076 
00080         int _localMark;
00081 
00085         static int& GlobalMark()
00086         {
00087                 static int im = 0;
00088                 return im;
00089         }
00090         
00091         static void Insert(HeapType& heap, PosType& p, int mark)
00092         {
00093                 if(!p.IsBorder() && p.F()->IsW() && p.FFlip()->IsW()) {
00094                         MYTYPE* newflip = new MYTYPE(p, mark);
00095                         heap.push_back(HeapElem(newflip));
00096                         std::push_heap(heap.begin(), heap.end());
00097                 }
00098         }
00099         
00100 public:
00104         inline PlanarEdgeFlip()
00105         {
00106         }
00107         
00108         
00112         inline PlanarEdgeFlip(PosType pos, int mark)
00113         {
00114                 _pos = pos;
00115                 _localMark = mark;
00116                 _priority = ComputePriority();
00117         }
00118         
00119         
00123         inline PlanarEdgeFlip(const PlanarEdgeFlip &par)
00124         {
00125                 _pos = par.GetPos();
00126                 _localMark = par.GetMark();
00127                 _priority = par.Priority();
00128         }
00129         
00130         
00133         ~PlanarEdgeFlip()
00134         {
00135         }
00136         
00137         
00141         static ScalarType &CoplanarAngleThresholdDeg()
00142         {
00143                 static ScalarType _CoplanarAngleThresholdDeg = 0.01f;
00144                 return _CoplanarAngleThresholdDeg;
00145         }
00146         
00147         inline PosType GetPos()
00148         {
00149                 return _pos;
00150         }
00151         
00152         inline int GetMark()
00153         {
00154                 return _localMark;
00155         }
00156         
00157         
00161         ModifierType IsOfType()
00162         {
00163                 return TriEdgeFlipOp;
00164         }
00165         
00166         
00170         bool IsUpToDate()
00171         {
00172                 int lastMark = _pos.F()->V(0)->IMark();
00173                 lastMark = vcg::math::Max<int>(lastMark, _pos.F()->V(1)->IMark());
00174                 lastMark = vcg::math::Max<int>(lastMark, _pos.F()->V(2)->IMark());
00175 
00176                 return ( _localMark >= lastMark );
00177         }
00178 
00184         virtual bool IsFeasible()
00185         {
00186                 if(!vcg::face::CheckFlipEdge(*this->_pos.F(), this->_pos.E()))
00187                         return false;
00188                 
00189                 if( math::ToDeg( Angle(_pos.FFlip()->cN(), _pos.F()->cN()) ) > CoplanarAngleThresholdDeg() )
00190                         return false;
00191 
00192                 CoordType v0, v1, v2, v3;
00193                 int i = _pos.E();
00194                 
00195                 v0 = _pos.F()->P0(i);
00196                 v1 = _pos.F()->P1(i);
00197                 v2 = _pos.F()->P2(i);
00198                 v3 = _pos.F()->FFp(i)->P2(_pos.F()->FFi(i));
00199 
00200                 // Take the parallelogram formed by the adjacent faces of edge
00201                 // If a corner of the parallelogram on extreme of edge to flip is >= 180
00202                 // the flip produce two identical faces - avoid this
00203                 if( (Angle(v2 - v0, v1 - v0) + Angle(v3 - v0, v1 - v0) >= M_PI) ||
00204                     (Angle(v2 - v1, v0 - v1) + Angle(v3 - v1, v0 - v1) >= M_PI))
00205                         return false;
00206                 
00207                 // if any of two faces adj to edge in non writable, the flip is unfeasible
00208                 if(!_pos.F()->IsW() || !_pos.F()->FFp(i)->IsW())
00209                         return false;
00210                 
00211                 return true;
00212         }
00213 
00217         /*
00218              1  
00219             /|\
00220            / | \
00221           2  |  3 
00222            \ | /
00223             \|/
00224              0
00225          */
00226         virtual ScalarType ComputePriority()
00227         {
00228                 CoordType v0, v1, v2, v3;
00229                 int i = _pos.E();
00230                 v0 = _pos.F()->P0(i);
00231                 v1 = _pos.F()->P1(i);
00232                 v2 = _pos.F()->P2(i);
00233                 v3 = _pos.F()->FFp(i)->P2(_pos.F()->FFi(i));
00234 
00235                 ScalarType Qa = QualityFunc(v0, v1, v2);
00236                 ScalarType Qb = QualityFunc(v0, v3, v1);
00237 
00238                 ScalarType QaAfter = QualityFunc(v1, v2, v3);
00239                 ScalarType QbAfter = QualityFunc(v0, v3, v2);
00240                 
00241                 // < 0 if the average quality of faces improves after flip
00242                 _priority = (Qa + Qb - QaAfter - QbAfter) / (ScalarType)2.0;
00243                 
00244                 return _priority;
00245         }
00246 
00250         virtual ScalarType Priority() const
00251         {
00252                 return _priority;
00253         }
00254 
00258         void Execute(TRIMESH_TYPE &m)
00259         {
00260                 int i = _pos.E();
00261                 int j = _pos.F()->FFi(i);
00262                 FacePointer f1 = _pos.F();
00263                 FacePointer f2 = _pos.F()->FFp(i);
00264                 
00265                 vcg::face::FlipEdge(*_pos.F(), _pos.E());
00266                 
00267                 // avoid texture coordinates swap after flip
00268                 if(tri::HasPerWedgeTexCoord(m)) {
00269                         f2->WT((j + 1) % 3) = f1->WT((i + 2) % 3);
00270                         f1->WT((i + 1) % 3) = f2->WT((j + 2) % 3);
00271                 }
00272         }
00273 
00276         const char* Info(TRIMESH_TYPE &m)
00277         {
00278                 static char dump[60];
00279                 sprintf(dump,"%d -> %d %g\n", _pos.F()->V(0)-&m.vert[0], _pos.F()->V(1)-&m.vert[0],-_priority);
00280                 return dump;
00281         }
00282 
00285         static void Init(TRIMESH_TYPE &mesh, HeapType &heap)
00286         {
00287                 heap.clear();
00288                 FaceIterator fi;
00289                 for(fi = mesh.face.begin(); fi != mesh.face.end(); ++fi) {
00290                         if(!(*fi).IsD() && (*fi).IsW()) {
00291                                 for(unsigned int i = 0; i < 3; i++) {
00292                                         if( !(*fi).IsB(i) && !((*fi).FFp(i)->IsD()) && (*fi).FFp(i)->IsW() ) {
00293                                                 if((*fi).V1(i) - (*fi).V0(i) > 0) {
00294                                                         PosType p(&*fi, i);
00295                                                         Insert(heap, p,  IMark(mesh));
00296                                                 }
00297                                                         //heap.push_back( HeapElem( new MYTYPE(PosType(&*fi, i), mesh.IMark() )) );
00298                                         } //endif
00299                                 } //endfor
00300                         }
00301                 } //endfor
00302         }
00303 
00306         virtual void UpdateHeap(HeapType &heap)
00307         {
00308                 GlobalMark()++;
00309                 
00310                 // after flip, the new edge just created is the next edge
00311                 int flipped = (_pos.E() + 1) % 3;
00312                 
00313                 PosType pos(_pos.F(), flipped);
00314 
00315                 pos.F()->V(0)->IMark() = GlobalMark();
00316                 pos.F()->V(1)->IMark() = GlobalMark();
00317                 pos.F()->V(2)->IMark() = GlobalMark();
00318                 pos.F()->FFp(flipped)->V2(pos.F()->FFi(flipped))->IMark() = GlobalMark();
00319 
00320                 pos.FlipF(); pos.FlipE();
00321                 Insert(heap, pos, GlobalMark());
00322 
00323                 pos.FlipV(); pos.FlipE();
00324                 Insert(heap, pos, GlobalMark());
00325 
00326                 pos.FlipV(); pos.FlipE();
00327                 pos.FlipF(); pos.FlipE();
00328                 Insert(heap, pos, GlobalMark());
00329 
00330                 pos.FlipV(); pos.FlipE();
00331                 Insert(heap, pos, GlobalMark());
00332         }
00333 }; // end of PlanarEdgeFlip class
00334 
00335 
00336 template <class TRIMESH_TYPE, class MYTYPE>
00337 class TriEdgeFlip : public PlanarEdgeFlip<TRIMESH_TYPE, MYTYPE>
00338 {
00339 protected:
00340         typedef typename TRIMESH_TYPE::FaceType FaceType;
00341         typedef typename TRIMESH_TYPE::ScalarType ScalarType;
00342         typedef typename TRIMESH_TYPE::CoordType CoordType;
00343         typedef vcg::face::Pos<FaceType> PosType;
00344 
00345 public:
00349         inline TriEdgeFlip() {}
00350 
00354         inline TriEdgeFlip(const PosType pos, int mark)
00355         {
00356                 this->_pos = pos;
00357                 this->_localMark = mark;
00358                 this->_priority = ComputePriority();
00359         }
00360 
00364         inline TriEdgeFlip(const TriEdgeFlip &par)
00365         {
00366                 this->_pos = par.GetPos();
00367                 this->_localMark = par.GetMark();
00368                 this->_priority = par.Priority();
00369         }
00370         
00371 
00372         ScalarType ComputePriority()
00373         {
00374                 /*
00375                      1  
00376                     /|\
00377                    / | \
00378                   2  |  3 
00379                    \ | /
00380                     \|/
00381                      0
00382                  */
00383                 CoordType v0, v1, v2, v3;
00384                 int i = this->_pos.E();
00385                 v0 = this->_pos.F()->P0(i);
00386                 v1 = this->_pos.F()->P1(i);
00387                 v2 = this->_pos.F()->P2(i);
00388                 v3 = this->_pos.F()->FFp(i)->P2(this->_pos.F()->FFi(i));
00389                 
00390                 // if the sum of angles in v2 e v3 is > 180, then the triangle
00391                 // pair is not a delaunay triangulation
00392                 ScalarType alpha = math::Abs(Angle(v0 - v2, v1 - v2));
00393                 ScalarType beta = math::Abs(Angle(v0 - v3, v1 - v3));
00394                 this->_priority = 180 - math::ToDeg((alpha + beta));
00395                 return this->_priority;
00396         }
00397 };
00398 
00399 
00400 // This kind of flip minimize the variance of number of incident faces
00401 // on the vertices of two faces involved in the flip
00402 template <class TRIMESH_TYPE, class MYTYPE>
00403 class TopoEdgeFlip : public PlanarEdgeFlip<TRIMESH_TYPE, MYTYPE>
00404 {
00405 protected:
00406         typedef typename TRIMESH_TYPE::VertexPointer VertexPointer;
00407         
00408         typedef typename TRIMESH_TYPE::FaceType FaceType;
00409         typedef typename TRIMESH_TYPE::FacePointer FacePointer;
00410         typedef typename TRIMESH_TYPE::ScalarType ScalarType;
00411         typedef typename TRIMESH_TYPE::CoordType CoordType;
00412         typedef vcg::face::Pos<FaceType> PosType;
00413 
00414         typedef typename LocalOptimization<TRIMESH_TYPE>::HeapElem HeapElem;
00415         typedef typename LocalOptimization<TRIMESH_TYPE>::HeapType HeapType;
00416 
00417         typedef typename TRIMESH_TYPE::FaceIterator FaceIterator;
00418         typedef typename TRIMESH_TYPE::VertexIterator VertexIterator;
00419 
00420 public:
00424         inline TopoEdgeFlip() {}
00425 
00429         inline TopoEdgeFlip(const PosType pos, int mark)
00430         {
00431                 this->_pos = pos;
00432                 this->_localMark = mark;
00433                 this->_priority = ComputePriority();
00434         }
00435 
00439         inline TopoEdgeFlip(const TopoEdgeFlip &par)
00440         {
00441                 this->_pos = par.GetPos();
00442                 this->_localMark = par.GetMark();
00443                 this->_priority = par.Priority();
00444         }
00445         
00446 
00447         ScalarType ComputePriority()
00448         {
00449                 /*
00450                      1  
00451                     /|\
00452                    / | \
00453                   2  |  3 
00454                    \ | /
00455                     \|/
00456                      0
00457                  */
00458                 VertexPointer v0, v1, v2, v3;
00459                 int i = this->_pos.E();
00460                 v0 = this->_pos.F()->V0(i);
00461                 v1 = this->_pos.F()->V1(i);
00462                 v2 = this->_pos.F()->V2(i);
00463                 v3 = this->_pos.F()->FFp(i)->V2(this->_pos.F()->FFi(i));
00464                 
00465                 // This kind of flip minimize the variance of number of incident faces
00466                 // on the vertices of two faces involved in the flip
00467                 
00468                 ScalarType avg = (v0->Q() + v1->Q() + v2->Q() + v3->Q()) / 4.0; 
00469                 
00470                 ScalarType varbefore = (powf(v0->Q() - avg, 2.0) + 
00471                                         powf(v1->Q() - avg, 2.0) + 
00472                                                 powf(v2->Q() - avg, 2.0) + 
00473                                                 powf(v3->Q() - avg, 2.0)) / 4.0;
00474                 
00475                 ScalarType varafter = (powf(v0->Q() - 1 - avg, 2.0) +
00476                                powf(v1->Q() - 1 - avg, 2.0) +
00477                                        powf(v2->Q() + 1 - avg, 2.0) +
00478                                        powf(v3->Q() + 1 - avg, 2.0)) / 4.0; 
00479                 
00480                 this->_priority = varafter - varbefore;
00481                 return this->_priority;
00482         }
00483         
00484         
00488         void Execute(TRIMESH_TYPE &m)
00489         {
00490                 int i = this->_pos.E();
00491                 FacePointer f1 = this->_pos.F();
00492                 FacePointer f2 = f1->FFp(i);
00493                 int j = f1->FFi(i);
00494                 
00495                 // update the number of faces adjacent to vertices
00496                 f1->V0(i)->Q()--;
00497                 f1->V1(i)->Q()--;
00498                 f1->V2(i)->Q()++;
00499                 f2->V2(j)->Q()++;
00500                 
00501                 // do the flip
00502                 vcg::face::FlipEdge(*this->_pos.F(), this->_pos.E());
00503                 
00504                 // avoid texture coordinates swap after flip 
00505                 if (tri::HasPerWedgeTexCoord(m)) {
00506                         f2->WT((j + 1) % 3) = f1->WT((i + 2) % 3);
00507                         f1->WT((i + 1) % 3) = f2->WT((j + 2) % 3);
00508                 }
00509         }
00510         
00511         
00512         static void Init(TRIMESH_TYPE &m, HeapType &heap)
00513         {
00514                 // reset quality field for each vertex
00515                 VertexIterator vi;
00516                 for(vi = m.vert.begin(); vi != m.vert.end(); ++vi)
00517                         if(!(*vi).IsD())
00518                                 (*vi).Q() = 0;
00519                 
00520                 // for each vertex, put the number of incident faces in quality field
00521                 FaceIterator fi;
00522                 for(fi = m.face.begin(); fi != m.face.end(); ++fi)
00523                         if(!(*fi).IsD())
00524                                 for(int i = 0; i < 3; i++)
00525                                         (*fi).V(i)->Q()++;
00526                 
00527                 TriEdgeFlip<TRIMESH_TYPE, MYTYPE>::Init(m, heap);
00528         }
00529         
00530         
00531         void UpdateHeap(HeapType &heap)
00532         {
00533                 this->GlobalMark()++;
00534 
00535                 VertexPointer v0, v1, v2, v3;
00536                 int flipped = (this->_pos.E() + 1) % 3;
00537                 FacePointer f1 = this->_pos.F();
00538                 FacePointer f2 = this->_pos.F()->FFp(flipped);
00539 
00540                 v0 = f1->V0(flipped);
00541                 v1 = f1->V1(flipped);
00542                 v2 = f1->V2(flipped);
00543                 v3 = f2->V2(f1->FFi(flipped));
00544 
00545                 v0->IMark() = this->GlobalMark();
00546                 v1->IMark() = this->GlobalMark();
00547                 v2->IMark() = this->GlobalMark();
00548                 v3->IMark() = this->GlobalMark();
00549                 
00550                 // edges of the first face, except the flipped edge
00551                 for(int i = 0; i < 3; i++) if(i != flipped) {
00552                         PosType newpos(f1, i);
00553                         Insert(heap, newpos, this->GlobalMark());
00554                 }
00555 
00556                 // edges of the second face, except the flipped edge
00557                 for(int i = 0; i < 3; i++) if(i != f1->FFi(flipped)) {
00558                         PosType newpos(f2, i);
00559                         Insert(heap, newpos, this->GlobalMark());
00560                 }
00561 
00562                 // every edge with v0, v1 v3 of f1
00563                 for(int i = 0; i < 3; i++) {
00564                         PosType startpos(f1, i);
00565                         PosType pos(startpos);
00566 
00567                         do { // go to the first border (if there is one)
00568                                 pos.NextE();
00569                         } while(pos != startpos && !pos.IsBorder());
00570                         
00571                         // if a border is reached, set startpos here
00572                         if(pos.IsBorder())
00573                                 startpos = pos;
00574 
00575                         do {
00576                                 VertexPointer v = pos.VFlip();
00577                                 if(v != v0 && v != v1 && v != v2 && v != v3)
00578                                 Insert(heap, pos, this->GlobalMark());
00579 
00580                                 pos.NextE();
00581                         } while(pos != startpos && !pos.IsBorder());
00582                 }
00583 
00584                 PosType startpos(f2, (f1->FFi(flipped) + 2) % 3);
00585                 PosType pos(startpos);
00586 
00587                 do { // go to the first border (if there is one)
00588                         pos.NextE();
00589                 } while(pos != startpos && !pos.IsBorder());
00590                 
00591                 // if a border is reached, set startpos here
00592                 if(pos.IsBorder())
00593                         startpos = pos;
00594 
00595                 do {
00596                         VertexPointer v = pos.VFlip();
00597                         if(v != v0 && v != v1 && v != v2 && v != v3)
00598                         Insert(heap, pos, this->GlobalMark());
00599 
00600                         pos.NextE();
00601                 } while(pos != startpos && !pos.IsBorder());
00602         }
00603 };
00604 
00605 
00606 } // end of namespace tri
00607 } // end of namespace vcg
00608 
00609 #endif