24 #ifndef __VCG_TRI_UPDATE_TOPOLOGY
25 #define __VCG_TRI_UPDATE_TOPOLOGY
35 template <
class UpdateMeshType>
40 typedef UpdateMeshType MeshType;
41 typedef typename MeshType::ScalarType ScalarType;
42 typedef typename MeshType::VertexType VertexType;
43 typedef typename MeshType::VertexPointer VertexPointer;
44 typedef typename MeshType::VertexIterator VertexIterator;
45 typedef typename MeshType::EdgeType EdgeType;
46 typedef typename MeshType::EdgePointer EdgePointer;
47 typedef typename MeshType::EdgeIterator EdgeIterator;
48 typedef typename MeshType::FaceType FaceType;
49 typedef typename MeshType::FacePointer FacePointer;
50 typedef typename MeshType::FaceIterator FaceIterator;
51 typedef typename MeshType::TetraType TetraType;
52 typedef typename MeshType::TetraPointer TetraPointer;
53 typedef typename MeshType::TetraIterator TetraIterator;
72 PFace (TetraPointer tp,
const int nz) { this->Set(tp, nz); }
74 void Set (TetraPointer tp ,
const int nz )
77 assert (nz >= 0 && nz < 4);
79 v[0] = tp->cV(Tetra::VofF(nz, 0));
80 v[1] = tp->cV(Tetra::VofF(nz, 1));
81 v[2] = tp->cV(Tetra::VofF(nz, 2));
83 assert(v[0] != v[1] && v[1] != v[2]);
86 std::swap(v[0], v[1]);
88 std::swap(v[1], v[2]);
90 std::swap(v[0], v[1]);
98 inline bool operator < (
const PFace & pf)
const
104 if (v[0] > pf.v[0])
return false;
110 if (v[1] > pf.v[1])
return false;
112 return (v[2] < pf.v[2]);
117 inline bool operator == (
const PFace & pf)
const
119 return v[0] == pf.v[0] && v[1] == pf.v[1] && v[2] == pf.v[2];
123 static void FillFaceVector (MeshType & m, std::vector<PFace> & fvec)
125 ForEachTetra(m, [&fvec] (TetraType & t) {
126 for (
int i = 0; i < 4; ++i)
127 fvec.push_back(
PFace(&t, i));
131 static void FillUniqueFaceVector (MeshType & m, std::vector<PFace> & fvec)
133 FillFaceVector(m, fvec);
134 std::sort(fvec.begin(), fvec.end());
135 typename std::vector<PFace>::iterator newEnd = std::unique(fvec.begin(), fvec.end());
152 PEdge(FacePointer pf,
const int nz) { this->Set(pf,nz); }
153 void Set( FacePointer pf,
const int nz )
160 v[1] = pf->V(pf->Next(nz));
161 assert(v[0] != v[1]);
163 if( v[0] > v[1] ) std::swap(v[0],v[1]);
168 inline bool operator < (
const PEdge & pe )
const
170 if( v[0]<pe.v[0] )
return true;
171 else if( v[0]>pe.v[0] )
return false;
172 else return v[1] < pe.v[1];
175 inline bool operator == (
const PEdge & pe )
const
177 return v[0]==pe.v[0] && v[1]==pe.v[1];
183 Point3<ScalarType> interp(0,0,0);
184 interp[ this->z ] = u;
185 interp[(this->z+1)%3] = 1.0f-u;
194 static void FillEdgeVector(MeshType &m, std::vector<PEdge> &edgeVec,
bool includeFauxEdge=
true)
196 edgeVec.reserve(m.fn*3);
197 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
199 for(
int j=0;j<(*fi).VN();++j)
200 if(includeFauxEdge || !(*fi).IsF(j))
201 edgeVec.push_back(
PEdge(&*fi,j));
204 static void FillUniqueEdgeVector(MeshType &m, std::vector<PEdge> &edgeVec,
bool includeFauxEdge=
true,
bool computeBorderFlag=
false)
207 sort(edgeVec.begin(), edgeVec.end());
209 if (computeBorderFlag) {
210 for (
size_t i=0; i<edgeVec.size(); i++)
211 edgeVec[ i ].isBorder =
true;
212 for (
size_t i=1; i<edgeVec.size(); i++) {
213 if (edgeVec[i]==edgeVec[i-1])
214 edgeVec[i-1].isBorder = edgeVec[i-1].isBorder =
false;
218 typename std::vector< PEdge>::iterator newEnd = std::unique(edgeVec.begin(), edgeVec.end());
220 edgeVec.resize(newEnd-edgeVec.begin());
223 static void FillSelectedFaceEdgeVector(MeshType &m, std::vector<PEdge> &edgeVec)
225 edgeVec.reserve(m.fn*3);
226 ForEachFace(m, [&](FaceType &f){
227 for(
int j=0;j<f.VN();++j)
229 edgeVec.push_back(PEdge(&f,j));
232 sort(edgeVec.begin(), edgeVec.end());
233 edgeVec.erase(std::unique(edgeVec.begin(), edgeVec.end()),edgeVec.end());
246 for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
251 std::vector<PEdge> Edges;
252 FillUniqueEdgeVector(m,Edges,
true,tri::HasPerEdgeFlags(m) );
253 assert(m.edge.empty());
255 assert(m.edge.size()==Edges.size());
258 if(tri::HasEVAdjacency(m))
260 for(
size_t i=0; i< Edges.size(); ++i)
262 m.edge[i].V(0) = Edges[i].v[0];
263 m.edge[i].V(1) = Edges[i].v[1];
267 if (tri::HasPerEdgeFlags(m)){
268 for(
size_t i=0; i< Edges.size(); ++i) {
269 if (Edges[i].isBorder) m.edge[i].SetB();
else m.edge[i].ClearB();
273 if(tri::HasEFAdjacency(m))
275 for(
size_t i=0; i< Edges.size(); ++i)
277 std::vector<FacePointer> fpVec;
278 std::vector<int> eiVec;
280 m.edge[i].EFp() = Edges[i].f;
281 m.edge[i].EFi() = Edges[i].z;
285 if(tri::HasFEAdjacency(m))
287 for(
size_t i=0; i< Edges.size(); ++i)
289 std::vector<FacePointer> fpVec;
290 std::vector<int> eiVec;
292 for(
size_t j=0;j<fpVec.size();++j)
293 fpVec[j]->FEp(eiVec[j])=&(m.edge[i]);
322 RequireTTAdjacency(m);
323 ForEachTetra(m, [] (TetraType & t) {
324 for (
int i = 0; i < 4; ++i)
335 RequireTTAdjacency(m);
336 if (m.tn == 0)
return;
338 std::vector<PFace> fvec;
339 FillFaceVector(m, fvec);
340 std::sort(fvec.begin(), fvec.end());
343 typename std::vector<PFace>::iterator pback, pfront;
344 pback = fvec.begin();
345 pfront = fvec.begin();
349 if (pfront == fvec.end() || !(*pfront == *pback))
351 typename std::vector<PFace>::iterator q, q_next;
352 for (q = pback; q < pfront - 1; ++q)
357 assert((*q_next).z >= 0 && (*q_next).z < 4);
359 (*q).t->TTp(q->z) = (*q_next).t;
360 (*q).t->TTi(q->z) = (*q_next).z;
363 (*q).t->TTp(q->z) = pback->t;
364 (*q).t->TTi(q->z) = pback->z;
368 if (pfront == fvec.end())
break;
376 RequireFFAdjacency(m);
377 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
381 for(
int j=0;j<fi->VN();++j)
393 RequireFFAdjacency(m);
394 if( m.fn == 0 )
return;
396 std::vector<PEdge> e;
398 sort(e.begin(), e.end());
402 typename std::vector<PEdge>::iterator pe,ps;
403 ps = e.begin();pe=e.begin();
407 if( pe==e.end() || !(*pe == *ps) )
409 typename std::vector<PEdge>::iterator q,q_next;
410 for (q=ps;q<pe-1;++q)
416 assert((*q_next).z>=0);
417 assert((*q_next).z< (*q_next).f->VN());
418 (*q).f->FFp(q->z) = (*q_next).f;
419 (*q).f->FFi(q->z) = (*q_next).z;
422 assert((*q).z< (*q).f->VN());
423 (*q).f->FFp((*q).z) = ps->f;
424 (*q).f->FFi((*q).z) = ps->z;
428 if(pe==e.end())
break;
437 RequireVTAdjacency(m);
440 ForEachVertex(m, [] (VertexType & v) {
445 ForEachTetra(m, [] (TetraType & t) {
448 for (
int i = 0; i < 4; ++i)
450 t.VTp(i) = t.V(i)->VTp();
451 t.VTi(i) = t.V(i)->VTi();
467 RequireVFAdjacency(m);
469 for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
475 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
478 for(
int j=0;j<(*fi).VN();++j)
480 (*fi).VFp(j) = (*fi).V(j)->VFp();
481 (*fi).VFi(j) = (*fi).V(j)->VFi();
482 (*fi).V(j)->VFp() = &(*fi);
483 (*fi).V(j)->VFi() = j;
500 typename FaceType::TexCoordType v[2];
506 void Set( FacePointer pf,
const int nz )
513 v[1] = pf->WT(pf->Next(nz));
514 assert(v[0] != v[1]);
516 if( v[1] < v[0] ) std::swap(v[0],v[1]);
521 inline bool operator < (
const PEdgeTex & pe )
const
523 if( v[0]<pe.v[0] )
return true;
524 else if( pe.v[0]<v[0] )
return false;
525 else return v[1] < pe.v[1];
527 inline bool operator == (
const PEdgeTex & pe )
const
529 return (v[0]==pe.v[0]) && (v[1]==pe.v[1]);
531 inline bool operator != (
const PEdgeTex & pe )
const
533 return (v[0]!=pe.v[0]) || (v[1]!=pe.v[1]);
548 RequireFFAdjacency(m);
549 RequirePerFaceWedgeTexCoord(m);
551 for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
555 for (
int i = 0; i < (*fi).VN(); i++)
559 typename MeshType::FacePointer nextFace = (*fi).FFp(i);
560 int nextEdgeIndex = (*fi).FFi(i);
562 if ((*fi).cV(i) == nextFace->cV(nextEdgeIndex))
564 if ((*fi).WT(i) != nextFace->WT(nextEdgeIndex) || (*fi).WT((*fi).Next(i)) != nextFace->WT(nextFace->Next(nextEdgeIndex)))
569 if ((*fi).WT(i) != nextFace->WT(nextFace->Next(nextEdgeIndex)) || (*fi).WT((*fi).Next(i)) != nextFace->WT(nextEdgeIndex))
584 std::vector<int> numVertex(m.vert.size(),0);
586 tri::RequireVEAdjacency(m);
588 for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
592 assert(tri::IsValidPointer(m,ei->V(0)));
593 assert(tri::IsValidPointer(m,ei->V(1)));
594 if(ei->VEp(0)) assert(tri::IsValidPointer(m,ei->VEp(0)));
595 if(ei->VEp(1)) assert(tri::IsValidPointer(m,ei->VEp(1)));
596 numVertex[tri::Index(m,(*ei).V(0))]++;
597 numVertex[tri::Index(m,(*ei).V(1))]++;
601 for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
606 for(edge::VEIterator<EdgeType> vei(&*vi);!vei.End();++vei)
608 assert((numVertex[tri::Index(m,*vi)] == 0) == (vi->VEp()==0) );
609 assert(cnt==numVertex[tri::Index(m,*vi)]);
618 SimpleTempData<typename MeshType::VertContainer, int > numVertex(m.vert,0);
620 assert(tri::HasPerVertexVFAdjacency(m));
622 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
626 numVertex[(*fi).V0(0)]++;
627 numVertex[(*fi).V1(0)]++;
628 numVertex[(*fi).V2(0)]++;
632 vcg::face::VFIterator<FaceType> VFi;
634 for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
640 assert(tri::IsValidPointer(m, vi->VFp()));
646 assert(!VFi.F()->IsD());
647 assert((VFi.F()->V(VFi.I()))==&(*vi));
650 assert(num==numVertex[&(*vi)]);
658 assert(HasFFAdjacency(m));
660 for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
664 for (
int i=0;i<(*fi).VN();i++)
666 FaceType *ffpi=fi->FFp(i);
669 assert(ffpi->FFp(e) == &(*fi));
670 assert(ffpi->FFi(e) == i);
674 VertexPointer v0i= fi->V0(i);
675 VertexPointer v1i= fi->V1(i);
677 VertexPointer ffv0i= ffpi->V0(e);
678 VertexPointer ffv1i= ffpi->V1(e);
680 assert( (ffv0i==v0i) || (ffv0i==v1i) );
681 assert( (ffv1i==v0i) || (ffv1i==v1i) );
709 inline bool operator < (
const PVertexEdge & pe )
const {
return ( v<pe.v ); }
710 inline bool operator == (
const PVertexEdge & pe )
const {
return ( v==pe.v ); }
711 inline bool operator != (
const PVertexEdge & pe )
const {
return ( v!=pe.v ); }
716 static void EdgeEdge(MeshType &m)
718 RequireEEAdjacency(m);
719 std::vector<PVertexEdge> v;
720 if( m.en == 0 )
return;
723 for(EdgeIterator pf=m.edge.begin(); pf!=m.edge.end(); ++pf)
732 sort(v.begin(), v.end());
736 typename std::vector<PVertexEdge>::iterator pe,ps;
738 ps = v.begin();pe=v.begin();
742 if( pe==v.end() || !(*pe == *ps) )
744 typename std::vector<PVertexEdge>::iterator q,q_next;
745 for (q=ps;q<pe-1;++q)
751 assert((*q_next).z>=0);
752 assert((*q_next).z< 2);
753 (*q).e->EEp(q->z) = (*q_next).e;
754 (*q).e->EEi(q->z) = (*q_next).z;
758 (*q).e->EEp((*q).z) = ps->e;
759 (*q).e->EEi((*q).z) = ps->z;
763 if(pe==v.end())
break;
768 static void VertexEdge(MeshType &m)
770 RequireVEAdjacency(m);
772 for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
778 for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
782 { assert(tri::IsValidPointer(m,ei->V(j)));
783 (*ei).VEp(j) = (*ei).V(j)->VEp();
784 (*ei).VEi(j) = (*ei).V(j)->VEi();
785 (*ei).V(j)->VEp() = &(*ei);
786 (*ei).V(j)->VEi() = j;