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 #ifndef __VCG_TETRA_UPDATE_TOPOLOGY
00040 #define __VCG_TETRA_UPDATE_TOPOLOGY
00041 #include <algorithm>
00042 #include <vector>
00043 #include <map>
00044 #include <vcg\simplex\tetrahedron\pos.h>
00045 using namespace std;
00046 namespace vcg {
00047 namespace tetra {
00054 template < class VERT_TYPE , class TETRA_TYPE>
00055 class Facet{
00056
00057 public:
00058
00060 typedef VERT_TYPE MVTYPE;
00061 typedef TETRA_TYPE MTTYPE;
00062
00063
00064 private:
00065 MTTYPE *Tr;
00066 int numface;
00067 MVTYPE * vertex[3];
00068
00069 public:
00070
00071 Facet(MVTYPE *v0,MVTYPE *v1,MVTYPE *v2,TETRA_TYPE * t,int index)
00072 {
00073 vertex[0]=v0;
00074 vertex[1]=v1;
00075 vertex[2]=v2;
00076 if(vertex[0] > vertex[1]) std::swap(vertex[0], vertex[1]);
00077 if(vertex[1] > vertex[2])
00078 {
00079 std::swap(vertex[1], vertex[2]);
00080 if(vertex[0] > vertex[1])
00081 {
00082 std::swap(vertex[0], vertex[1]);
00083 }
00084 }
00085 Tr = t;
00086 numface = index;
00087 }
00088
00089 inline const MVTYPE * V(int index) const
00090 {
00091 return vertex[index];
00092 }
00093
00094 TETRA_TYPE *getTetrahedron()
00095 {
00096 return Tr;
00097 }
00098
00099 void setTetrahedron(TETRA_TYPE * t)
00100 {
00101 Tr=t;
00102 }
00103
00104 inline bool operator == ( Facet const & f) const
00105 {
00106 return ((vertex[0]==f.V(0))&&(vertex[1]==f.V(1))&&(vertex[2]==f.V(2)));
00107 }
00108
00109 inline bool operator != ( Facet const & f) const
00110 {
00111 return !((*this) == f);
00112 }
00113
00114 inline bool operator > ( Facet const & f) const
00115 {
00116
00117 if (vertex[0]!=f.V(0))
00118 {
00119 if (vertex[0]>f.V(0))
00120 return true;
00121 else
00122 return false;
00123 }
00124 else
00125 if (vertex[1]!=f.V(1))
00126 {
00127 if (vertex[1]>f.V(1))
00128 return true;
00129 else
00130 return false;
00131 }
00132 else
00133 if (vertex[2]!=f.V(2))
00134 {
00135 if (vertex[2]>f.V(2))
00136 return true;
00137 else
00138 return false;
00139 }else
00140 return false;
00141
00142 }
00143
00144 inline bool operator < ( Facet const & f) const
00145 {
00146 return (!((*this)>f)&&((*this)!=f));
00147 }
00148
00149 inline bool operator <= ( Facet const & f) const
00150 {
00151 return (((*this)<f)||((*this)==f));
00152 }
00153
00154 inline bool operator >= ( Facet const & f) const
00155 {
00156 return (((*this)>f)||((*this)==f));
00157 }
00158
00159 int getFaceIndex()const
00160 {
00161 return numface;
00162 }
00163
00164 };
00167
00173 template < class STL_VERT_CONT ,class STL_TETRA_CONT >
00174 class UpdateTopologyBase
00175 {
00176
00177 public:
00178
00180 typedef STL_VERT_CONT VertexContainer;
00181
00183 typedef STL_TETRA_CONT TetraContainer;
00184
00186 typedef typename STL_VERT_CONT::value_type VertexType;
00187
00189 typedef typename STL_TETRA_CONT::value_type TetraType;
00190
00192 typedef typename STL_VERT_CONT::iterator VertexIterator;
00193
00195 typedef typename STL_TETRA_CONT::iterator TetraIterator;
00196
00198 typedef typename STL_VERT_CONT::const_iterator const_VertexIterator;
00199
00201 typedef typename STL_TETRA_CONT::const_iterator const_TetraIterator;
00202
00203 public:
00204
00205
00209
00210
00212 static void VTTopology( VertexContainer & vert, TetraContainer & tetra )
00213 {
00214 ClearVTTopology( vert, tetra );
00215 for( TetraIterator t = tetra.begin(); t != tetra.end(); ++t )
00216 if( !(*t).IsD() )
00217 for( int j = 0; j < 4; ++j )
00218 {
00219 (*t).VTp(j) = (*t).V(j)->VTp();
00220 (*t).VTi(j) = (*t).V(j)->VTi();
00221 (*t).V(j)->VTp() = &(*t);
00222 (*t).V(j)->VTi() = j;
00223 }
00224 }
00225
00226
00228 static void ClearVTTopology( VertexContainer & vert, TetraContainer & tetra )
00229 {
00230 for( VertexIterator v = vert.begin(); v != vert.end(); ++v ) { v->VTp() = 0; v->VTi() = 0; }
00231 for( TetraIterator t = tetra.begin(); t != tetra.end(); ++t )
00232 if( ! (*t).IsD() )
00233 for( int j = 0; j < 4; ++j ) { (*t).VTp(j) = 0; (*t).VTi(j) = 0; }
00234 }
00235
00236
00238 static void DetachVTTopology( TetraType *t )
00239 {
00240 if( ! (*t).IsD() )
00241 for( int i = 0; i < 4; i++ ) DetachVTTopology( t->V(i), t );
00242 }
00243
00244
00246 static void DetachVTTopology( VertexType *v, TetraType *t )
00247 {
00248 TetraType *lastt;
00249 int lastz;
00250 VTIterator<TetraType> Et( v->VTb(), v->VTi() );
00251 if( Et.Vt() == t )
00252 {
00253 v->VTb() = (TetraType *) t->VTp( v->VTi() );
00254 v->VTi() = t->VTi( v->VTi() );
00255 }
00256 else
00257 {
00258 lastz = Et.Vi();
00259 while( ( Et.Vt() != t ) && ( !Et.End() ) )
00260 {
00261 lastz = Et.Vi();
00262 lastt = Et.Vt();
00263 ++Et;
00264 }
00266 assert( Et.Vt() != NULL );
00267 lastt->VTp(lastz) = Et.Vt()->VTp( Et.Vi() );
00268 lastt->VTi(lastz) = Et.Vt()->VTi( Et.Vi() );
00269 }
00270 }
00271
00272
00274 static void InsertVTTopology( VertexType *v, int z, TetraType *t )
00275 {
00276 if( ! (*t).IsD() )
00277 {
00278 t->VTp(z) = v->VTb();
00279 t->VTi(z) = v->VTi();
00280 v->VTb() = &(*t);
00281 v->VTi() = z;
00282 }
00283 }
00284
00285
00287 static void InsertVTTopology( TetraType *t )
00288 {
00289 assert( !( t->IsD() ) );
00290 for( int k = 0; k < 4; k++ )
00291 {
00292 assert( !( t->V(k)->IsD() ) );
00293 InsertVTTopology( t->V(k), k, t );
00294 }
00295 }
00296
00297
00299 static void TestVTTopology( VertexContainer & vert, TetraContainer & tetra )
00300 {
00301 int i;
00302 for( VertexIterator vi = vert.begin(); vi != vert.end(); vi++ )
00303 if( !(*vi).IsD() )
00304 {
00305 TetraType *nextT = vi->VTb();
00306 int nextI = vi->VTi();
00307 int oldI;
00308 while( nextT != NULL )
00309 {
00310 assert( ( nextT->V(nextI) == &(*vi) ) );
00311 oldI = nextI;
00312 nextI = nextT->VTi(nextI);
00313 nextT = nextT->VTp(oldI);
00314 }
00315 }
00316 }
00317
00318
00320
00324
00325 static void TTTopology(const VertexContainer &vert,TetraContainer &tetra)
00326 {
00327 vector <Facet<VertexType,TetraType> > VF;
00328 VertexType* v0;
00329 VertexType* v1;
00330 VertexType* v2;
00331
00332 for (TetraIterator ti=tetra.begin();ti!=tetra.end();ti++)
00333 if (!(*ti).IsD())
00334 {
00335 (*ti).TTi(0)=0;
00336 (*ti).TTi(1)=1;
00337 (*ti).TTi(2)=2;
00338 (*ti).TTi(3)=3;
00339 (*ti).TTp(0)=(&(*ti));
00340 (*ti).TTp(1)=(&(*ti));
00341 (*ti).TTp(2)=(&(*ti));
00342 (*ti).TTp(3)=(&(*ti));
00343
00344 v0=(*ti).V(Tetra::VofF(0,0));
00345 v1=(*ti).V(Tetra::VofF(0,1));
00346 v2=(*ti).V(Tetra::VofF(0,2));
00347
00348 VF.push_back(Facet<VertexType,TetraType>(v0,v1,v2,&(*ti),0));
00349
00350 v0=(*ti).V(Tetra::VofF(1,0));
00351 v1=(*ti).V(Tetra::VofF(1,1));
00352 v2=(*ti).V(Tetra::VofF(1,2));
00353
00354 VF.push_back(Facet<VertexType,TetraType>(v0,v1,v2,&(*ti),1));
00355
00356 v0=(*ti).V(Tetra::VofF(2,0));
00357 v1=(*ti).V(Tetra::VofF(2,1));
00358 v2=(*ti).V(Tetra::VofF(2,2));
00359
00360 VF.push_back(Facet<VertexType,TetraType>(v0,v1,v2,&(*ti),2));
00361
00362 v0=(*ti).V(Tetra::VofF(3,0));
00363 v1=(*ti).V(Tetra::VofF(3,1));
00364 v2=(*ti).V(Tetra::VofF(3,2));
00365
00366 VF.push_back(Facet<VertexType,TetraType>(v0,v1,v2,&(*ti),3));
00367 }
00368 sort(VF.begin(),VF.end());
00369
00370 TetraType *t0;
00371 TetraType *t1;
00372 int faceindex0;
00373 int faceindex1;
00374 int j;
00375 unsigned int i;
00376 for (i=0;i<VF.size()-1;i++)
00377 {
00378 j=i+1;
00379 if (VF[i]==VF[j])
00380 {
00381 t0=VF[i].getTetrahedron();
00382 t1=VF[j].getTetrahedron();
00383 faceindex0=VF[i].getFaceIndex();
00384 faceindex1=VF[j].getFaceIndex();
00385 t0->TTp(faceindex0)=(t1);
00386 t1->TTp(faceindex1)=(t0);
00387 t0->TTi(faceindex0)=(faceindex1);
00388 t1->TTi(faceindex1)=(faceindex0);
00389 i++;
00390 }
00391
00392 }
00393 }
00394
00395
00396
00398 static void _AttachTTTopology(TetraType *t0,int i0,TetraType *t1,int i1)
00399 {
00400 assert((i0>=0)&&(i0<4));
00401 assert((i1>=0)&&(i1<4));
00402 assert((!t0->IsD())&&(!t1->IsD()));
00403 t0->TTp(i0)=t1;
00404 t0->TTi(i0)=i1;
00405 t1->TTp(i1)=t0;
00406 t1->TTi(i1)=i0;
00407 assert( (((t0->TTp(i0))->TTp(t0->TTi(i0)))==t0));
00408 assert( (((t1->TTp(i1))->TTp(t1->TTi(i1)))==t1));
00409 }
00410
00412 static void DetachTTTopology(TetraType *t)
00413 {
00414 assert(!t->IsD());
00415 int i;
00416 for(i=0; i < 4; ++i)
00417 t->TTp(i)->TTp(t->TTi(i)) = t->TTp(i);
00418 }
00419
00420
00422 static void TestTTTopology(VertexContainer &vert,TetraContainer &tetra)
00423 {
00424 int i;
00425 for (TetraIterator ti=tetra.begin();ti!=tetra.end();ti++)
00426 if ((!(*ti).IsD()))
00427 for (i=0;i<4;i++)
00428 {
00429 {
00430 assert( ((((*ti).TTp(i))->TTp((*ti).TTi(i)))==&(*ti)));
00431
00432 VertexType *v0=(*ti).V(Tetra::VofF(i,0));
00433 VertexType *v1=(*ti).V(Tetra::VofF(i,1));
00434 VertexType *v2=(*ti).V(Tetra::VofF(i,2));
00435
00436 TetraType *t1=(TetraType*)(*ti).TTp(i);
00437 assert (!t1->IsD());
00438 int z1=(*ti).TTi(i);
00439
00440 VertexType *vo0=(*t1).V(Tetra::VofF(z1,0));
00441 VertexType *vo1=(*t1).V(Tetra::VofF(z1,1));
00442 VertexType *vo2=(*t1).V(Tetra::VofF(z1,2));
00443
00444 assert((v0!=v1)&&(v0!=v2)&&(v1!=v2));
00445 assert((vo0!=vo1)&&(vo0!=vo2)&&(vo1!=vo2));
00446
00447 assert ((v0==vo0)||(v0==vo1)||(v0==vo2));
00448 assert ((v1==vo0)||(v1==vo1)||(v1==vo2));
00449 assert ((v2==vo0)||(v2==vo1)||(v2==vo2));
00450 }
00451 }
00452 }
00453
00455 static void TestExternalVertex(VertexContainer &vert,TetraContainer &tetra)
00456 {
00457 TetraIterator ti;
00458 VertexIterator vi;
00459
00460 typedef pair <VertexType*, bool> VertBoolPair;
00461 map<VertexType*, bool> Inserted;
00462 typename map<VertexType*, bool>::iterator MapIte;
00463
00464 for (ti=tetra.begin();ti<tetra.end();ti++)
00465 {
00466 int i;
00467 if (!ti->IsD())
00468 {
00469 for (i=0;i<4;i++)
00470 if (ti->IsBorderF(i))
00471 {
00472 VertexType *v0=ti->V(Tetra::VofF(i,0));
00473 VertexType *v1=ti->V(Tetra::VofF(i,1));
00474 VertexType *v2=ti->V(Tetra::VofF(i,2));
00475
00476 MapIte = Inserted.find(v0);
00477 if ( MapIte == Inserted.end( ) )
00478 Inserted.insert (VertBoolPair(v0,true));
00479
00480 MapIte = Inserted.find(v1);
00481 if ( MapIte == Inserted.end( ) )
00482 Inserted.insert (VertBoolPair(v1,true));
00483
00484 MapIte = Inserted.find(v2);
00485 if ( MapIte == Inserted.end( ) )
00486 Inserted.insert (VertBoolPair(v2,true));
00487
00488 assert(!((v0->IsD())||(v1->IsD())||(v2->IsD())));
00489 assert ((v0->IsB())&&(v1->IsB())&&(v2->IsB()));
00490 }
00491 }
00492 }
00493
00494 for (vi=vert.begin();vi<vert.end();vi++)
00495 {
00496 if (!vi->IsD())
00497 {
00498 if (vi->IsB())
00499 {
00500 MapIte = Inserted.find(&(*vi));
00501
00502 assert ( MapIte != Inserted.end( ) );
00503 }
00504 }
00505 }
00506 }
00507
00509 static void setExternalVertices(VertexContainer &vert,TetraContainer &tetra)
00510 {
00511
00512 TetraIterator tt;
00513 VertexIterator vi;
00514 int i;
00515 for (vi=vert.begin();vi<vert.end();++vi)
00516 vi->ClearB();
00517 for (tt=tetra.begin();tt<tetra.end();++tt)
00518 if(!(*tt).IsD())
00519 {
00520 for(i=0;i<4;i++)
00521 {
00522 if ((*tt).IsBorderF(i))
00523 {
00524 (*tt).V(Tetra::VofF(i,0))->SetB();
00525 (*tt).V(Tetra::VofF(i,1))->SetB();
00526 (*tt).V(Tetra::VofF(i,2))->SetB();
00527 }
00528
00529 }
00530
00531 }
00532 }
00533
00534
00537 private:
00538
00539 struct _triV
00540 {
00541 VertexType *v[3];
00542
00543 _triV(VertexType *v0,VertexType *v1,VertexType *v2)
00544 {
00545 v[0]=v0;
00546 v[1]=v1;
00547 v[2]=v2;
00548 sort(v,v+3);
00549 }
00550
00551 inline const VertexType * V(int index) const
00552 {
00553 return v[index];
00554 }
00555
00556 inline bool operator == ( _triV const & tv) const
00557 {
00558 return ((v[0]==tv.V(0))&&(v[1]==tv.V(1))&&(v[2]==tv.V(2)));
00559 }
00560
00561 inline bool operator != ( _triV const & tv) const
00562 {
00563 return !((*this) == tv);
00564 }
00565
00566 inline bool operator > ( _triV const & tv ) const
00567 {
00568
00569 if (v[0]!=tv.V(0))
00570 {
00571 if (v[0]>tv.V(0))
00572 return true;
00573 else
00574 return false;
00575 }
00576 else
00577 if (v[1]!=tv.V(1))
00578 {
00579 if (v[1]>tv.V(1))
00580 return true;
00581 else
00582 return false;
00583 }
00584 else
00585 if (v[2]!=tv.V(2))
00586 {
00587 if (v[2]>tv.V(2))
00588 return true;
00589 else
00590 return false;
00591 }else
00592 return false;
00593
00594 }
00595
00596 inline bool operator < (_triV const & tv) const
00597 {
00598 return !(((*this)>tv)&&((*this)!=tv));
00599 }
00600
00601 inline bool operator <= (_triV const & tv) const
00602 {
00603 return (((*this)<tv)||((*this)==tv));
00604 }
00605
00606 inline bool operator >= ( _triV const & tv) const
00607 {
00608 return (((*this)>tv)||((*this)==tv));
00609 }
00610 };
00611
00612
00613 public:
00615 static bool IsExternEdge(TetraType *t,int edge)
00616 {
00617 std::vector < _triV > Faces;
00618
00619 assert((t->HasTTAdjacency())||(t->HasVTAdjacency()));
00620 if ((!t->V(Tetra::VofE(edge,0))->IsB())||(!t->V(Tetra::VofE(edge,1))->IsB()))
00621 return (false);
00622
00623 if (t->HasTTAdjacency())
00624 {
00625 PosLoop<TetraType> pl(t,Tetra::FofE(edge,0),edge,Tetra::VofE(edge,0));
00626 pl.Reset();
00627
00628 while ((!pl.LoopEnd())&&(!pl.T()->IsBorderF(Tetra::FofE(pl.E(),0)))&&(!pl.T()->IsBorderF(Tetra::FofE(pl.E(),1))))
00629 pl.NextT();
00630 if (pl.LoopEnd())
00631 return false;
00632 else
00633 return true;
00634 }
00635 else
00636 {
00637 VertexType *v0=t->V(Tetra::VofE(edge,0));
00638 VertexType *v1=t->V(Tetra::VofE(edge,1));
00639 assert(v0!=v1);
00640 VTIterator<TetraType> Vti(v0->VTb(),v0->VTi());
00641 int num=0;
00642 Faces.clear();
00643 Faces.reserve(40);
00644 while (!Vti.End())
00645 {
00646
00647 int f0=Tetra::FofV(Vti.Vi(),0);
00648 int f1=Tetra::FofV(Vti.Vi(),1);
00649 int f2=Tetra::FofV(Vti.Vi(),2);
00650 VertexType *vf0=Vti.Vt()->V(Tetra::VofF(f0,0));
00651 VertexType *vf1=Vti.Vt()->V(Tetra::VofF(f0,1));
00652 VertexType *vf2=Vti.Vt()->V(Tetra::VofF(f0,2));
00653
00654 if ((vf0==v1)||(vf1==v1)||(vf2==v1))
00655 {
00656 Faces.push_back(_triV(vf0,vf1,vf2));
00657 num++;
00658 }
00659 }
00660 sort(Faces.begin(),Faces.end());
00661
00662
00663 bool isExtern=false;
00664 typename std::vector < _triV >::iterator TVIo;
00665 typename std::vector < _triV >::iterator TVIn;
00666 TVIo=Faces.begin();
00667 TVIn=Faces.begin();
00668 TVIn++;
00669 int j=0;
00670 while (((*TVIo)==(*TVIn))&&(j<num))
00671 {
00672
00673 TVIo++;
00674 TVIo++;
00675 TVIn++;
00676 TVIn++;
00677 j++;
00678 j++;
00679 }
00680 if (j>=num)
00681 return false;
00682 else
00683 return true;
00684 }
00685
00686 }
00687 };
00688
00689 template <class TetraMeshType>
00690 class UpdateTopology: public UpdateTopologyBase<typename TetraMeshType::VertexContainer,
00691 typename TetraMeshType::TetraContainer>{
00692 public:
00693 static void TTTopology(TetraMeshType & tmesh){
00694 UpdateTopologyBase<typename TetraMeshType::VertexContainer,typename TetraMeshType::TetraContainer>::
00695 TTTopology(tmesh.vert,tmesh.tetra);
00696 }
00697 static void VTTopology(TetraMeshType & tmesh){
00698 UpdateTopologyBase<typename TetraMeshType::VertexContainer,typename TetraMeshType::TetraContainer>::
00699 VTTopology(tmesh.vert,tmesh.tetra);
00700 }
00701
00702
00703 };
00704
00706 }
00707 }
00708
00709
00710 #endif
