VCG Library
complex/algorithms/update/topology.h
1 /****************************************************************************
2 * VCGLib o o *
3 * Visual and Computer Graphics Library o o *
4 * _ O _ *
5 * Copyright(C) 2004-2016 \/)\/ *
6 * Visual Computing Lab /\/| *
7 * ISTI - Italian National Research Council | *
8 * \ *
9 * All rights reserved. *
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 * This program is distributed in the hope that it will be useful, *
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
20 * for more details. *
21 * *
22 ****************************************************************************/
23 
24 #ifndef __VCG_TRI_UPDATE_TOPOLOGY
25 #define __VCG_TRI_UPDATE_TOPOLOGY
26 
27 namespace vcg {
28 namespace tri {
30 
32 
34 
35 template <class UpdateMeshType>
37 {
38 
39 public:
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 
52 
54 
56 
60 class PEdge
61 {
62 public:
63 
64  VertexPointer v[2]; // the two Vertex pointer are ordered!
65  FacePointer f; // the face where this edge belong
66  int z; // index in [0..2] of the edge of the face
67  bool isBorder;
68 
69  PEdge() {}
70  PEdge(FacePointer pf, const int nz) { this->Set(pf,nz); }
71  void Set( FacePointer pf, const int nz )
72  {
73  assert(pf!=0);
74  assert(nz>=0);
75  assert(nz<pf->VN());
76 
77  v[0] = pf->V(nz);
78  v[1] = pf->V(pf->Next(nz));
79  assert(v[0] != v[1]); // The face pointed by 'f' is Degenerate (two coincident vertexes)
80 
81  if( v[0] > v[1] ) std::swap(v[0],v[1]);
82  f = pf;
83  z = nz;
84  }
85 
86  inline bool operator < ( const PEdge & pe ) const
87  {
88  if( v[0]<pe.v[0] ) return true;
89  else if( v[0]>pe.v[0] ) return false;
90  else return v[1] < pe.v[1];
91  }
92 
93  inline bool operator == ( const PEdge & pe ) const
94  {
95  return v[0]==pe.v[0] && v[1]==pe.v[1];
96  }
99  inline Point3<ScalarType> EdgeBarycentricToFaceBarycentric(ScalarType u) const
100  {
101  Point3<ScalarType> interp(0,0,0);
102  interp[ this->z ] = u;
103  interp[(this->z+1)%3] = 1.0f-u;
104  return interp;
105  }
106 };
107 
111 
112 static void FillEdgeVector(MeshType &m, std::vector<PEdge> &edgeVec, bool includeFauxEdge=true)
113 {
114  edgeVec.reserve(m.fn*3);
115  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
116  if( ! (*fi).IsD() )
117  for(int j=0;j<(*fi).VN();++j)
118  if(includeFauxEdge || !(*fi).IsF(j))
119  edgeVec.push_back(PEdge(&*fi,j));
120 }
121 
122 static void FillUniqueEdgeVector(MeshType &m, std::vector<PEdge> &edgeVec, bool includeFauxEdge=true, bool computeBorderFlag=false)
123 {
124  FillEdgeVector(m,edgeVec,includeFauxEdge);
125  sort(edgeVec.begin(), edgeVec.end()); // oredering by vertex
126 
127  if (computeBorderFlag) {
128  for (size_t i=0; i<edgeVec.size(); i++)
129  edgeVec[ i ].isBorder = true;
130  for (size_t i=1; i<edgeVec.size(); i++) {
131  if (edgeVec[i]==edgeVec[i-1])
132  edgeVec[i-1].isBorder = edgeVec[i-1].isBorder = false;
133  }
134  }
135 
136  typename std::vector< PEdge>::iterator newEnd = std::unique(edgeVec.begin(), edgeVec.end());
137 
138  edgeVec.resize(newEnd-edgeVec.begin()); // redundant! remove?
139 }
140 
141 
147 static void AllocateEdge(MeshType &m)
148 {
149  // Delete all the edges (if any)
150  for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
153 
154  // Compute and add edges
155  std::vector<PEdge> Edges;
156  FillUniqueEdgeVector(m,Edges,true,tri::HasPerEdgeFlags(m) );
157  assert(m.edge.empty());
158  tri::Allocator<MeshType>::AddEdges(m,Edges.size());
159  assert(m.edge.size()==Edges.size());
160 
161  // Setup adjacency relations
162  if(tri::HasEVAdjacency(m))
163  {
164  for(size_t i=0; i< Edges.size(); ++i)
165  {
166  m.edge[i].V(0) = Edges[i].v[0];
167  m.edge[i].V(1) = Edges[i].v[1];
168  }
169  }
170 
171  if (tri::HasPerEdgeFlags(m)){
172  for(size_t i=0; i< Edges.size(); ++i) {
173  if (Edges[i].isBorder) m.edge[i].SetB(); else m.edge[i].ClearB();
174  }
175  }
176 
177  if(tri::HasEFAdjacency(m)) // Note it is an unordered relation.
178  {
179  for(size_t i=0; i< Edges.size(); ++i)
180  {
181  std::vector<FacePointer> fpVec;
182  std::vector<int> eiVec;
183  face::EFStarFF(Edges[i].f,Edges[i].z,fpVec,eiVec);
184  m.edge[i].EFp() = Edges[i].f;
185  m.edge[i].EFi() = Edges[i].z;
186  }
187  }
188 
189  if(tri::HasFEAdjacency(m))
190  {
191  for(size_t i=0; i< Edges.size(); ++i)
192  {
193  std::vector<FacePointer> fpVec;
194  std::vector<int> eiVec;
195  face::EFStarFF(Edges[i].f,Edges[i].z,fpVec,eiVec);
196  for(size_t j=0;j<fpVec.size();++j)
197  fpVec[j]->FEp(eiVec[j])=&(m.edge[i]);
198 
199 // Edges[i].f->FE(Edges[i].z) = &(m.edge[i]);
200 // Connect in loop the non manifold
201 // FaceType* fpit=fp;
202 // int eit=ei;
203 
204 // do
205 // {
206 // faceVec.push_back(fpit);
207 // indVed.push_back(eit);
208 // FaceType *new_fpit = fpit->FFp(eit);
209 // int new_eit = fpit->FFi(eit);
210 // fpit=new_fpit;
211 // eit=new_eit;
212 // } while(fpit != fp);
213 
214 
215 // m.edge[i].EFp() = Edges[i].f;
216 // m.edge[i].EFi() = ;
217  }
218  }
219 
220 }
221 
224 static void ClearFaceFace(MeshType &m)
225 {
226  RequireFFAdjacency(m);
227  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
228  {
229  if( ! (*fi).IsD() )
230  {
231  for(int j=0;j<fi->VN();++j)
232  {
233  fi->FFp(j)=0;
234  fi->FFi(j)=-1;
235  }
236  }
237  }
238 }
239 
241 static void FaceFace(MeshType &m)
242 {
243  RequireFFAdjacency(m);
244  if( m.fn == 0 ) return;
245 
246  std::vector<PEdge> e;
247  FillEdgeVector(m,e);
248  sort(e.begin(), e.end()); // Lo ordino per vertici
249 
250  int ne = 0; // Numero di edge reali
251 
252  typename std::vector<PEdge>::iterator pe,ps;
253  ps = e.begin();pe=e.begin();
254  //for(ps = e.begin(),pe=e.begin();pe<=e.end();++pe) // Scansione vettore ausiliario
255  do
256  {
257  if( pe==e.end() || !(*pe == *ps) ) // Trovo blocco di edge uguali
258  {
259  typename std::vector<PEdge>::iterator q,q_next;
260  for (q=ps;q<pe-1;++q) // Scansione facce associate
261  {
262  assert((*q).z>=0);
263  //assert((*q).z< 3);
264  q_next = q;
265  ++q_next;
266  assert((*q_next).z>=0);
267  assert((*q_next).z< (*q_next).f->VN());
268  (*q).f->FFp(q->z) = (*q_next).f; // Collegamento in lista delle facce
269  (*q).f->FFi(q->z) = (*q_next).z;
270  }
271  assert((*q).z>=0);
272  assert((*q).z< (*q).f->VN());
273  (*q).f->FFp((*q).z) = ps->f;
274  (*q).f->FFi((*q).z) = ps->z;
275  ps = pe;
276  ++ne; // Aggiorno il numero di edge
277  }
278  if(pe==e.end()) break;
279  ++pe;
280  } while(true);
281 }
282 
284 
291 static void VertexFace(MeshType &m)
292 {
293  RequireVFAdjacency(m);
294 
295  for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
296  {
297  (*vi).VFp() = 0;
298  (*vi).VFi() = 0; // note that (0,-1) means uninitiazlied while 0,0 is the valid initialized values for isolated vertices.
299  }
300 
301  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
302  if( ! (*fi).IsD() )
303  {
304  for(int j=0;j<(*fi).VN();++j)
305  {
306  (*fi).VFp(j) = (*fi).V(j)->VFp();
307  (*fi).VFi(j) = (*fi).V(j)->VFi();
308  (*fi).V(j)->VFp() = &(*fi);
309  (*fi).V(j)->VFi() = j;
310  }
311  }
312 }
313 
314 
316 
318 
322 class PEdgeTex
323 {
324 public:
325 
326  typename FaceType::TexCoordType v[2]; // the two TexCoord are ordered!
327  FacePointer f; // the face where this edge belong
328  int z; // index in [0..2] of the edge of the face
329 
330  PEdgeTex() {}
331 
332  void Set( FacePointer pf, const int nz )
333  {
334  assert(pf!=0);
335  assert(nz>=0);
336  assert(nz<3);
337 
338  v[0] = pf->WT(nz);
339  v[1] = pf->WT(pf->Next(nz));
340  assert(v[0] != v[1]); // The face pointed by 'f' is Degenerate (two coincident vertexes)
341 
342  if( v[1] < v[0] ) std::swap(v[0],v[1]);
343  f = pf;
344  z = nz;
345  }
346 
347  inline bool operator < ( const PEdgeTex & pe ) const
348  {
349  if( v[0]<pe.v[0] ) return true;
350  else if( pe.v[0]<v[0] ) return false;
351  else return v[1] < pe.v[1];
352  }
353  inline bool operator == ( const PEdgeTex & pe ) const
354  {
355  return (v[0]==pe.v[0]) && (v[1]==pe.v[1]);
356  }
357  inline bool operator != ( const PEdgeTex & pe ) const
358  {
359  return (v[0]!=pe.v[0]) || (v[1]!=pe.v[1]);
360  }
361 
362 };
363 
364 
366 
372 static void FaceFaceFromTexCoord(MeshType &m)
373 {
374  RequireFFAdjacency(m);
375  RequirePerFaceWedgeTexCoord(m);
377  for (FaceIterator fi = m.face.begin(); fi != m.face.end(); ++fi)
378  {
379  if (!(*fi).IsD())
380  {
381  for (int i = 0; i < (*fi).VN(); i++)
382  {
383  if (!vcg::face::IsBorder((*fi), i))
384  {
385  typename MeshType::FacePointer nextFace = (*fi).FFp(i);
386  int nextEdgeIndex = (*fi).FFi(i);
387  bool border = false;
388  if ((*fi).cV(i) == nextFace->cV(nextEdgeIndex))
389  {
390  if ((*fi).WT(i) != nextFace->WT(nextEdgeIndex) || (*fi).WT((*fi).Next(i)) != nextFace->WT(nextFace->Next(nextEdgeIndex)))
391  border = true;
392  }
393  else
394  {
395  if ((*fi).WT(i) != nextFace->WT(nextFace->Next(nextEdgeIndex)) || (*fi).WT((*fi).Next(i)) != nextFace->WT(nextEdgeIndex))
396  border = true;
397  }
398  if (border)
399  vcg::face::FFDetach((*fi), i);
400 
401  }
402  }
403  }
404  }
405 }
406 
408 static void TestVertexEdge(MeshType &m)
409 {
410  std::vector<int> numVertex(m.vert.size(),0);
411 
412  tri::RequireVEAdjacency(m);
413 
414  for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
415  {
416  if (!(*ei).IsD())
417  {
418  assert(tri::IsValidPointer(m,ei->V(0)));
419  assert(tri::IsValidPointer(m,ei->V(1)));
420  if(ei->VEp(0)) assert(tri::IsValidPointer(m,ei->VEp(0)));
421  if(ei->VEp(1)) assert(tri::IsValidPointer(m,ei->VEp(1)));
422  numVertex[tri::Index(m,(*ei).V(0))]++;
423  numVertex[tri::Index(m,(*ei).V(1))]++;
424  }
425  }
426 
427  for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
428  {
429  if (!vi->IsD())
430  {
431  int cnt =0;
432  for(edge::VEIterator<EdgeType> vei(&*vi);!vei.End();++vei)
433  cnt++;
434  EdgeType *vep = vi->VEp();
435  assert((numVertex[tri::Index(m,*vi)] == 0) == (vi->VEp()==0) );
436  assert(cnt==numVertex[tri::Index(m,*vi)]);
437  }
438  }
439 }
440 
441 
443 static void TestVertexFace(MeshType &m)
444 {
445  SimpleTempData<typename MeshType::VertContainer, int > numVertex(m.vert,0);
446 
447  assert(tri::HasPerVertexVFAdjacency(m));
448 
449  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
450  {
451  if (!(*fi).IsD())
452  {
453  numVertex[(*fi).V0(0)]++;
454  numVertex[(*fi).V1(0)]++;
455  numVertex[(*fi).V2(0)]++;
456  }
457  }
458 
459  vcg::face::VFIterator<FaceType> VFi;
460 
461  for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
462  {
463  if (!vi->IsD())
464  if(vi->VFp()!=0) // unreferenced vertices MUST have VF == 0;
465  {
466  int num=0;
467  assert(tri::IsValidPointer(m, vi->VFp()));
468  VFi.f=vi->VFp();
469  VFi.z=vi->VFi();
470  while (!VFi.End())
471  {
472  num++;
473  assert(!VFi.F()->IsD());
474  assert((VFi.F()->V(VFi.I()))==&(*vi));
475  ++VFi;
476  }
477  assert(num==numVertex[&(*vi)]);
478  }
479  }
480 }
481 
483 static void TestFaceFace(MeshType &m)
484 {
485  assert(HasFFAdjacency(m));
486 
487  for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
488  {
489  if (!fi->IsD())
490  {
491  for (int i=0;i<(*fi).VN();i++)
492  {
493  FaceType *ffpi=fi->FFp(i);
494  int e=fi->FFi(i);
495  //invariant property of FF topology for two manifold meshes
496  assert(ffpi->FFp(e) == &(*fi));
497  assert(ffpi->FFi(e) == i);
498 
499  // Test that the two faces shares the same edge
500  // Vertices of the i-th edges of the first face
501  VertexPointer v0i= fi->V0(i);
502  VertexPointer v1i= fi->V1(i);
503  // Vertices of the corresponding edge on the other face
504  VertexPointer ffv0i= ffpi->V0(e);
505  VertexPointer ffv1i= ffpi->V1(e);
506 
507  assert( (ffv0i==v0i) || (ffv0i==v1i) );
508  assert( (ffv1i==v0i) || (ffv1i==v1i) );
509  }
510 
511  }
512  }
513 }
514 
518 {
519 public:
520 
521  VertexPointer v; // the two Vertex pointer are ordered!
522  EdgePointer e; // the edge where this vertex belong
523  int z; // index in [0..1] of the vertex of the edge
524 
525  PVertexEdge( ) {}
526  PVertexEdge( EdgePointer pe, const int nz )
527 {
528  assert(pe!=0);
529  assert(nz>=0);
530  assert(nz<2);
531 
532  v= pe->V(nz);
533  e = pe;
534  z = nz;
535 }
536 inline bool operator < ( const PVertexEdge & pe ) const { return ( v<pe.v ); }
537 inline bool operator == ( const PVertexEdge & pe ) const { return ( v==pe.v ); }
538 inline bool operator != ( const PVertexEdge & pe ) const { return ( v!=pe.v ); }
539 };
540 
541 
542 
543 static void EdgeEdge(MeshType &m)
544 {
545  RequireEEAdjacency(m);
546  std::vector<PVertexEdge> v;
547  if( m.en == 0 ) return;
548 
549 // printf("Inserting Edges\n");
550  for(EdgeIterator pf=m.edge.begin(); pf!=m.edge.end(); ++pf) // Lo riempio con i dati delle facce
551  if( ! (*pf).IsD() )
552  for(int j=0;j<2;++j)
553  {
554 // printf("egde %i ind %i (%i %i)\n",tri::Index(m,&*pf),j,tri::Index(m,pf->V(0)),tri::Index(m,pf->V(1)));
555  v.push_back(PVertexEdge(&*pf,j));
556  }
557 
558 // printf("en = %i (%i)\n",m.en,m.edge.size());
559  sort(v.begin(), v.end()); // Lo ordino per vertici
560 
561  int ne = 0; // Numero di edge reali
562 
563  typename std::vector<PVertexEdge>::iterator pe,ps;
564  // for(ps = v.begin(),pe=v.begin();pe<=v.end();++pe) // Scansione vettore ausiliario
565  ps = v.begin();pe=v.begin();
566  do
567  {
568 // printf("v %i -> e %i\n",tri::Index(m,(*ps).v),tri::Index(m,(*ps).e));
569  if( pe==v.end() || !(*pe == *ps) ) // Trovo blocco di edge uguali
570  {
571  typename std::vector<PVertexEdge>::iterator q,q_next;
572  for (q=ps;q<pe-1;++q) // Scansione edge associati
573  {
574  assert((*q).z>=0);
575  assert((*q).z< 2);
576  q_next = q;
577  ++q_next;
578  assert((*q_next).z>=0);
579  assert((*q_next).z< 2);
580  (*q).e->EEp(q->z) = (*q_next).e; // Collegamento in lista delle facce
581  (*q).e->EEi(q->z) = (*q_next).z;
582  }
583  assert((*q).z>=0);
584  assert((*q).z< 2);
585  (*q).e->EEp((*q).z) = ps->e;
586  (*q).e->EEi((*q).z) = ps->z;
587  ps = pe;
588  ++ne; // Aggiorno il numero di edge
589  }
590  if(pe==v.end()) break;
591  ++pe;
592  } while(true);
593 }
594 
595 static void VertexEdge(MeshType &m)
596 {
597  RequireVEAdjacency(m);
598 
599  for(VertexIterator vi=m.vert.begin();vi!=m.vert.end();++vi)
600  {
601  (*vi).VEp() = 0;
602  (*vi).VEi() = 0;
603  }
604 
605  for(EdgeIterator ei=m.edge.begin();ei!=m.edge.end();++ei)
606  if( ! (*ei).IsD() )
607  {
608  for(int j=0;j<2;++j)
609  { assert(tri::IsValidPointer(m,ei->V(j)));
610  (*ei).VEp(j) = (*ei).V(j)->VEp();
611  (*ei).VEi(j) = (*ei).V(j)->VEi();
612  (*ei).V(j)->VEp() = &(*ei);
613  (*ei).V(j)->VEi() = j;
614  }
615  }
616 }
617 
618 }; // end class
619 
620 } // End namespace
621 } // End namespace
622 
623 
624 #endif