vcglib: edge_split.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_SPLIT
00028 #define __VCG_TETRA_EDGE_SPLIT
00029 
00030 #include <vcg/simplex/tetrahedron/pos.h>
00031 #include <vcg/complex/tetramesh/allocate.h>
00032 #include <vcg/complex/tetramesh/update/topology.h>
00033 #include <vcg/space/tetra.h>
00034 namespace vcg{
00035 namespace tetra{
00036 
00039 
00040 
00041 template <class TETRA_MESH_TYPE> 
00042 class EdgeSplit
00043         {
00044         public:
00046   typedef       typename TETRA_MESH_TYPE TetraMeshType;
00048   typedef       typename TetraMeshType::TetraType TetraType;
00050         typedef typename TetraType::VertexType VertexType;
00052   typedef       typename TetraMeshType::VertexIterator VertexIterator;
00054   typedef       typename TetraMeshType::TetraIterator TetraIterator;
00056         typedef typename TetraType::VertexType::CoordType CoordType;
00058   typedef typename TetraMeshType::TetraContainer TetraContainer;
00060   typedef typename TetraMeshType::VertexContainer VertexContainer;
00062   typedef PosLoop<TetraType> PosType;
00064   typedef vcg::tetra::UpdateTetraTopology<VertexContainer,TetraContainer> Topology;
00066   typedef  vcg::tetra::Allocator<TetraMeshType> TetraAllocator;
00068         EdgeSplit()
00069                 {
00070                 };
00071 
00072   ~EdgeSplit()
00073                 {
00074                 };
00075 
00076 private:
00078 TetraType* _toDel[30];
00080 int _nT;
00081 
00082 Topology _Topo;
00083 
00085 
00086 VertexType* _AddVertexEdge(TetraMeshType &tm,const TetraType &t,const int &edge,const double &alfa)
00087 {
00088   VertexType *v0=(VertexType*)t.V(Tetra::VofE(edge,0));
00089         VertexType *v1=(VertexType*)t.V(Tetra::VofE(edge,1));
00090         Allocator<TetraMeshType> All= Allocator<TetraMeshType>();
00091         VertexIterator vn=All.AddVertices(tm,1);
00092         vn->Flags()=0;
00093         vn->VTb()=NULL;
00094         vn->VTi()=-1;
00095   vn->P()=(v0->P()*alfa)+(v1->P()*(1.0f-alfa));
00096   return (&(*vn));
00097 }
00098 
00100 void _SetDefultVTTopology(TetraType *t)
00101 {
00102 unsigned int j;
00103 for (j=0;j<4;j++)
00104 {
00105         t->TVp(j) = NULL;
00106         t->TVi(j) = -1;
00107 }
00108 }
00109 
00112 static int _GetMapVertEdgeRot(const int &indexE,const int &indexV)
00113         {       
00114                 static int mapvertedgerot[12][4]={
00115                                                   {0,3,1,2},
00116                                                   {0,1,2,3},
00117                                                   {0,2,3,1},
00118                                                   {1,3,2,0},
00119                                                   {1,0,3,2},
00120                                                   {2,1,3,0},
00121 
00122                                                   {1,2,0,3},
00123                                                   {2,3,0,1},
00124                                                   {3,1,0,2},
00125                                                   {2,0,1,3},
00126                                                   {3,2,1,0},
00127                                                   {3,0,2,1},
00128                                                 };
00129                 assert ((indexE<12)&&(indexV<4));
00130                 return mapvertedgerot[indexE][indexV];
00131         }       
00132 
00135   static int _GetMapFaceEdgeRot(const int &indexE,const int &indexF)
00136         {       
00137                 static int mapfaceedgerot[12][4]={
00138                                                   {1,2,0,3},
00139                                                   {0,1,2,3},
00140                                                   {2,0,1,3},
00141                                                   {3,1,0,2},
00142                                                   {1,0,3,2},
00143                                                   {3,0,2,1},
00144 
00145                                                   {0,3,1,2},
00146                                                   {2,3,0,1},
00147                                                   {1,3,2,0},
00148                                                   {0,2,3,1},
00149                                                   {3,2,1,0},
00150                                                   {2,1,3,0},
00151                                                 };
00152                 assert ((indexE<12)&&(indexF<4));
00153                 return mapfaceedgerot[indexE][indexF];
00154         }       
00155 
00158  static int _GetDirRot(int indexE,int indexF)
00159         {       
00160     static int mapfaceedgerot[12][4]={
00161                                                   {2,0,-1,-1},
00162                                                   {0,-1,2,-1},
00163                                                   {-1,2,0,-1},
00164                                                   {2,-1,-1,0},
00165                                                   {-1,0,-1,2},
00166                                                   {-1,-1,2,0},
00167                
00168               {0,2,-1,-1},
00169                                                   {2,-1,0,-1},
00170                                                   {-1,0,2,-1},
00171                                                   {0,-1,-1,2},
00172                                                   {-1,2,-1,0},
00173                                                   {-1,-1,0,2},
00174                                                 };
00175 
00176                 assert ((indexE<12)&&(indexF<4));
00177                 return mapfaceedgerot[indexE][indexF];
00178         }       
00179 
00181 PosType _FindPos(TetraType *t,int edge)
00182 {       
00183         int face0=Tetra::FofE(edge,0);
00184         int ve0=Tetra::VofE(edge,0);
00185         PosType pos(t,face0,edge,ve0);
00186         return pos;
00187 }
00188 
00190 void _AssertOrder(TetraType *t,VertexType *v0,VertexType *v1,VertexType *v2,VertexType *v3)
00191 {
00192   assert(t->V(0)==v0);
00193         assert(t->V(1)==v1);
00194         assert(t->V(2)==v2);
00195         assert(t->V(3)==v3);
00196 }
00197 
00199 void _ConnectTTTopology(TetraType *t0,int i0,TetraType *t1,int i1) 
00200 {
00201   assert((i0>=0)&&(i0<4));
00202   assert((i1>=0)&&(i1<4));
00203   assert((!t0->IsD())&&(!t1->IsD()));
00204   t0->TTp(i0)=t1;
00205   t0->TTi(i0)=i1;
00206   t1->TTp(i1)=t0;
00207   t1->TTi(i1)=i0;
00208   assert( (((t0->TTp(i0))->TTp(t0->TTi(i0)))==t0));
00209   assert( (((t1->TTp(i1))->TTp(t1->TTi(i1)))==t1));
00210 }
00211 
00213 void _Divide(PosType pos,VertexType *vnew,TetraType *newtp0,TetraType *newtp1,bool invert)
00214 {
00215       int curredge=pos.E();
00216      
00217                         //control if the edge vertices arein the right order for the table
00218                         if (invert)
00219                         curredge+=6;
00220 
00221                         //find the new position to vertex according
00222                         int ie0=_GetMapVertEdgeRot(curredge,0);
00223                         int ie1=_GetMapVertEdgeRot(curredge,2);
00224                         int in0=_GetMapVertEdgeRot(curredge,1);
00225                         int in1=_GetMapVertEdgeRot(curredge,3);
00226                 
00227                         //as first the ones that appartain to the selected curredge
00228                         VertexType *ve0=pos.T()->V(ie0);
00229                         VertexType *ve1=pos.T()->V(ie1);
00230 
00231                         //and after the others that will be in the cutting plane
00232                         VertexType *vn0=pos.T()->V(in0);
00233                         VertexType *vn1=pos.T()->V(in1);
00234                 
00235                         newtp0->V(0)=ve0;
00236       newtp0->V(1)=vn0;
00237       newtp0->V(2)=vnew;
00238       newtp0->V(3)=vn1;
00239 
00240       newtp1->V(0)=vnew;
00241       newtp1->V(1)=vn0;
00242       newtp1->V(2)=ve1;
00243       newtp1->V(3)=vn1;
00244      
00245                   //right order of the vertices
00246 #ifdef _DEBUG
00247       _AssertOrder(newtp0,ve0,vn0,vnew,vn1);
00248                         _AssertOrder(newtp1,vnew,vn0,ve1,vn1);
00249                         //end asserts
00250 #endif
00251 }
00252 
00253 bool _InvertRotation(PosType pos)
00254 {
00255   return (pos.V()!=Tetra::VofE(pos.E(),0));
00256 }
00257 
00259 void _SubstituteVTTopology(TetraType *told,TetraType *newtp0,TetraType *newtp1)
00260 {
00261   _SetDefultVTTopology(newtp0);
00262         _SetDefultVTTopology(newtp1);
00263                         
00264   //detach the old tetrahedron from VTtopology
00265   _Topo.DetachVTTopology(told);
00266         //tetrahedron 0
00267         _Topo.InsertVTTopology(newtp0);
00268         //tetrahedron 1
00269         _Topo.InsertVTTopology(newtp1);         
00270 }
00271 
00273 void _ControlConnection(TetraType *oldtp0,TetraType *newtp0)
00274 {
00275   VertexType *v00=oldtp0->V(0);
00276   VertexType *v01=oldtp0->V(1);
00277   VertexType *v02=oldtp0->V(2);
00278   VertexType *v03=oldtp0->V(3);
00279 
00280   VertexType *v10=newtp0->V(0);
00281   VertexType *v11=newtp0->V(1);
00282   VertexType *v12=newtp0->V(2);
00283   VertexType *v13=newtp0->V(3);
00284   
00285   assert(((v00==v10)&&(v02==v12))||((v00==v12)&&(v02==v10)));
00286   assert(((v01==v13)&&(v03!=v11))||((v01!=v13)&&(v03==v11)));
00287 }
00288 
00290 void _SetDefaultTTExtern(TetraType *t)
00291 {
00292   for (int y=0;y<4;y++)
00293                         {
00294                                 t->TTp(y)=t;
00295                                 t->TTi(y)=y;
00296       }
00297 }
00298 
00301 
00302 void _SubstituteTTTopology(TetraType *old_t,TetraType *new_t,int edgerot,int face)
00303 {
00304    int indexface=_GetMapFaceEdgeRot(edgerot,face);
00305 
00306                         if (old_t->IsBorderF(indexface))
00307                         {
00308                 new_t->TTp(face)=new_t;
00309                                 new_t->TTi(face)=face;
00310       }
00311       else
00312       {
00313           TetraType *tetrad=old_t->TTp(indexface);
00314                             int fad=old_t->TTi(indexface);
00315           _ConnectTTTopology(new_t,face,tetrad,fad);
00316           assert (!tetrad->IsD());
00317       }
00318 }
00319 
00322 
00323 void _AddNewTetrahedrons(TetraMeshType &tm,PosType pos,VertexType *vnew)
00324 {
00325 
00326         TetraType *oldtp0=NULL;
00327         TetraType *oldtp1=NULL;
00328 
00329         TetraType *newtp0;
00330   TetraType *newtp1;
00331 
00332   TetraType *firsttp0=NULL;
00333   TetraType *firsttp1=NULL;
00334 
00335 
00336   int curredge;
00337   int direction=-1;
00338   bool invert=false;
00339 
00340 TetraAllocator All=TetraAllocator();
00341 pos.Reset();
00342 _nT=0;
00343 
00344 while (!pos.LoopEnd())
00345   {     
00346                         assert(!pos.T()->IsD());
00347       
00348       invert=_InvertRotation(pos);
00349 
00350                         //CREATE THE NEW TETRAHEDRONS
00351 
00352                         //create the new ones putting the veritices in the right order
00353       TetraIterator ti=All.AddTetra(tm,2);              
00354       newtp0 = &(*ti);
00355                         ti++;
00356       newtp1 = &(*ti);  
00357       
00358 
00359       _Divide(pos,vnew,newtp0,newtp1,invert);
00360 
00361 #ifdef _DEBUG
00362       if ((oldtp0!=NULL)&&(!pos.Jump()))
00363       _ControlConnection(oldtp0,newtp0);
00364       if ((oldtp1!=NULL)&&(!pos.Jump()))
00365       _ControlConnection(oldtp1,newtp1);
00366 #endif
00367       
00368       // SUBSTITUTE NEW TETRAHEDRONS ON VT TOPOLOGY
00369       if (tm.HasVTTopology())
00370       _SubstituteVTTopology(pos.T(),newtp0,newtp1);
00371                         
00372 
00373                         //THEN SET THE T-T TOPOLOGY
00374 
00375       _SetDefaultTTExtern(newtp0);
00376       _SetDefaultTTExtern(newtp1);
00377                         
00378       curredge=pos.E();
00379       if (invert)
00380                           curredge+=6;
00381 
00382       //face3 
00383       _SubstituteTTTopology(pos.T(),newtp1,curredge,3);
00384                 
00385                         //face1 
00386       _SubstituteTTTopology(pos.T(),newtp0,curredge,1);
00387       
00388                         //now I set t-t topology between themselfes
00389 
00390                         _ConnectTTTopology(newtp0,3,newtp1,1);
00391 
00392       if (pos.Jump())
00393       {
00394         vnew->SetB();
00395         oldtp0=NULL;
00396         oldtp1=NULL;
00397       }
00398       
00399       direction=_GetDirRot(curredge,pos.F());
00400       assert(direction!=-1);
00401        //control the direction of moving
00402       if ((oldtp0!=NULL)&&(oldtp1!=NULL))
00403       {
00404         //direction=_GetDirRot(oldtp0,newtp0);
00405 
00406         //find direction of moving
00407         if (direction==0)
00408                         {
00409          _ConnectTTTopology(oldtp0,0,newtp0,2);
00410          _ConnectTTTopology(oldtp1,0,newtp1,2);
00411                         }
00412                           else 
00413         if (direction==2)
00414                           {
00415           _ConnectTTTopology(oldtp0,2,newtp0,0);
00416           _ConnectTTTopology(oldtp1,2,newtp1,0);
00417                           }
00418       }
00419       //assign if it is the first one
00420       if (firsttp0==NULL)
00421         firsttp0=newtp0;
00422       if (firsttp1==NULL)
00423         firsttp1=newtp1;
00424 
00425       oldtp0=newtp0;
00426       oldtp1=newtp1;
00427 
00428       _toDel[_nT]=pos.T();
00429       _nT++;
00430       pos.NextT();
00431       }
00432   
00433   //at the end I finish the connections
00434   if (!(pos.Jump())&&(direction==0)&&(firsttp0!=NULL)&&(firsttp1!=NULL)&&(oldtp0!=NULL)&&(oldtp1!=NULL))
00435    {
00436      _ConnectTTTopology(oldtp0,0,firsttp0,2);
00437      _ConnectTTTopology(oldtp1,0,firsttp1,2);
00438    }
00439   else if (!(pos.Jump())&&(direction==2)&&(firsttp0!=NULL)&&(firsttp1!=NULL)&&(oldtp0!=NULL)&&(oldtp1!=NULL))
00440    {
00441       _ConnectTTTopology(oldtp0,2,firsttp0,0);
00442       _ConnectTTTopology(oldtp1,2,firsttp1,0);
00443    }
00444   else if (pos.Jump())
00445     vnew->SetB();
00446 
00447 }
00448 
00450 void _DeleteOldTetra()
00451 {
00452   for (int i=0;i<_nT;i++)
00453   _toDel[i]->SetD();
00454 }
00455 
00456 //=========================================================================
00457 
00458 public:
00459 
00462 VertexType* DoSplit(TetraMeshType &tm,TetraType *t,int edge,double alfa)
00463 {
00464         assert(!t->IsD());
00465   assert(tm.HasTTTopology());
00466         assert((alfa>0)&&(alfa<1));
00467         assert((edge>=0)&&(edge<6));
00468         VertexType *vnew=_AddVertexEdge(tm,*t,edge,alfa);
00469         _AddNewTetrahedrons(tm,_FindPos(t,edge),vnew);
00470   _DeleteOldTetra();
00471         return(vnew);
00472 }
00473 
00474 };//end class
00475 
00476 }//end namespace tetra
00477 }//end namespace vcg
00478 #endif