vcglib: edge_collapse.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   History
00025 ****************************************************************************/
00026 
00027 #ifndef __VCG_TETRA_EDGE_COLLAPSE
00028 #define __VCG_TETRA_EDGE_COLLAPSE
00029 
00030 #include <vcg/space/tetra3.h>
00031 #include <vcg/complex/tetramesh/update/topology.h>
00032 #include <vcg/complex/tetramesh/update/normal.h>
00033 
00034 
00035 
00036 namespace vcg{
00037 namespace tetra{
00038 
00041 
00042 template <class TETRA_MESH_TYPE> 
00043 class EdgeCollapse
00044 {
00045         public:
00047   typedef       TETRA_MESH_TYPE TetraMeshType;
00049   typedef       typename TetraMeshType::TetraType TetraType;
00051   typedef       typename TetraType::VertexType VertexType;
00053   typedef       typename TetraMeshType::VertexIterator VertexIterator;
00055   typedef       typename TetraMeshType::TetraIterator TetraIterator;
00057   typedef       typename TetraType::VertexType::CoordType CoordType;
00059   typedef       typename TetraMeshType::VertexType::ScalarType ScalarType;
00061   typedef typename TetraMeshType::TetraContainer TetraContainer;
00063   typedef typename TetraMeshType::VertexContainer VertexContainer;
00065   typedef Pos<TetraType> PosType;
00067   typedef PosLoop<TetraType> PosLType;
00069   typedef typename vcg::tetra::UpdateTetraTopology<VertexContainer,TetraContainer> Topology;
00071   typedef  typename vcg::tetra::UpdateNormals<TetraMeshType> UpdateNormals;
00072 
00073 
00075         EdgeCollapse()
00076                 {
00077                 };
00078 
00079   ~EdgeCollapse()
00080                 {
00081                 };
00082 
00083   private:
00084 
00085         typedef pair <int,int> FacePair;
00086         struct Face
00087         {
00088                         VertexType* v[3];
00089 
00090       Face(     VertexType* a, VertexType* b,VertexType* c)
00091            {
00092                                                 assert((a!=b)&&(b!=c)&&(a!=c));
00093             v[0]=a;
00094             v[1]=b;
00095             v[2]=c;
00096             sort(v,v+3);
00097                                                 }
00098 
00099       const bool operator <(const Face & f) const 
00100       {
00101                                 return ((v[0]==f.v[0])?((v[1]==f.v[1])?(v[2]<f.v[2]):(v[1]<f.v[1])):(v[0]<f.v[0]));
00102                         }
00103 
00104                         const bool operator ==(const Face & f) const {
00105                         return ((v[0]==f.v[0])&&(v[1]==f.v[1])&&(v[2]==f.v[2]));
00106                         }
00107 
00108       };
00109 
00110         struct Edge{
00111                         VertexType* v0;
00112       VertexType* v1;
00113       Edge(     VertexType* a, VertexType* b){
00114                                                 assert(a!=b);
00115                                                 if(a<b) 
00116                                                         {v0=a;v1=b;}
00117                                                 else
00118                                                 {v1=a;v0=b;}
00119       }
00120                         
00121                         const bool operator <(const Edge & e) const {
00122                                 return (v0==e.v0)?(v1<e.v1):(v0<e.v0);
00123                         }
00124 
00125                         const bool operator ==(const Edge & e) const {
00126                         return (v0==e.v0)&&(v1==e.v1);
00127                         }
00128 
00129 };
00130 struct TetraSets
00131 {
00132   std::vector <TetraType*> v0;
00133   std::vector <TetraType*> v1;
00134   std::vector <TetraType*> v0_U_v1;
00135   std::vector <TetraType*> no_E;
00136   std::vector <TetraType*> E;
00137   std::vector <char> indexE;
00138   std::vector <char> indexv0;
00139   std::vector <char> indexv1;
00140 
00141   void clear()
00142   {
00143     v0.clear();
00144     v1.clear();
00145     v0_U_v1.clear();
00146     no_E.clear();
00147     E.clear();
00148         indexE.clear();
00149         indexv0.clear();
00150         indexv1.clear();
00151   }
00152 };
00153 
00154 
00155 
00156 
00157 
00158 static map<Edge,char> & _EdgeMark(){
00159         static map<Edge,char>  em;
00160         return em;
00161 };
00162 
00163 static map<Face,char> & _FaceMark(){
00164         static map<Face,char> fm;
00165         return fm;
00166 }
00167 
00168 static VertexType &_DummyV(){
00169         static VertexType _dv;
00170         return _dv;
00171 }
00172 
00173 static TetraSets &_Sets(){
00174         static TetraSets _s;
00175         return _s;
00176 }
00177 
00178 
00179 
00181 static FacePair _FindNoEdgeFace(TetraType *t,int edge)
00182 {       
00183                                 //as first I find the 2 faces on the opposite sides of the egde
00184         int fa0=Tetra::FofE(edge,0);
00185                                 int fa1=Tetra::FofE(edge,1);
00186 
00187                                 //then find the faces that remain
00188                                 int fa2=(fa0+1)%4;
00189                                 while ((fa2==fa0)||(fa2==fa1))
00190                                 {
00191                                         fa2=(fa2+1)%4;
00192                                 }
00193                                 int fa3=(fa2+1)%4;
00194                                 while ((fa3==fa0)||(fa3==fa1)||(fa3==fa2))
00195                                 {
00196                                         fa3=(fa3+1)%4;
00197                                 }
00198         return FacePair(fa2,fa3);
00199 }
00200 
00201 #ifdef _DEBUG
00202 static void _AssertingVolume(TetraType *t)
00203 {
00204                 //assert(t->ComputeVolume() >0);
00205                 assert(vcg::ComputeVolume<TetraType>(*t)>0);
00206 }
00207 #endif
00208 
00209 
00211 static int _Collapse(PosType p,CoordType NewP)
00212 {
00213           int n_deleted=0;
00214           vector<TetraType*> To_Del;
00215       VertexType *Vrem=(p.T()->V(Tetra::VofE(p.E(),0)));
00216       VertexType *Vdel=(p.T()->V(Tetra::VofE(p.E(),1)));
00217       //Vrem->P()=(Vrem->P()*alfa)+(Vdel->P()*(1.f-alfa));
00218       Vrem->P()=NewP;
00219       PosLType pos(p.T(),p.F(),p.E(),p.V());
00220       pos.Reset();
00221       To_Del.reserve(40);
00222       To_Del.clear();
00223                         while (!pos.LoopEnd())
00224                         {
00225                                 //get the two faces that doesn't share the edge
00226                                 FacePair fp=_FindNoEdgeFace(pos.T(),pos.E());
00227                                 int fa0=fp.first;
00228                                 int fa1=fp.second;
00229 
00230                                 //now set the T-T topology on that faces
00231                                 TetraType *tleft=pos.T()->TTp(fa0);
00232                                 TetraType *tright=pos.T()->TTp(fa1);
00233                                 int ileft=pos.T()->TTi(fa0);
00234                                 int iright=pos.T()->TTi(fa1);
00235                                 
00236                                  //in this case I cannot do the collapse
00237                                 assert (!((pos.T()==tleft)&&(pos.T()==tright)));
00238                                 
00239                                 //case no one is extern face
00240                                 if ((!pos.T()->IsBorderF(fa0))&&(!pos.T()->IsBorderF(fa1)))
00241                                 //connect the 2 tetrahedrons
00242                                 Topology::_AttachTTTopology(tleft,ileft,tright,iright); 
00243                                 else
00244                                   //case f2 is an extern face
00245                                 if (pos.T()->IsBorderF(fa0))
00246                                 {
00247                                         tright->TTp(iright)=tright;
00248                                         tright->TTi(iright)=iright;
00249                                 }
00250         
00251         else //case fa1 is an extern face
00252         //if ((pos.T()->IsBorderF(fa3))
00253                                 {
00254                                         tleft->TTp(ileft)=tleft;
00255                                         tleft->TTi(ileft)=ileft;        
00256                                 }
00257                                 
00258                                 //end setting T-T topology
00259 
00260                                 //setting the V-T topology
00261 
00262                                 //i remove the tetrahedrons that have the edge
00263                                 // to collapse
00264                                 Topology::DetachVTTopology(pos.T());
00265 
00266                                 //end setting the V-T topology  
00267                                 To_Del.push_back(pos.T());
00268                                 pos.NextT();
00269                                 n_deleted++;
00270 //        tm.tn--;
00271       }
00272 
00273       //delting old tetrahedrons
00274       typename vector<TetraType*>::iterator ti;
00275       for (ti=To_Del.begin();ti<To_Del.end();ti++)
00276         (*ti)->SetD();
00277 
00278                         //now I cycle on the tetrahedron that had the old vertex
00279                         //reassegning the new one.
00280 
00281                         VTIterator<TetraType> VTi(Vdel->VTb(),Vdel->VTi());
00282                         while (!VTi.End())
00283                         {       
00284                                 TetraType *T_Change=VTi.Vt();
00285                                 int index=VTi.Vi();
00286                                 //VTi++;
00287                                 //assegning the vertex that remain
00288                                 T_Change->V(index)=Vrem;
00289                                 Topology::DetachVTTopology(Vdel,T_Change);
00290                                 Topology::InsertVTTopology(Vrem,index,T_Change);
00291                                 //that's cause i restart everytime in the chain 
00292                                 //from the vertex
00293                             VTi.Vt()=Vdel->VTb();
00294                                 VTi.Vi()=Vdel->VTi();
00295 #ifdef _DEBUG
00296        _AssertingVolume(T_Change);
00297 #endif
00298        
00299                         }
00300 
00301       if (Vdel->IsB())
00302         Vrem->SetB();
00303       //set as deleted the vertex
00304                         Vdel->SetD();
00305                         return n_deleted;
00306 }
00307 
00308 
00309 static void orMarkE(Edge E,char M)
00310 {
00311  typename map<Edge,char>::iterator EI;
00312  EI=_EdgeMark().find(E);
00313  if (EI==_EdgeMark().end())
00314   _EdgeMark().insert (pair<Edge,char>(E,M));
00315  else
00316    (*EI).second|=M;
00317 }
00318 
00319 static bool isMarkedE(Edge E,char M)
00320 {
00321  typename map<Edge,char>::iterator EI;
00322  EI=_EdgeMark().find(E);
00323  if (EI==_EdgeMark().end())
00324     return false;
00325  else return (((*EI).second & M)!=0);
00326 }
00327 
00328 static void orMarkF(Face F,char M)
00329 {
00330  typename map< Face,char>::iterator FI;
00331  FI=_FaceMark().find(F);
00332  if (FI==_FaceMark().end())
00333   _FaceMark().insert (pair<Face,char>(F,M));
00334  else
00335    (*FI).second|=M;
00336 }
00337 
00338 static bool isMarkedF(Face F,char M)
00339 {
00340  typename map<Face,char>::iterator FI;
00341  FI=_FaceMark().find(F);
00342  if (FI==_FaceMark().end())
00343     return false;
00344  else return (((*FI).second & M)!=0);
00345 }
00346 
00347 
00349 static bool _LinkConditionsF(PosType pos) 
00350 {       
00351     const int LINK_V0 = 0x00000001;
00352     const int LINK_EE = 0x00000002;
00353    
00354     _EdgeMark().clear();
00355 
00356                 // Mark edges of ve0 
00357     typename vector< TetraType *>::iterator ti=_Sets().v0.begin(); 
00358     typename vector< char >::iterator en=_Sets().indexv0.begin();
00359         VertexType *v0=(*ti)->V(*en);
00360     while (ti!=_Sets().v0.end())
00361     {
00362           assert(v0==(*ti)->V(*en));
00363       //put dummy face
00364       for (int f=0;f<3;f++)
00365       {
00366        int f_test=Tetra::FofV((*en),f);
00367         if  ((*ti)->IsBorderF(f_test))
00368         {
00369           orMarkF(Face((*ti)->V(Tetra::VofF(f_test,0)),(*ti)->V(Tetra::VofF(f_test,1)),&_DummyV()),LINK_V0);
00370           orMarkF(Face((*ti)->V(Tetra::VofF(f_test,1)),(*ti)->V(Tetra::VofF(f_test,2)),&_DummyV()),LINK_V0);
00371           orMarkF(Face((*ti)->V(Tetra::VofF(f_test,2)),(*ti)->V(Tetra::VofF(f_test,0)),&_DummyV()),LINK_V0);
00372         }
00373       }
00374      ti++;
00375      en++;
00376     }
00377     
00378     ti=_Sets().E.begin(); 
00379     en=_Sets().indexE.begin();
00380     //mark them as intersection
00381     while (ti!=_Sets().E.end())
00382     {
00383       //faces on the edge
00384       int f0=Tetra::FofE((*en),0);
00385       int f1=Tetra::FofE((*en),1);
00386 
00387       if  ((*ti)->IsBorderF(f0))
00388       {
00389           orMarkF(Face((*ti)->V(Tetra::VofF(f0,0)),(*ti)->V(Tetra::VofF(f0,1)),&_DummyV()),LINK_EE);
00390           orMarkF(Face((*ti)->V(Tetra::VofF(f0,1)),(*ti)->V(Tetra::VofF(f0,2)),&_DummyV()),LINK_EE);
00391           orMarkF(Face((*ti)->V(Tetra::VofF(f0,2)),(*ti)->V(Tetra::VofF(f0,0)),&_DummyV()),LINK_EE);
00392       }
00393 
00394       if  ((*ti)->IsBorderF(f1))
00395       {
00396           orMarkF(Face((*ti)->V(Tetra::VofF(f1,0)),(*ti)->V(Tetra::VofF(f1,1)),&_DummyV()),LINK_EE);
00397           orMarkF(Face((*ti)->V(Tetra::VofF(f1,1)),(*ti)->V(Tetra::VofF(f1,2)),&_DummyV()),LINK_EE);
00398           orMarkF(Face((*ti)->V(Tetra::VofF(f1,2)),(*ti)->V(Tetra::VofF(f1,0)),&_DummyV()),LINK_EE);
00399       }
00400 
00401       ti++;
00402       en++;
00403     }
00404    
00405     //and at the end I verify if the intersection is equal to the star of the edge
00406     ti=_Sets().v1.begin(); 
00407     en=_Sets().indexv1.begin();
00408         VertexType *v1=(*ti)->V(*en);
00409     while (ti!=_Sets().v1.end())
00410     {
00411           assert(v1==(*ti)->V(*en));
00412       //dummy edges control
00413       for (int f=0;f<3;f++)
00414       {
00415        int f_test=Tetra::FofV((*en),f);
00416         if  ((*ti)->IsBorderF(f_test))
00417         {
00418           //control all the 3 edges
00419           Face f_test0=Face((*ti)->V(Tetra::VofF(f_test,0)),(*ti)->V(Tetra::VofF(f_test,1)),&_DummyV());
00420           Face f_test1=Face((*ti)->V(Tetra::VofF(f_test,1)),(*ti)->V(Tetra::VofF(f_test,2)),&_DummyV());
00421           Face f_test2=Face((*ti)->V(Tetra::VofF(f_test,2)),(*ti)->V(Tetra::VofF(f_test,0)),&_DummyV());
00422           if (((isMarkedF(f_test0,LINK_V0))&&(!isMarkedF(f_test0,LINK_EE)))||
00423             ((isMarkedF(f_test1,LINK_V0))&&(!isMarkedF(f_test1,LINK_EE)))||
00424             ((isMarkedF(f_test2,LINK_V0))&&(!isMarkedF(f_test2,LINK_EE))))
00425                                         {
00426 //                                              FAIL::LKF();
00427             return false;
00428                                         }
00429         }
00430       }
00431       ti++;
00432       en++;
00433     }
00434     return true;
00435 }
00436 
00437 
00439 static bool _LinkConditionsE(PosType pos) 
00440 {       
00441     const int LINK_V0 = 0x00000001;
00442     const int LINK_EE = 0x00000002;
00443    
00444     _FaceMark().clear();
00445 
00446                 // Mark edges of ve0 
00447     typename vector< TetraType *>::iterator ti=_Sets().v0.begin(); 
00448     typename vector< char >::iterator en=_Sets().indexv0.begin();
00449     while (ti!=_Sets().v0.end())
00450     {
00451       //put dummy edge
00452       for (int f=0;f<3;f++)
00453       {
00454        int f_test=Tetra::FofV((*en),f);
00455         if  ((*ti)->IsBorderF(f_test))
00456         {
00457           orMarkE(Edge((*ti)->V(Tetra::VofF(f_test,0)),&_DummyV()),LINK_V0);
00458           orMarkE(Edge((*ti)->V(Tetra::VofF(f_test,1)),&_DummyV()),LINK_V0);
00459           orMarkE(Edge((*ti)->V(Tetra::VofF(f_test,2)),&_DummyV()),LINK_V0);
00460         }
00461       }
00462      ti++;
00463      en++;
00464     }
00465     
00466     ti=_Sets().E.begin(); 
00467     en=_Sets().indexE.begin();
00468     //mark them as intersection
00469     while (ti!=_Sets().E.end())
00470     {
00471       //faces on the edge
00472       int f0=Tetra::FofE((*en),0);
00473       int f1=Tetra::FofE((*en),1);
00474 
00475       if  ((*ti)->IsBorderF(f0))
00476       {
00477           orMarkE(Edge((*ti)->V(Tetra::VofF(f0,0)),&_DummyV()),LINK_EE);
00478           orMarkE(Edge((*ti)->V(Tetra::VofF(f0,1)),&_DummyV()),LINK_EE);
00479           orMarkE(Edge((*ti)->V(Tetra::VofF(f0,2)),&_DummyV()),LINK_EE);
00480       }
00481 
00482       if  ((*ti)->IsBorderF(f1))
00483       {
00484           orMarkE(Edge((*ti)->V(Tetra::VofF(f1,0)),&_DummyV()),LINK_EE);
00485           orMarkE(Edge((*ti)->V(Tetra::VofF(f1,1)),&_DummyV()),LINK_EE);
00486           orMarkE(Edge((*ti)->V(Tetra::VofF(f1,2)),&_DummyV()),LINK_EE);
00487       }
00488 
00489       ti++;
00490       en++;
00491     }
00492    
00493     //and at the end I verify if the intersection is equal to the star of the edge
00494     ti=_Sets().v1.begin(); 
00495     en=_Sets().indexv1.begin();
00496     while (ti!=_Sets().v1.end())
00497     {
00498 
00499       //dummy edges control
00500       for (int f=0;f<3;f++)
00501       {
00502        int f_test=Tetra::FofV((*en),f);
00503         if  ((*ti)->IsBorderF(f_test))
00504         {
00505           //control all the 3 edges
00506           Edge e_test0=Edge((*ti)->V(Tetra::VofF(f_test,0)),&_DummyV());
00507           Edge e_test1=Edge((*ti)->V(Tetra::VofF(f_test,1)),&_DummyV());
00508           Edge e_test2=Edge((*ti)->V(Tetra::VofF(f_test,2)),&_DummyV());
00509           if (((isMarkedE(e_test0,LINK_V0))&&(!isMarkedE(e_test0,LINK_EE)))||
00510             ((isMarkedE(e_test1,LINK_V0))&&(!isMarkedE(e_test1,LINK_EE)))||
00511             ((isMarkedE(e_test2,LINK_V0))&&(!isMarkedE(e_test2,LINK_EE))))
00512                                         {
00513 //                                              FAIL::LKE();
00514             return false;
00515                                         }
00516         }
00517       }
00518       ti++;
00519       en++;
00520     }
00521     return true;
00522 }
00523 
00524 static bool _QuickConditions(PosType pos)
00525 {       
00526   VertexType *v0=pos.T()->V(Tetra::VofE(pos.E(),0));
00527   VertexType *v1=pos.T()->V(Tetra::VofE(pos.E(),1));
00528 
00529   //if the two vertices are of border and the edge is not a border edge
00530   //we can do it.
00531 
00532   bool border0=v0->IsB();
00533   bool border1=v1->IsB();
00534   bool bordere=Topology::IsExternEdge(pos.T(),pos.E());
00535 
00536   //first case vertex external and edge internal
00537         if ((border0 && border1)&&(!bordere))
00538         {
00539                 return false;
00540         }
00541         else 
00542         {
00543         
00544         typename vector< TetraType *>::iterator ti=_Sets().E.begin(); 
00545         typename vector< char >::iterator en=_Sets().indexE.begin();
00546                 //mark them as intersection
00547     while (ti!=_Sets().E.end())
00548     {
00549                 //get the two faces that doesn't share the edge
00550                 FacePair fp=_FindNoEdgeFace(pos.T(),pos.E());
00551                 int fa0=fp.first;
00552                 int fa1=fp.second;
00553 
00554                 //now set the T-T topology on that faces
00555                 TetraType *tleft=pos.T()->TTp(fa0);
00556                 TetraType *tright=pos.T()->TTp(fa1);
00557                 int ileft=pos.T()->TTi(fa0);
00558                 int iright=pos.T()->TTi(fa1);
00559                                 
00560                  //in this case I cannot do the collapse
00561                 if (((pos.T()==tleft)&&(pos.T()==tright)))
00562                 {
00563                         return false;
00564                 }
00565                 ti++;
00566                 en++;
00567         }               
00568         
00569         }
00570                 return true;
00571 }
00572 
00574 static bool _LinkConditionsV() 
00575 {       
00576     const int LINK_V0 = VertexType::NewBitFlag();
00577         const int LINK_V1 = VertexType::NewBitFlag();
00578     const int LINK_EE = VertexType::NewBitFlag();
00579     
00580         const int NOT_LINKED = ~(LINK_V0 | LINK_V1 | LINK_EE);
00581     _DummyV().Flags() &= NOT_LINKED;
00582 
00583     VertexType *vt0;
00584     VertexType *vt1;
00585     VertexType *vt2;
00586     VertexType *vt3;
00587                 
00588 
00589    typename vector< TetraType *>::iterator ti=_Sets().v0_U_v1.begin(); 
00590     
00591     //reset all link flags
00592     while (ti!=_Sets().v0_U_v1.end())
00593     {
00594       for(int i=0;i<4;i++)
00595         (*ti)->V(i)->Flags() &= NOT_LINKED;
00596       ti++;
00597     }
00598 
00599 
00600     //also in the ones that appartain to the edge
00601     typename  vector< char >::iterator en;
00602     ti=_Sets().E.begin(); 
00603     en=_Sets().indexE.begin();
00604     //reset all link flags for intersection and in the same
00605     //time mark them as intersection
00606     while (ti!=_Sets().E.end())
00607     {
00608       for(int i=0;i<4;i++)
00609       {
00610         (*ti)->V(i)->Flags() &= NOT_LINKED;
00611         (*ti)->V(i)->Flags() |= LINK_EE;
00612       }
00613 
00614       //dummy vertex
00615 
00616       //faces on the edge
00617       int f0=Tetra::FofE((*en),0);
00618       int f1=Tetra::FofE((*en),1);
00619       
00620       if  (((*ti)->IsBorderF(f0))||((*ti)->IsBorderF(f1)))
00621          _DummyV().Flags() |= LINK_EE;
00622 
00623       ti++;
00624       en++;
00625     }
00626 
00627 
00628                 // Mark vertices of ve0 
00629     ti=_Sets().v0.begin();
00630     en=_Sets().indexv0.begin();
00631 
00632     while (ti!=_Sets().v0.end())
00633     {
00634       for(int i=0;i<4;i++)
00635         (*ti)->V(i)->Flags() |= LINK_V0;
00636       
00637       //dummy faces on the vertex
00638       int f0=Tetra::FofV((*en),0);
00639       int f1=Tetra::FofV((*en),1);
00640       int f2=Tetra::FofV((*en),2);
00641 
00642       if  (((*ti)->IsBorderF(f0))||((*ti)->IsBorderF(f1))||((*ti)->IsBorderF(f2)))
00643         _DummyV().Flags() |= LINK_V0;
00644          
00645       ti++;
00646       en++;
00647     }
00648 
00649     //and at the end I verify if the intersection is equal to the star of the edge
00650     bool correct=true;
00651     ti=_Sets().v1.begin(); 
00652     en=_Sets().indexv1.begin();
00653 
00654     while (ti!=_Sets().v1.end())
00655     {
00656       vt0=(*ti)->V(0);
00657       vt1=(*ti)->V(1);
00658       vt2=(*ti)->V(2);
00659       vt3=(*ti)->V(3);
00660 
00661       if ((vt0->Flags()& LINK_V0)&&(!(vt0->Flags()& LINK_EE)))
00662         correct=false;
00663       else
00664       if ((vt1->Flags()& LINK_V0)&&(!(vt1->Flags()& LINK_EE)))
00665         correct=false;
00666       else
00667       if ((vt2->Flags()& LINK_V0)&&(!(vt2->Flags()& LINK_EE)))
00668         correct=false;
00669       else
00670       if ((vt3->Flags()& LINK_V0)&&(!(vt3->Flags()& LINK_EE)))
00671         correct=false;
00672 
00673        //dummy vertex control
00674       int f0=Tetra::FofV((*en),0);
00675       int f1=Tetra::FofV((*en),1);
00676       int f2=Tetra::FofV((*en),2);
00677 
00678       if  (((*ti)->IsBorderF(f0))||((*ti)->IsBorderF(f1))||((*ti)->IsBorderF(f2)))
00679         if ((_DummyV().Flags()& LINK_V0)&&(!(_DummyV().Flags()& LINK_EE)))
00680           correct=false;
00681 
00682       if (!correct)
00683       {
00684         VertexType::DeleteBitFlag(LINK_EE);
00685         VertexType::DeleteBitFlag(LINK_V1);
00686         VertexType::DeleteBitFlag(LINK_V0); 
00687 //                              FAIL::LKV();
00688         return (false);
00689       }
00690       en++;
00691       ti++;
00692     }
00693     VertexType::DeleteBitFlag(LINK_EE);
00694     VertexType::DeleteBitFlag(LINK_V1);
00695     VertexType::DeleteBitFlag(LINK_V0);
00696     return true;
00697 }
00698 
00700 static bool _FlipCondition(PosType pos,CoordType NewP)
00701 {       
00702   int edge=pos.E();
00703   VertexType *ve0=pos.T()->V(Tetra::VofE(edge,0));
00704   VertexType *ve1=pos.T()->V(Tetra::VofE(edge,1));
00705   CoordType oldpos0;
00706   CoordType oldpos1;
00707 
00708   typename  vector< TetraType *>::iterator ti=_Sets().no_E.begin();
00709 
00710   //saving old position
00711   oldpos0 = ve0->P();
00712   oldpos1 = ve1->P();
00713 
00714   //assegning new position
00715   ve0->P() =NewP;
00716   ve1->P() =NewP;
00717 
00718         while (ti!=_Sets().no_E.end())
00719     {
00720                         assert(!(*ti)->IsD());
00721                         assert((((*ti)->V(0)==ve0)||((*ti)->V(1)==ve0)||((*ti)->V(2)==ve0)||((*ti)->V(3)==ve0))^
00722             (((*ti)->V(0)==ve1)||((*ti)->V(1)==ve1)||((*ti)->V(2)==ve1)||((*ti)->V(3)==ve1)));
00723                         if (vcg::ComputeVolume<TetraType>(**ti)<=0)
00724                         {       
00725 //                              FAIL::VOL();
00726                                 ve0->P()=oldpos0;
00727                                 ve1->P()=oldpos1;
00728                             return false;
00729                         }
00730                         ti++;   
00731         }
00732 
00733   //reset initial value
00734         ve0->P()=oldpos0;
00735         ve1->P()=oldpos1;
00736 
00737         return true;
00738 }
00739 
00741 static void _InitTetrahedronValues(VertexType* v)
00742 {
00743  
00744   VTIterator<TetraType> VTi= VTIterator<TetraType>(v->VTb(),v->VTi());
00745   while (!VTi.End())
00746   {
00747     if (TetraType::HasTetraQuality())
00748     {
00749       VTi.Vt()->ComputeAspectRatio();
00750     }
00751 
00752     if (TetraType::HasTetraNormal())
00753     {
00754       VTi.Vt()->ComputeNormal();
00755     }
00756 
00757     ++VTi;
00758   }
00759 
00760   VTi.Vt()=v->VTb();
00761   VTi.Vi()=v->VTi();
00762   while (!VTi.End())
00763   {
00764     for (int i=0;i<4;i++)
00765     {
00766       if (VTi.Vt()->V(i)->IsB())
00767       {
00768         if (VertexType::HasNormal())
00769         UpdateNormals::PerVertex(VTi.Vt()->V(i));
00770       }
00771       
00772     }
00773       ++VTi;
00774   }
00775 
00776 }
00777 
00778 public:
00779 
00781 static void Reset(){
00782         _EdgeMark().clear();
00783         _FaceMark().clear();
00784         _Sets().clear();
00785         _DummyV().ClearFlags();
00786 }
00789 static ScalarType AspectRatioCollapsed(PosType p)
00790 {
00791   //PosL pos=PosL(p.T(),p.F(),p.E(),p.V());
00792    PosLoop<TetraType> pos=PosLoop<TetraType>(p.T(),p.F(),p.E(),p.V());
00793   pos.Reset();
00794   int num=0;
00795   ScalarType ratio_media=0.f;
00796   while(!pos.end())
00797   {
00798     ratio_media+=pos.T()->AspectRatio();
00799     pos.NextT();
00800     num++;
00801   }
00802   ratio_media=ratio_media/num;
00803   return (ratio_media);
00804 }
00805 
00806 
00808 static bool  CheckPreconditions(PosType pos,CoordType NewP)
00809 {       
00810    VertexType *v0=pos.T()->V(Tetra::VofE(pos.E(),0));
00811    VertexType *v1=pos.T()->V(Tetra::VofE(pos.E(),1));
00812   //if the two vertices are of border and the edge is not a border edge
00813   //we can do it.
00814   bool border0=v0->IsB();
00815   bool border1=v1->IsB();
00816   bool bordere=Topology::IsExternEdge(pos.T(),pos.E());
00817         if (!_QuickConditions(pos))
00818         {
00819                 //FAIL::BOR();
00820                 return false;
00821         }
00822  // //first case vertex external and edge internal
00823         //if ((border0 && border1)&&(!bordere))
00824         //{
00825         //      //FAIL::BOR();
00826         //      return false;
00827         //}
00828         else
00829   //if both vertex are internal so is enougth to verify flip conditions
00830         if ((!border0) && (!border1))
00831            return (_FlipCondition(pos,NewP));
00832         else
00833         //if the edge is internal is enougth to verify link condition on vertex
00834         if (!bordere)
00835       return((_FlipCondition(pos,NewP))&&(_LinkConditionsV()));
00836         else
00837         //at the end if trh edge is on the border we must verify also with the complete test
00838           return ((_FlipCondition(pos,NewP))&&(_LinkConditionsV())&&(_LinkConditionsE(pos))&&(_LinkConditionsF(pos)));
00839    //return false;
00840 }
00841 
00843 static ScalarType VolumeOriginal()
00844 {
00845   typename  vector< TetraType *>::iterator ti=_Sets().v0_U_v1.begin(); 
00846   ScalarType vol=0;
00847   while (ti!=_Sets().v0_U_v1.end())
00848   {
00849     vol+=(*ti)->Volume();
00850     ti++;
00851   }
00852   return vol;
00853 }
00854 
00856 static ScalarType VolumeSimulateCollapse(PosType Pos,CoordType &newP)
00857 {
00858   VertexType *Vrem=(Pos.T()->V(Tetra::VofE(Pos.E(),0)));
00859   VertexType *Vdel=(Pos.T()->V(Tetra::VofE(Pos.E(),1)));
00860 
00861   if (Vrem!=Pos.T()->V(Pos.V()))
00862     swap<VertexType*>(Vdel,Vrem);
00863 
00864   ScalarType vol=0;
00865   CoordType oldpos = Vrem->P();
00866  
00867 //move vertex that remain in the new position
00868   Vrem->P() = newP;
00869 
00870   typename vector< TetraType *>::iterator ti=_Sets().no_E.begin(); 
00871 
00872   while (ti!=_Sets().no_E.end())
00873   {
00874  /*       Tetra3<ScalarType> T=Tetra3<ScalarType>();
00875         T.P0(0)=(*ti)->V(0)->cP();
00876         T.P1(0)=(*ti)->V(1)->cP();
00877         T.P2(0)=(*ti)->V(2)->cP();
00878         T.P3(0)=(*ti)->V(3)->cP();
00879        
00880                 vol+=T.ComputeVolume(); */
00881 //              vol+= vcg::ComputeVolume<TetraType>(*((Tetra3<ScalarType>*)&*ti));
00882                                         
00883                 vol+= vcg::ComputeVolume(**ti);
00884         ti++;
00885   }
00886   Vrem->P()=oldpos;
00887   return vol;
00888 }
00889 
00891 static void FindSets(vcg::tetra::Pos<TetraType> pos)
00892 {
00893  
00894   _Sets().clear();
00895   int size=40;
00896   _Sets().v0.reserve(size);
00897   _Sets().indexv0.reserve(size);
00898   _Sets().v1.reserve(size);
00899   _Sets().indexv1.reserve(size);
00900   _Sets().v0_U_v1.reserve(size*2);
00901   _Sets().no_E.reserve(size*2);
00902   _Sets().E.reserve(size);
00903   _Sets().indexE.reserve(size);
00904   
00905   int edge =pos.E();
00906 
00907   VertexType *ve0=pos.T()->V(Tetra::VofE(edge,0));
00908   VertexType *ve1=pos.T()->V(Tetra::VofE(edge,1));
00909         
00910         // put all tetrahedrons in the first one vector and in the union
00911   VTIterator<TetraType> vf0(ve0->VTb(),ve0->VTi());
00912   while (!vf0.End())
00913   {
00914     //set of ve0
00915     _Sets().v0.push_back(vf0.Vt());
00916     _Sets().indexv0.push_back(vf0.Vi());
00917     //set of union
00918     _Sets().v0_U_v1.push_back(vf0.Vt());
00919     //set of union minus intersection
00920     if ((vf0.Vt()->V(0)!=ve1)&&(vf0.Vt()->V(1)!=ve1)&&(vf0.Vt()->V(2)!=ve1)&&(vf0.Vt()->V(3)!=ve1))
00921                   _Sets().no_E.push_back(vf0.Vt());
00922     ++vf0;
00923         }
00924 
00925   //second vertex iteration
00926   vf0.Vt()=ve1->VTb();
00927   vf0.Vi()=ve1->VTi();
00928   
00929   while (!vf0.End())
00930   {
00931     //set of ve1
00932     _Sets().v1.push_back(vf0.Vt());
00933     _Sets().indexv1.push_back(vf0.Vi());
00934     //set of union
00935     _Sets().v0_U_v1.push_back(vf0.Vt());
00936     //set of union minus intersection 
00937     if ((vf0.Vt()->V(0)!=ve0)&&(vf0.Vt()->V(1)!=ve0)&&(vf0.Vt()->V(2)!=ve0)&&(vf0.Vt()->V(3)!=ve0))
00938                   _Sets().no_E.push_back(vf0.Vt());
00939     ++vf0;
00940         }
00941 
00942   //erase duplicated tetrahedrons from the union set
00943   sort(_Sets().v0_U_v1.begin(),_Sets().v0_U_v1.end());
00944   unique(_Sets().v0_U_v1.begin(),_Sets().v0_U_v1.end());
00945 
00946   //now compute the intersection
00947   PosLType PL(pos.T(),pos.F(),pos.E(),pos.V());
00948 
00949     //mark the vertex on the edge
00950     while (!PL.LoopEnd())
00951     {
00952       _Sets().E.push_back(PL.T());
00953       _Sets().indexE.push_back(PL.E());
00954       PL.NextT();
00955     }
00956 
00957 }
00958 
00960 static int DoCollapse(PosType p,CoordType newP)
00961 {
00962   VertexType *v=p.T()->V(p.V());
00963   assert(p.T()->HasVTAdjacency());
00964   int n_del=_Collapse(p,newP);
00965   _InitTetrahedronValues(v);
00966   return n_del;
00967 }
00968 
00969 
00970 };
00971 }//end namespace
00972 }//end namespace
00973 #endif